# Difference between revisions of "GenericAttacksHash"

Crechberger (talk | contribs) |
(→Collision attacks) |
||

Line 36: | Line 36: | ||

</bibtex> | </bibtex> | ||

+ | <bibtex> | ||

+ | @inproceedings{fseHochS06, | ||

+ | author = {Jonathan J. Hoch and | ||

+ | Adi Shamir}, | ||

+ | title = {Breaking the ICE - Finding Multicollisions in Iterated Concatenated | ||

+ | and Expanded (ICE) Hash Functions}, | ||

+ | booktitle = {FSE}, | ||

+ | year = {2006}, | ||

+ | pages = {179-194}, | ||

+ | volume = {4047}, | ||

+ | series = {LNCS}, | ||

+ | publisher = {Springer}, | ||

+ | isbn = {3-540-36597-4}, | ||

+ | url = {http://dx.doi.org/10.1007/11799313_12}, | ||

+ | crossref = {DBLP:conf/fse/2006}, | ||

+ | bibsource = {DBLP, http://dblp.uni-trier.de}, | ||

+ | abstract = {The security of hash functions has recently become one of | ||

+ | the hottest topics in the design and analysis of cryptographic primitives. | ||

+ | Since almost all the hash functions used today (including the MD and SHA families) | ||

+ | have an iterated design, it is important to study the general security properties | ||

+ | of such functions. At Crypto 2004 Joux showed that in any iterated hash function | ||

+ | it is relatively easy to find exponential sized multicollisions, and thus the | ||

+ | concatenation of several hash functions does not increase their security. However, | ||

+ | in his proof it was essential that each message block is used at most once. In 2005 | ||

+ | Nandi and Stinson extended the technique to handle iterated hash functions in which | ||

+ | each message block is used at most twice. In this paper we consider the general case | ||

+ | and prove that even if we allow each iterated hash function to scan the input multiple | ||

+ | times in an arbitrary expanded order, their concatenation is not stronger than a | ||

+ | single function. Finally, we extend the result to tree-based hash functions with arbitrary tree structures.} | ||

+ | } | ||

+ | </bibtex> | ||

=== The birthday attack === | === The birthday attack === | ||

The birthday attack (also called''square-root'' attack) is a generic attack which considers a | The birthday attack (also called''square-root'' attack) is a generic attack which considers a | ||

Line 89: | Line 120: | ||

abstract = {An open question about the asymptotic cost of connecting many processors to a large memory using three dimensions for wiring is answered, and this result is used to find the full cost of several cryptanalytic attacks. In many cases this full cost is higher than the accepted complexity of a given algorithm based on the number of processor steps. The full costs of several cryptanalytic attacks are determined, including Shanksrsquo method for computing discrete logarithms in cyclic groups of prime order n, which requires $n^{1/2}+o(1)$ processor steps, but, when all factors are taken into account, has full cost n2/3+o(1). Other attacks analyzed are factoring with the number field sieve, generic attacks on block ciphers, attacks on double and triple encryption, and finding hash collisions. In many cases parallel collision search gives a significant asymptotic advantage over well-known generic attacks.}, | abstract = {An open question about the asymptotic cost of connecting many processors to a large memory using three dimensions for wiring is answered, and this result is used to find the full cost of several cryptanalytic attacks. In many cases this full cost is higher than the accepted complexity of a given algorithm based on the number of processor steps. The full costs of several cryptanalytic attacks are determined, including Shanksrsquo method for computing discrete logarithms in cyclic groups of prime order n, which requires $n^{1/2}+o(1)$ processor steps, but, when all factors are taken into account, has full cost n2/3+o(1). Other attacks analyzed are factoring with the number field sieve, generic attacks on block ciphers, attacks on double and triple encryption, and finding hash collisions. In many cases parallel collision search gives a significant asymptotic advantage over well-known generic attacks.}, | ||

} | } | ||

− | </bibtex> | + | </bibtex> |

= Attacks in the quantum setting = | = Attacks in the quantum setting = |

## Revision as of 14:17, 11 March 2008

## Contents

# 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.

*Ralph C. Merkle* - **A Certified Digital Signature**

- CRYPTO 435:218-238,1989
- http://link.springer.de/link/service/series/0558/bibs/0435/04350218.htm

