Lyra2

Lyra2 is a password hashing scheme (PHS) that can also work as a key derivation function (KDF). It received a special recognition during the Password Hashing Competition in July 2015., which was won by Argon2. Besides being used for its original purposes, it is also in the core of proof-of-work algorithms such as Lyra2REv2, adopted by Vertcoin, 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 an improvement over Lyra, previously proposed by the same authors. Lyra2 preserves the security, efficiency and flexibility of its predecessor, including: (1) the ability to configure the desired amount of memory, processing time and parallelism to be used by the algorithm; and (2) the capacity of providing a high memory usage with a processing time similar to that obtained with scrypt. In addition, it brings the following improvements when compared to its predecessor:
This algorithm enables parameterization in terms of:
Strengths.
The main strengths of the algorithm are:
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.
Security analysis.
Against Lyra2, the processing cost of attacks using formula_8 of the amount of memory employed by a legitimate user is expected to be between formula_9 and formula_10, the latter being a better estimate for formula_11, instead of the formula_12 achieved when the amount of memory is formula_12, where formula_1 is a user-defined parameter to define a processing time.
This compares well to scrypt, which displays a cost of formula_15 when the memory usage is formula_16, and with other solutions in the literature, for which the results are usually formula_17.
Nonetheless, in practice these solutions usually involve a value of formula_2 (memory usage) lower than those attained with the Lyra2 for the same processing time.
Performance.
The processing time obtained with a SSE single-core implementation of Lyra2 are illustrated in the hereby shown figure. This figure was extracted from, and is very similar of third-party benchmarks performed during the PHC context.
The results depicted correspond to the average execution time of Lyra2 configured with formula_19, formula_20, formula_21 bits (i.e., the inner state has 256 bits), and different formula_1 and formula_2 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 formula_24 and formula_25) or up to 1 GB of memory (with formula_26 and formula_27); or in less than 5 s with 1.6 GB (with formula_28 and formula_29).
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.