MD6

MD6
Creată 2008
publicat 2008
Dimensiunea hash variabilă, 0<d≤512
Numărul de runde variabil. Implicit, fără cheie=40+[d/4], cu cheie=max(80,40+(d/4))
Tip de funcția hash

MD6 ( Message Digest 6 ) este un  algoritm de hashing cu lungime variabilă dezvoltat de profesorul Ronald Rivest de la Massachusetts Institute of Technology în 2008 [1] . Conceput pentru a crea „amprente” sau rezumate de mesaje de lungime arbitrară. Propus pentru a înlocui MD5 mai puțin avansat . Potrivit autorilor, algoritmul este rezistent la criptoanaliza diferențială. Folosit pentru a verifica integritatea și, într-un fel, autenticitatea mesajelor publicate prin compararea rezumatului mesajului cu mesajul publicat. Această operație se numește verificare hash. Funcțiile hash sunt, de asemenea, utilizate pe scară largă pentru a genera chei cu lungime fixă ​​pentru algoritmii de criptare bazați pe un șir de chei dat.

Istorie

MD6 este unul dintr-o serie de algoritmi de rezumare a mesajelor dezvoltate de profesorul Ronald L. Rivest de la Massachusetts Institute of Technology. MD6 a fost prezentat pentru prima dată la conferința Crypto 2008 ca candidat pentru standardul SHA-3 . Cu toate acestea, mai târziu în 2009, la aceeași conferință, Rivest a declarat că MD6 nu era încă pregătit să devină un standard. Pe site-ul oficial MD6, acesta a declarat că, deși aplicația nu este retrasă oficial, algoritmul are încă probleme cu viteza și incapacitatea de a oferi securitate în versiunea cu un număr redus de runde [2] . Drept urmare, MD6 nu s-a calificat în turul doi al competiției. Anterior, în decembrie 2008, un cercetător de la Fortify Software a descoperit o eroare de depășire a tamponului în implementarea originală MD6. Pe 19 februarie 2009, profesorul Rivest a publicat detaliile acestui bug și a furnizat și o remediere de implementare [3] .

Algoritm

Algoritmul funcției hash folosește câteva idei foarte originale. Într-o singură trecere, sunt procesați 512 octeți, ceea ce face dificilă efectuarea unui număr de atacuri și facilitează paralelizarea, care este folosită și pentru structurile arborescente.

Date de intrare și proceduri

M mesaj original de lungime m , 1 ≤ m ≤ (2 64 - 1) biți
d lungimea hash-ului rezultat în biți, 1 ≤ d ≤ 512
K valoare cheie arbitrară a lungimii keylen octeți (0 ≤ keylen ≤ 64), completată cu zerouri în partea dreaptă cu un număr de 64 - keylen
L parametru nenegativ de 1 octet, 0 ≤ L ≤ 64 (implicit L = 64), indicând numărul de calcule paralele și adâncimea arborelui
r Parametru nenegativ pe 12 biți: numărul de runde (implicit r = 40 + [ d /4])
Q o matrice de 15 elemente de 8 octeți, valoarea acestuia este dată mai jos
ƒ Funcție de compresie MD6 care convertește 712 de octeți de date de intrare (inclusiv blocul B de 512 de octeți) în rezultatul C de 128 de octeți folosind r runde de evaluare
PAR operație de micșorare paralelă pentru fiecare nivel de arbore, niciodată apelată când L = 0
SECV operație de compresie în serie, niciodată apelată când L = 64
Q = {0x7311c2812425cfa0, 0x6432286434aac8e7, 0xb60450e9ef68b7c1, 0xe8fb23908d9f06f1, 0xdd2e76cba691e5bf, 0x0cd0d63b2c30bc41, 0x1f8ccf6823058f8a, 0x54e5ed5b88e3775d, 0x4ad12aae0a6d6031, 0x3e7f16bb88222e0d, 0x8af8671d3fb50c2c, 0x995ad1178bd25c31, 0xc878c1dd04c4b633, 0x3b72066c7a1552ac, 0x0d6f3522631effcb}

matrice Q

Procedura de bază

Inițializare

Se notează l = 0, M 0 = M , m 0 = m .

Bucla principală
  • l = l + 1.
  • Dacă l = L + 1, returnează SEQ( M l-1 , d , K , L , r ) ca rezultat.
  • Ml = PAR( Ml -1 , d , K , L , r , l ) . Notați m l ca lungimea lui M l în biți.
  • Dacă m l = 8 * c (adică M l are 8 * c octeți), returnează ultimii d biți ai lui M l . În caz contrar, revenim la începutul ciclului.

Operațiunea PAR

PAR returnează un mesaj cu lungimea m l = 1024 * max(1, [ m l-1 / 4096])

