Cripta

cripta
Prima publicat mai 2009

scrypt (citește es-crypt [1] ) este o funcție adaptivă de derivare a cheilor criptografice bazată pe parolă creată de ofițerul de securitate FreeBSD Colin Percival pentru sistemul de stocare de rezervă Tarsnap . Funcția este concepută astfel încât să complice atacul cu forță brută folosind FPGA . Calculul său necesită o cantitate semnificativă de memorie cu acces aleatoriu . La 17 septembrie 2012, algoritmul scrypt a fost publicat de IETF sub forma unui Internet Draft , acesta este planificat să fie inclus în RFC [2] . Este folosit, de exemplu, ca dovadă a muncii depuse în criptomoneda Litecoin [3] .

Funcțiile de derivare a cheilor bazate pe parole ( PBKDF ) sunt de obicei concepute pentru a necesita timpi de calcul relativ lungi (de ordinul mărimii, sute de milisecunde). Atunci când este utilizat de un utilizator legal, este necesar să se calculeze o astfel de funcție o dată (de exemplu, în timpul autentificării) și un astfel de timp este acceptabil. Dar într-un atac cu forță brută , atacatorul trebuie să efectueze miliarde de calcule de funcții, iar complexitatea sa de calcul face ca atacul să fie mai lent și mai costisitor.

Cu toate acestea, PBKDF-urile timpurii (de exemplu , PBKDF2 dezvoltat de RSA Laboratories ) sunt relativ rapid de calculat și pot fi implementate eficient pe hardware specializat ( FPGA sau ASIC ). Această implementare vă permite să lansați atacuri paralele de forță brută la scară largă, de exemplu, folosind sute de instanțe de funcție în fiecare cip FPGA.

Funcția scrypt a fost concepută pentru a face implementările hardware mai complexe prin creșterea cantității de resurse necesare pentru calcul. Acest algoritm folosește o cantitate semnificativă de RAM (memorie cu acces aleatoriu) în comparație cu alte PBKDF. Memoria din scrypt este folosită pentru a stoca un vector mare de secvențe de biți pseudo-aleatorie generate la începutul algoritmului [4] . Odată ce un vector a fost creat, elementele sale sunt interogate într-o ordine pseudo-aleatoare și combinate între ele pentru a obține o cheie. Deoarece algoritmul de generare a vectorului este cunoscut, este posibil să se implementeze scrypt, care nu necesită memorie, dar calculează fiecare element în momentul accesării. Cu toate acestea, calcularea unui element este relativ complexă și fiecare element este citit de multe ori în timpul funcției scrypt. scrypt are un astfel de echilibru între memorie și timp, încât implementările non-memory sunt prea lente.

Definiția scrypt

scrypt (P, S, N, r, p, dkLen) = MFcrypt HMAC SHA256,SMix r (P, S, N, p, dkLen)

unde N, r, p sunt parametri care specifică complexitatea calculului funcției.

MFcrypt este definit astfel: DK = MFcrypt PRF,MF (P, S, N, p, dkLen)

Unde

Parametrii de intrare scrypt și MFcrypt:

Funcția MFcrypt funcționează conform algoritmului:

  1. (B 0 … B p−1 ) = PBKDF2 PRF (P, S, 1, p * MFLen)
  2. Pentru toate i de la 0 la p−1, aplicați funcția MF: Bi = MF(B i , N)
  3. DK = PBKDF2 PRF (P, B0 || B1 || … || B p−1 ,1, dkLen)

Consumul de memorie este estimat la 128*r*N octeți [5] . Raportul dintre numărul de citiri și scrieri în această memorie este estimat la 100% și 63% [6] .

Exemple

Parametrii scrypt recomandați: N = 16384, r = 8, p = 1 (consum de memorie - aproximativ 16 MB) [5] [6] .

Viteza de calcul pentru o singură operațiune de criptare pe un procesor de uz general este de aproximativ 100 de milisecunde atunci când este configurată pentru a utiliza 32 MB de memorie. Când se setează la o durată de 1 milisecundă, se folosește prea puțină memorie și algoritmul devine mai slab decât algoritmul bcrypt , care este setat la o viteză comparabilă [7] .

Criptomoneda Litecoin folosește următorii parametri scrypt: N = 1024, r = 1, p = 1, dimensiunea parametrului de intrare și sare este de 80 de octeți, dimensiunea DK este de 256 de biți (32 de octeți) [8] . Consumul de RAM este de aproximativ 128 KB. Calculul unui astfel de scrypt pe plăcile video este de aproximativ 10 ori mai rapid decât pe procesoarele de uz general [6] , ceea ce este un indiciu al alegerii unor parametri insuficient de puternici [7] .

Vezi și

Note

  1. ↑ Colin Percival pe Twitter: „Pentru evidență, „scrypt” se pronunță „ess crypt”. Ca și bcrypt, cu excepția cu un S în loc de B. NU se pronunță „script”.” . Preluat la 4 mai 2017. Arhivat din original pe 17 februarie 2019.
  2. ↑ C. Percival, S. Josefsson. Funcția de derivare a cheii bazată pe parolă scrypt  (neopr.) . - Internet Engineering Council , 2012. - 17 septembrie.
  3. ↑ Litecoin-Bitcoin . Consultat la 16 iulie 2013. Arhivat din original la 16 iunie 2018.
  4. ↑ Copie arhivată (link nu este disponibil) . Consultat la 17 iulie 2013. Arhivat din original la 17 decembrie 2013.   pagina 5
  5. ↑ 1 2 Crypto.Scrypt
  6. ↑ 1 2 3 http://2012.zeronights.org/includes/docs/SolarDesigner%20-%20New%20Developments%20in%20Password%20Hashing.pdf Arhivat 28 decembrie 2016 pe diapozitivul Wayback Machine 4 „Probleme cu scrypt pentru autentificarea în masă a utilizatorilor”; slide 6
  7. ↑ 1 2 http://distro.ibiblio.org/openwall/presentations/Password-Hashing-At-Scale/YaC2012-Password-Hashing-At-Scale.pdf Arhivat la 18 octombrie 2014 la diapozitivul Wayback Machine 18 „GPU Attacks pe hash-uri moderne": "criptare până la ~1MB (utilizare greșită)"; slide 19-21
  8. ↑ Scrypt - Litecoin Wiki (link în jos) . Consultat la 17 iulie 2013. Arhivat din original la 16 august 2013. 

Link -uri

Implementări:

 Funcții hash
scop general
Criptografic
Funcții de generare a cheilor
Numărul de verificare ( comparație )
Hashes