SIMD (funcție hash)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 27 octombrie 2021; verificările necesită 2 modificări .
SIMD
Creată 2008
publicat octombrie 2008
Dimensiunea hash 256 sau 512 biți
Numărul de runde patru
Tip de funcția hash

SIMD este o funcție hash criptografică  iterativă dezvoltată de Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque. Ea a fost nominalizată ca candidată pentru competiția standard SHA-3 organizată de Institutul Național de Standarde și Tehnologie (SUA) , unde a ajuns în turul doi [1] .

Există două versiuni ale funcției hash, SIMD-256 și SIMD-512, care convertesc un mesaj de lungime arbitrară într-o valoare hash de 256 sau 512 biți, numită și un mesaj digest . În plus, este posibil să se definească funcții hash SIMD-n ca trunchieri ale funcțiilor SIMD-256 și SIMD-512 pentru n<256 și respectiv 256<n<512 [2] .

Potrivit creatorilor, principala caracteristică a funcției hash este o extindere semnificativă a mesajului, care vă permite să vă protejați de criptoanaliza diferențială [3] .

Algoritm

Descriere generală și parametri

Partea principală a funcției hash h este funcția de compresie . Pentru a calcula h(M) , mesajul M este împărțit în k părți de m biți fiecare. Funcția de compresie : este apoi aplicată iterativ părților mesajului . Starea inițială sau vectorul de inițializare este desemnat și fixat pentru fiecare funcție de familie SIMD. Rezultatul final al funcției hash se obține prin aplicarea funcției de finalizare la .

Funcția de compresie C în modul Davis-Meier este de obicei construită folosind funcția de criptare bloc : , cu toate acestea, sunt utilizate câteva îmbunătățiri pentru funcția hash SIMD.

Familia SIMD de funcții hash utilizează următorii parametri:

Dimensiunea hash, n Dimensiunea blocului de mesaje, m Mărimea stării interne ( ), p
SIMD-256 256 512 512
SIMD-512 512 1024 1024

Starea internă este reprezentată de o matrice 4x4 de cuvinte de 32 de biți pentru SIMD-256 și 8x4 pentru SIMD-512.


Funcția de compresie

Funcția de compresie SIMD se bazează pe designul Davis-Meyer cu unele modificări.

În primul rând, în loc de funcția de compresie , .

În al doilea rând, în loc de operația XOR pentru și în SIMD, mai multe runde Feistel suplimentare sunt utilizate cu h ca tastă de intrare. Această acțiune este efectuată de funcția .

Astfel, funcția de compresie este definită ca . Potrivit autorilor funcției SIMD hash, aceste modificări oferă același nivel de securitate ca și designul original Davis-Meyer, dar în același timp previn unele tipuri de atacuri multi-bloc [4] .

Extensia mesajului

Extinderea mesajului a funcției hash SIMD-256 (respectiv SIMD-512) convertește un bloc de mesaje de 512 biți (respectiv 1024 biți) într-un mesaj extins de 4096 biți (respectiv 8192 biți) cu o distanță minimă de 520 ( resp. .1032).

Utilizarea rețelei Feistel

Utilizarea structurii Feistel de către funcția hash SIMD este construită în mod similar cu familia de funcții hash MD/SHA:

sau într-un format mai convenabil:

pentru SIMD-256

pentru SIMD-512

unde este o funcție logică, este adiție modulo și este o deplasare ciclică la stânga pe bit.

Pentru SIMD-256 sunt utilizate 4 celule Feistel paralele (respectiv 8 pentru SIMD-512), care interacționează între ele datorită permutărilor . Permutările sunt alese pentru a asigura o bună amestecare.

Pentru SIMD-256 este definit:

În consecință, pentru SIMD-512:

În general, funcția de compresie funcționează în 4 runde, fiecare dintre ele constând din 8 pași (pași), plus o rundă finală suplimentară.

Funcția finală de compresie

După ce toate blocurile mesajului au fost comprimate, se face un alt apel suplimentar la funcția de comprimare cu dimensiunea mesajului ca intrare. În acest caz, lungimea mesajului este calculată în biți modulo dacă este necesar.

Pentru funcția finală de compresie, se utilizează o metodă de extindere a mesajelor ușor modificată:

pentru SIMD-256 este folosit în loc de .

În consecință, pentru SIMD-512, în loc de a utiliza

Astfel, intervalul extins de mesaje pentru etapa finală este diferit de intervalul extins de mesaje al blocurilor de corpuri de mesaje.

După aplicarea funcției finale de compresie, rezultatul este următoarea reprezentare șir:

pentru SIMD-256

pentru SIMD-512

În cazul SIMD-n, primii n biți ai SIMD-256 (n < 256) sau SIMD 512 (256 < n < 512) sunt ieșiți. De exemplu, pentru SIMD-384 ieșirea va fi

Vector de inițializare

Fiecare funcție hash din familia SIMD își folosește propriul IV pentru a evita legăturile între ieșirile diferitelor funcții SIMD-n. IV pentru funcția SIMD-n este definită după cum urmează:

IV = SIMD-Compress(0, "SIMD-(i)" v1.0, 0) unde șirul este în ASCII completat cu zerouri și (i) este reprezentarea zecimală a lui n.

Valori IV pentru diferite funcții hash ale familiei SIMD:

Îmbunătățiri pentru runda a doua a concursului SHA-3

2 părți ale algoritmului au suferit modificări: permutări și deplasări ciclice (rotații) [5] .

La alegerea noilor permutări, autorii funcției hash au fost ghidați de următoarele criterii:


SIMD-256. Permutări inițiale:

Permutări noi:

unde . Astfel, numărul de permutări a crescut de la 2 la 3.


SIMD-512. Permutări inițiale:

Permutări noi:

unde . Astfel, numărul de permutări a crescut de la 4 la 7.

Pseudocod SIMD [6]

1: funcția MessageExpansion(M, f) //f marchează funcția finală de compresie 2: dacă f = 0 atunci 3: y(i) = NTT(M + X127) //respectiv X255 pentru SIMD-512 4:altfel 5: y(i) = NTT(M + X127 + X125) //respectiv X255 + X253 pentru SIMD-512 6: termina dacă 7: Calculați Z(i,j) aplicând codurile interne I(185) și I(233) la y(i). 8: Calculați W(i,j) aplicând permutări pentru Z(i,j) 9: returnează W(i,j) 10: funcția finală unsprezece: 12: funcția Round(S, i, r) 13: S = Pas (S; W(8i+0); IF; r0; r1) 14: S = Pas (S; (W8i+1); IF; r1; r2) 15: S = Pas (S; W(8i+2); IF; r2; r3) 16: S = Pas (S; W(8i+3); IF; r3; r0) 17: S = Treapta(S; W(8i+4);MAJ; r0; r1) 18: S = Pas (S; W(8i+5);MAJ; r1; r2) 19: S = Treapta(S; W(8i+6);MAJ; r2; r3) 20: S = Pas (S; W(8i+7); MAJ; r3; r0) 21: întoarcere S 22: funcția finală 23: 24: funcția SIMD-Compress (IV, M, f) 25: W = MessageExpansion(M; f) 26: S = IV x sau M 27: S = rotund(S; 0; [3; 20; 14; 27]) 28: S = rotund(S; 1; [26; 4; 23; 11]) 29: S = rotund(S; 2; [19; 28; 7; 22]) 30: S = rotund(S; 3; [15; 5; 29; 9]) 31: S = Pas (S; IV(0); IF; 15; 5) 32: S = Pas (S; IV(1); IF; 5; 29) 33: S = Pas (S; IV(2); IF; 29; 9) 34: S = Pas (S; IV(3); IF; 9; 15) 35: întoarcere S 36: funcția finală 37: 38: funcția SIMD(M) 39: Împărțiți mesajul M în părți M(i); 0 =<i<k. 40: M(k-1) umplut cu zerouri. 41:S=IV 42: pentru 0 =< i < k do 43: S = SIMD-Comprimare(S; M(i); 0) 44: sfârşitul pentru 45: S = SIMD-Comprimare(S; ||M||; 1) 46: returnează Truncare(S) 47: funcția finală

