Argon 2

Argon 2

Argon2 on keskeinen johdannaisfunktio, jonka ovat kehittäneet Alex Biryukov , Daniel Dinu ja Dmitry Khovratovich Luxemburgin yliopistosta vuonna 2015 [ 1] .

Tämä on moderni yksinkertainen algoritmi, joka tähtää korkeaan muistin täyttöasteeseen ja useiden laskentayksiköiden tehokkaaseen käyttöön [2] . Algoritmi julkaistaan Creative Commons -lisenssillä .

Historia

Vuonna 2013 Password Hashing Competition julkistettiin uuden salasanan hajautustoiminnon luomiseksi. Vaatimukset uudelle algoritmille olivat käytetyn muistin määrä, muistilohkojen läpikulkujen määrä ja kryptausanalyysin kestävyys.

Vuonna 2015 Argon2 julistettiin kilpailun voittajaksi [1] . Sen jälkeen algoritmiin on tehty 4 suurta muutosta. Joitakin lohkojen ja kirjoitusvirheiden muodostavien algoritmien kuvauksia on korjattu, suositeltuja parametreja on lisätty [1] [3] .

Syöttötiedot

Argon2 käyttää perus- ja lisäparametreja tiivistykseen:

Pääasiallinen:

Viesti (salasana) , pituus välillä - . $P$ $0$ $2^{{32}}-1$
Suola S, pituus välillä - . $kahdeksan$ $2^{{32}}-1$

Lisätiedot:

Yhdensuuntaisuuden aste , mikä tahansa kokonaisluku alkaen - — niiden säikeiden lukumäärä, joihin algoritmi voidaan rinnastaa. $s$ $yksi$ $2^{24}-1$
Tunnisteen pituus , pituus välillä - . $\tau$ $neljä$ $2^{{32}}-1$
Muistin koko , kokonaisluku kilotavuja välillä - $m$ $8p$ $2^{{32}}-1$
Iteraatioiden määrä [4] ${\näyttötyyli t}$

Algoritmin versiot

Algoritmista on kaksi versiota:

Argon2d - sopii suojaamaan digitaalista valuuttaa ja tietojärjestelmiä, jotka eivät ole alttiina hyökkäyksille kolmansien osapuolien kanavien kautta .
Argon2i - tarjoaa korkean suojan kompromisseja vastaan , mutta on hitaampi kuin d-versio useiden muistinkulkujen vuoksi [1] .

Kuvaus

Argon2 toimii seuraavan periaatteen mukaisesti:

Salasana tiivistetään Blake2b- hajautustoiminnolla .
Hajautustulos kirjoitetaan muistilohkoihin.
Muistilohkot muunnetaan käyttämällä pakkaustoimintoa $G$
Algoritmin tuloksena syntyy avain ( eng. Tag ).

Muistilohkojen täyttäminen

$B[0]=H(P,S)$

$B[j]=G(B[\phi _{1}(j)],B[\phi _{2}(j)],...,B[\phi _{k}(j )])$ ,, missä $j=1...t$

$\phi _{k}(j)$ — indeksointitoiminto — muistitaulukko — pakkaustoiminto — viesti (salasana), — Blake2b- hajautustoiminto . $B[]$ $G$ $P$ $H$

Indeksointitoiminnot riippuvat Argon2-algoritmin versiosta:

Argon2d - riippuu edellisestä lohkosta $\phi$

Argon2i on satunnaislukugeneraattorin määrittelemä arvo. $\phi$

Jos kyseessä on peräkkäinen toiminta, pakkaustoimintoa käytetään kerran. Argon2d-versiossa -:nnessa vaiheessa edellisen lohkon määrittämä indeksi syötetään funktion tuloon . Argon2i-versiossa otetaan satunnaislukugeneraattorin arvo ( laskuritilassa). $m$ $i$ $G$ $\phi (i)$ $\phi (i)=g(B[i])$ $G$

Rinnakkaistilassa (algoritmi rinnastetaan säikeiksi ) tiedot jaetaan matriisin lohkoille , jolloin ensimmäiset lohkot ovat tulotietojen hajautustuloksia ja seuraavat asetetaan pakkausfunktiolla. edellisille lohkoille ja viitelohkolle : $p$ $B[i][j]$ $G$ $B^{1}[i'][j']$

$B^{1}[i][0]=H'(\ H_{0}\ ||\ {\underset {4bytes}{0))\ ||\ {\underset {4bytes}{i} }\ ),0\leq i<p$

$B^{1}[i][1]=H'(\ H_{0}\ ||\ {\underset {4bytes}{1))\ ||\ {\underset {4bytes}{i} }\ ),0\leq i<p$

$B^{1}[i][j]=G(B^{1}[i][j-1],B^{1}[i'][j']),0\leq i <p$

$B^{t}[i][0]=G(B^{t-1}[i][q-1],B^{1}[i'][j'])\oplus B ^{t-1}[i][0]$

$B^{t}[i][j]=G(B^{t}[i][j-1],B^{1}[i'][j'])\oplus B^{ t-1}[i][j]$

