Scrypt

{{Use dmy dates|date=March 2022}} {{Short description|2009 password-based key derivation function}} {{distinguish|Script (disambiguation)}} {{lowercase}} {{Infobox cryptographic hash function | name = scrypt | image = | caption = <!-- General --> | designers = Colin Percival | publish date = 2009 | series = | derived from = | derived to = | related to = | certification = <!-- Detail --> | digest size = variable | block size = variable | structure = | rounds = variable | cryptanalysis = }}

In cryptography, '''scrypt''' (pronounced "ess crypt"<ref>{{cite web|title=Colin Percival |website=Twitter|url=https://twitter.com/cperciva/status/734613598383841281 |archive-url=https://web.archive.org/web/20190217215034/https://twitter.com/cperciva/status/734613598383841281 |archive-date=17 February 2019 |url-status=live}}</ref>) is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service.<ref name="tarsnap">{{cite web |title=The scrypt key derivation function |website=Tarsnap |url=http://www.tarsnap.com/scrypt.html |access-date=21 January 2014 |archive-date=28 May 2019 |archive-url=https://web.archive.org/web/20190528073159/https://www.tarsnap.com/scrypt.html |url-status=live }}</ref><ref name="manpages">{{cite web |title=SCRYPT(1) General Commands Manual |website=Debian Manpages |url=https://manpages.debian.org/testing/scrypt/scrypt.1.en.html |access-date=2 March 2022 |archive-date=2 March 2022 |archive-url=https://web.archive.org/web/20220302173629/https://manpages.debian.org/testing/scrypt/scrypt.1.en.html |url-status=live }}</ref> 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.<ref>{{cite web |last1=Percival |first1=Colin |last2=Josefsson |first2=Simon |title=The scrypt Password-Based Key Derivation Function |date=August 2016 |url=https://datatracker.ietf.org/doc/html/rfc7914 |publisher=RFC Editor |access-date=13 December 2021 |ref=RFC 7914 |archive-date=13 December 2021 |archive-url=https://web.archive.org/web/20211213142419/https://datatracker.ietf.org/doc/html/rfc7914 |url-status=live }}</ref> 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.<ref>{{cite web|url=https://www.vice.com/en/article/beyond-bitcoin-a-guide-to-the-most-promising-cryptocurrencies/|title=Beyond Bitcoin: A Guide to the Most Promising Cryptocurrencies|author=Alec Liu|date=29 November 2013|access-date=8 July 2017|archive-date=13 June 2018|archive-url=https://web.archive.org/web/20180613111615/https://motherboard.vice.com/en_us/article/4x3ywn/beyond-bitcoin-a-guide-to-the-most-promising-cryptocurrencies|url-status=live}}</ref>

== Introduction ==

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,<ref>{{Cite web |url=http://www.tarsnap.com/scrypt/scrypt.pdf |title=Stronger Key Derivation Via Sequential Memory-Hard Functions |access-date=2022-11-11 |last=Percival |first=Colin |archive-date=14 April 2019 |archive-url=https://web.archive.org/web/20190414144147/http://www.tarsnap.com/scrypt/scrypt.pdf |url-status=live }}</ref> 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.

== Overview == 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.

== Algorithm == {{pre|style=font-size:80%|1=<nowiki/> <span style="color:blue;">'''Function'''</span> scrypt <span style="color:blue;">'''Inputs:'''</span> <span style="color:green;">''This algorithm includes the following parameters:''</span> Passphrase: Bytes <span style="color:green;">string of characters to be hashed</span> Salt: Bytes <span style="color:green;">string of random characters that modifies the hash to protect against Rainbow table attacks</span> CostFactor (N): Integer <span style="color:green;">CPU/memory cost parameter – Must be a power of 2 (e.g. 1024)</span> BlockSizeFactor (r): Integer <span style="color:green;">blocksize parameter, which fine-tunes sequential memory read size and performance. (8 is commonly used)</span> ParallelizationFactor (p): Integer <span style="color:green;">''Parallelization parameter''. (1 .. 2³²-1 * hLen/MFlen)</span> DesiredKeyLen (dkLen): Integer <span style="color:green;">Desired key length in bytes (Intended output length in octets of the derived key; a positive integer satisfying dkLen ≤ (2³²− 1) * hLen.)</span> hLen: Integer <span style="color:green;">The length in octets of the hash function (32 for SHA256).</span> MFlen: Integer <span style="color:green;">The length in octets of the output of the mixing function (''SMix'' below). Defined as r * 128 in RFC7914.</span> <span style="color:blue;">'''Output:'''</span> DerivedKey: Bytes <span style="color:green;">array of bytes, DesiredKeyLen long</span> <span style="color:green;">''Step 1. Generate expensive salt''</span> blockSize ← 128*BlockSizeFactor <span style="color:green;">''// Length (in bytes) of the SMix mixing function output (e.g. 128*8 = 1024 bytes)''</span> <span style="color:green;">Use PBKDF2 to generate initial 128*BlockSizeFactor*p bytes of data (e.g. 128*8*3 = 3072 bytes)</span> <span style="color:green;">Treat the result as an array of ''p'' elements, each entry being ''blocksize'' bytes (e.g. 3 elements, each 1024 bytes)</span> [B₀...B_p−1] ← PBKDF2_HMAC-SHA256(''Passphrase'', ''Salt'', 1, blockSize*ParallelizationFactor) <span style="color:green;">Mix each block in '''B''' Costfactor times using '''ROMix''' function (each block can be mixed in parallel)</span> <span style="color:blue;">'''for'''</span> i ← 0 <span style="color:blue;">'''to'''</span> p-1 <span style="color:blue;">'''do'''</span> B_i ← ROMix(B_i, CostFactor) <span style="color:green;">All the elements of B is our new "expensive" salt</span> expensiveSalt ← B₀∥B₁∥B₂∥ ... ∥B_p-1 <span style="color:green;">''// where ∥ is concatenation''</span> <span style="color:green;">''Step 2. Use PBKDF2 to generate the desired number of bytes, but using the expensive salt we just generated''</span> <span style="color:blue;">'''return'''</span> PBKDF2_HMAC-SHA256(Passphrase, expensiveSalt, 1, DesiredKeyLen); }} Where ''{{code|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) <span style="color:green;">Create ''Iterations'' copies of ''X''</span> X ← Block '''for''' i ← 0 '''to''' Iterations−1 '''do''' V_i ← X X ← BlockMix(X) '''for''' i ← 0 '''to''' Iterations−1 '''do''' j ← Integerify(X) mod Iterations X ← BlockMix(X '''xor''' V_j) '''return''' X

Where RFC 7914 defines {{code|Integerify(X)}} as the result of interpreting the last 64 bytes of X as a ''little-endian'' integer A₁.

Since Iterations equals 2 to the power of N, only the ''first'' {{code|Ceiling(N / 8)}} bytes among the ''last'' 64 bytes of X, interpreted as a ''little-endian'' integer A₂, are actually needed to compute <code>Integerify(X) mod Iterations = A₁ mod Iterations = A₂ mod Iterations</code>.

'''Function''' BlockMix(B): <span style="color:green;">''The block B is r 128-byte chunks (which is equivalent of 2r 64-byte chunks)''</span> r ← Length(B) / 128; <span style="color:green;">''Treat B as an array of 2r 64-byte chunks''</span> [B₀...B_2r-1] ← B X ← B_2r−1 '''for''' i ← 0 '''to''' 2r−1 '''do''' X ← Salsa20/8(X xor B_i) <span style="color:green;">'''// Salsa20/8 hashes from 64-bytes to 64-bytes'''</span> Y_i ← X '''return''' ← Y₀∥Y₂∥...∥Y_2r−2 ∥ Y₁∥Y₃∥...∥Y_2r−1

Where ''Salsa20/8'' is the 8-round version of Salsa20.

== Cryptocurrency uses == 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.<ref>{{cite book |url=https://books.google.com/books?id=IXmrBQAAQBAJ&pg=PA221 |title=Mastering Bitcoin: Unlocking Digital Cryptocurrencies |pages=221, 223 |author=Andreas M. Antonopoulos |date=3 December 2014 |publisher=O'Reilly Media |isbn=9781491902646 }}</ref><ref>{{cite web | url=https://litecoin.info/History_of_cryptocurrency | title=History of cryptocurrency |date=7 February 2014|website=litecoin.info wiki| access-date=27 June 2014 | archive-url=https://web.archive.org/web/20160611133738/https://litecoin.info/History_of_cryptocurrency | archive-date=11 June 2016 | url-status=dead }}</ref> 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.<ref>{{cite book|url=https://www.amazon.com/Litecoin-Scrypt-Mining-Configurations-Radeon-ebook/dp/B00E2RT1I4|title=Litecoin Scrypt Mining Configurations for Radeon 7950|author=Roman Guelfi-Gibbs|publisher=Amazon Digital Services|access-date=11 September 2017|archive-date=24 October 2016|archive-url=https://web.archive.org/web/20161024084236/https://www.amazon.com/Litecoin-Scrypt-Mining-Configurations-Radeon-ebook/dp/B00E2RT1I4|url-status=live}}</ref> This led to shortages of high end GPUs due to the rising price of these currencies in the months of November and December 2013.<ref>{{cite web|url=http://www.extremetech.com/computing/172381-massive-surge-in-litecoin-mining-leads-to-radeon-shortage|author=Joel Hruska|title=Massive surge in Litecoin mining leads to graphics card shortage|date=10 December 2013|publisher=ExtremeTech|access-date=1 January 2014|archive-date=12 December 2017|archive-url=https://web.archive.org/web/20171212093559/http://www.extremetech.com/computing/172381-massive-surge-in-litecoin-mining-leads-to-radeon-shortage|url-status=live}}</ref>

== Utility == {{Infobox software | name = scrypt encryption utility | developer = Colin Percival | latest release version = {{wikidata|property|preferred|references|edit|Q114883606|P348|P548=Q2804309}} | latest release date = {{Start date and age|{{wikidata|qualifier|preferred|single|Q114883606|P348|P548=Q2804309|P577}}|df=yes}} | latest preview version = | repo = {{URL|https://github.com/Tarsnap/scrypt}} | operating system = | size = | language = | license = | website = {{URL|https://www.tarsnap.com/scrypt.html}} }} The scrypt utility was written in May 2009 by Colin Percival as a demonstration of the scrypt key derivation function.<ref name="tarsnap"/><ref name="manpages"/> It's available in most Linux and BSD distributions.

==See also== {{Portal|Free and open-source software}} * Argon2 – winner of the Password Hashing Competition in 2015 * bcrypt – blowfish-based password-hashing function * bcrypt – blowfish-based cross-platform file encryption utility developed in 2002<ref>{{cite web|url=https://bcrypt.sourceforge.net/|title=Bcrypt – Blowfish File Encryption (homepage)|accessdate=8 April 2024|first1=Johnny|last1=Shelley|first2=Philip|last2=Stolarczyk|website=Sourceforge|archive-date=29 August 2015|archive-url=https://web.archive.org/web/20150829060804/http://bcrypt.sourceforge.net/|url-status=live}}</ref><ref>{{Cite web|url=https://droidinformer.org/tools/bcrypt/|title=bcrypt APK for Android – free download on Droid Informer|website=droidinformer.org|access-date=2 March 2022|archive-date=15 February 2020|archive-url=https://web.archive.org/web/20200215210334/https://droidinformer.org/tools/bcrypt/|url-status=live}}</ref><ref>{{Cite web|url=http://t2sde.org/packages/bcrypt.html|title=T2 package – trunk – bcrypt – A utility to encrypt files.|website=t2sde.org|access-date=2 March 2022|archive-date=28 October 2017|archive-url=https://web.archive.org/web/20171028043502/http://t2sde.org/packages/bcrypt.html|url-status=live}}</ref><ref>{{Cite web|url=https://docs.oracle.com/goldengate/1212/gg-winux/OGGLC/ogglc_licenses.htm|title=Oracle® GoldenGate Licensing Information|website=Oracle Help Center|access-date=8 April 2024|archive-date=6 March 2024|archive-url=https://web.archive.org/web/20240306230633/https://docs.oracle.com/goldengate/1212/gg-winux/OGGLC/ogglc_licenses.htm|url-status=live}}</ref> * crypt – Unix C library function * crypt – Unix utility * ccrypt – utility * Key derivation function * Key stretching * mcrypt – utility * PBKDF2 – a widely used standard Password-Based Key Derivation Function 2 * [https://github.com/epixoip/pufferfish PufferFish] – a cache-hard password hashing function based on improved bcrypt design * Space–time tradeoff * yescrypt – successor to scrypt

== References == {{reflist}}

== External links == * [https://www.tarsnap.com/scrypt.html The scrypt page on the Tarsnap website.] * [https://www.tarsnap.com/scrypt/scrypt.pdf The original scrypt paper.] * {{GitHub|https://github.com/Tarsnap/scrypt}}

{{Cryptography navbox|hash}}

{{Cryptocurrencies}}

Category:Cryptographic algorithms Category:Key derivation functions Category:Articles with example pseudocode