SHA-3

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 3 ianuarie 2016; verificările necesită 57 de modificări .
SHA-3, Keccak
Dezvoltatori Guido Bertoni, Joan Dymen , Mikael Pieters, Gilles Van Asche
Creată 2008
publicat 2008
Predecesor SHA-2
Dimensiunea hash 224, 256, 384, 512 (variabilă, 0<d≤2 64 -1)
Numărul de runde 24 (implicit)
Tip de funcția hash

SHA-3 ( keccak  - pronunțat „kechak”) este un algoritm de hashing cu lungime variabilă dezvoltat de un grup de autori condus de Joan Dymen , co-autor al cărții Rijndael , autor al cifrurilor MMB , SHARK , Noekeon , SQUARE și BaseKing . Pe 2 octombrie 2012, Keccak a devenit câștigătorul Concursului de algoritm criptografic susținut de Institutul Național de Standarde și Tehnologie din SUA [1] . La 5 august 2015, algoritmul a fost aprobat și publicat ca standard FIPS 202 [2] [3] . În implementarea software-ului, autorii pretind 12,5 cicluri pe octet atunci când sunt executate pe un PC cu un procesor Intel Core 2 . Cu toate acestea, în implementările hardware, Keccak s-a dovedit a fi mult mai rapid decât toți ceilalți finaliști. [patru]

Algoritmul SHA-3 este construit pe principiul unui burete criptografic (această structură de algoritmi criptografici a fost propusă anterior de autorii algoritmului Keccak) [5] .

Istorie

În 2004-2005, mai mulți algoritmi de hashing au fost atacați, inclusiv atacuri grave publicate împotriva algoritmului SHA-1 al Institutului Național de Standarde și Tehnologie (NIST) . Ca răspuns, NIST a organizat ateliere deschise și pe 2 noiembrie 2007 a anunțat o competiție pentru dezvoltarea unui nou algoritm de hashing. Pe 2 octombrie 2012, algoritmul Keccak a devenit câștigătorul competiției și a fost standardizat ca noul algoritm SHA-3 [6] . La 5 august 2015, algoritmul a fost aprobat și publicat ca standard FIPS 202 [2] [3] .

Algoritmul a fost dezvoltat de Guido Bertoni , Joan Dymen , Gilles Van Asche de la STMicroelectronics și Mikael Pieters de la NXP [7] .

Algoritmul se bazează pe funcțiile hash anterioare Panama și RadioGatún [8] . Panama a fost dezvoltat de Dimen și Craig Clapp în 1998, RadioGatún a fost implementat pe baza Panama de către Dimen, Peters și Van Asche în 2006 [8] .

În timpul competiției, concurenților li s-a permis să facă modificări algoritmului lor pentru a corecta problemele descoperite. Modificări aduse algoritmului Keccak [9] [10] :

Algoritm

Funcțiile hash ale familiei SHA-3 se bazează pe construcția unui burete criptografic [5] , în care datele sunt mai întâi „absorbite” în burete, în care mesajul original este supus unor permutări cu mai multe runde , apoi rezultatul este „stors” din burete. În faza de „înmuiere”, blocurile de mesaje sunt însumate modulo 2 cu un subset al stării, după care întreaga stare este transformată folosind funcția de permutare . În timpul etapei „push”, blocurile de ieșire sunt citite din același subset al stării modificate de funcția de permutare . Mărimea părții din stare care este scrisă și citită se numește „viteză” ( ing. rate ) și este notă cu , iar dimensiunea părții care este neatinsă de intrare/ieșire se numește „capacitate” ( ing . .capacitate ) şi se notează cu .

Algoritmul pentru obținerea valorii funcției hash poate fi împărțit în mai multe etape [11] :

Datorită faptului că starea conține biți suplimentari, algoritmul este rezistent la atacul de prelungire a mesajului , la care algoritmii SHA-1 și SHA-2 sunt susceptibili .

În SHA-3, o stare este o matrice de 5 × 5 cuvinte de lungime = 64 de biți, pentru un total de 5 × 5 × 64 = 1600 de biți. Tot în Keccak pot fi folosite lungimi egale cu puteri mai mici de 2 (de la = 1 la = 32).

Supliment

Pentru ca mesajul original M să fie împărțit în blocuri de lungime r , este necesară umplutura . SHA-3 folosește modelul pad10*1 [11] : un 1 este adăugat la mesaj, urmat de 0 sau mai mulți biți zero (până la r-1 ) și un 1 la sfârșit.

r-1 biți zero pot fi adăugați atunci când ultimul bloc de mesaj are r-1 biți. Acest bloc este umplut cu unul, următorul bloc va fi format din r-1 zerouri și unu.

