I understand the practical use of public and private keys, encryption, decryption, and checksums, but I'm less familiar with the mathematical side of cryptography. I'm trying to understand why finding hash collisions by brute force is considered difficult.
For a hash function with 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. In principle, the inputs could simply be the integers 1 through 2^n + 1.
However, on a 64-bit machine, a single integer cannot hold values as large as 2^128 or 2^256, which are relevant to hashes such as MD5, SHA-1, SHA-224, and SHA-256. Does that prevent us from generating or testing such inputs, or can computers work with larger values?
I also estimated that storing 2^n + 1 n-bit hash outputs would require roughly n × 2^(n−3) bytes. For a 128-bit hash, that works out to about 2^132 bytes, or 2^92 TiB. Is this the right way to think about the resources required? More generally, is the main reason cryptographic hashes are useful simply that 2^n becomes enormous even for moderately sized n-bit outputs?
4 Answers
The reasoning assumes that each input produces an independent, uniformly random-looking n-bit output. That is the security model for a good cryptographic hash, not a mathematical guarantee that every hash function behaves this way. MD5 and SHA-1 are examples where weaknesses let researchers find collisions much more efficiently than generic brute force. Their broken collision resistance does not mean that all hash functions are easy to collide.
The storage calculation describes the guaranteed pigeonhole-style approach, but it is far more than what is normally needed. With an ideal n-bit hash, a collision is expected after about 2^(n/2) hashes, not 2^n. A straightforward implementation might store those results in a table, requiring on the order of n × 2^(n/2) bits, plus overhead for the inputs and data structure.
There are also algorithms that use less memory by trading memory for additional computation. The exact practical attack depends on the hash function and implementation, but the birthday bound is the key general result.
The important distinction is between a preimage attack and a collision attack. For a preimage attack, you are given a particular target hash and search for an input that produces it. Assuming the hash behaves randomly, you generally need about 2^(n−1) trials on average, and you can do this without storing every result.
For a collision, you only need any two different inputs with the same output. Testing 2^n + 1 inputs guarantees a collision, but you normally expect to find one after roughly 2^(n/2) trials because of the birthday paradox. You may store the input/output pairs to detect repeats, though there are time-memory tradeoffs.
So your basic intuition that exponential sizes are enormous is right, but collisions are substantially easier than searching for a specific hash. That is why collision resistance for an n-bit hash is usually described as roughly n/2 bits of security.
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. Cryptographic software routinely does this for things like large RSA keys, although operations become more expensive as numbers grow.
That clears up my misunderstanding about machine word size. I’ll look into arbitrary-precision arithmetic.
Thanks, the distinction between preimages and collisions makes the resource estimates much clearer. I’ll read more about birthday attacks.