Grostl

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 15 iunie 2015; verificările necesită 10 modificări .
Grostl
Dezvoltatori Soren Stefan Thompson, Lars Knudsen , Martin Schlaffer, Christian Rechberger, Florian Mendel, Christian Matusevich, Praaven Gauravaram
Dimensiunea hash 224, 256, 384, 512 (variabil, 8-512 biți)
Numărul de runde 9 (recomandat)
Tip de funcția hash

Grøstl ( Groestl ) este o funcție hash criptografică iterativă . Unul dintre cei cinci finaliști în competiția SHA-3 organizată de NIST . Funcția de contracție Grøstl constă din două permutări fixe de 2n biți P și Q, a căror structură este împrumutată din cifrul AES . În special, este folosită aceeași S-box . Rezultatul funcției hash poate avea o lungime de la 8 la 512 biți cu un pas de 8 biți. Varianta care returnează n biți se numește Grøstl-n.

Istorie

Algoritmul Grøstl a fost conceput special pentru competiția de funcții criptografice SHA-3 de o echipă de criptografi [1] de la Universitatea Tehnică Daneză . Funcția a fost inițial numită Grøstl-0. Cu toate acestea, diferențele structurale dintre permutări au fost crescute pentru a se califica în finală. Au fost modificate valorile ShiftBytes în permutarea Q. Au fost modificate și constantele rotunde din P și Q. Funcția hash actualizată a fost numită Grøstl. Cu toate acestea, după ce a demonstrat o putere criptografică bună , a fost inferior celorlalți participanți în runda finală într-un număr de indicatori și nu a putut deveni un câștigător.

Originea numelui

Gröstl  este un fel de mâncare austriac . Rețeta este foarte apropiată de felul de mâncare numit „Hash” în SUA . Litera „ö” din numele funcției a fost înlocuită cu litera „ø” din alfabetul danez, care are aceeași pronunție.

Caracteristici

Grøstl este o rețea SP orientată pe octeți . În structura sa, diferă semnificativ de algoritmii familiei SHA. Multe componente ale funcției hash sunt împrumutate de la cifrul AES. La fel ca AES, permutările sunt dezvoltate folosind strategia de proiectare Wide Trail , ale cărei principii principale sunt că cifrul bloc are :

Dimensiunea stării interne a funcției este mult mai mare decât dimensiunea datelor de ieșire. Aceasta este așa-numita „construcție cu țevi late”.

Algoritm

În primul rând, mesajul este împărțit în blocuri , ,…, fiecare bit cu bit. Pentru variantele de funcție care returnează până la 256 de biți = 512. Pentru variantele care returnează valori mari = 1024.

Apoi, o funcție hash este construită folosind o metodă de calcul recurentă. Fiecare bloc este procesat secvenţial de o funcţie de compresie conform formulei , .

, ,…,  este așa-numita intrare de înlănțuire.

Valoarea inițială = .

După procesarea ultimului bloc, valoarea -bit este introdusă în funcția de transformare Ω , care returnează un mesaj de lungime , astfel încât ≤ .

Astfel, rezultatul funcției hash Ω

Valoarea inițială

Valoarea inițială a funcției Grøstl-n i se atribuie o reprezentare -bit a numărului n. Tabelul arată valorile inițiale pentru diferite funcții hash.

224 00…00 00 e0
256 00...00 01 00
384 00...00 01 80
512 00...00 02 00

funcția pad

Pentru a lucra cu mesaje de lungime arbitrară, utilizați funcția . Acesta convertește un mesaj de lungime arbitrară într-un mesaj cu o lungime care este un multiplu de . Pentru a face acest lucru, la mesaj se adaugă mai întâi un bit cu valoarea 1. Apoi se adaugă zero biți, unde . Și, în final, se adaugă o reprezentare pe 64 de biți a numărului . Același număr determină numărul de blocuri în care va fi împărțit mesajul.

Funcția de contracție

Funcția de comprimare sau funcția de compresie constă din permutări de doi biți și și este definită ca .

Transformare de ieșire

