Passwords: Slow on purpose: salts, bcrypt, scrypt and Argon2

In December 2009 a hacker downloaded the user database of RockYou, a maker of social-network games: 32 million passwords, stored in plain text. The list became the attackers' dictionary of choice; its most common entry was 123456, used by almost 300,000 people. In 2012 LinkedIn lost 6.5 million passwords hashed with SHA-1, without salt (the full leak, later, had 117 million); most were cracked within days. Passwords are the weakest link of most systems, and the way a server stores them decides whether a breach reveals a few of them or nearly all.

Never store the password

A server does not need to know your password, only to check it. So it stores a one-way function of it, and at login it recomputes the function on what you typed and compares. Encrypting the passwords is not enough (whoever steals the database often steals the key too), and a plain fast hash is not enough either, as LinkedIn showed. The first good design dates from 1979, when Robert Morris and Ken Thompson described Unix's password scheme: the password was used as a DES key to encrypt a block of zeros, iterated 25 times to make it slower, with a random 12-bit salt that changed the encryption for each user.

Salt

Without salt, the same password always has the same hash. An attacker can then hash a dictionary once and look up every stolen hash in it, and can see at a glance which users share a password. Martin Hellman showed in 1980 that precomputation can trade time for memory: with about $N^{2 / 3}$ memory one can invert a function on $N$ values in about $N^{2 / 3}$ time per target. Philippe Oechslin's rainbow tables (2003) made the trade-off practical and could crack Windows password hashes in seconds.

Proposition (salt defeats precomputation)

If each password is hashed together with an independent random salt of $s$ bits, a precomputed table is useful for at most one salt value, and an attacker with $U$ users to attack must spend the full guessing effort on each user separately: the total work is multiplied by $min (U, 2^{s})$ compared with an unsalted database.

Salts are not secret; they are stored next to the hash. Modern formats write everything in one string. The desktop app produces, for Argon2id, strings like $argon2id$v=19$m=19456,t=2,p=1$salt$hash: algorithm, version, cost, salt and hash, so verification needs nothing else.

How many guesses is a password worth?

If a password of length $L$ is chosen uniformly at random from an alphabet of $N$ symbols, an attacker needs on average half of $N^{L}$ guesses, and the password carries

H = L \log_{2} N bits

of entropy. Eight random lowercase letters give $8 \log_{2} 26 \approx 37.6$ bits; twelve random characters from the 94 printable ASCII symbols give $78.7$ bits. But people do not choose uniformly: they choose words, names, dates and patterns, with a capital at the start and a digit at the end. Attackers' tools (Hashcat, John the Ripper) start with leaked lists like RockYou's and apply mangling rules, and real passwords fall far faster than their length suggests. Randall Munroe's 2011 comic “correct horse battery staple” made the point: four random common words (about 44 bits) beat a short password with clever substitutions.

An upper bound on the strength of a password, assuming its characters were chosen at random, and the average time one high-end GPU would need to find it depending on how the server stored it. The speeds are rough public benchmarks, to show orders of magnitude: the storage choice moves the answer by eight orders of magnitude, from seconds to centuries.

NIST's guidelines (SP 800-63B, 2017) changed the official advice accordingly: long passphrases rather than composition rules, no forced periodic changes, and checking new passwords against lists of breached ones.

Slow on purpose: PBKDF2

A fast hash is a feature for files and a flaw for passwords: a GPU computes billions of SHA-256 per second. The fix is key stretching: iterate the function many times, so that one guess costs the attacker as much as one login costs the server, which can afford a few hundred milliseconds. PBKDF2 (RSA Laboratories' PKCS #5 v2.0, 2000; RFC 8018) iterates HMAC $c$ times:

U_{1} = {HMAC}_{P} (S ‖ INT (i)), U_{j} = {HMAC}_{P} (U_{j - 1}), T_{i} = U_{1} \oplus U_{2} \oplus \dots \oplus U_{c} .

OWASP recommended 600,000 iterations of HMAC-SHA-256 in 2023. PBKDF2 protects Wi-Fi passwords (WPA2, with 4,096 iterations), password managers and full-disk encryption, and it is approved by FIPS.

Real PBKDF2-HMAC-SHA256, computed by your browser's WebCrypto. Choose the number of iterations and derive a key: the time it takes here is the cost of one guess on this device. A GPU is much faster, but every iteration multiplies its work just the same.

bcrypt

In 1999 Niels Provos and David Mazières, for OpenBSD, built bcrypt on Blowfish's expensive key setup (chapter 04), repeated $2^{cost}$ times, so the cost grows exponentially with one parameter that can be raised as hardware improves. bcrypt uses a little memory (4 KB of S-boxes that change constantly), which already hurts GPUs, and after twenty-five years it is still a good choice. Its one trap: only the first 72 bytes of the password are used; the desktop app refuses longer ones instead of silently truncating them.

Memory-hard functions: scrypt

Attackers do not use CPUs: they use GPUs and, for the most valuable targets, custom chips, which have thousands of cores but little memory per core. Colin Percival's scrypt (2009, for his backup service Tarsnap) fills a large buffer with pseudorandom data and then reads it back in a data-dependent order, so it cannot be computed quickly without the whole buffer in memory.

Idea (memory-hardness)

The cost of an attacker's hardware is roughly the area of the chip times the time it is used. A function that needs memory $M$ for time $T$ , and cannot be computed with much less memory without a large slowdown, costs about $M \times T$ per guess. Raising $M$ makes every parallel core of the attacker expensive, not just slower.

With the parameters $N = 2^{17}$ , $r = 8$ , scrypt needs 128 MiB per guess. Litecoin adopted it as proof of work in 2011, which promptly produced scrypt ASICs: memory-hardness raises the cost but does not make dedicated hardware impossible.

Argon2: the competition's winner

As with AES and SHA-3, the community held an open contest: the Password Hashing Competition (2013–2015) received 24 candidates and chose Argon2, by Alex Biryukov, Daniel Dinu and Dmitry Khovratovich of the University of Luxembourg. It has three parameters: memory (in KiB), passes over the memory, and parallel lanes. Its hybrid variant Argon2id starts with data-independent memory access (resisting side-channel attacks) and continues with data-dependent access (resisting time–memory trade-offs); it was standardised in RFC 9106 (2021). OWASP's minimum is 19 MiB, two passes and one lane, the desktop app's default; raise the memory if your server can afford it.

Encrypting with a password

The same functions turn a password into an encryption key. The desktop app's “AES-GCM + Argon2id” does it the modern way: a random 16-byte salt, Argon2id to derive a 256-bit key, and AES-GCM with a random nonce, so that a wrong password or a modified ciphertext is detected. The output carries everything needed except the password: a version byte, the salt, the nonce and the ciphertext with its tag.

cryptoKit 1.0 and Jasypt

The first version of cryptoKit (2022) offered password-based encryption through the Jasypt library: PBEWithHMACSHA512AndAES_256, which is PBKDF2 with HMAC-SHA-512, 1,000 iterations, a 16-byte salt and AES-256 in CBC mode. In 2022 that iteration count was already six hundred times below the recommendation, and the scheme has no authentication: a wrong password usually shows up only as a padding error. Version 2 keeps it, reimplemented with the JDK alone and tested both ways against Jasypt, so that old ciphertexts can still be decrypted; for new data, use AES-GCM + Argon2id.

§Never store the password

§Salt

§How many guesses is a password worth?

§Slow on purpose: PBKDF2

§bcrypt

§Memory-hard functions: scrypt

§Argon2: the competition's winner

§Encrypting with a password

§cryptoKit 1.0 and Jasypt

§Further reading