Lyra2

Lyra2
Vytvořeno 2014
zveřejněno 2014
Typ hashovací funkce

Lyra2  je kryptografická hašovací funkce , kterou lze také použít jako funkci odvození klíče . Lyra2 vytvořili Marcos Simplicio Jr., Leonardo C. Almeida, Everton R. Andrade, Paulo C. F. Santos a Paulo C. L. M. Barreto z Polytechnické školy Univerzity v São Paulu [1] . Lyra2 je jedním z široce používaných hashovacích algoritmů spolu s PBKDF2 , bcrypt a scrypt . Před příchodem Lyra2 však byl scrypt jediným dostupným řešením, které zohledňovalo náklady na paměť a dobu zpracování. Lyra2 představila vylepšení, jako jsou: oddělení paměti a parametrů zpracování, které uživatelům poskytuje větší flexibilitu; použití jedné základní funkce houby spíše než dvou používaných v scrypt; vyšší odolnost vůči útokům pomocí kompromisů mezi časem a pamětí ; a lepší výkon umožňující vyšší využití paměti při podobné době zpracování [2] .

Lyra2 je volně dostupná a má dvě rozšíření: [3]

Odolnost proti útokům

Hlavní výhody algoritmu:

  1. Paměťové a časové náklady lze oddělit, což vám umožňuje využívat zdroje inteligentněji.
  2. Rychlý díky použití funkce houby se sníženým počtem nábojů v algoritmu.
  3. Poskytuje výstup libovolné požadované délky, takže může fungovat jako funkce odvození klíče .

Lyra2 lze nakonfigurovat tak, aby chránila před útočícími platformami a optimalizovala výkon na platformě uživatele:

Výpočetní náklady útoku leží asymptoticky mezi a při použití pořadí paměti na uživatelské platformě. Jiné algoritmy nejsou horší než tyto indikátory, ale v praxi mají hodnotu nižší než Lyra2. [4] [5] [6] [7] [8]

Funkce houby

Funkce kryptografické houby jsou hashovací funkce schopné iterativně zpracovávat libovolné délky vstupních a výstupních dat. Jejich návrh zahrnuje permutaci s pevnou délkou, která funguje na vnitřním stavu reprezentovaném sekvencí bitových velikostí, sestávající z bitové rychlosti délky a kapacity délky , kombinované se vstupními daty rozřezanými na b - bitové bloky. Funkce houby zahrnuje operaci absorbování, která se má iterativně aplikovat na vnitřní stav po aplikaci operace bitové rychlosti na každý z b - bitových vstupních bitů. Všimněte si, že počet iterací v této operaci je dán parametrem počet kol . Operace squeeze je zase aplikace na celý vnitřní stav a následné vydání bitové rychlosti na výstup, tato operace bude prováděna, dokud nebude jako výstup poskytnut uživatelem zadaný počet bitů. Existuje také duplexní operace, což je série párů postupně aplikovaných operací absorbování a stlačování.

Parametry algoritmu

Lyra2 poskytuje možnost nakonfigurovat algoritmus nejvhodnějším způsobem pro potřeby uživatele. To je zajištěno různými parametry algoritmu, jako jsou: [3]

Algoritmové zařízení

Jako každá jiná kryptografická hašovací funkce, i Lyra2 bere sůl a heslo jako vstup a vytváří pseudonáhodnou sekvenci jako výstup . Interně je jeho paměť organizována jako dvourozměrné pole, jehož buňky jsou iterativně čteny a zapisovány, jednoduše nazývané paměťová matice [2] . Za zmínku také stojí, že počet návštěv buňky matice pro její přepočet určuje uživatel, což vám umožňuje upravit algoritmus v souladu s možnostmi počítačových systémů uživatele. Inicializace matice a návštěva využívá kombinaci provozních stavů absorbování, mačkání a duplexu hlavní funkce houby, což zajišťuje konzistenci celého procesu. Kromě toho mohou uživatelé definovat velikost matice a počet opakovaných návštěv jejích buněk po inicializaci, což umožňuje doladit využití zdrojů Lyra2. Lyra2 se skládá ze čtyř po sobě jdoucích fází: bootstrapping, nastavení, putování a balení.

