Topic: ASICS 101 for dunces? (Read 777 times)

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 random access memory 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.

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.