Hashing and Password Storage

A website can check a member's password at every sign-in without ever keeping a copy of it. What it keeps instead is a hash: a short, scrambled fingerprint of the password, computed by a fixed recipe. When the member signs in, it runs what was typed through the same recipe and compares fingerprints.

Here is SHA-256, a member of the SHA family, applied to two passwords that differ by one letter. Each output is written in hexadecimal, where every character stands for 4 bits.

nightrider   1402b5f2d3cd1686d5acbb215c5b1532b28208fd15b479aab1ca7abb865eb66d
nightriders  90e01f9b1fa63e14782cf292ae2dbe8f29cd7344cb2c69f04ca1aef51bc437ed

Count the characters in one output and work out how many bits SHA-256 produces.

Each output has 64 characters, and 64 times 4 is 256 bits, the number in the name. A whole novel run through SHA-256 would also come out as 64 characters. The two outputs share nothing you could use to guess that the inputs were nearly identical. Run nightrider through it again and the first line comes back exactly.

Fixed length has a consequence. SHA-256 has $2^{256}$ possible results, an enormous number but a finite one, while the texts it accepts vastly outnumber them. Somewhere, two texts share a result.

A small video game studio runs an online racing game with about 80,000 player accounts. Its sign-in server keeps a table with each player's name and password hash. At sign-in the server runs the typed password through the same function and checks the output against that player's row. Nobody at the studio, and nobody who copies the table, can read a password off it.

In June 2012, a file of about 6.5 million password hashes appeared on a Russian password-cracking forum, posted with a request for help cracking them. The file came from LinkedIn, which had hashed its members' passwords with SHA-1 and stored them, as in the studio's table, with nothing added. Within days, people working through the file had recovered a large share of the passwords.

A hash can't be run backward, so how were they recovered so quickly? And what would have been different if each account's password had been mixed with something unique before hashing? Think about both, then look at the figure.

Nobody ran a hash backward, and SHA-1's collision weakness played no part. The crackers hashed likely passwords, word lists and the passwords from earlier breaches, and looked for each result in the file. Without salt, one guess checked every account at once, because every member who chose the same password had the same hash, like kestrel and dune_rider in the top panel. With a different salt per account, as in the bottom panel, each guess costs a separate hash for every account, using that account's salt, and two members with the same password no longer look alike.

A far larger file from the same 2012 break-in, about 117 million LinkedIn email addresses and password hashes, was offered for sale in 2016. LinkedIn then made the owners of accounts from before 2012 that still had their old passwords choose new ones. The intruder, Yevgeniy Nikulin, had also broken into Dropbox and Formspring. He was arrested in Prague in 2016, sent to the United States, convicted by a jury in San Francisco in 2020, and sentenced to 88 months in prison.

The studio switches its sign-in server to salted hashes, made with bcrypt, a hash function built for passwords and deliberately slow. SHA-256 is designed to be fast, which suits checking files and suits an adversary testing guesses just as well. Bitcoin runs on SHA-256, and the machines built to mine it carry chips that compute SHA-256 and nothing else. One common model, the Antminer S9, has 189 of those chips and makes about 14 trillion hashes a second. Those chips can't test passwords, since they hash only Bitcoin's own data, but they show how fast SHA-256 runs on hardware built for it.

Each player gets a new random salt, stored beside the hash; the salt isn't a secret, and it doesn't need to be. Since nobody knows the old passwords, each player's new hash is made the next time that player signs in. The server checks the typed password against the old hash one last time, then stores a fresh salt and the new hash in its place. Accounts that haven't signed in after a few months get their passwords reset, so no unsalted row is left behind. Once every row is salted, a guess like nightrider has to be tried 80,000 separate times, once per salt, each try slowed on purpose, and finding it for one player says nothing about any other.