SHA-3

Keccak (pronunție: [kɛtʃak] , la fel ca „ketchak”) este o funcție criptografică hash concepută de Guido Bertoni, Joan Daemen , Michaël Peeters și Gilles Van Assche din funcția RadioGatún .

SHA-3 vine de la concurs funcția de NIST hash care a fost ales Keccak algoritmul pe2 octombrie 2012. Nu este destinat să înlocuiască SHA-2 , care nu a fost încă compromis de un atac semnificativ, ci să ofere o soluție alternativă la posibilitățile de atac împotriva standardelor MD5 , SHA-0 și SHA-1 .

Keccak este o funcție burete în care blocurile de mesaje sunt XORed cu biți inițiali, apoi schimbați reversibil.

Uneori se folosește algoritmul Keccak așa cum a fost transmis inițial, acesta diferă de algoritmul specificat de NIST deoarece NIST a specificat cum să completeze mesajul atunci când lungimea mesajului nu este egală cu dimensiunea cerută ca intrare de funcția burete. Rezultatele sunt diferite.

Permutarea blocului lui Keccak

Keccak este o funcție de burete a cărei transformare o vom descrie, numită $f$ în terminologia construcției buretelui. Această transformare este o permutare validă prin alegerea unui cuvânt de o dimensiune care este o putere de două w = 2 ℓ . În cazul lui Keccak cuvintele sunt pe 64 de biți, adică $ℓ = 6$ .

Starea internă a acestei funcții va fi văzută ca o matrice de dimensiune 5 × 5 × w . va fi bitul intrării. Indicii sunt calculați modulul 5 pentru primele două dimensiuni și modulul w pentru a treia. $a [i] [j] [k]$ $(i * 5 + j) * w + k$

Keccak a funcției $f$ este o permutare care constă din $12 + 2ℓ$ iterații ( $adică$ 24) din cinci subrutine destul simplu:

Rutina

θ

Calculați paritatea coloanelor de 5 × w (5 biți) ale raportului, apoi calculați exclusivitatea sau între două coloane învecinate.

a [i] [j] [k] \ leftarrow a [i] [j] [k] \ oplus parite (a [0..4] [j-1] [k]) \ oplus parite (a [0. .4] [j + 1] [k-1])

Rutina

ρ

Deplasați circular cele 25 de cuvinte ale unui număr triunghiular (0, 1, 3, 6, 10, 15, ...). nu este deplasat și:

a [0] [0]

pentru fiecare

0 \leq t <24

\ begin {pmatrix} i \\ j \ end {pmatrix} \ leftarrow \ begin {pmatrix} 3 & 2 \\ 1 & 0 \ end {pmatrix} ^ t \ begin {pmatrix} 0 \\ 1 \ end {pmatrix}

a [i] [j] [k] \ leftarrow a [i] [j] [k- (t + 1) (t + 2) / 2]

Rutina

π

Permutarea celor 25 de cuvinte cu un model fix:

a [3i + 2j] [i] = a [i] [j]

Rutina

χ

Combinați rânduri bit cu bit conform formulei :

a = a \ oplus (\ lnot b \ & c)

{\ displaystyle a [i] [j] [k] \ leftarrow a [i] [j] [k] \ oplus \ lnot (a [i] [j + 1] [k]) \ & (a [i] [j + 2] [k])}

Această operație este singura numită neliniară. Rutina

ι

Calculați exclusivitatea sau a unei constante cu un cuvânt de stare, care depinde de numărul de iterație (

n

): pentru fiecare

0 \leq m \leq ℓ

a [0] [0] [2 ^ m-1]

este Xore cu bitul numerotat

m + 7n

al unei secvențe LFSR de gradul 8. Acest ultim pas își propune să spargă ultimele simetrii lăsate de cele anterioare.

Hash mesaje de dimensiuni variabile

SHA-3 folosește construcția de burete , în care intrarea este, metaforic, într-o primă propoziție absorbită de stat, la o anumită viteză și într-o a doua extrasă , cu aceeași viteză.

Pentru a absorbi $r$ biți ai datelor, datele sunt XOR ed în primii biți ai stării, apoi se aplică permutarea blocului dacă se dorește o ieșire suplimentară.

Capacitatea funcției hash, $c = 25 w - r$ biți de state care nu sunt direct afectate de intrare sau de ieșire, este un parametru important. Poate fi ajustat în funcție de siguranța preconizată a construcției, dar standardul SHA-3 îl stabilește în mod rezonabil la $c = 2 n$ , cu n dimensiunea amprentei dorite.

