SHA-3

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2016. január 3-án felülvizsgált verziótól ; az ellenőrzések 57 szerkesztést igényelnek .
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] .

Történelem

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] :

Algoritmus

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).

Kiegészítés

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] .

A permutációs függvény

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.

lépés

Minden és , úgy, hogy , , tesszük

Mindenki számára , , ,

lépés

Mindenki számára , úgy, hogy

Legyen az elején . 0 és 23 között:

  1. Mindenki számára , úgy, hogy

lépés

Mindenki számára , _

lépés

Mindenki számára , _

lépés

Bevezetünk egy további függvényt , ahol a bemenet egy egész szám , a kimenet pedig egy bit.

Algoritmus
  1. Ha , akkor 1-et ad vissza
  2. Hadd
  3. 1-től t mod 255-ig:
    1. R = 0 || R
  4. Visszatér
Algoritmus

 - kerek szám.

  1. Mindenki számára , _
  2. Legyen egy nullákkal kitöltött  hosszúságú tömb .
  3. 0- tól :
  4. Mindenki számára , úgy, hogy

Permutációs algoritmus

  1. Karakterlánc fordítása tömbbe
  2. tól ig _
  3. Tömb átalakítása hosszúságú karakterláncra

Tetszőleges hosszúságú üzenetek kivonatolása

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.

Beállítások

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 )

További szolgáltatások

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 )

Tesztvektorok

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) a

Az ü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) 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

Kriptanalízis

A kriptoanalízis eredményei a verseny során [4] .
Cé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

Jegyzetek

  1. A NIST kiválasztja a Secure Hash Algorithm (SHA-3) verseny győztesét . Letöltve: 2012. október 3. Az eredetiből archiválva : 2012. október 5..
  2. 1 2 A NIST kiadja az SHA-3 Cryptographic Hash szabványt . Letöltve: 2016. január 21. Az eredetiből archiválva : 2015. augusztus 17..
  3. 1 2 NIST Manuscript Publication Search . Letöltve: 2016. január 21. Az eredetiből archiválva : 2015. augusztus 12..
  4. ↑ 1 2 Shu-jen Chang, Ray Perlner, William E. Burr, Meltem Sonmez Turan, John M. Kelsey. Az SHA-3 Cryptographic Hash Algorithm Competition harmadik fordulójának jelentése . - doi : 10.6028/nist.ir.7896 .
  5. ↑ 1 2 Keccak Team  . keccak.csapat. Hozzáférés dátuma: 2017. december 15. Az eredetiből archiválva : 2017. december 16.
  6. SHA-3 projekt – Hash függvények | CSRC . csrc.nist.gov. Letöltve: 2017. november 7. Az eredetiből archiválva : 2017. november 20.
  7. A NIST kiválasztja a Secure Hash Algorithm (SHA-3) verseny győztesét . NIST (2012. október 2.). Letöltve: 2012. október 2. Az eredetiből archiválva : 2017. április 30.
  8. ↑ 1 2 Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche. The Road from Panama to Keccak via RadioGatún  // Szimmetrikus kriptográfia / Helena Handschuh, Stefan Lucks, Bart Preneel, Phillip Rogaway. - Dagstuhl, Németország: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Németország, 2009. Az eredetiből archiválva : 2017. december 22..
  9. Keccak  Team . keccak.csapat. Letöltve: 2017. november 12. Az eredetiből archiválva : 2017. november 13.
  10. Keccak  Team . keccak.csapat. Letöltve: 2017. november 12. Az eredetiből archiválva : 2017. november 13.
  11. ↑ 1 2 3 4 5 6 Morris J. Dworkin. SHA-3 szabvány: Permutáció alapú hash és kiterjeszthető kimeneti funkciók . - doi : 10.6028/nist.fips.202 .
  12. Keccak = SHA-3? (2013. Október 1). Hozzáférés időpontja: 2013. december 20. Az eredetiből archiválva : 2014. január 30.
  13. Mi a fene történik a NIST titkosítási szabványával, az SHA-3-mal?  (angol)  (2013. szeptember 24.). Archiválva az eredetiből 2014. január 25-én. Letöltve: 2013. december 20.
  14. Igen, ez Keccak! (2013. október 4.). Letöltve: 2013. december 20. Az eredetiből archiválva : 2013. december 8..  - válasznyilatkozat a Keccak szerzőitől
  15. A Keccak szivacs funkciócsalád (2011. január 17.). Letöltve: 2015. szeptember 30. Az eredetiből archiválva : 2015. szeptember 12..  — a kitöltési algoritmus változása a verseny 3. fordulójában
  16. SHA-3 származtatott függvények: cSHAKE, KMAC, TupleHash és ParallelHash . Letöltve: 2017. október 31. Az eredetiből archiválva : 2017. október 31..

Linkek

Megvalósítások: