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] .
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 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] .
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 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ă.
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
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:
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.
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 |
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).
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.
Funcții hash | |
---|---|
scop general | |
Criptografic | |
Funcții de generare a cheilor | |
Numărul de verificare ( comparație ) | |
Hashes |
|