For SHA-256, the birthday bound suggests a collision is expected after about how many hash evaluations?

• A. 2^256
• B. 2^32
• C. 2^64
• D. 2^128

Answer: (D)

The birthday bound says that for a hash with an n-bit output, you expect a collision after about sqrt(2^n) evaluations, which is 2^(n/2). For SHA-256, n is 256, so the expected number of hash evaluations to see a collision is about 2^128. This is why SHA-256 is described as having roughly 128-bit collision resistance. The other numbers would correspond to different properties or smaller hash lengths (for example, preimage resistance for SHA-256 is around 2^256, and a 128-bit hash would have a collision bound around 2^64).