Bootstrapping

V této fázi je inicializován vnitřní stav hlavní funkce houby. Vstup hlavní funkce houbičky obdrží heslo, sůl a další parametry. Parametry jsou obvykle reprezentovány délkou salt, heslem, časem a parametry nákladů na paměť, tedy těmi, které si nastavuje uživatel, lze přidat i další. Na tomto vstupu se provede operace absorbování a inicializuje se vnitřní stav funkce houby.

Založit

Ve fázi nastavení se inicializuje paměťová matice. Buňky matice mají délku bitů, tedy velikost bitrate hlavní funkce houby. Pro zlepšení výkonu při práci s potenciálně velkou paměťovou maticí používá instalační program duplexní operaci houby na sloupcích paměťové matice s menším počtem kol. Tento přístup urychluje operace s houbou a umožňuje tak pokrytí více paměťových pozic v daném intervalu, za daných časových omezení, než u celého cyklu f. Tato fáze končí, když byly navštíveny všechny sloupce paměťové matice.

Putování

Fáze putování spočívá v pseudonáhodném přepisování buněk paměťové matice pomocí duplexní operace na sloupcích stejným způsobem jako ve fázi Setup. Počet iterací v této fázi je omezen parametrem časové náklady.

zabalit

V této fázi je aplikována operace absorbování s maximálním počtem kol a poté operace stlačování a na výstupu je získána pseudonáhodná sekvence dané velikosti.

Notový zápis Symboly ⊕ označují bitovou výlučnost nebo (XOR), zatímco ⊞ označuje přidání strojových slov. Zřetězení mezi bajtovými poli a a b se píše || b. Pro bajtové pole x je zápis |x| a len(x) znamenají, v tomto pořadí, délka x v bitech a bajtech (tj. minimální počet bitů/bajtů potřebný k reprezentace x). Předpokládá se, že počítač má little-endian pořadí bajtů, v tomto popisu algoritmu vrací lsw(x) nejméně významný slovem x a rot^y(x) je w-bitový kruhový posun o x doleva, opakovaný ykrát. Parametr: H # Funkce houby s maximálním počtem kol p_max Parametr: p # Počet kol pro fázi nastavení a putování, p < p_max Parametr: Hp # Funkce Sponge se sníženým počtem kol str Parametr: w # Počet bitů použitých pro cyklický posun Vstup: pwd # Heslo Vstup: sůl # Sůl Vstup: T # Parametr, který definuje náklady v čase Vstup: R, C # Parametry, které určují cenu paměti Vstup: k # Délka výstupní sekvence v bitech Výstup: K # Hash závislý na heslu o délce k bitů Bootstrapping Parametry <- len(k) || len(pwd) || len(sůl) || T || R || C # Reprezentující parametry jako posloupnost bajtů H.absorb(pad(pwd || salt || params)) # Rozdělte sekvenci na podsekvence o délce b bitů Předchozí 0 <- 2; řádek1 <- 1; předchozí1<-0 Založit Pro (sloupec <- 0 až C-1) udělejte {M[0][C-1-col] <- Hp.squeeze(b)} konec pro # Inicializovat M[0] Pro (sloupec <- 0 až C-1) udělejte {M[1][C-1-sloupec] <- M[0][sloupec] ⊕ Hp.duplex(M[0][sloupec], b)} konec pro # Inicializovat M[1] Pro (sloupec <- 0 až C-1) udělejte {M[2][C-1-sloupec] <- M[1][sloupec] ⊕ Hp.duplex(M[1][sloupec], b)} konec pro # Inicializovat M[2] Pro (řádek0 <- 3 až R-1) proveďte # Inicializujte zbývající řádky Pro (sloupec <- 0 až C-1) proveďte # iteraci přes sloupce, zde se inicializuje M[řádek0] a přepíše se M[řádek1] rand <- Hp.duplex(M[řádek1][sloupec] ⊞ M[předchozí0][sloupec] ⊞ M[předchozí1][sloupec], b) M[řádek0][C-1-sloupec] <- M[předchozí0][sloupec] ⊕ rand M[řádek1][C-1-sloupec] <- M[řádek1][sloupec] ⊕ rot(rand) # rot(): rotace w bitů konec pro předchozí0 <- řádek0 ; prev1 <- row1 # Definuje řádky, které se mají použít v další iteraci getNext(row1) # Aktualizujte řádek1 pro další iteraci Konec pro Putování Pro (wCount <- 0 až R*T - 1) budou # 2*R*T řádky přepsány pseudonáhodně row0 <- lsw(rand) mod R ; row1 <- lsw(rot(rand)) mod R # Řádky jsou vybírány náhodně pro (sloupec <- 0 až C-1) do col0 <- lsw(rot^2(rand)) mod C ; col1 <- lsw(rot^3(rand)) mod C # Pseudo náhodný výběr sloupců rand <- Hp.duplex(M[řádek0][sloupec] ⊞ M[řádek1][sloupec] ⊞ M[předchozí0][sloupec] ⊞ M[předchozí1][sloupec], b) M[row0][col] <- M[row0][col] ⊕ rand # Přepsat pseudonáhodnou buňku M[row1][col] <- M[row1][col] ⊕ rot(rand) # rot(): rotace w bitů konec pro předchozí0 <- řádek0 ; prev1 <- row1 # Definuje řádky, které se mají použít v další iteraci Konec pro zabalit h.absorb(M[řádek0][0]) K <- H.squeeze(k) Návrat K

