Luffa (funcția hash)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 aprilie 2014; verificările necesită 16 modificări .
Luffa
Dezvoltatori Dai Watanabe, Hisayoshi Sato, Christophe De Canniere
Creată 2008
publicat 2008
Dimensiunea hash 224, 256, 384, 512
Tip de funcția hash

Lúffa [1] (funcția hash, pronunțată „luffa”) este un algoritm criptografic (familie de algoritmi) pentru hashing cu lungime variabilă de biți, dezvoltat de Dai Watanabe ,  Hisayoshi Sato de la Hitachi  Yokohama Research Laboratory și Christophe De Cannière ( Niderl. Christophe De Cannière) . ) de la grupul de cercetare COSIC ( en: COSIC ) al Universității Catolice din Leuven pentru a participa la competiția [2] , Institutul Național de Standarde și Tehnologie din SUA ( NIST ). Lúffa este o variantă a funcției burete propusă de Guido Bertoni și colab., a cărei putere criptografică se bazează doar pe aleatorietatea permutației subiacente . Spre deosebire de funcția originală de burete , Lúffa utilizează mai multe permutări paralele și funcții de injectare a mesajelor.   

Istoricul participării la competiția NIST SHA-3 [2]

Algoritmul Lúffa [6]

Prelucrarea mesajelor este realizată de un lanț de funcții de amestecare rotunde cu o lungime fixă ​​de intrare și ieșire, care este o funcție de burete . Lanțul este format din blocuri intermediare de amestecare C' (funcții rotunde) și un bloc de completare C''. Funcțiile rotunde sunt formate dintr-o familie de permutări neliniare, așa-numitele funcții pas. Introducerea funcției din prima rundă este : primul bloc al mesajului și valorile de inițializare , unde  este numărul de permutări. Parametrii de intrare ai rundei --a sunt : ​​ieșirea rundei anterioare și blocul de mesaje --lea .

Completarea mesajului

Adăugarea unui mesaj cu lungime de până la un multiplu de 256 de biți se realizează prin șir , unde numărul de zerouri este determinat din comparație.

Inițializare

În plus față de primul bloc al mesajului , vectorii sunt dați ca valori de inițializare la intrarea funcției din prima rundă .

i j
0 unu 2 3 patru 5 6 7
0 0x6d251e69 0x44b051e0 0x4eaa6fb4 0xdbf78465 0x6e292011 0x90152df4 0xee058139 0xdef610bb
unu 0xc3b44b95 0xd9d2f256 0x70eee9a0 0xde099fa3 0x5d9b0557 0x8fc944b3 0xcf1ccf0e 0x746cd581
2 0xf7efc89d 0x5dba5781 0x04016ce5 0xad659c05 0x0306194f 0x666d1836 0x24aa230a 0x8b264ae7
3 0x858075d5 0x36d79cce 0xe571f7d7 0x204b1f67 0x35870c6a 0x57e9e923 0x14bcb808 0x7cde72ce
patru 0x6c68e9be 0x5ec41e22 0xc825b7c7 0xaffb4363 0xf5df3999 0x0fc688f1 0xb07224cc 0x03e86cea

Funcția rotundă

Funcția rotundă este o aplicare secvențială a funcției de injectare a mesajului MI și a funcției de permutare P.

Funcții de injectare a mesajelor

Funcția de injectare a mesajului poate fi reprezentată ca o matrice de transformare peste un inel . Polinom generator de câmp .

Funcții de injectare a mesajelor

unde numerele denotă respectiv polinoamele

Funcții de injectare a mesajelor

Funcții de injectare a mesajelor

Funcția de permutare

Funcția de permutare neliniară are un bit de intrare, lungimea sub-permutației este fixată în specificația Lúffa [6] , ; numărul de permutări depinde de dimensiunea hashului și este prezentat în tabel.

Lungimea hash Numărul de permutări
224 3
256 3
384 patru
512 5

Funcția de permutare este o iterație de 8 ori a funcției de trecere peste blocul obținut din funcția de injectare a mesajului . Blocul este reprezentat ca 8 cuvinte pe 32 de biți: . Funcția de pas constă din 3 funcții: SubCrumb, MixWord, AddConstant.

