scrypt

A kriptográfiában a scrypt egy kulcslevezető függvény, amit Colin Percival eredetileg a Tarsnap online biztonságimentő-szolgáltatáshoz készített el. Az algoritmust úgy fejlesztette ki, hogy sok memória kelljen a nagy méretű egyénihardver-támadásokhoz. 2016-ban a scrypt algoritmust az IETF RFC 7914 számmal kiadta. Egy egyszerűsített változatát számos kriptovaluta használja, mint pl. a LiteCoin.

Egy jelszó alapú kulcslevezető függvényt gyakran úgy terveznek, hogy sok számítást kelljen elvégezni, hogy relatív hosszú időt vegyen igénybe a kiszámítása (pl. néhány száz ezredmásodpercet). A hiteles felhasználóknak elég kevésszer végrehajtani ezt, így a szükséges idő elhanyagolható. De egy nyers erejű támadás esetén gyakran több milliárdszor kell a műveletet végrehajtani, így az elhasznált idő jelentőssé válik, ideális esetben ellehetetleníti a támadást.

Áttekintés

A scrypt nagy memóriaigénye az algoritmus részeként generált véletlenszerű bitsorozatok hatalmas vektorából ered. Amikor a vektor elkészül, elemeihez véletlenszerű sorrendben férnek, és azokat kombinálják, hogy a levezetett kulcsot kiadja.

A korábbi jelszóalapú KDF-ek (például a PBKDF2) kevéssé erőforrás-igényesek, így nem igényelnek nagy teljesítményű hardvert. Így könnyen, olcsón megvalósíthatók, például ASIC-en vagy FPGA-n. Ez lehetővé teszi egy elég erőforrással rendelkező támadónak a nagymértékű párhuzamos támadást több száz vagy ezer megvalósítás létrehozásával, melyek mindegyike a kulcstér más részében kutat. Ez a támadáshoz szükséges időt a megvalósítások számával osztja, a gyakorlatban használható időtartamra csökkentve azt.

A scrypt célja ezek gátlása az algoritmus erőforrásigényével. Az algoritmus több memóriát igényel más jelszóalapú KDF-eknél, így a hardveres megvalósítás mérete és költsége nagyobb, korlátozva a támadó által használható párhuzamosságot adott mennyiségű pénz esetén.

Mivel a vektor elemei algoritmussal jönnek létre, az elemek szükség esetén időközben is létrejöhetnek, egyidejűleg egy elem tárolásával, így a memóriaigény jelentős csökkentésével. Az elemek létrehozásának számítási tekintetben azonban költségesnek kell lennie, és az elemeket várhatóan a függvény végrehajtása során sokszor kell hozzáférni, így a sebesség kisebb az alacsony memóriaigény mellett.

Ez gyakran szerepel a számítógépes algoritmusokban: a sebesség nagyobb memóriahasználattal növelhető, a memóriahasználat több művelet végzésével csökkenthető. A scrypt ötlete, hogy ezt bármely irányban nagyon költségessé tegye. Így a támadó kis memóriaigényű, jól párhuzamosítható, de lassú vagy gyors, de nagy memóriaigényű, így kevésbé párhuzamosítható algoritmust használhat.

Története

A scryptet Colin Percival tervezte a Tarsnapnek, és 2009 májusában a BSDCan-konferencián mutatta be. 2012-ben az IETF egy scrypt-tervet internetes vázlatként közölt. 2020 augusztusában jelent meg a scrypt-1.3.1.

A scrypt nem vett részt a Password Hashing Competitionön, ahol új hasítóalgoritmust választottak, de Colin Percival részt vett szakértőként. Alexander Peslyak Yescryptje azonban igen, mely a YESCRYPT-WORM kiterjesztéssel eredeti scrypt-értékeket tudott kiadni.

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
      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);

ahol a PBKDF2(P, S, c, dkLen) jelölést az RFC 2898 határozza meg, c az ismétlésszám.

E jelölést az RFC 7914 használja a PBKDF2 használatával c=1 esetre.

function ROMix(Block, Iterations)

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

   for i ← 0 to Iterations−1
      j ← Integerify(X) % Iterations 
      X ← BlockMix(X ^ Vj)

   return X

Ahol

Integerify(X)

X utolsó 64 bájtjának little-endian egészkénti értelmezése.

Mivel Iterations = 2^N, csak az első $\lceil {N \over 8}\rceil$ bájt szükséges ténylegesen Integerify(X) % Iterations = A1%Iterations=A2%Iterations kiszámítására.

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
        X ← Salsa20/8(X ^ Bi) // Salsa20/8 hashes from 64-bytes to 64-bytes
        Yi ← X

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

ahol Salsa20/8 a 8 ismétléses Salsa20.

Kriptovaluták

A scryptet sok kriptovaluta használja ellenőrző algoritmusaiban hasítófüggvényként. Először a Tenebrix (2011) használta, és a szintén ezt használó Litecoin és Dogecoin alapja is volt. A kriptovaluták „bányászatát” gyakran grafikus feldolgozóegységeken (GPU) végzik a CPU-knál nagyobb feldolgozóképességük miatt. Ez GPU-hiányhoz vezetett az emelkedő árak miatt 2013 novemberében és decemberében.

Eszköz

A scrypt-eszközt Colin Percival 2009 májusában írta a scrypt KDF bemutatására. Számos Linux- és BSD-változaton elérhető

Fordítás

Ez a szócikk részben vagy egészben a scrypt című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• The scrypt page on the Tarsnap website.
• The original scrypt paper.