Výkon

Lyra2 umožňuje provádět výpočty za méně než 1 sekundu pomocí 400 MB paměti s hodnotami parametrů a [2] .

Testy byly provedeny na procesoru Intel Xeon E5-2430 (2,20 GHz, 12 jader, 64bitový systém) s 48 GB DRAM , na 64bitovém operačním systému Ubuntu 14.04 LTS , kód algoritmu byl zkompilován pomocí gcc 4.9. 2 [2] .

Poznámky

  1. ↑ Archiv kryptologie ePrint: Zpráva 2015/136 . eprint.iacr.org . Získáno 22. března 2016. Archivováno z originálu 9. března 2016.
  2. ↑ 1 2 3 4 Andrade, E.; Simplicio Jr, M.; Barreto, P.; Santos, P. Lyra2: efektivní hašování hesel s vysokou bezpečností proti kompromisům mezi časem a pamětí  // IEEE  Transactions on Computers : deník. - 2016. - 1. ledna ( roč. PP , č. 99 ). - S. 3096-3108 . — ISSN 0018-9340 . - doi : 10.1109/TC.2016.2516011 .
  3. ↑ 1 2 Simplicio Jr, Marcos A.; Almeida, Leonardo C.; Andrade, Everton R.; Santos, Paulo C.; Barreto, Paulo SLM Referenční příručka Lyra2 . PHC . Soutěž v hašování hesel. Získáno 6. prosince 2019. Archivováno z originálu dne 30. listopadu 2020.
  4. ↑ Gmane -- další PHC kandidáti na mechanické testy . article.gmane.org . Staženo: 22. března 2016.  (nedostupný odkaz)
  5. ↑ Gmane -- Recenze za den Lyra2 . article.gmane.org . Staženo: 22. března 2016.  (nedostupný odkaz)
  6. ↑ Gmane -- První recenze Lyra2 . article.gmane.org . Staženo: 22. března 2016.  (nedostupný odkaz)
  7. ↑ Výkon Gmane - Memory a útoky ASIC . article.gmane.org . Staženo: 22. března 2016.  (nedostupný odkaz)
  8. ↑ Gmane -- Rychlá analýza argonu . article.gmane.org . Staženo: 22. března 2016.  (nedostupný odkaz)

Odkazy

 Hashovací funkce
obecný účel
Kryptografický
Funkce generování klíčů
Kontrolní číslo ( srovnání )
Hashe