Lyra2

Short description: Key derivative function

Lyra2 is a password hashing scheme (PHS) that can also work as a key derivation function (KDF). It received a special recognition during the Password Hashing Competition in July 2015,[1] which was won by Argon2. Besides being used for its original purposes, it is also in the core of proof-of-work algorithms such as Lyra2REv2,[2] adopted by Vertcoin,[3] 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] 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 the following improvements when compared to its predecessor:[9]

* 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 hence, slower storage devices
* Lyra2 is released under public domain, and provides two main extensions:[10]
* Lyra2-δ, gives the user better control over the algorithm's bandwidth usage
* Lyra2p, takes advantage of parallelism capabilities on the legitimate user's platform

This algorithm enables parameterization in terms of:[10]

* 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 (κ)

## Contents

* 1 Strengths
* 2 Design
* 2.1 Functions/symbols
* 2.2 Inputs
* 2.3 Algorithm without parallelism
* 2.4 Algorithm with parallelism
* 3 Security analysis
* 4 Performance
* 5 References
* 6 External links

## Strengths

The main strengths of the algorithm are:[5][10]

* 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 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
* 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 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][failed verification][citation needed]

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
W				The target machine's word size (usually, 32 or 64)
omega				Number of bits to be used in rotations (recommended: a multiple of the machine's word size, W)
>>>				Right rotation
rho				Number of rounds for reduced squeeze or duplexing operations
blen				Sponge's block size in bytes
H or H_i			Sponge with block size blen (in bytes) and underlying permutation f
H.absorb(input)			Sponge's absorb operation on input
H.squeeze(len)			Sponge's squeeze operation of len bytes
H.squeeze_{rho}(len)		Sponge's squeeze operation of len bytes using rho rounds of f
H.duplexing(input,len)		Sponge's duplexing operation on input, producing len bytes
H.duplexing_{rho}(input,len)	Sponge's duplexing operation on input, using rho rounds of f, producing len bytes
pad(string)			Pads a string to a multiple of blen bytes (padding rule: 10*1)
lsw(input)			The least significant word of input
len(string)			Length of a string, in bytes
syncThreads()			Synchronize parallel threads
swap(input1,input2)		Swap the value of two inputs
C				Number of columns on the memory matrix (usually, 64, 128, 256, 512 or 1024)
P				Degree of parallelism (P >= 1 and (m_cost/2) % P = 0)

### Inputs

* password
* salt
* t_cost
* m_cost
* outlen

### Algorithm without parallelism

** Bootstrapping phase: Initializes the sponge's state and local variables
# Byte representation of input parameters (others can be added)
params =  outlen || len(password) || len(salt) || t_cost || m_cost || C

# Initializes the sponge's state (after that, password can be overwritten)
H.absorb( pad(password || salt || params) )

# Initializes visitation step, window and first rows that will feed
gap = 1
stp = 1
wnd = 2
sqrt = 2

prev0 = 2
row1 = 1
prev1 = 0

** Setup phase: Initializes a (m_cost x C) memory matrix, its cells having blen-byte cells

# Initializes M[0], M[1] and M[2]
for col = 0 to C-1
M[0][C-1-col] = H.squeeze_{rho}(blen)
for col = 0 to C-1
M[1][C-1-col] = H.duplexing_{rho}( M[0][col], blen)
for col = 0 to C-1
M[2][C-1-col] = H.duplexing_{rho}( M[1][col], blen)

# Filling Loop: initializes remainder rows
for row0 = 3 to m_cost-1
# Columns Loop: M[row0] is initialized and M[row1] is updated
for col = 0 to C-1
rand = H.duplexing_{rho}( M[row1][col] [+] M[prev0][col] [+] M[prev1][col], blen)
M[row0][C-1-col] = M[prev0][col] ^ rand
M[row1][col] = M[row1][col] ^ ( rand >>> omega )

# Rows to be revisited in next loop
prev0 = row0
prev1 = row1
row1 = (row1 + stp) % wnd

# Window fully revisited
if (row1 = 0)
# Doubles window and adjusts step
wnd = 2 * wnd
stp = sqrt + gap
gap = -gap

# Doubles sqrt every other iteration
if (gap = -1)
sqrt = 2 * sqrt

** Wandering phase: Iteratively overwrites pseudorandom cells of the memory matrix

# Visitation Loop: (2 * m_cost * t_cost) rows revisited in pseudorandom fashion
for wCount = 0 to ( (m_cost * t_cost) - 1)
# Picks pseudorandom rows
row0 = lsw(rand) % m_cost
row1 = lsw( rand >>> omega ) % m_cost

# Columns Loop: updates both M[row0] and M[row1]
for col = 0 to C-1
# Picks pseudorandom columns
col0 = lsw( ( rand >>> omega ) >>> omega ) % C
col1 = lsw( ( ( rand >>> omega ) >>> omega ) >>> omega ) % C

rand = H.duplexing_{rho}( M[row0][col] [+] M[row1][col] [+] M[prev0][col0] [+] M[prev1][col1], blen)
M[row0][col] = M[row0][col] ^ rand
M[row1][col] = M[row1][col] ^ ( rand >>> omega )

# Next iteration revisits most recently updated rows
prev0 = row0
prev1 = row1

** Wrap-up phase: output computation

# Absorbs a final column with a full-round sponge
H.absorb( M[row0][0] )

# Squeezes outlen bits with a full-round sponge
output = H.squeeze(outlen)

# Provides outlen-long bitstring as output
return output

### Algorithm with parallelism

for each i in [0..P]
** Bootstrapping phase: Initializes the sponge's state and local variables

# Byte representation of input parameters (others can be added)
params =  outlen || len(password) || len(salt) || t_cost || m_cost || C || P || i

# Initializes the sponge's state (after that, password can be overwritten)
H_i.absorb( pad(password || salt || params) )

# Initializes visitation step, window and first rows that will feed
gap = 1
stp = 1
wnd = 2
sqrt = 2
sync = 4
j = i

prev0 = 2
rowP = 1
prevP = 0

** Setup phase: Initializes a (m_cost x C) memory matrix, its cells having blen-byte cells

# Initializes M_i[0], M_i[1] and M_i[2]
for col = 0 to C-1
M_i[0][C-1-col] = H_i.squeeze_{rho}(blen)
for col = 0 to C-1
M_i[1][C-1-col] = H_i.duplexing_{rho}( M_i[0][col], blen)
for col = 0 to C-1
M_i[2][C-1-col] = H_i.duplexing_{rho}( M_i[1][col], blen)

# Filling Loop: initializes remainder rows
for row0 = 3 to ( (m_cost / P) - 1 )
# Columns Loop: M_i[row0] is initialized and M_j[row1] is updated
for col = 0 to C-1
rand = H_i.duplexing_{rho}( M_j[rowP][col] [+] M_i[prev0][col] [+] M_j[prevP][col], blen)
M_i[row0][C-1-col] = M_i[prev0][col] ^ rand
M_j[rowP][col] = M_j[rowP][col] ^ ( rand >>> omega )

# Rows to be revisited in next loop
prev0 = row0
prevP = rowP
rowP = (rowP + stp) % wnd

# Window fully revisited
if (rowP = 0)
# Doubles window and adjusts step
wnd = 2 * wnd
stp = sqrt + gap
gap = -gap

# Doubles sqrt every other iteration
if (gap = -1)
sqrt = 2 * sqrt

# Synchronize point
if (row0 = sync)
sync = sync + (sqrt / 2)
j = (j + 1) % P
syncThreads()

syncThreads()

** Wandering phase: Iteratively overwrites pseudorandom cells of the memory matrix

wnd = m_cost / (2 * P)
sync = sqrt
off0 = 0
offP = wnd

# Visitation Loop: (2 * m_cost * t_cost / P) rows revisited in pseudorandom fashion
for wCount = 0 to ( ( (m_cost * t_cost) / P) - 1)
# Picks pseudorandom rows and slices (j)
row0 = off0 + (lsw(rand) % wnd)
rowP = offP + (lsw( rand >>> omega ) % wnd)
j = lsw( ( rand >>> omega ) >>> omega ) % P

# Columns Loop: update M_i[row0]
for col = 0 to C-1
# Picks pseudorandom column
col0 = lsw( ( ( rand >>> omega ) >>> omega ) >>> omega ) % C

rand = H_i.duplexing_{rho}( M_i[row0][col] [+] M_i[prev0][col0] [+] M_j[rowP][col], blen)
M_i[row0][col] = M_i[row0][col] ^ rand

# Next iteration revisits most recently updated rows
prev0 = row0

# Synchronize point
if (wCount = sync)
sync = sync + sqrt
swap(off0,offP)
syncThreads()

syncThreads()

** Wrap-up phase: output computation

# Absorbs a final column with a full-round sponge
H_i.absorb( M_i[row0][0] )

# Squeezes outlen bits with a full-round sponge
output_i = H_i.squeeze(outlen)

# Provides outlen-long bitstring as output
return output_0 ^ ... ^ output_{P-1}

## Security analysis

Against Lyra2, the processing cost of attacks using 1/2n+2 of the amount of memory employed by a legitimate user is expected to be between O(22nTR3) and O(22nTRn+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(R2) when the memory usage is O(1),[12] and with other solutions in the literature, for which the results are usually O(RT+1).[7][13][14][15]

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.[16][17][18][19][20]

## Performance

Performance of SSE-enabled Lyra2, for C = 256, ρ = 1, p = 1, and different T and R settings, compared with SSE-enabled Scrypt and memory-hard PHC finalists with minimum parameters.

The processing time obtained with a SSE single-core implementation of Lyra2 are illustrated in the hereby shown figure. This figure was extracted from,[9] and is very similar of third-party benchmarks performed during the PHC context.[16][17][18][19][20]

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=214 and T=5) or up to 1 GB of memory (with R≈4.2⋅104 and T=1); or in less than 5 s with 1.6 GB (with R=216 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.[9]

## References

1. ↑ "Password Hashing Competition". https://password-hashing.net/.
2. ↑ "Lyra2REv2". https://en.bitcoinwiki.org/wiki/Lyra2REv2.
3. ↑ "Vertcoin". http://vertcoin.org.
4. ↑ "MonaCoin". https://monacoin.org.
5. ↑ 5.0 5.1 5.2 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. doi:10.1109/ISCAS.2019.8702498.
6. ↑ "Cryptology ePrint Archive: Report 2015/136". https://eprint.iacr.org/2015/136.
7. ↑ 7.0 7.1 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" (in en). Journal of Cryptographic Engineering 4 (2): 75–89. doi:10.1007/s13389-013-0063-5. ISSN 2190-8508.
8. ↑ "Cryptology ePrint Archive: Report 2014/030". https://eprint.iacr.org/2014/030.
9. ↑ 9.0 9.1 9.2 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.
10. ↑ 10.0 10.1 10.2 Simplicio Jr, Marcos A.; Almeida, Leonardo C.; Andrade, Ewerton R.; Santos, Paulo C.; Barreto, Paulo S. L. M.. "The Lyra2 reference guide". The Password Hashing Competition. https://password-hashing.net/submissions/specs/Lyra2-v3.pdf.
11. ↑ Chen, Lily (2009). Recommendation for Key Derivation Using Pseudorandom Functions (Revised). NIST. doi:10.6028/NIST.SP.800-108. http://csrc.nist.gov/publications/nistpubs/800-108/sp800-108.pdf.
12. ↑ Percival, Colin. "Stronger Key Derivation via Sequential Memory-Hard Functions". The Technical BSD Conference. https://www.tarsnap.com/scrypt/scrypt.pdf.
13. ↑ "Cryptology ePrint Archive: Report 2013/525". https://eprint.iacr.org/2013/525.
14. ↑ Schmidt, Sascha. "Implementation of the Catena Password-Scrambling Framework". Faculty of Media. https://www.uni-weimar.de/fileadmin/user/fak/medien/professuren/Mediensicherheit/Research/Theses/sascha-schmidt-master-thesis-catena.pdf.
15. ↑ "P-H-C/phc-winner-argon2". https://github.com/P-H-C/phc-winner-argon2/blob/master/argon2-specs.pdf.
16. ↑ 16.0 16.1 "Gmane -- Another PHC candidates mechanical tests". http://article.gmane.org/gmane.comp.security.phc/2237.
17. ↑ 17.0 17.1 "Gmane -- A review per day Lyra2". http://article.gmane.org/gmane.comp.security.phc/1992.
18. ↑ 18.0 18.1 "Gmane -- Lyra2 initial review". http://article.gmane.org/gmane.comp.security.phc/1596.
19. ↑ 19.0 19.1 "Gmane -- Memory performance and ASIC attacks". http://article.gmane.org/gmane.comp.security.phc/1849.
20. ↑ 20.0 20.1 "Gmane -- Quick analysis of Argon". http://article.gmane.org/gmane.comp.security.phc/1830.

## External links

* Lyra2's website
* Lyra2 source code repository on Github

* v
* t
* e

Cryptographic hash functions & message authentication codes

* List
* Comparison
* Known attacks

Common functions|

* MD5
* SHA-1
* SHA-2
* SHA-3
* BLAKE2

SHA-3 finalists|

* BLAKE
* Grøstl
* JH
* Skein
* Keccak (winner)

Other functions|

* CubeHash
* ECOH
* FSB
* GOST
* HAS-160
* HAVAL
* Kupyna
* LM hash
* MD2
* MD4
* MD6
* MDC-2
* N-Hash
* RIPEMD
* RadioGatún
* SM3
* SWIFFT
* Snefru
* Streebog
* Tiger
* VSH
* Whirlpool

Key derivation functions|

* Argon2
* Balloon
* bcrypt
* crypt
* Lyra2
* PBKDF2
* scrypt

MAC functions|

* DAA
* CBC-MAC
* GMAC
* HMAC
* NMAC
* OMAC/CMAC
* PMAC
* VMAC
* UMAC
* Poly1305
* SipHash

Authenticated
encryption modes|

* CCM
* CWC
* EAX
* GCM
* IAPM
* OCB

Attacks|

* Collision attack
* Preimage attack
* Birthday attack
* Brute-force attack
* Rainbow table
* Side-channel attack
* Length extension attack

Design|

* Avalanche effect
* Hash collision
* Merkle–Damgård construction
* Sponge function
* HAIFA construction

Standardization|

* CRYPTREC
* NESSIE
* NIST hash function competition

Utilization|

* Hash-based cryptography
* Key stretching
* Merkle tree
* Message authentication
* Proof of work
* Salt
* Pepper

* v
* t
* e

Cryptography

* History of cryptography
* Cryptanalysis
* Outline of cryptography

* Symmetric-key algorithm
* Block cipher
* Stream cipher
* Public-key cryptography
* Cryptographic hash function
* Message authentication code
* Random numbers
* Steganography

* Category

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Lyra2. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Lyra2&oldid=274423"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template