GenericAttacksMerkleDamgaard - Revision history

Fmendel: /* Second preimage attacks */

2008-11-10T13:26:39Z

‎Second preimage attacks

Fmendel: /* Second preimage attacks */

2008-11-10T13:22:13Z

‎Second preimage attacks

Crechberger at 16:39, 25 March 2008

2008-03-25T16:39:41Z

Crechberger at 16:37, 25 March 2008

2008-03-25T16:37:49Z

Crechberger at 16:37, 25 March 2008

2008-03-25T16:37:11Z

Crechberger at 16:19, 25 March 2008

2008-03-25T16:19:23Z

Crechberger at 14:28, 25 March 2008

2008-03-25T14:28:49Z

Crechberger at 09:42, 12 March 2008

2008-03-12T09:42:33Z

Crechberger at 09:38, 12 March 2008

2008-03-12T09:38:19Z

Crechberger at 08:37, 12 March 2008

2008-03-12T08:37:57Z

@@ Line 168: / Line 168: @@
    title = {Second Preimage Attacks on Dithered Hash Functions},
    booktitle = {EUROCRYPT},
-   year = {2008},
+   editor    = {Nigel P. Smart},
-   editor = {Nigel Smart},
+  volume    = {4965},
    series = {LNCS},
    publisher = {Springer},
    abstract = {We develop a new generic long-message second preimage attack, based on combining the techniques in the second preimage attacks of Dean and Kelsey and Schneier with the herding attack of Kelsey and Kohno. We show that these generic attacks apply to hash functions using the Merkle-Damgard construction with only slightly more work than the previously known attack, but allow enormously more control of the contents of the second preimage found. Additionally, we show that our new attack applies to several hash function constructions which are not vulnerable to the previously known attack, including the dithered hash proposal of Rivest, Shoup's UOWHF and the ROX hash construction. We analyze the properties of the dithering sequence used in, and develop a time-memory tradeoff which allows us to apply our second preimage attack to a wide range of dithering sequences, including sequences which are much stronger than those in Rivest's proposals. Finally, we show that both the existing second preimage attacks and our new attack can be applied even more efficiently to multiple target messages; in general, given a set of many target messages with a total of 2^R message blocks, these second preimage attacks can find a second preimage for one of those target messages with no more work than would be necessary to find a second preimage for a single target message of 2^R message blocks.},
+}
 </bibtex>

