Difference between revisions of "GenericAttacksHash"
Crechberger (talk | contribs) |
Crechberger (talk | contribs) |
||
| Line 20: | Line 20: | ||
found more efficiently than what could be expected based on its hash | found more efficiently than what could be expected based on its hash | ||
length, then the function is considered to be broken. | length, then the function is considered to be broken. | ||
| + | |||
| + | === The birthday attack === | ||
| + | The birthday attack (also called''square-root'' attack) is a generic attack which considers a | ||
| + | hash function as black box. Therefore, a birthday attack is | ||
| + | successful for every hash function. For any message $m$ we can | ||
| + | compute the $n$-bit hash value $y = h(m)$. Since at least a fraction | ||
| + | $2^{-n}$ of the pairs $(m,m^*)$ satisfies $h(m) = h(m^*)$, one can | ||
| + | expect to find a colliding message pair after trying about $2^n$ | ||
| + | arbitrary message pairs, \cf~\eqref{eqn:collision}. Nevertheless, it | ||
| + | follows from the birthday paradox that one can check $2^n$ pairs | ||
| + | with only $2^{n/2}$ evaluations of $h$. A birthday attack works as | ||
| + | follows: | ||
| + | \begin{enumerate} | ||
| + | \item Pick any message $m$ and compute $h(m)$. | ||
| + | \item Update list $L$ %Check if $h(m)$ is in the list $L$. | ||
| + | \begin{itemize} | ||
| + | \item if $(h(m),m)$ is already in $L$, a colliding message pair has been found. | ||
| + | \item else save the pair $(h(m),m)$ in the list $L$ and go back to step 1. | ||
| + | \end{itemize} | ||
| + | \end{enumerate} | ||
| + | From the birthday paradox we know that we can expect to find a | ||
| + | matching entry, after performing about $2^{n/2}$ hash evaluations. | ||
| + | Note that in a birthday attack an attacker has full control over the | ||
| + | messages. Hence, as pointed out by Yuval~\cite{}, this method | ||
| + | enables an attacker to construct meaningful collisions. | ||
Revision as of 15:33, 10 March 2008
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.
2.1 The birthday attack
The birthday attack (also calledsquare-root attack) is a generic attack which considers a hash function as black box. Therefore, a birthday attack is successful for every hash function. For any message $m$ we can compute the $n$-bit hash value $y = h(m)$. Since at least a fraction $2^{-n}$ of the pairs $(m,m^*)$ satisfies $h(m) = h(m^*)$, one can expect to find a colliding message pair after trying about $2^n$ arbitrary message pairs, \cf~\eqref{eqn:collision}. Nevertheless, it follows from the birthday paradox that one can check $2^n$ pairs with only $2^{n/2}$ evaluations of $h$. A birthday attack works as follows: \begin{enumerate}
\item Pick any message $m$ and compute $h(m)$.
\item Update list $L$ %Check if $h(m)$ is in the list $L$.
\begin{itemize}
\item if $(h(m),m)$ is already in $L$, a colliding message pair has been found.
\item else save the pair $(h(m),m)$ in the list $L$ and go back to step 1.
\end{itemize}
\end{enumerate} From the birthday paradox we know that we can expect to find a matching entry, after performing about $2^{n/2}$ hash evaluations. Note that in a birthday attack an attacker has full control over the messages. Hence, as pointed out by Yuval~\cite{}, this method enables an attacker to construct meaningful collisions.
