hypesystem
commented
7 years ago Pidgeon-hole principle (lulz): if you map a large space to a smaller output space, if you exhaust the output space you must have at least one collision. If we assume a uniformly random mapping function (like a hash function) or if we do uniform sampling from a non-uniformly random mapping function, we get a probability of p = 1/2 for having found a collision once we have done 2^(l/2) requests where 2^l is the size of the output space.
Nice illustration: pidgeon holes and pidgeons being placed into them. Show worst case (2^l + 1 request leads to collision) and average case (uniformly random sampling).
Based on the birthday paradox which is not a paradox. (Link to wikipedia?)
Concatenation attack on Merkle-Damgård? I can predict a hash by requesting a hash of a prefix z = H^S(m_pre), computing h(h(z, |m_pre|), |m_pre| + 1), which is equivalent of H^S(m_pre || |m_pre|) (which is a distinct message).