Krypt

krypt
Først udgivet maj 2009

scrypt (læs es-crypt [1] ) er en adaptiv adgangskodebaseret kryptografisk nøgleafledningsfunktion skabt af FreeBSD sikkerhedsofficer Colin Percival til Tarsnap backup-lagersystemet . Funktionen er designet på en sådan måde, at den komplicerer brute-force-angrebet ved hjælp af FPGA . Dens beregning kræver en betydelig mængde hukommelse med tilfældig adgang . Den 17. september 2012 blev krypteringsalgoritmen udgivet af IETF i form af en Internet Draft , den er planlagt til at blive inkluderet i RFC [2] . Det bruges for eksempel som bevis på arbejde udført i Litecoin- kryptovalutaen [3] .

Adgangskodebaserede nøgleafledningsfunktioner ( PBKDF'er ) er typisk designet til at kræve relativt lange beregningstider (i størrelsesordenen hundreder af millisekunder). Når det bruges af en lovlig bruger, er det nødvendigt at beregne en sådan funktion én gang (for eksempel under godkendelse), og en sådan tid er acceptabel. Men i et brute-force-angreb skal angriberen udføre milliarder af funktionsberegninger, og dets beregningsmæssige kompleksitet gør angrebet langsommere og dyrere.

Imidlertid er tidlige PBKDF'er (f.eks. PBKDF2 udviklet af RSA Laboratories ) relativt hurtige at beregne og kan effektivt implementeres på specialiseret hardware ( FPGA eller ASIC ). Denne implementering giver dig mulighed for at starte store parallelle brute-force-angreb, for eksempel ved at bruge hundredvis af funktionsforekomster i hver FPGA-chip.

Krypteringsfunktionen blev designet til at gøre hardwareimplementeringer mere komplekse ved at øge mængden af ​​ressourcer, der kræves til beregning. Denne algoritme bruger en betydelig mængde RAM (Random Access Memory) sammenlignet med andre PBKDF'er. Hukommelsen i scrypt bruges til at lagre en stor vektor af pseudo-tilfældige bitsekvenser genereret i begyndelsen af ​​algoritmen [4] . Når først en vektor er blevet oprettet, forespørges dens elementer i en pseudo-tilfældig rækkefølge og kombineres med hinanden for at opnå en nøgle. Da algoritmen til at generere vektoren er kendt, er det muligt at implementere scrypt, som ikke kræver hukommelse, men beregner hvert element på adgangstidspunktet. At beregne et element er imidlertid relativt komplekst, og hvert element læses mange gange under krypteringsfunktionen. scrypt har en sådan balance mellem hukommelse og tid , at implementeringer uden hukommelse er for langsomme.

Definition af scrypt

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

hvor N, r, p er parametre, der specificerer kompleksiteten af ​​funktionsberegningen.

MFcrypt er defineret sådan: DK = MFcrypt PRF,MF (P, S, N, p, dkLen)

hvor

Inputparametre scrypt og MFcrypt:

MFcrypt - funktionen fungerer i henhold til algoritmen:

  1. (B 0 … B p−1 ) = PBKDF2 PRF (P, S, 1, p * MFLen)
  2. For alle i fra 0 til p−1 skal du anvende MF-funktionen: Bi = MF( Bi , N)
  3. DK = PBKDF2 PRF (P, B0 || B1 || … || B p−1 ,1, dkLen)

Hukommelsesforbruget er estimeret til 128*r*N bytes [5] . Forholdet mellem antallet af læsninger og skrivninger til denne hukommelse er estimeret til 100 % og 63 % [6] .

Eksempler

Anbefalede krypteringsparametre: N = 16384, r = 8, p = 1 (hukommelsesforbrug - ca. 16 MB) [5] [6] .

Beregningshastigheden for en enkelt krypteringsoperation på en generel processor er omkring 100 millisekunder, når den er konfigureret til at bruge 32 MB hukommelse. Når den indstilles til en varighed på 1 millisekund, bruges der for lidt hukommelse, og algoritmen bliver svagere end bcrypt- algoritmen , som er sat til en sammenlignelig hastighed [7] .

Litecoin - krypteringsvalutaen bruger følgende krypteringsparametre: N = 1024, r = 1, p = 1, størrelsen af ​​inputparameteren og salt er 80 bytes, størrelsen af ​​DK er 256 bit (32 bytes) [8] . RAM-forbruget er omkring 128 KB. Beregningen af ​​en sådan kryptering på videokort er cirka 10 gange hurtigere end på processorer til generelle formål [6] , hvilket er en indikation af valget af utilstrækkeligt stærke parametre [7] .

Se også

Noter

  1. ↑ Colin Percival på Twitter: "For ordens skyld udtales "scrypt" "ess crypt". Ligesom bcrypt, undtagen med et S i stedet for B. Det udtales IKKE "script"." . Hentet 4. maj 2017. Arkiveret fra originalen 17. februar 2019.
  2. ↑ C. Percival, S. Josefsson. Den krypterede adgangskodebaserede  nøgleafledningsfunktion (neopr.) . - Internet Engineering Council , 2012. - 17. september.
  3. ↑ Litecoin-Bitcoin . Hentet 16. juli 2013. Arkiveret fra originalen 16. juni 2018.
  4. ↑ Arkiveret kopi (link ikke tilgængeligt) . Hentet 17. juli 2013. Arkiveret fra originalen 17. december 2013.   side 5
  5. ↑ 1 2 Crypto.Scrypt
  6. ↑ 1 2 3 http://2012.zeronights.org/includes/docs/SolarDesigner%20-%20New%20Developments%20in%20Password%20Hashing.pdf Arkiveret 28. december 2016 på Wayback Machine -dias 4 "Problemer med scrypt massebrugergodkendelse"; slide 6
  7. ↑ 1 2 http://distro.ibiblio.org/openwall/presentations/Password-Hashing-At-Scale/YaC2012-Password-Hashing-At-Scale.pdf Arkiveret 18. oktober 2014 på Wayback Machine- dias 18 "GPU-angreb på moderne hashes": "kryptere med op til ~1MB (misbrug)"; rutsjebane 19-21
  8. ↑ Scrypt - Litecoin Wiki (downlink) . Hentet 17. juli 2013. Arkiveret fra originalen 16. august 2013. 

Links

Implementeringer:

 Hash funktioner
generelle formål
Kryptografisk
Nøglegenereringsfunktioner
Tjek nummer ( sammenligning )
Hashes