PLATFORM18

Hash

CIPHER

WHEN

FROM

STATUS

The last train on the board is not a cipher at all. A hash function takes any message, a word or a whole library, and boils it down to a fingerprint of fixed size: for SHA-256, 256 bits, written as 64 hexadecimal digits. There is no key and no way back. That sounds useless for secrets, yet hashes hold much of modern security together: they check that files have not been tampered with, they sit inside every digital signature, and they are how sensible websites store your password.

The machine

The fingerprint machine

Type anything. The machine runs the real SHA-256, here in your browser, and shows the result twice: on 64 flaps, and on a panel of 256 lamps, one for each bit. Then change a single letter. A good hash is built so that any change, however small, scrambles the whole output: about half the lamps flip, and which ones is impossible to predict. This is called the avalanche effect.

Break it yourself

The leaked password file

A careless site stored its staff passwords as plain SHA-256 hashes, and the file has leaked. You cannot run the hashes backwards, but you can run guesses forwards: hash a likely password and see whether its fingerprint is in the file. That is a dictionary attack. Your dictionary is a notebook of the commonest passwords. One account was stored more carefully; see if you can tell why it resists.

ARRIVED · CIPHER CRACKED

The story

Ron Rivest, the R of RSA, designed MD5 in 1991; it was published as an internet standard in 1992 and became the hash everyone used. In 1993 the US National Security Agency designed SHA, the Secure Hash Algorithm, published by NIST, the national standards institute; a corrected version, SHA-1, followed in 1995. In 2001 NIST published a draft of the NSA's SHA-2 family, whose best-known member is SHA-256; it became a standard in 2002. The NSA is based at Fort Meade, Maryland, and NIST at Gaithersburg, also in Maryland: hence the departure point on the board.

Inside, SHA-256 chops the message into blocks of 512 bits and stirs each into a running state of eight 32-bit words, with 64 rounds of additions, rotations and bit mixing per block. The constants it uses are taken from the cube roots of the first 64 prime numbers, a way of showing that nobody hid a trapdoor in them.

Where hashes work

When you download software, the publisher can list its hash: if your copy hashes the same, it is the same file. A digital signature signs the hash of a document rather than the document. Bitcoin's ledger is a chain of blocks each carrying the SHA-256 hash of the one before, and "mining" means hashing over and over until the result happens to start with enough zeros.

And passwords. A site should never keep your password, only its hash; when you log in it hashes what you type and compares. Even then, people choose the same few passwords, so attackers hash huge lists of likely ones and look for matches, or build tables of them in advance. The defence is salt: a random string, different for every user and stored beside the hash, mixed in before hashing. Two users with the same password then get different hashes, and no table built in advance helps. Good systems also use deliberately slow password hashes such as bcrypt or Argon2, so that each guess costs real time.

How it was broken

A hash is "broken" when someone can find two different messages with the same fingerprint (a collision) faster than by blind luck. MD5 fell first: in 2004 Xiaoyun Wang and her colleagues showed how to make MD5 collisions in hours, and by 2008 researchers had used them to forge a web security certificate. SHA-1 lasted longer. In 2017 a team from Google and CWI Amsterdam published "SHAttered": two different PDF files with the same SHA-1 hash, at a cost of about nine quintillion SHA-1 computations.

SHA-256 still stands. No collision has ever been found, and the best attacks only manage reduced versions with fewer rounds. What falls, every week, are weak passwords stored without salt, exactly as in the puzzle above.