SHA-3
A Keccak (kiejtése: [kɛtʃak] , mint a „ketchak”) egy kriptográfiai hash függvény , amelyet Guido Bertoni, Joan Daemen , Michaël Peeters és Gilles Van Assche terveztek a RadioGatún funkcióból .
SHA-3 származik a NIST hash függvény verseny , amely megválasztotta az Keccak algoritmus a 2012. október 2. Nem célja az SHA-2 helyettesítése , amelyet egy jelentős támadás még nem veszélyeztetett, hanem alternatív megoldást kínál az MD5 , SHA- szabványok 0 és SHA-1 elleni támadások lehetőségeire .
Keccak egy szivacs funkció , amelyben az üzenet blokkok XORed a kezdeti bit , akkor cserélték reverzibilis.
Előfordul, hogy az eredetileg beküldött Keccak algoritmust használják, ez eltér a NIST által megadott algoritmustól, mert a NIST meghatározta, hogyan kell kitölteni az üzenetet, ha az üzenet hossza nem egyenlő a szivacsfunkció által bevitt méretével. Az eredmények különbözőek.
Keccak blokk-permutációja
A Keccak egy szivacsfunkció, amelynek átalakulását le fogjuk írni, amelyet a szivacs felépítésének terminológiájában f -nek nevezünk . Ez az átalakítás érvényes permutáció, ha olyan szót választunk, amely két w = 2 ℓ hatványú . Keccak esetében a szavak 64 bitesek, azaz = 6 .
Ennek a függvénynek a belső állapota az 5 × 5 × w dimenziójú mátrixnak fog tekinteni . a bejegyzés bitje lesz . Az indexeket az első két dimenzióra az 5 modulo , a harmadikra a modulo w- t kell kiszámítani .
![a [i] [j] [k]](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0474c99b9724ec0f39a468963ab200effd12d85)
Keccak f függvénye egy permutáció, amely öt meglehetősen egyszerű alprogram 12 + 2ℓ iterációjából ( azaz 24) áll:
A rutin θ Számítsa ki a jelentés 5 × w (5 bites) oszlopainak paritását , majd számolja ki a kizáró vagy két szomszédos oszlop közötti értéket. A rutin ρ Körkörösen tolja el a háromszög szám 25 szavát (0, 1, 3, 6, 10, 15,…). nincs eltolva, és: minden 0 ≤ t <24 esetén :![a [i] [j] [k] \ balra nyíl a [i] [j] [k] \ oplus parite (a [0..4] [j-1] [k]) \ oplus parite (a [0. .4] [j + 1] [k-1])](https://wikimedia.org/api/rest_v1/media/math/render/svg/e9b948aee83bef765f94cf1d267cdcefd4f6b902)
![a [0] [0]](https://wikimedia.org/api/rest_v1/media/math/render/svg/0dbeae550dc256ff2771b99560b01ecdfaa87f2d)
A rutin π A 25 szó rögzített mintázatú permutációja: A rutin χ Kombinálja a sorokat apránként a képlet szerint : Ez a művelet az egyetlen, amelyet nemlineárisnak nevezünk. A rutin ι Számítsa ki az exkluzívat vagy a konstansot egy állapotszóval, amely az iterációs számtól ( n ) függ : minden 0 ≤ m ≤ ℓ esetén :van Xore a bit számozott m + 7N egy LFSR szekvencia fokú 8. Ennek az utolsó lépésnek az a célja, hogy megtörje az előzőek által hagyott utolsó szimmetriákat.
![a [i] [j] [k] \ balra nyíl a [i] [j] [k- (t + 1) (t + 2) / 2]](https://wikimedia.org/api/rest_v1/media/math/render/svg/414d6ec8b2b82aab56a67f5ea289a9d6a8bc6992)
![a [3i + 2j] [i] = a [i] [j]](https://wikimedia.org/api/rest_v1/media/math/render/svg/992833d197d3f56b18cf1bb1b2746644bef39163)
![{\ displaystyle a [i] [j] [k] \ balra nyíl a [i] [j] [k] \ oplus \ lnot (a [i] [j + 1] [k]) \ & (a [i] [j + 2] [k])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41fd060c67b3e600539cb831362d942201b2072e)
![a [0] [0] [2 ^ m-1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1cfd7e0aa7b20cff4843ed244e2a21090d75913)
Hash változó méretű üzenetek
Az SHA-3 a szivacsszerkezetet használja , amelyben a bemenet metaforikusan szerepel az állam által elnyelt első mondatban , egy bizonyos sebességgel, a másodikban pedig kicsavarva, azonos sebességgel.
Az adatok r bitjeinek elnyeléséhez az adatokat XOR szerkesztjük az állapot első bitjeiben, majd blokk-permutációt alkalmazunk, ha további kimenetre van szükség.
A kapacitás a hash függvény, a c = 25 w - r bit az államok, amelyek soha nem közvetlenül érinti a bemeneti és kimeneti, fontos paraméter. Meg lehet igazítani a várt biztonsági az építési, de az SHA-3 szabvány meghatározza, hogy ésszerűen át c = 2 n , és n a méret a kívánt lábnyom.
Így r , az egyes permutációk során feldolgozott üzenet bitjeinek mennyisége a kívánt lenyomat méretétől függ. A különböző r sebességválasztási lehetőségek 1152, 1088, 832 vagy 576 (144, 136, 104 vagy 72 bájt ) 224, 256, 384 és 512 bites ujjlenyomat-méret esetén, ha w értéke 64.
Ha az üzenetet egy r bitblokk méretének többszöröséhez akarjuk igazítani , akkor azt kitöltjük ( kitöltéssel vagy angol nyelvű kitöltéssel ) a 10 ... 01 bináris mintával : egy első bit 1-nél, esetleg a megfelelő bitszám 0-nál (maximális r -1 bit), de mindig következik egy másik bit 1-nél. Ez az utolsó bit szükséges előfeltétele a szivacs felépítésének biztonságosságának igazolásához (az üzenet utolsó blokkjának nem -nulla).
Az algoritmus a következőképpen halad: az állapotot 0-ra inicializáljuk, a bejegyzést kitöltjük, r bit blokkokra osztva . A bemenetet az állapot abszorbeálja, vagyis minden blokkhoz XOR izot adunk az állapottal, majd a permutációt alkalmazzuk az eredményre.
Miután az összes permutációt elvégeztük, az eredmény ujjlenyomatát a jelentés első n bitje alkotja. r mindig nagyobb, mint n , ezért soha nem kell több permutációt alkalmazni a spin fázis alatt. Más alkalmazásokban, például az Optimal Asymmetric Encryption Padding (OAEP) változó méretű kimenet hasznos. Ebben az esetben n több biztonsági paraméter, mint pusztán kimeneti méret.
A kisebb hash-ok előállítására szolgáló permutációs függvény változatai a belső állapotuk feléig terjedő kivonatméretekig is rendelkezésre állnak, ha az r sebesség elég alacsony. Nem volt szükségük az SHA versenyre való nevezésre. Például 256 bites lábnyom kiszámítása 25 32 bites szó felhasználásával lehetséges, ha r = 800−2 × 256 = 288 , vagy 32 bájt iterációnként.
Az SHA-3, a szivacs felépítését példázva, álkóddal írható:
SHA-3 funkció ( adatfolyam ): építési paraméterek: f : az előző szakaszban leírt b bit → b bit átalakulása r : a kimeneti blokkonkénti bitek száma pad : a bemeneti adatfolyam r bitekből álló egész blokkokban történő kitöltésére szolgáló funkció n s : a kimeneti blokkok száma belső változók: állapot : 0 bitre inicializált b bit tömb, [1 .. r ] állapotra és [ r +1 .. b ] állapotra osztva blokkok : mindegyik r bit blokk tömbje z : egy visszatérő karakterlánc, amelynek hossza n s × r , inicializálása üres algoritmus: (* abszorpciós fázis *) blokkok ← vágási pad ( fluxus ) blokkokra mérete r bit minden p -re blokkokban : állapot ← f ( állapot [1 .. r ] ⊕ p ) (* centrifugálási fázis *) ismételje n s -szer : z ← összefűz ( z , állapot [1 .. r ]) állapot ← f ( állam ) visszatér zMegjegyzések és hivatkozások
(fr) Ez a cikk részben vagy egészben venni a Wikipedia cikket angolul című „ Keccak ” ( lásd a szerzők listáját ) .- (in) Guido Bertoni, Joan Daemen, Michaël Peeters és Gilles Van Assche, " The Keccak sponge function family: Specifications summary " on http://keccak.noekeon.org/ (megtekintve 2011. május 11. )
- Patrick Guignot, " Keccak nyeri az ajánlatot és SHA-3 lesz " , a Linuxfr-n
- (in) Guido Bertoni, Joan október másodikán, Michaël Peeters és Gilles Van Assche, " Szivacs funkciók " , ECRYPT Hash Workshop 2007
- (in) Guido Bertoni, Joan október másodikán, Michaël Peeters és Gilles Van Assche, " A Indifferentiability építése a szivacs " , EuroCrypt 2008
- „abc” karakterlánc értéke az algoritmus több változatánál