Funcția de transformare de ieșire este definită ca Ω , unde  este o funcție care returnează ultimii biți ai valorii de intrare .

Permutările lui P și Q

Funcția de compresie Grøstl poate funcționa cu mesaje scurte (512 biți) și mesaje lungi (1024 biți). În consecință, există 4 permutări , și , .

Fiecare permutare este efectuată în runde, în fiecare dintre acestea fiind efectuate 4 transformări runde:

Aceste transformări controlează starea, care este reprezentată de o matrice A care conține 1 octet de informații în fiecare celulă. Pentru a lucra cu rezumate de mesaje scurte, matricea are o dimensiune de 8X8, pentru rezumate lungi - 8X16.

În primul rând, matricea A este umplută cu o secvență de octeți. De exemplu, pentru secvența 00 01 02 … 3f matricea A arată astfel.

Matricea 8 X 16 este umplută în același mod.

În continuare, se efectuează transformări rotunde pe matricea A.

AddRoundConstant

Această transformare realizează o operație XOR între matricea de stări și o constantă specifică rotundei: A←A , unde  este o constantă specifică rotunjii. Aceste constante sunt diferite pentru fiecare permutare a lui P și Q:

512

1024

512

1024

unde este numărul rotund reprezentat de o valoare de 8 biți.

Subocteți

Această transformare înlocuiește fiecare octet al matricei de stare cu o valoare luată din S-box. Funcția hash Grøstl folosește aceeași casetă S ca și cifrul AES. Prin urmare, transformarea arată astfel: ← , unde  este un element al matricei A. Și S-box arată astfel:


00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
00 63 7c 77 7b f2 6b 6f c5 treizeci 01 67 2b fe d7 ab 76
zece ca 82 c9 7d fa 59 47 f0 anunț d4 a2 af 9c a4 72 c0
douăzeci b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 cincisprezece
treizeci 04 c7 23 c3 optsprezece 96 05 9a 07 12 80 e2 eb 27 b2 75
40 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
cincizeci 53 d1 00 ed douăzeci fc b1 5b 6a cb fi 39 4a 4c 58 cf
60 d0 ef aa fb 43 4d 33 85 45 f9 02 7f cincizeci 3c 9f a8
70 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 zece ff f3 d2
80 CD 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
90 60 81 4f DC 22 2a 90 88 46 ee b8 paisprezece de 5e 0b db
a0 e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b0 e7 c8 37 6d 8 D d5 4e a9 6c 56 f4 ea 65 7a ae 08
c0 ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d0 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e0 e1 f8 98 unsprezece 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f0 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16


Transformarea caută elementele din prima coloană și elementul din primul rând.(  este un „sau”) logic. Ieșirea este elementul situat la intersecția lor.


ShiftBytes(ShiftBytesWide)

Fie α=[α 1 , α 2 ,…, α 7 ] o mulțime de numere întregi de la 1 la 7. Transformarea ShiftBytes rotește toți octeții din rândul i a matricei de stare A cu pozițiile α i la stânga. Pentru permutările P și Q, aceste seturi de numere sunt diferite:

  • P 512 : α=[0,1,2,3,4,5,6,7]
  • Q 512 : α=[1,3,5,7,0,2,4,6]

În consecință, pentru funcția ShiftBytesWide:

  • P 1024 : a=[0,1,2,3,4,5,6,11]
  • Q 1024 : α=[1,3,5,11,0,2,4,6]


MixBytes

Cu această transformare, fiecare coloană a matricei A este înmulțită cu o matrice constantă B într-un câmp finit . Matricea B este definită ca

Transformarea MixBytes poate fi notată ca: A←B A.

Securitate

Fiabilitatea unei funcții hash depinde direct de numărul de runde. Ca rezultat al criptoanalizei, a fost posibil să se producă doar primele 3 runde. Tabelul arată câteva dintre rezultatele criptoanalizei efectuate în runda finală a concursului de funcție hash SHA-3:

