Password hashing, from crypt to bcrypt to Argon2

Ken Thompson’s password is p/q2-q4!. It’s a chess opening in descriptive notation, pawn from queen’s 2 to queen’s 4, which is about the most Ken Thompson password imaginable from one of the two people who built Belle, the chess machine.

The story came out a couple of weeks ago. Leah Neukirchen found an /etc/passwd file in a copy of the BSD 3 source tree back in 2014, full of hashes belonging to the people who built Unix, and cracked most of them. Dennis Ritchie’s was dmac, Brian Kernighan’s was /.,/.,, Stephen Bourne’s was bourne. A handful didn’t fall, Ken’s included, even after she’d exhausted every combination of lowercase letters and digits. She raised it on the Unix Heritage Society mailing list this month, and Nigel Williams replied with the answer. His note said it took more than four days on an AMD Vega 64 running hashcat at about 930 million guesses a second.

Which is a fun bit of history, and also a pretty good illustration of the whole problem. That hash was state of the art when it was made. It was also designed, explicitly, to be slow. And one consumer graphics card does nearly a billion of them a second today.

1979: crypt, salt, and slowness on purpose

The design comes from a 1979 paper by Robert Morris and Ken Thompson, “Password Security: A Case History”, which is short and still worth reading. Early Unix stored passwords in the clear, then moved to an encrypted form, and the paper describes how they made it harder to attack. Two ideas from it are still the foundation of everything since.

First, the password isn’t decrypted to check it. The system uses the password itself as a key, with DES, to encrypt a block of zeros, and stores the result. To check a login you do the same thing again and compare. There’s nothing to decrypt; the only way back is to guess.

Second, they slowed it down on purpose. Instead of encrypting once, crypt runs the DES encryption 25 times. And they added a salt, 12 random bits chosen when the password is set and stored next to the hash, that tweaks the DES algorithm itself. The salt means that two users with the same password get different hashes, and more importantly that an attacker can’t precompute one big table of hashes for common passwords and look everyone up in it. With 4,096 possible salts, they’d need 4,096 tables. The modified DES also meant you couldn’t use off-the-shelf DES hardware to speed things up.

Both of those ideas were right. What’s changed is the arithmetic. Crypt only uses the first 8 characters of the password, so the whole keyspace for 8 printable ASCII characters is 95⁸, about 6.6 × 10¹⁵. At 930 million a second that’s 82 days for one hash, on one card. Leah’s lowercase-and-digits search, 36⁸ or about 2.8 × 10¹², takes under an hour at that speed. Williams’s four-plus days is about 3 × 10¹⁴ guesses, a few percent of the full space, so I assume he used a smarter set of characters than “everything”. I don’t know what it was.

The fast-hash detour

Then, for a couple of decades, a lot of the industry forgot the slow part. Web apps in the 2000s commonly stored md5(password) or sha1(password), sometimes with a salt, often without. When LinkedIn’s 6.5 million password hashes leaked in 2012, they were unsalted SHA-1. A modern GPU computes general-purpose hashes like MD5 and SHA-1 in the billions per second, and those functions are designed to be fast, which is exactly the property you don’t want.

I wrote about how hash tables work a while ago, and the hash functions there are judged by how quickly they spread keys around. A password hash is the opposite tool with the same name. You compute it once per login, so you can afford for it to take a tenth of a second. The attacker computes it once per guess, billions of times, so every extra millisecond you spend is a millisecond multiplied by billions for them.

Salting alone doesn’t fix this. A salt stops precomputation and forces the attacker to attack each user separately, which matters a lot when there are millions of users, but it doesn’t make a single guess any slower. If your hashes leak and one of your users picked Summer2019!, a fast salted hash still falls in seconds.

Making it slow again

md5crypt, which Poul-Henning Kamp wrote for FreeBSD in 1994, kept the Unix idea and just ran MD5 a thousand times. It was a good step at the time. The problem with a fixed count is that it’s fixed, and hardware isn’t. PHK himself said back in 2012 that it shouldn’t be used any more.

bcrypt, from Niels Provos and David Mazières at USENIX in 1999, fixed that. It’s built on Blowfish, which has an unusually expensive key setup, and bcrypt makes that setup deliberately more expensive still, with a cost parameter. The work is 2^cost, so every increment doubles it. Cost 10 is 1,024 rounds of the expensive part, cost 12 is 4,096. When hardware gets faster, you bump the number, and the cost is stored in the hash string itself, so old hashes keep verifying and you can rehash each user at their next login. Twenty years later it’s still a perfectly decent choice. Its one well-known gotcha is that it only looks at the first 72 bytes of the password, which almost never matters, unless you pre-hash with something that can output a zero byte, or someone uses an enormous passphrase.

PBKDF2 (RFC 2898, 2000) is the same idea expressed generically: run HMAC with your favorite hash N times. It’s the one in most standards, and it’s what .NET gives you out of the box. Back in my MVP days, Rfc2898DeriveBytes was the class I’d point people to when they asked how to store passwords in ASP.NET, and its default of 1,000 iterations of SHA-1 was reasonable-ish in 2005. It’s not now. ASP.NET Identity’s current hasher uses PBKDF2 with HMAC-SHA256 and 10,000 iterations, which is better, and you can turn it up.

The GPU problem, and memory

The trouble with all of these is that they cost time but almost no memory, and that’s precisely the shape of work a GPU is good at. Thousands of small cores, each happily running its own copy of the hash on a different guess. A defender has one CPU that needs to do one hash in 100ms. An attacker has thousands of cores that each need a few kilobytes.

Colin Percival’s scrypt, from 2009, attacks that asymmetry. It requires a large block of memory, megabytes, and accesses it in a pattern that can’t easily be traded away for more computation. Your server can spare 16MB for 100ms per login. A GPU with thousands of cores can’t give each of them 16MB, so the attacker’s parallelism collapses. It’s the reason a lot of cryptocurrencies picked it for mining, too, though the ASICs eventually caught up there.

Argon2 is the current answer. It won the Password Hashing Competition in 2015, a multi-year open process that looked a lot like the AES and SHA-3 competitions, and it has separate knobs for time, memory and parallelism. There are three variants, and Argon2id, a hybrid of the other two, is the one people recommend for password hashing. It’s in libsodium, and PHP’s built-in password_hash has supported Argon2i since 7.2 and Argon2id since 7.3.

What I’d actually do

On a new system today: Argon2id from a well-maintained library, with memory and iteration settings tuned so a login hash takes something like 100–250ms on your production hardware. If Argon2 isn’t available in your stack, bcrypt at cost 11 or 12 is fine, and so is PBKDF2 with a six-figure iteration count if you’re stuck with it for compliance reasons. Don’t write your own. Store the parameters with the hash so you can raise them later, and actually raise them later.

The part people forget is the migration. If you have an old table of SHA-1 or MD5 hashes, you don’t need users’ passwords to upgrade: wrap the old hash, so the stored value becomes bcrypt(sha1(password)), and mark those rows. At the next login, verify, then rehash the plain password properly. Within a few months most active users are on the new scheme and the old rows are protected by bcrypt anyway.

None of this would have saved Ken’s password from 40 years of hardware improvements, because the speed of crypt was fixed in 1979. What would have helped is the knob. I’d like to think that if bcrypt had been available in 1979, someone would have been turning it up every few years. More likely, if experience is any guide, it would have been set once and left alone.