$q={m' \over p}\ \ \ \ \ m'=\lfloor {m \over 4p}\rfloor 4p$ , jossa on 1024 tavun kokoisten muistilohkojen lukumäärä, on hash-funktio, joka ottaa syötteeksi 32-bittisen esityksen tuloparametreista, jonka lähtö on 64-bittinen arvo, on muuttuvan pituinen hash-funktio alkaen , on muistin määrä, on iteraatioiden lukumäärä. $m'$ $H_{0}$ $H'$ $H$ $m$ ${\näyttötyyli t}$

Lopulta:

$B_{final}=B^{T}[0][q-1]\oplus B^{T}[1][q-1]\oplus ...\oplus B^{T}[p -1][q-1]$

$Tag\leftarrow H'(B_{lopullinen})$ [5]

Tukilohkon etsiminen

Argon2d: valitse lohkoista ensimmäiset 32 bittiä ja seuraavat 32 bittiä $J_{1}$ $J_{2}$ $B[i][j-1]$
Argon2i: , jossa - iteraationumero, - rivin numero, - asettaa version (tässä tapauksessa yhden) $(J_{1}||J_{2})=G^{2}(nolla_{1024},{r||l||s||m'||t||y||i|| null_{968}})$ $r$ $l$ $y$

Seuraavaksi määritetään sen rivin indeksi , josta lohko tulee. Kun arvoksi otetaan nykyinen rivinumero . Sitten joukko indeksejä määritetään kahden säännön mukaisesti: $l=J_{2}mod\p$ $r=0,s=0$ $l$ $R$

Jos se vastaa nykyisen rivin numeroa, kaikki aiemmin tallentamattomat lohkot lisätään indeksijoukkoon ilman $l$ $B[i][j-1]$
Jos se ei täsmää, lohkot otetaan kaikista viivan osista ja viimeisistä osista. $l$ $S-1=3$

Tämän seurauksena lohkon numero lasketaan kohdasta , jota pidetään viitteenä: $r$

$z=|R|-1-({\frac {|R|*((J_{1})^{2}/2^{32})}{2^{32))})$ [6]

Funktio H'

Blake2b on 64-bittinen versio BLAKE -funktiosta , joten se on rakennettu seuraavasti: $H'$

$if\ \tau \ \leq \ 64$

$H'(X)=H_{\tau }(\tau ||X).$

Yleisesti ottaen funktion lähtöarvo rakentuu lohkojen ensimmäisille 32 bitille - ja viimeiselle lohkolle : $\tau$ $A_{i}$ $V_i$

$r=\lceil \tau /32\rceil -2$

$V_{1}\longleftarrow H_{64}(\tau ||X)$

$V_{r+1}\longleftarrow H_{\tau -32r}(V_{r})$

$H'(X)=A_{1}||A_{2}||...A_{r}||V_{r+1}$

G-pakkaustoiminto

Perustuu Blake2b-pakkausominaisuuteen. Se vastaanottaa kaksi 8192-bittistä lohkoa tulona ja tuottaa 1024-bittisen lohkon. Ensin lisätään kaksi lohkoa ( ), sitten matriisi käsitellään rivi riviltä ( ), sitten tuloksena oleva matriisi käsitellään sarake sarakkeelta ( ) ja tulos on [6] . $P$ $A=X\oplus Y$ $A_{8,8}$ $P$ $A\longrightarrow Q$ $Q\longrightarrow Z$ $G$ $Z\oplus A$

Kryptanalysis

Törmäyssuojaus : Itse Blake2b-toimintoa pidetään kryptografisesti turvallisena. Lisäksi algoritmin laatijat osoittivat indeksointisääntöihin viitaten törmäysten puuttumisen datalohkojen sisällä ja niiden esiintymisen pienen todennäköisyyden pakkausfunktiota käytettäessä.

Hyökkäys esikuvan löytämiseksi : anna hyökkääjän poimianiin, ettäjatkaakseen hyökkäystä hänen täytyy poimia esikuva:, mikä on mahdotonta. Sama päättely soveltuu toisen esikuvan etsimiseen. $m$ $G(m)=h$ $n$ $H(n)=m$

Ajoitushyökkäykset : Jos käyttäjän on sopeuduttava ajoitushyökkäykseen , tulee käyttää Argon2i-versiota, koska se käyttää itsenäistä muistia [7] .

Hyökkäykset

Muistin optimointihyökkäys

Dan Bonet , Henry Corrigan-Gibbs ja Stuart Schechter osoittivat Argon2i version 1.2 haavoittuvuuden työssään. Yksikierrosversiossa heidän hyökkäyksensä vähensi muistin kulutusta kertoimella 4 hidastamatta suoritusta. Monikierrosversiolle - 2,72 kertaa. Myöhemmin versiossa 1.3 korvausoperaatio korvattiin XOR :lla [8] .

AB16

Joel Alwen ja Jeremiah Blocki osoittivat työssään, että heidän AB16-hyökkäysalgoritminsa on tehokas paitsi Argon2i-A:lle (erittelyn ensimmäisestä versiosta), mutta myös Argon2i-B:lle (uusimmasta versiosta 1.3). He osoittivat, että Argon2:n hyökkääminen 1 Gt RAM-muistilla vähentää laskenta-aikaa puoleen. Tehokas suojaus edellyttää yli 10 läpimenoa. Mutta suositellulla menetelmällä algoritmiparametrien valintaan käytännössä usein voidaan valita vain 1 kierros. Argon2:n kehittäjät väittävät, että käyttämällä AB16-hyökkäystä Argon2i-B:lle klo , aika lyhenee enintään 2 kertaa muistiin asti, ja suosittelevat käyttämään koon binäärilogaritmin ylittävää läpikulkua. $t=6$ $t\geq 4$ [ selventää ] käytetty muisti [9] .

Sijoituksen kompromissihyökkäys

Tämä hyökkäys on yksi tehokkaimmista Argon2d:lle. Se lyhentää käsittelyaikaa 1,33 kertaa. Argon2i: n kohdalla kerroin on 3 [10] . $t>2$

Roskakeräilijöiden hyökkäykset

Esitetyn hyökkäyksen pääehto on hyökkääjän pääsy kohdekoneen sisäiseen muistiin joko hajautusjärjestelmän päätyttyä tai jossain vaiheessa, kun itse salasana on vielä muistissa. Toiminnon avulla tapahtuvan tietojen uudelleenkirjoituksen ansiosta Argon2i ja Argon2d kestävät näitä hyökkäyksiä [11] . $G$

Sovellus

Argon2 on optimoitu x86 - arkkitehtuurille ja voidaan toteuttaa Linuxissa , OS X :ssä ja Windowsissa .

Argon2d on tarkoitettu järjestelmiin, joissa hyökkääjä ei käytä säännöllisesti järjestelmämuistia tai prosessoria. Esimerkiksi taustapalvelimille ja kryptomineraajille . Käytettäessä yhtä ydintä 2 GHz:n suorittimessa ja 250 Mt RAM-muistia Argon2d:n kanssa (p=2), kryptominointi kestää 0,1 s, ja käytettäessä 4 ydintä ja 4 Gt muistia (p=8 ) todennus taustapalvelimella kestää 0, 5 s .

Argon2i sopii paremmin käyttöliittymäpalvelimiin ja kiintolevyn salaukseen . Avaimen luominen salausta varten 2 GHz:n suorittimessa , jossa on 2 ydintä ja 6 Gt RAM-muistia Argon2i:n kanssa (p=4), kestää 3 sekuntia, kun taas todennus käyttöliittymäpalvelimella käyttämällä kahta ydintä ja 1 Gt muistia Argon2i:n avulla (p=4) , kestää 0,5 s [12] .

Muistiinpanot

↑ 1 2 3 4 Salasanan hajautuskilpailu .
↑ Argon, 2016 , s. 293.
↑ Argon, 2016 , s. 292.
↑ Argon, 2016 , s. 294.
↑ Argon, 2016 , s. 294-295.
↑ 1 2 Argon, 2016 , s. 295.
↑ Argon, 2016 , s. 296-297.
↑ Henry Corrigan-Gibbs, 2016 .
↑ Alwen, Blocki, 2016 .
↑ Argon, 2016 , s. 297.
↑ Yleiskatsaus, 2015 .
↑ Argon, 2016 , s. 300.

Kirjallisuus

Joel Alwen, Jeremiah Blocki. Laskee tehokkaasti datasta riippumattomia muisti-kovatoimintoja. - Kryptologian edistysaskel - CRYPTO 2016, 2016. - S. 241-271. - ISBN 978-3-662-53008-5 .
Dan Boneh, Henry Corrigan-Gibbs, Stuart Schechter. Balloon Hashing: Muistia vaativa toiminto, joka tarjoaa todistetusti suojan peräkkäisiä hyökkäyksiä vastaan. - Kryptologian edistysaskel - ASIACRYPT 2016, 2016. - S. 220-248. - ISBN 978-3-662-53887-6 .
Salasanan hajautuskilpailu . (määrätön)
Alex Biryukov, Daniel Dinu, Dmitry Khovratovich. Argon2: uuden sukupolven muistia vaativia toimintoja salasanan hajautus- ja muihin sovelluksiin. — European Symposium on Security and Privacy, 2016.
Christian Forler, Eik List, Stefan Lucks, Jakob Wenzel. Yleiskatsaus salasanojen hajautuskilpailun ehdokkaisiin ja heidän vastustukseensa roskienkeräilijöiden hyökkäyksiä vastaan. - Salasanojen tekniikka ja käytäntö, 2015. - S. 3-18. — ISBN 978-3-319-24192-0 .

Linkit

https://github.com/PHC/phc-winner-argon2
https://www.cryptolux.org/index.php/Argon2
https://github.com/khovratovich/Argon2 (ominaisuuden varhainen versio)

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA