# GenericAttacksMerkleDamgaard

### From The ECRYPT Hash Function Website

On this page, we describe attacks that apply on hash function that are designed according to the Merkle-Damgaard principle. Attacks that are even more generic and apply on all hash functions are described on this page

# 1 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
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
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}
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
the analysis of concatenated constructions. Assuming two hash
functions of output size n each whose outputs is concatenated, one
would ideally expect a security of 2^{n} against birthday based
collision search attacks. Generating a 2^{n/2} multicollision for
one of the hash functions is however enough to find a collision in
the concatenated construction. This has a total cost of
2^{n / 2 + log(n)}.

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 such a multicollision idea.

*Antoine Joux*-

**Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions**

- In Proceedings of CRYPTO, LNCS 3152, pp. 306-316, Springer, 2004
- [Electronic Edition] [Bibtex]
**Author :**Antoine Joux**Title :**Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions**In :**In Proceedings of CRYPTO -

*Don Coppersmith*-

**Another Birthday Attack**

- In Proceedings of CRYPTO, LNCS 218, pp. 14-17, Springer, 1985
- [Electronic Edition] [Bibtex]
**Author :**Don Coppersmith**Title :**Another Birthday Attack**In :**In Proceedings of CRYPTO -

# 2 Second preimage attacks

Discoveries about second preimage attacks on iterated hash functions
span more than two decades. Winternitz notes
in 1984 that for messages of length 2^{k}, the same number of
different target hash values will speed-up the search for second
preimages (of potentially different length) to 2^{n - k} trials.

Lai and Massey built up on that and also showed in 1992 that for
first preimage larger than 2^{n / 2}, the effort to find a second
preimage does not grow above 2 * 2^{n / 2}. Preneel further generalized
this by taking storage requirements into account.

*Robert S. Winternitz*-

**A Secure One-Way Hash Function Built from DES**

- In Proceedings of IEEE Symposium on Security and Privacy, , pp. 88-90, 1984
- [Electronic Edition] [Bibtex] [Abstract]
**Author :**Robert S. Winternitz**Title :**A Secure One-Way Hash Function Built from DES**In :**In Proceedings of IEEE Symposium on Security and Privacy -

*Xuejia Lai, James L. Massey*-

**Hash Function Based on Block Ciphers**

- In Proceedings of EUROCRYPT, LNCS 658, pp. 55-70, 1993
- [Electronic Edition] [Bibtex]
**Author :**Xuejia Lai, James L. Massey**Title :**Hash Function Based on Block Ciphers**In :**In Proceedings of EUROCRYPT -

*Bart Preneel*-

**Analysis and Design of Cryptographic Hash Functions**

- Phd Thesis, , 1999
- [Bibtex] [Abstract]
**Author :**Bart Preneel**Title :**Analysis and Design of Cryptographic Hash Functions**In :**Phd Thesis, -

One of the reasons to include the message length as part of the
message to be hashed in constructions since then, is to prevent
these type of attacks. However, Dean describes in 1999 a way
to circumvent this measure by used so-called expandable messages.
Expandable messages are a set of messages of different lengths that
all yield the same intermediate hash value.

Dean's construction only works for compression functions that have
easily constructed fixed-points, i.e. where it is easy to find a
message block and an input chaining value that results into the same
output chaining value. Many popular hash function construction
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
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^{n-k+1}word.

Very recently, Andreeva et al. extended this to cases in which there are multiple (say 2^{t}) first
preimages. Assuming a length of 2^{k} of each of them, it turns out
that finding a single second preimage is equivalent to finding a
second preimage for a message of 2^{k + t} message blocks. Also in
this work it was shown that several constructions that employ dithering as a means to prevent previous generic second preimage fall to this new attack.

*Richard D. Dean*-

**Formal Aspects of Mobile Code Security**

- Phd Thesis, , 1999
- [Bibtex] [Abstract]
**Author :**Richard D. Dean**Title :**Formal Aspects of Mobile Code Security**In :**Phd Thesis, -

*John Kelsey, Bruce Schneier*-

**Second Preimages on n-Bit Hash Functions for Much Less than 2^n Work**

- In Proceedings of EUROCRYPT, LNCS 3494, pp. 474-490, Springer, 2005
- [Electronic Edition] [Bibtex] [Abstract]
**Author :**John Kelsey, Bruce Schneier**Title :**Second Preimages on n-Bit Hash Functions for Much Less than 2^n Work**In :**In Proceedings of EUROCRYPT -

*Elena Andreeva, Charles Bouillaguet, Pierre-Alain Fouque, Jonathan J. Hoch, John Kelsey, Adi Shamir, Sebastien Zimmer*-

**Second Preimage Attacks on Dithered Hash Functions**

- In Proceedings of EUROCRYPT, LNCS 4965, pp. 270-288, Springer, 2008
- [Bibtex] [Abstract]
**Author :**Elena Andreeva, Charles Bouillaguet, Pierre-Alain Fouque, Jonathan J. Hoch, John Kelsey, Adi Shamir, Sebastien Zimmer**Title :**Second Preimage Attacks on Dithered Hash Functions**In :**In Proceedings of EUROCRYPT -

# 3 Preimage attacks

Herding attacks are a special kind of preimage attack, in the sense that an additional assumption is being made for the attack to work. The basic scenario in which herding attacks are applicable is as 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 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.

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^{n}- invocations of h.

For short suffixes, the workfactor for a herding attack on an
iterative hash functions is 2^{(2n - 5) / 3}. 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
attacker, a linking message *S*_{1} 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
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
2^{107} would be needed to compute H. This requires about
2^{60} bits of storage for the required data-structure.
Afterwards, 2^{107} 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
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
needed. Such a fast collision search would need to find a pair
(*m*,*m*^{ * }) such that *h*_{c}(*c**v*_{1},*m*) = *h*_{c}(*c**v*_{2},*m*^{ * }) where the attacker
has little control over the chaining variables *c**v*_{1} and *c**v*_{2}.
Such an algorithm is not known to date.

*John Kelsey, Tadayoshi Kohno*-

**Herding Hash Functions and the Nostradamus Attack**

- In Proceedings of EUROCRYPT, LNCS 4004, pp. 183-200, Springer, 2006
- [Electronic Edition] [Bibtex] [Abstract]
**Author :**John Kelsey, Tadayoshi Kohno**Title :**Herding Hash Functions and the Nostradamus Attack**In :**In Proceedings of EUROCRYPT -