Passwords

Every website with a login has to check passwords, so it has to keep something that lets it check them. Sooner or later, many such sites lose their database to an attacker. This page is about what a site should keep, so that a leak gives away as little as possible, and how attackers get passwords out of a leak when the site got it wrong. Every figure runs in your browser, and nothing you type leaves it; even so, use made-up passwords, never real ones.

1 · Never store the password

The obvious way to check a password is to keep it, and compare. Then anyone who reads the database (an attacker, or someone working at the site) has every password, and since people reuse passwords, a leak from one site opens their accounts on others.

The fix is a hash function: a calculation that turns any input into a fixed-size fingerprint (here SHA-256, whose fingerprint is 256 bits, written as 64 hex digits). It’s easy to work out forwards, and as far as anyone knows, impossible to run backwards: given a hash, there’s no better way to find an input that gives it than guessing (more on Hash functions). So the site keeps only the hash. When someone logs in, it hashes what they typed and compares the hashes.

Sign up with a made-up password, then log in. The site stores only the hash of the password; to check a login it hashes what was typed and compares. Change one letter and the hash changes completely, so the stored hash gives no hint of how close a wrong guess was.

2 · Cracking a leaked table

A hash can’t be run backwards, but it can be run forwards as often as an attacker likes. With a leaked table of hashes, they hash guesses and look each one up: any match is a password. And people’s passwords are guessable: words, names, with a capital at the front and a digit or two on the end, because a site insisted.

Here’s a made-up site’s leaked table, and an attacker’s dictionary: the 611 different words in the first chapter of Alice’s Adventures in Wonderland, each tried 26 ways (as it is and with a capital letter, each followed by nothing, a digit, “123” or ”!”). That’s 15,886 guesses. Real attackers’ dictionaries hold billions of words and passwords from earlier leaks, and thousands of rules like these.

A leaked table: twelve users and the SHA-256 hash of each one’s (made-up) password. Run the dictionary: each guess is hashed once and looked up against the whole table. Ten of the twelve fall, every one with a single pass of 15,886 hashes (pinned in the tests), in a fraction of a second here. The two left are a random jumble of characters and four words joined together: no rule produces them. Two hashes are the same (highlighted): carol and grace chose the same password, and the table says so before anything is cracked.

Real leaks look like this. In 2012 a large social network’s table of passwords, stored as unsalted SHA-1 hashes, was posted online, and much of it was cracked within days.

3 · Salt

The table above gives away two things for free. Users with the same password have the same hash, so cracking one cracks both. And since everyone’s hash is just SHA-256 of their password, an attacker can hash a dictionary once, in advance, and look up every leaked table from every site in it ever after.

The fix is a salt: a random value made for each user when they sign up, stored next to the hash, and put in front of the password before hashing. The salt isn’t secret. It doesn’t need to be: it just makes every user’s hash a different function of their password.

The same twelve users and passwords, each with a salt (8 hex digits here; a real site uses 16 random bytes or more), and the hash of salt + password stored. Carol’s and grace’s hashes now differ. The same dictionary finds the same ten passwords, but each guess has to be hashed again with every user’s salt: 83,670 hashes this time, 5.3 times as many (pinned in the tests), and it would be twelve times as many if no password were found early. For a leak of a million users, it’s a million times the work.

Salt was there from early on: Unix’s password scheme, described by Robert Morris and Ken Thompson in 1979, added a 12-bit salt to each password for exactly these reasons.

Precomputed tables, and rainbow tables

Without salt, an attacker’s precomputing is limited only by storage. Hashing every possible password and keeping every hash takes as much storage as there are passwords. In 1980 Martin Hellman found a trade-off between time and memory, and Philippe Oechslin’s rainbow tables (2003) refined it: keep only a little of the work, and redo a little at lookup time.

A rainbow table is made of chains. Start from a password, hash it, then reduce the hash: turn it back into something that looks like a password (a different way at each step of the chain, hence “rainbow”). Hash that, reduce it, and so on. Keep only each chain’s first and last password. To look up a hash, reduce it and walk forward to the end of a chain; if that end is in the table, rebuild the chain from its start, and the password is the one just before the hash.

A rainbow table for 4-digit PINs (10,000 of them), hashed with SHA-256. Each chain hashes and reduces its way along; the table keeps only its start and end. With 400 chains of 50 steps, the chains pass through 7,635 of the 10,000 PINs, but only 199 pairs are kept (pinned in the tests): when two chains land on the same PIN at the same step, they run on together and end in the same place, and only one of them is kept. Look up a made-up PIN: when it’s in a kept chain, it’s found after at most a few thousand hashes, not 10,000; when it isn’t, the table can’t find it. Change the chains and their length, and watch what’s kept and what’s covered.

Rainbow tables were once a serious threat to systems that stored unsalted hashes: tables covering every short password were shared freely. A salt kills them: a table would have to be built for every salt, and each is used once.

