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] .
Î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] :
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).
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 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'.
Pentru toți și , astfel încât , , punem
Pentru toti , astfel incat , , ,
Pentru toți , astfel încât ,
Lasă la început . Pentru 0 până la 23:
Pentru toți , astfel încât ,
Pentru toți , astfel încât ,
Introducem o funcție suplimentară , în care intrarea este un număr întreg și ieșirea este un pic.
Algoritm- număr rotund.
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.
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 ) |
Î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 ) |
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) 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc8294b494721b494721b48647294O 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Ţ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 |
Implementări:
Funcții hash | |
---|---|
scop general | |
Criptografic | |
Funcții de generare a cheilor | |
Numărul de verificare ( comparație ) | |
Hashes |
|