I understand how to use public/private keys, encryption, and checksums, but I'm less familiar with the mathematical side of cryptography. I'm trying to understand why brute-force collision searches are considered difficult.
If a hash produces an n-bit output, there are 2^n possible hash values. By the pigeonhole principle, hashing 2^n + 1 distinct inputs must produce at least one collision. However, hashes such as MD5, SHA-1, SHA-224, and SHA-256 have outputs much larger than the native integer size of a typical 64-bit machine.
Does that mean a computer cannot generate or work with values such as 2^128 or 2^256? Also, if we tried to find a collision by storing every input and output, would the required storage really be roughly n × 2^n bits? Is the basic intuition correct that the enormous size of 2^n is what makes brute-force attacks impractical?
3 Answers
The important distinction is between a preimage attack and a collision attack. For a preimage attack, you are given a target hash and search for an input that produces it. Assuming the hash behaves randomly, this takes about 2^(n-1) trials on average and does not require storing all previous results.
For a collision, you only need any two inputs with the same hash. Although 2^n + 1 inputs guarantee a collision, the birthday effect means a collision will usually appear after roughly 2^(n/2) random inputs. A straightforward implementation stores the results so it can detect duplicates, but there are also memory-efficient approaches such as distinguished points and collision-search algorithms.
So the general intuition is right, but collisions are substantially easier than searching for a specific hash: an n-bit hash offers roughly n/2 bits of collision security.
The storage calculation describes one naive strategy: keep about 2^n hash outputs, each n bits long. That is indeed impossibly large for modern hash sizes. But you do not need to enumerate all 2^n possible values to find a collision. Random sampling reaches a likely collision near 2^(n/2), and specialized algorithms can reduce memory further. The exponential growth is still the key reason brute force becomes infeasible.
A 64-bit processor does not limit you to numbers that fit in one 64-bit word. Arbitrary-precision libraries represent larger integers using several machine words and handle carries between them, much like ordinary long multiplication on paper. Cryptographic software routinely works with values far larger than 64 bits, so this is not a fundamental obstacle.
That clears up the distinction between preimages and collisions. I’ll read more about the birthday problem and collision-search methods.