Properties of Good Hash Functions
Hashing Fundamentals · Data & Hashing track
5 min read
In this module
What Makes a Good Hash Function?
Hash functions aren't interchangeable. The "sum all bytes" thing from the previous lesson is technically a hash function, and completely useless for anything beyond a tutorial. A good hash has to satisfy specific properties — and which properties matter depends on what you're using it for.
Determinism
The most basic requirement: same input, same output, every time. If hash("Hello") returns one value today and a different value tomorrow, the function is useless for verification, indexing, or anything else.
Sounds obvious. Worth saying because it rules out functions that fold in randomness, timestamps, or any other shifting state.
Uniform Distribution
A good hash function spreads its outputs as evenly as possible across the output space. If some output values turn up more often than others, the hash is biased, and bias causes pain: hash tables sprout hot spots, collision attacks get cheaper.
Ideally, for random inputs, every possible output value is equally likely. That's uniformity.
The Avalanche Effect
Changing even a single bit of the input should change approximately half of the output bits. This is the avalanche effect (also called the strict avalanche criterion).
sha256("Hello") --> 185f8db3...sha256("Hellp") --> 2113cd4a... (completely different)Without the avalanche effect, an attacker could nudge an input bit by bit, watch how the hash drifts, and gradually walk towards any target hash value they want.
The avalanche effect ensures that tiny input changes cause dramatic output changes. If flipping one input bit consistently flips about half the output bits, the hash function thoroughly mixes its input, making it impossible to predict output changes from input modifications.
Flip a single input bit and count how many of SHA-256's 256 output bits change. It hovers around half, whichever character you pick.
Flipping the lowest bit of that character gives Ce Bitwise. One input bit is different.
Hashing…
Pre-Image Resistance
Given a hash value h, it should be computationally infeasible to find any input m such that hash(m) = h. That's pre-image resistance, also known as the one-way property.
Stare at 185f8db32271fe25... for as long as you like — you should never be able to work backward to "Hello." The only avenue should be brute force: try inputs one by one until something matches. For a 256-bit hash, that's 2^256 possibilities. Don't bother.
Second Pre-Image Resistance
Given an input m1, you shouldn't be able to find a different input m2 such that hash(m1) = hash(m2). Put plainly: given a specific document, no one should be able to fabricate a different document with the same hash.
Subtly different from general collision resistance. Second pre-image resistance is about targeted forgery — an attacker with a specific signed document cannot cook up a different document that passes the same signature check.
Collision Resistance
It should be computationally infeasible to find any two different inputs m1 and m2 such that hash(m1) = hash(m2). Stronger than second pre-image resistance, because the attacker gets to pick both inputs freely.
The birthday paradox matters here. In a room of 23 people, there's a 50% chance two share a birthday. Same maths for hashes: with an n-bit output, you only need to hash roughly 2^(n/2) random inputs before bumping into a collision with 50% probability. For SHA-256, that's 2^128 — still infeasible, but far fewer than the 2^256 you might expect.
Side by side, the three properties differ in how much the attacker is handed and how much they get to choose. Each step to the right gives the attacker more freedom, and collision-finding gets a square-root discount from the birthday paradox:
Because the collision-finder can choose both inputs, collisions are always the first to fall when a hash weakens. That's the order MD5 and SHA-1 broke in, as the next lesson shows.
Speed: A Double-Edged Sword
For hash tables, you want fast. The function gets called billions of times, and every nanosecond compounds.
For password hashing, you want slow. If an attacker steals a database of password hashes, a deliberately slow hash function stops them from ripping through billions of guesses a second.
This is why there are separate families of hash functions for different purposes:
- Fast hashes for data structures: MurmurHash, xxHash, CityHash
- Cryptographic hashes for security: SHA-256, SHA-3, BLAKE2
- Password hashes deliberately designed to be slow: bcrypt, scrypt, Argon2
Non-Cryptographic vs. Cryptographic
Not every hash needs every property. For a hash table, determinism, uniform distribution, and speed will do. Collision resistance and pre-image resistance? Skip them, as long as there's no adversary crafting malicious inputs. When users control the keys, there might be (more on that below).
Cryptographic hash functions satisfy every property, and pay for it in speed. They're built to take a beating.
Picking the wrong category bites in both directions. A non-cryptographic hash where you need cryptographic security is a vulnerability. A cryptographic hash where you only want a fast lookup key is wasted cycles.
Designing for the Right Adversary
Which properties matter is entirely a question of threat model. Hash table for an internal application with trusted inputs? Speed and uniform distribution, done. Hash table for a web server where users control the input? You want collision resistance against adversarial inputs — reach for SipHash or another keyed hash. Verifying software downloads? You want cryptographic collision resistance — reach for SHA-256. Work out which properties your actual threat model demands, and stop there.
The next lesson surveys the specific hash functions out in the wild and shows how each one delivers (or fails to deliver) these properties.