Argon 2

Argon 2

Argon2 är en nyckelhärledningsfunktion utvecklad av Alex Biryukov , Daniel Dinu och Dmitry Khovratovich vid universitetet i Luxemburg 2015 [1] .

Detta är en modern enkel algoritm som syftar till hög minnesfyllnadshastighet och effektiv användning av flera beräkningsenheter [2] . Algoritmen släpps under en Creative Commons-licens .

Historik

2013 tillkännagavs Password Hashing Competition för att skapa en ny lösenordshashningsfunktion. Kraven för den nya algoritmen var mängden minne som användes, antalet passeringar genom minnesblock och motståndet mot kryptoanalys.

2015 utsågs Argon2 till vinnare av tävlingen [1] . Sedan dess har algoritmen genomgått 4 stora förändringar. Några av beskrivningarna av algoritmer för att generera vissa block och stavfel har korrigerats, rekommenderade parametrar har lagts till [1] [3] .

Indata

Argon2 använder grundläggande och avancerade parametrar för hash:

Huvudsakliga:

Meddelande (lösenord) , längd från till . $P$ $0$ $2^{{32}}-1$
Salt S, längd från till . $åtta$ $2^{{32}}-1$

Ytterligare:

Graden av parallellitet , vilket heltal som helst från till – antalet trådar som algoritmen kan parallelliseras till. $sid$ $ett$ $2^{24}-1$
Tagglängd , längd från till . $\tau$ $fyra$ $2^{{32}}-1$
Minnesstorlek , heltal antal kilobyte från till $m$ $8p$ $2^{{32}}-1$
Antal iterationer [4] $t$

Versioner av algoritmen

Det finns två versioner av algoritmen:

Argon2d - lämplig för att skydda digitala valuta- och informationssystem som inte utsätts för attacker via tredjepartskanaler .
Argon2i - ger högt skydd mot avvägningsattacker , men är långsammare än d-versionen på grund av flera minnespass [1] .

Beskrivning

Argon2 fungerar enligt följande princip:

Lösenordet hashas med Blake2b- hashfunktionen .
Hashresultatet skrivs till minnesblock.
Minnesblock konverteras med hjälp av komprimeringsfunktionen $G$
Som ett resultat av algoritmen genereras en nyckel ( eng. Tag ).

Fylla minnesblock

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

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

$\phi _{k}(j)$ — indexeringsfunktion , — minnesmatris, — komprimeringsfunktion, — meddelande(lösenord), — Blake2b hash-funktion . $B[]$ $G$ $P$ $H$

Indexeringsfunktionerna beror på versionen av Argon2-algoritmen:

Argon2d - beror på föregående block $\phi$

Argon2i är värdet som bestäms av slumptalsgeneratorn. $\phi$

Vid sekventiell drift tillämpas komprimeringsfunktionen en gång. För Argon2d-versionen, i det -e steget, matas blocket med indexet som bestämts av föregående block till funktionsingången . För Argon2i-versionen tas värdet av slumptalsgeneratorn ( i räknarläge). $m$ $i$ $G$ $\phi (i)$ $\phi (i)=g(B[i])$ $G$

I fallet med ett parallellt läge (algoritmen är parallelliserad till trådar ) fördelas data över blocken i matrisen , där de första blocken är resultatet av hashning av indata, och de nästa ställs in av komprimeringsfunktionen för de föregående blocken och referensblocket : $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$ , där är antalet minnesblock med en storlek på 1024 byte, är en hashfunktion som tar en 32-bitars representation av ingångsparametrar som indata, vars utdata är ett 64-bitars värde, är en hashfunktion av variabel längd från , är mängden minne, är antalet iterationer. $m'$ $H_{0}$ $H'$ $H$ $m$ $t$

Så småningom:

$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_{final})$ [5]

Hitta stödblocket