4 · Slow on purpose

Salt makes the attacker work on each user separately, but each guess is still one fast hash. SHA-256 was designed to be fast, and a graphics card computes billions of them a second. For passwords, fast is the wrong goal. A site checks one password at a time, when someone logs in, and can spare a fraction of a second. An attacker needs billions of guesses, so a hash that takes a fraction of a second each makes their job billions of times longer.

PBKDF2 (Password-Based Key Derivation Function 2, published by RSA Laboratories and as RFC 2898 in 2000, now RFC 8018) makes a hash slow by doing it many times: an HMAC (a keyed hash) of the password, then of that result, and so on for a chosen number of iterations, all XORed together. The iteration count is stored with the salt, so a site can raise it as computers get faster. (The page’s own PBKDF2 matches the standard’s test vectors, and the browser’s own for 4,096 iterations; both checked in the tests.)

timing…

PBKDF2 with SHA-256, run by your browser’s own cryptography, at more and more iterations: the time for one guess, how many guesses a second that allows, and how long the dictionary from section 2 would take against the twelve salted users. Past the first thousand or so, each iteration costs about the same, so the time grows in step with the count (at a single iteration, most of the time is the browser getting started).

The catch is that the attacker’s hardware is far better at this than the site’s. PBKDF2 needs almost no memory, so a graphics card can run thousands of guesses side by side, and chips built for the purpose more still. bcrypt (Niels Provos and David Mazières, 1999) helped a little by needing a few kilobytes of memory per guess.

5 · Memory-hard

The way to slow down a graphics card is to make each guess need a lot of memory. A site’s server has plenty of memory for one guess at a time; a graphics card running thousands of guesses side by side doesn’t have thousands of times as much, and memory is far more expensive to put on a purpose-built chip than arithmetic is.

scrypt (Colin Percival, 2009) does this. It fills a large table, each entry the hash of the one before, then reads entries back in an order that depends on what it’s read so far, so it can’t know in advance which it will need. Keeping the whole table is cheapest. An attacker can keep only part of it and work the missing entries out again from the nearest one kept, but each missing entry they read costs extra hashes.

A small memory-hard function in scrypt’s style (not scrypt itself): a table of SHA-256 hashes, each from the one before, then as many reads at places chosen by the running result. The site keeps the whole table. The attacker keeps one entry in so many, and works out the others when a read needs them. For a table of 4,096 entries: the whole table takes 8,193 hashes; keeping half of it, 10,208; a quarter, 14,238; one entry in 16, 39,058 (pinned in the tests). Both get the same answer. Less memory, more work: there’s no cheap way round it.

Argon2, which won the open Password Hashing Competition in 2015 and is standardised as RFC 9106 (2021), builds on the same idea, with settings for time, memory and the number of processor cores to use. It’s what’s recommended for new systems today (by OWASP’s guidance, for example), with scrypt and bcrypt as acceptable alternatives.

6 · Choosing a password

All of this is the site’s responsibility. Your part is to choose a password that no dictionary contains, and to use a different one on every site, so a leak from one can’t open the others.

How hard a password is to guess is its entropy: how many it could have been, as bits (see Randomness). That counts only what was chosen at random. A word from the chapter with a rule applied is one of 15,886, however clever it looks: 14 bits. Random characters and random words are another matter.

How long it would take to try every password of each kind, at the speed of this page’s SHA-256 (fast), and of PBKDF2 with 600,000 iterations (slow), both measured here. Turn up the attacker’s hardware: a real attacker has many fast processors, and the times fall in proportion. Compare the two columns: the slow hash multiplies every row by the same large factor (the ratio of the two speeds, below). This page’s SHA-256 is written to be read, not to be fast; well-written code runs many times faster, which would make the fast column shorter still and the gap between the columns wider. Four random words from the chapter (37.0 bits) are about as hard to guess as eight random letters (37.6); six words (55.5) are harder still, though not as hard as ten random characters (65.5).

So a password manager, making a long random password for every site, is the best answer. Where a password has to be remembered, several words chosen at random (by dice or a program, not by you) are as strong as a jumble of characters and far easier to type. Current guidance (NIST’s SP 800-63B, for example) says the same: length matters more than mixing in symbols, and sites should check new passwords against lists of leaked ones rather than demand a capital and a digit.

Summary

A site should never store passwords, only their hashes, checked by hashing what’s typed.
A leaked table of fast hashes falls to a dictionary attack: hash likely passwords and look them up.
A random salt per user makes every hash different: no shared hashes, no precomputed or rainbow tables, and each user must be attacked separately.
Slow hashes (PBKDF2’s iterations) multiply the attacker’s work; memory-hard ones (scrypt, Argon2) defeat their graphics cards and custom chips.
A password’s strength is how much of it was chosen at random: random words or a password manager, and a different password for every site.