Scrypt

Scrypt
Name	Scrypt
Invented by	Colin Percival
Introduced	2009
Purpose	Password-based key derivation, proof-of-work
License	Free (various implementations)

Scrypt is a password-based key derivation function and memory-hard algorithm originally published in 2009 for use in secure storage and computationally intensive proof-of-work schemes. It was designed to increase the cost of large-scale custom hardware attacks by requiring substantial memory, and it has been adopted in diverse software, cryptographic systems, and digital currency projects. The design reflects reactions to developments in Application-specific integrated circuits, the evolution of SHA-256-based mining, and concerns voiced in cryptographic research communities such as those around Usenix and the Cryptography Research community.

History

Scrypt was introduced by Colin Percival in 2009 while he was associated with the Tarsnap online backup service and described in an IACR whitepaper and associated postings to Usenix and mailing lists. The release occurred amid debates involving Bitcoin researchers, proponents of SHA-256 mining, and developers of Litecoin and other alternative cryptocurrencies who sought ASIC-resistant proof-of-work primitives. Early adopters included projects influenced by work on OpenSSL, GnuPG, and password storage guidance from organizations such as NIST and security advocates like Bruce Schneier. Subsequent discourse involved implementers from Google and contributors to OpenBSD and FreeBSD kernels adapting memory-hard schemes for practical deployments.

Design and algorithm

Scrypt's design builds on concepts from established primitives such as PBKDF2, HMAC, and SHA-256, combining pseudorandom functions with large, sequentially accessed memory arrays to enforce memory hardness. The core algorithm derives keys by expanding input through an initial key derivation stage (akin to PBKDF2-HMAC-SHA256), filling a large vector of pseudorandom blocks, repeatedly mixing entries with a block function inspired by AES-like mixing and integer arithmetic, and applying a final extraction stage. Parameters N, r, and p control cost: N sets the CPU/memory iteration count, r adjusts block size similar to Salsa20's block mixing considerations, and p allows parallelization reflective of thread-level models used by projects like OpenMP and POSIX threads. The algorithm’s structure references constructions explored in academic venues such as CRYPTO and Eurocrypt.

Security and cryptanalysis

Analyses of Scrypt by researchers at institutions including University of Illinois, MIT, and ETH Zurich examined time-memory trade-offs, cache-timing considerations, and side-channel vectors similar to those studied for RSA and AES. Attacks investigated include sequential memory-reduction attacks, time-memory-data trade-offs, and specialized hardware implementations by vendors producing FPGA and ASIC miners. Cryptanalytic results often cite reductions and bounds in the style of papers presented at IEEE Symposium on Security and Privacy and ACM CCS, noting that practical attacks generally require either prohibitive time penalties or large-area memory on silicon. Work from groups at Georgia Tech and Microsoft Research explored potential optimizations and proof techniques, while vendors like Xilinx and Intel considered FPGA/CPU trade-offs.

Implementations and libraries

Implementations of the algorithm exist in many languages and ecosystems, including ports in OpenSSL-associated projects, bindings for Python maintained in repositories used by PyPI projects, C implementations used in LibreSSL and OpenBSD, and optimized kernels for CUDA and OpenCL targeting NVIDIA and AMD GPUs. Libraries include widely used packages integrated into OpenSSH-adjacent tooling, cryptographic toolchains in GnuTLS stacks, and language-specific modules for ecosystems such as Node.js, Go (programming language), Rust (programming language), and Java (programming language). Enterprise vendors like IBM and Oracle Corporation have evaluated scrypt for secure credential storage in products and services.

Use in cryptocurrencies and applications

Scrypt has been adopted as a proof-of-work function in several cryptocurrencies seeking resistance to SHA-256 ASIC dominance, most notably in Litecoin and later in projects such as Dogecoin, Feathercoin, and Vertcoin. These communities, which include contributors from Bitcointalk forums and developers associated with foundations like the Litecoin Foundation, chose scrypt to raise the cost of custom hashing hardware and to encourage CPU/GPU mining. Outside cryptocurrencies, scrypt has been used for encrypting backups in services like Tarsnap and for password hashing in applications leveraging Dovecot, Postfix, and web frameworks favored by GitHub and Stack Overflow developers.

Performance and memory-hardness

The memory-hardness claim of scrypt centers on forcing large pseudorandom arrays to be stored and accessed, making low-memory implementations slower by significant factors compared to full-memory implementations. Performance comparisons between CPU, GPU, FPGA, and ASIC implementations were documented in benchmarking studies led by research groups at Princeton University and companies such as NVIDIA and AMD; these studies highlight that scrypt raises the cost-per-hash for silicon miners compared to SHA-256d miners used in Bitcoin. Parameter tuning (N, r, p) allows deployment-specific trade-offs similar to tuning knobs in PBKDF2 and bcrypt, with higher N increasing both RAM requirements and wall-clock time. Memory bandwidth, cache architecture from Intel and ARM Holdings CPUs, and NUMA effects influence real-world performance.

Alternatives and related key derivation functions

Related memory-hard and password-based functions include PBKDF2, bcrypt, Argon2, and constructions from academic proposals like Catena and Lyra2. Argon2, winner of the Password Hashing Competition organized by ECRYPT and hosted by groups including CNRS and INRIA, introduced design elements such as improved resistance to GPU/ASIC trade-offs and multiple operational modes (Argon2i/Argon2d/Argon2id). Other alternatives include KDFs standardized in NIST Special Publications and proposals from the IETF and IACR communities. Comparative studies by researchers at UC Berkeley and ETH Zurich evaluate trade-offs in security, parallelism, and implementation complexity across these functions.

Category:Key derivation functions