close

Scrypt

Přejít na navigaci Přejít na hledání

scrypt
Poprvé zveřejněno května 2009

scrypt (čti es-crypt [1] ) je adaptivní funkce odvozování kryptografického klíče založená na hesle, kterou vytvořil bezpečnostní důstojník FreeBSD Colin Percival pro systém zálohování Tarsnap . Funkce je navržena tak, aby zkomplikovala útok hrubou silou pomocí FPGA . Jeho výpočet vyžaduje značné množství paměti s náhodným přístupem . 17. září 2012 zveřejnila IETF algoritmus scrypt ve formě internetového návrhu , plánuje se jeho zařazení do RFC [2] . Používá se například jako doklad o provedené práci v kryptoměna Litecoin [3] .

Funkce odvozování klíčů založené na hesle ( PBKDF ) jsou obvykle navrženy tak, aby vyžadovaly relativně dlouhé doby výpočtu (řádově stovky milisekund). Při použití legálním uživatelem je nutné takovou funkci vypočítat jednou (například při autentizaci) a takový čas je přijatelný. Při útoku hrubou silou však útočník potřebuje provést miliardy výpočtů funkcí a jeho výpočetní složitost zpomaluje a prodražuje útok.

Avšak rané PBKDF (např . PBKDF2 vyvinuté RSA Laboratories ) jsou relativně rychlé na výpočet a mohou být efektivně implementovány na specializovaném hardwaru ( FPGA nebo ASIC ). Tato implementace umožňuje spouštět rozsáhlé paralelní útoky hrubou silou, například pomocí stovek instancí funkcí v každém čipu FPGA.

Funkce scrypt byla navržena tak, aby byla hardwarová implementace složitější zvýšením množství zdrojů požadovaných pro výpočet. Tento algoritmus využívá značné množství RAM (paměť s náhodným přístupem) ve srovnání s jinými PBKDF. Paměť v scrypt se používá k uložení velkého vektoru pseudonáhodných bitových sekvencí generovaných na začátku algoritmu [4] . Jakmile je vektor vytvořen, jsou jeho prvky dotazovány v pseudonáhodném pořadí a vzájemně kombinovány za účelem získání klíče. Protože je znám algoritmus pro generování vektoru, je možné implementovat scrypt, který nevyžaduje paměť, ale vypočítává každý prvek v okamžiku přístupu. Výpočet prvku je však poměrně složitý a každý prvek je během funkce scrypt čten mnohokrát. scrypt má takovou rovnováhu mezi pamětí a časem , že nepaměťové implementace jsou příliš pomalé.

Definice scrypt

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

kde N, r, p jsou parametry určující složitost výpočtu funkce.

MFcrypt je definován takto: DK = MFcrypt PRF,MF (P, S, N, p, dkLen)

kde

  • PRF  - pseudonáhodná funkce (v scrypt - HMAC - SHA256 )
  • hLen je délka výstupu PRF v bajtech
  • MF (mixing function) - sekvenční funkce, která vyžaduje paměť s náhodným přístupem (mapování od do (v scrypt - SMix založený na Salsa20 / 8)
  • MFLen je délka bloku zamíchaná v MF (v bajtech). MFLen=128 * r.

Vstupní parametry scrypt a MFcrypt:

  • P - heslo (passphrase) - bajtový řetězec.
  • S - salt (salt) - bajtový řetězec.
  • N je parametr, který udává složitost (počet iterací pro MF).
  • r je parametr, který určuje velikost bloku.
  • p – stupeň rovnoběžnosti, celé číslo menší než (2 32 − 1)*hLen/MFLen
  • dkLen je požadovaná délka výstupního klíče v bajtech, ne větší než (2 32 − 1)*hLen.
  • DK - výstupní klíč

Funkce MFcrypt pracuje podle algoritmu:

  1. (B 0 … B p−1 ) = PBKDF2 PRF (P, S, 1, p * MFLen)
  2. Pro všechna i od 0 do p−1 použijte funkci MF:
    Bi = MF(B i , N)
  3. DK = PBKDF2 PRF (P, B0 || B1 || … || B p−1 ,1, dkLen)

Spotřeba paměti se odhaduje na 128*r*N bytů [5] . Poměr počtu čtení a zápisů do této paměti se odhaduje na 100 % a 63 % [6] .

Příklady

Doporučené parametry šifrování: N = 16384, r = 8, p = 1 (spotřeba paměti - asi 16 MB) [5] [6] .

Výpočetní rychlost pro jednu operaci scrypt na univerzálním procesoru je asi 100 milisekund, když je nakonfigurován na použití 32 MB paměti. Při nastavení na dobu trvání 1 milisekundu se používá příliš málo paměti a algoritmus se stává slabším než algoritmus bcrypt , který je nastaven na srovnatelnou rychlost [7] .

Kryptoměna Litecoin používá tyto parametry scrypt: N = 1024, r = 1, p = 1, velikost vstupního parametru a salt je 80 bajtů, velikost DK je 256 bitů (32 bajtů) [8] . Spotřeba RAM je cca 128 KB. Výpočet takového scryptu na grafických kartách je přibližně 10x rychlejší než na procesorech pro všeobecné použití [6] , což svědčí o volbě nedostatečně silných parametrů [7] .

Viz také

Poznámky

  1. ↑ Colin Percival na Twitteru: "Pro zajímavost, "scrypt" se vyslovuje "ess crypt". Jako bcrypt, až na to, že má S místo B. NENÍ to vyslovováno "script"." . Staženo 4. května 2017. Archivováno z originálu 17. února 2019.
  2. ↑ C. Percival, S. Josefsson. Funkce odvození klíče na základě hesla  scrypt (neopr.) . - Internet Engineering Council , 2012. - 17. září.
  3. ↑ Litecoin-Bitcoin . Získáno 16. července 2013. Archivováno z originálu 16. června 2018.
  4. ↑ Archivovaná kopie (odkaz není dostupný) . Získáno 17. července 2013. Archivováno z originálu 17. prosince 2013.   strana 5
  5. ↑ 1 2 Crypto.Scrypt
  6. ↑ 1 2 3 http://2012.zeronights.org/includes/docs/SolarDesigner%20-%20New%20Developments%20in%20Password%20Hashing.pdf Archivováno 28. prosince 2016 na snímku Wayback Machine se 4 „Iscryptem“ hromadné ověření uživatele"; snímek 6
  7. ↑ 1 2 http://distro.ibiblio.org/openwall/presentations/Password-Hashing-At-Scale/YaC2012-Password-Hashing-At-Scale.pdf Archivováno 18. října 2014 na snímku Wayback Machine 18 "GPU Attacks na moderních hashech": "šifrovat až ~1 MB (zneužití)"; snímek 19-21
  8. ↑ Scrypt - Litecoin Wiki (downlink) . Získáno 17. července 2013. Archivováno z originálu 16. srpna 2013. 

Odkazy

Implementace:

Zdroj – https://ru.wikipedia.org/w/index.php?title=Scrypt&oldid=124355421