Lyra2 is a Key Derivation Function (KDF), also called Password Hashing Schemes (PHS), that received a special recognition during the Password Hashing Competition in July 2015. 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 from Escola Politécnica da Universidade de São Paulo.
Lyra2 is an improvement of 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 important improvements when compared to its predecessor:
it allows a higher security level against attack venues involving time-memory trade-offs
it allows legitimate users to benefit more effectively from the parallelism capabilities of their own platforms
it includes tweaks for increasing the costs involved in the construction of dedicated hardware to attack the algorithm
it balances resistance against side-channel threats and attacks relying on cheaper (and, hence, slower) storage devices
Lyra2 is released under a public domain, and provides two main extensions:
Lyra2-δ (that give for the users a better control over the algorithm's bandwidth usage)
Lyra2p (that take advantage of parallelism capabilities potentially available on the legitimate 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
)
degree of parallelism (number of threads
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 (
ρ
)
number of bits to be used in rotations (
ω
)
output length (
κ
)
High resistance against processing-memory tradeoffs: 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 the resources' 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, balancing these conflicting requirements
Considers a wider range of configurations for protecting against attacking platforms while optimizing execution on legitimate platform, such as:
Support for parallelism, for multicore 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 should already max out the bandwidth in current machines, but feature may be useful for future hardware)
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.
Against Lyra2, the processing cost of attacks using
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
)
and
O
(
2
2
n
T
R
n
+
2
)
, the latter being a better estimate for
n
≫
1
, instead of the
O
(
R
)
achieved when the amount of memory is
O
(
R
)
, where
T
is a user-defined parameter to define a processing time.
This compares well to scrypt, which displays a cost of
O
(
R
2
)
when the memory usage is
O
(
1
)
, and with other solutions in the literature, for which the best result is
O
(
R
T
+
1
)
.
Nonetheless, in practice these solutions usually involve a value of
R
(memory usage) lower than those attained with the Lyra2 for the same processing time.
The processing time obtained with a SSE single-core implementation of Lyra2 are illustrated in the figure besides.
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
C
=
256
,
ρ
=
1
,
b
=
768
bits (i.e., the inner state has 256 bits), and different
T
and
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
and
T
=
5
) or up to 1 GB of memory (with
R
≈
4.2
⋅
10
4
and
T
=
1
); or in less than 5 s with 1.6 GB (with
R
=
2
16
and
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.
