Hash bazat pe sindromul rapid

Hash bazat pe sindromul rapid
Dezvoltatori	Daniel Ogot, Matthew Finiash, Nicolas Sandrier
Creată	2003
publicat	2008
Dimensiunea hash	160, 224, 256, 384, 512
Tip de	funcția hash

FSB (Fast Syndrome-Based Hash Function) este un set de funcții hash criptografice create în 2003 și depus în 2008 ca candidat pentru competiția SHA-3 [1] . Spre deosebire de multe funcții hash utilizate în prezent, puterea criptografică a FSB poate fi dovedită într-o anumită măsură. Demonstrarea puterii FSB-ului este că spargerea FSB-ului este la fel de dificilă ca și rezolvarea unei probleme NP-complete cunoscute sub numele de decodare obișnuită a sindromului. Deși încă nu se știe dacă problemele NP-complete sunt rezolvabile în timp polinomial , se presupune în general că nu sunt.

În timpul procesului de dezvoltare, au fost propuse mai multe versiuni ale FSB, ultima dintre acestea a fost depusă la competiția SHA-3, dar a fost respinsă în primul tur. În timp ce toate versiunile FSB pretind că sunt sigure , unele versiuni pre-lansare au fost în cele din urmă sparte [2] . La dezvoltarea celei mai recente versiuni de FSB au fost luate în considerare toate vulnerabilitățile, iar momentan algoritmul rămâne rezistent criptografic la toate atacurile cunoscute în prezent.

Pe de altă parte, rezistența vine cu un cost. FSB este mai lent decât funcțiile hash tradiționale și utilizează destul de multă memorie RAM, ceea ce îl face nepractic în mediile în care este limitat. În plus, funcția de compresie utilizată în FSB necesită o dimensiune mare a mesajului de ieșire pentru a garanta puterea criptografică. Această problemă a fost rezolvată în versiunile recente în care rezultatul este comprimat de funcția Whirlpool . Cu toate acestea, deși autorii susțin că adăugarea acestei ultime contracții nu reduce stabilitatea, face imposibilă demonstrarea formală a acesteia [3] .

Descrierea funcției hash

Funcția de compresie are parametri precum și . Această funcție va funcționa numai cu mesaje cu o lungime de . - dimensiunea de iesire. Mai mult, și trebuie să fie numere naturale - logaritmul binar). Motivul este că dorim să fie o funcție de compresie, deci intrarea trebuie să fie mai mare decât ieșirea. Mai târziu, folosim construcția Merkle-Damgard pentru a extinde domeniul de intrare pentru mesaje de lungime arbitrară. $\phi$ ${n,r,w}$ $n>w$ $w\log(n/w)>r$ $s=w\log(n/w)$ $r$ $n,r,w,s$ $\log(n/w)$ $\Buturuga$ $w\cdot \log(n/w)>r$ $\phi$

Baza acestei funcții constă dintr-o matrice binară (aleasă aleatoriu) care interacționează cu un mesaj de biți prin multiplicare a matricei . Aici codificăm un mesaj -bit ca vector într- un spațiu vectorial -dimensional peste un câmp de două elemente, astfel încât rezultatul va fi un mesaj de biți. $r\times n$ $H$ $n$ $w\log(n/w)$ $(\mathbf {F} _{2})^{n)$ $n$ $r$

Din motive de securitate și, de asemenea, pentru a avea o rată de hash rapidă, doar „cuvinte obișnuite de greutate ” sunt folosite ca intrare în matricea noastră. $w$

Definiții

Un mesaj se numește cuvânt de greutate și lungime dacă este format din biți și din acești biți nu sunt zero. $w$ $n$ $n$ $w$

Un cuvânt de greutate și lungime se numește regulat dacă fiecare interval conține exact un element diferit de zero pentru toate . Aceasta înseamnă că dacă împărțim mesajul în w părți egale, atunci fiecare parte conține exact un element diferit de zero. $w$ $n$ $[(i-1)w,iw)$ $0<i<n/w+1$

Funcția de compresie

Există exact diferite cuvinte obișnuite de greutate și lungime , așa că avem nevoie de exact biți de date pentru a codifica acele cuvinte obișnuite. Fixați o corespondență unu-la-unu între setul de șiruri de biți de lungime și setul de cuvinte obișnuite de greutate și lungime , apoi definiți funcția de compresie FSB după cum urmează: $(n/w)^{w)$ $w$ $n$ $\log((n/w)^{w})=w\log(n/w)=s$ $s$ $w$ $n$

Intrarea este un mesaj de dimensiune $s$
Transformarea acestuia într-un cuvânt obișnuit de greutate și lungime $w$ $n$
Înmulțirea matricei $H$
La ieșire, obținem un hash de dimensiunea $r$

