Content deleted Content added
→Design: failed verification |
m Copy edits |
||
(33 intermediate revisions by 23 users not shown) | |||
Line 1:
{{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.<ref>{{Cite web|url=https://password-hashing.net/|title=Password Hashing Competition|website=password-hashing.net|access-date=2016-03-22}}</ref>, 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 <ref name="Lyra2REv2">{{Cite web|url=https://en.bitcoinwiki.org/wiki/Lyra2REv2|title=Lyra2REv2|website=eprint.iacr.org|access-date=2016-03-22}}</ref>, adopted by Vertcoin <ref name="vertcoin">{{Cite web|url=http://vertcoin.org|title=Vertcoin|website=vertcoin.org|access-date=2019-10-08}}</ref>, MonaCoin <ref name="MonaCoin">{{Cite web|url=https://monacoin.org|title=MonaCoin|website=monacoin.org|access-date=2019-10-08}}</ref>, among other cryptocurrencies<ref name="lyra2ToC">{{Cite conference|last=van Beirendonck|first=M.|last2=Trudeau|first2=L.|last3=Giard|first3=P.|last4=Balatsoukas-Stimming|first4=A.|date=2019-05-29|title=A Lyra2 FPGA Core for Lyra2REv2-Based Cryptocurrencies|conference=IEEE International Symposium on Circuits and Systems (ISCAS)|location=Sapporo, Japan|publisher=IEEE|pages=1–5|doi=10.1109/ISCAS.2019.8702498}}</ref>▼
{{Multiple issues|
{{advert|date=October 2017}}<!-- self-promotion by one of the authors of the algo: most of the article is written by a single-purpose account "Erandrade" -->
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 [[Polytechnic School of the University of São Paulo|Escola Politécnica da Universidade de São Paulo]].<ref name=":0">{{Cite web|url=https://eprint.iacr.org/2015/136|title=Cryptology ePrint Archive: Report 2015/136|website=eprint.iacr.org|access-date=2016-03-22}}</ref>. It is an improvement over Lyra,<ref name=":1">{{Cite journal|last=Almeida|first=Leonardo C.|last2=Andrade|first2=Ewerton R.|last3=Barreto|first3=Paulo S. L. M.|last4=Simplicio Jr|first4=Marcos A. |date=2014-01-04|title=Lyra: password-based key derivation with tunable memory and processing costs|journal=Journal of Cryptographic Engineering|language=en|volume=4|issue=2|pages=75–89|doi=10.1007/s13389-013-0063-5|issn=2190-8508|citeseerx=10.1.1.642.8519}}</ref><ref name=":8">{{Cite web|url=https://eprint.iacr.org/2014/030|title=Cryptology ePrint Archive: Report 2014/030|website=eprint.iacr.org|access-date=2016-03-22}}</ref> 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:<ref name="lyra2ToC2">{{Cite journal|last=Andrade|first=E.|last2=Simplicio Jr|first2=M. |last3=Barreto|first3=P.|last4=Santos|first4=P.|date=2016-01-01|title=Lyra2: efficient password hashing with high security against time-memory trade-offs|journal=IEEE Transactions on Computers|volume=PP|issue=99|pages=3096–3108|doi=10.1109/TC.2016.2516011|issn=0018-9340}}</ref>▼
{{primary sources|date=October 2017}}
* it allows a higher security level against attack venues involving [[Time/memory/data tradeoff attack|time-memory trade-offs]]▼
{{more citations needed|date=October 2017}}
* it allows legitimate users to benefit more effectively from the [[Parallel computing|parallelism]] capabilities of their own platforms▼
}}
* it includes tweaks for increasing the costs involved in the construction of [[Field-programmable gate array|dedicated hardware]] to attack the algorithm▼
▲'''Lyra2''' is a [[Password hashing|password hashing scheme]] (PHS) that can also work as a [[key derivation function]] (KDF). It received
* it balances resistance against [[side-channel attack|side-channel threats]] and attacks relying on cheaper (and, hence, slower) [[data storage device|storage devices]]▼
▲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 [[Polytechnic School of the University of São Paulo|Escola Politécnica da Universidade de São Paulo]].<ref name=":0">{{Cite web|url=https://eprint.iacr.org/2015/136|title=Cryptology ePrint Archive: Report 2015/136|website=eprint.iacr.org|access-date=2016-03-22}}</ref>
* Lyra2 is released under [[public domain]], and provides two main extensions:<ref name="lyra2RefGuide">{{Cite web|url=https://password-hashing.net/submissions/specs/Lyra2-v3.pdf|title=The Lyra2 reference guide|last=Simplicio Jr|first=Marcos A.|last2=Almeida|first2=Leonardo C.|last3=Andrade|first3=Ewerton R.|last4=Santos|first4=Paulo C.|last5=Barreto|first5=Paulo S. L. M.|website=PHC|publisher=The Password Hashing Competition}}</ref>▼
▲*
▲*
▲*
▲*
▲* Lyra2 is released under [[public domain]], and provides two main extensions:<ref name="lyra2RefGuide">{{Cite web|url=https://password-hashing.net/submissions/specs/Lyra2-v3.pdf|title=The Lyra2 reference guide|
* Lyra2-δ, gives the user better control over the algorithm's bandwidth usage
* Lyra2''p'', takes advantage of [[Parallel computing|parallelism]] capabilities on the legitimate user's platform
This algorithm enables parameterization in terms of:<ref name="lyra2RefGuide"/>▼
▲This algorithm enables parameterization in terms of:<ref name="lyra2RefGuide" />
* execution time (time cost <math>T</math>)
* memory required (number of rows <math>R</math>, and number of columns <math>C</math>)
Line 17 ⟶ 24:
* number of rounds performed for the underlying permutation function (<math>\rho</math>)
* number of bits to be used in rotations (<math>\omega</math>)
* output length
==Strengths ==
The core strengths of the algorithm are as follows:<ref name="lyra2ToC"/><ref name="lyra2RefGuide"/>
*High resistance against processing-memory
*Fast due to use of reduced-round sponge function in the algorithm's core.▼
▲*High resistance against processing-memory tradeoffs: estimated processing costs of [[Time/memory/data tradeoff attack|attacks with low memory usage]] involve a factor that grows exponentially with time cost due to recomputations
*Can provide outputs of any desired length, behaving as a [[
▲*Memory and time costs can be decoupled, allowing the resources' usage to be fine-tuned
*Design combines resistance to [[side-channel attack]]s (during the whole Setup phase) and to attacks involving cheap (hence, low-speed) [[Computer data storage|memory devices]], aiming to balance such conflicting requirements.▼
▲*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|Key Derivation Function]] (KDF)
**Support for parallelism
▲*Design combines resistance to [[side-channel attack]]s (during the whole Setup phase) and to attacks involving cheap (hence, low-speed) [[Computer data storage|memory devices]], aiming to balance such conflicting requirements
**Capability of using different underlying sponge functions depending on the target platform (e.g., [[BLAKE2
▲*Considers a wide range of configurations for protecting against attacking platforms while optimizing execution on legitimate platform, such as:
**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)▼
▲**Support for parallelism, for [[Multi-core processor|multicore platforms]], without giving much advantage to [[Graphics processing unit|GPU]]-based attacks
▲**Capability of using different underlying sponge functions depending on the target platform (e.g., [[BLAKE2|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 (cryptography)|salt]] and a
Internally, the scheme's memory is organized as a matrix that is expected to remain in memory during the whole password hashing process
The construction and visitation of the matrix is done using a stateful combination of the absorbing, squeezing and duplexing operations of the underlying [[Sponge function|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.
# *** Inputs ***▼
# password ▼
# salt ▼
# t_cost ▼
# m_cost ▼
# outlen ▼
# *** Algorithm without parallelism ***▼
# ** Bootstrapping phase: Initializes the sponge's state and local variables▼
{{pre|1=<nowiki>
# Byte representation of input parameters (others can be added)
params = outlen || len(password) || len(salt) || t_cost || m_cost || C
Line 91 ⟶ 95:
row1 = 1
prev1 = 0
</nowiki>
# Initializes M[0], M[1] and M[2]
Line 126 ⟶ 130:
sqrt = 2 * sqrt
# Visitation Loop: (2 * m_cost * t_cost) rows revisited in pseudorandom fashion
Line 148 ⟶ 152:
prev1 = row1
# Absorbs a final column with a full-round sponge
Line 158 ⟶ 162:
# Provides outlen-long bitstring as output
return output
}}
<pre>
for each i in [0
# Byte representation of input parameters (others can be added)
Line 182 ⟶ 187:
prevP = 0
# Initializes M_i[0], M_i[1] and M_i[2]
Line 224 ⟶ 229:
syncThreads()
wnd = m_cost / (2 * P)
Line 257 ⟶ 262:
syncThreads()
# Absorbs a final column with a full-round sponge
Line 267 ⟶ 272:
# Provides outlen-long bitstring as output
return output_0 ^ ... ^ output_{P-1}
</pre>
==Security analysis==
Against Lyra2, the processing cost of attacks using <math>1/2^{n+2} </math> of the amount of memory employed by a legitimate user is expected to be between <math>O(2^{2nT}R^{3})</math> and <math>O(2^{2nT}R^{n+2})</math>, the latter being a better estimate for <math>n \gg 1</math>, instead of the <math>O(R)</math> achieved when the amount of memory is <math>O(R)</math>, where <math>T</math> is a user-defined parameter to define a processing time.
This compares well to [[
Nonetheless, in practice these solutions usually involve a value of <math>R</math> (memory usage) lower than those attained with the Lyra2 for the same processing time.<ref name=":3">{{Cite web|url=http://article.gmane.org/gmane.comp.security.phc/2237|title=Gmane -- Another PHC candidates
==Performance==
[[File:Lyra2-Bench.pdf|thumb|1050x1050px|center|Performance of SSE-enabled Lyra2, for C = 256, ρ = 1, p = 1, and different T and R settings, compared with SSE-enabled
The processing time obtained with a SSE single-core implementation of Lyra2 are illustrated in the hereby shown figure. This figure was extracted from,<ref name="
The results depicted correspond to the average execution time of Lyra2 configured with <math>C=256</math>, <math>\rho=1</math>, <math>b=768</math> bits (i.e., the inner state has 256 bits), and different <math>T</math> and <math>R</math> settings, giving an overall idea of possible combinations of parameters and the corresponding usage of resources.
Line 285 ⟶ 290:
As shown in this figure, Lyra2 is able to execute in: less than 1 s while using up to 400 MB (with <math>R = 2^{14}</math> and <math>T=5</math>) or up to 1 GB of memory (with <math>R \approx 4.2\cdot10^{4}</math> and <math>T=1</math>); or in less than 5 s with 1.6 GB (with <math>R = 2^{16}</math> and <math>T=6</math>).
All tests were performed on an [[List of Intel Xeon microprocessors|Intel Xeon E5-2430]] (2.20 GHz with 12 Cores, 64 bits) equipped with 48 GB of [[Dynamic random-access memory|DRAM]], running [[Ubuntu (operating system)|Ubuntu]] 14.04 LTS 64 bits, and the source code was compiled using [[GNU Compiler Collection|gcc]] 4.9.2.<ref name="
==References==
|