Lyra2

Lyra2
Creată	2014
publicat	2014
Tip de	funcția hash

Lyra2 este o funcție hash criptografică care poate fi folosită și ca funcție de derivare a cheilor . Lyra2 a fost creat de Marcos Simplicio Jr., Leonardo C. Almeida, Everton R. Andrade, Paulo C. F. Santos și Paulo C. L. M. Barreto de la Școala Politehnică a Universității din São Paulo [1] . Lyra2 este unul dintre algoritmii de hashing folosiți pe scară largă împreună cu PBKDF2 , bcrypt și scrypt . Cu toate acestea, înainte de apariția Lyra2, scrypt era singura soluție disponibilă care ținea cont de costurile de memorie și de timp de procesare. Lyra2 a introdus îmbunătățiri precum: separarea memoriei și a parametrilor de procesare, ceea ce oferă mai multă flexibilitate utilizatorilor; folosind o funcție de bază de burete, mai degrabă decât cele două utilizate în scrypt; rezistență mai mare la atacuri folosind compromisuri timp-memorie ; și o performanță mai bună, permițând o utilizare mai mare a memoriei pentru un timp de procesare similar [2] .

Lyra2 este disponibil gratuit și are două extensii: [3]

Lyra2-δ, oferind utilizatorului mai mult control asupra lățimii de bandă.
Lyra2p, care folosește posibilitățile de paralelism ale sistemelor de calcul ale utilizatorilor algoritmului.

Rezistența la atac

Principalele avantaje ale algoritmului:

Costurile de memorie și de timp pot fi separate, ceea ce vă permite să utilizați resursele mai inteligent.
Rapid datorită utilizării funcției burete cu un număr redus de runde în algoritm.
Furnizarea de ieșire de orice lungime dorită, deci poate funcționa ca o funcție de derivare a tastei .

Lyra2 poate fi configurat atât pentru a proteja împotriva platformelor atacante, cât și pentru a optimiza performanța pe platforma utilizatorului:

Suport paralelism pentru sisteme multiprocesor .
Posibilitatea de a utiliza diverse funcții de bază ale bureților.
Posibilitatea de a crește lățimea de bandă a memoriei pentru algoritm.

Costul de calcul al atacului se situează asimptotic între și atunci când se utilizează ordinea memoriei pe platforma utilizatorului. Alți algoritmi nu sunt inferiori acestor indicatori, dar în practică au o valoare mai mică decât cea a Lyra2. [4] [5] [6] [7] [8] $O(2^{nT}R^{3})$ $O(2^{nT}R^{n+2})$ $1/2^{n+2}$ $O(R)$

Funcția burete

Funcțiile burete criptografice sunt funcții hash capabile să proceseze iterativ lungimi arbitrare ale datelor de intrare și de ieșire. Proiectarea lor implică o permutare cu lungime fixă care operează pe o stare internă reprezentată de o secvență de mărimi de biți, constând dintr-o rată de biți de lungime și o capacitate de lungime , combinată cu datele de intrare tăiate în blocuri de b -biți. Funcția burete include o operație de absorbție, care trebuie să se aplice în mod iterativ la starea internă după aplicarea operației de rată de biți la fiecare dintre biții de intrare b - biți. Rețineți că numărul de iterații în această operație este dat de parametrul numărul de runde . Operația de strângere, la rândul său, este o aplicație pentru întreaga stare internă și emiterea ulterioară a unui bitrate la ieșire, această operație va fi efectuată până când numărul de biți specificat de utilizator este furnizat ca ieșire. Există, de asemenea, o operație duplex, care este o serie de perechi de operații de absorbție și stoarcere aplicate secvențial. $f$ $b+c$ $b$ $c$ $M$ $f$ $XOR$ $\rho$ $f$

Parametrii algoritmului

Lyra2 oferă posibilitatea de a configura algoritmul în cel mai potrivit mod pentru nevoile utilizatorului. Acest lucru este furnizat de diverși parametri ai algoritmului, cum ar fi: [3]

Timp de execuție (cost de timp)
Memoria necesară (numărul de rânduri și coloane din matrice)
Gradul de paralelism (număr de fire )
Funcția principală a buretelui
Numărul de blocuri utilizate de funcția principală de burete (bitrate)
Numărul de runde pentru funcția de bază a bureților
Lungimea secvenței de ieșire

Dispozitiv de algoritm

