Argon2

Argon2

Argon2 je klíčová derivační funkce vyvinutá Alexem Biryukovem , Danielem Dinu a Dmitrijem Khovratovičem z Lucemburské univerzity v roce 2015 [1] .

Jedná se o moderní jednoduchý algoritmus zaměřený na vysokou rychlost zaplňování paměti a efektivní využití více výpočetních jednotek [2] . Algoritmus je vydán pod licencí Creative Commons .

Historie

V roce 2013 byla vyhlášena soutěž Password Hashing Competition s cílem vytvořit novou funkci hashování hesel. Požadavky na nový algoritmus byly množství použité paměti, počet průchodů paměťovými bloky a odolnost vůči kryptoanalýze.

V roce 2015 byl Argon2 vyhlášen vítězem soutěže [1] . Od té doby prošel algoritmus 4 zásadními změnami. Byly opraveny některé popisy algoritmů pro generování některých bloků a překlepů, přidány doporučené parametry [1] [3] .

Vstupní data

Argon2 používá základní a pokročilé parametry pro hashování:

Hlavní:

Zpráva (heslo) , délka od do . $P$ $0$ $2^{{32}}-1$
Sůl S, délka od do . $osm$ $2^{{32}}-1$

Další:

Stupeň paralelismu , libovolné celé číslo od do — počet vláken, ke kterým lze algoritmus paralelizovat. $p$ $jeden$ $2^{24}-1$
Délka značky , délka od do . $\tau$ $čtyři$ $2^{{32}}-1$
Velikost paměti , celý počet kilobajtů od do $m$ $8p$ $2^{{32}}-1$
Počet iterací [4] $t$

Verze algoritmu

Existují dvě verze algoritmu:

Argon2d - vhodný pro ochranu digitální měny a informačních systémů , které nejsou vystaveny útokům prostřednictvím kanálů třetích stran .
Argon2i - poskytuje vysokou ochranu proti kompromisním útokům , ale je pomalejší než verze d kvůli několika průchodům paměti [1] .

Popis

Argon2 funguje na následujícím principu:

Heslo je hašováno pomocí hašovací funkce Blake2b .
Výsledek hash je zapsán do paměťových bloků.
Paměťové bloky se převádějí pomocí funkce komprese $G$
V důsledku algoritmu je vygenerován klíč ( eng. Tag ).

Plnění paměťových bloků

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

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

$\phi _{k}(j)$ — indexační funkce , — paměťové pole, — kompresní funkce, — zpráva (heslo), — hašovací funkce Blake2b . $B[]$ $G$ $P$ $H$

Funkce indexování závisí na verzi algoritmu Argon2:

Argon2d - závisí na předchozím bloku $\phi$

Argon2i je hodnota určená generátorem náhodných čísel. $\phi$

V případě sekvenčního provozu se kompresní funkce použije jednou. U verze Argon2d je v -tém kroku blok s indexem určeným předchozím blokem přiveden na funkční vstup . U verze Argon2i se bere hodnota generátoru náhodných čísel ( v režimu čítače). $m$ $i$ $G$ $\phi (i)$ $\phi (i)=g(B[i])$ $G$

V případě paralelního režimu (algoritmus je paralelizován do vláken ) jsou data distribuována po blocích matice , kde první bloky jsou výsledkem hashování vstupních dat a další jsou nastaveny kompresní funkcí. pro předchozí bloky a referenční blok : $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'=\lpatro {m \over 4p}\rpatro 4p$ , kde je počet paměťových bloků o velikosti 1024 bajtů, je hašovací funkce, která jako vstup přebírá 32bitovou reprezentaci vstupních parametrů, jejímž výstupem je 64bitová hodnota, je hašovací funkce proměnné délky from , je množství paměti, je počet iterací. $m'$ $H_{0}$ $H'$ $H$ $m$ $t$

Nakonec:

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

Nalezení podpůrného bloku

