Scrypt
scryptが多くのメモリを必要とすることはアルゴリズムの一部として生成される擬似ランダムビット文字列の大きなベクターに由来する。ベクターが一度生成されると、派生鍵を生成するためにその要素に対して擬似ランダムな順序でアクセスと結合が行われる。単純な実装では、必要に応じてアクセスできるように、ベクター全体をRAMに保持する必要がある。
ベクターの要素はアルゴリズムで生成されるので、必要に応じて各要素をオンザフライで生成でき、一度に1つの要素だけをメモリに格納できるので、メモリ使用量が大幅に削減される。しかし、各要素の生成には多くの計算資源を必要とすることを意図しており、要素は関数の実行中に何度もアクセスされることが予想される。したがって、メモリの使用量を減らすには速度に大きなトレードオフがある。
この種の時間とメモリのトレードオフは、多くのコンピューターアルゴリズムに存在する。速度はより多くのメモリを使用することで上げることができ、メモリ使用量はより多くの操作を実行して長い時間を必要とすることで減らすことができる。scryptの背後にある考え方は、このトレードオフを意図的にどちらも高価なものにすることである。したがって、攻撃者は限られた費用で大規模な並列化が可能な多くの計算資源を必要としない実装を使用する可能性があるが、これの実行速度は非常に遅くなる。または、高速に実行できる実装を使用する場合は、大量のメモリが必要となることから並列化のコストが高価になる。
パスワードベースの鍵導出関数は一般的に多くの計算資源が必要になるように設計されているので、計算に比較的長い時間がかかる。正しいユーザーは認証などの操作ごとにこれを1回だけ実行するので、必要な時間は僅かである。しかし、総当たり攻撃では操作を何十億回も実行する必要がある可能性が高く、その時点で必要な時間が無視できないほどになり、理想的には途方もない時間が必要となる。
RSAセキュリティによるPBKDF2などの以前のパスワードベースの鍵導出関数は、要求される計算資源が比較的低く、実行に綿密なハードウェアや大量のメモリを必要としない。そのため、ASICやFPGAなどのハードウェアに簡単かつ安価に実装することができる。これによって、十分な計算資源を持つ攻撃者は、数百から数千のハードウェアにアルゴリズムの実装を構築し、それぞれが鍵空間の異なるサブセットを検索することで、大規模な並列攻撃を始めることができる。これは総当たり攻撃を完了するのに必要な時間を利用可能な実装で割ることにより、必要な時間を妥当なものに引き下げる可能性が非常に高い。
scrypt関数はアルゴリズムの計算資源要求を引き上げることによって、このような試みを阻止するように設計されている。具体的には、このアルゴリズムは他のパスワードベースの鍵導出関数と比較して大量のメモリを使用するように設計されており、ハードウェア実装のサイズとコストが遥かに高くなるので、攻撃者が実行可能な並列処理の量が制限される。