Lyra2 Explained

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,^[1] which was won by Argon2. It is also used in proof-of-work algorithms such as Lyra2REv2,^[2] adopted by Vertcoin^[3] and MonaCoin,^[4] among other cryptocurrencies.^[5]

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.^[6] It is an improvement over Lyra,^{[7] [8]} which had been created by the same team. Lyra2 maintains the security, efficiency, and flexibility of its predecessor, including:

• 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 brings the following improvements compared to its predecessor:^[9]

• Provides higher security against time-memory trade-offs.
• Allows legitimate users to better benefit from the parallelism capabilities of their own platforms.
• Includes tweaks to increase 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 and offers two main extensions:^[10]

• **Lyra2-δ**: Provides better control over the algorithm's bandwidth usage.
• **Lyra2p**: Takes advantage of parallelism capabilities on the user's platform.

This algorithm enables parameterization in terms of:

• execution time (time cost

T )

• memory required (number of rows

R , and number of columns C )p )

• underlying permutation function (can be seen as the main cryptographic primitive)
• number of blocks used by the underlying permutation function (bitrate)
• number of rounds performed for the underlying permutation function (

\rho )

• number of bits to be used in rotations (

\omega )

• output length(

\kappa )

Strengths

The core strengths of the algorithm are as follows:^{[5] [10]}

• High resistance against processing-memory trade-offs: estimated processing costs of attacks with low memory usage involve a factor that grows exponentially with time cost due to recomputations.
• Memory and time costs can be decoupled, allowing their usage to be fine-tuned.
• Fast due to use of reduced-round sponge function in the algorithm's core.
• Can provide outputs of any desired length, behaving as a key derivation function (KDF).
• Design combines resistance to side-channel attacks (during the whole Setup phase) and to attacks involving cheap (hence, low-speed) memory devices, aiming to balance such conflicting requirements.
• It considers a wide range of configurations for protecting against attacking platforms while optimizing execution on legitimate platform, such as:
  • Support for parallelism for multi-core platforms, without giving much advantage to GPU-based attacks.
  • Capability of using different underlying sponge functions depending on the target platform (e.g., BLAKE2b for software implementations; Keccak for hardware implementations; BlaMka for additional resistance against hardware platforms; etc.)
  • Ability to raise the algorithm's memory bandwidth usage. (note: the original specification is expected to max out the bandwidth in current machines, but this feature may be useful for future hardware)

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.^[11]

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.^[5]

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.

Functions/symbols

|| : Concatenate two strings

: Bitwise XOR

: Wordwise add operation (i.e., ignoring carries between words)

: Modulus

: The target machine's word size (usually, 32 or 64)

: Number of bits to be used in rotations (recommended: a multiple of the machine's word size, W)

: Right rotation

: Number of rounds for reduced squeeze or duplexing operations

: Sponge's block size in bytes

: Sponge with block size blen (in bytes) and underlying permutation f

: Sponge's absorb operation on input

: Sponge's squeeze operation of len bytes

: Sponge's squeeze operation of len bytes using rho rounds of f

: Sponge's duplexing operation on input, producing len bytes

:Sponge's duplexing operation on input, using rho rounds of f, producing len bytes

: Pads a string to a multiple of blen bytes (padding rule: 10*1)

: The least significant word of input

: Length of a string, in bytes

: Synchronize parallel threads

: Swap the value of two inputs

: Number of columns on the memory matrix (usually, 64, 128, 256, 512 or 1024)

: Degree of parallelism (and)

Algorithm without parallelism

Notes and References

1. Web site: Password Hashing Competition. password-hashing.net. 2016-03-22.
2. Web site: Lyra2REv2. eprint.iacr.org. 2016-03-22.
3. Web site: Vertcoin. vertcoin.org. 2019-10-08.
4. Web site: MonaCoin. monacoin.org. 2019-10-08.
5. 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. 1–5. 10.1109/ISCAS.2019.8702498. 1807.05764.
6. Web site: Cryptology ePrint Archive: Report 2015/136. eprint.iacr.org. 2016-03-22.
7. 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. en. 4. 2. 75–89. 10.1007/s13389-013-0063-5. 2190-8508. 10.1.1.642.8519. 5245769 .
8. Web site: Cryptology ePrint Archive: Report 2014/030. eprint.iacr.org. 2016-03-22.
9. 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. 10.1109/TC.2016.2516011. 37232444 . 0018-9340.
10. Web site: The Lyra2 reference guide. Simplicio Jr. Marcos A.. Almeida. Leonardo C.. Andrade. Ewerton R.. Santos. Paulo C.. Barreto. Paulo S. L. M.. PHC. The Password Hashing Competition.
11. Recommendation for Key Derivation Using Pseudorandom Functions (Revised). Chen. Lily. Computer Security. NIST. 10.6028/NIST.SP.800-108. 2009. free.