0.2 Hash functions

What is a hash function?

Think of a fingerprint. A person is large and complicated, but a fingerprint is small, it always comes out the same for the same person, and two different people almost never share one. A cryptographic hash function does the same for data. It takes any sequence of bytes, a password, a contract, a 4 GB disk image, and returns a short, fixed-size value called a digest or hash.

SHA-256, the most widely used hash today, always returns 256 bits, which is 32 bytes or 64 hex digits (see 0.1 Encoding for how bytes become hex). The input “hello” followed by a newline gives

5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03

Hashing is not encryption. There is no key and no way back: you cannot “decrypt” a digest into the original data. It is also deterministic. Anyone who hashes the same bytes gets the same digest, which is exactly what makes it useful for checking data.

The three security properties

Any function that shrinks data must have collisions: there are infinitely many inputs and only $2^{256}$ possible SHA-256 outputs. The security promise is that nobody can find them. Cryptographers split this into three properties, from weakest to strongest demand on the attacker:

In plain language: preimage resistance means a digest reveals nothing you can use to rebuild the input. Second-preimage resistance means nobody can forge a different file that matches the digest of your file. Collision resistance means nobody can prepare two files, say a harmless contract and a harmful one, that share a digest. The last one is the hardest to guarantee, because the attacker is free to choose both inputs.

The avalanche effect

A good hash behaves like a random function. Change one bit of the input and each output bit flips with probability one half, independently of the others. So a small edit produces a digest that looks completely unrelated, and similar inputs do not produce similar digests. Try it: the two messages below differ in one character.

With the starting messages the digests differ in 123 of 256 bits, close to the 128 you expect from two unrelated random strings. This is why you cannot learn anything about an input by looking at its digest, and why you cannot “nudge” an input towards a target digest.

The birthday bound: why 256 bits gives 128-bit security

In a room of just 23 people, the chance that two share a birthday is already about 50.7%, even though there are 365 possible days. The reason is that you are comparing every pair, and 23 people form 253 pairs. The same effect applies to hashes: after computing $k$ random digests, the number of pairs grows like $k^2/2$, so a collision becomes likely long before $k$ gets close to the number of possible outputs.

For SHA-256 that is roughly $2^{128}$ hash computations, far beyond any computer that exists or is planned. After a mere $2^{64}$ digests the collision probability is only about $1.5 \times 10^{-39}$. The same arithmetic explains why short hashes are weak: MD5 has 128-bit output, so even a perfect 128-bit hash would only give 64-bit collision security, which is within reach of large computations today.

SHA-2, SHA-3, SHAKE and BLAKE

SHA-3 did not replace SHA-2 because SHA-2 failed; SHA-2 is still considered secure. SHA-3 exists so that the world has a strong hash built on different ideas in case one design is ever broken. Its extendable-output siblings, SHAKE128 and SHAKE256, are especially handy when an algorithm needs a long stream of pseudorandom bytes from a short seed. That is exactly how the post-quantum standards use them: ML-KEM and ML-DSA expand a 32-byte seed into their whole public matrix with SHAKE128. ML-KEM also uses SHA3-256 and SHA3-512 for its internal hashing, and ML-DSA uses SHAKE256.

Here is how to compute these in Python with the standard library. Note that the 16-byte and 32-byte SHAKE outputs share their first 16 bytes: an XOF simply keeps producing output.

import hashlib

msg = b"Transfer 100 euros to Alice"
print(hashlib.sha256(msg).hexdigest())
print(hashlib.sha256(b"Transfer 900 euros to Alice").hexdigest())
print(hashlib.sha3_256(msg).hexdigest())
print(hashlib.shake_128(msg).hexdigest(16))   # 16 bytes of output
print(hashlib.shake_128(msg).hexdigest(32))   # 32 bytes: same prefix, just longer

a7355e5aa2a812d4c39c74605a0cc33dac527a21cea2df73fd66178f70d13139
3ec045d16535d2f75772464d26e1e8df292b3e0ec2116e47f842216c375b1237
e59d1c0dd0908da21fe389f4dc9b51dcc52816e10c414d333a1d0120806b80e0
c0f6599efc6e3c774da83aac1c11596b
c0f6599efc6e3c774da83aac1c11596b9f8d0f8443a619846ac7888967c3a222

