About Hash Mill
A hash function takes any message, a word or a whole film, and minces it into a short fixed-size number called a digest. The same message always gives the same digest. Change anything and the digest looks completely different. And there is no way to turn the mince back into the message. The word is the same as the one on a pub menu: "hash" comes from the French hacher, to chop.
MINCE: type, or open a file. Each digest in the ledger updates as you type. A file is read in the tab, a piece at a time, and never leaves your computer; only its digests are kept, and only until you clear them. The buttons above the tray choose which digest comes out on it.
AVALANCHE: edit the changed copy, or pick one of its bits. The grid shows the output bits, with a red cross on every one that flipped. RUN repeats it on random messages and draws how many bits flipped each time against the Expected bell. Try the tiny hash to see what a bad one looks like.
INSIDE SHA-256: the real working for a message that fits one block. STEP, BACK or START (then PAUSE and RESUME) through the 64 rounds, or use ← and → and Space. The values are the real ones; the finished digest is the one the MINCE tab gives.
COLLISIONS: keep only the first few bits of SHA-256 and search for inputs that match, either any two (a collision) or a fixed target. It really does the hashing, in a background worker. The page's own measured speed then says how long the full 256 bits would take.
USES: comparing two files; a small dictionary attack, really run in the page, on the same made-up passwords stored three ways; and a proof-of-work search.
R runs whatever the current tab runs. Nothing you type goes into a link unless you tick the box on MINCE, and that never covers files.
THE STORY
Hashing began as a filing trick. Hans Peter Luhn of IBM wrote an internal memo in 1953 that is usually taken as the start of it: chop a key up and use the pieces to choose a bucket, so you can find it again quickly. The cryptographic kind, where nobody should be able to find two messages with the same digest, came later.
Ron Rivest published MD5 in 1992 (RFC 1321). The US government's first SHA came in 1993 and was quickly revised to SHA-1 in 1995. Ralph Merkle and Ivan Damgård had each shown in 1989 how to build a hash for any length from a fixed-size mixing step, and all three in this app are built that way. SHA-256 belongs to the SHA-2 family, published by NIST in 2001 and designed by the NSA.
MD5 fell first. Xiaoyun Wang and her colleagues showed real collisions in 2004. In 2008 a team led by Alexander Sotirov and Marc Stevens used a collision to make a rogue certificate authority, using a cluster of 200 PlayStation 3s, and the Flame malware, found in 2012, faked a Microsoft signature the same way. An ordinary computer now finds an MD5 collision in seconds.
SHA-1 was weakened on paper by Wang, Yin and Yu in 2005 and broken in practice by SHAttered: in February 2017, CWI Amsterdam and Google published two different PDF files with the same SHA-1. It took about 263 computations (about 6,500 CPU years and 110 GPU years), against 280 for the plain birthday search. In 2020 Gaëtan Leurent and Thomas Peyrin made it worse with a chosen-prefix collision, where both messages can start however the attacker likes. NIST says to stop using SHA-1 by the end of 2030.
SHA-256 has no known collision. Published attacks only reach versions with some of the 64 rounds taken away.
Passwords. Robert Morris and Ken Thompson wrote up the salted Unix password scheme in 1979, with a 12-bit salt and a deliberately slowed function. The Python script password_cracker.py this app grew from is the attack it was built to hinder: read the salt from the stored hash, then try every word in a dictionary. bcrypt followed in 1999, PBKDF2 in 2000 and Argon2, which also demands a lot of memory, won the Password Hashing Competition in 2015.
Proof of work. Cynthia Dwork and Moni Naor proposed making a computer pay in effort to fight junk mail in 1992. Adam Back's Hashcash (1997) used leading zero bits of a hash, and Bitcoin (2008) uses the same idea with SHA-256 applied twice.
HOW IT WORKS
The hashes are written out here from the published standards, not borrowed from the browser, and checked against the published test values and against another implementation on thousands of random inputs. SHA-256 pads the message to a whole number of 64-byte blocks: the message, one 1 bit (the 80 byte), zeros, and the length. Each block is stretched from 16 words to 64 (the schedule), then 64 rounds stir eight registers using one schedule word and one constant each round. The constants aren't magic: they are the first 32 bits of the fractional parts of the cube roots of the first 64 primes, and the registers start from the square roots of the first 8. Numbers with nothing up their sleeve, as cryptographers say. The answer is added to the starting values, so the mixing can't simply be run backwards from the answer.
The tiny hash is h = h × 31 + next byte, kept to 16 bits, the sum Java uses for strings cut down to size. It's for showing the idea and for showing what goes wrong. "Aa" and "BB" clash because 65 × 31 + 97 = 66 × 31 + 66.
The birthday bound. With N possible values, the Expected number of random tries before any two match is about √(πN/2) + 2/3. That's why 23 people are enough for a shared birthday to be more likely than not, and why a hash of b bits gives only b/2 bits of protection against collisions. Finding a match for one fixed target has no such shortcut: Expected tries are N.
Simplifications. The search keeps every value it has seen in a table, which is fine up to 40 bits. Serious searches use tricks that need almost no memory, but take about the same number of tries. Each input in a search is the text "mince", a run number and a counter. The password demo uses PBKDF2 because SHA-256 is already here; a new system today would choose Argon2 or similar. A real attacker's graphics cards go far faster than this page but the ratios stay much the same, except that memory-hard functions hurt them more. Everything named in the password demo is made up, and the word list is a short one of the common sort.
FURTHER WATCHING AND READING