Argon2

Argon2

Argon2 este o funcție de derivare cheie dezvoltată de Alex Biryukov , Daniel Dinu și Dmitry Khovratovich de la Universitatea din Luxemburg în 2015 [1] .

Acesta este un algoritm modern simplu care vizează o rată mare de umplere a memoriei și utilizarea eficientă a mai multor unități de calcul [2] . Algoritmul este lansat sub o licență Creative Commons .

Istorie

În 2013, a fost anunțată competiția de hashing parole pentru a crea o nouă funcție de hashing a parolei. Cerințele pentru noul algoritm au fost cantitatea de memorie utilizată, numărul de treceri prin blocuri de memorie și rezistența la criptoanaliza.

În 2015, Argon2 a fost declarat câștigătorul competiției [1] . De atunci, algoritmul a suferit 4 modificări majore. Unele dintre descrierile algoritmilor pentru generarea unor blocuri și greșeli de scriere au fost corectate, au fost adăugați parametri recomandați [1] [3] .

Date de intrare

Argon2 folosește parametri de bază și avansați pentru hashing:

Principal:

Mesaj (parolă) , lungime de la până la . $P$ $0$ $2^{{32}}-1$
Sarea S, lungime de la până la . $opt$ $2^{{32}}-1$

Adiţional:

Gradul de paralelism , orice număr întreg de la până la — numărul de fire la care algoritmul poate fi paralelizat. $p$ $unu$ $2^{24}-1$
Lungimea etichetei , lungime de la până la . $\tau$ $patru$ $2^{{32}}-1$
Dimensiunea memoriei , număr întreg de kiloocteți de la până la $m$ $8p$ $2^{{32}}-1$
Număr de iterații [4] $t$

Versiuni ale algoritmului

Există două versiuni ale algoritmului:

Argon2d - potrivit pentru protejarea monedei digitale și a sistemelor de informații care nu sunt supuse atacurilor prin canale terțe .
Argon2i - oferă o protecție ridicată împotriva atacurilor de compromis , dar este mai lent decât versiunea d din cauza trecerilor multiple de memorie [1] .

Descriere

Argon2 funcționează după următorul principiu:

Parola este indexată folosind funcția hash Blake2b .
Rezultatul hash este scris în blocurile de memorie.
Blocurile de memorie sunt convertite folosind funcția de compresie $G$
Ca rezultat al algoritmului, este generată o cheie ( ing. Tag ).

Umplerea blocurilor de memorie

$B[0]=H(P,S)$

$B[j]=G(B[\phi _{1}(j)],B[\phi _{2}(j)],...,B[\phi _{k}(j )])$ , , unde $j=1...t$

$\phi _{k}(j)$ — funcție de indexare , — matrice de memorie, — funcție de compresie, — mesaj (parolă), — funcție hash Blake2b . $B[]$ $G$ $P$ $H$

Funcțiile de indexare depind de versiunea algoritmului Argon2:

Argon2d - depinde de blocul anterior $\phi$

Argon2i este valoarea determinată de generatorul de numere aleatoare. $\phi$

In cazul functionarii secventiale, functia de compresie se aplica o singura data. Pentru versiunea Argon2d, la pasul -, blocul cu indicele determinat de blocul anterior este alimentat la intrarea funcției . Pentru versiunea Argon2i, valoarea generatorului de numere aleatoare este luată ( în modul contor). $m$ $i$ $G$ $\phi (i)$ $\phi (i)=g(B[i])$ $G$

În cazul unui mod paralel (algoritmul este paralelizat în fire ), datele sunt distribuite peste blocurile matricei , unde primele blocuri sunt rezultatul hashingului datelor de intrare, iar următoarele sunt setate de funcția de compresie. pentru blocurile anterioare și blocul de referință : $p$ $B[i][j]$ $G$ $B^{1}[i'][j']$

$B^{1}[i][0]=H'(\ H_{0}\ ||\ {\underset {4bytes}{0))\ ||\ {\underset {4bytes}{i} }\ ),0\leq i<p$

$B^{1}[i][1]=H'(\ H_{0}\ ||\ {\underset {4bytes}{1))\ ||\ {\underset {4bytes}{i} }\ ),0\leq i<p$

$B^{1}[i][j]=G(B^{1}[i][j-1],B^{1}[i'][j']),0\leq i <p$

$B^{t}[i][0]=G(B^{t-1}[i][q-1],B^{1}[i'][j'])\oplus B ^{t-1}[i][0]$

$B^{t}[i][j]=G(B^{t}[i][j-1],B^{1}[i'][j'])\oplus B^{ t-1}[i][j]$

