For an ideal hash function with a 256-bit output, which combination gives the approximate number of computations needed for a brute-force attack in two cases: finding an input that produces a given hash value (a preimage attack), and finding any two different inputs that produce the same hash value (a collision attack)?

Answer: A. Preimage attack: about 2^256; collision attack: about 2^128

An ideal hash function with an n-bit output has 2^n possible hash values, and each input tried matches a given hash value with probability 1/2^n. A preimage attack therefore needs about 2^n computations, which for n = 256 is about 2^256. In a collision attack, however, any two inputs may match, so trying k inputs gives about k^2/2 pairs to compare. Once k^2/2 approaches 2^n, that is, when k is around 2^(n/2), a collision becomes likely; for n = 256 that is about 2^128. This is the same idea as the birthday paradox, in which a group of 23 people has a better than 50% chance that two share a birthday, so it is called a birthday attack. Consequently, a hash function's strength against collisions is estimated at half its output length, and achieving 128-bit strength requires a 256-bit output.

• A. Correct. A preimage attack takes about 2^256 computations, and a collision attack about 2^128 thanks to the birthday attack.
• B. This swaps the two. The collision attack, where any two inputs may match, needs fewer computations.
• C. In a collision attack any pair of the inputs tried may match, so about 2^128 computations suffice, far fewer than for a preimage attack.