SWIFFT

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 6 februarie 2021; verificările necesită 3 modificări .

SWIFFT
Dezvoltatori	Vadim Lyubashevsky, Daniel Michiancio, Chris Peikert, Alon Rosen
Creată	2008
publicat	2008
Tip de	funcția hash

SWIFFT este un set de funcții hash criptografice cu securitate dovedită [1] [2] [3] . Acestea se bazează pe transformarea rapidă Fourier ( FFT ) și folosesc algoritmul de baze reduse cu LLL . Securitatea criptografică a funcțiilor SWIFFT (în sensul asimptotic) [4] este dovedită matematic folosind parametrii recomandați [5] . Găsirea coliziunilor în SWIFFT este cel puțin la fel de consumatoare de timp în cel mai rău caz ca găsirea de vectori scurti în rețele ciclice/ ideale . Aplicarea practică a SWIFFT va fi valoroasă tocmai în acele cazuri în care rezistența la coliziuni este deosebit de importantă. De exemplu, semnăturile digitale, care trebuie să rămână de încredere mult timp.

Acest algoritm oferă un debit de aproximativ 40 Mb/s pe un procesor Intel Pentium 4 cu o frecvență de ceas de 3,2 GHz [6] [1] . Au fost făcute cercetări pentru a accelera FFT, care este folosit în SWIFFT [7] . Ca urmare, viteza algoritmului a fost mărită de peste 13 ori [6] . Această implementare a SWIFFT sa dovedit a fi mai rapidă decât implementările funcțiilor hash utilizate pe scară largă [8] .

La concursul Institutului Național de Standarde și Tehnologie [2] din 2012, SWIFFTX (o modificare a SWIFFT) a fost propus ca SHA-3 (pentru a înlocui vechiul SHA-2 și în special SHA-1 [9] ), dar a fost respins în primul tur [10] .

Descrierea lucrării

Funcțiile SWIFFT pot fi descrise ca o simplă expresie algebrică peste un inel polinomial [1] [11] . Familia de funcții depinde de trei parametri principali : fie o putere de 2, - un număr întreg mic și - nu neapărat un număr prim , dar este mai bine să-l alegeți prim. Îl definim ca un inel de forma . De exemplu, inelul de polinoame din , ai căror coeficienți sunt numere întregi, este numărul cu care efectuăm împărțirea modulo și . Un element din poate fi un polinom de grad inferior cu coeficienți din . $R$ $n$ $m>0$ $p>0$ $R$ $R=\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ $\alfa$ $p$ $\alpha ^{n}+1$ $R$ $n$ $Z_{p}$

O funcție definită în familia SWIFFT este definită ca elemente inelare fixe , numite multiplicatori. Această funcție peste inel poate fi scrisă în următoarea formă: $m$ $a_{1},\ldots ,a_{m}\în R$ $R$ $R$

$\sum _{i=1}^{m}(a_{i}\cdot x_{i})$ ,

unde sunt polinoame cu coeficienți binari corespunzători unui mesaj de intrare binar de lungime . $x_{1},\ldots ,x_{m}\în R$ $mn$

Algoritmul de operare este următorul: [1] [12] [11]

Luat este un polinom ireductibil peste $\alfa$ $\mathbb {Z} [\alpha ]$
Intrarea este un mesaj de lungime $M$ $mn$
$M$ este convertit într-un set de polinoame într-un anumit inel polinomial cu coeficienți binari $m$ $p_{i}$ $R$
Coeficienții Fourier sunt calculați pentru fiecare $p_{i}$
Coeficienții Fourier fix sunt setați în funcție de familia SWIFFT $a_{i}$
Coeficienții Fourier sunt înmulțiți în perechi cu pentru fiecare $p_{i}$ $a_{i}$ $i$
Transformata Fourier inversă este utilizată pentru a obține cel mult polinoame de grad $m$ $f_{i}$ $2n$
Calculat modulo și . $f=\sum _{i=1}^{m}(f_{i})$ $p$ $\alpha ^{n}+1$
$f$ convertit în biți și trimis la ieșire $n\log(p)$

Operația rapidă de transformare Fourier la pasul 4 este ușor de inversat. Se efectuează pentru a obține confuzie - amestecarea biților dați la intrare.
Combinația liniară din pasul 6 este confuză deoarece comprimă intrarea.

Exemplu

Valorile specifice pentru parametrii n , m și p sunt alese după cum urmează: n = 64, m = 16, p = 257 [13] . Pentru acești parametri, orice funcție fixă de compresie a familiei va accepta un mesaj cu lungimea mn = 1024 biți (128 octeți) ca intrare. Ieșirea este într-un interval care are dimensiune . Datele de ieșire pot fi reprezentate folosind 528 de biți (66 de octeți). $\mathbb {Z} _{p}^{n}$ $p^{n}=257^{64}$ $\mathbb {Z} _{p}^{n}$

