Hash functions

A hash function takes an input of any size and returns a fixed-size digest. The same input always gives the same digest. SHA-256 always returns 256 bits, written as 64 hex characters, whether the input is one byte or a 4 GB file.

The useful part is what happens when the input changes. A one-character edit gives a digest that looks unrelated to the old one.

Walking through it

Here are two inputs that differ by one period:

SHA-256("hello")  = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA-256("hello.") = 1589999b0ca6ef8814283026a9f166d51c70a910671c3d44049755f07f2eb910

Nothing in the second digest hints at the first. This is the avalanche effect. A secure hash spreads every input change across the whole output.

A secure hash has three properties:

1. Preimage resistance: given a digest, you can't find an input that produces it.
2. Second-preimage resistance: given one input, you can't find a different input with the same digest.
3. Collision resistance: you can't find any two inputs with the same digest.

Collision resistance is the weakest of the three because of the birthday paradox. For an n-bit hash, finding a specific preimage takes about 2^n tries. Finding some collision takes only about 2^(n/2). SHA-256 therefore gives about 128 bits of collision resistance, which is still far out of reach.

You meet hashes everywhere: Git commit IDs, Docker image digests, download checksums, Merkle trees in databases, and as the building block inside HMAC and signatures.

Never use MD5 or SHA-1 for security

MD5 (128 bits) has had practical collisions since 2004. In 2012, the Flame malware used an MD5 collision to forge a certificate that Windows Update trusted. SHA-1 (160 bits) fell in 2017, when Google and CWI Amsterdam published SHAttered: two different PDFs with the same SHA-1. In 2020, the SHA-1 is a Shambles team produced a chosen-prefix collision. That is worse, because the attacker picks both meaningful prefixes.

MD5 is fine as a checksum where nobody gains from a collision, such as a cache key or an ETag. If an attacker might want two inputs to collide, use SHA-256, SHA-3 or BLAKE2 and BLAKE3.

Common mistakes

• Using MD5 or SHA-1 anywhere an attacker could benefit from a collision.
• Hashing a secret together with a message to prove authenticity.
• Using a fast hash to store passwords. Passwords need a slow hash, covered in password hashing.

Check yourself

• Why does "hello." produce a digest unrelated to the digest of "hello"? Answer: the avalanche effect. A secure hash spreads any input change across all output bits.
• Why isn't sha256(secret + message) a safe MAC? Answer: length extension lets an attacker extend the message without knowing the secret. HMAC prevents this.

Key takeaways

• A hash maps any input to a fixed-size digest, and the same input always gives the same digest.
• A secure hash resists preimages and collisions. Collision resistance is the weakest, because of the birthday bound.
• MD5 and SHA-1 are broken for anything adversarial. Use SHA-256, SHA-3 or BLAKE3.
• Don't build authentication from a bare hash. Use HMAC.

Further learning

Next, see how a hash combined with a secret key becomes a message tag in HMAC and webhook signing.