Argon2d: vyberte prvních 32 bitů pro a dalších 32 bitů pro z bloků $J_{1}$ ${\displaystyle J_{2))$ $B[i][j-1]$
Argon2i: , kde - číslo iterace, - číslo řádku, - nastavuje verzi (v tomto případě jedna) $(J_{1}||J_{2})=G^{2}(null_{1024},{r||l||s||m'||t||y||i|| null_{968}})$ $r$ $l$ $y$

Dále se určí index řádku, ze kterého blok pochází. Když , je hodnota brána jako aktuální číslo řádku . Pak je sada indexů určena podle 2 pravidel: $l=J_{2}mod\p$ $r=0,s=0$ $l$ $R$

Pokud odpovídá číslu aktuálního řádku, pak jsou všechny dříve nezaznamenané bloky přidány do sady indexů bez $l$ $B[i][j-1]$
Pokud se neshoduje, bloky se převezmou ze všech segmentů čáry a posledních částí. $l$ $S-1=3$

V důsledku toho se číslo bloku vypočítá z , což se bere jako reference: $r$

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

Funkce H'

Blake2b je 64bitová verze funkce BLAKE , takže je postavena takto: $H'$

$if\ \tau \ \leq \ 64$

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

Celkově je výstupní hodnota funkce postavena na prvních 32 bitech bloků – a na posledním bloku : $\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 kompresní funkce

Na základě funkce komprese Blake2b. Jako vstup přijímá dva 8192bitové bloky a vytváří 1024bitový blok. Nejprve se přidají dva bloky ( ), poté se matice zpracuje řádek po řádku ( ), poté se výsledná matice zpracuje sloupec po sloupci ( ) a výstupem je [6] . $P$ $A=X\oplus Y$ $A_{8,8}$ $P$ $A\longrightarrow Q$ $Q\longrightarrow Z$ $G$ $Z\oplus A$

Kryptoanalýza

Ochrana proti kolizi : Samotná funkce Blake2b je považována za kryptograficky bezpečnou. Autoři algoritmu také s odkazem na pravidla indexování prokázali absenci kolizí v datových blocích a nízkou pravděpodobnost jejich výskytu při aplikaci kompresní funkce.

Útok na nalezení předobrazu : nechejte útočníka zvednout tak, žepak, aby mohl pokračovat v útoku, musí zvednout předobraz:, což je nemožné. Stejná úvaha se hodí i pro útok nalezení druhého předobrazu. $m$ $G(m)=h$ $n$ $H(n)=m$

Časové útoky: Pokud se uživatel potřebuje přizpůsobit časovacímu útoku , pak by měla být použita verze Argon2i, protože používá nezávislou paměť [7] .

Útoky

Útok optimalizace paměti

Dan Bonet , Henry Corrigan-Gibbs a Stuart Schechter ukázali ve své práci zranitelnost Argon2i verze 1.2. U jednoprůchodové verze jejich útok snížil spotřebu paměti o faktor 4, aniž by zpomalil provádění. Pro víceprůchodovou verzi - 2,72 krát. Později, ve verzi 1.3, byla operace přepsání nahrazena XOR [8] .

AB16

Joel Alwen a Jeremiah Blocki ve své práci dokázali, že jejich algoritmus útoku AB16 je účinný nejen pro Argon2i-A (od první verze specifikace), ale také pro Argon2i-B (od nejnovější verze 1.3). Ukázali, že útok na Argon2 s 1 GB RAM zkracuje dobu výpočtu na polovinu. Pro účinnou ochranu je třeba zadat více než 10 průchodů. Ale s doporučeným přístupem pro výběr parametrů algoritmu lze v praxi často vybrat pouze 1 průchod. Vývojáři Argon2 tvrdí, že použitím útoku AB16 na Argon2i-B v , se čas zkrátí maximálně 2krát až na 32 GB paměti a doporučují použít počet průchodů, který přesahuje binární logaritmus velikosti. $t=6$ $t\geq 4$ [ objasnit ] použitá paměť [9] .

The ranking tradeoff attack

Tento útok je pro Argon2d jedním z nejúčinnějších. Zkracuje dobu zpracování 1,33krát. Pro Argon2i at je koeficient 3 [10] . $t>2$

Útoky sběračů odpadků

Hlavní podmínkou pro prezentovaný útok je přístup útočníka do vnitřní paměti cílového stroje, a to buď po ukončení hashovacího schématu, nebo v určitém okamžiku, kdy je samotné heslo stále přítomno v paměti. Díky přepisování informací pomocí funkce jsou Argon2i a Argon2d vůči těmto útokům odolné [11] . $G$

Aplikace

Argon2 je optimalizován pro architekturu x86 a může být implementován na Linuxu , OS X , Windows .

Argon2d je určen pro systémy, kde útočník pravidelně nepřistupuje k systémové paměti nebo procesoru. Například pro backend servery a kryptomery . Při použití jednoho jádra na 2GHz CPU a 250 MB RAM s Argon2d (p=2) trvá kryptominace 0,1 s a při použití 4 jader a 4 GB paměti (p=8) trvá ověření na backend serveru 0,5 s .

Argon2i je vhodnější pro frontend servery a šifrování pevných disků . Generování klíče pro šifrování na 2GHz CPU pomocí 2 jader a 6 GB RAM s Argon2i (p=4) trvá 3 s, zatímco ověřování na frontend serveru pomocí 2 jader a 1 GB paměti s Argon2i (p=4) , trvá 0,5 s [12] .

Poznámky

↑ Soutěž v hašování hesel 1 2 3 4 .
↑ Argon, 2016 , str. 293.
↑ Argon, 2016 , str. 292.
↑ Argon, 2016 , str. 294.
↑ Argon, 2016 , str. 294-295.
↑ 1 2 Argon, 2016 , str. 295.
↑ Argon, 2016 , str. 296-297.
↑ Henry Corrigan-Gibbs, 2016 .
↑ Alwen, Blocki, 2016 .
↑ Argon, 2016 , str. 297.
↑ Přehled, 2015 .
↑ Argon, 2016 , str. 300.

Literatura

Joel Alwen, Jeremiah Blocki. Efektivní výpočet datově nezávislých funkcí paměti. - Pokroky v kryptologii - CRYPTO 2016, 2016. - S. 241-271. - ISBN 978-3-662-53008-5 .
Dan Boneh, Henry Corrigan-Gibbs, Stuart Schechter. Balloon Hashing: Funkce náročná na paměť poskytující prokazatelnou ochranu před sekvenčními útoky. - Pokroky v kryptologii - ASIACRYPT 2016, 2016. - S. 220-248. - ISBN 978-3-662-53887-6 .
Soutěž v hašování hesel . (neurčitý)
Alex Biryukov, Daniel Dinu, Dmitrij Chovratovič. Argon2: nová generace paměťových funkcí pro hashování hesel a další aplikace. — Evropské symposium o bezpečnosti a soukromí, 2016.
Christian Forler, Eik List, Stefan Lucks, Jakob Wenzel. Přehled kandidátů do soutěže o hašování hesel a jejich odolnost proti útokům sběračů odpadků. - Technologie a praxe hesel, 2015. - S. 3-18. — ISBN 978-3-319-24192-0 .

Odkazy

https://github.com/PHC/phc-winner-argon2
https://www.cryptolux.org/index.php/Argon2
https://github.com/khovratovich/Argon2 (časná verze funkce)

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga 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 Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA