Scrypt

In cryptography, scrypt is a 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 parallel brute force attacks by using large amounts of computer memory.

Introduction

A key derivation function, or 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.

However, previous 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 specifically 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 KDFs, making the size and the cost of a hardware implementation much more expensive, and therefore limiting the amount of paralleling 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 straight forward implementation would need to keep the entire vector in random access memory so that it can be accessed as needed.

Of course, 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.

Such a trade off often exists in computer algorithms: you can increase speed at the cost of using more memory, or decrease memory requirements 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 they could use an implementation that runs more quickly but has very large memory requirements and is therefore more expensive to parallelize.

External Links

• The scrypt page on the Tarsnap web site.