Hash Collisions Explained: When Two Inputs Share One Hash

A hash collision happens when two different inputs produce the same hash output. Feed “hello” and some other string into the same hash function, and if both come out as the identical digest, that is a collision. It sounds like a bug, but it is a mathematical certainty for every hash function ever made. The interesting part is when collisions are harmless, and when they break your security.

What is a hash collision?

A hash function takes any input (a word, a file, a 4 GB video) and maps it to a fixed-size output. SHA-256 always returns 256 bits, no matter what you feed it. That fixed size is the whole point: it makes lookups fast and comparisons cheap.

A collision is simply two distinct inputs, x and y, where hash(x) == hash(y) even though x is not equal to y. For example, MD5 famously has known collisions, so two completely different files can share the same MD5 digest. You can verify this yourself by hashing both files and seeing the identical string come back.

Collisions are not always a problem. In a hash table, a collision is a routine event you plan for. In cryptography, a deliberate collision can forge a signature or fake a certificate. Same word, two very different stakes.

Why collisions are unavoidable: the pigeonhole principle

Collisions have to exist, and the reason is a counting argument called the pigeonhole principle. If you have more pigeons than holes, at least one hole holds two pigeons. There is no way around it.

Now apply that to hashing. The set of possible inputs is effectively infinite: every file, every string, every number. The set of possible outputs is finite: SHA-256 has 2 to the power of 256 possible values, which is huge but still a fixed number. Infinite inputs mapped onto a finite set of outputs means some inputs must land on the same output. Guaranteed.

So no hash function can be collision-free. When people say a hash function is “good,” they do not mean collisions cannot happen. They mean collisions are so rare and so hard to find on purpose that you will never stumble into one by accident. That distinction is the entire game.

The birthday paradox: why collisions happen sooner than you’d think

Here is where intuition fails most people. You might guess that to find a collision in a hash with N possible outputs, you would need to try about N inputs. You actually need far fewer, roughly the square root of N. This is the birthday paradox, and it drives the birthday attack.

The classic version: in a room of just 23 people, there is about a 50 percent chance two of them share a birthday. That feels wrong because there are 365 possible birthdays. But you are not matching one specific person, you are matching any pair, and the number of possible pairs grows fast. With 23 people you already have 253 pairs to compare.

For hashing, the math is the same. A hash with 2 to the power of 128 outputs does not need 2 to the power of 128 attempts to collide. It needs about 2 to the power of 64, the square root. That is why a birthday attack is the baseline threat model for any hash: an attacker looking for any two colliding inputs has a much easier job than one hunting for a specific target. If you want the full mechanics of how a digest is built in the first place, see how hashing works.

Collisions in hash tables vs collisions in cryptography

The word “collision” means two opposite things depending on where you are standing.

In a hash table (the data structure behind dictionaries, sets, and database indexes), collisions are expected and cheap. A hash table has maybe a few thousand slots, and a good implementation assumes items will sometimes hash to the same slot. Handling that gracefully is just part of the design. A collision here costs you a few extra CPU cycles, nothing more.

In cryptography, a collision is a weapon. If an attacker can produce two files with the same hash, they can get you to sign the harmless one and then swap in the malicious one, because both carry the identical digest. That is not a performance hiccup, that is a broken trust chain. The defenses are completely different, so it helps to keep the two worlds separate in your head.

Collision resolution: chaining and open addressing

Hash tables handle collisions with two main strategies, and this is what “hash collision resolution” refers to.

Separate chaining stores a small list at each slot. When two keys hash to slot 7, both live in slot 7’s list, and a lookup walks that short list to find the right one. It is simple and degrades gracefully as the table fills up. Most standard library hash maps use some form of chaining.

Open addressing keeps everything in the array itself. When slot 7 is taken, the algorithm probes for the next free slot using a rule (linear probing checks slot 8, then 9, and so on). It uses memory more tightly and plays nicer with CPU caches, but it slows down badly once the table gets crowded. That is why open-addressing tables resize before they get too full, usually around 70 to 80 percent load. Either way, a hash table collision is a solved, boring problem. It only becomes interesting when the hash is doing security work.

When a collision becomes an attack: the MD5 and SHA-1 breaks

A collision stops being theoretical the moment someone can generate one on demand. That has already happened to two widely used hash functions.

MD5 fell first. Researchers demonstrated practical collisions in 2004, and by 2008 a team used MD5 collisions to forge a rogue certificate authority certificate, meaning they could have impersonated secure websites. MD5 is now considered completely broken for any security purpose. It is fine as a fast checksum against accidental corruption, and nothing more.

SHA-1 followed. In 2017, Google and CWI Amsterdam published “SHAttered,” the first practical SHA-1 collision: two different PDF files with the same SHA-1 hash. It took enormous compute, but it proved SHA-1 was dead for signatures and certificates. Browsers and certificate authorities had already been phasing it out, and this sealed it. If you are still using MD5 or SHA-1 to verify integrity where an attacker might tamper with the data, that is the bug to fix today. A side-by-side of the two older functions lives in SHA-256 vs MD5.

How collision resistance is measured (and why SHA-256 holds up)

Collision resistance is the property that makes finding any two colliding inputs computationally infeasible. It is measured in the effort an attacker needs, expressed as a number of hash operations.

For a hash with an n-bit output, the birthday attack sets the bar at roughly 2 to the power of (n/2) operations to find a collision. SHA-256 has a 256-bit output, so its collision resistance is about 2 to the power of 128 operations. That number is so large that even with every computer on Earth working together, finding a collision would take longer than the age of the universe. A hash “holds up” when the cheapest known attack is still no better than this birthday bound.

MD5 and SHA-1 broke because clever cryptanalysis found shortcuts far cheaper than their birthday bounds. SHA-256 has no such shortcut known after years of scrutiny, which is why it is the default for TLS certificates, Git object IDs, blockchain, and file integrity checks. When you need to actually compute a digest and compare it, you can paste text or a file into a hash generator that outputs SHA-256 and MD5 side by side, so you can see a real collision-free digest for yourself instead of taking the math on faith.

FAQ

Can two different files really have the same hash?

Yes. For MD5 and SHA-1 it is not only possible but has been done on purpose with real, downloadable file pairs. For SHA-256 no collision has ever been found, but the pigeonhole principle guarantees they exist in theory. The practical answer: with a broken hash, treat matching digests as no proof at all; with SHA-256, a match is safe to trust.

Is a hash collision a security vulnerability?

It depends on where the hash is used. In a hash table it is a normal, handled event and not a vulnerability. In a digital signature, certificate, or password system, an attacker who can produce collisions can forge data, so there it is a serious weakness. That is exactly why MD5 and SHA-1 were retired from security use.

How many hashes until a collision?

Far fewer than the total number of outputs, thanks to the birthday paradox. For an n-bit hash you expect a collision after about 2 to the power of (n/2) random inputs, the square root of the output space. For a 128-bit hash that is about 2 to the power of 64 attempts, not 2 to the power of 128.

Does SHA-256 have collisions?

Mathematically it must, because there are infinitely many inputs and only 2 to the power of 256 outputs. But no one has ever found one, and the best known method still needs about 2 to the power of 128 operations, which is beyond any real-world attacker. For every practical purpose, SHA-256 is collision-free.