Ca orice altă funcție hash criptografică, Lyra2 ia o sare și o parolă ca intrare, producând o secvență pseudo-aleatorie ca rezultat . Pe plan intern, memoria sa este organizată ca o matrice bidimensională ale cărei celule sunt citite și scrise iterativ, numită pur și simplu matrice de memorie [2] . De asemenea, este de remarcat faptul că numărul de vizite la celula matricei pentru recalcularea acesteia este determinat de utilizator, ceea ce vă permite să ajustați algoritmul în conformitate cu capacitățile sistemelor de calcul ale utilizatorului. Inițializarea și vizitarea matricei utilizează o combinație a stărilor de funcționare absorb, stoarcere și duplex ale funcției principale a buretelui, asigurând consistența întregului proces. În plus, utilizatorii pot defini dimensiunea matricei și numărul de revizii la celulele acesteia după inițializare, ceea ce permite reglarea fină a utilizării resurselor Lyra2. Lyra2 constă din patru faze consecutive: bootstrapping, setup, wandering și wrap-up.

Bootstrapping

În această etapă, starea internă a funcției principale a buretelui este inițializată. Introducerea funcției principale a buretelui primește o parolă, sare și alți parametri. Parametrii sunt de obicei reprezentați de lungimea parametrilor de sare, parolă, timp și cost de memorie, adică cei care sunt setați de utilizator, pot fi adăugați și alții. Pe această intrare se efectuează o operație de absorbție, iar starea internă a funcției burete este inițializată.

Înființat

În etapa de configurare, matricea de memorie este inițializată. Celulele matricei au o lungime de biți, adică dimensiunea ratei de biți a funcției principale a buretelui. Pentru a îmbunătăți performanța atunci când lucrați cu o matrice de memorie potențial mare, instalatorul folosește operația duplex cu burete pe coloanele matricei de memorie cu mai puține runde. Această abordare accelerează operațiunile cu burete și, astfel, permite acoperirea mai multor poziții de memorie într-un interval dat, având în vedere constrângerile de timp, decât cu un ciclu complet f. Această fază se încheie când toate coloanele matricei de memorie au fost vizitate. $b$

Rătăcire

Faza de wander constă în rescrierea pseudo-aleatorie a celulelor matricei de memorie folosind operația duplex pe coloane în același mod ca în faza de configurare. Numărul de iterații în această etapă este limitat de parametrul costului de timp.

învelire

În această etapă, se aplică operația de absorbție cu numărul maxim de runde, apoi operația de strângere, iar la ieșire se obține o secvență pseudo-aleatorie de o dimensiune dată.

