Lyra2

Lyra2
Skapad 2014
publiceras 2014
Sorts hash-funktion

Lyra2  är en kryptografisk hashfunktion som också kan användas som en nyckelhärledningsfunktion . Lyra2 skapades av Marcos Simplicio Jr., Leonardo C. Almeida, Everton R. Andrade, Paulo C. F. Santos och Paulo C. L. M. Barreto från Polytechnic School vid University of São Paulo [1] . Lyra2 är en av de mycket använda hashalgoritmerna tillsammans med PBKDF2 , bcrypt och scrypt . Men före tillkomsten av Lyra2 var scrypt den enda tillgängliga lösningen som tog hänsyn till kostnader för minne och behandlingstid. Lyra2 introducerade förbättringar såsom: separation av minne och bearbetningsparametrar, vilket ger användarna mer flexibilitet; använder en bassvampfunktion snarare än de två som används i scrypt; högre motståndskraft mot attacker med avvägningar för tidsminne ; och bättre prestanda som möjliggör högre minnesanvändning för liknande bearbetningstid [2] .

Lyra2 är fritt tillgänglig och har två tillägg: [3]

Attackmotstånd

De viktigaste fördelarna med algoritmen:

  1. Minnes- och tidskostnader kan separeras, vilket gör att du kan använda resurserna mer intelligent.
  2. Snabbt tack vare användningen av svampfunktionen med minskat antal omgångar i algoritmen.
  3. Tillhandahåller utdata av valfri längd, så kan fungera som en nyckelhärledningsfunktion .

Lyra2 kan konfigureras för att både skydda mot attackerande plattformar och optimera prestandan på användarens plattform:

Beräkningskostnaden för attacken ligger asymptotiskt mellan och när man använder minnesordningen på användarplattformen. Andra algoritmer är inte sämre än dessa indikatorer, men i praktiken har de ett lägre värde än Lyra2. [4] [5] [6] [7] [8]

Svampfunktion

Kryptografiska svampfunktioner är hashfunktioner som kan iterativt bearbeta godtyckliga längder av in- och utdata. Deras design involverar en permutation med fast längd som fungerar på ett internt tillstånd representerat av en sekvens av bitstorlekar, bestående av en bithastighet av längd och en kapacitet av längd , kombinerat med indata som skärs i b -bitars block. Svampfunktionen inkluderar en absorberingsoperation, som är att iterativt tillämpas på det interna tillståndet efter applicering av bithastighetsoperationen på var och en av b -bitars inmatningsbitar. Observera att antalet iterationer i denna operation ges av parametern antal rundor . Squeeze-operationen är i sin tur en applikation till hela det interna tillståndet och den efterföljande utfärdandet av en bithastighet till utgången, denna operation kommer att utföras tills det användarspecificerade antalet bitar tillhandahålls som en utgång. Det finns också en duplexoperation, som är en serie par av sekventiellt applicerade absorberings- och klämoperationer.

Algoritmparametrar

Lyra2 ger möjlighet att konfigurera algoritmen på det mest lämpliga sättet för användarens behov. Detta tillhandahålls av olika parametrar i algoritmen, såsom: [3]

Algoritmenhet

Liksom alla andra kryptografiska hashfunktioner tar Lyra2 ett salt och ett lösenord som indata, vilket producerar en pseudo-slumpmässig sekvens som utdata . Internt är dess minne organiserat som en tvådimensionell array vars celler iterativt läses och skrivs, helt enkelt kallad en minnesmatris [2] . Det är också värt att notera att antalet besök i matriscellen för dess omräkning bestäms av användaren, vilket gör att du kan justera algoritmen i enlighet med kapaciteten hos användarens datorsystem. Matrixinitiering och besök använder en kombination av absorberings-, squeeze- och duplexdriftstillstånden för svampens huvudfunktion, vilket säkerställer konsistensen i hela processen. Dessutom kan användare definiera storleken på matrisen och antalet återbesök till dess celler efter initialisering, vilket gör det möjligt att finjustera användningen av Lyra2-resurser. Lyra2 består av fyra på varandra följande faser: bootstrapping, setup, wandering och wrap-up.

Bootstrapping

I detta skede initieras det interna tillståndet för svampens huvudfunktion. Ingången av svampens huvudfunktion får ett lösenord, salt och andra parametrar. Parametrar representeras vanligtvis av längden på parametrarna för salt, lösenord, tid och minneskostnad, det vill säga de som ställs in av användaren, andra kan också läggas till. En absorberingsoperation utförs på denna ingång och det interna tillståndet för svampfunktionen initieras.

Uppstart

I installationsstadiet initieras minnesmatrisen. Matrisens celler har en längd av bitar, det vill säga storleken på bithastigheten för svampens huvudfunktion. För att förbättra prestandan när man arbetar med en potentiellt stor minnesmatris använder installationsprogrammet svampduplexoperationen på minnesmatrisens kolumner med färre omgångar. Detta tillvägagångssätt påskyndar svampoperationer och tillåter således fler minnespositioner att täckas i ett givet intervall, givna tidsbegränsningar, än med en hel cykel f. Denna fas avslutas när alla kolumner i minnesmatrisen har besökts.

Vandrande

Vandringsfasen består av pseudo-slumpmässig omskrivning av minnesmatriscellerna med hjälp av duplexoperationen på kolumner på samma sätt som i installationsfasen. Antalet iterationer i detta skede begränsas av tidskostnadsparametern.

sammanfatta

I detta skede appliceras absorberingsoperationen med det maximala antalet omgångar, och sedan squeeze-operationen, och en pseudoslumpmässig sekvens av en given storlek erhålls vid utgången.

Notation Symbolerna ⊕ anger bitvis exklusiv eller (XOR), medan ⊞ betecknar tillägg av maskinord. Sammankoppling mellan byte-arrayer a och b skrivs en || b. För en byte-array x, beteckningen |x| och len(x) betyder, respektive, längden av x i bitar och byte (dvs det minsta antalet bitar/byte som krävs för att representationer x). Det förutsätts att datorn har liten endian byteordning, i denna beskrivning av algoritmen, returnerar lsw(x) minst signifikant med ordet x, och rot^y(x) är en w-bit cirkulär förskjutning av x till vänster, upprepad y gånger. Param: H # Svampfunktion med maximalt antal omgångar p_max Param: p # Antal omgångar för faserna Setup och Wandering, p < p_max Param: Hp # Svampfunktion med reducerat antal omgångar sid Param: w # Antal bitar som används för cykliskt skift Inmatning: pwd # Lösenord Ingång: salt # Salt Indata: T # Parameter som definierar kostnaden över tid Ingång: R, C # Parametrar som bestämmer kostnaden för minne Ingång: k # Längden på utgångssekvensen i bitar Utdata: K # Lösenordsberoende hash med längd k bitar Bootstrapping Params <- len(k) || len(pwd) || len(salt) || T || R || C # Representerar parametrar som en sekvens av bytes H.absorb(pad(pwd || salt || params)) # Dela sekvensen i undersekvenser med längden b bitar Föregående0 <- 2; rad1 <- 1 ; föregående1<-0 Uppstart För (kol <- 0 till C-1) gör {M[0][C-1-kol] <- Hp.squeeze(b)} slut för # Initiera M[0] För (kol <- 0 till C-1) gör {M[1][C-1-kol] <- M[0][kol] ⊕ Hp.duplex(M[0][col], b)} slut för # Initiera M[1] För (kol <- 0 till C-1) gör {M[2][C-1-kol] <- M[1][kol] ⊕ Hp.duplex(M[1][kol], b)} slut för # Initiera M[2] För (rad0 <- 3 till R-1) gör # Initiera återstående rader För (kol <- 0 till C-1) gör # Iterera över kolumner, M[rad0] initieras här och M[rad1] skrivs över rand <- Hp.duplex(M[rad1][kol] ⊞ M[prev0][kol] ⊞ M[prev1][kol], b) M[rad0][C-1-kol] <- M[prev0][kol] ⊕ rand M[rad1][C-1-kol] <- M[rad1][kol] ⊕ rot(rand) # rot(): rotera w bitar slut för prev0 <- rad0; prev1 <- row1 # Definiera raderna som ska användas i nästa iteration getNext(row1) # Uppdatera rad1 för nästa iteration Slut för Vandrande För (wCount <- 0 till R*T - 1) kommer # 2*R*T rader att skrivas över pseudo-slumpmässigt rad0 <- lsw(rand) mod R ; rad1 <- lsw(rot(rand)) mod R # Rader väljs slumpmässigt för (kol <-0 till C-1) gör col0 <- lsw(rot^2(rand)) mod C ; col1 <- lsw(rot^3(rand)) mod C # Pseudoslumpmässigt urval av kolumner rand <- Hp.duplex(M[rad0][kol] ⊞ M[rad1][kol] ⊞ M[prev0][kol] ⊞ M[prev1][kol], b) M[rad0][kol] <- M[rad0][kol] ⊕ rand # Skriv över pseudo-slumpmässig cell M[rad1][kol] <- M[rad1][kol] ⊕ rot(rand) # rot(): rotera w bitar slut för prev0 <- rad0; prev1 <- row1 # Definiera raderna som ska användas i nästa iteration Slut för sammanfatta h.absorb(M[rad0][0]) K <- H.squeeze(k) Retur K

Prestanda

Lyra2 låter dig utföra beräkningar på mindre än 1 sekund med 400 MB minne med parametrarnas värden och [2] .

Testerna utfördes på en Intel Xeon E5-2430-processor (2,20 GHz, 12 kärnor, 64-bitars system) med 48 GB DRAM , på Ubuntu 14.04 LTS 64-bitars operativsystem , algoritmkoden kompilerades med gcc 4.9. 2 [2] .

Anteckningar

  1. ↑ Kryptologi ePrint-arkiv: Rapport 2015/136 . eprint.iacr.org . Hämtad 22 mars 2016. Arkiverad från originalet 9 mars 2016.
  2. ↑ 1 2 3 4 Andrade, E.; Simplicio Jr, M.; Barreto, P.; Santos, P. Lyra2: effektiv lösenordshasning med hög säkerhet mot tidsminnesavvägningar  // IEEE-  transaktioner på datorer : journal. - 2016. - 1 januari ( vol. PP , nr 99 ). - P. 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 Lyra2 referensguide . PHC . Lösenordshashing-tävlingen. Hämtad 6 december 2019. Arkiverad från originalet 30 november 2020.
  4. ↑ Gmane - En annan PHC kandidater mekaniska tester . article.gmane.org . Hämtad: 22 mars 2016.  (inte tillgänglig länk)
  5. ↑ Gmane - En recension per dag Lyra2 . article.gmane.org . Hämtad: 22 mars 2016.  (inte tillgänglig länk)
  6. ↑ Gmane - Lyra2 initial recension . article.gmane.org . Hämtad: 22 mars 2016.  (inte tillgänglig länk)
  7. ↑ Gmane-Minnesprestanda och ASIC-attacker . article.gmane.org . Hämtad: 22 mars 2016.  (inte tillgänglig länk)
  8. ↑ Gmane - Snabb analys av argon . article.gmane.org . Hämtad: 22 mars 2016.  (inte tillgänglig länk)

Länkar

 Hash-funktioner
generell mening
Kryptografisk
Nyckelgenereringsfunktioner
Kontrollnummer ( jämförelse )
Hashes