Skip to main content

scrypt - Memory-Hard Key Derivation

About 2 min read

scrypt is a memory-hard password hash function that resists parallel attacks by GPUs and ASICs by consuming large amounts of memory. It was designed by Colin Percival in 2009 for key derivation in the online backup service Tarsnap. Whereas bcrypt is CPU-bound, scrypt demands memory-bound computation, raising the cost of attacks. It is also used as the Proof of Work algorithm of the cryptocurrency Litecoin.

Historical Background

In the late 2000s, general-purpose computing on GPUs (GPGPU) spread rapidly, and brute-force attacks against CPU-bound hash functions like bcrypt became a realistic threat. To address this, Colin Percival designed scrypt around the idea that "if you force the consumption of large amounts of memory in addition to computation, you can reduce the advantage of GPU parallelism." It was adopted for Tarsnap's backup encryption in 2009 and published as the informational RFC 7914 in 2016. When Litecoin, which appeared in 2011, adopted scrypt, it also came into use in the cryptocurrency field.

How the ROMix Algorithm Works

The core of scrypt is an algorithm called ROMix. The processing is broadly divided into two phases.

Phase 1: Memory Filling

Generate N pseudo-random blocks from an initial value and store them in a huge array. When N = 2^20 (about 1 million) and r = 8, it consumes about 1 GiB of memory. This array is referenced in the next phase.

Phase 2: Memory-Dependent Mixing

Mix the values while referencing random positions in the array N times. Because each reference target depends on the immediately preceding computation result, it cannot be predicted in advance. Reducing memory forces recomputation, which raises the time cost.

This property, where "cutting memory increases the computation time," is the essence of scrypt's memory-hardness. When an attacker tries to save memory to increase parallelism, the computation time per instance grows, so the total attack cost is hard to bring down.

Comparison with Argon2 and bcrypt

PropertybcryptscryptArgon2id
Year introduced199920092015
Memory-hard✗✓✓
Side-channel resistanceHighLow (data-dependent access)High (Argon2id hybrid mode)
Parameter intuitivenessSimple with a single costThe relationship of N, r, p is complexMemory, time, and parallelism are independent
OWASP recommendation rank3rd2nd1st
Adoption in cryptocurrenciesNoneLitecoin, Dogecoin, etc.Some mining-resistant designs

Parameter Design (N, r, p)

scrypt has the following three parameters.

N (CPU/memory cost): Specified as a power of 2. Memory usage ≈ 128 × N × r bytes
r (block size): The size of the internal block. RFC 7914 (2016) states that r = 8 and p = 1 appeared to yield good results at the time
p (parallelism): The number of lanes that can be computed independently
Recommended settings (OWASP 2025): N = 2^17 (131072), r = 8, p = 1 → about 128 MB of memory

Doubling N doubles both memory usage and computation time. Because the interdependence of the parameters is complex, tuning is somewhat more difficult compared with algorithms like Argon2id that allow memory, time, and parallelism to be adjusted independently. The salt follows the same basic principles as other password hashing schemes.

Adoption in Litecoin

Litecoin, which appeared in 2011, adopted scrypt as its Proof of Work algorithm in place of Bitcoin's SHA-256. The aim at the time was to "prevent the oligopolization of mining by ASICs and allow ordinary PCs to participate in mining." However, scrypt-compatible ASICs appeared around 2014, and the original goal was not achieved. We explain cryptocurrency security in cryptocurrency wallet security.

Examples of Misconceptions

Some argue that "scrypt is old, so it should not be used," but when operated with appropriate parameters, it still provides sufficient security as of 2025. OWASP states that scrypt should be used when Argon2id is not available. For the fundamentals of cryptography, see the basics of encryption, and for the overall picture of password management, also refer to the secure password management guide.

Was this article helpful?

Related Terms