Hash functions explained
When you download software and compare a checksum, log in with a password, sign a document or add a block to Bitcoin, a hash function is at work. It turns any amount of data into a short fingerprint of fixed size, the digest, in a way that cannot be undone or forged. The idea is simple, yet the demands on a good hash are strict, and two of the most widely used ones, MD5 and SHA-1, did not survive them.
A fingerprint for data
A hash function takes an input of any length and returns a digest of a fixed length: 256 bits for SHA-256, written as 64 hexadecimal digits. The same input always gives the same digest, so the digest can stand for the data. If two files have the same SHA-256 digest you can be sure they are identical, and if one bit of a download was damaged its digest no longer matches the one the publisher listed. Because there are far more possible inputs than digests, many inputs must share each digest; a good hash simply makes it impossible to find any of them.
Three promises
A cryptographic hash makes three promises. Preimage resistance: given a digest, you cannot find an input that produces it. Second-preimage resistance: given an input, you cannot find another input with the same digest. Collision resistance: you cannot find any two inputs with the same digest. For an ideal hash with n bits the best attacks are guessing: about 2ⁿ tries for a preimage and about 2ⁿᐟ² for a collision. A hash is called broken when someone finds a way that is much faster than that.
The avalanche effect
Change one bit of the input and each bit of the digest should flip with a chance of one half, independently of the others. Then a small change in the message gives a digest that looks completely unrelated, and the digest betrays nothing about which part of the input changed. SHA-256 achieves this by running 64 rounds that rotate, add and combine its eight 32-bit words, so that within a few rounds every input bit has influenced every word. A simple sum of the bytes, by contrast, changes by exactly the amount the input changed, so it gives everything away.
Inside SHA-256
SHA-256 first pads the message: it appends a 1 bit, zeros and the length of the message, until the total is a multiple of 512 bits. Then it processes the message 512 bits at a time. Each block is stretched into 64 words, which are mixed into a state of eight 32-bit words, starting from fixed values taken from the square roots of the first eight primes. The state after the last block is the digest. This chained design, named after Ralph Merkle and Ivan Damgård, is shared by MD5, SHA-1 and SHA-512; the newer SHA-3, standardised in 2015, uses a different construction called a sponge.
The birthday attack
In a group of 23 people the chance that two share a birthday is just over one half, although the year has 365 days, because what matters is the number of pairs, which grows with the square of the group. Collisions in a hash follow the same rule. Among 2ᵏ possible digests, a collision is expected after about √(π/2 · 2ᵏ) random inputs. For 32 bits that is about 82,000 inputs, done in moments; for 128 bits it is about 2⁶⁴, which is within reach of large computing efforts. That is why MD5's 128 bits were never generous, and why SHA-256 doubles the length to give a security of 128 bits.
MD5 and SHA-1: broken
Ron Rivest designed MD5 in 1991, and the NSA designed SHA-1, published in 1995. In 2004 Xiaoyun Wang and her colleagues showed how to make MD5 collisions quickly, and in 2008 researchers used them to forge a certificate that web browsers trusted. The Flame espionage software of 2012 used an MD5 collision to pass as a Microsoft update. SHA-1 fell in 2017, when Google and CWI Amsterdam published two different PDF files with the same SHA-1 digest, after about 2⁶³ computations. Both are still fine for spotting accidental errors, but not for anything an attacker might target.
Where hashes are used
Digital signatures sign the hash of a document rather than the document itself. Git names every file and commit by its hash, and Bitcoin miners search for block headers whose double SHA-256 hash starts with a long run of zeros. Websites should never store passwords, only a hash of them; but because people choose short passwords, that hash must be slow and salted, with methods such as bcrypt, scrypt or Argon2, so that guessing becomes expensive. Checksums like CRC-32, used in ZIP files, PNG images and Ethernet, are hashes too, built to catch noise rather than attackers.
Explore it
Open the hash function playground to hash your own text with SHA-256, SHA-512, SHA-1, MD5, CRC-32 and a toy sum of bytes. Change one character and count the flipped bits, run the avalanche test over a thousand one-bit changes to see the bell curve around half the digest, and find real collisions on the first 8 to 32 bits of a digest to watch the birthday attack at work.
Frequently asked questions
Is hashing the same as encryption?
No. Encryption is meant to be undone by whoever holds the key; hashing has no key and cannot be undone by anyone. Encryption keeps a message secret, while a hash only gives a fingerprint that lets you check a message you already have.
How long would it take to find a SHA-256 collision?
With the birthday attack, about 2¹²⁸ hashes, a number with 39 digits. Even if every computer on Earth did nothing else, it would take vastly longer than the age of the universe. No shortcut is known.
Why do two hashes of the same text never differ?
A hash function is deterministic: it has no randomness and no key, so the same bytes always give the same digest. Small differences you cannot see, such as a trailing space, a different line ending or another Unicode form of an accented letter, do give a different digest.
What is a salt?
A random value stored next to a password hash and mixed into it. Two users with the same password then get different hashes, and an attacker cannot use one precomputed table of common passwords for every account.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Open the hash function playground