Se adaugă și doi biți de 1 dacă lungimea mesajului original M este divizibil cu r [11] . În acest caz, la mesaj se adaugă un bloc, care începe și se termină cu unii, între care există r-2 biți zero. Acest lucru este necesar pentru ca pentru un mesaj care se termină cu o secvență de biți ca în funcția de umplutură și pentru un mesaj fără acești biți, valorile hash sunt diferite.

Primul 1 bit este necesar pentru ca rezultatele funcției hash din mesajele care diferă cu câțiva biți zero la sfârșit să fie diferite [11] .

Funcția de permutare

Funcția de permutare utilizată în SHA-3 include SAU exclusiv (XOR) , ȘI pe biți (ȘI) și negație pe biți (NU) . Funcția este definită pentru șiruri de lungime-putere 2 . În implementarea principală a SHA-3 ( ).

Starea poate fi reprezentată ca o matrice tridimensională de dimensiunea 5 × 5 × . Apoi elementul de matrice este bitul liniei de stare .

Funcția conține mai mulți pași: , , , , , care se efectuează în mai multe runde [11] . La fiecare pas, notăm tabloul de intrare A, tabloul de ieșire A'.

Pasul

Pentru toți și , astfel încât , , punem

Pentru toti , astfel incat , , ,

Pasul

Pentru toți , astfel încât ,

Lasă la început . Pentru 0 până la 23:

  1. Pentru toți , astfel încât ,

Pasul

Pentru toți , astfel încât ,

Pasul

Pentru toți , astfel încât ,

Pasul

Introducem o funcție suplimentară , în care intrarea este un număr întreg și ieșirea este un pic.

Algoritm
  1. Dacă , atunci este returnat 1
  2. Lăsa
  3. Pentru i de la 1 la t mod 255:
    1. R = 0 || R
  4. Se intoarce
Algoritm

 - număr rotund.

  1. Pentru toți , astfel încât ,
  2. Fie  o matrice de lungime umplută cu zerouri.
  3. De la 0 la :
  4. Pentru toți , astfel încât ,

Algoritm de permutare

  1. Traducerea unui șir într-o matrice
  2. Pentru de la până la
  3. Conversia unui tablou într-un șir de lungime

Hashing mesaje de lungime arbitrară

Baza funcției de compresie a algoritmului este funcția f, care realizează amestecarea stării interne a algoritmului. Starea (să o notăm A) este reprezentată ca o matrice 5×5 , ale cărei elemente sunt cuvinte de 64 de biți inițializate cu zero biți (adică dimensiunea stării este de 1600 de biți). Funcția f efectuează 24 de runde, în fiecare dintre acestea fiind efectuate următoarele acțiuni:

C[x] = A[x, 0] A[x, 1] A[x, 2] A[x, 3] A[x, 4], x = 0…4; D[x] = C[x - 1] (С[x + 1] >>> 1), x = 0…4; A[x, y] = A[x, y] D[x], x = 0…4, y = 0…4; B[y, 2x + 3y] = A[x, y] >>> r[x, y], x = 0…4, y = 0…4; A[x, y] = B[x, y] (~B[x + 1, y] & B[x + 2, y]), x = 0…4, y = 0…4,

Unde:

B  este o matrice temporară similară ca structură cu matricea de stare; C și D  sunt tablouri temporare care conțin fiecare cinci cuvinte de 64 de biți; r  este o matrice care definește cantitatea de deplasare ciclică pentru fiecare cuvânt de stare; ~x  este complementul pe biți a lui x ; iar operațiile pe indici de matrice sunt efectuate modulo 5.

Pe lângă operațiile de mai sus, în fiecare rundă, operația XOR impune și o constantă rotundă cuvântului A[0, 0].

Înainte ca funcția de compresie să fie executată, se suprapune operația XORing fragmente din mesajul original cu fragmentele din starea inițială. Rezultatul este procesat de funcția f . Această suprapunere, împreună cu funcția de compresie efectuată pentru fiecare bloc de date de intrare, constituie faza „absorbantă” a buretelui criptografic.

Este demn de remarcat faptul că funcția f utilizează numai operațiuni care sunt rezistente la atacurile de scurgere de date pe canalul lateral.

Valoarea hash rezultată este calculată în timpul fazei de stoarcere a buretelui criptografic, care se bazează și pe funcția f descrisă mai sus . Dimensiunile hash posibile sunt 224, 256, 384 și 512 biți.

Setări