Calculul rezultatului înmulțirii polinoamelor

Cea mai grea parte a calculului expresiei de mai sus este de a calcula rezultatul înmulțirii [1] [14] . O modalitate rapidă de a calcula un produs dat este să utilizați teorema de convoluție , care afirmă că în anumite condiții: $a_{i}\cdot x_{i}$

{\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}

Aici denotă transformata Fourier , iar operația înseamnă înmulțirea coeficienților cu același indice. În general, teorema de convoluție are sensul de convoluție , nu de înmulțire. Totuși, se poate demonstra că înmulțirea polinoamelor este o convoluție. ${\mathcal {F}}$ $\cdot$ $*$

Transformată Fourier rapidă

Pentru a găsi transformata Fourier, folosim transformata Fourier rapidă (FFT), care necesită [1] . Algoritmul de multiplicare este următorul [14] : calculăm toți coeficienții Fourier pentru toate polinoamele simultan folosind FFT. Apoi înmulțim în perechi coeficienții Fourier corespunzători celor două polinoame. După ce folosim inversul FFT, după care obținem un polinom de grad nu mai mare decât . $O(n\log(n))$ $2n$

Transformată Fourier discretă

În loc de transformarea Fourier obișnuită, SWIFFT folosește transformata Fourier discretă (DFT) [1] [14] . Folosește rădăcinile unității în loc de rădăcini complexe ale unității. Acest lucru va fi adevărat dacă este un câmp finit și a 2- a n - a rădăcină simplă a unității există în câmpul dat. Aceste condiții vor fi îndeplinite dacă luăm un astfel de număr prim care este divizibil cu . $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$ $p$ $p-1$ $2n$

Alegerea opțiunilor

Parametrii m , p , n trebuie să îndeplinească următoarele cerințe [15] :

n trebuie să fie o putere de doi
p trebuie să fie un număr prim
p -1 trebuie să fie divizibil cu 2 n
$\log(p)<$ m

Puteți lua, de exemplu, următorii parametri: n =64, m =16, p =257. Luăm debitul la nivelul de 40 Mb/s [6] , securitate din căutarea coliziunilor - operațiuni. $2^{106}$

Proprietăți statistice

Hashing universal. Familia de funcții SWIFFT este universală [1] . Cu alte cuvinte, pentru orice funcție diferită fixă și aleasă aleatoriu din familie, probabilitatea ca egalitatea să se țină este invers proporțională cu valoarea intervalului ales. $x,x*$ $f$ $f(x)=f(x*)$
Regularitate. Funcțiile din familia SWIFFT de funcții de micșorare sunt obișnuite [1] .
generator de entropie. SWIFFT este un generator de entropie [1] . Pentru tabelele hash și aplicațiile conexe, este de dorit ca cheile pentru valorile introduse în funcție să fie distribuite uniform (sau aproape de distribuția uniformă), chiar dacă valorile de intrare sunt distribuite neuniform. Funcțiile hash care se comportă în acest fel sunt numite generatoare de entropie, deoarece pot reda parametrii distribuiți neuniform într-o ieșire (aproape) uniformă. Formal, această proprietate are de obicei o familie de funcții, din care o funcție a fost aleasă aleatoriu.

Proprietăți criptografice și securitate

SWIFFT nu este o funcție pseudo-aleatorie datorită liniarității [1] . Pentru o funcție arbitrară din familia SWIFFT, următorul lucru este adevărat: pentru doi parametri de intrare , astfel încât să fie și un parametru de intrare, . Îndeplinirea acestei relații nu este potrivită pentru o funcție aleatorie, iar un atacator poate distinge cu ușurință funcția noastră de una aleatoare. $f$ $x_{1}$ $x_{2}$ $x_{1}+x_{2}$ $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$

Pentru familia de funcții SWIFFT, rezistența criptografică la coliziuni (în sensul asimptotic) a fost dovedită sub o ipoteză relativ moderată cu privire la complexitatea problemei de a găsi vectori scurti în rețelele ciclice/ideale în cel mai rău caz. Aceasta înseamnă că familia de funcții SWIFFT este, de asemenea, rezistentă la al doilea atac preimagine [4] [16] .

Stabilitate teoretică

SWIFFT - Funcții criptografice dovedite de securitate [1] [3] . Ca în majoritatea cazurilor, demonstrarea securității funcțiilor se bazează pe faptul că problema matematică folosită în funcții nu poate fi rezolvată în timp polinomial. Aceasta înseamnă că puterea SWIFFT constă doar în faptul că se bazează pe o problemă matematică complexă.