@@ Line 87: / Line 87: @@
+}
 </bibtex>
 <bibtex>
 @inproceedings{eurocryptLaiM92,
@@ Line 96: / Line 97: @@
    abstract  = {},
    url        = {http://link.springer.de/link/service/series/0558/bibs/0658/06580055.htm},
+}
 </bibtex>
 <bibtex>
 @phdthesis{phdPreneel93,

@@ Line 26: / Line 26: @@
 one of the hash functions is however enough to find a collision in
 the concatenated construction. This has a total cost of
-^{n/2+log(n)}.
+<math>2^{n/2+log(n)}</math>.
 As a historic note, it should be mentioned that Coppersmith's attack
@@ Line 202: / Line 202: @@
 <math>2^{107}</math> would be needed to compute H. This requires about
 <math>2^{60}</math> bits of storage for the required data-structure.
-Afterwards, <math>2^{107}</math> effort would be needed to compute $S$ given a
+Afterwards, <math>2^{107}</math> effort would be needed to compute S given a
-particular $P$, by search for a linking message block. This amounts
+particular P, by search for a linking message block. This amounts
 to a total running time of <math>2^{108}</math>. If partial knowledge of P
 exists the attack can be much faster.

@@ Line 18: / Line 18: @@
 different messages consisting of t message blocks can be
 constructed that all lead to the same hash value.
 An application of Joux's multicollisions is
@@ Line 187: / Line 186: @@
 she is given P, it should not be possible to find S such that
 h(P||S)=H is considerably faster than by 2<sup>n</sup>- invocations of h.
 For short suffixes, the workfactor for a herding attack on an
@@ Line 198: / Line 196: @@
 digest H at its end <math>S_2</math>, then the result string S such that
 h(P||S)=H is S=S_1 || S_2.
 Besides observing this theoretical weakness, we can also consider

@@ Line 127: / Line 127: @@
 again example messages can be constructed and hence the search for
 second preimages is again of order 2<sup>n-k+1</sup>word.
 <bibtex>
 @phdthesis{phdDean99,
@@ Line 149: / Line 156: @@
    isbn = {3-540-25910-4},
    url = {http://dx.doi.org/10.1007/11426639_28},
+}
 </bibtex>
@@ Line 159: / Line 179: @@
 follows. At the cost of a pre-computation step, an attacker can
 commit to a digest of a hash function without yet knowing the input.
-In \cite{Kelsey2005HerdingHashFunctionsa}, this attack is described
+In the work of Kelsey and Kohno, this attack is described
 and shows that for all iterated hash functions the complexity is
 less than one would expect from an ideal hash function.
-\begin{definition}[Resistance against herding attacks]
+Resistance against herding attacks
 Given a hash function h, the attacker may choose a digest H. If
 she is given P, it should not be possible to find S such that
 h(P||S)=H is considerably faster than by 2<sup>n</sup>- invocations of h.
-\end{definition}
 For short suffixes, the workfactor for a herding attack on an
-iterative hash functions as shown in
+iterative hash functions is <math>2^{(2n-5)/3}</math>. First a
 so-called diamond structure is built in a precomputation phase that
-results in a particular digest $H$. After $P$ is given to the
+results in a particular digest H. After P is given to the
-attacker, a linking message $S_1$ is searched that connects $P$ with
+attacker, a linking message <math>S_1</math> is searched that connects P with
 one of the edges of the diamond structure. Let's denote the path
 between the found entry point in the diamond structure and the
-digest $H$ at its end $S_2$, then the result string $S$ such that
+digest H at its end <math>S_2</math>, then the result string S such that
-$h(P||S)=H$ is $S=S_1 || S_2$.
+h(P||S)=H is S=S_1 || S_2.
 Besides observing this theoretical weakness, we can also consider
 the feasibility in practice of this attack. In the case of SHA-1,
-and without partial knowledge of $P$, a pre-computation effort of
+and without partial knowledge of P, a pre-computation effort of
-$2^{107}$ would be needed to compute $H$. This requires about
+<math>2^{107}</math> would be needed to compute H. This requires about
-$2^{60}$ bits of storage for the required data-structure.
+<math>2^{60}</math> bits of storage for the required data-structure.
-Afterwards, $2^{107}$ effort would be needed to compute $S$ given a
+Afterwards, <math>2^{107}</math> effort would be needed to compute $S$ given a
 particular $P$, by search for a linking message block. This amounts
-to a total running time of $2^{108}$. If partial knowledge of $P$
+to a total running time of <math>2^{108}</math>. If partial knowledge of P
-exists (as is the case when facing the challenge of predicting the
+exists the attack can be much faster.
 In order to exploit dedicated collision-search attacks on SHA-1, a
-collision search which is faster than about $2^{55.5}$ would be
+collision search which is faster than about <math>2^{55.5}</math> would be
 needed. Such a fast collision search would need to find a pair
-$(m,m^*)$  such that $h_c(cv_1,m)=h_c(cv_2,m^*)$ where the attacker
+<math>(m,m^*)</math>  such that <math>h_c(cv_1,m)=h_c(cv_2,m^*)</math> where the attacker
-has little control over the chaining variables $cv_1$ and $cv_2$.
+has little control over the chaining variables <math>cv_1</math> and <math>cv_2</math>.
 Such an algorithm is not known to date.

@@ Line 67: / Line 67: @@
 = Second preimage attacks =
 Discoveries about second preimage attacks on iterated hash functions
-span the last three decades. Merkle notes in 1979 that for messages
+span more than two decades. Winternitz notes
-of length 2<sup>k</sup>, the same number of different target hash values
+in 1984 that for messages of length <math>2^k</math>, the same number of
-will speed-up the search for second preimages (of potentially
+different target hash values will speed-up the search for second
-different length) to 2<sup>n-k</sup> trials. See also extensions of Winternitz, Lai and Massey, and Preneel.
+preimages (of potentially different length) to <math>2^{n-k}</math> trials.
@@ Line 86: / Line 122: @@
 indeed do have this property. In 2005, Kelsey and Schneier managed
 to remove this constraint and gave an algorithm to construct
-expandable messages for any compression function with an $n$-bit
+expandable messages for any compression function with an n-bit
 intermediate value. Their idea is to construct multicollisions out
 of collisions between message blocks of different length. From that,
 again example messages can be constructed and hence the search for
 second preimages is again of order 2<sup>n-k+1</sup>word.
+<bibtex>
 <bibtex>
 @inproceedings{eurocryptKelseyS05,

@@ Line 8: / Line 8: @@
 boxes at this point), multi-collisions can be constructed more
 efficiently. Ideally, the effort to find 2<sup>t</sup> single collisions
-should grow according to the birthday paradox: for t \ll n/2 the
+should grow according to the birthday paradox: for t much smaller than n/2 the
 effort should grow almost linearly with each additional collision.
 What Joux showed in 2004 is that for iterated constructions
@@ Line 22: / Line 22: @@
 An application of Joux's multicollisions is
 the analysis of concatenated constructions. Assuming two hash
-functions of output size $n$ each whose outputs is concatenated, one
+functions of output size n each whose outputs is concatenated, one
 would ideally expect a security of 2<sup>n</sup> against birthday based
 collision search attacks. Generating a 2<sup>n/2</sup> multicollision for
@@ Line 31: / Line 31: @@
 As a historic note, it should be mentioned that Coppersmith's attack
 in 1985 on the Davies-Price
-variant of Rabin's scheme builds already on exactly
+variant of Rabin's scheme builds already on such a
-this idea.
+multicollision idea.
+<bibtex>
 <bibtex>
-@article{titNandiS07,
+@inproceedings{cryptoCoppersmith85,
-   author    = {Mridul Nandi and
+   author = {Don Coppersmith},
-               Douglas R. Stinson},
+   title = {Another Birthday Attack},
-   title     = {Multicollision Attacks on Some Generalized Sequential Hash
+  booktitle = {CRYPTO},
-               Functions},
+   year = {1985},
-   journal   = {IEEE Transactions on Information Theory},
+   pages = {14-17},
-   volume    = {53},
+  editor = {Hugh C. Williams},
-   number    = {2},
+   volume = {218},
-   year      = {2007},
+   series = {LNCS},
-   pages     = {759-767},
+   publisher = {Springer},
-   url       = {http://dx.doi.org/10.1109/TIT.2006.889721},
+   isbn = {3-540-16463-4},
-  bibsource = {DBLP, http://dblp.uni-trier.de},
+   url = {http://link.springer.de/link/service/series/0558/bibs/0218/02180014.htm},
+}
 </bibtex>

@@ Line 82: / Line 82: @@
 @inproceedings{eurocryptKelseyS05,
    author = {John Kelsey and Bruce Schneier},
-   title = {Second Preimages on n-Bit Hash Functions for Much Less than 2$^{\mbox{n}}$ Work},
+   title = {Second Preimages on n-Bit Hash Functions for Much Less than 2^n Work},
    booktitle = {EUROCRYPT},
    year = {2005},
@@ Line 108: / Line 108: @@
 \begin{definition}[Resistance against herding attacks]
-Given a hash function $h$, the attacker may choose a digest $H$. If
+Given a hash function h, the attacker may choose a digest H. If
-she is given $P$, it should not be possible to find $S$ such that
+she is given P, it should not be possible to find S such that
-$h(P||S)=H$ is considerably faster than by $2^n$ invocations of $h$.
+h(P||S)=H is considerably faster than by 2<sup>n</sup>- invocations of h.
 \end{definition}

@@ Line 3: / Line 3: @@
-= Collision style Attacks =
+= Collision style attacks =
 In case a hash function is not considered as a black box, but built
 from compression functions (which in turn are considered as black
 boxes at this point), multi-collisions can be constructed more
-efficiently. Ideally, the effort to find $2^t$ single collisions
+efficiently. Ideally, the effort to find 2^t single collisions
-should grow according to the birthday paradox: for $t \ll n/2$ the
+should grow according to the birthday paradox: for t \ll n/2 the
 effort should grow almost linearly with each additional collision.
 What Joux showed in 2004~\cite{} is that for iterated constructions
-the effort to find a $2^t$-multicollision is actually $t*2^{n/2}$.
+the effort to find a $2^t$-multicollision is actually t*2^{n/2}.
 The idea is to simply concatenate $t$ collisions found by a birthday
 attack (or by any other mean like shortcut attacks for that matter).
 Since each collision allows to pick a message out of a pair of
-messages, and this choice is available $t$ times, a set of $2^t$
+messages, and this choice is available t times, a set of 2^t
-different messages consisting of $t$ message blocks can be
+different messages consisting of t message blocks can be
 constructed that all lead to the same hash value.