Această versiune este denumită în general compresie sindromică. Acest lucru este destul de lent și, în practică, se face într-un mod diferit și mai rapid numit compresie sindromică rapidă. Împărțim în submatrice de dimensiune și fixăm o corespondență unu-la-unu între șirurile de biți de lungime și un set de secvențe de numere de la 1 la . Aceasta este echivalentă cu o corespondență unu-la-unu cu un set de cuvinte obișnuite de lungime și greutate , deoarece se poate vedea acel cuvânt ca o secvență de numere de la 1 la . Funcția de compresie arată astfel: $H$ $Bună$ $r\times n/w$ $w\log(n/w)$ $w$ $n/w$ $n$ $w$ $n/w$

Intrarea este un mesaj de dimensiune $s$
Convertindu-l într-o succesiune de numere de la 1 la $w$ $s_{1},\dots ,s_{w)$ $n/w$
Adăugarea coloanelor adecvate de matrice pentru a obține un șir binar de lungime $Bună$ $r$
La ieșire, obținem un hash de dimensiunea $r$

Acum putem folosi structura Merkle-Damgard pentru a generaliza funcția de compresie, astfel încât intrarea să poată fi de lungime arbitrară.

Exemplu de compresie

Conditii initiale :

Trimitem mesajul folosind o matrice care este împărțită în submatrici , , . $s=010011$ $4\times 12$ $H$
${\displaystyle H=\left({\begin{array}{llllcllllclll}1&0&1&1&~&0&1&0&0&~&1&0&1&1\\0&1&0&0&~&0&1&1&1&~&0&1&0&0\\0&1&1&1&1&1&0&0&0&~&1&0&~&0&1&0&~&0&{1&0&~0&1&0&~&0&1&0&~$
$w=3$ $H_1$ $H_2$ $H_3$

Algoritm :

Împărțim mesajul primit în părți ale lungimii și obținem , , . $s$ $w=3$ $\log _{2}(12/3)=2$ $s_{1}=01$ $s_{2}=00$ $s_{3}=11$
Să convertim fiecare șir într-un număr și să obținem , , . $si}$ $s_{1}=1$ $s_{2}=0$ $s_{3}=3$
Din prima submatrice luăm a doua coloană, din a doua luăm prima, din a treia - a patra. $H_1$ $H_2$ $H_3$
Adăugați coloanele selectate și obțineți rezultatul: . $r=0111\oplus 0001\oplus 1001=1111$

Dovada de securitate FSB

Structura Merkle-Damgard își bazează securitatea doar pe securitatea funcției de compresie utilizată. Astfel, trebuie doar să arătăm că funcția de compresie este rezistentă la criptoanaliza . $\phi$

O funcție hash criptografică trebuie să fie sigură în trei moduri diferite:

Prima rezistență preimagine: Având în vedere un hash h , ar trebui să fie greu de găsit un mesaj m astfel încât Hash( m )= h .
A doua rezistență preimagine este: având în vedere un mesaj m 1 , ar trebui să fie greu de găsit un mesaj m 2 astfel încât Hash( m 1 ) = Hash( m 2 ).
Rezistent la coliziune: Ar trebui să fie greu să găsiți două mesaje distincte m 1 și m 2 astfel încât Hash( m 1 )=Hash( m 2 ).

Este de remarcat faptul că, dacă puteți găsi a doua preimagine, atunci puteți, desigur, să găsiți o coliziune . Aceasta înseamnă că, dacă putem dovedi că sistemul nostru este rezistent la coliziuni, cu siguranță va fi sigur împotriva găsirii unei a doua preimagine.

De obicei, în criptografie dificil înseamnă ceva de genul „aproape sigur dincolo de îndemâna oricărui adversar a cărui încălcare a sistemului trebuie prevenită”, dar să definim acest concept mai precis. Vom presupune: „timpul de execuție al oricărui algoritm care găsește o coliziune sau preimagine depinde exponențial de mărimea valorii hash”. Aceasta înseamnă că, cu adăugiri relativ mici la dimensiunea hash, putem ajunge rapid la un nivel ridicat de putere criptografică.

Rezistența preimagine

După cum am menționat mai devreme, puterea criptografică a FSB depinde de o sarcină numită decodare sindromică obișnuită. Inițial o problemă în teoria codificării , dar caracterul complet al NP a făcut din aceasta o aplicație la îndemână pentru criptografie. Este un caz special de decodificare a sindromului și este definit după cum urmează:

Date matrice de dimensiune și un șir de biți de lungime astfel încât să existe un set de coloane, câte una pentru fiecare , care alcătuiesc . Trebuie să găsim un astfel de set de coloane. $w$ $Bună$ $r\times (n/w)$ $S$ $r$ $w$ $Bună$ $S$

S-a dovedit că această problemă este NP-completă prin evitarea potrivirii 3D. Din nou, deși nu se știe dacă există algoritmi polinomi pentru rezolvarea problemelor de timp NP-complete, niciunul dintre ei nu este cunoscut și găsirea unuia ar fi o descoperire uriașă.

Este ușor de observat că găsirea preimaginei unui hash dat este exact echivalentă cu această problemă, astfel încât problema preimagine FSB trebuie să fie și NP-completă. $S$

Mai trebuie să dovedim rezistența la coliziune. Pentru a face acest lucru, avem nevoie de o altă variație NP-completă a codificării sindromice obișnuite, numită „decodificare sindromică biregulară zero”.

Rezistența la coliziune

Sunt date matrice de dimensiuni și un șir de biți de lungime . Apoi există un set de coloane, fie două, fie niciunul în fiecare , alcătuind 0, unde . Trebuie să găsim un astfel de set de coloane. Această metodă s-a dovedit a fi NP-completă prin evitarea potrivirii 3D. $w$ $Bună$ $r\times (n/w)$ $S$ $r$ $w'$ $Bună$ $(0<w'<2w)$

Așa cum decodificarea sindromică obișnuită este, în esență, echivalentă cu găsirea unui cuvânt obișnuit astfel încât , decodificarea sindromică biregulară zero este echivalentă cu găsirea unui cuvânt biregular astfel încât . Un cuvânt biregular de lungime și greutate este un șir de biți de lungime astfel încât în fiecare interval fie exact două intrări sunt 1, fie nici una. Rețineți că un cuvânt cu 2 obișnuit este pur și simplu suma a două cuvinte obișnuite. $w$ $Hw=S$ $w'$ $hw'=0$ $n$ $w$ $n$ $[(i-1)w,iw)$

Să presupunem că am găsit o coliziune: Hash( m 1 ) = Hash( m 2 ) for . Apoi putem găsi două cuvinte obișnuite și astfel încât . Obținem apoi , unde este suma a două cuvinte regulate diferite și trebuie să fie un cuvânt biregular al cărui hash este zero, așa că am rezolvat problema de decodificare a sindromului nul biregular. Am ajuns la concluzia că găsirea coliziunilor în FSB este cel puțin la fel de dificilă ca rezolvarea problemei de decodificare a sindromului nul biregular și, prin urmare, algoritmul este NP-complet. $m_{1}\neq m_{2}$ $w_{1}$ $w_{2)$ $Hw_{1}=Hw_{2}$ $H(w_{1}+w_{2})=Hw_{1}+Hw_{2}=2Hw_{1}=0$ $(w_{1}+w_{2})$

Versiunile recente ale FSB au folosit funcția de compresie Whirlpool pentru a comprima și mai mult rezultatul funcției hash. Deși puterea criptografică în acest caz nu poate fi dovedită, autorii susțin că această ultimă compresie nu o reduce. Rețineți că, chiar dacă ar fi posibil să găsiți coliziuni în Whirpool, ar fi totuși necesar să găsiți coliziuni preimagine în funcția de compresie FSB originală pentru a găsi coliziuni în FSB.

Exemple

Rezolvând problema decodării sindromice obișnuite, suntem, parcă, în direcția opusă, în ceea ce privește hashingul. Folosind aceleași valori ca în exemplul anterior, ni se oferă un subbloc și un șir . Trebuie să găsim o coloană în fiecare subbloc, deci vor fi . Deci răspunsul așteptat ar fi , , . Acest lucru este notoriu dificil de calculat pentru matrici mari. În decodificarea sindromului zero biregular, dorim să găsim în fiecare subbloc nu o coloană, ci fie două, fie niciuna, astfel încât să conducă la (și nu la ). În exemplu, am putea folosi a doua și a treia coloană (numărând de la 0) din , niciuna dintre coloanele de , zero și a doua din . Sunt posibile mai multe soluții, de exemplu, fără a utiliza nici una dintre coloanele din . $H$ $w=3$ $r=1111$ $r$ $s_{1}=1$ $s_{2}=0$ $s_{3}=3$ $0000$ $r$ $H_1$ $H_2$ $H_3$ $H_3$

Criptanaliza liniară

Securitatea demonstrabilă a FSB înseamnă că găsirea coliziunilor este NP-complet. Dar dovada este o reducere la o problemă mai complexă. Dar acest lucru oferă doar garanții de securitate limitate, deoarece poate exista încă un algoritm care rezolvă cu ușurință problema pentru un subset al spațiului dat. De exemplu, există o metodă de liniarizare care poate fi utilizată pentru a obține coliziuni în câteva secunde pe un computer desktop pentru versiunile inițiale ale FSB cu un rating de siguranță revendicat 2128 . Se arată că atunci când spațiul mesajului este ales într-un anumit mod, funcția hash oferă rezistență minimă la preimagine sau la coliziune.

Rezultatele securității în practică

Tabelul arată complexitatea celor mai faimoase atacuri împotriva FSB:

Dimensiunea de ieșire (biți)	Dificultate în găsirea coliziunilor	Complexitatea inversării
160	2 100,3	2 163,6
224	2 135,3	2229,0 _
256	2 190,0	2 261,0
384	2 215,5	2 391,5
512	2 285,6	2527,4 _

Alte proprietăți

Dimensiunea blocului de intrare și ieșire a funcției hash este complet scalabilă.
Viteza poate fi ajustată prin modificarea numărului de operații pe biți utilizate de FSB pe bit de intrare.
Siguranța poate fi ajustată prin ajustarea dimensiunii de ieșire.
Există cazuri proaste și trebuie avut grijă atunci când alegeți matricea . $H$
Matricea utilizată în funcția de micșorare poate deveni uriașă în anumite cazuri.

Opțiuni

Acesta din urmă poate fi problematic atunci când utilizați FSB pe dispozitive cu memorie relativ mică.

Această problemă a fost rezolvată în 2007, într-o funcție hash conexă numită IFSB (Improved Fast Syndrome Based Hash) [4] , care este încă sigură dovedit, dar se bazează pe presupuneri ceva mai puternice.

În 2010 a fost introdus S-FSB, care are o viteză cu 30% mai mare decât FSB [5] .

În 2011, Daniel Julius Bernstein și Tanya Lange au introdus RFSB, care a fost de 10 ori mai rapid decât FSB-256 [6] . RFSB, când este rulat pe o mașină FPGA Spartan 6, a atins un debit de până la 5 Gbps [7] .

Note

↑ Augt, D.; Finiasz, M.; Sendrier, N. O funcție hash criptografică rapidă și sigură (2003). Data accesului: 10 decembrie 2015. Arhivat din original pe 3 martie 2016. (nedefinit)
↑ Saarinen, Markku-Juhani O. Linearization Attacks Against Syndrome Based Hashes (2007). Consultat la 10 decembrie 2015. Arhivat din original pe 4 martie 2016. (nedefinit)
↑ Finiasz, M.; Gaborit, P.; Sendrier, N. Funcții hash criptografice îmbunătățite bazate pe sindromul rapid (link inaccesibil) (2007). Data accesului: 10 decembrie 2015. Arhivat din original pe 3 martie 2016. (nedefinit)
↑ Finiasz, M.; Gaborit, P.; Sendrier, N. Funcții hash criptografice îmbunătățite bazate pe sindromul rapid (2007). Data accesului: 12 decembrie 2015. Arhivat din original pe 22 decembrie 2015. (nedefinit)
↑ Meziani M.; Dagdelen O.; CayrelPL; El Yousfi Alaoui SM S-FSB: O variantă îmbunătățită a familiei Hash FSB (link indisponibil) (2010). Data accesului: 12 decembrie 2015. Arhivat din original pe 22 decembrie 2015. (nedefinit)
↑ Bernstein, DJ, Lange, T.; Peters C.; Schwabe P.;. Hashing cu adevărat rapid bazat pe sindrom (2011). Consultat la 12 decembrie 2015. Arhivat din original pe 14 decembrie 2014. (nedefinit)
↑ Von Maurich, I.; Guneysu, T.;. Hashing bazat pe sindromul încorporat (link indisponibil) (2011). Data accesului: 12 decembrie 2015. Arhivat din original pe 2 mai 2015. (nedefinit)

Funcții hash
scop general	Adler-32 CRC Suma de control Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash suma hash
Criptografic	Stribog GOST R 34.11-94 centura BLAKE BMW CubeHash ECOU edonkey2k FSB Fugă Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Piele Snefru Tigru Vârtej
Funcții de generare a cheilor	bcrypt PBKDF2 cripta Argon2 Lyra2
Numărul de verificare ( comparație )	Verificați suma Algoritmul lui Verhouff Algoritmul lunii Algoritmul Damm Cod de bare conturi bancare carduri bancare ESTE IN SNILS OKPO STANIU OKATO ISBN OGRN și OGRNIP VIN
Hashes	Comparația numerelor de cec Protocoale de autentificare Comparația codurilor de bare Criptografie Legătură magnetică Semnătura Merkle ed2k URNĂ