scrypt - scrypt

Nesmí být zaměňována s Script (disambiguation) .
scrypt
Všeobecné
Návrháři Colin Percival
Nejprve publikováno 2009
Šifra detail
Velikosti trávení proměnná
Velikosti bloků proměnná
Kola proměnná

V kryptografii je scrypt (vyslovuje se „ess crypt“) funkce odvození klíče založená na hesle, kterou vytvořil Colin Percival, původně pro online zálohovací službu Tarsnap . Algoritmus byl speciálně navržen tak, aby byl nákladný při provádění rozsáhlých vlastních hardwarových útoků vyžadováním velkého množství paměti. V roce 2016 zveřejnil algoritmus scrypt IETF jako RFC 7914. Zjednodušená verze scrypt je používána jako schéma proof-of-work řady kryptoměn , nejprve implementována anonymním programátorem s názvem ArtForz v Tenebrix a poté Fairbrix a Litecoin brzy poté.

Úvod

Funkce odvození klíče na základě hesla (KDF založená na hesle) je obecně navržena tak, aby byla výpočetně náročná, takže výpočet trvá relativně dlouho (řekněme řádově několik stovek milisekund). Legitimní uživatelé potřebují provést funkci pouze jednou za operaci (např. Autentizace), a tak je požadovaný čas zanedbatelný. Útok hrubou silou by však pravděpodobně musel provést operaci miliardkrát, v tomto okamžiku se časové požadavky stanou významnými a v ideálním případě nepřiměřenými.

Předchozí KDF založené na heslech (například populární PBKDF2 od RSA Laboratories ) mají relativně nízké nároky na zdroje, což znamená, že k provedení nevyžadují propracovaný hardware ani příliš mnoho paměti. Jsou proto snadno a levně implementovány v hardwaru (například na ASIC nebo dokonce FPGA ). To umožňuje útočníkovi s dostatečnými prostředky zahájit rozsáhlý paralelní útok vytvořením stovek nebo dokonce tisíců implementací algoritmu v hardwaru a vyhledáváním každé jiné podmnožiny prostoru klíčů. To dělí množství času potřebného k dokončení útoku hrubou silou počtem dostupných implementací, což je velmi pravděpodobné, že se sníží na rozumný časový rámec.

Funkce scrypt je navržena tak, aby bránila takovým pokusům zvyšováním požadavků na zdroje algoritmu. Algoritmus je konkrétně navržen tak, aby používal velké množství paměti ve srovnání s jinými KDF založenými na heslech, čímž se výrazně prodražila velikost a náklady na implementaci hardwaru, a tím se omezilo množství paralelismu, které může útočník použít, pro daný množství finančních prostředků.

Přehled

Velké požadavky na paměť scrypt pocházejí z velkého vektoru pseudonáhodných bitových řetězců, které jsou generovány jako součást algoritmu. Jakmile je vektor vygenerován, k jeho prvkům se přistupuje v pseudonáhodném pořadí a spojením se vytvoří odvozený klíč. Přímočará implementace by musela zachovat celý vektor v RAM, aby k němu bylo možné přistupovat podle potřeby.

Protože prvky vektoru jsou generovány algoritmicky, každý prvek lze generovat za běhu podle potřeby, pouze ukládat jeden prvek do paměti najednou, a proto významně snížit požadavky na paměť. Generace každého prvku je však zamýšlena jako výpočetně nákladná a očekává se, že prvky budou během provádění funkce mnohokrát zpřístupněny. Existuje tedy značný kompromis v rychlosti, abychom se zbavili velkých požadavků na paměť.

Tento druh kompromisu mezi časem a pamětí často existuje v počítačových algoritmech: rychlost lze zvýšit za cenu využití více paměti nebo se nároky na paměť snižují za cenu provedení více operací a delšího trvání. Myšlenkou skryptu je záměrně učinit tento kompromis nákladným v obou směrech. Útočník by tedy mohl použít implementaci, která nevyžaduje mnoho zdrojů (a lze ji tedy masivně paralelizovat s omezenými náklady), ale běží velmi pomalu, nebo použít implementaci, která běží rychleji, ale má velmi velké požadavky na paměť, a proto je dražší paralelizovat.

Algoritmus

