scrypt
scrypt is a password -based key derivation function ( password-based key derivation function ), which was published in 2010 by Colin Percival. The development of scrypt was motivated by the vulnerability of previous key derivation functions such as bcrypt and PBKDF2 against brute force and dictionary attacks with specialized hardware.
background
Passwords themselves are not suitable as cryptographic keys. The simple hash value of the password prevents the password from being recalculated, but does not protect against dictionary attacks , the brute force method and rainbow tables . Password-based key derivation functions also incorporate a random number, the salt , into the key calculation and specifically increase the cost of calculating a key in order to make it difficult to “try out” many options.
In contrast to other key derivation functions, Scrypt does not only measure the computational effort according to the pure computing time. Instead, scrypt also specifically increases the cost of hardware that is suitable for breaking a password in a certain amount of time ( dollar seconds ). This paradigm shift is due to the fact that the development of specialized hardware such as FPGAs and graphics processors can dramatically shorten the real computing time for breaking a password ( custom hardware attack ). The slowing down of the calculation due to the number of hash operations (iterations) intended in the key derivation functions bcrypt and PBKDF2 can be compensated for by parallelizing the attack using special hardware. Such parallel programming cannot be prevented in principle. Scrypt takes advantage of the fact that main memory is relatively expensive, requests a vector with (by default) 16 MB and thus increases the cost of using specialized hardware. The HEKS key derivation function was based on this idea, but is supplemented by sequencing in scrypt .
history
Scrypt was developed by Colin Percival for the company Tarsnap and presented in May 2009 at the BSD Can Conference. In 2012 the IETF published a draft of scrypt as an internet draft. In August 2015 Colin Percival released version scrypt-1.2.0.
Scrypt did not take part in the Password Hashing Competition , a selection process for a new password hashing process, although Colin Percival was involved as an expert. With Yescrypt by Alexander Peslyak, however, an algorithm took part which, with the extension "YESCRYPT-WORM", can also produce original scrypt hash values.
description
Scrypt is considered sequential memory-hard (sequential memory-intensive). In the ROMix function, a vector is filled with values from the Salsa20 / 8 function, a version of the Salsa20 stream cipher that has been shortened to eight rounds . This is then accessed in a pseudo-random manner, thus ensuring that the vector must be kept permanently in the memory - or that the computing time is extremely increased. Scrypt allows the parameterization of the CPU costs (computing time) and the storage costs and also has a parallelization parameter.
Parameters:
N: CPU and memory
factor r: memory
factor p: parallel
factor Colin Percival recommended (N = 16384, r = 8, p = 1) for normal requirements and (N = 1048576, r = 8, p = 1 ) for high demands. The parameters r and p were intended to be adapted to technical developments over time.
Use in cryptocurrencies
In addition to password-based key derivation, Scrypt is also used for so-called mining in crypto currencies such as Litecoin and Dogecoin . The contribution of computing power for these currencies and thus the participation in transaction fees should originally be distributed as evenly as possible among the participants. However, through the use of special hardware (ASICs), for example in the crypto currency Bitcoin , computing power has become dependent on financial strength and thus centralization. Currencies like Litecoin wanted to prevent this and took advantage of the fact that Scrypt is difficult to implement in ASICs due to the high memory requirements . However, Litecoin uses Scrypt with lower parameters (N = 1024, r = 1, p = 1) than recommended by Colin Percival and therefore with significantly lower memory requirements. In the meantime, ASICs are also on the market for the Scrypt version used in these cryptocurrencies.
The cryptocurrency Vertcoin then introduced Scrypt with a variable N-Factor ( Adaptive N-Factor ), a parameter that adapts the memory requirements to the development and is intended to prevent implementation in ASICs. In the meantime, Vertcoin has announced that it will replace Scrypt with the Lyra2 function , which, like Scrypt, has parameters for memory requirements and computing power. In contrast to Scrypt, these parameters are not linked to each other in Lyra2. The Lyra2 password hashing function is a candidate in the Password Hashing Competition .
Many smaller cryptocurrencies such as YaCoin use Scrypt-Jane , a flexible implementation of Scrypt (other hash functions such as Keccak and ChaCha20 / 8), whose memory requirements also increase over time.
safety
Scrypt is relatively new and untested, but is considered an alternative to bcrypt and PBKDF2 . Since the security of password-based key derivation functions is measured primarily by their protection against dictionary attacks and the brute-force method , the obvious vulnerability of other functions motivates the use of relatively new functions such as scrypt.
2013 theoretical vulnerability was of scrypt against a side-channel attack by cache timing published. The password-dependent different access times to the memory vector in the subsequent iterations of scrypt can be used for a password sieve under certain circumstances ( cache-time attack ). The authors point out that such an attack on scrypt is currently only theoretically possible.
In 2014, Markus Dürmuth and Thorsten Kranz from the Ruhr University Bochum compared the password hashing methods bcrypt and Scrypt with regard to attacks with specialized hardware. Scrypt is therefore more vulnerable than bcrypt, despite higher memory requirements for low parameters, since Scrypt can be efficiently executed by GPUs with low parameters . A vulnerability of Scrypt with low parameters by GPUs was also determined elsewhere.
Web links
- scrypt page from Tarsnap (English)
- Internet-Draft IETF to scrypt (English)
- coinwiki.org: List of all Coins. List of cryptocurrencies. The algorithms for mining are also listed.
Individual evidence
- ↑ Mark Dürmuth, Tim Güneysu, Markus Kasper, Christof Paar, Tolga Yalcin, Ralf Zimmermann: Evaluation of Standardized Password-Based Key Derivation against Parallel Processing Platforms. In: Computer Security - ESORICS 2012, Springer-Verlag, Berlin Heidelberg 2012, ISBN 978-3-642-33166-4 , pp. 716-733.
- ^ Arnold Reinhold: HEKS: A Family of Key Stretching Algorithms .
- ↑ Lecture about Scrypt at the BSDCan: scrypt - A new key derivation function (English)
- ↑ Tarsnap announcement: scrypt 1.2.0 released .
- ^ Website of the Password Hashing Competition: Introduction. (English)
- ↑ Presentation of YESCRYPT 1.0.0 on Openwall: yescrypt - modern KDF and password hashing scheme (English)
- ↑ Comparison between Litecoin and Bitcoin Mining ( Memento of the original from July 2, 2014 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (English)
- ↑ Litecoin official website: Block hashing algorithm. ( Memento of the original from August 10, 2017 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. (English)
- ↑ Bitcoin magazine: ASICS for Litecoin. Here they come. (English)
- ↑ David Muller: What is Vertcoin? ( Memento of the original from December 8, 2015 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. (pdf) (English)
- ^ Coin-Brief-Announcement: Vertcoin (VTC) plans algorithm change to Lyra2. (English)
- ^ Password Hashing Competition: Candidates. ( Memento of 11 August 2015, Internet Archive ) (English)
- ↑ About YACoin. (English)
- ↑ Scrypt-Jane at GitHub: A flexible implementation of Colin Percival's scrypt (English)
- ↑ Introduction of the Password Hashing Competition (English)
- ↑ Christian Forler, Stefan Lucks, Jacob Wenzel: Catena: A Memory-Consuming Password Scrambler . Cryptology ePrint Archive: Report 2013/525.
- ↑ Markus Dürmuth and Thorsten Kranz: On Password Guessing with GPUs and FPGAs. (pdf)
- ↑ Openwall mailing list: using scrypt for user authentication.
- ^ Anthony Ferrara: Why I Don't Recommend Scrypt. ircmaxell's blog
