Scrypt


In cryptography, scrypt is a password-based key derivation function created by Colin Percival, originally for the Tarsnap online backup service. 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. 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.

Introduction

A password-based key derivation function is generally designed to be computationally intensive, so that it takes a relatively long time to compute. Legitimate users only need to perform the function once per operation, 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 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. 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,
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 in order 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 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

The algorithm includes the following parameters:
Function scrypt
Inputs:
Passphrase: Bytes string of characters to be hashed
Salt: Bytes random salt
CostFactor : Integer CPU/memory cost parameter - Must be a power of 2
BlockSizeFactor : Integer blocksize parameter
ParallelizationFactor : Integer Parallelization parameter.
DesiredKeyLen: Integer Desired key length in bytes
Output:
DerivedKey: Bytes array of bytes, DesiredKeyLen long
Step 1. Generate expensive salt
blockSize ← 128*BlockSizeFactor //Length of the SMix mixing function output
Use PBKDF2 to generate initial 128*BlockSizeFactor*p bytes of data
Treat the result as an array of p elements, each entry being blocksize bytes
← PBKDF2HMAC-SHA256
Mix each block in B Costfactor times using ROMix function
for i ← 0 to p-1 do
Bi ← ROMix
All the elements of B is our new "expensive" salt
expensiveSalt ← B0∥B1∥B2∥... ∥Bp-1 //where ∥ is concatenation

Step 2. Use PBKDF2 to generate the desired number of bytes, but using the expensive salt we just generated
return PBKDF2HMAC-SHA256;
Where PBKDF2 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
Create Iterations copies of X
X ← Block
for i ← 0 to Iterations−1 do
Vi ← X
X ← BlockMix
for i ← 0 to Iterations−1 do
j ← Integerify mod Iterations
X ← BlockMix
return X
Where RFC 7914 defines Integerify 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 bytes among the last 64 bytes of X, interpreted as a little-endian integer A2, are actually needed to compute Integerify mod Iterations = A1 mod Iterations = A2 mod Iterations.
Function BlockMix:
The block B is r 128-byte chunks
r ← Length / 128;
Treat B as an array of 2r 64-byte chunks
← B
X ← B2r−1
for i ← 0 to 2r−1 do
X ← Salsa20/8 //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.

Cryptocurrency uses

Scrypt is used in many cryptocurrencies as a proof-of-work algorithm. It was first implemented for Tenebrix and served as the basis for Litecoin and Dogecoin, which also adopted its scrypt algorithm. Mining of cryptocurrencies that use scrypt is often performed on graphics processing units since GPUs tend to have significantly more processing power compared to the CPU. This led to shortages of high end GPUs due to the rising price of these currencies in the months of November and December 2013.
As of May 2014, specialized ASIC mining hardware is available for scrypt-based cryptocurrencies.