Argon2d: välj de första 32 bitarna för och nästa 32 bitar för från block $J_{1}$ $J_{2}$ $B[i][j-1]$
Argon2i: , där - iterationsnummer, - radnummer, - anger versionen (i detta fall en) $(J_{1}||J_{2})=G^{2}(null_{1024},{r||l||s||m'||t||y||i|| null_{968}})$ $r$ $l$ $y$

Därefter bestäms indexet för linjen där blocket kommer ifrån. När tas värdet som det aktuella radnumret . Sedan bestäms en uppsättning index enligt 2 regler: $l=J_{2}mod\p$ $r=0,s=0$ $l$ $R$

Om det matchar numret på den aktuella raden, läggs alla tidigare oinspelade block till indexuppsättningen utan $l$ $B[i][j-1]$
Om det inte matchar, tas block från alla linjesegment och de sista delarna. $l$ $S-1=3$

Som ett resultat beräknas blocknumret från , som tas som referens: $r$

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

Funktion H'

Blake2b är en 64-bitarsversion av BLAKE- funktionen , så den är byggd så här: $H'$

$if\ \tau \ \leq \ 64$

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

I stort bygger funktionens utdatavärde på de första 32 bitarna av blocken - och det sista blocket : $\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 komprimeringsfunktion

Baserat på Blake2b-kompressionsfunktionen. Den tar emot två 8192-bitars block som indata och producerar ett 1024-bitars block. Först läggs två block till ( ), sedan bearbetas matrisen rad för rad ( ), sedan bearbetas den resulterande matrisen kolumn för kolumn ( ), och utmatningen är [6] . $P$ $A=X\oplus Y$ $A_{8,8}$ $P$ $A\longrightarrow Q$ $Q\longrightarrow Z$ $G$ $Z\oplus A$

Kryptanalys

Kollisionsskydd : Själva Blake2b-funktionen anses vara kryptografiskt säker. Dessutom, med hänvisning till indexeringsreglerna, bevisade författarna till algoritmen frånvaron av kollisioner inom datablock och den låga sannolikheten för att de skulle inträffa när komprimeringsfunktionen användes.

Attack för att hitta förbilden : låt angriparen plocka uppså att, för att fortsätta denna attack, han måste plocka upp förbilden:, vilket är omöjligt. Samma resonemang är lämpligt för attacken att hitta den andra förbilden. $m$ $G(m)=h$ $n$ $H(n)=m$

Tajmingsattacker: Om användaren behöver anpassa sig till en timingattack bör Argon2i-versionen användas eftersom den använder oberoende minne [7] .

Attacker

Minnesoptimeringsattack

Dan Bonet , Henry Corrigan-Gibbs och Stuart Schechter visade Argon2i version 1.2 sårbarheten i sitt arbete. För single-pass versionen minskade deras attack minnesförbrukningen med en faktor 4 utan att sakta ner exekveringen. För multipassversionen - 2,72 gånger. Senare, i version 1.3, ersattes överskrivningsoperationen av XOR [8] .

AB16

Joel Alwen och Jeremiah Blocki bevisade i sitt arbete att deras AB16-attackalgoritm är effektiv inte bara för Argon2i-A (från den första versionen av specifikationen), utan även för Argon2i-B (från den senaste versionen 1.3). De visade att attacken av Argon2 med 1 GB RAM minskar beräkningstiden med hälften. För effektivt skydd måste fler än 10 pass anges. Men med det rekommenderade tillvägagångssättet för att välja algoritmparametrar kan i praktiken ofta bara 1 pass väljas. Utvecklarna av Argon2 hävdar att genom att applicera AB16-attacken på Argon2i-B vid , reduceras tiden med högst 2 gånger upp till 32 GB minne och rekommenderar att du använder antalet pass som överstiger den binära logaritmen för storleken $t=6$ $t\geq 4$ [ förtydliga ] använt minne [9] .

Ranking avvägningsattacken

Denna attack är en av de mest effektiva för Argon2d. Det minskar bearbetningstiden med 1,33 gånger. För Argon2i vid , är koefficienten 3 [10] . $t>2$

Skräpsamlarattacker

Huvudvillkoret för den presenterade attacken är angriparens åtkomst till målmaskinens interna minne, antingen efter att hashing-schemat har avslutats, eller vid någon tidpunkt när själva lösenordet fortfarande finns i minnet. Tack vare omskrivningen av information med funktionen , är Argon2i och Argon2d resistenta mot dessa attacker [11] . $G$

Applikation

Argon2 är optimerad för x86 - arkitektur och kan implementeras på Linux , OS X , Windows .

Argon2d är avsedd för system där en angripare inte regelbundet kommer åt systemminnet eller processorn. Till exempel för backend-servrar och kryptominerare . När du använder en kärna på en 2 GHz CPU och 250 MB RAM med Argon2d (p=2), tar kryptominering 0,1 s, och när du använder 4 kärnor och 4 GB minne (p=8) tar autentiseringen på backend -servern 0, 5 s .

Argon2i är mer lämplig för frontend-servrar och hårddiskkryptering . Nyckelgenerering för kryptering på en 2 GHz CPU med 2 kärnor och 6 GB RAM med Argon2i (p=4) tar 3 s, medan autentisering på frontendservern använder 2 kärnor och 1 GB minne med Argon2i (p=4) , tar 0,5 s [12] .

Anteckningar

↑ 1 2 3 4 Lösenordshashing-tävling .
↑ Argon, 2016 , sid. 293.
↑ Argon, 2016 , sid. 292.
↑ Argon, 2016 , sid. 294.
↑ Argon, 2016 , sid. 294-295.
↑ 1 2 Argon, 2016 , sid. 295.
↑ Argon, 2016 , sid. 296-297.
↑ Henry Corrigan-Gibbs, 2016 .
↑ Alwen, Blocki, 2016 .
↑ Argon, 2016 , sid. 297.
↑ Översikt, 2015 .
↑ Argon, 2016 , sid. 300.

Litteratur

Joel Alwen, Jeremiah Blocki. Effektiv beräkning av dataoberoende minnes-hårda funktioner. - Framsteg inom kryptologi - CRYPTO 2016, 2016. - P. 241-271. - ISBN 978-3-662-53008-5 .
Dan Boneh, Henry Corrigan-Gibbs, Stuart Schechter. Ballonghashing: En minneshård funktion som ger bevisligt skydd mot sekventiella attacker. - Framsteg inom kryptologi - ASIACRYPT 2016, 2016. - P. 220-248. - ISBN 978-3-662-53887-6 .
Lösenordshasningstävling . (obestämd)
Alex Biryukov, Daniel Dinu, Dmitry Khovratovich. Argon2: ny generation av minneshårda funktioner för hashing av lösenord och andra applikationer. — European Symposium on Security and Privacy, 2016.
Christian Forler, Eik List, Stefan Lucks, Jakob Wenzel. Översikt över kandidaterna till Password Hashing-tävlingen och deras motstånd mot sopsamlarattacker. - Teknik och praktisering av lösenord, 2015. - S. 3-18. — ISBN 978-3-319-24192-0 .

Länkar

https://github.com/PHC/phc-winner-argon2
https://www.cryptolux.org/index.php/Argon2
https://github.com/khovratovich/Argon2 (tidig version av funktionen)

Hash-funktioner
generell mening	Adler-32 CRC Fletcher kontrollsumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hashträd jenkins hash hash summa
Kryptografisk	Stribog GOST R 34,11-94 Bälte BLAKE bmw CubeHash EKO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H 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 Hud Snefru Tiger Bubbelpool
Nyckelgenereringsfunktioner	bcrypt PBKDF2 kryptera Argon 2 Lyra2
Kontrollnummer ( jämförelse )	Kontrollera summan Verhouffs algoritm Månen algoritm Jävla algoritm Streckkod bankkonton bankkort ÄR I SNILS OKPO TENN OKATO ISBN OGRN och OGRNIP VIN
Hashes	Jämförelse av checknummer Autentiseringsprotokoll Streckkodsjämförelse Kryptografi Magnet länk Merkle signatur ed2k URNA