Exemplu de rezultate [7]

Mesaj M SIMD-256(M)
Mesaj gol 8029e81e7320e13ed9001dc3d8021fec695b7a25cd43ad805260181c35fcaea8
0x00; 0x01; 0x02; … 0x3f 5bebdb816cd3e6c8c2b5a42867a6f41570c4b917f1d3b15aabc17f24679e6acd
Mesaj M SIMD-512(M)
Mesaj gol 51a5af7e243cd9a5989f7792c880c4c3168c3d60c4518725fe5757d1f7a69c63

66977eaba7905ce2da5d7cfd07773725f0935b55f3efb954996689a49b6d29e0

0x00; 0x01; 0x02; … 0x3f 8851ad0a57426b4af57af3294706c0448fa6accf24683fc239871be58ca913fb

ee53e35c1dedd88016ebd131f2eb0761e97a3048de6e696787fd5f54981d6f2c

Performanță

Testele independente de performanță ale algoritmului SIMD, efectuate folosind benchmark -ul eBASH , au arătat următoarele rezultate (viteza este indicată în cicluri pe octet ( cpb )) [8] [3] :

CPU Core i5 Core 2 (45nm) Core 2 (65nm)
SIMD-256 7,51 cbp 9,18 cbp 11,34 cbp
SIMD-512 8,63 cbp 10,02 cpb 12,05 cpb

În același timp, aproximativ jumătate din timpul funcției hash este alocat operației de extindere a mesajelor: Transformarea teoretică a numărului (NTT) este cea mai scumpă parte a algoritmului în ceea ce privește performanța.

Funcția de compresie SIMD are o arhitectură parțial paralelă, care vă permite să creați implementări eficiente ale algoritmului folosind instrucțiuni vectoriale ( SIMD ). Aceste instrucțiuni sunt disponibile pe multe arhitecturi binecunoscute: SSE pe x86 , AltiVec pe PowerPC , IwMMXt pe ARM .

În ceea ce privește cerințele RAM, funcția SIMD hash are nevoie de memorie pentru a stoca starea internă (64 de octeți pentru SIMD-256 și 128 de octeți pentru SIMD-512) și memorie pentru valorile de ieșire NTT (4*64 = 256 de octeți pentru SIMD-256). și 4*128 = 512 octeți pentru SIMD-512).

Rezultatele concursului SHA-3 pentru SIMD

Funcția SIMD hash nu a fost selectată ca finalist în concursul SHA-3.

Experții concursului au remarcat că, deși funcția hash SIMD repetă în mare măsură algoritmii familiilor MD / SHA, îmbunătățirile aduse de autori au făcut cu adevărat posibilă protejarea SIMD de multe tipuri de atacuri (de exemplu, un atac de coliziune ). În plus, modificările făcute pentru a doua rundă au putut proteja funcția hash SIMD de atacul de criptoanaliza diferențială efectuat de Mendel și Nad, la care SIMD a fost expus în implementarea sa inițială [9] .

Cu toate acestea, cerințele mari de RAM și disponibilitatea instrucțiunilor SIMD pentru o performanță bună fac ca funcția hash să fie un candidat slab pentru implementarea FPGA [10] . În principal din acest motiv, funcția SIMD hash nu a ajuns în etapa finală a competiției.

Note

  1. SHA-3 Runda 2 Candidați .
  2. Descrierea oficială a funcției SIMD hash , p. 9.
  3. 1 2 Site-ul oficial al funcției SIMD hash .
  4. Descrierea oficială a funcției SIMD hash , p. 7-8.
  5. Îmbunătățiri ale funcției SIMD Hash pentru a doua rundă a concursului SHA-3 , p. 1-2.
  6. Descrierea oficială a funcției SIMD hash , p. 22.
  7. Descrierea oficială a funcției SIMD hash , p. 43-270.
  8. site-ul oficial eBASH benchmark .
  9. Raport cu rezultatele rundei a doua a concursului SHA-3 .
  10. Implementarea candidaților concursului SHA-3 pe FPGA.

Literatură