Organul procedurii
  • Dacă este necesar, extindeți M l-1 , adăugând zero biți la dreapta, până când lungimea sa devine un multiplu de 512 octeți. Acum să împărțim M l-1 în blocuri B 0 , B 1 , …, B j-1 , unde j = max(1, [ m l-1 / 512]);
  • Pentru fiecare bloc B i , i = 0, 1, …, j - 1, calculăm C i în paralel conform următorului algoritm:
  • Fie p să desemneze numărul de biți adăugați B i , 0 ≤ p ≤ 4096. ( p este întotdeauna mai mare decât zero pentru i = j - 1.);
  • Notăm z = 1 dacă j = 1, în caz contrar z = 0;
  • Notați V ca o valoare de 8 octeți r ǁ L ǁ z ǁ p ǁ keylen ǁ d astfel:
  • 4 biți de zerouri;
  • 12 biți r ;
  • 8 biți L ;
  • 4 biți z ;
  • 16 biți p ;
  • Keylen pe 8 biți .
  • 12 biți d .
  • Să notăm U = l * 2 56 + i – identificatorul unic de 8 octeți al blocului curent;
  • C i = ƒ( Q ǁ K ǁ U ǁ V ǁ B i ).
  • Se întoarce M l = C 0 ǁ C 1 ǁ … ǁ C j-1 .

Operațiunea SEQ

SEQ returnează un hash de lungime d biți. Această operație nu este niciodată numită dacă L = 64.

Organul procedurii
  • Fie C -1 să desemneze un vector nul cu lungimea de 128 de octeți.
  • Dacă este necesar, extindem ML , adăugând zero biți la dreapta, până când lungimea sa devine un multiplu de 384 de octeți. Acum să împărțim M L în blocuri B 0 , B 1 , …, B j-1 , unde j = max(1, [ m L / 384]).
  • Pentru fiecare bloc B i , i = 0, 1, …, j - 1, calculăm C i în paralel conform următorului algoritm:
  • Fie p să desemneze numărul de biți adăugați Bi , 0 ≤ p ≤ 3072. ( p este întotdeauna mai mare decât zero pentru i = j - 1.);
  • Notăm z = 1 dacă i = j - 1, în caz contrar z = 0;
  • Notați V ca o valoare de 8 octeți r ǁ L ǁ z ǁ p ǁ keylen ǁ d în același mod ca în operația anterioară;
  • Se notează U = ( L + 1) * 2 56 + i – identificatorul unic de 8 octeți al blocului curent;
  • C i = ƒ( Q ǁ K ǁ U ǁ V ǁ C i-1 ǁ B i ).
  • Returnăm ultimii d biți ai valorii C j-1 ca hash final.

Funcția de compresie MD6

Date de intrare și de ieșire

Funcția ia ca intrare un tablou N , format din n = 89 cuvinte de 8 octeți (712 octeți) și numărul de runde r .
Funcția returnează o matrice C de 16 elemente de 8 octeți.

Constante
t0 _ t1 _ t2 _ t3 _ t4 _
17 optsprezece 21 31 67
( i - n ) mod 16 0 unu 2 3 patru 5 6 7 opt 9 zece unsprezece 12 13 paisprezece cincisprezece
r i-n zece 5 13 zece unsprezece 12 2 7 paisprezece cincisprezece 7 13 unsprezece 7 6 12
l i-n unsprezece 24 9 16 cincisprezece 9 27 cincisprezece 6 2 29 opt cincisprezece 5 31 9

S i-n = S | (in)/
16S | 0 = 0x0123456789abcde
S* = 0x7311c2812425cfa0
S | j+1 = ( S | j <<< 1) ⊕ ( S | j ^ S*)

Corpul funcției

Se notează t = 16 r . (Vor fi 16 pași în fiecare rundă)
Fie A [0.. t + n - 1] o matrice de t + n elemente de 8 octeți. Primele n elemente trebuie copiate din tabloul de intrare N .

Bucla funcției principale arată astfel:
pentru i = n la t + n - 1: /* t pași */

x = S i-n ⊕ A i-n ⊕ A i-t 0 x = x ⊕ (A i-t 1 ^ A i-t 2 ) ⊕ (A i-t 3 ^ A i-t 4 ) x = x ⊕ (x >> r i-n ) Ai = x ⊕ (x << l i-n )

Returnează A [ t + n - 16 .. t + n - 1].

Note

  1. ↑ Ronald L. Rivest, Funcția hash MD6 O propunere către NIST pentru SHA-3 Arhivată la 9 noiembrie 2020 la Wayback Machine
  2. ↑ Schneier, Bruce MD6 Retras de la SHA-3 Competition (link indisponibil) (1 iulie 2009). Preluat la 9 iulie 2009. Arhivat din original la 21 martie 2012. 
  3. ↑ Copie arhivată (link nu este disponibil) . Data accesului: 28 noiembrie 2010. Arhivat din original la 22 februarie 2012. 

Link -uri

 Funcții hash
scop general
Criptografic
Funcții de generare a cheilor
Numărul de verificare ( comparație )
Hashes