Bibtex**Author :**Ralph C. Merkle**Title :**A Certified Digital Signature**In :**CRYPTO -**Address :****Date :**1989

*Jonathan J. Hoch, Adi Shamir* - **Breaking the ICE - Finding Multicollisions in Iterated Concatenated
**

**
and Expanded (ICE) Hash Functions**

- FSE 4047:179-194,2006
- http://dx.doi.org/10.1007/11799313_12

Bibtex**Author :**Jonathan J. Hoch, Adi Shamir**Title :**Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions**In :**FSE -**Address :****Date :**2006

### 2.1 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.

### 2.2 Parallel collision search

*Paul C. van Oorschot, Michael J. Wiener* - **{Parallel Collision Search with Cryptanalytic Applications}**

- J. Cryptology 12(1):1-28,1999
- http://link.springer.de/link/service/journals/00145/bibs/12n1p1.html

Bibtex**Author :**Paul C. van Oorschot, Michael J. Wiener**Title :**{Parallel Collision Search with Cryptanalytic Applications}**In :**J. Cryptology -**Address :****Date :**1999

*Michael J. Wiener* - **The Full Cost of Cryptanalytic Attacks**

- J. Cryptology 17(2):105-124,2004
- http://dx.doi.org/10.1007/s00145-003-0213-5

Bibtex**Author :**Michael J. Wiener**Title :**The Full Cost of Cryptanalytic Attacks**In :**J. Cryptology -**Address :****Date :**2004

# 3 Attacks in the quantum setting

Results of quantum complexity theorists as well as newly invented algorithms suggest that even with the power of hypothetic quantum computers applied against commonly used hash functions, no exponential improvement over classical computers is possible. Here we briefly discuss hash function related aspects of this work.

One of the celebrated results in quantum algorithms is Grover's~\cite{Grover1996AFastQuantum} from 1996. %(building up on pioneering work of Deutsch, etc..~\cite{}): The search for a particular element in an unordered database of size $r$ takes at most $O(r^{1/2})$, an actual algorithm is provided that uses xxx memory. Matching lower bounds exist for this problem as well~\cite{boyer98tight,zalka99GroversQuantumSearching}. This algorithm is of wide interest as it does not rely on a particular structure of the elements in the search space.

This result has already direct implications on hash functions: There, the search for a preimage or a second preimage is at most as hard as a search in an unordered database, hence security against these types of generic attacks is lowered from $2^{n}$ to $2^{n/2}$ in the quantum setting.

How about collision attacks in the quantum setting? Here, the fact that many collisions exist and the problem is to find a single one indeed leads to (both asymptotically and for commonly used finite dimensions\todo{better wording than finite dim. needed!}) faster algorithms. An actual quantum algorithm for the collision problem is due to Brassard, H{\o}yer, and Tapp~\cite{DBLP:conf/latin/BrassardHT98} from 1997. This combination of Grover's algorithm with the birthday effect yields a runtime of $2^{n/3}$ for a hash function with $n$ bit output size. The algorithm requires $\Theta(n^{1/3}$log $n)$ classical bits of memory. To the best of the author's knowledge, no time/memory tradeoffs are known. Is this the best one can do? Nontrivial lower bounds for the collision problem were an open problem for some time. Only in 2001, Aaronson~\cite{DBLP:conf/stoc/Aaronson02} proved a query complexity of $\Omega(n^{1/5})$. Subsequent work of Shi improved this bound to $\Omega(n^{1/4})$ and finally to $\Omega(n^{1/3})$(\cite{DBLP:conf/focs/Shi02,DBLP:journals/jacm/AaronsonS04}). As this constitutes a tight bound, indeed one can not do better than Brassard~\etal. That is, given our current axiomatic assumptions about the nature of quantum mechanics.

The bottom line here is as follows. Ignoring practical problems with implementations of large, stable quantum computers, and still requiring a (what now became standard) 128-bit security level gives rise to the following minimal output sizes for hash functions. If only oneway-ness but not collision resistance is required then 256-bits would be enough, for collision resistance at least 384 bits are needed. Of course, these blackbox results might not be the end of the story, dedicated quantum cryptanalytic techniques have not been considered yet. Fast quantum algorithms to compute median and mean values~\cite{DBLP:conf/stoc/Grover98}, and other basic building blocks seem to be an interesting starting point.