| General | |
|---|---|
| Designers | Colin Percival |
| First published | 2009 |
| Cipher detail | |
| Digest sizes | variable |
| Block sizes | variable |
| Rounds | variable |
In cryptography, scrypt (pronounced "ess crypt" [1] ) is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service. [2] [3] The algorithm was specifically designed to make it costly to perform large-scale custom hardware attacks by requiring large amounts of memory. In 2016, the scrypt algorithm was published by IETF as RFC 7914. [4] A simplified version of scrypt is used as a proof-of-work scheme by a number of cryptocurrencies, first implemented by an anonymous programmer called ArtForz in Tenebrix and followed by Fairbrix and Litecoin soon after. [5]
A password-based key derivation function (password-based KDF) is generally designed to be computationally intensive, so that it takes a relatively long time to compute (say on the order of several hundred milliseconds). Legitimate users only need to perform the function once per operation (e.g., authentication), and so the time required is negligible. However, a brute-force attack would likely need to perform the operation billions of times, at which point the time requirements become significant and, ideally, prohibitive.
Previous password-based KDFs (such as the popular PBKDF2 from RSA Laboratories) have relatively low resource demands, meaning they do not require elaborate hardware or very much memory to perform. They are therefore easily and cheaply implemented in hardware (for instance on an ASIC or even an FPGA). This allows an attacker with sufficient resources to launch a large-scale parallel attack by building hundreds or even thousands of implementations of the algorithm in hardware and having each search a different subset of the key space. This divides the amount of time needed to complete a brute-force attack by the number of implementations available, very possibly bringing it down to a reasonable time frame.
The scrypt function is designed to hinder such attempts by raising the resource demands of the algorithm. Specifically, the algorithm is designed to use a large amount of memory compared to other password-based KDFs, [6] making the size and the cost of a hardware implementation much more expensive, and therefore limiting the amount of parallelism an attacker can use, for a given amount of financial resources.
The large memory requirements of scrypt come from a large vector of pseudorandom bit strings that are generated as part of the algorithm. Once the vector is generated, the elements of it are accessed in a pseudo-random order and combined to produce the derived key. A straightforward implementation would need to keep the entire vector in RAM so that it can be accessed as needed.
Because the elements of the vector are generated algorithmically, each element could be generated on the fly as needed, only storing one element in memory at a time and therefore cutting the memory requirements significantly. However, the generation of each element is intended to be computationally expensive, and the elements are expected to be accessed many times throughout the execution of the function. Thus there is a significant trade-off in speed to get rid of the large memory requirements.
This sort of time–memory trade-off often exists in computer algorithms: speed can be increased at the cost of using more memory, or memory requirements decreased at the cost of performing more operations and taking longer. The idea behind scrypt is to deliberately make this trade-off costly in either direction. Thus an attacker could use an implementation that doesn't require many resources (and can therefore be massively parallelized with limited expense) but runs very slowly, or use an implementation that runs more quickly but has very large memory requirements and is therefore more expensive to parallelize.
Function scrypt Inputs:This algorithm includes the following parameters: Passphrase: Bytes string of characters to be hashed Salt: Bytes string of random characters that modifies the hash to protect against Rainbow table attacks CostFactor (N): Integer CPU/memory cost parameter – Must be a power of 2 (e.g. 1024) BlockSizeFactor (r): Integer blocksize parameter, which fine-tunes sequential memory read size and performance. (8 is commonly used) ParallelizationFactor (p): Integer Parallelization parameter. (1 .. 232-1 * hLen/MFlen) DesiredKeyLen (dkLen): Integer Desired key length in bytes (Intended output length in octets of the derived key; a positive integer satisfying dkLen ≤ (232− 1) * hLen.) hLen: Integer The length in octets of the hash function (32 for SHA256). MFlen: Integer The length in octets of the output of the mixing function (SMix below). Defined as r * 128 in RFC7914.Output: DerivedKey: Bytes array of bytes, DesiredKeyLen longStep 1. Generate expensive salt blockSize ← 128*BlockSizeFactor // Length (in bytes) of the SMix mixing function output (e.g. 128*8 = 1024 bytes)Use PBKDF2 to generate initial 128*BlockSizeFactor*p bytes of data (e.g. 128*8*3 = 3072 bytes)Treat the result as an array of p elements, each entry being blocksize bytes (e.g. 3 elements, each 1024 bytes) [B0...Bp−1] ← PBKDF2 HMAC-SHA256(Passphrase, Salt, 1, blockSize*ParallelizationFactor) Mix each block in B Costfactor times using ROMix function (each block can be mixed in parallel)for i ← 0 to p-1 do Bi ← ROMix(Bi, CostFactor) All the elements of B is our new "expensive" salt expensiveSalt ← B0∥B1∥B2∥ ... ∥Bp-1// where ∥ is concatenationStep 2. Use PBKDF2 to generate the desired number of bytes, but using the expensive salt we just generatedreturn PBKDF2HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen);
Where PBKDF2(P, S, c, dkLen) notation is defined in RFC 2898, where c is an iteration count.
This notation is used by RFC 7914 for specifying a usage of PBKDF2 with c = 1.
Function ROMix(Block, Iterations) Create Iterations copies of X X ← Block for i ← 0 to Iterations−1 do Vi ← X X ← BlockMix(X) for i ← 0 to Iterations−1 do j ← Integerify(X) mod Iterations X ← BlockMix(X xor Vj) return XWhere RFC 7914 defines Integerify(X) as the result of interpreting the last 64 bytes of X as a little-endian integer A1.
Since Iterations equals 2 to the power of N, only the first Ceiling(N / 8) bytes among the last 64 bytes of X, interpreted as a little-endian integer A2, are actually needed to compute Integerify(X) mod Iterations = A1 mod Iterations = A2 mod Iterations.
Function BlockMix(B): The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks) r ← Length(B) / 128; Treat B as an array of 2r 64-byte chunks [B0...B2r-1] ← B X ← B2r−1for i ← 0 to 2r−1 do X ← Salsa20/8(X xor Bi) // Salsa20/8 hashes from 64-bytes to 64-bytes Yi ← X return ← Y0∥Y2∥...∥Y2r−2 ∥ Y1∥Y3∥...∥Y2r−1
Where Salsa20/8 is the 8-round version of Salsa20.
Scrypt is used in many cryptocurrencies as a proof-of-work algorithm (more precisely, as the hash function in the Hashcash proof-of-work algorithm). It was first implemented for Tenebrix (released in September 2011) and served as the basis for Litecoin and Dogecoin, which also adopted its scrypt algorithm. [7] [8] Mining of cryptocurrencies that use scrypt is often performed on graphics processing units (GPUs) since GPUs tend to have significantly more processing power (for some algorithms) compared to the CPU. [9] This led to shortages of high end GPUs due to the rising price of these currencies in the months of November and December 2013. [10]
| Developer(s) | Colin Percival |
|---|---|
| Stable release | |
| Repository | github |
| Website | www |
The scrypt utility was written in May 2009 by Colin Percival as a demonstration of the scrypt key derivation function. [2] [3] It's available in most Linux and BSD distributions.
Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in many cipher suites and encryption products. Blowfish provides a good encryption rate in software, and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard (AES) now receives more attention, and Schneier recommends Twofish for modern applications.
In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message. An HMAC is a type of keyed hash function that can also be used in a key derivation scheme or a key stretching scheme.
A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:
In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format, such as converting a group element that is the result of a Diffie–Hellman key exchange into a symmetric key for use with AES. Keyed cryptographic hash functions are popular examples of pseudorandom functions used for key derivation.
In cryptanalysis and computer security, password cracking is the process of recovering passwords from data that has been stored in or transmitted by a computer system in scrambled form. A common approach is to repeatedly try guesses for the password and to check them against an available cryptographic hash of the password. Another type of approach is password spraying, which is often automated and occurs slowly over time in order to remain undetected, using a list of common passwords.
In cryptography, PBKDF1 and PBKDF2 are key derivation functions with a sliding computational cost, used to reduce vulnerability to brute-force attacks.
A rainbow table is a precomputed table for caching the outputs of a cryptographic hash function, usually for cracking password hashes. Passwords are typically stored not in plain text form, but as hash values. If such a database of hashed passwords falls into the hands of an attacker, they can use a precomputed rainbow table to recover the plaintext passwords. A common defense against this attack is to compute the hashes using a key derivation function that adds a "salt" to each password before hashing it, with different passwords receiving different salts, which are stored in plain text along with the hash.
In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate. Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker.
bcrypt is a password-hashing function designed by Niels Provos and David Mazières, based on the Blowfish cipher and presented at USENIX in 1999. Besides incorporating a salt to protect against rainbow table attacks, bcrypt is an adaptive function: over time, the iteration count can be increased to make it slower, so it remains resistant to brute-force search attacks even with increasing computation power.
BLAKE is a cryptographic hash function based on Daniel J. Bernstein's ChaCha stream cipher, but a permuted copy of the input block, XORed with round constants, is added before each ChaCha round. Like SHA-2, there are two variants differing in the word size. ChaCha operates on a 4×4 array of words. BLAKE repeatedly combines an 8-word hash value with 16 message words, truncating the ChaCha result to obtain the next hash value. BLAKE-256 and BLAKE-224 use 32-bit words and produce digest sizes of 256 bits and 224 bits, respectively, while BLAKE-512 and BLAKE-384 use 64-bit words and produce digest sizes of 512 bits and 384 bits, respectively.
HKDF is a simple key derivation function (KDF) based on the HMAC message authentication code. It was initially proposed by its authors as a building block in various protocols and applications, as well as to discourage the proliferation of multiple KDF mechanisms. The main approach HKDF follows is the "extract-then-expand" paradigm, where the KDF logically consists of two modules: the first stage takes the input keying material and "extracts" from it a fixed-length pseudorandom key, and then the second stage "expands" this key into several additional pseudorandom keys.
Litecoin is a decentralized peer-to-peer cryptocurrency and open-source software project released under the MIT/X11 license. Inspired by Bitcoin, Litecoin was among the earliest altcoins, starting in October 2011. In technical details, the Litecoin main chain shares a slightly modified Bitcoin codebase. The practical effects of those codebase differences are lower transaction fees, faster transaction confirmations, and faster mining difficulty retargeting. Due to its underlying similarities to Bitcoin, Litecoin has historically been referred to as the "silver to Bitcoin's gold." In 2022, Litecoin added optional privacy features via soft fork through the MWEB upgrade.
Microsoft Office password protection is a security feature that allows Microsoft Office documents to be protected with a user-provided password.
crypt is a POSIX C library function. It is typically used to compute the hash of user account passwords. The function outputs a text string which also encodes the salt, and identifies the hash algorithm used. This output string forms a password record, which is usually stored in a text file.
In cryptography, the Salted Challenge Response Authentication Mechanism (SCRAM) is a family of modern, password-based challenge–response authentication mechanisms providing authentication of a user to a server. As it is specified for Simple Authentication and Security Layer (SASL), it can be used for password-based logins to services like LDAP, HTTP, SMTP, POP3, IMAP and JMAP (e-mail), XMPP (chat), or MongoDB and PostgreSQL (databases). For XMPP, supporting it is mandatory.
Master Password is a type of algorithm first implemented by Maarten Billemont for creating unique passwords in a reproducible manner. It differs from traditional password managers in that the passwords are not stored on disk or in the cloud, but are regenerated every time from information entered by the user: Their name, a master password, and a unique identifier for the service the password is intended for.
Argon2 is a key derivation function that was selected as the winner of the 2015 Password Hashing Competition. It was designed by Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich from the University of Luxembourg. The reference implementation of Argon2 is released under a Creative Commons CC0 license or the Apache License 2.0, and provides three related versions:
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, 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, adopted by Vertcoin, MonaCoin, among other cryptocurrencies 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. It is an improvement over 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 the following improvements when compared to its predecessor:
Colin A. Percival is a Canadian computer scientist and computer security researcher. He completed his undergraduate education at Simon Fraser University and a doctorate at the University of Oxford. While at university he joined the FreeBSD project, and achieved some notoriety for discovering a security weakness in Intel's hyper-threading technology. Besides his work in delta compression and the introduction of memory-hard functions, he is also known for developing the Tarsnap online backup service, which became his full-time job.
| |||||||||||||||||||||||||||||
| Technology | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Consensus mechanisms | |||||||||||||||
| Proof of work currencies |
| ||||||||||||||
| Proof of stake currencies | |||||||||||||||
| ERC-20 tokens | |||||||||||||||
| Stablecoins | |||||||||||||||
| Other currencies | |||||||||||||||
| Inactive currencies | |||||||||||||||
| Cryptocurrency exchanges |
| ||||||||||||||
| Crypto service companies | |||||||||||||||
| Related topics |
| ||||||||||||||
