Argon 2

Argon 2

Argon2 er en nøgleafledningsfunktion udviklet af Alex Biryukov , Daniel Dinu og Dmitry Khovratovich fra University of Luxembourg i 2015 [1] .

Dette er en moderne simpel algoritme rettet mod høj hukommelsesfyldningshastighed og effektiv brug af flere computerenheder [2] . Algoritmen er frigivet under en Creative Commons-licens .

Historie

I 2013 blev Password Hashing Competition annonceret for at skabe en ny adgangskode-hash-funktion. Kravene til den nye algoritme var mængden af brugt hukommelse, antallet af gennemløb gennem hukommelsesblokke og modstanden mod kryptoanalyse.

I 2015 blev Argon2 kåret som vinder af konkurrencen [1] . Siden dengang har algoritmen gennemgået 4 store ændringer. Nogle af beskrivelserne af algoritmer til generering af nogle blokke og tastefejl er blevet rettet, anbefalede parametre er tilføjet [1] [3] .

Input data

Argon2 bruger grundlæggende og avancerede parametre til hashing:

Hoved:

Besked (adgangskode) , længde fra til . $P$ $0$ $2^{{32}}-1$
Salt S, længde fra til . $otte$ $2^{{32}}-1$

Ekstra:

Graden af parallelitet , ethvert heltal fra til - antallet af tråde, som algoritmen kan paralleliseres til. $s$ $en$ $2^{24}-1$
Taglængde , længde fra til . $\tau$ $fire$ $2^{{32}}-1$
Hukommelsesstørrelse , heltal antal kilobytes fra til $m$ $8p$ $2^{{32}}-1$
Antal gentagelser [4] $t$

Versioner af algoritmen

Der er to versioner af algoritmen:

Argon2d - velegnet til at beskytte digitale valuta- og informationssystemer, der ikke er genstand for angreb gennem tredjepartskanaler .
Argon2i - giver høj beskyttelse mod afvejningsangreb , men er langsommere end d-versionen på grund af flere hukommelsesgennemgange [1] .

Beskrivelse

Argon2 fungerer efter følgende princip:

Adgangskoden hash ved hjælp af Blake2b hash-funktionen .
Hash-resultatet skrives til hukommelsesblokke.
Hukommelsesblokke konverteres ved hjælp af komprimeringsfunktionen $G$
Som et resultat af algoritmen genereres en nøgle ( eng. Tag ).

Udfyldning af hukommelsesblokke

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

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

$\phi _{k}(j)$ — indekseringsfunktion , — hukommelsesmatrix, — komprimeringsfunktion, — besked(adgangskode), — Blake2b hash-funktion . $B[]$ $G$ $P$ $H$

Indekseringsfunktionerne afhænger af versionen af Argon2-algoritmen:

Argon2d - afhænger af den forrige blok $\phi$

Argon2i er værdien bestemt af tilfældige talgeneratoren. $\phi$

I tilfælde af sekventiel drift anvendes komprimeringsfunktionen én gang. For Argon2d-versionen, i det -. trin, føres blokken med indekset bestemt af den foregående blok til funktionsinputtet . For Argon2i-versionen tages værdien af den tilfældige talgenerator ( i tællertilstand). $m$ $jeg$ $G$ $\phi (i)$ $\phi (i)=g(B[i])$ $G$

I tilfælde af en parallel tilstand (algoritmen er paralleliseret i tråde ) fordeles dataene over blokkene i matrixen , hvor de første blokke er resultatet af hash af inputdata, og de næste er sat af komprimeringsfunktionen for de foregående blokke og referenceblokken : $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'])\plus B ^{t-1}[i][0]$

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

$q={m' \over p}\ \ \ \ \ m'=\lfloor {m \over 4p}\rfloor 4p$ , hvor er antallet af hukommelsesblokke med en størrelse på 1024 bytes, er en hashfunktion, der tager en 32-bit repræsentation af inputparametre som input, hvis output er en 64-bit værdi, er en hashfunktion af variabel længde fra , er mængden af hukommelse, er antallet af iterationer. $m'$ $H_{0}$ $H'$ $H$ $m$ $t$

Til sidst:

$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]

At finde støtteblokken