Function scrypt
   Inputs: This algorithm includes the following parameters:
      Passphrase:                Bytes    string of characters to be hashed
      Salt:                      Bytes    string of random characters that modifies the hash to protect against Rainbow table attacks
      CostFactor (N):            Integer  CPU/memory cost parameter - Must be a power of 2 (e.g. 1024)
      BlockSizeFactor (r):       Integer  blocksize parameter, which fine-tunes sequential memory read size and performance. (8 is commonly used)
      ParallelizationFactor (p): Integer  Parallelization parameter. (1 .. 232-1 * hLen/MFlen)
      DesiredKeyLen (dkLen):     Integer  Desired key length in bytes (Intended output length in octets of the derived key; a positive integer satisfying dkLen ≤ (232− 1) * hLen.)
      hLen:                      Integer  The length in octets of the hash function (32 for SHA256).
      MFlen:                     Integer  The length in octets of the output of the mixing function (SMix below). Defined as r * 128 in RFC7914.
   Output:
      DerivedKey:                Bytes    array of bytes, DesiredKeyLen long

   Step 1. Generate expensive salt
   blockSize ← 128*BlockSizeFactor  // Length (in bytes) of the SMix mixing function output (e.g. 128*8 = 1024 bytes)

   Use PBKDF2 to generate initial 128*BlockSizeFactor*p bytes of data (e.g. 128*8*3 = 3072 bytes)
   Treat the result as an array of p elements, each entry being blocksize bytes (e.g. 3 elements, each 1024 bytes)
   [B0...Bp−1] ← PBKDF2HMAC-SHA256(Passphrase, Salt, 1, blockSize*ParallelizationFactor)

   Mix each block in B Costfactor times using ROMix function (each block can be mixed in parallel)
   for i ← 0 to p-1 do
      Bi ← ROMix(Bi, CostFactor)

   All the elements of B is our new "expensive" salt
   expensiveSalt ← B0∥B1∥B2∥ ... ∥Bp-1  // where ∥ is concatenation
 
   Step 2. Use PBKDF2 to generate the desired number of bytes, but using the expensive salt we just generated
   return PBKDF2HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen);

Kde je v RFC 2898 definován zápis PBKDF2 (P, S, c, dkLen) , kde c je počet iterací.

Tuto notaci používá RFC 7914 k určení použití PBKDF2 s c = 1. 

Function ROMix(Block, Iterations)

   Create Iterations copies of X
   X ← Block
   for i ← 0 to Iterations−1 do
      Vi ← X
      X ← BlockMix(X)

   for i ← 0 to Iterations−1 do
      j ← Integerify(X) mod Iterations 
      X ← BlockMix(X xor Vj)

   return X

Kde RFC 7914 definuje Integerify(X)jako výsledek interpretace posledních 64 bajtů X jako integer A 1 malého endianu .

Protože Iterace se rovnají 2 síle N , jsou k výpočtu ve skutečnosti potřeba pouze první bajty stropu (N / 8) z posledních 64 bytů X, interpretované jako málo endianové celé číslo A 2 . Integerify(X) mod Iterations = A1 mod Iterations = A2 mod Iterations

Function BlockMix(B):

    The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks)
    r ← Length(B) / 128;

    Treat B as an array of 2r 64-byte chunks
    [B0...B2r-1] ← B

    X ← B2r−1
    for i ← 0 to 2r−1 do
        X ← Salsa20/8(X xor Bi)  // Salsa20/8 hashes from 64-bytes to 64-bytes
        Yi ← X

    return ← Y0∥Y2∥...∥Y2r−2 ∥ Y1∥Y3∥...∥Y2r−1

Kde Salsa20/8 je 8kolová verze Salsa20 .

Používání kryptoměny

Scrypt se používá v mnoha kryptoměnách jako algoritmus proof-of-work . Poprvé byl implementován pro Tenebrix (vydán v září 2011) a sloužil jako základ pro litecoiny a dogecoiny , které rovněž přijaly svůj skriptovací algoritmus. Těžba kryptoměn, které používají scrypt, se často provádí na grafických procesorových jednotkách ( GPU ), protože GPU mají ve srovnání s CPU podstatně větší výpočetní výkon (u některých algoritmů). To vedlo k nedostatku špičkových GPU kvůli rostoucí ceně těchto měn v měsících listopad a prosinec 2013.

Od května 2014 je pro kryptoměny založené na scryptech k dispozici specializovaný těžařský hardware ASIC .

Viz také

Reference

externí odkazy