The Black Chamber RU

Lesson №10 1979–2017 20 min

Hashes: fingerprints of data

A function that turns anything into a short string and won’t let you go back. Passwords, downloads and signatures all rest on it. Here’s how it gets fooled, and how people defend it.

In this lesson

  • what a hash is and how it differs from a cipher
  • the avalanche effect: one letter flips half the bits
  • how passwords are stored, and how dictionaries crack them
  • what salt is for, and what rainbow tables are
  • what a collision is, and why MD5 and SHA-1 are broken

June 2012. A file turns up on a hackers’ forum: six and a half million lines, each of them forty hexadecimal characters. They are the password hashes of LinkedIn users. The passwords themselves aren’t in the file; the site never stored them. And yet within days a large share of them had been worked out and posted in plain text.

How do you “decrypt” something that was never encrypted? Why did the site keep hashes instead of passwords? And what did it get wrong? To answer, let’s meet the most useful function in cryptography, the one that hides nothing and only leaves a fingerprint.

A fingerprint of data

A hash function takes any data at all (a word, a book, a ten-gigabyte film) and returns a string of fixed length, called a hash. The SHA-256 function, for example, always gives 256 bits, which is 64 hexadecimal characters. Here’s the hash of the word “password”:

5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8

A good hash function has four properties:

  • Deterministic. The same data always gives the same hash, on any computer, on any day.
  • One-way. You can’t get the data back from the hash, any more than you can turn a sausage back into a pig.
  • Avalanche. Change a single input bit and the hash becomes completely different.
  • Collision-resistant. It’s practically impossible to find two different inputs with the same hash.

A hash is not a cipher. A cipher has a key, and with the key everything comes back. A hash has no key, and nothing comes back. It isn’t there to hide things but to recognise them. Download a program, compare its hash with the one printed on the author’s site: if they match, not a single byte was damaged or swapped on the way. Version control systems like Git, digital signatures and blockchains are all built on hashes. You can hash anything in the hash generator.

The avalanche effect

The most striking property is the avalanche. Hashes of similar texts aren’t similar at all. Change “9” to “8” and about half of the 256 bits flip, with no way to tell in advance which ones.

The square is the 256 bits of the second text’s hash: dark cells are ones, light cells zeros. Red marks the bits that differ from the first text’s hash. “300 random edits” changes one letter three hundred times and draws a histogram.

Why exactly half? Because that’s what randomness does. If a hash looks like a random string, each bit of the new hash matches the old one with probability ½, like a coin. Toss 256 coins and about 128 land heads. If far fewer flipped (say 10 bits), the hash would reveal how similar the inputs were, and that would be a foothold for an attacker.

The SHA-256 of “cat” starts with certain characters. What can you say about the SHA-256 of “cot”?

In a good hash every output bit depends on every input bit. Change one letter and everything is reshuffled: the hashes of “cat” and “cot” are as unlike as those of “cat” and “War and Peace”.

How passwords are stored

You sign up to a site and choose a password. Storing it as it is would be dangerous: anyone who reaches the database (an intruder, a dishonest employee, someone who steals a backup) would see everybody’s password. And people, sadly, use the same password everywhere.

So the site stores not the password but its hash. When you log in, it hashes what you typed and compares that with the stored hash. If they match, the password is right. The site doesn’t know your password and can’t find it out: the hash is one-way. If the database leaks, only hashes leak.

But one-way doesn’t mean unguessable. An attacker can’t go from the hash to the password, but can go from a password to its hash: take a likely password, hash it, compare. And people’s passwords are astonishingly alike: “123456”, “qwerty” and “password” have topped the most-common lists for years. Hash a dictionary of popular passwords once, and from then on you simply look up ready-made hashes in any leaked database.

First hash the dictionary, then compare it with the leak. Then switch to “Salted” and try again. Keep an eye on the hash counter.

One more line turned up in the leaked database, unsalted. The director’s password is one of the dictionary words above. Hash the dictionary and find which word gave this hash:

000c285457fc971f862a79b786476c78812c8897063c6fa9c045f579a3b2d63f

Press “Hash the dictionary” in the widget. The first ten characters of each word’s hash appear under it.

Look for the word whose hash starts with 000c2854.

It’s monkey: its SHA-256 starts with 000c285457. Nothing had to be “decrypted” to find it. We hashed a couple of dozen words and compared.

Real cracking dictionaries hold billions of entries: every password from past leaks, names, dates, words with digits on the end. A graphics card computes billions of SHA-256 hashes a second. So a password that anyone has ever thought of before you is close to worthless.

Precomputing hashes for a vast number of passwords makes a gigantic table. In 2003 Philippe Oechslin showed how to store such a table hundreds of times more compactly, at the price of a little computation per lookup. These became known as rainbow tables. You can download them ready-made for popular hash functions and find a password from its hash almost instantly.

