For a hash function with a 128‑bit output, the birthday bound indicates that a collision is likely after about how many evaluations?

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

Answer: (D)

The birthday bound shows that collisions become likely when you’ve sampled about the square root of all possible hash outputs. A 128‑bit hash has a huge number of possible values, so the point where a collision is probable is much smaller than trying every possible value, yet still astronomically large. In other words, the practical collision window is determined by the square root of the total output space, not the full space. This is why the expected threshold for collisions aligns with that square-root scale for a 128‑bit hash. The other options either imply far more evaluations than the birthday bound suggests or far fewer, so they don’t match this principle.