Paper 2014/030

Lyra: Password-Based Key Derivation with Tunable Memory and Processing Costs

Leonardo C. Almeida, Ewerton R. Andrade, Paulo S. L. M. Barreto, and Marcos A. Simplicio Jr.

Abstract

We present Lyra, a password-based key derivation scheme based on cryptographic sponges. Lyra was designed to be strictly sequential (i.e., not easily parallelizable), providing strong security even against attackers that use multiple processing cores (e.g., custom hardware or a powerful GPU). At the same time, it is very simple to implement in software and allows legitimate users to fine-tune its memory and processing costs according to the desired level of security against brute force password guessing. We compare Lyra with similar-purpose state-of-the-art solutions, showing how our proposal provides a higher security level and overcomes limitations of existing schemes. Specfically, we show that if we fix Lyra's total processing time t in a legitimate platform, the cost of a memory-free attack against the algorithm is exponential, while the best known result in the literature (namely, against the scrypt algorithm) is quadratic. In addition, for an identical same processing time, Lyra allows for a higher memory usage than its counterparts, further increasing the cost of brute force attacks.

Note: 01-Apr-2014 Modification of the Lyra algorithm (Alg. 2): truncation to one word on lines 16 and 17 Details added: little endianness; initialization of underlying sponge's state; block length used in benchmarks. 07-Apr-2014 Addition of "basil" for avoiding trivial collisions; Algorithm: Inversion on the order in which the salt and password are fed into the sponge (easier to accommodate basil and follows the general rule ``feed data into hash functions in order of decreasing entropy'' as originally proposed in MD5crypt).

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. MINOR revision.Journal of Cryptographic Engineering
DOI
10.1007/s13389-013-0063-5
Keywords
Password-based key derivationmemory usagecryptographic sponges
Contact author(s)
lalmeida @ larc usp br
History
2014-04-07: last of 4 revisions
2014-01-12: received
See all versions
Short URL
https://ia.cr/2014/030
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/030,
      author = {Leonardo C.  Almeida and Ewerton R.  Andrade and Paulo S.  L.  M.  Barreto and Marcos A.  Simplicio Jr.},
      title = {Lyra: Password-Based Key Derivation with Tunable Memory and Processing Costs},
      howpublished = {Cryptology ePrint Archive, Paper 2014/030},
      year = {2014},
      doi = {10.1007/s13389-013-0063-5},
      note = {\url{https://eprint.iacr.org/2014/030}},
      url = {https://eprint.iacr.org/2014/030}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.