That’s what happened to LinkedIn: the passwords were stored as plain SHA-1 hashes with no protection against precomputed tables. Every simple password was found by looking it up in work already done.

Salt

The defence against precomputed tables is wonderfully simple. Before hashing, each user’s password gets a salt: a random string, different for everyone. The database stores the salt and the hash of salt + password. The salt isn’t secret; it sits right beside the hash. But it does two important things.

First, precomputed tables become useless: nobody hashed “7f3a” + “qwerty” in advance. Second, two users with the same password now have different hashes, so the attacker has to run the dictionary separately for each one. Unix already did this in the late 1970s: Robert Morris and Ken Thompson described it in their 1979 paper on password security.

A leaked database holds 1,000 users, each with their own salt. The attacker has a dictionary of 10,000 passwords. How many hashes must be computed to check the whole dictionary against every user? (Without salt, 10,000 would do.)

Each user has their own salt, so the hash of “salt + password” for one user is no use for another.

For each of the 1,000 users the 10,000 words must be run afresh: 1,000 × 10,000 = 10,000,000 hashes. The salt multiplied the work by exactly the number of users in the database.

Note that salt doesn’t save a weak password: “123456” is found on the first try, salt or no salt. What it stops is the wholesale attack, one table breaking millions of users at once.

The second trick is to make each guess expensive. SHA-256 was built to be fast, and that’s bad news for passwords: a fast hash means fast guessing. So deliberately slow functions were designed for passwords: bcrypt (1999), scrypt (2009) and Argon2 (winner of a 2015 competition). One check takes, say, a tenth of a second. A user logging in won’t notice; an attacker with a billion-word dictionary is stuck for years. The AES password encryption tool does the same with PBKDF2, which runs SHA-256 250,000 times.

A hash isn’t decrypted; it’s guessed: hash likely passwords and compare. Salt forces the guessing to be done for each user separately, and a slow hash makes each guess costly. And a long random password can only be found by honest brute force, which takes longer than a lifetime.

Collisions and birthdays

SHA-256 has 2256 possible hashes, a 78-digit number. But there are infinitely many possible inputs. So some different inputs must share a hash. Such a match is called a collision. Every hash function has them; the only question is whether anyone can find one.

The birthday problem helps here. How many people do you need for a better-than-even chance that two share a birthday? Not 183, just 23. We’re looking for a match between any two, and 23 people already make 253 pairs. For hashes the rule is: a hash of k bits gives up a collision after roughly 2k/2 tries, the square root of the number of possible hashes.

Keep the first 16, 20 or 24 bits of SHA-256 and hunt for two messages whose hashes start the same. Each extra four bits makes the work about four times longer, not sixteen: that’s the square root at work.

For full SHA-256 that’s 2128 tries, more than all the computers on Earth could manage in the age of the universe. Older functions, though, turned out to have shortcuts far faster than brute force.

  • MD5 (1991, 128 bits). In 2004 a team led by the Chinese mathematician Wang Xiaoyun showed how to build collisions quickly. Today an ordinary laptop finds them in seconds. In 2012 the Flame malware used an MD5 collision to forge a Microsoft digital certificate.
  • SHA-1 (160 bits). In 2017 Google and the Dutch institute CWI published two different PDF files with the same SHA-1. The project was called SHAttered.
  • SHA-256 and its relatives. No collision has ever been found, and they’re used everywhere.

What does a collision give a crook? Picture this: you sign the hash of a harmless contract, while the crook has a second contract ready with the same hash. Your signature fits both. That’s why a broken hash can no longer be trusted for signatures and certificates, even if no password can be recovered from it.

What does “MD5 is broken” mean?

It’s broken in the collision sense: there are ways to build two different inputs with the same MD5 far faster than brute force. It still catches accidental errors, but it’s no good for signatures or protection against forgery.

What to take with you

  • A hash is a fixed-length fingerprint of data. It can’t be reversed, and any edit changes it entirely (the avalanche: about half the bits).
  • Sites store password hashes, not passwords. But hashes get guessed: hash a dictionary and compare. A simple password falls instantly.
  • Salt is a random string per user. It defeats precomputed and rainbow tables and forces a separate run for each user. Slow hashes (bcrypt, scrypt, Argon2) make every guess costly.
  • Every hash has collisions, but in a good one you can’t find them: k bits take about 2k/2 tries. MD5 and SHA-1 are broken; SHA-256 isn’t.

Ciphers and hashes have so far shared one problem: how do you agree on a secret with someone you’ve never met? For thousands of years the answer was “you can’t”. Next: public keys →

Tools for this lesson

Everything from the lesson, working: paste your own text.