$q={m' \over p}\ \ \ \ \ m'=\lfloor {m \over 4p}\rfloor 4p$ , unde este numărul de blocuri de memorie cu o dimensiune de 1024 de octeți, este o funcție hash care ia ca intrare o reprezentare pe 32 de biți a parametrilor de intrare, a cărei ieșire este o valoare de 64 de biți, este o funcție hash de lungime variabilă de la , este cantitatea de memorie, este numărul de iterații. $m'$ $H_{0}$ $H'$ $H$ $m$ $t$

În cele din urmă:

$B_{final}=B^{T}[0][q-1]\oplus B^{T}[1][q-1]\oplus ...\oplus B^{T}[p -1][q-1]$

$Tag\leftarrow H'(B_{final})$ [5]

Găsirea blocului suport

Argon2d: selectați primii 32 de biți pentru și următorii 32 de biți pentru din blocuri $J_{1)$ $J_{2}$ $B[i][j-1]$
Argon2i: , unde - numărul iterației, - numărul rândului, - setează versiunea (în acest caz, una) $(J_{1}||J_{2})=G^{2}(null_{1024},{r||l||s||m'||t||y||i|| null_{968}})$ $r$ $l$ $y$

În continuare, se determină indicele liniei de unde provine blocul. Când , valoarea este luată ca număr de linie curent . Apoi se determină un set de indici după 2 reguli: $l=J_{2}mod\p$ $r=0,s=0$ $l$ $R$

Dacă se potrivește cu numărul liniei curente, atunci toate blocurile neînregistrate anterior sunt adăugate la setul de index fără $l$ $B[i][j-1]$
Dacă nu se potrivește, blocurile sunt luate din toate segmentele de linie și din ultimele părți. $l$ $S-1=3$

Ca rezultat, numărul blocului este calculat din , care este luat ca referință: $r$

$z=|R|-1-({\frac {|R|*((J_{1})^{2}/2^{32})}{2^{32))})$ [6]

Funcția H'

Blake2b este o versiune pe 64 de biți a funcției BLAKE , deci este construită astfel: $H'$

$dacă\ \tau \ \leq \ 64$

$H'(X)=H_{\tau }(\tau ||X).$

În general , valoarea de ieșire a funcției este construită pe primii 32 de biți ai blocurilor - și ultimul bloc : $\tau$ $A_{i}$ $V_i$

$r=\lceil \tau /32\rceil -2$

$V_{1}\longleftarrow H_{64}(\tau ||X)$

$V_{r+1}\longleftarrow H_{\tau -32r}(V_{r})$

$H'(X)=A_{1}||A_{2}||...A_{r}||V_{r+1}$

Funcția de compresie G

Bazat pe caracteristica de compresie Blake2b. Primește două blocuri de 8192 de biți ca intrare și produce un bloc de 1024 de biți. Mai întâi se adaugă două blocuri ( ), apoi matricea este procesată rând cu rând ( ), apoi matricea rezultată este procesată coloană cu coloană ( ), iar rezultatul este [6] . $P$ $A=X\oplus Y$ $A_{8,8}$ $P$ $A\longrightarrow Q$ $Q\longrightarrow Z$ $G$ $Z\oplus A$

Criptanaliză

Protecție la coliziune : funcția Blake2b în sine este considerată sigură din punct de vedere criptografic. De asemenea, referindu-se la regulile de indexare, autorii algoritmului au demonstrat absența coliziunilor în cadrul blocurilor de date și probabilitatea scăzută de apariție a acestora la aplicarea funcției de compresie.

Atacul de găsire a preimaginei : lăsați atacatorul să ridiceastfel încât, apoi pentru a continua acest atac, trebuie să ridice preimaginea:, ceea ce este imposibil. Același raționament este potrivit pentru atacul găsirii celei de-a doua preimagine. $m$ $G(m)=h$ $n$ $H(n)=m$

Atacuri de sincronizare: Dacă utilizatorul trebuie să se adapteze la un atac de sincronizare , atunci versiunea Argon2i ar trebui să fie utilizată deoarece folosește memorie independentă [7] .

Atacurile

Atacul de optimizare a memoriei

Dan Bonet , Henry Corrigan-Gibbs și Stuart Schechter au arătat vulnerabilitatea Argon2i versiunea 1.2 în munca lor. Pentru versiunea cu o singură trecere, atacul lor a redus consumul de memorie cu un factor de 4 fără a încetini execuția. Pentru versiunea multi-pass - de 2,72 ori. Mai târziu, în versiunea 1.3, operația de suprascriere a fost înlocuită cu XOR [8] .

AB16

Joel Alwen și Jeremiah Blocki au dovedit în munca lor că algoritmul lor de atac AB16 este eficient nu numai pentru Argon2i-A (din prima versiune a specificației), ci și pentru Argon2i-B (din cea mai recentă versiune 1.3). Ei au arătat că atacarea Argon2 cu 1 GB de RAM reduce timpul de calcul la jumătate. Pentru o protecție eficientă, trebuie specificate mai mult de 10 treceri. Dar, cu abordarea recomandată pentru alegerea parametrilor algoritmului, în practică, adesea poate fi selectată doar 1 trecere. Dezvoltatorii Argon2 susțin că prin aplicarea atacului AB16 asupra Argon2i-B la , timpul este redus de cel mult 2 ori până la 32 GB de memorie și recomandă utilizarea numărului de treceri care depășește logaritmul binar al dimensiunii $t=6$ $t\geq 4$ [ clarifica ] memorie folosită [9] .

Atacul compromisului de clasare

Acest atac este unul dintre cele mai eficiente pentru Argon2d. Reduce timpul de procesare de 1,33 ori. Pentru Argon2i la , coeficientul este 3 [10] . $t>2$

Atacuri cu colectorii de gunoi

Condiția principală pentru atacul prezentat este accesul atacatorului la memoria internă a mașinii țintă, fie după terminarea schemei de hashing, fie la un moment dat când parola în sine este încă prezentă în memorie. Datorită rescrierii informațiilor folosind funcția , Argon2i și Argon2d sunt rezistente la aceste atacuri [11] . $G$

Aplicație

Argon2 este optimizat pentru arhitectura x86 și poate fi implementat pe Linux , OS X , Windows .

Argon2d este destinat sistemelor în care un atacator nu accesează în mod regulat memoria sistemului sau procesorul. De exemplu, pentru servere backend și criptomineri . Când utilizați un nucleu pe un procesor de 2 GHz și 250 MB de RAM cu Argon2d (p=2), criptominingul durează 0,1 s, iar când utilizați 4 nuclee și 4 GB de memorie (p=8) , autentificarea pe serverul backend durează 0, 5 s .

Argon2i este mai potrivit pentru serverele frontend și pentru criptarea hard diskului . Generarea cheii pentru criptare pe un procesor de 2 GHz folosind 2 nuclee și 6 GB de memorie RAM cu Argon2i (p=4) durează 3 s, în timp ce autentificarea pe serverul frontend folosind 2 nuclee și 1 GB de memorie cu Argon2i (p=4) , durează 0,5 s [12] .

Note

↑ 1 2 3 4 Concurs de hashing parole .
↑ Argon, 2016 , p. 293.
↑ Argon, 2016 , p. 292.
↑ Argon, 2016 , p. 294.
↑ Argon, 2016 , p. 294-295.
↑ 1 2 Argon, 2016 , p. 295.
↑ Argon, 2016 , p. 296-297.
↑ Henry Corrigan-Gibbs, 2016 .
↑ Alwen, Blocki, 2016 .
↑ Argon, 2016 , p. 297.
↑ Privire de ansamblu, 2015 .
↑ Argon, 2016 , p. 300.

Literatură

Joel Alwen, Jeremiah Blocki. Calcularea eficientă a funcțiilor de memorie independentă de date. - Progrese în Criptologie - CRYPTO 2016, 2016. - P. 241-271. - ISBN 978-3-662-53008-5 .
Dan Boneh, Henry Corrigan-Gibbs, Stuart Schechter. Hashing cu baloane: o funcție de memorie dificilă care oferă protecție dovedibilă împotriva atacurilor secvențiale. - Progrese în Criptologie - ASIACRYPT 2016, 2016. - P. 220-248. - ISBN 978-3-662-53887-6 .
Concurs de hashing parole . (nedefinit)
Alex Biryukov, Daniel Dinu, Dmitri Hovratovici. Argon2: noua generație de funcții de memorie hard pentru hashing parole și alte aplicații. — Simpozionul european privind securitatea și confidențialitatea, 2016.
Christian Forler, Eik List, Stefan Lucks, Jakob Wenzel. Prezentare generală a candidaților pentru competiția de hashing a parolelor și rezistența acestora împotriva atacurilor Garbage-Collector. - Tehnologia și practica parolelor, 2015. - P. 3-18. — ISBN 978-3-319-24192-0 .

Link -uri

https://github.com/PHC/phc-winner-argon2
https://www.cryptolux.org/index.php/Argon2
https://github.com/khovratovich/Argon2 (versiunea timpurie a funcției)

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Ă