Astfel , r , cantitatea de biți ai mesajului procesat la fiecare permutare, depinde de mărimea amprentei dorite. Diferitele opțiuni ale ratei r sunt 1152, 1088, 832 sau 576 (144, 136, 104 sau 72 octeți ) pentru dimensiuni de amprentă de 224, 256, 384 și respectiv 512 biți, pentru w setat la 64.

Pentru a alinia mesajul pe un multiplu de dimensiune de dimensiunea unui bloc de r biți, acesta este umplut (prin umplere sau umplere în limba engleză) cu modelul binar 10 ... 01 : un prim bit la 1, urmat eventual de numărul corespunzător de biți la 0 (maxim r -1 biți), dar întotdeauna urmat de un alt bit la 1. Acest ultim bit este o condiție necesară pentru dovada siguranței construcției buretelui (ultimul bloc de mesaj trebuie să fie non -zero).

Algoritmul continuă după cum urmează: starea este inițializată la 0, intrarea este completată, împărțită în blocuri de r biți. Intrarea este absorbită de către stat, adică să spunem că pentru fiecare bloc este XOR zată cu statul , atunci permutarea este aplicată rezultatului.

Odată realizate toate permutările, amprenta rezultată este alcătuită din primii n biți ai raportului. r este întotdeauna mai mare decât n , deci nu este niciodată necesar să se aplice mai multe permutări în timpul fazei de centrifugare. În alte aplicații, cum ar fi Optimal Asymmetric Encryption Padding (OAEP), este utilă ieșirea cu dimensiune variabilă. În acest caz, n este mai mult un parametru de securitate decât o dimensiune de ieșire.

Variante ale funcției de permutare pentru a genera hashuri mai mici sunt de asemenea disponibile pentru dimensiuni hash de până la jumătate din dimensiunea stării lor interne, dacă rata r este suficient de mică. Nu au fost solicitați pentru participarea la concursul SHA. De exemplu, este posibil să se calculeze o amprentă pe 256 de biți folosind 25 de cuvinte pe 32 de biți dacă $r = 800-2 \times 256 = 288$ sau 32 de octeți pe iterație.

SHA-3, instanțând construcția buretelui, ar putea fi scris în pseudo-cod:

Funcția

SHA-3

( flux ): parametrii de construcție:

f

: o transformare a

b

biți →

b

biți, descrisă în secțiunea anterioară r : numărul de biți pe bloc de ieșire

pad

: o funcție pentru umplerea fluxului de intrare în blocuri întregi de r biți n s : numărul de blocuri de ieșire variabile interne: state : o matrice de b biți, inițializată la 0, împărțită în

starea

[1 .. r ] și starea [ r +1 .. b ] blocuri : o serie de blocuri de r biți fiecare z : un șir de returnat, de lungime n s × r , inițializat gol algoritm: (* faza de absorbție *) Blocuri ← tăiere

pad

( flux ) în blocuri de dimensiune r biți pentru fiecare p în blocuri : state ←

f

( state [1 .. r ] ⊕ p ) (* faza de centrifugare *) repeta n s ori : z ← concatenează ( z , starea [1 .. r ]) stat ← f ( stat ) întoarce z

Note și referințe

(fr) Acest articol este preluat parțial sau în întregime din articolul din Wikipedia engleză intitulat „ Keccak ” ( vezi lista autorilor ) .

(în) Guido Bertoni, Joan Daemen, Michaël Peeters și Gilles Van Assche, „ Familia de funcții burete Keccak: Rezumat specificații ” pe http://keccak.noekeon.org/ (accesat la 11 mai 2011 )
Patrick Guignot, „ Keccak câștigă oferta și devine SHA-3 ” , pe Linuxfr
(în) Guido Bertoni, Joan Daemen, Michaël Peeters și Gilles Van Assche, „ Sponge Functions ” , ECRYPT Hash Workshop 2007
(în) Guido Bertoni, Joan Daemen, Michaël Peeters și Gilles Van Assche, „ Despre construcția indiferențierii buretelui ” , EuroCrypt 2008
Valoarea a șirului „abc” pentru mai multe variante ale algoritmului

SHA-3

Permutarea blocului lui Keccak

Hash mesaje de dimensiuni variabile

Note și referințe

Anexe

Articole similare

linkuri externe