Argon2d: vælg de første 32 bits for og de næste 32 bits for fra blokke $J_{1}$ ${\displaystyle J_{2))$ $B[i][j-1]$
Argon2i: , hvor - iterationsnummer, - linjenummer, - angiver versionen (i dette tilfælde en) $(J_{1}||J_{2})=G^{2}(null_{1024},{r||l||s||m'||t||y||i|| null_{968}})$ $r$ $l$ $y$

Dernæst bestemmes indekset for den linje, hvor blokken kommer fra. Når , tages værdien som det aktuelle linjenummer . Derefter bestemmes et sæt indekser efter 2 regler: $l=J_{2}mod\p$ $r=0,s=0$ $l$ $R$

Hvis det matcher nummeret på den aktuelle linje, tilføjes alle tidligere uoptagne blokke til indekssættet uden $l$ $B[i][j-1]$
Hvis det ikke stemmer overens, tages der blokke fra alle linjestykker og de sidste dele. $l$ $S-1=3$

Som følge heraf beregnes bloknummeret fra , som tages som reference: $r$

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

Funktion H'

Blake2b er en 64 bit version af BLAKE -funktionen , så den er bygget sådan her: $H'$

$if\ \tau \ \leq \ 64$

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

Generelt er outputværdien af funktionen bygget på de første 32 bit af blokkene - og den sidste blok : $\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

Baseret på Blake2b kompressionsfunktionen. Den modtager to 8192-bit blokke som input og producerer en 1024-bit blok. Først tilføjes to blokke ( ), derefter behandles matrixen række for række ( ), derefter behandles den resulterende matrix kolonne for kolonne ( ), og outputtet er [6] . $P$ $A=X\oplus Y$ $A_{8,8}$ $P$ $A\longrightarrow Q$ $Q\longrightarrow Z$ $G$ $Z\oplus A$

Krypteringsanalyse

Kollisionsbeskyttelse : Selve Blake2b-funktionen betragtes som kryptografisk sikker. Også under henvisning til indekseringsreglerne beviste forfatterne af algoritmen fraværet af kollisioner inden for datablokke og den lave sandsynlighed for deres forekomst, når de anvendte komprimeringsfunktionen.

Angreb for at finde forbilledet : lad angriberen samle opsådan, athan, for at fortsætte dette angreb, skal hente forbilledet:, hvilket er umuligt. Den samme begrundelse er egnet til angrebet med at finde det andet forbillede. $m$ $G(m)=h$ $n$ $H(n)=m$

Timing angreb: Hvis brugeren skal tilpasse sig et timing angreb , så bør Argon2i-versionen bruges, da den bruger uafhængig hukommelse [7] .

Angreb

Hukommelsesoptimeringsangreb

Dan Bonet , Henry Corrigan-Gibbs og Stuart Schechter viste Argon2i version 1.2 sårbarheden i deres arbejde. For single-pass versionen reducerede deres angreb hukommelsesforbruget med en faktor 4 uden at bremse udførelsen. For multi-pass versionen - 2,72 gange. Senere, i version 1.3, blev overskrivningsoperationen erstattet af XOR [8] .

AB16

Joel Alwen og Jeremiah Blocki beviste i deres arbejde, at deres AB16-angrebsalgoritme ikke kun er effektiv for Argon2i-A (fra den første version af specifikationen), men også for Argon2i-B (fra den seneste version 1.3). De viste, at angreb på Argon2 med 1 GB RAM reducerer beregningstiden med det halve. For effektiv beskyttelse skal der angives mere end 10 gennemløb. Men med den anbefalede tilgang til valg af algoritmeparametre kan der i praksis ofte kun vælges 1 pas. Udviklerne af Argon2 hævder, at ved at anvende AB16-angrebet på Argon2i-B ved , reduceres tiden med ikke mere end 2 gange op til 32 GB hukommelse og anbefaler at bruge antallet af gennemløb, der overstiger den binære logaritme af størrelsen $t=6$ $t\geq 4$ [ afklar ] brugt hukommelse [9] .

Rangeringsafvejningsangrebet

Dette angreb er et af de mest effektive for Argon2d. Det reducerer behandlingstiden med 1,33 gange. For Argon2i ved , er koefficienten 3 [10] . $t>2$

Skraldesamlerangreb

Hovedbetingelsen for det præsenterede angreb er angriberens adgang til målmaskinens interne hukommelse, enten efter at hashing-skemaet er afsluttet, eller på et tidspunkt, hvor selve adgangskoden stadig er til stede i hukommelsen. Takket være omskrivningen af information ved hjælp af funktionen , er Argon2i og Argon2d modstandsdygtige over for disse angreb [11] . $G$

Ansøgning

Argon2 er optimeret til x86- arkitektur og kan implementeres på Linux , OS X , Windows .

Argon2d er beregnet til systemer, hvor en hacker ikke regelmæssigt får adgang til systemhukommelsen eller processoren. For eksempel til backend-servere og kryptominere . Når du bruger én kerne på en 2-GHz CPU og 250 MB RAM med Argon2d (p=2), tager kryptominering 0,1 s, og når du bruger 4 kerner og 4 GB hukommelse (p=8) , tager autentificering på backend -serveren 0, 5 s .

Argon2i er mere velegnet til frontend - servere og harddiskkryptering . Nøglegenerering til kryptering på en 2-GHz CPU ved hjælp af 2 kerner og 6 GB RAM med Argon2i (p=4) tager 3 s, mens godkendelse på frontend-serveren bruger 2 kerner og 1 GB hukommelse med Argon2i (p=4) , tager 0,5 s [12] .

Noter

↑ 1 2 3 4 Password Hashing-konkurrence .
↑ 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.
↑ Oversigt, 2015 .
↑ Argon, 2016 , s. 300.

Litteratur

Joel Alwen, Jeremiah Blocki. Effektiv beregning af data-uafhængige hukommelses-hårde funktioner. - Fremskridt inden for kryptologi - CRYPTO 2016, 2016. - S. 241-271. - ISBN 978-3-662-53008-5 .
Dan Boneh, Henry Corrigan-Gibbs, Stuart Schechter. Ballonhashing: En hukommelseshård funktion, der giver beviselig beskyttelse mod sekventielle angreb. - Fremskridt inden for kryptologi - ASIACRYPT 2016, 2016. - S. 220-248. - ISBN 978-3-662-53887-6 .
Password Hashing-konkurrence . (ubestemt)
Alex Biryukov, Daniel Dinu, Dmitry Khovratovich. Argon2: ny generation af hukommelseshårde funktioner til hashing af adgangskoder og andre applikationer. — European Symposium on Security and Privacy, 2016.
Christian Forler, Eik List, Stefan Lucks, Jakob Wenzel. Oversigt over kandidaterne til Password Hashing-konkurrencen og deres modstand mod garbage-collector-angreb. - Teknologi og praktisering af adgangskoder, 2015. - S. 3-18. — ISBN 978-3-319-24192-0 .

Links

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

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge 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 Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE