Lyra2

Uses your system voice; voice and rate in settings.

Snapshot

≈ 8 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Lyra2 is a password hashing scheme (PHS) that can also function as a key derivation function (KDF). It gained recognition during the Password Hashing Competition in July 2015, which was won by Argon2. It is also used in proof-of-work algorithms such as Lyra2REv2, adopted by Vertcoin and MonaCoin, among other cryptocurrencies. Lyra2 was designed by Marcos A. Simplicio Jr., Leonardo C. Almeida, Ewerton R. Andrade, Paulo C. F. dos Santos, and Paulo S. L. M. Barreto from Escola Politécnica da Universidade de São Paulo. It is based on Lyra, which had been created by the same team. Lyra2 includes: * The ability to configure the desired amount of memory, processing time, and parallelism for the algorithm. * High memory usage with processing time similar to scrypt. In addition, it: * Provides higher security against time-memory trade-offs. * Allows legitimate users to better benefit from the parallelism capabilities of their own platforms. * Increases the costs of creating dedicated hardware to attack the algorithm. * Balances resistance against side-channel threats and attacks using cheaper, slower storage devices. Lyra2 is released into the public domain.

Lyra2 is a password hashing scheme (PHS) that can also function as a key derivation function (KDF). It gained recognition during the Password Hashing Competition in July 2015, which was won by Argon2. It is also used in proof-of-work algorithms such as Lyra2REv2, adopted by Vertcoin and MonaCoin, among other cryptocurrencies. Lyra2 was designed by Marcos A. Simplicio Jr., Leonardo C. Almeida, Ewerton R. Andrade, Paulo C. F. dos Santos, and Paulo S. L. M. Barreto from Escola Politécnica da Universidade de São Paulo. It is based on Lyra, which had been created by the same team. Lyra2 includes: The ability to configure the desired amount of memory, processing time, and parallelism for the algorithm. High memory usage with processing time similar to scrypt. In addition, it: Provides higher security against time-memory trade-offs. Allows legitimate users to better benefit from the parallelism capabilities of their own platforms. Increases the costs of creating dedicated hardware to attack the algorithm. Balances resistance against side-channel threats and attacks using cheaper, slower storage devices. Lyra2 is released into the public domain.

Design

As any PHS, Lyra2 takes as input a salt and a password, creating a pseudorandom output that can then be used as key material for cryptographic algorithms or as an authentication string. Internally, the scheme's memory is organized as a matrix that is expected to remain in memory during the whole password hashing process. Since its cells are iteratively read and written, discarding a cell for saving memory leads to the need of recomputing it whenever it is accessed once again, until the point it was last modified. The construction and visitation of the matrix is done using a stateful combination of the absorbing, squeezing and duplexing operations of the underlying sponge (i.e., its internal state is never reset to zero), ensuring the sequential nature of the whole process. Also, the number of times the matrix's cells are revisited after initialization is defined by the user, allowing Lyra2's execution time to be fine-tuned according to the target platform's resources. params = outlen || len(password) || len(salt) || t_cost || m_cost || C || P || i # Initializes the sponge's state (after that, password can be overwritten) H_i.absorb( pad(password || salt || params) ) # Initializes visitation step, window and first rows that will feed gap = 1 stp = 1 wnd = 2 sqrt = 2 sync = 4 j = i prev0 = 2 rowP = 1 prevP = 0 ** Setup phase: Initializes a (m_cost x C) memory matrix, its cells having blen-byte cells # Initializes M_i[0], M_i[1] and M_i[2] for col = 0 to C-1 M_i[0][C-1-col] = H_i.squeeze_{rho}(blen) for col = 0 to C-1 M_i[1][C-1-col] = H_i.duplexing_{rho}( M_i[0][col], blen) for col = 0 to C-1 M_i[2][C-1-col] = H_i.duplexing_{rho}( M_i[1][col], blen) # Filling Loop: initializes remainder rows for row0 = 3 to ( (m_cost / P) - 1 ) # Columns Loop: M_i[row0] is initialized and M_j[row1] is updated for col = 0 to C-1 rand = H_i.duplexing_{rho}( M_j[rowP][col] [+] M_i[prev0][col] [+] M_j[prevP][col], blen) M_i[row0][C-1-col] = M_i[prev0][col] ^ rand M_j[rowP][col] = M_j[rowP][col] ^ ( rand >>> omega ) # Rows to be revisited in next loop prev0 = row0 prevP = rowP rowP = (rowP + stp) % wnd # Window fully revisited if (rowP = 0) # Doubles window and adjusts step wnd = 2 * wnd stp = sqrt + gap gap = -gap # Doubles sqrt every other iteration if (gap = -1) sqrt = 2 * sqrt # Synchronize point if (row0 = sync) sync = sync + (sqrt / 2) j = (j + 1) % P syncThreads() syncThreads() ** Wandering phase: Iteratively overwrites pseudorandom cells of the memory matrix wnd = m_cost / (2 * P) sync = sqrt off0 = 0 offP = wnd # Visitation Loop: (2 * m_cost * t_cost / P) rows revisited in pseudorandom fashion for wCount = 0 to ( ( (m_cost * t_cost) / P) - 1) # Picks pseudorandom rows and slices (j) row0 = off0 + (lsw(rand) % wnd) rowP = offP + (lsw( rand >>> omega ) % wnd) j = lsw( ( rand >>> omega ) >>> omega ) % P # Columns Loop: update M_i[row0] for col = 0 to C-1 # Picks pseudorandom column col0 = lsw( ( ( rand >>> omega ) >>> omega ) >>> omega ) % C rand = H_i.duplexing_{rho}( M_i[row0][col] [+] M_i[prev0][col0] [+] M_j[rowP][col], blen) M_i[row0][col] = M_i[row0][col] ^ rand # Next iteration revisits most recently updated rows prev0 = row0 # Synchronize point if (wCount = sync) sync = sync + sqrt swap(off0,offP) syncThreads() syncThreads() ** Wrap-up phase: output computation # Absorbs a final column with a full-round sponge H_i.absorb( M_i[row0][0] ) # Squeezes outlen bits with a full-round sponge output_i = H_i.squeeze(outlen) Provides outlen-long bitstring as output return output_0 ^ ... ^ output_{P-1}

Security analysis

Against Lyra2, the processing cost of attacks using 1/2^{n+2} of the amount of memory employed by a legitimate user is expected to be between O(2^{2nT}R^{3}) and O(2^{2nT}R^{n+2}) , the latter being a better estimate for n \gg 1 , instead of the O(R) achieved when the amount of memory is O(R) , where T is a user-defined parameter to define a processing time. This compares well to Scrypt, which displays a cost of O(R^{2}) when the memory usage is high O(1) , and with other solutions in the literature, for which the results are usually O(R^{T+1}) . Nonetheless, in practice these solutions usually involve a value of R (memory usage) lower than those attained with the Lyra2 for the same processing time.

Performance

and memory-hard PHC finalists with minimum parameters. The processing time obtained with an SSE single-core implementation of Lyra2 is illustrated in the hereby shown figure. This figure was extracted from, and is very similar to, third-party benchmarks performed during the PHC context. The results depicted correspond to the average execution time of Lyra2 configured with C=256 , \rho=1 , b=768 bits (i.e., the inner state has 256 bits), and different T and R settings, giving an overall idea of possible combinations of parameters and the corresponding usage of resources. As shown in this figure, Lyra2 is able to execute in: less than 1 s while using up to 400 MB (with R = 2^{14} and T=5 ) or up to 1 GB of memory (with R \approx 4.2\cdot10^{4} and T=1 ); or in less than 5 s with 1.6 GB (with R = 2^{16} and T=6 ). All tests were performed on an Intel Xeon E5-2430 (2.20 GHz with 12 Cores, 64 bits) equipped with 48 GB of DRAM, running Ubuntu 14.04 LTS 64 bits, and the source code was compiled using GCC 4.9.2.

Extensions

Lyra offers two main extensions: Lyra2-δ: Provides more control over the algorithm's bandwidth usage. Lyra2p: Takes advantage of parallelism capabilities on the user's platform.

References

External links

Lyra2's website Lyra2 source code repository on Github

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374573610 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

17 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.