Permutare(a[8], j){ //Permutare Q_j pentru (r = 0; r < 8; r++){ SubCrumb(a[0],a[1],a[2],a[3]); SubCrumb(a[5],a[6],a[7],a[4]); pentru (k = 0; k < 4; k++) MixWord(a[k],a[k+4]); AddConstant(a, j, r); } } SubCrumb

SubCrumb  este funcția de înlocuire a biților l-i în sau de-a lungul cutiei S , rezultatul execuției este înlocuirea , indicele casetei S se obține prin concatenarea biților corespunzători : , biții sunt înlocuiți cu biții corespunzători din la următoarea schemă:

MixWord

MixWord  este o funcție de permutare liniară, ia și , ca intrare ; ieșirile sunt și , obținute de algoritmul:

  1. , (<<< 2 - rotiți la stânga cu 2 biți)
AddConstant

AddConstant - funcție pentru a  adăuga o constantă

Un tabel de constante este dat în anexa B la specificația Lúffa [6] .

Bloc de completare

Etapa finală a formării rezumatului mesajului constă în iterații succesive ale funcției de ieșire și ale funcției rotunde cu un bloc de mesaj zero 0x00 0 la intrare. Funcția de ieșire este un XOR al tuturor valorilor intermediare, iar rezultatul este un cuvânt de 256 de biți . La i -a iterație, valoarea funcției de ieșire este determinată ca

, unde , dacă , altfel

Indicați prin cuvinte de 32 de biți în , apoi rezultatele lui Lúffa sunt compuse secvenţial . Simbolul „||” reprezintă concatenare.

Lungimea hash Valoare hash
224
256
384
512

Hash-ul Lúffa-224 este de fapt hash-ul Lúffa-256 fără ultimul cuvânt de 32 de biți.

Vectori de testare [6]

Rezumate ale mesajului „abc” la diferite dimensiuni hash .

224 256 384 512
Z0.0 _ 0xf29311b8 0xf29311b8 0x9a7abb79 0xf4024597
Z0.1 _ 0x7e9e40de 0x7e9e40de 0x7a840e2d 0x3e80d79d
Z0.2 _ 0x7699be23 0x7699be23 0x423c34c9 0x0f4b9b20
Z 0,3 0xfbeb5a47 0xfbeb5a47 0x1f559f68 0x2ddd4505
Z0.4 _ 0xcb16ea4f 0xcb16ea4f 0x09bdb291 0xb81b8830
Z0.5 _ 0x5556d47c 0x5556d47c 0x6fb2e9ef 0x501bea31
Z0.6 _ 0xa40c12ad 0xa40c12ad 0xfec2fa0a 0x612b5817
Z 0,7 0x764a73bd 0x7a69881b 0xaae38792
Z 1,0 0xe9872480 0x1dcefd80
Z 1.1 0xc635d20d 0x8ca2c780
Z 1.2 0x2fd6e95d 0x20aff593
Z 1.3 0x046601a7 0x45d6f91f
Z 1.4 0x0ee6b2ee
Z 1,5 0xe113f0cb
Z 1,6 0xcf22b643
Z 1,7 0x81387e8a

Criptanaliză

În timpul celei de-a doua runde a concursului SHA-3 , Luffa-224 și Luffa-256 au arătat inițial o putere criptografică scăzută, iar mesajele au fost necesare pentru un atac de succes. După aceea, algoritmul a fost modificat de Dai Watanabe și a fost numit Luffa v.2. Luffa v.2 [5] modificări :

  • a adăugat funcția de completare a rotundelor goale pentru toate dimensiunile hash
  • S-block schimbat
  • a crescut numărul de repetări ale funcției pasului de la 7 la 8

Bart Preneel a prezentat un atac cu succes de detectare a coliziunilor [7] pentru 4 runde ale funcției de pas Luffa pentru operațiuni de hashing și pentru 5 runde, arătând astfel rezistența de proiectare la detectarea coliziunii diferențiale.

Performanță

În 2010, Thomas Oliviera și Giulio Lopez au efectuat cercetări de succes [8] cu privire la posibilitatea de a crește performanța implementării originale a Luffa. Implementarea optimizată a algoritmului are o creștere a performanței cu 20% în calculul hash-ului Luffa-512 atunci când este executat într-un fir; pentru Luffa-256/384, câștigul de performanță al implementării cu un singur thread în diferite teste nu este mai mare de 5%. Rezultatele testului sunt prezentate în tabel în cicluri pe octet :

  • Pe platforme pe 64 de biți fără SSE:
Implementarea algoritmului Luffa-256 Luffa-384 Luffa-512
Implementare inițială 2009
Implementare cu un singur fir 27 42 58
Thomas Oliviera 2010
Implementare cu un singur fir 24 42 46
Implementare cu mai multe fire douăzeci 24 36
  • Folosind SSE:
Implementarea algoritmului Luffa-256 Luffa-384 Luffa-512
Implementare inițială 2009
Implementare cu un singur fir 17 19 treizeci
Thomas Oliviera 2010
Implementare cu un singur fir cincisprezece 16 24
Implementare cu mai multe fire cincisprezece optsprezece 25

Pentru comparație, implementarea lui Keccak (câștigătorul concursului SHA-3 ) în teste [9] pe un procesor similar folosind SSE a arătat următoarele rezultate: Keccak-256 - 15 c/b, Keccak-512 - 12 c/b .

Note

  1. ^ The Hash Function Family Luffa . Consultat la 22 noiembrie 2013. Arhivat din original la 28 decembrie 2013.
  2. 12 Competiția NIST sha-3 . Consultat la 22 noiembrie 2013. Arhivat din original pe 9 iulie 2011.
  3. 1 2 Candidați din turul al doilea . Consultat la 28 decembrie 2013. Arhivat din original la 10 aprilie 2012.
  4. A doua conferință de candidați SHA-3 . Consultat la 28 decembrie 2013. Arhivat din original la 12 ianuarie 2014.
  5. 1 2 Raport de stare privind a doua rundă a SHA-3 . Consultat la 28 decembrie 2013. Arhivat din original la 14 martie 2011.
  6. 1 2 3 4 Specificația Luffa V.2.01 . Consultat la 29 noiembrie 2013. Arhivat din original pe 20 februarie 2013.
  7. Găsirea coliziunilor pentru Reduced Luffa-256 v2 . Data accesului: 4 ianuarie 2014. Arhivat din original pe 20 februarie 2013.
  8. Îmbunătățirea performanței algoritmului Luffa Hash . Preluat la 28 decembrie 2013. Arhivat din original la 21 martie 2014.
  9. Familia de funcții de burete Keccak: Performanță software . Data accesului: 4 ianuarie 2014. Arhivat din original pe 4 ianuarie 2014.

Literatură

Link -uri