A quirk of SHA-2: length extension

SHA-256 processes its input in 64-byte blocks and carries a running internal state from block to block. The final digest is that internal state. As a result, anyone who knows $H(\text{secret} \,\|\, \text{message})$ and the length of the secret can compute the hash of $\text{secret} \,\|\, \text{message} \,\|\, \text{padding} \,\|\, \text{more}$ without knowing the secret. So the tempting construction “prepend a secret key and hash” is not a safe way to authenticate messages.

This is not a flaw in collision or preimage resistance; it is simply a property the design never promised to avoid. The fix is to use a construction built for keyed authentication, HMAC, covered in 0.4 MACs and key derivation. SHA-3 and BLAKE2/3 do not have this property.

What hashes are used for

• Integrity checks. A download page lists the SHA-256 of a file; you hash what you downloaded and compare. If even one byte changed, the digests differ.
• Content addressing. Git names every file and commit by its hash, and deduplicating storage systems store each block under its digest.
• Commitments. Publish $H(\text{prediction} \,\|\, \text{random nonce})$ now and reveal the prediction later; the digest proves you did not change it, and the random nonce stops others from guessing it.
• Merkle trees. Hash many items, then hash pairs of digests, then pairs of those, up to one root digest. Proving that an item is included takes only about $\log_2 N$ digests. Certificate Transparency logs and blockchains use this, and so do hash-based signatures such as SLH-DSA.
• Building blocks. Signatures hash the message first (0.6), HMAC and HKDF are built from hashes (0.4), and lattice schemes use SHAKE to expand seeds.

Why a plain hash is wrong for passwords

A tempting idea is to store $\text{SHA-256}(\text{password})$ instead of the password. The problem is speed. A modern GPU computes billions of SHA-256 hashes per second, and real passwords come from a small, predictable space. If the database leaks, an attacker simply hashes likely passwords until the digests match. Identical passwords also produce identical digests, so one precomputed table cracks every account that shares a common password.

Password storage needs a different tool: a salted, deliberately slow and memory-hard function such as Argon2id, scrypt or bcrypt. These are covered in 0.4.

Hashing a large file

Hash functions process data as a stream, so you never need to load a large file into memory. Feed it in chunks and read the digest at the end:

import hashlib

def file_sha256(path: str) -> str:
    h = hashlib.sha256()
    with open(path, "rb") as f:
        for chunk in iter(lambda: f.read(1 << 16), b""):
            h.update(chunk)
    return h.hexdigest()

with open("example.txt", "wb") as f:
    f.write(b"hello\n")
print(file_sha256("example.txt"))
# 5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03
# (the same value as: printf 'hello\n' | shasum -a 256)

Common mistakes

• Calling hashing “encryption”. There is no key and no decryption. If you need to get the data back, you need encryption (0.3).
• Using MD5 or SHA-1 for anything security-related. Both have practical collisions. Use SHA-256 or better.
• Authenticating with $H(\text{key} \,\|\, \text{message})$. With SHA-2 this is vulnerable to length extension. Use HMAC.
• Storing passwords with a fast hash, with or without salt. Use Argon2id, scrypt or bcrypt.
• Hashing text without fixing the encoding. “é” can be one or two Unicode code points, and UTF-8 versus UTF-16 give different bytes, so the digests differ. Normalise and encode first (0.1).
• Truncating digests too far. A 64-bit truncated digest has only 32-bit collision security.

Further reading

NIST FIPS 180-4 (SHA-2) and FIPS 202 (SHA-3 and SHAKE) are the standards. For a readable treatment of hash security and the birthday bound, see chapter 6 of Jean-Philippe Aumasson's Serious Cryptography (cited from memory). The SHA-1 collision is described at shattered.io.

Next: 0.3 Symmetric encryption, where a key finally lets you hide data and get it back.