Algoritmul Keccak original are mulți parametri ajustabili [11] pentru a oferi echilibrul optim între puterea criptografică și viteza pentru o anumită aplicare a algoritmului pe o anumită platformă. Valorile ajustabile sunt: ​​dimensiunea blocului de date, dimensiunea stării algoritmului, numărul de runde în funcția f() și altele.

În timpul concursului de hashing al Institutului Național de Standarde și Tehnologie , participanții au avut dreptul de a-și modifica algoritmii pentru a rezolva probleme. Așadar, s-au făcut unele modificări la Keccak: numărul de runde a fost crescut de la 18 la 24 pentru a crește marja de siguranță.

Autorii lui Keccak au stabilit o serie de premii pentru realizările în criptoanaliza acestui algoritm.

Versiunea algoritmului adoptată ca standard SHA-3 final are câteva diferențe minore față de prezentarea inițială a lui Keccak la competiție. În special, unii parametri au fost limitați (modurile lente c=768 și c=1024 au fost renunțate), inclusiv pentru creșterea performanței [12] [13] [14] [15] . De asemenea, standardul a introdus „funcții cu rezultat extins” (XOF, Extendable Output Functions) SHAKE128 și SHAKE256, pentru care a devenit necesară completarea mesajului hashed cu un „ sufix ” de 2 sau 4 biți, în funcție de tipul funcției. .

Funcţie Formulă
SHA3-224( M ) Keccak[448]( M ||01, 224)
SHA3-256( M ) Keccak[512]( M ||01, 256)
SHA3-384( M ) Keccak[768]( M ||01, 384)
SHA3-512( M ) Keccak[1024]( M ||01, 512)
SHAKE128( M , d ) Keccak[256]( M ||1111, d )
SHAKE256( M , d ) Keccak[512]( M ||1111, d )

Caracteristici suplimentare

În decembrie 2016, Institutul Național de Standarde și Tehnologie din SUA a publicat un nou document, NIST SP.800-185 [16] , care descrie caracteristici suplimentare bazate pe SHA-3:

Funcţie Descriere
cSHAKE128( X , L , N , S ) Versiune parametrizată de SHAKE
cSHAKE256( X , L , N , S )
KMAC128( K , X , L , S ) Inserție de imitație bazată pe Keccak
KMAC256( K , X , L , S )
KMACXOF128( K , X , L , S )
KMACXOF256( K , X , L , S )
TupleHash128( X , L , S ) Hashing un tuplu de șiruri
TupleHash256( X , L , S )
TupleHashXOF128( X , L , S )
TupleHashXOF256( X , L , S )
ParallelHash128( X , B , L , S ) Funcție hash paralelizabilă bazată pe Keccak
ParallelHash256( X , B , L , S )
ParallelHashXOF128( X , B , L , S )
ParallelHashXOF256( X , B , L , S )

Vectori de testare

Valorile diferitelor variante hash dintr-un șir gol.

SHA3-224("") 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7 SHA3-256("") a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a SHA3-384("") 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004 SHA3-512("") a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f50016298583501623858500162385 SHAKE128("", 256) 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 SHAKE256("", 512) 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc8294b494721b494721b48647294

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

SHA3-224 (" Vulpea maro iute sare peste câinele leneș ") d15dadceaa4d5d7bb3b48f446421d542e08ad8887305e28d58335795 SHA3-224 ("Vulpea maro iute sare peste câinele leneș . ") 2d0708903833afabdd232a20201176e8b58c5be8a6fe74265ac54db0 SHA3-256 ("Vulpea maro iute sare peste câinele leneș") 69070dda01975c8c120c3aada1b282394e7f032fa9cf32f4cb2259a0897dfc04 SHA3-256 ("Vulpea maro iute sare peste câinele leneș . ") a80f839cd4f83f6c3dafc87feae470045e4eb0d366397d5c6ce34ba1739f734d SHA3-384 ("Vulpea maro iute sare peste câinele leneș") 7063465e08a93bce31cd89d2e3ca8f602498696e253592ed26f07bf7e703cf328581e1471a7ba7ab119b1a9ebdf8be41 SHA3-384 ("Vulpea maro iute sare peste câinele leneș . ") 1a34d81695b622df178bc74df7124fe12fac0f64ba5250b78b99c1273d4b080168e10652894ecad5f1f4d5b965437fb9 SHA3-512 ("Vulpea maro iute sare peste câinele leneș") 01dedd5de4ef14642445ba5f5b97c15e47b9ad931326e4b0727cd94cefc44fff23f07bf543139939b49128caf436dc1bdee54fcb08bd436dc1bdee54fcb08bd94fcb08bd44f07bf543139939 SHA3-512 ("Vulpea maro iute sare peste câinele leneș . ") 18f4f4bd419603f95538837003d9d254c26c23765565162247483f65c50303597bc9ce4d289f21d1c2f1f458828e3135063630303030303030303030030030037003 SHAKE128(„Vulpea maro iute sare peste câinele leneș”, 256) f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e SHAKE128(„Vulpea maro iute sare peste leneșul f ”, 256) 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