Notaţie Simbolurile ⊕ denotă exclusiv pe biți sau (XOR), în timp ce ⊞ denotă adăugarea de cuvinte mașină. Concatenare între matricele de octeți a și b se scrie a || b. Pentru o matrice de octeți x, notația |x| și, respectiv, medie len(x), lungimea lui x în biți și octeți (adică numărul minim de biți/octeți necesar pentru reprezentări x). Se presupune că computerul are little-endian ordinea octeților, în această descriere a algoritmului, lsw(x) returnează cel mai puțin semnificativ prin cuvântul x, iar rot^y(x) este o deplasare circulară pe w-biți a lui x la stânga, repetată de de ori. Param: H # Funcție burete cu număr maxim de runde p_max Param: p # Numărul de runde pentru fazele de configurare și de rătăcire, p < p_max Param: Hp # Funcție burete cu număr redus de runde p Param: w # Numărul de biți utilizați pentru deplasarea ciclică Intrare: pwd # Parolă Intrare: sare # Sare Intrare: T # Parametru care definește costul în timp Intrare: R, C # Parametri care determină costul memoriei Intrare: k # Lungimea secvenței de ieșire în biți Ieșire: K # Hash dependent de parolă de lungime k biți Bootstrapping Params <- len(k) || len(pwd) || len(sare) || T || R || C # Reprezentând parametrii ca o secvență de octeți H.absorb(pad(pwd || sare || params)) # Împărțiți secvența în subsecvențe de lungime b biți Anterior0 <- 2 ; rândul 1 <- 1; prev1<-0 Înființat Pentru (col <- 0 la C-1) faceți {M[0][C-1-col] <- Hp.squeeze(b)} final pentru # Inițializați M[0] Pentru (col <- 0 la C-1) faceți {M[1][C-1-col] <-M[0][col] ⊕ Hp.duplex(M[0][col], b)} sfârșit pentru # Inițializați M[1] Pentru (col <- 0 la C-1) faceți {M[2][C-1-col] <-M[1][col] ⊕ Hp.duplex(M[1][col], b)} sfârșit pentru # Inițializați M[2] Pentru (rândul 0 <- 3 la R-1) faceți # Inițializați rândurile rămase Pentru (col <- 0 la C-1) faceți # Iterați peste coloane, M[row0] este inițializat aici și M[row1] este suprascris rand <- Hp.duplex(M[rând1][col] ⊞ M[prev0][col] ⊞ M[prev1][col], b) M[rând0][C-1-col] <- M[prev0][col] ⊕ rand M[rând1][C-1-col] <- M[rând1][col] ⊕ rot(rand) # rot(): rotiți w biți sfârşitul pentru prev0 <- row0 ; prev1 <- row1 # Definiți rândurile care vor fi utilizate în următoarea iterație getNext(row1) # Actualizați rândul 1 pentru următoarea iterație Sfârșit pentru Rătăcire Pentru (wCount <- 0 la R*T - 1) nu #2*R*T rândurile vor fi suprascrise pseudo-aleatoriu row0 <- lsw(rand) mod R ; row1 <- lsw(rot(rand)) mod R # Rândurile sunt selectate aleatoriu pentru (col <- 0 la C-1) face col0 <- lsw(rot^2(rand)) mod C ; col1 <- lsw(rot^3(rand)) mod C # Selecție pseudoaleatorie a coloanelor rand <- Hp.duplex(M[rând0][col] ⊞ M[rând1][col] ⊞ M[prev0][col] ⊞ M[prev1][col], b) M[row0][col] <- M[row0][col] ⊕ rand # Suprascrie celula pseudo-aleatorie M[rând1][col] <- M[rând1][col] ⊕ rot(rand) # rot(): rotiți w biți sfârşitul pentru prev0 <- row0 ; prev1 <- row1 # Definiți rândurile care vor fi utilizate în următoarea iterație Sfârșit pentru învelire h.absorb(M[rând0][0]) K <- H.strângere(k) Întoarce K

Performanță

Lyra2 vă permite să efectuați calcule în mai puțin de 1 secundă folosind 400 MB de memorie cu valorile parametrilor și [2] . $T=4$ $R=2^{15}$

Testele au fost efectuate pe un procesor Intel Xeon E5-2430 (2,20 GHz, 12 nuclee, sistem pe 64 de biți) cu 48 GB DRAM , pe sistemul de operare Ubuntu 14.04 LTS pe 64 de biți , codul algoritmului a fost compilat folosind gcc 4.9. 2 [2 ] .

Note

↑ Arhiva Cryptology ePrint: Raport 2015/136 . eprint.iacr.org . Consultat la 22 martie 2016. Arhivat din original pe 9 martie 2016. (nedefinit)
↑ 1 2 3 4 Andrade, E.; Simplicio Jr, M.; Barreto, P.; Santos, P. Lyra2: hashing eficient al parolelor cu securitate ridicată împotriva compromisurilor timp-memorie // IEEE Transactions on Computers : jurnal. - 2016. - 1 ianuarie ( vol. PP , nr. 99 ). - P. 3096-3108 . — ISSN 0018-9340 . - doi : 10.1109/TC.2016.2516011 .
↑ 1 2 Simplicio Jr, Marcos A.; Almeida, Leonardo C.; Andrade, Everton R.; Santos, Paulo C.; Barreto, Paulo SLM Ghidul de referință Lyra2 . AMP . Concursul de hashing a parolelor. Preluat la 6 decembrie 2019. Arhivat din original la 30 noiembrie 2020. (nedefinit)
↑ Gmane -- Alte teste mecanice candidate la PHC . article.gmane.org . Preluat: 22 martie 2016. (nedefinit) (link indisponibil)
↑ Gmane -- O recenzie pe zi Lyra2 . article.gmane.org . Preluat: 22 martie 2016. (nedefinit) (link indisponibil)
↑ Gmane -- Revizuirea inițială a Lyra2 . article.gmane.org . Preluat: 22 martie 2016. (nedefinit) (link indisponibil)
↑ Gmane - Performanța memoriei și atacurile ASIC . article.gmane.org . Preluat: 22 martie 2016. (nedefinit) (link indisponibil)
↑ Gmane -- Analiză rapidă a Argonului . article.gmane.org . Preluat: 22 martie 2016. (nedefinit) (link indisponibil)

Link -uri

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Ă