SHA-3, Keccak | |
---|---|
Fejlesztők | Guido Bertoni, Joan Dymen , Mikael Pieters, Gilles Van Asche |
Létrehozva | 2008 |
közzétett | 2008 |
Előző | SHA-2 |
Hash méret | 224, 256, 384, 512 (változó, 0<d≤2 64 -1) |
A körök száma | 24 (alapértelmezett) |
Típusú | hash függvény |
Az SHA-3 ( Keccak - ejtsd: "kechak") egy változó hosszúságú kivonatoló algoritmus , amelyet Joan Dymen , Rijndael társszerzője , az MMB , a SHARK , a Noekeon , a SQUARE és a BaseKing titkosítások szerzője által vezetett szerzőcsoport fejlesztett ki . 2012. október 2- án Keccak lett az Egyesült Államok Nemzeti Szabványügyi és Technológiai Intézete által rendezett Cryptographic Algorithm Contest [1] győztese . 2015. augusztus 5- én az algoritmust jóváhagyták és FIPS 202 szabványként tették közzé.[2] [3] . A szoftvermegvalósítás során a szerzők 12,5 ciklust állítanak elő bájtonként, ha Intel Core 2 processzorral rendelkező PC -n hajtják végre . A hardveres megvalósításban azonban a Keccak sokkal gyorsabbnak bizonyult, mint az összes többi döntős. [négy]
Az SHA-3 algoritmus a kriptográfiai szivacs elvén épül fel (a kriptográfiai algoritmusok ilyen struktúráját korábban a Keccak algoritmus szerzői javasolták) [5] .
2004 és 2005 között több kivonatolási algoritmust is megtámadtak, köztük a National Institute of Standards and Technology (NIST) SHA-1 algoritmusa ellen közzétett súlyos támadásokat . Válaszul a NIST nyílt workshopokat tartott, és 2007. november 2- án versenyt hirdetett egy új kivonatolási algoritmus kidolgozására. 2012. október 2- án a Keccak algoritmus lett a verseny győztese, és az új SHA-3 algoritmusként szabványosították [6] . 2015. augusztus 5- én az algoritmust FIPS 202 [2] [3] szabványként hagyták jóvá és tették közzé .
Az algoritmust Guido Bertoni , Joan Dymen , Gilles Van Asche az STMicroelectronicstól és Mikael Pieters az NXP -től [7] fejlesztette ki .
Az algoritmus a korábbi Panama és RadioGatún [8] hash függvényeken alapul . A Panamát Dimen és Craig Clapp fejlesztette ki 1998-ban, a RadioGatúnt Panama alapján Dimen, Peters és Van Asche 2006-ban [8] .
A verseny során a versenyzők módosíthatták az algoritmusukat, hogy kijavítsák a felfedezett problémákat. A Keccak algoritmus módosításai [9] [10] :
Az SHA-3 család hash funkciói egy kriptográfiai szivacs [5] felépítésén alapulnak , amelyben az adatokat először a szivacsba "abszorbeálják", amelyben az eredeti üzenetet többkörös permutációnak vetik alá , majd a eredmény "kinyomódik" a szivacsból. A "soak" fázisban az üzenetblokkok modulo 2 összegzésre kerülnek az állapot egy részhalmazával, majd a teljes állapotot a permutációs függvény segítségével átalakítják . A "push" szakaszban a kimeneti blokkok a permutációs függvény által módosított állapot azonos részhalmazából kerülnek kiolvasásra . Az állapot írott és olvasott részének méretét „sebességnek” ( eng. rate ) nevezzük, és jelöli , a bemenettől/kimenettől érintetlen rész méretét pedig „kapacitásnak” ( eng . kapacitás ) és jelölése .
A hash függvény értékének megszerzésére szolgáló algoritmus több szakaszra osztható [11] :
Tekintettel arra, hogy az állapot további biteket tartalmaz, az algoritmus ellenáll az üzenethosszabbító támadásnak , amelyre az SHA-1 és SHA-2 algoritmusok érzékenyek .
Az SHA-3-ban egy állapot egy 5 × 5 szóból álló tömb, amelynek hossza = 64 bit, összesen 5 × 5 × 64 = 1600 bit. Keccakban is használhatók 2 kisebb hatványaival egyenlő hosszúságok ( = 1-től = 32-ig).
Ahhoz, hogy az eredeti M üzenetet r hosszúságú blokkra oszthassuk , kitöltés szükséges . Az SHA-3 a pad10*1 [11] mintát használja: egy 1 -et adunk az üzenethez, ezt követi 0 vagy több nulla bit ( r-1- ig ), és egy 1 a végén.
r-1 nulla bitet lehet hozzáadni, ha az utolsó üzenetblokk r-1 bit hosszú. Ez a blokk eggyel párnázott, a következő blokk r-1 nullákból és egyből áll.
Két 1 bitet is hozzáadunk, ha az eredeti M üzenet hossza osztható r -rel [11] . Ebben az esetben egy blokk kerül az üzenetbe, amely egyesekkel kezdődik és végződik, amelyek között r-2 nulla bit található. Erre azért van szükség, hogy egy bitsorozattal végződő üzenetnél, mint a kitöltési funkciónál, és a bitek nélküli üzeneteknél a hash értékek eltérőek legyenek.
Az első 1 bit azért szükséges, hogy a végén több nulla bittel eltérő üzenetekből származó hash függvény eredménye eltérő legyen [11] .
Az SHA-3-ban használt permutációs függvény magában foglalja a kizárólagos VAGY (XOR) , a bitenkénti ÉS (AND) és a bitenkénti negációt (NOT) . A függvény 2 hosszúságú-hatékonyságú karakterláncokra van definiálva . Az SHA-3 fő megvalósításában ( ).
Az állapot egy 5 × 5 × méretű háromdimenziós tömbként ábrázolható . Ekkor a tömb eleme az állapotsor bitje .
A függvény több lépést tartalmaz: , , , , , amelyeket több körben hajtanak végre [11] . Minden lépésnél jelöljük az A bemeneti tömböt, az A' kimeneti tömböt.
Minden és , úgy, hogy , , tesszük
Mindenki számára , , ,
Mindenki számára , úgy, hogy
Legyen az elején . 0 és 23 között:
Mindenki számára , _
Mindenki számára , _
Bevezetünk egy további függvényt , ahol a bemenet egy egész szám , a kimenet pedig egy bit.
Algoritmus- kerek szám.
Az algoritmus tömörítési függvényének alapja az f függvény, amely az algoritmus belső állapotának keverését végzi. Az állapotot (jelöljük A-val) egy 5×5 -ös tömbként ábrázoljuk, melynek elemei 64 bites, nulla bittel inicializált szavak (azaz az állapot mérete 1600 bit). Az f függvény 24 kört hajt végre, amelyek mindegyikében a következő műveleteket hajtják végre:
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] és B[x + 2, y]), x = 0…4, y = 0…4,Ahol:
B az állapottömbhöz hasonló szerkezetű ideiglenes tömb; C és D ideiglenes tömbök, amelyek egyenként öt 64 bites szót tartalmaznak; r egy tömb, amely meghatározza az egyes állapotszavak ciklikus eltolásának mértékét; ~x az x bitenkénti kiegészítése ; és a tömbindexekkel végzett műveleteket modulo 5 hajtja végre.A fenti műveleteken kívül minden körben az XOR művelet egy kerek állandót is ír az A[0, 0] szóra.
A tömörítési funkció végrehajtása előtt az eredeti üzenet töredékeinek XORing művelete a kezdeti állapot töredékeivel szuperponálódik. Az eredményt az f függvény dolgozza fel . Ez az átfedés az egyes bemeneti adatblokkokhoz végrehajtott tömörítési funkcióval együtt alkotja a kriptográfiai szivacs „elnyelő” fázisát.
Érdemes megjegyezni, hogy az f függvény csak olyan műveleteket használ, amelyek ellenállnak az oldalcsatornás adatszivárgási támadásoknak.
A kapott hash értéket a kriptográfiai szivacs összenyomási fázisában számítjuk ki, amely szintén a fent leírt f függvényen alapul . A lehetséges hash-méretek: 224, 256, 384 és 512 bit.
Az eredeti Keccak algoritmus számos beállítható paraméterrel [11] rendelkezik, hogy optimális egyensúlyt biztosítson a kriptográfiai erősség és sebesség között az algoritmus egy adott platformon történő adott alkalmazásához. A beállítható értékek a következők: az adatblokk mérete, az algoritmus állapotának mérete, az f() függvény fordulóinak száma stb.
Az Országos Szabványügyi és Technológiai Intézet kivonatolási versenye során a résztvevőknek joguk volt módosítani algoritmusaikat a problémák megoldása érdekében. Így történt néhány változtatás a Keccakon: a körök számát 18-ról 24-re emelték a biztonsági ráhagyás növelése érdekében.
A Keccak szerzői számos díjat alapítottak az algoritmus kriptoanalízisében elért eredményekért.
Az algoritmus végső SHA-3 szabványként elfogadott verziója néhány kisebb eltérést mutat Keccak eredeti pályázatához képest. Konkrétan néhány paramétert korlátoztak (a c=768 és c=1024 lassú üzemmódokat elhagytuk), többek között a teljesítmény növelése érdekében [12] [13] [14] [15] . Ezenkívül a szabvány bevezette a „bővített eredménnyel rendelkező függvényeket” (XOF, Extendable Output Functions) a SHAKE128 és a SHAKE256, amelyeknél szükségessé vált a hash üzenet kiegészítése 2 vagy 4 bites „ utótaggal ” a függvény típusától függően. .
Funkció | Képlet |
---|---|
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 ) |
2016 decemberében az Egyesült Államok Nemzeti Szabványügyi és Technológiai Intézete közzétett egy új dokumentumot, a NIST SP.800-185 [16] , amely az SHA-3 alapján további funkciókat ír le:
Funkció | Leírás |
---|---|
cSHAKE128( X , L , N , S ) | A SHAKE paraméterezett változata |
cSHAKE256( X , L , N , S ) | |
KMAC128( K , X , L , S ) | Keccak alapján készült utánzati betét |
KMAC256 ( K , X , L , S ) | |
KMACXOF128( K , X , L , S ) | |
KMACXOF256 ( K , X , L , S ) | |
TupleHash128( X , L , S ) | Egy sor karakterlánc kivonatolása |
TupleHash256 ( X , L , S ) | |
TupleHashXOF128 ( X , L , S ) | |
TupleHashXOF256 ( X , L , S ) | |
ParallelHash128( X , B , L , S ) | Keccak alapján párhuzamosítható hash függvény |
ParallelHash256( X , B , L , S ) | |
ParallelHashXOF128( X , B , L , S ) | |
ParallelHashXOF256( X , B , L , S ) |
Különböző hash-változatok értékei egy üres karakterláncból.
SHA3-224("") 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7 SHA3-256 ("") a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a SHA3-384("") 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004 SHA3-512 ("") a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500b68d SHAKE128("", 256) 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 SHAKE256("", 512) aAz üzenet kis változása nagy változást eredményez a hash értékben a lavinahatás miatt , amint azt a következő példák is mutatják:
SHA3-224 (" A gyors barna róka átugrik a lusta kutyán ") d15dadceaa4d5d7bb3b48f446421d542e08ad8887305e28d58335795 SHA3-224 ("A gyors barna róka átugrik a lusta kutyán . ") 2d0708903833afabdd232a20201176e8b58c5be8a6fe74265ac54db0 SHA3-256 ("A gyors barna róka átugrik a lusta kutyán") 69070dda01975c8c120c3aada1b282394e7f032fa9cf32f4cb2259a0897dfc04 SHA3-256 ("A gyors barna róka átugrik a lusta kutyán . ") a80f839cd4f83f6c3dafc87feae470045e4eb0d366397d5c6ce34ba1739f734d SHA3-384 ("A gyors barna róka átugrik a lusta kutyán") 7063465e08a93bce31cd89d2e3ca8f602498696e253592ed26f07bf7e703cf328581e1471a7ba7ab119b1a9ebdf8be41 SHA3-384 ("A gyors barna róka átugrik a lusta kutyán . ") 1a34d81695b622df178bc74df7124fe12fac0f64ba5250b78b99c1273d4b080168e10652894ecad5f1f4d5b965437fb9 SHA3-512 ("A gyors barna róka átugrik a lusta kutyán") 03 SHA3-512 ("A gyors barna róka átugrik a lusta kutyán . ") A SHAKE128 ("A gyors barna róka átugrik a lusta kutyán", 256) f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e SHAKE128("A gyors barna róka átugrik a lusta róka felett " , 256) 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10cCél | Támadás típusa | Kijárat | választási lehetőség | CF hívás | memória |
---|---|---|---|---|---|
hash függvény | ütközés | 160 | r = {240, 640, 1440},
c=160 1, 2 kör |
||
hash függvény | A prototípus megtalálása | 80 | r = {240, 640, 1440},
c=160 1, 2 kör |
||
Permutációk | támadás-diszkriminátor | Összes | 24 kör | ||
Permutációk | különbségi tulajdonság | Összes | 8 kör | ||
hash függvény | támadás-diszkriminátor | 224, 256 | 4 kör | ||
hash függvény | ütközés | 224, 256 | 2 kör | ||
hash függvény | A második prototípus megtalálása | 224, 256 | 2 kör | ||
hash függvény | A második prototípus megtalálása | 512 | 6 kör | ||
hash függvény | A második prototípus megtalálása | 512 | 7 kör | ||
hash függvény | A második prototípus megtalálása | 512 | 8 kör | ||
hash függvény | ütközés | 224, 256 | 4 kör |
Megvalósítások:
Hash függvények | |
---|---|
Általános rendeltetésű | |
Kriptográfia | |
Kulcsgenerálási funkciók | |
Csekkszám ( összehasonlítás ) | |
Hashes |
|