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.10
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.11
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.
The algorithm additionally enables parameterization in terms of:12
Against Lyra2, the processing cost of attacks using 1 / 2 n + 2 {\displaystyle 1/2^{n+2}} of the amount of memory employed by a legitimate user is expected to be between O ( 2 2 n T R 3 ) {\displaystyle O(2^{2nT}R^{3})} and O ( 2 2 n T R n + 2 ) {\displaystyle O(2^{2nT}R^{n+2})} , the latter being a better estimate for n ≫ 1 {\displaystyle n\gg 1} , instead of the O ( R ) {\displaystyle O(R)} achieved when the amount of memory is O ( R ) {\displaystyle O(R)} , where T {\displaystyle T} is a user-defined parameter to define a processing time.
This compares well to Scrypt, which displays a cost of O ( R 2 ) {\displaystyle O(R^{2})} when the memory usage is high O ( 1 ) {\displaystyle O(1)} ,13 and with other solutions in the literature, for which the results are usually O ( R T + 1 ) {\displaystyle O(R^{T+1})} .14151617
Nonetheless, in practice these solutions usually involve a value of R {\displaystyle R} (memory usage) lower than those attained with the Lyra2 for the same processing time.1819202122
The processing time obtained with an SSE single-core implementation of Lyra2 is illustrated in the hereby shown figure. This figure was extracted from,23 and is very similar to, third-party benchmarks performed during the PHC context.2425262728
The results depicted correspond to the average execution time of Lyra2 configured with C = 256 {\displaystyle C=256} , ρ = 1 {\displaystyle \rho =1} , b = 768 {\displaystyle b=768} bits (i.e., the inner state has 256 bits), and different T {\displaystyle T} and R {\displaystyle 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 {\displaystyle R=2^{14}} and T = 5 {\displaystyle T=5} ) or up to 1 GB of memory (with R ≈ 4.2 ⋅ 10 4 {\displaystyle R\approx 4.2\cdot 10^{4}} and T = 1 {\displaystyle T=1} ); or in less than 5 s with 1.6 GB (with R = 2 16 {\displaystyle R=2^{16}} and T = 6 {\displaystyle 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.29
Lyra offers two main extensions:30
"Password Hashing Competition". password-hashing.net. Retrieved 2016-03-22. https://password-hashing.net/ ↩
"Lyra2REv2". eprint.iacr.org. Retrieved 2016-03-22. https://en.bitcoinwiki.org/wiki/Lyra2REv2 ↩
"Vertcoin". vertcoin.org. Retrieved 2019-10-08. http://vertcoin.org ↩
"MonaCoin". monacoin.org. Retrieved 2019-10-08. https://monacoin.org ↩
van Beirendonck, M.; Trudeau, L.; Giard, P.; Balatsoukas-Stimming, A. (2019-05-29). A Lyra2 FPGA Core for Lyra2REv2-Based Cryptocurrencies. IEEE International Symposium on Circuits and Systems (ISCAS). Sapporo, Japan: IEEE. pp. 1–5. arXiv:1807.05764. doi:10.1109/ISCAS.2019.8702498. /wiki/ArXiv_(identifier) ↩
"Cryptology ePrint Archive: Report 2015/136". eprint.iacr.org. Retrieved 2016-03-22. https://eprint.iacr.org/2015/136 ↩
Almeida, Leonardo C.; Andrade, Ewerton R.; Barreto, Paulo S. L. M.; Simplicio Jr, Marcos A. (2014-01-04). "Lyra: password-based key derivation with tunable memory and processing costs". Journal of Cryptographic Engineering. 4 (2): 75–89. CiteSeerX 10.1.1.642.8519. doi:10.1007/s13389-013-0063-5. ISSN 2190-8508. S2CID 5245769. /wiki/CiteSeerX_(identifier) ↩
"Cryptology ePrint Archive: Report 2014/030". eprint.iacr.org. Retrieved 2016-03-22. https://eprint.iacr.org/2014/030 ↩
Andrade, E.; Simplicio Jr, M.; Barreto, P.; Santos, P. (2016-01-01). "Lyra2: efficient password hashing with high security against time-memory trade-offs". IEEE Transactions on Computers. PP (99): 3096–3108. doi:10.1109/TC.2016.2516011. ISSN 0018-9340. S2CID 37232444. /wiki/Doi_(identifier) ↩
Chen, Lily (2009). "Recommendation for Key Derivation Using Pseudorandom Functions (Revised)" (PDF). Computer Security. NIST. doi:10.6028/NIST.SP.800-108. http://csrc.nist.gov/publications/nistpubs/800-108/sp800-108.pdf ↩
Simplicio Jr, Marcos A.; Almeida, Leonardo C.; Andrade, Ewerton R.; Santos, Paulo C.; Barreto, Paulo S. L. M. "The Lyra2 reference guide" (PDF). PHC. The Password Hashing Competition. https://password-hashing.net/submissions/specs/Lyra2-v3.pdf ↩
Percival, Colin. "Stronger Key Derivation via Sequential Memory-Hard Functions" (PDF). TARSNAP. The Technical BSD Conference. https://www.tarsnap.com/scrypt/scrypt.pdf ↩
"Cryptology ePrint Archive: Report 2013/525". eprint.iacr.org. Retrieved 2016-03-22. https://eprint.iacr.org/2013/525 ↩
Schmidt, Sascha. "Implementation of the Catena Password-Scrambling Framework" (PDF). Bauhaus-Universität Weimar. Faculty of Media. https://www.uni-weimar.de/fileadmin/user/fak/medien/professuren/Mediensicherheit/Research/Theses/sascha-schmidt-master-thesis-catena.pdf ↩
"P-H-C/phc-winner-argon2" (PDF). GitHub. Retrieved 2016-03-22. https://github.com/P-H-C/phc-winner-argon2/blob/master/argon2-specs.pdf ↩
"Gmane -- Another PHC candidates mechanical tests". article.gmane.org. Retrieved 2016-03-22. http://article.gmane.org/gmane.comp.security.phc/2237 ↩
"Gmane -- A review per day Lyra2". article.gmane.org. Retrieved 2016-03-22. http://article.gmane.org/gmane.comp.security.phc/1992 ↩
"Gmane -- Lyra2 initial review". article.gmane.org. Retrieved 2016-03-22. http://article.gmane.org/gmane.comp.security.phc/1596 ↩
"Gmane -- Memory performance and ASIC attacks". article.gmane.org. Retrieved 2016-03-22. http://article.gmane.org/gmane.comp.security.phc/1849 ↩
"Gmane -- Quick analysis of Argon". article.gmane.org. Retrieved 2016-03-22. http://article.gmane.org/gmane.comp.security.phc/1830 ↩