GenericAttacksHash

1 Preimage attacks

The resistance of a hash function to collision and (second) preimage attacks depends in the first place on the length $n$ of the hash value. Regardless of how a hash function is designed, an adversary will always be able to find preimages or second preimages after trying out about $2^n$ different messages. In case an adversary is given $2^k$ distinct target hashes, preimages can be found after trying about $2^{n-k}$ different messages~\cite[Chapter 2, pages 12-13]{Merkle79SecrecyAuthenticationAnd} %, chapter 2, pages 12-13}.

2 Collision attacks

As independently observed by Merkle~\cite{conf/crypto/Merkle89} and Yuval~\cite{journal/cryptologia/Yuval79} in 1979, finding collisions requires a much smaller number of trials: about $2^{n/2}$, as described subsequently in Sect.~\ref{sec:birth}. As a result, hash functions producing less than 160 bits of output are currently considered inherently insecure. Moreover, if the internal structure of a particular hash function allows collisions or preimages to be found more efficiently than what could be expected based on its hash length, then the function is considered to be broken.