Ținta atacului Tip de atac Numărul de biți de ieșire numărul de runde Numărul de operații
funcția hash găsirea coliziunilor 224, 256 3 264 _
funcția hash găsirea coliziunilor 512 3 2192 _
Funcția de compresie găsirea coliziunilor parțiale 256 6 2 120
Funcția de compresie găsirea coliziunilor parțiale 384 6 2 180
Funcția de compresie găsirea coliziunilor parțiale 512 6 2 180
Permutare proprietate diferenţială 256 9 2368 _
Permutare proprietate diferenţială 512 opt 2280 _
Permutare proprietate diferenţială 512 9 2328 _
Permutare proprietate diferenţială 512 zece 2392 _
transformarea ieșirii Găsirea prototipului 256 6 2251 _
transformarea ieșirii Găsirea prototipului 256 5 2206 _
transformarea ieșirii Găsirea prototipului 512 opt 2495 _
funcția hash găsirea unei pseudo-preimagine 256 5 2245 _
funcția hash găsirea unei pseudo-preimagine 512 opt 2507 _

Performanță

Implementarea software a lui Grøstl este concepută în principal pentru un procesor pe 64 de biți, dar este posibil să se lucreze și pe procesoare pe 32 de biți. În timpul testelor desfășurate în finala competiției NIST, performanța funcției hash a fost cea mai scăzută în comparație cu ceilalți participanți la competiție. Cu toate acestea, la executarea algoritmului pe un microcontroler, viteza de funcționare a acestuia s-a dovedit a fi mult mai mare decât cea a concurenților. Tabelul arată viteza implementărilor software ale diferitelor versiuni ale funcției.

CPU Varianta caracteristică Viteza (ciclu/octet)
Intel Core i7 M620 Grøstl-224/256 12.45
Intel Core i7 M620 Grøstl-384/512 17.85


Următorul tabel arată implementarea pe 8 biți pe microcontrolerul ATmega 163.

funcția hash CPU Memorie Viteza (ciclu/octet)
Grøstl-256 ATmega163 994 469
Grøstl-256 ATmega163 226 531
Grøstl-256 ATmega163 164 760

Exemple de hash Grøstl

Valorile diferitelor variante hash dintr-un șir gol.

Grøstl-224("") 0x f2e180fb5947be964cd584e22e496242c6a329c577fc4ce8c36d34c3 Grøstl-256("") 0x 1a52d11d550039be16107f9c58db9ebcc417f16f736adb2502567119f0083467 Grøstl-384("") 0x ac353c1095ace21439251007862d6c62f829ddbe6de4f78e68d310a9205a736d8b11d99bffe448f57a1cfa2934f044a5 Grøstl-5 0x 6d3ad29d279110eef3adbd66de2a0345a77baede1557f5d099fce0c03d6dc2ba8e6d4a6633dfbd66053c20faa87d1a11f39a8081f04a96082f040000000

O mică modificare a mesajului poate duce la o modificare mare a valorii hash din cauza efectului de avalanșă , așa cum se arată în exemplul următor:

Grøstl-256 ("Vulpea maro iute sare peste câinele leneș") 0x 8c7ad62eb26a21297bc39c2d7293b4bd4d3399fa8afab29e970471739e28b301 Grøstl-256(„Vulpea maro iute sare peste câinele leneș”) 0x f48290b1bcacee406a0429b993adb8fb3d065f4b09cbcdb464a631d4a0080aaf Grøstl-512 ("Vulpea maro iute sare peste câinele leneș") 0x badc1f70ccd69e0cf3760c3f93884289da84ec13c70b3d12a53a7a8a4a513f99715d46288f55e1dbf926e6d084a0538e6d084a0538e6d084a0538e614eeebst2c91429292c91429292c91429292000 0x 518a55cc274fc887d8dcbd0bb24000395f6d3be62445d84cc9e85d419161a968268e490f7537e475e57d8c009b095702caaccd58202caaccd5820cabcd58

Note

  1. ↑ Funcția hash Grøstl - candidat SHA-3 . Consultat la 13 decembrie 2013. Arhivat din original la 11 octombrie 2013.

Link -uri

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