Lyra2

A diagram of the Lyra2 memory matrix.

Lyra2 is a memory-hard password hashing scheme that can also derive cryptographic keying material. It was designed by Marcos A. Simplicio Jr., Leonardo C. Almeida, Ewerton R. Andrade, Paulo C. F. dos Santos and Paulo S. L. M. Barreto at the University of São Paulo.

Lyra2 was a finalist in the 2013–2015 Password Hashing Competition and received special recognition. Argon2, not Lyra2, was selected as the competition's winner.

Purpose

Human-selected passwords usually contain less entropy than cryptographic keys. If a password database or encrypted file is obtained, an attacker can test guesses offline. A password hashing scheme raises the cost of each guess by requiring configurable computation and, for a memory-hard design, substantial memory.

Lyra2 belongs to this password-based branch of the broader Key derivation function family. It accepts a password, salt, desired output length and cost parameters. Its output can be stored as a password verifier or used as keying material, depending on the application. A salt separates records that use the same password; it is not normally secret.

Design

Lyra2 is built from a cryptographic sponge, a construction with an internal state that absorbs input and later squeezes out pseudorandom output. The algorithm stores intermediate values in a memory matrix and revisits them during processing. Discarding parts of that matrix to save memory forces an evaluator to recompute values, which is intended to make time–memory trade-offs costly.

The specification divides evaluation into three broad phases:

1. Bootstrapping and setup absorb the password, salt and parameters, then initialize the memory matrix.
2. Wandering revisits and modifies rows of the matrix according to values derived from the evolving sponge state. The time-cost parameter controls repeated work.
3. Wrap-up absorbs a final matrix value and squeezes the requested output from the sponge.

The main cost parameters are the number of wandering passes (T) and the dimensions of the memory matrix: rows (R) and columns (C). With a sponge bitrate of b, the matrix occupies b × R × C bits. The output length and the sponge's underlying permutation, bitrate, rotation and reduced-round settings are also part of the specification. This configurability lets an implementer raise processing time without necessarily increasing memory, or select a larger matrix for a platform with more memory.

The paper describes two named extensions. Lyra2-δ changes the proportion of matrix cells revisited during wandering to adjust memory-bandwidth use. Lyra2p runs multiple synchronized sponge instances over slices of a shared matrix so that a legitimate multicore platform can increase memory use or work without the same increase in latency. These are parameterized variants of the research design, not independent standards.

Security rationale

Lyra2's authors designed the changing memory-access pattern and repeated row updates to penalize attackers who retain less memory than the configured amount. A discarded row may have to be reconstructed from earlier state and then reconstructed again after later updates, so reducing peak memory introduces extra work. The authors also sought to balance resistance to side-channel observation with resistance to implementations using inexpensive, slower storage and to increase the cost of dedicated FPGA or ASIC implementations. These are design goals and analyses from the paper; they do not guarantee that every implementation or parameter set is secure.

The setup phase uses a predictable access pattern, while the wandering phase selects rows from the evolving internal state. The distinction reflects a trade-off: data-dependent access can increase resistance to some low-memory strategies but may reveal information through caches or other side channels. The paper's alternatives and variants let implementers choose different points in that trade-off, which means the exact version and configuration are part of any security claim.

Password hashing remains limited by password quality and operational choices. A low memory or time setting reduces the cost of attack, while an excessive setting can enable denial of service. Implementations also need unique salts, authenticated parameter storage, constant-time comparisons where appropriate, bounded input sizes and a migration plan for stronger settings.

Password Hashing Competition

The Password Hashing Competition invited public proposals for a modern password hashing standard. Lyra2 advanced to the final round and was one of four schemes—alongside Catena, Makwa and yescrypt—to receive special recognition. The panel selected Argon2 as the overall winner in July 2015.

Special recognition established Lyra2 as a notable research design, not a universal deployment recommendation. Current protocol or platform guidance may specify another function. For example, RFC 9106 provides an implementer-oriented specification and recommended profiles for Argon2id.

Use in proof of work

Modified constructions bearing the Lyra2 name have been included in chained proof-of-work algorithms used by some cryptocurrencies, including Lyra2RE and Lyra2REv2. Those mining algorithms combine multiple functions and may change Lyra2's parameters or role. Their use should not be treated as evidence that the original password hashing scheme is suited to every mining or password-storage application.

Implementation status

The authors released reference material and code with the competition submission. Applications should identify the exact version and parameters they implement. Copying the algorithm from secondary pseudocode, omitting validation or selecting obsolete settings can break interoperability and invalidate the intended cost assumptions.

External links

• Lyra2 research paper
• Password Hashing Competition submissions