Criptanaliză

Rezultatele criptoanalizei în timpul concursului [4] .
Ţintă Tip de atac Ieșire Opțiune CF Apel Memorie
funcția hash coliziune 160 r = {240, 640, 1440},

c=160

1, 2 runde

funcția hash Găsirea prototipului 80 r = {240, 640, 1440},

c=160

1, 2 runde

Permutări atac-discriminator Toate 24 de runde
Permutări proprietate diferenţială Toate 8 runde
funcția hash atac-discriminator 224, 256 4 runde
funcția hash coliziune 224, 256 2 runde
funcția hash Găsirea celui de-al doilea prototip 224, 256 2 runde
funcția hash Găsirea celui de-al doilea prototip 512 6 runde
funcția hash Găsirea celui de-al doilea prototip 512 7 runde
funcția hash Găsirea celui de-al doilea prototip 512 8 runde
funcția hash coliziune 224, 256 4 runde

Note

  1. NIST selectează câștigătorul competiției Secure Hash Algorithm (SHA-3) . Consultat la 3 octombrie 2012. Arhivat din original pe 5 octombrie 2012.
  2. 1 2 NIST lansează standardul hash criptografic SHA-3 . Preluat la 21 ianuarie 2016. Arhivat din original la 17 august 2015.
  3. 1 2 Căutare publicație de manuscris NIST . Preluat la 21 ianuarie 2016. Arhivat din original la 12 august 2015.
  4. ↑ 1 2 Shu-jen Chang, Ray Perlner, William E. Burr, Meltem Sonmez Turan, John M. Kelsey. Raportul rundei a treia a competiției pentru algoritmul hash criptografic SHA-3 . - doi : 10.6028/nist.ir.7896 .
  5. ↑ 1 2 Echipa  Keccak . keccak.echipă. Data accesului: 15 decembrie 2017. Arhivat din original pe 16 decembrie 2017.
  6. Proiect SHA-3 - Funcții Hash | CSRC . csrc.nist.gov. Consultat la 7 noiembrie 2017. Arhivat din original pe 20 noiembrie 2017.
  7. NIST selectează câștigătorul competiției Secure Hash Algorithm (SHA-3) . NIST (2 octombrie 2012). Consultat la 2 octombrie 2012. Arhivat din original la 30 aprilie 2017.
  8. ↑ 1 2 Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche. Drumul de la Panama la Keccak prin RadioGatún  // Criptografie simetrică / Helena Handschuh, Stefan Lucks, Bart Preneel, Phillip Rogaway. - Dagstuhl, Germania: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germania, 2009. Arhivat din original la 22 decembrie 2017.
  9. Echipa Keccak  . keccak.echipă. Consultat la 12 noiembrie 2017. Arhivat din original pe 13 noiembrie 2017.
  10. Echipa Keccak  . keccak.echipă. Consultat la 12 noiembrie 2017. Arhivat din original pe 13 noiembrie 2017.
  11. ↑ 1 2 3 4 5 6 Morris J. Dworkin. Standard SHA-3: Funcții hash bazate pe permutare și ieșire extensibilă . - doi : 10.6028/nist.fips.202 .
  12. Will Keccak = SHA-3? (1 octombrie 2013). Data accesului: 20 decembrie 2013. Arhivat din original la 30 ianuarie 2014.
  13. Ce naiba se întâmplă cu standardul criptografic al NIST, SHA-3?  (engleză)  (24 septembrie 2013). Arhivat din original pe 25 ianuarie 2014. Preluat la 20 decembrie 2013.
  14. Da, acesta este Keccak! (4 octombrie 2013). Consultat la 20 decembrie 2013. Arhivat din original pe 8 decembrie 2013.  - declarație de răspuns din partea autorilor cărții Keccak
  15. Familia de funcție a bureților Keccak (17 ianuarie 2011). Consultat la 30 septembrie 2015. Arhivat din original la 12 septembrie 2015.  — modificarea algoritmului de umplere în runda a 3-a a competiției
  16. Funcții derivate SHA-3: cSHAKE, KMAC, TupleHash și ParallelHash . Consultat la 31 octombrie 2017. Arhivat din original la 31 octombrie 2017.

Link -uri

Implementări: