The previous post introduced cryptography's three tools. This post goes into the first and most used of them: the hash function. Git names every commit with one. Browsers check certificates with one. This site uses one to put ?v=... after CSS file names, to know whether a Vietnamese post has changed since its translation (source_hash), and to sign sign-in sessions (HMAC).
Roadmap: what a hash function is and its three properties, the avalanche effect (measured), the history of MD5, SHA-1 and today's functions, speed (measured), collisions and the birthday paradox (measured), the length-extension attack and HMAC (done for real), comparisons safe against timing attacks (measured), then where hashing shows up in practice. Measured with Python 3.12 on a real machine.
What a hash function is
A cryptographic hash function takes data of any length and returns a string of fixed length. SHA-256 returns 256 bits (32 bytes, 64 hex characters):
sha256("viet.sarl") = b1bd86a146ce47b7af5cf5d595a29d2a8b35182c9da0d1350522a523ff40c80b
sha256("viet.sarm") = 0c0dee002f3a4b9679b41a4fd0284aa3b21c102a6ded28728d9433cc2f904387
Change the last letter and the result is completely different. A cryptographic hash function (unlike the hash behind a Python dict) must have three properties:
| Property | Means | If lost |
|---|---|---|
| One-way (preimage resistance) | Given a hash, you can't find the input | Passwords leak from their hashes |
| Second preimage resistance | Given a file, you can't make another with the same hash | A downloaded file is swapped for malware that still passes the check |
| Collision resistance | You can't find any two inputs with the same hash | Forged certificates, forged signatures |
Note the word "can't": collisions always exist (infinitely many inputs map onto 2²⁵⁶ outputs), it's just that nobody can find one in reasonable time.
The avalanche effect
A good hash function makes every input bit affect every output bit, as if the output were random. Measure it: take 2,000 random 32-byte messages, flip 1 bit anywhere, and count how many bits differ between the two SHA-256 hashes:
avalanche mean bits changed /256: 127.919 min 99 max 153
On average 127.9 out of 256 bits, exactly half, like a coin toss for each bit. There's no way to look at a hash and guess "the input is close to that one". That's why a hash works as a fingerprint: two files that differ by even one bit have completely different fingerprints.
MD5, SHA-1 and the functions still in use
| Function | Year | Output | Status |
|---|---|---|---|
| MD5 | 1992 | 128 bits | Broken. Since 2006, finding a collision on a laptop takes under a minute |
| SHA-1 | 1995 | 160 bits | Broken. First real collision in 2017 (SHAttered: two different PDF files with the same hash) |
| SHA-256, SHA-512 (the SHA-2 family) | 2001 | 256 / 512 bits | Safe, the most used |
| SHA-3 | 2015 | 224–512 bits | Safe, built entirely differently from SHA-2 (in case SHA-2 has problems) |
| BLAKE2, BLAKE3 | 2012 / 2020 | configurable | Safe, fast in software |
MD5 collisions have been used in the wild: in 2008, researchers made a fake CA certificate thanks to an MD5 collision, and the Flame malware (2012) forged Windows update signatures the same way. Git originally used SHA-1, and after SHAttered it moved to a SHA-1 variant with collision detection, and built a repository format that uses SHA-256.
MD5 is still fine where there's no attacker, such as checking whether a download was corrupted in transit. But there's no reason to pick it for a new project, especially as it's also slower than SHA-256.
Speed
Hashing 64 MB of random data, best of three runs:
| Function | MB/second |
|---|---|
| MD5 | 957 |
| SHA-1 | 3,348 |
| SHA-256 | 3,350 |
| SHA-512 | 1,912 |
| SHA3-256 | 1,109 |
| BLAKE2b | 1,653 |
SHA-256 is the fastest here, 3.5 times faster than MD5. The reason isn't the algorithm: many CPUs today have dedicated instructions for SHA-256, just as they have dedicated instructions for AES. On a CPU without them the order is different: BLAKE2b and SHA-512 usually beat SHA-256. The lesson from the CPU post still holds: measure on the machine you run on, don't guess.
Three GB per second is far too fast for one job: storing passwords. Attackers hash just as fast. That's the topic of post 3.
Collisions and the birthday paradox
In a class of 23 people, the chance that two share a birthday is over 50%, even though a year has 365 days. The reason: you don't need someone matching one given day, just any two people matching each other, and the number of pairs grows with the square of the number of people.
Hash functions work the same way: a hash with an n-bit output needs about 2^(n/2) attempts to hit a collision, not 2^n. Measure it by truncating SHA-256 to 32 bits and hashing random data until two results match:
32-bit collision after 32539 tries
32-bit collision after 102205 tries
32-bit collision after 132589 tries
Theory predicts about √(π/2 · 2³²) ≈ 82,000 attempts. The three runs sit around that number, nowhere near 4.3 billion (2³²). The whole experiment takes under a second.
Applied to real functions: 128-bit MD5 only had 64 bits of "collision resistance" even before it was broken, weak from the start. SHA-256 gives 128 bits, i.e. 2¹²⁸ attempts, beyond any computer. It's also why a truncated hash (say 12 hex characters = 48 bits, like this site's source_hash) is only for detecting changes, not for resisting someone deliberately making a collision: 2²⁴ ≈ 16 million attempts and you have one.
The length-extension attack, and HMAC
Say a server wants to "sign" a link so users can't change its parameters. The natural idea: keep a secret key, compute sha256(key + data), attach it to the link. An attacker without the key can't compute the right hash... right?
Wrong. SHA-256 (like MD5, SHA-1 and SHA-512) processes data in 64-byte blocks, and the final hash is the internal state after the last block. Holding the hash means holding the state, and an attacker can keep hashing from there, adding data to the end without knowing the key. They only need to know the key's length, which they can usually guess in a few tries.
The experiment: rewrite SHA-256 in pure Python (~30 lines) so it can start from a given state. The server has a random 16-byte key and signs user=an&amount=100:
mac = hashlib.sha256(key + b"user=an&amount=100").hexdigest() # the server publishes this
state = unpack(">8I", bytes.fromhex(mac)) # attacker: the hash is the state
glue = padding(len(key) + len(msg)) # the padding the server added itself
forged_msg = msg + glue + b"&amount=1000000"
forged = sha256_continue(state, b"&amount=1000000", ...)
forged message: b'user=an&amount=100\x80\x00\x00...\x00\x01\x10&amount=1000000'
server accepts: True
HMAC of forged == attacker guess: False
The server accepts it. The forged message has some junk bytes in the middle (the padding), but many parameter parsers ignore it, and the last amount parameter wins. A flaw of this kind really existed in Flickr's API in 2009.
The right fix is HMAC (hash-based message authentication code): a construction that hashes twice, H((K ⊕ opad) ‖ H((K ⊕ ipad) ‖ m)), proven secure even when the underlying hash has the length-extension property. The last line of the experiment shows the same trick against HMAC fails. In Python:
import hmac, hashlib
tag = hmac.new(key, message, hashlib.sha256).digest()
SHA-3 and BLAKE2/3 aren't vulnerable to length extension thanks to their different design, but the practical rule stays simple: when you need a "signature" with a shared key, use HMAC, don't glue a key onto data yourself. This site's HS256 sign-in tokens are exactly HMAC-SHA256.
Comparing signatures: don't use ==
When a server receives an HMAC from a user and compares it with the one it computed, the comparison itself can leak. The == operator on bytes stops at the first differing byte. Measured on two 1 MB strings, one differing in the first byte and one in the last:
== first-byte diff 0.02 us, last-byte diff 18.55 us | compare_digest 276.08 / 276.24 us
== takes 0.02 µs when wrong in the first byte and 18.55 µs when wrong in the last, almost 1,000 times apart. An attacker timing responses could probe byte by byte: try 256 values for the first byte, the slightly slower one is right, then move to the next. With a short string like a 32-byte HMAC the difference is only a few nanoseconds and mostly hidden by network noise, but researchers have measured differences of that size over a LAN with enough repetitions.
hmac.compare_digest always walks the whole string, taking the same time wherever the mismatch is (276 µs both times, slower because it deliberately avoids shortcuts, but negligible for 32 bytes). This site uses it when comparing OAuth's state:
if not (code and state and saved and secrets.compare_digest(state, saved.state)):
Where hashing shows up in practice
| Where | Hashes what | Why |
|---|---|---|
| Git | Each file's content, directory trees, commits | Naming by content; change one byte of history and every later commit id changes |
| This site's static files | ?v= + a hash of the CSS/JS content |
Change the file and the URL changes, so it can be cached for long without going stale |
The blog's source_hash |
The Vietnamese text | Know when a translation is out of date |
| Software downloads | SHA-256 of the installer | Detect a corrupted or swapped file (when the hash comes from a trusted channel) |
| TLS certificates, digital signatures | Hash the data, then sign the hash | Sign 32 bytes instead of the whole file |
| Passwords | Slow hashing with a salt | Post 3 |
| JWT HS256, signed cookies, webhooks | HMAC | Stopping content from being altered |
| Blockchain | The previous block's hash, Merkle trees, proof of work | Each block "locks" the entire history before it |
One limit often forgotten in the "software downloads" row: if an attacker can replace the file on the download page, they can also replace the hash printed right next to it. A hash only proves "this file matches that hash". To prove "this file was made by the right publisher" you need a digital signature (post 4).
Summary
- A cryptographic hash: fixed-size output, one-way, collision-resistant, and flipping 1 input bit changes on average 127.9/256 output bits.
- MD5 and SHA-1 are broken for collisions. Use SHA-256, SHA-3 or BLAKE2/3.
- Measured: SHA-256 at 3,350 MB/s (thanks to dedicated CPU instructions), faster than MD5. Fast is good for checking files and bad for passwords.
- Birthday paradox: n bits only resist collisions up to 2^(n/2). A 32-bit hash collided after 33–133 thousand attempts.
sha256(key + data)can be forged with a length-extension attack (done for real in the post). Use HMAC.- Compare signatures with
hmac.compare_digest, not==(almost 1,000 times apart between a first-byte and a last-byte mismatch).
The next post uses hashing for the most sensitive job: storing passwords. Why a fast SHA-256 is a disaster there, what salt stops, how slow on purpose the Argon2id this site uses is, and how long someone with a copy of the database needs to crack an 8-character password.