În cazul SWIFFT, securitatea dovedită constă în problema găsirii vectorilor scurti în rețele ciclice/ ideale [17] . Se poate dovedi că următoarea afirmație este adevărată: să presupunem că avem un algoritm care poate găsi coliziuni de funcții pentru o versiune aleatorie a SWIFFT obținută din , într-un timp posibil cu probabilitate . Aceasta înseamnă că algoritmul funcționează doar pe o fracțiune mică, dar vizibilă, din funcțiile familiei. Apoi, putem găsi, de asemenea, un algoritm care poate găsi întotdeauna un vector scurt pe orice rețea ideală peste un inel într-un timp posibil, în funcție de și . Aceasta înseamnă că găsirea coliziunilor în SWIFFT nu este mai puțin dificilă, problema găsirii de vectori scurti într-o rețea peste , pentru care există doar algoritmi exponențiali . $f$ $f$ $T$ $p$ $f_{2}$ $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ $T_{2}$ $T$ $p$ $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$

Durabilitate practică

Autorii acestei funcții hash au examinat-o pentru vulnerabilități la diferite atacuri și au descoperit că atacul „zile de naștere” necesită cele mai puține operațiuni de numărare hash (2 106 ) pentru a găsi coliziuni. [18] [1] . Atacurile de permutare necesită 2.448 de numărări pentru parametrii standard. O enumerare completă a valorilor posibile ar necesita 2.528 de calcule hash. Acest lucru este de obicei suficient pentru a face imposibil un atac inamic.

Vezi și

Transformare rapidă Fourier

Note

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 Lyubashevsky și colab., 2008 .
↑ 12 Arbitman și colab., 2008 .
↑ 1 2 Györfi și colab., 2012 , p. 2.
↑ 12 Arbitman și colab., 2008 , p. unu.
↑ Buchmann și Lindner 2009 , p. 1-2.
↑ 1 2 3 Györfi și colab., 2012 , p. cincisprezece.
↑ Györfi și colab., 2012 , p. 15-16.
↑ Györfi și colab., 2012 , p. 16.
↑ CONCURS PRE-SHA-3 . Institutul Național de Standarde și Tehnologie (15 aprilie 2005). Arhivat din original pe 9 august 2017. (nedefinit)
↑ Candidații din runda a doua . Institutul Național de Standarde și Tehnologie (19 ianuarie 2010). Consultat la 14 februarie 2010. Arhivat din original pe 10 aprilie 2012. (nedefinit)
↑ 1 2 Györfi și colab., 2012 , p. 3.
↑ Arbitman și colab., 2008 , p. 4-5.
↑ Györfi și colab., 2012 .
↑ 1 2 3 Györfi și colab., 2012 , p. patru.
↑ Buchmann, Lindner, 2009 .
↑ Sarinay, 2010 , p. 9.
↑ Arbitman și colab., 2008 , p. 10-11.
↑ Buchmann și Lindner 2009 , p. 2.

Literatură

Cărți

Schneier B. Criptografia aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .

Articole

Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFT: A Modest Proposal for FFT Hashing (engleză) // Fast Software Encryption - 2008. - Vol. 5086. - P. 54-72. doi:10.1007/ 978-3-540-71039-4_4
Arbitman Y. , Dogon G. , Lyubashevsky V. , Micciancio D. , Peikert C. , Rosen A. SWIFFTX: O propunere pentru standardul SHA-3 (engleză) - 2008.
Buchmann J. , Lindner R. Secure Parameters for SWIFFT (engleză) // Progress in Cryptology - INDOCRYPT 2009 : 10th International Conference on Cryptology in India, New Delhi, India, 13-16 decembrie 2009. Proceedings / B. Roy , N Sendrier - Springer Berlin Heidelberg , 2009. - P. 1-17. - ISBN 978-3-642-10627-9 - doi:10.1007/978-3-642-10628-6_1
Šarinay J. Interpreting Hash Function Security Proofs (engleză) // Provable Security : 4th International Conference, ProvSec 2010, Malacca, Malaysia, October 13-15, 2010. Proceedings / S. Heng , K. Kurosawa - Springer Berlin Heidelberg , .2010 -P. 119-132. — ISBN 978-3-642-16279-4 — doi:10.1007/978-3-642-16280-0_8
Győrfi T. , Cret O. , Hanrot G. , Brisebarre N. Arhitectura hardware de înaltă performanță pentru funcțiile Hash SWIFFT / SWIFFTX // Cryptology ePrint Archive - Asociația Internațională pentru Cercetare Cryptologică , 2012.

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Ă