GenericAttacksHash - Revision history

Crechberger at 11:33, 25 March 2008

2008-03-25T11:33:03Z

Crechberger at 11:27, 25 March 2008

2008-03-25T11:27:54Z

Crechberger at 11:00, 25 March 2008

2008-03-25T11:00:51Z

Crechberger at 20:17, 21 March 2008

2008-03-21T20:17:22Z

Crechberger at 10:56, 21 March 2008

2008-03-21T10:56:21Z

Crechberger at 09:05, 17 March 2008

2008-03-17T09:05:07Z

Crechberger at 08:45, 17 March 2008

2008-03-17T08:45:16Z

Crechberger at 08:16, 17 March 2008

2008-03-17T08:16:54Z

Crechberger at 12:45, 11 March 2008

2008-03-11T12:45:57Z

Crechberger at 12:44, 11 March 2008

2008-03-11T12:44:39Z

@@ Line 297: / Line 297: @@
 Ä(pn) queries.},
    url        = {http://doi.acm.org/10.1145/1008731.1008735},
+}
 </bibtex>

@@ Line 169: / Line 169: @@
    year      = {1996},
    pages     = {212--219},
    url        = {http://doi.acm.org/10.1145/237814.237866},
+}
 </bibtex>

@@ Line 42: / Line 42: @@
+}
 </bibtex>
 <bibtex>
 @article{cryptologiaYuval79,
@@ Line 98: / Line 96: @@
+}
 </bibtex>
 <bibtex>
 @article{jocWiener04,
@@ Line 163: / Line 160: @@
 mean values by Grover, and other basic building
 blocks seem to be an interesting starting point.

@@ Line 75: / Line 75: @@
 enables an attacker to construct meaningful collisions.
 <bibtex>
 @article{jocOorschotW99,
@@ Line 133: / Line 141: @@
 Tapp from 1997. This combination
 of Grover's algorithm with the birthday effect yields a runtime of 2<sup>n/3</sup> for a hash function with n bit output size. The
-algorithm requires \Theta(n<sup>1/3</sup>log n) classical bits of
+algorithm requires <math>\Theta(n^{1/3}log n)</math> 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 proved a
-query complexity of \Omega(n<sup>1/5</sup>). Subsequent work of Shi
+query complexity of <math>\Omega(n^{1/5})</math>. Subsequent work of Shi
-improved this bound to \Omega(n<sup>1/4</sup>) and finally to
+improved this bound to <math>\Omega(n^{1/4})</math> and finally to
-\Omega(n<sup>1/3)</sup>. As this constitutes a tight bound, indeed one can not do better than
+<math>\Omega(n^{1/3})</math>. As this constitutes a tight bound, indeed one can not do better than
 Brassard et al. That is, given our current axiomatic assumptions
 about the nature of quantum mechanics.

@@ Line 42: / Line 42: @@
+}
 </bibtex>
 <bibtex>
-@inproceedings{fseHochS06,
+@article{cryptologiaYuval79,
-   author    = {Jonathan J. Hoch and
+   author    = {Gideon Yuval},
-               Adi Shamir},
+   title     = {How to Swindle Rabin},
-   title     = {Breaking the ICE - Finding Multicollisions in Iterated Concatenated
+   journal   = {Cryptologia},
-               and Expanded (ICE) Hash Functions},
+   volume    = {3},
-   booktitle = {FSE},
+   year      = {1979},
-   year      = {2006},
+   pages     = {187-189},
+}
 </bibtex>
@@ Line 100: / Line 80: @@
 @article{jocOorschotW99,
    author    = {Paul C. van Oorschot and Michael J. Wiener},
-   title     = {{Parallel Collision Search with Cryptanalytic Applications}},
+   title     = {Parallel Collision Search with Cryptanalytic Applications},
    journal   = {J. Cryptology},
    volume    = {12},
@@ Line 134: / Line 114: @@
 One of the celebrated results in quantum algorithms is
 Grover's from 1996: The search for a particular element in an unordered database of size
-r takes at most O(r<sup>1/2</sup>), an actual algorithm is provided that
+r takes at most O(r<sup>1/2</sup>), an actual algorithm is provided. Matching lower bounds exist for this problem as
 well (see Boyer et al. and Zalka). This
 algorithm is of wide interest as it does not rely on a particular

@@ Line 11: / Line 11: @@
 <bibtex>
 @phdthesis{phdMerkle79,
-   author    = {Ralf Merkle},
+   author    = {Ralf C. Merkle},
    title     = {Secrecy, authentication, and public key systems},
    year      = {1979},

@@ Line 2: / Line 2: @@
 The resistance of a hash function to collision and (second) preimage
-attacks depends in the first place on the length $n$ of the hash
+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
@@ Line 8: / Line 8: @@
 given 2<sup>k</sup> distinct target hashes, preimages can be found after
 trying about 2<sup>n-k</sup> different
-messages. this is first described in the thesis of Merkle, pages 12-13.
+messages. This is first described in the thesis of Merkle, pages 12-13.
 = Collision attacks =
@@ Line 78: / Line 85: @@
 with only 2<sup>n/2</sup> evaluations of h. A birthday attack works as
 follows:
-. Pick any message m and compute h(m).
+* Pick any message m and compute h(m).
-. Update list L. Check if h(m) is in the list L.
+* Update list L. Check if h(m) is in the list L.
-.1.   if (h(m),m) is already in L, a colliding message pair has been found.
+**   if (h(m),m) is already in L, a colliding message pair has been found.
-.2    else save the pair (h(m),m) in the list L and go back to step 1.
+**    else save the pair (h(m),m) in the list L and go back to step 1.
 From the birthday paradox we know that we can expect to find a
 matching entry, after performing about 2<sup>n/2</sup> hash evaluations.
@@ Line 154: / Line 161: @@
 query complexity of \Omega(n<sup>1/5</sup>). Subsequent work of Shi
 improved this bound to \Omega(n<sup>1/4</sup>) and finally to
-\Omega(n<sup>1/3</sup. As this constitutes a tight bound, indeed one can not do better than
+\Omega(n<sup>1/3)</sup>. As this constitutes a tight bound, indeed one can not do better than
-Brassard~\etal. That is, given our current axiomatic assumptions
+Brassard et al. That is, given our current axiomatic assumptions
 about the nature of quantum mechanics.

@@ Line 14: / Line 14: @@
 Yuval in 1979, finding collisions
 requires a much smaller number of trials: about 2<sup>n/2</sup>, as
-described subsequently in Sect.~\ref{sec:birth}. As a result, hash
+described subsequently. As a result, hash
 functions producing less than 160 bits of output are currently
 considered inherently insecure. Moreover, if the internal structure
@@ Line 70: / Line 70: @@
 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
+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
+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
+<sup>-n</sup> of the pairs (m,m*) satisfies h(m) = h(m*), one can
-expect to find a colliding message pair after trying about $2^n$
+expect to find a colliding message pair after trying about 2<sup>n</sup>,
-arbitrary message pairs, \cf~\eqref{eqn:collision}. Nevertheless, it
+arbitrary message pairs. Nevertheless, it
-follows from the birthday paradox that one can check $2^n$ pairs
+follows from the birthday paradox that one can check 2<sup>n</sup> pairs
-with only $2^{n/2}$ evaluations of $h$. A birthday attack works as
+with only 2<sup>n/2</sup> evaluations of h. A birthday attack works as
 follows:
-\begin{enumerate}
+. Pick any message m and compute h(m).
-  \item Pick any message $m$ and compute $h(m)$.
+. Update list L. Check if h(m) is in the list L.
-  \item Update list $L$ %Check if $h(m)$ is in the list $L$.
+.1.   if (h(m),m) is already in L, a colliding message pair has been found.
-    \begin{itemize}
+.2    else save the pair (h(m),m) in the list L and go back to step 1.
 From the birthday paradox we know that we can expect to find a
-matching entry, after performing about $2^{n/2}$ hash evaluations.
+matching entry, after performing about 2<sup>n/2</sup> 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
+messages. Hence, as pointed out by Yuval, this method
 enables an attacker to construct meaningful collisions.
@@ Line 104: / Line 100: @@
    pages     = {1-28},
    url        = {http://link.springer.de/link/service/journals/00145/bibs/12n1p1.html},
-   abstract  = {A simple new technique of parallelizing methods for solving search problems which seek collisions in pseudorandom walks is presented. This technique can be adapted to a wide range of cryptanalytic problems which can be reduced to finding collisions. General constructions are given showing how to adapt the technique to finding discrete logarithms in cyclic groups, finding meaningful collisions in hash functions, and performing meet-in-the-middle attacks such as a known-plaintext attack on double encryption. The new technique greatly extends the reach of practical attacks, providing the most cost-effective means known to date for defeating: the small subgroup used in certain schemes based on discrete logarithms such as Schnorr, DSA, and elliptic curve cryptosystems; hash functions such as MD5, RIPEMD, SHA-1, MDC-2, and MDC-4; and double encryption and three-key triple encryption. The practical significance of the technique is illustrated by giving the design for three $10 million custom machines which could be built with current technology: one finds elliptic curve logarithms in $GF(2^{155})$ thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days, the second finds MD5 collisions in expected time 21 days, and the last recovers a double-DES key from two known plaintexts in expected time 4 years, which is four orders of magnitude faster than the conventional meet-in-the-middle attack on double-DES. Based on this attack, double-DES offers only 17 more bits of security than single-DES.},
+   abstract  = {A simple new technique of parallelizing methods for solving search problems which seek collisions in pseudorandom walks is presented. This technique can be adapted to a wide range of cryptanalytic problems which can be reduced to finding collisions. General constructions are given showing how to adapt the technique to finding discrete logarithms in cyclic groups, finding meaningful collisions in hash functions, and performing meet-in-the-middle attacks such as a known-plaintext attack on double encryption. The new technique greatly extends the reach of practical attacks, providing the most cost-effective means known to date for defeating: the small subgroup used in certain schemes based on discrete logarithms such as Schnorr, DSA, and elliptic curve cryptosystems; hash functions such as MD5, RIPEMD, SHA-1, MDC-2, and MDC-4; and double encryption and three-key triple encryption. The practical significance of the technique is illustrated by giving the design for three $10 million custom machines which could be built with current technology: one finds elliptic curve logarithms in GF2<sup>155</sup>) thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days, the second finds MD5 collisions in expected time 21 days, and the last recovers a double-DES key from two known plaintexts in expected time 4 years, which is four orders of magnitude faster than the conventional meet-in-the-middle attack on double-DES. Based on this attack, double-DES offers only 17 more bits of security than single-DES.},
+}
 </bibtex>
@@ Line 130: / Line 126: @@
 One of the celebrated results in quantum algorithms is
-Grover's~\cite{Grover1996AFastQuantum} from 1996.
+Grover's from 1996: The search for a particular element in an unordered database of size
-%(building up on pioneering work of Deutsch, etc..~\cite{}):
+r takes at most O(r<sup>1/2</sup>), an actual algorithm is provided that
 uses xxx memory. Matching lower bounds exist for this problem as
-well~\cite{boyer98tight,zalka99GroversQuantumSearching}. This
+well (see Boyer et al. and Zalka). This
 algorithm is of wide interest as it does not rely on a particular
 structure of the elements in the search space.
@@ Line 142: / Line 136: @@
 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}$
+these types of generic attacks is lowered from 2<sup>n</sup> to 2<sup>n/2</sup>
 in the quantum setting.
@@ Line 148: / Line 142: @@
 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
+dimensions) 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
+Tapp from 1997. This combination
-of Grover's algorithm with the birthday effect yields a runtime of
+of Grover's algorithm with the birthday effect yields a runtime of 2<sup>n/3</sup> for a hash function with n bit output size. The
-$2^{n/3}$ for a hash function with $n$ bit output size. The
+algorithm requires \Theta(n<sup>1/3</sup>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
+Only in 2001, Aaronson proved a
-query complexity of $\Omega(n^{1/5})$. Subsequent work of Shi
+query complexity of \Omega(n<sup>1/5</sup>). Subsequent work of Shi
-improved this bound to $\Omega(n^{1/4})$ and finally to
+improved this bound to \Omega(n<sup>1/4</sup>) and finally to
-$\Omega(n^{1/3})$(\cite{DBLP:conf/focs/Shi02,DBLP:journals/jacm/AaronsonS04}).
+\Omega(n<sup>1/3</sup. 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.
@@ Line 175: / Line 167: @@
 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
+mean values by Grover, and other basic building
 blocks seem to be an interesting starting point.

@@ Line 5: / Line 5: @@
 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
+trying out about 2<sup>n</sup> different messages. In case an adversary is
-given $2^k$ distinct target hashes, preimages can be found after
+given 2^<sup>k</sup> distinct target hashes, preimages can be found after
-trying about $2^{n-k}$ different
+trying about 2<sup>n-k</sup> different
-messages~\cite[Chapter 2, pages 12-13]{Merkle79SecrecyAuthenticationAnd} %, chapter 2, pages 12-13}.
+messages. this is first described in the thesis of Merkle, pages 12-13.
 = Collision attacks =