scrypt - scrypt
| Kenraali | |
|---|---|
| Suunnittelijat | Colin Percival |
| Ensimmäinen julkaistu | 2009 |
| Salaus yksityiskohdat | |
| Digest koot | muuttuja |
| Lohkojen koot | muuttuja |
| Kierrokset | muuttuja |
Vuonna kryptografia , scrypt (lausutaan "ess crypt") on salasanaan perustuvaa avaimenjohtamisfunktiota luonut Colin Percival, alunperin varten Tarsnap Online Backup palvelua. Algoritmi on suunniteltu erityisesti tekemään kalliiksi suorittaa suuria mukautettuja laitteistohyökkäyksiä vaatimalla suuria määriä muistia. Vuonna 2016 scrypt algoritmi on julkaissut IETF RFC 7914. yksinkertaistettu versio scrypt käytetään proof-of-työtä järjestelmän useat cryptocurrencies , toteutettiin ensimmäisen anonyymi ohjelmoija kutsutaan ArtForz sisään Tenebrix ja seurasi Fairbrix ja Litecoin pian sen jälkeen.
Johdanto
Salasanapohjainen avaimen johtamistoiminto (salasanapohjainen KDF) on yleensä suunniteltu laskennallisesti intensiiviseksi, joten sen laskeminen vie suhteellisen kauan (esimerkiksi usean sadan millisekunnin luokkaa). Laillisten käyttäjien on suoritettava toiminto vain kerran operaatiota kohti (esim. Todennus), joten tarvittava aika on vähäinen. Kuitenkin raa'an voiman hyökkäyksen olisi todennäköisesti suoritettava operaatio miljardeja kertoja, jolloin aikavaatimuksista tulee merkittäviä ja mieluiten kiellettyjä.
Edellinen salasana-pohjainen KDFs (kuten suosittu PBKDF2 alkaen RSA Laboratories ) on suhteellisen vähän resursseja vaatimukset, eli ne eivät vaadi monimutkaisia laitteistoa tai erittäin paljon muistia suorittamiseen. Siksi ne on helppo ja halpa toteuttaa laitteistossa (esimerkiksi ASIC: ssä tai jopa FPGA: ssa ). Tämän avulla hyökkääjä, jolla on riittävät resurssit, voi käynnistää laajamittaisen rinnakkaishyökkäyksen rakentamalla satoja tai jopa tuhansia algoritmin toteutuksia laitteistoon ja pyytämällä kutakin etsimään eri avaintilan osajoukkoa. Tämä jakaa raa'an voiman hyökkäyksen suorittamiseen tarvittavan ajan käytettävissä olevien toteutusten lukumäärällä, mikä saattaa mahdollisesti vähentää sen kohtuulliseen ajanjaksoon.
Scrypt-toiminto on suunniteltu estämään tällaisia yrityksiä nostamalla algoritmin resurssitarpeita. Algoritmi on suunniteltu käyttämään paljon muistia verrattuna muihin salasanapohjaisiin KDF-tiedostoihin, mikä tekee laitteistototeutuksen koon ja kustannukset paljon kalliimmaksi ja rajoittaa siten hyökkääjän käyttämän rinnakkaisuuden määrää tietyllä hetkellä taloudellisten resurssien määrä.
Yleiskatsaus
Scryptin suuret muistivaatimukset johtuvat suuresta näennäissatunnaisten bittijonojen vektorista, jotka syntyvät osana algoritmia. Kun vektori on luotu, sen elementteihin pääsee näennäissatunnaisessa järjestyksessä ja yhdistetään johdetun avaimen tuottamiseksi. Suoraviivainen toteutus vaatii koko vektorin pitämisen RAM-muistissa, jotta sitä voidaan käyttää tarvittaessa.
Koska vektorin elementit generoidaan algoritmisesti, kukin elementti voidaan luoda tarvittaessa lennossa , vain yksi elementti tallentuu muistiin kerrallaan ja vähentää siten muistivaatimuksia merkittävästi. Jokaisen elementin luomisen on kuitenkin tarkoitus olla laskennallisesti kallista, ja elementteihin odotetaan pääsevän useita kertoja koko toiminnon suorittamisen ajan. Siten nopeus on merkittävä kompromissi, jotta voidaan päästä eroon suurista muistivaatimuksista.
Tällainen aikamuistin kompromissi esiintyy usein tietokonealgoritmeissa: nopeutta voidaan lisätä muistin käytön kustannuksella tai muistin tarve vähenee, kun suoritetaan enemmän toimintoja ja kestää kauemmin. Scryptin idea on tehdä tämä kaupankäynti tarkoituksella kalliiksi kumpaankin suuntaan. Siksi hyökkääjä voi käyttää toteutusta, joka ei vaadi paljon resursseja (ja joka voidaan siten rinnakkain rajallisin kustannuksin), mutta toimii hyvin hitaasti, tai käyttää toteutusta, joka toimii nopeammin, mutta jolla on erittäin suuret muistivaatimukset ja joka on siksi kalliimpi rinnastaa.
Algoritmi
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);
Jos PBKDF2 (P, S, c, dkLen) -merkintä on määritelty standardissa RFC 2898, missä c on iteraatioluku.
Tätä merkintää käyttää RFC 7914 PBKDF2: n käytön määrittämiseen 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
Jossa RFC 7914 määrittelee Integerify(X)seurauksena tulkita viimeisen 64 tavua X niin vähän endian kokonaisluvun a 1 .
Koska iteraatiot on yhtä suuri kuin 2 potenssiin N, vain ensimmäinen Katto (N / 8) tavua joukossa viimeisen 64 tavua X, tulkitaan vähän endian kokonaisluvun a 2 , ovat itse asiassa tarvitaan laskea .
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
Jossa Salsa20 / 8 on 8-kierros versioon Salsa20 .
Kryptovaluutta käyttää
Scrypt käytetään monissa cryptocurrencies kuin proof-of-työtä algoritmin. Se otettiin ensimmäisen kerran käyttöön Tenebrixille (julkaistu syyskuussa 2011) ja toimi pohjana Litecoinille ja Dogecoinille , jotka myös ottivat käyttöön salausalgoritminsa. Louhinta cryptocurrencies että käytön scrypt usein suoritetaan Grafiikkaprosessori ( GPU ) vuodesta grafiikkapiiriä yleensä huomattavasti enemmän laskentatehoa (noin algoritmeja) verrattuna CPU. Tämä johti huippuluokan grafiikkasuorittimien puutteeseen johtuen näiden valuuttojen hinnannoususta marras- ja joulukuussa 2013.
Toukokuusta 2014 lähtien erikoistunut ASIC- kaivoslaitteisto on saatavilla skriptipohjaisille salausvaluutoille.
Katso myös
- Avaimen johtotoiminto
- Argon2 , salasanan hajautuskilpailun voittaja
- salaus , salasanan tallennus- ja vahvistusjärjestelmä
- PBKDF2 , laajalti käytetty salasanapohjainen avainjohdannaistoiminto
- bcrypt , salasanan hajautustoiminto Blowfishin avulla
- Aika-aika-kompromissi
