Scrypt

scrypt
Először megjelent 2009. május

A scrypt (olvassa el az es-crypt [1] ) egy adaptív, jelszó alapú kriptográfiai kulcs-levezető funkció , amelyet a FreeBSD biztonsági tisztje, Colin Percival hozott létre a Tarsnap biztonsági mentési rendszerhez . A funkciót úgy tervezték meg, hogy bonyolítsa az FPGA -t használó brute-force támadást . Kiszámítása jelentős mennyiségű , véletlen hozzáférésű memóriát igényel . A titkosítási algoritmust 2012. szeptember 17-én tette közzé az IETF Internet Draft formájában , a tervek szerint az RFC -be is beépítik [2] . Használják például a Litecoin kriptovalutában végzett munka igazolására [3] .

A jelszó alapú kulcs-levezetési függvényeket ( PBKDF ) általában úgy tervezték, hogy viszonylag hosszú számítási időt igényeljenek (nagyságrendileg több száz ezredmásodperc). Jogi felhasználó általi használat esetén egy ilyen függvényt egyszer kell kiszámítani (például hitelesítés során), és ez az idő elfogadható. A brute-force támadásnál azonban a támadónak több milliárd függvényszámítást kell végrehajtania, és a számítási összetettség miatt a támadás lassabb és drágább.

A korai PBKDF-ek (pl . az RSA Laboratories által kifejlesztett PBKDF2 ) azonban viszonylag gyorsan kiszámíthatók, és speciális hardveren ( FPGA vagy ASIC ) hatékonyan implementálhatók. Ez a megvalósítás lehetővé teszi nagyszabású párhuzamos brute force támadások indítását, például több száz függvénypéldány felhasználásával minden FPGA chipben.

A scrypt funkciót úgy tervezték, hogy a számításhoz szükséges erőforrások mennyiségének növelésével bonyolultabbá tegye a hardver megvalósítását. Ez az algoritmus más PBKDF-ekhez képest jelentős mennyiségű RAM-ot (random access memory) használ. A scrypt-ben lévő memória az algoritmus elején generált pszeudo-véletlen bitsorozatok nagy vektorának tárolására szolgál [4] . Miután létrehoztunk egy vektort, elemeit pszeudo-véletlen sorrendben lekérdezzük, és egymással kombinálva kulcsot kapunk. Mivel a vektor generálására szolgáló algoritmus ismert, lehetséges a scrypt megvalósítása, amely nem igényel memóriát, de az egyes elemeket a hozzáférés időpontjában számítja ki. Egy elem kiszámítása azonban viszonylag bonyolult, és a titkosítási funkció során minden elemet sokszor ki kell olvasni. A scrypt olyan egyensúlyban van a memória és az idő között , hogy a nem memóriás megvalósítások túl lassúak.

A scrypt meghatározása

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

ahol N, r, p a függvényszámítás bonyolultságát meghatározó paraméterek.

Az MFcrypt definíciója a következő: DK = MFcrypt PRF,MF (P, S, N, p, dkLen)

ahol

Bemeneti paraméterek scrypt és MFcrypt:

Az MFcrypt függvény a következő algoritmus szerint működik:

  1. (B 0 … B p−1 ) = PBKDF2 PRF (P, S, 1, p * MFLen)
  2. Minden i-re 0-tól p-1-ig alkalmazza az MF függvényt: B i = MF(B i , N)
  3. DK = PBKDF2 PRF (P, B0 || B1 || … || B p−1 ,1, dkLen)

A memóriafelhasználást 128*r*N bájtra becsülik [5] . Az olvasások és írások számának ehhez a memóriához viszonyított arányát 100%-ra és 63%-ra becsülik [6] .

Példák

Javasolt titkosítási paraméterek: N = 16384, r = 8, p = 1 (memóriafogyasztás - körülbelül 16 MB) [5] [6] .

Egy általános célú processzoron végzett egyetlen titkosítási művelet számítási sebessége körülbelül 100 ezredmásodperc, ha 32 MB memória használatára van beállítva. Ha 1 ezredmásodperces időtartamra van beállítva, túl kevés memória kerül felhasználásra, és az algoritmus gyengébb lesz, mint a bcrypt algoritmus , amely hasonló sebességre van beállítva [7] .

A Litecoin kriptovaluta a következő titkosítási paramétereket használja: N = 1024, r = 1, p = 1, a bemeneti paraméter és a só mérete 80 bájt, a DK mérete 256 bit (32 bájt) [8] . A RAM-fogyasztás körülbelül 128 KB. Az ilyen titkosítás kiszámítása a videokártyákon körülbelül 10-szer gyorsabb, mint az általános célú processzorokon [6] , ami a nem kellően erős paraméterek megválasztását jelzi [7] .

Lásd még

Jegyzetek

  1. ↑ Colin Percival a Twitteren: "Egyébként a "scrypt" szót "ess crypt"-nek ejtik. Mint a bcrypt, kivéve, ha a B helyett S betű van. NEM ejtik "script"." . Letöltve: 2017. május 4. Az eredetiből archiválva : 2019. február 17.
  2. ↑ C. Percival, S. Josefsson. A scrypt jelszó alapú kulcs származtatási függvény  (neopr.) . - Internet Engineering Council , 2012. - szeptember 17.
  3. ↑ Litecoin-Bitcoin . Letöltve: 2013. július 16. Az eredetiből archiválva : 2018. június 16.
  4. ↑ Archivált másolat (a hivatkozás nem elérhető) . Letöltve: 2013. július 17. Az eredetiből archiválva : 2013. december 17..   5. oldal
  5. ↑ 1 2 Crypto.Scrypt
  6. ↑ 1 2 3 http://2012.zeronights.org/includes/docs/SolarDesigner%20-%20New%20Developments%20in%20Password%20Hashing.pdf Archiválva : 2016. december 28. a Wayback Machine 4 "Is crypts foru diával" tömeges felhasználói hitelesítés"; 6. dia
  7. ↑ 1 2 http://distro.ibiblio.org/openwall/presentations/Password-Hashing-At-Scale/YaC2012-Password-Hashing-At-Scale.pdf Archiválva : 2014. október 18., a Wayback Machine 18 "GPU Attacks slide modern kivonatokon": "~1 MB-ig titkosítás (helytelen használat)"; dia 19-21
  8. ↑ Scrypt - Litecoin Wiki (downlink) . Letöltve: 2013. július 17. Az eredetiből archiválva : 2013. augusztus 16.. 

Linkek

Megvalósítások:

 Hash függvények
Általános rendeltetésű
Kriptográfia
Kulcsgenerálási funkciók
Csekkszám ( összehasonlítás )
Hashes