Difference between revisions of "GenericAttacksMerkleDamgaard"

From The ECRYPT Hash Function Website
(Second preimage attacks)
 
(11 intermediate revisions by 3 users not shown)
Line 3: Line 3:
  
  
= Collision style Attacks =
+
= Collision style attacks =
 
In case a hash function is not considered as a black box, but built
 
In case a hash function is not considered as a black box, but built
 
from compression functions (which in turn are considered as black
 
from compression functions (which in turn are considered as black
 
boxes at this point), multi-collisions can be constructed more
 
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<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.
 
effort should grow almost linearly with each additional collision.
What Joux showed in 2004~\cite{} is that for iterated constructions
+
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 effort to find a 2<sup>t</sup>-multicollision is actually t*2<sup>n/2</sup>
The idea is to simply concatenate $t$ collisions found by a birthday
+
The idea is to simply concatenate t collisions found by a birthday
 
attack (or by any other mean like shortcut attacks for that matter).
 
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
 
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<sup>t</sup>
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.
 
constructed that all lead to the same hash value.
  
 
+
An application of Joux's multicollisions is
An application of Joux's multicollisions (also given in~\cite{}) is
 
 
the analysis of concatenated constructions. Assuming two hash
 
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^n$ against birthday based
+
would ideally expect a security of 2<sup>n</sup> against birthday based
collision search attacks. Generating a $2^{n/2}$ multicollision for
+
collision search attacks. Generating a 2<sup>n/2</sup> multicollision for
 
one of the hash functions is however enough to find a collision in
 
one of the hash functions is however enough to find a collision in
 
the concatenated construction. This has a total cost of
 
the concatenated construction. This has a total cost of
$2^{n/2+log(n)}$.
+
<math>2^{n/2+log(n)}</math>.
  
 
As a historic note, it should be mentioned that Coppersmith's attack
 
As a historic note, it should be mentioned that Coppersmith's attack
in 1985~\cite{DBLP:conf/crypto/Coppersmith85} on the Davies-Price
+
in 1985 on the Davies-Price
variant~\cite{} of Rabin's scheme~\cite{} builds already on exactly
+
variant of Rabin's scheme builds already on such a
this idea.
+
multicollision idea.
 +
<bibtex>
 +
@inproceedings{cryptoJoux04,
 +
  author    = {Antoine Joux},
 +
  title    = {Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions},
 +
  booktitle = {CRYPTO},
 +
  year      = {2004},
 +
  pages    = {306-316},
 +
  url        = {http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3152{\&}spage=306},
 +
  editor    = {Matthew K. Franklin},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {3152},
 +
  isbn      = {3-540-22668-0},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{cryptoCoppersmith85,
 +
  author = {Don Coppersmith},
 +
  title = {Another Birthday Attack},
 +
  booktitle = {CRYPTO},
 +
  year = {1985},
 +
  pages = {14-17},
 +
  editor = {Hugh C. Williams},
 +
  volume = {218},
 +
  series = {LNCS},
 +
  publisher = {Springer},
 +
  isbn = {3-540-16463-4},
 +
  url = {http://link.springer.de/link/service/series/0558/bibs/0218/02180014.htm},
 +
}
 +
</bibtex>
 +
 
 +
 
 +
= 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 <math>2^k</math>, the same number of
 +
different target hash values will speed-up the search for second
 +
preimages (of potentially different length) to <math>2^{n-k}</math> trials.
 +
 
 +
Lai and Massey built up on that and also showed in 1992 that for
 +
first preimage larger than <math>2^{n/2}</math>, the effort to find a second
 +
preimage does not grow above <math>2 * 2^{n/2}</math>. Preneel further generalized
 +
this by taking storage requirements into account.
  
 
<bibtex>
 
<bibtex>
@article{titNandiS07,
+
@inproceedings{spWinternitz84,
   author    = {Mridul Nandi and
+
   author    = {Robert S. Winternitz},
              Douglas R. Stinson},
+
   title    = {A Secure One-Way Hash Function Built from DES},
   title    = {Multicollision Attacks on Some Generalized Sequential Hash
+
   booktitle = {IEEE Symposium on Security and Privacy},
              Functions},
+
   year      = {1984},
   journal  = {IEEE Transactions on Information Theory},
+
   abstract  = {Applying a one-way hash function is a useful preliminary to digitally signing a message, both for security and efficiency. Several proposals for building such a function out of DES have been shown to be insecure. This talk studies a proposal due to Davies, and provides some evidence for its security. We prove security under a black box model. That is, we consider algorithms which call the encryption function via an oracle, and calculate the expected running time for a randomly chosen block cipher. This mirrors attacks on the system which do not rely on special properties of the encryption function. Under this model, we show that, given Y, finding a message hashing to y requires 0(264) encryptions. However, if the opponent is also given some legitimately signed messages, a speedup is possible, proportional to the total length of such material. This can be foiled by adding a running count to each block. The resulting system provably requires O(264) steps to break, even given large amounts of signed material. By modifying the model, these results can be strengthened to show that tbe existence of weak keys and the complementation property of DES do not help the forger. Any successful attack would have to use more subtle properties of DES.},
  volume    = {53},
+
  url        = {http://doi.ieeecomputersociety.org/10.1109/SP.1984.10027},
  number    = {2},
+
  pages    = {88-90},
   year      = {2007},
 
   pages    = {759-767},
 
  url      = {http://dx.doi.org/10.1109/TIT.2006.889721},
 
  bibsource = {DBLP, http://dblp.uni-trier.de},
 
  abstract  = {A multicollision for a function is a set of inputs whose outputs are all identical. A. Joux showed multicollision attacks on the classical iterated hash function. He also showed how these multicollision attacks can be used to get a collision attack on a concatenated hash function. In this paper, we study multicollision attacks in a more general class of hash functions which we term "generalized sequential hash functions." We show that multicollision attacks exist for this class of hash functions provided that every message block is used at most twice in the computation of the message digest.}
 
 
}
 
}
 
</bibtex>
 
</bibtex>
  
 +
<bibtex>
 +
@inproceedings{eurocryptLaiM92,
 +
  author    = {Xuejia Lai and James L. Massey},
 +
  title    = {Hash Function Based on Block Ciphers},
 +
  booktitle = {EUROCRYPT},
 +
  year      = {1992},
 +
  pages    = {55-70},
 +
  abstract  = {},
 +
  url        = {http://link.springer.de/link/service/series/0558/bibs/0658/06580055.htm},
 +
  editor    = {Rainer A. Rueppel},
 +
  series    = {LNCS},
 +
  volume    = {658},
 +
  year      = {1993},
 +
}
 +
</bibtex>
  
= Second Preimage Attacks =
+
<bibtex>
Discoveries about second preimage attacks on iterated hash functions
+
@phdthesis{phdPreneel93,
span the last three decades. Merkle notes in 1979 that for messages
+
  author    = {Bart Preneel},
of length $2^k$, the same number of different target hash values
+
  title    = {Analysis and Design of Cryptographic Hash Functions},
will speed-up the search for second preimages (of potentially
+
  abstract  = {The subject of this thesis is the study of cryptographic hash functions. The importance of hash functions for protecting the authenticity of information is demonstrated. Applications include integrity protection, conventional message authentication and digital signatures. Theoretical results on cryptographic hash functions are reviewed. The information theoretic approach to authentication is described, and the practicality of schemes based on universal hash functions is studied. An overview is given of the complexity theoretic definitions and constructions. The main contribution of this thesis lies in the study of practical constructions for hash functions. A general model for hash functions is proposed and a taxonomy for attacks is presented. Then all schemes in the literature are divided into three classes: hash functions based on block ciphers, hash functions based on modular arithmetic and dedicated hash functions. An overview is given of existing attacks, new attacks are demonstrated, and new schemes are proposed. The study of basic building blocks of cryptographic hash functions leads to the study of the cryptographic properties of Boolean functions. New criteria are defined and functions satisfying new and existing criteria are studied.},
different length) to $2^{n-k}$ trials. \todo{Winternitz,lai}.
+
  year      = {1999},
 +
}
 +
</bibtex>
  
  
 
One of the reasons to include the message length as part of the
 
One of the reasons to include the message length as part of the
 
message to be hashed in constructions since then, is to prevent
 
message to be hashed in constructions since then, is to prevent
these type of attacks. However, Dean~\cite{} describes in 1999 a way
+
these type of attacks. However, Dean describes in 1999 a way
 
to circumvent this measure by used so-called expandable messages.
 
to circumvent this measure by used so-called expandable messages.
 
Expandable messages are a set of messages of different lengths that
 
Expandable messages are a set of messages of different lengths that
Line 68: Line 122:
  
 
Dean's construction only works for compression functions that have
 
Dean's construction only works for compression functions that have
easily constructed fixed-points, \ie where it is easy to find a
+
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
 
message block and an input chaining value that results into the same
 
output chaining value. Many popular hash function construction
 
output chaining value. Many popular hash function construction
 
indeed do have this property. In 2005, Kelsey and Schneier managed
 
indeed do have this property. In 2005, Kelsey and Schneier managed
 
to remove this constraint and gave an algorithm to construct
 
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
 
intermediate value. Their idea is to construct multicollisions out
 
of collisions between message blocks of different length. From that,
 
of collisions between message blocks of different length. From that,
 
again example messages can be constructed and hence the search for
 
again example messages can be constructed and hence the search for
second preimages is again of order $2^{n-k+1}$ word.
+
second preimages is again of order 2<sup>n-k+1</sup>word.
  
 +
Very recently, Andreeva et al. extended this to cases in which there are multiple (say <math>2^t</math>) first
 +
preimages. Assuming a length of <math>2^k</math> of each of them, it turns out
 +
that finding a single second preimage is equivalent to finding a
 +
second preimage for a message of <math>2^{k+t}</math> 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.
 +
 +
<bibtex>
 +
@phdthesis{phdDean99,
 +
  author    = {Richard D. Dean},
 +
  title    = {Formal Aspects of Mobile Code Security},
 +
  abstract  = {We believe that formal methods of all kinds are critical to mobile code security, as one route to gaining the assurance level necessary for running potentially hostile code on a routine basis. We begin by examining Java, and understanding the weaknesses in its architecture, on both design and implementation levels. Identifying dynamic linking as a key problem, we produce a formal model of linking, and prove desirable properties about our model. This investigation leads to a deep understanding of the underlying problem. Finally, we turn our attention to cryptographic hash functions, and their analysis with binary decision diagrams (BDDs). We show that three commonly used hash functions (MD4, MD5, and SHA-1) do not offer ideal strength against second preimages. The ability of a cryptographic hash function to resist the finding of second preimages is critical for its use in digital signature schemes: a second preimage enables the forgery of digital signatures, which would undermine confidence in digitally signed mobile code. Our results show that modern theorem provers and BDD-based reasoning tools are effective for reasoning about some of the key problems facing mobile code security today.},
 +
  year      = {1999},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{eurocryptKelseyS05,
 +
  author = {John Kelsey and Bruce Schneier},
 +
  title = {Second Preimages on n-Bit Hash Functions for Much Less than 2^n Work},
 +
  booktitle = {EUROCRYPT},
 +
  year = {2005},
 +
  pages = {474-490},
 +
  abstract = {We expand a previous result of Dean [Dea99] to provide a second preimage attack on all n-bit iterated hash functions with Damgård-Merkle strengthening and n-bit intermediate states, allowing a second preimage to be found for a 2k-message-block message with about k × 2n/2+1 + 2n – k + 1 work. Using RIPEMD-160 as an example, our attack can find a second preimage for a 260 byte message in about 2106 work, rather than the previously expected 2160 work. We also provide slightly cheaper ways to find multicollisions than the method of Joux [Jou04]. Both of these results are based on expandable messages–patterns for producing messages of varying length, which all collide on the intermediate hash result immediately after processing the message. We provide an algorithm for finding expandable messages for any n-bit hash function built using the Damgård-Merkle construction, which requires only a small multiple of the work done to find a single collision in the hash function.},
 +
  editor = {Ronald Cramer},
 +
  volume = {3494},
 +
  series = {LNCS},
 +
  publisher = {Springer},
 +
  isbn = {3-540-25910-4},
 +
  url = {http://dx.doi.org/10.1007/11426639_28},
 +
}
 +
</bibtex>
 
<bibtex>
 
<bibtex>
@inproceedings{Kelsey2005SecondPreimageOn,
+
@inproceedings{eurocryptAndreevaBFHKSZ08,
   author    = {John Kelsey and Bruce Schneier},
+
   author    = {Elena Andreeva and Charles Bouillaguet and Pierre-Alain Fouque and Jonathan J. Hoch and John Kelsey and Adi Shamir and Sebastien Zimmer},
   title     = {Second Preimages on n-Bit Hash Functions for Much Less than $2^n$ Work.},
+
   title = {Second Preimage Attacks on Dithered Hash Functions},
 
   booktitle = {EUROCRYPT},
 
   booktitle = {EUROCRYPT},
   year      = {2005},
+
  editor    = {Nigel P. Smart},
   pages    = {474-490},
+
  volume    = {4965},
   url      = {http://dx.doi.org/10.1007/11426639_28},
+
   year      = {2008},
 +
   series = {LNCS},
 +
   pages    = {270-288},
 
   publisher = {Springer},
 
   publisher = {Springer},
  series    = {LNCS},
+
   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.},
  volume    = {3494},
 
   abstract = {We expand a previous result of Dean [Dea99] to provide a second preimage attack on all n-bit iterated hash functions with Damgård-Merkle strengthening and n-bit intermediate states, allowing a second preimage to be found for a 2<sup>k</sup>-message-block message with about k × 2<sup>n/2+1</sup> + 2<sup>n - k + 1</sup> work. Using RIPEMD-160 as an example, our attack can find a second preimage for a 2<sup>60</sup> byte message in about 2<sup>106</sup> work, rather than the previously expected 2<sup>160</sup> work. We also provide slightly cheaper ways to find multicollisions than the method of Joux [Jou04]. Both of these results are based on expandable messages-patterns for producing messages of varying length, which all collide on the intermediate hash result immediately after processing the message. We provide an algorithm for finding expandable messages for any n-bit hash function built using the Damgård-Merkle construction, which requires only a small multiple of the work done to find a single collision in the hash function.},
 
 
}
 
}
 
</bibtex>
 
</bibtex>
  
 
+
= Preimage attacks =
= Preimage Attacks =
 
  
 
Herding attacks are a special kind of preimage attack, in the sense
 
Herding attacks are a special kind of preimage attack, in the sense
Line 102: Line 185:
 
follows. At the cost of a pre-computation step, an attacker can
 
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.
 
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
 
and shows that for all iterated hash functions the complexity is
 
less than one would expect from an ideal hash function.
 
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
+
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}
 
  
 
For short suffixes, the workfactor for a herding attack on an
 
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
\cite{Kelsey2005HerdingHashFunctionsa} is $2^{(2n-5)/3}$. First a
 
 
so-called diamond structure is built in a precomputation phase that
 
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
 
one of the edges of the diamond structure. Let's denote the path
 
between the found entry point in the diamond structure and the
 
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
 
Besides observing this theoretical weakness, we can also consider
 
the feasibility in practice of this attack. In the case of SHA-1,
 
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
+
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.
outcome of presidential elections when MD5 is
 
used~\cite{Stevens2008}), the attack can be much faster.
 
  
 
In order to exploit dedicated collision-search attacks on SHA-1, a
 
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
 
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.
 
Such an algorithm is not known to date.
 +
 +
<bibtex>
 +
@inproceedings{eurocryptKelseyK06,
 +
  author = {John Kelsey and Tadayoshi Kohno},
 +
  title = {Herding Hash Functions and the Nostradamus Attack},
 +
  booktitle = {EUROCRYPT},
 +
  year = {2006},
 +
  pages = {183-200},
 +
  abstract = {In this paper, we develop a new attack on Damgård-Merkle hash functions, called the herding attack, in which an attacker who can find many collisions on the hash function by brute force can first provide the hash of a message, and later “herd” any given starting part of a message to that hash value by the choice of an appropriate suffix. We focus on a property which hash functions should have–Chosen Target Forced Prefix (CTFP) preimage resistance–and show the distinction between Damgård-Merkle construction hashes and random oracles with respect to this property. We describe a number of ways that violation of this property can be used in arguably practical attacks on real-world applications of hash functions. An important lesson from these results is that hash functions susceptible to collision-finding attacks, especially brute-force collision-finding attacks, cannot in general be used to prove knowledge of a secret value.},
 +
  editor = {Serge Vaudenay},
 +
  volume = {4004},
 +
  series = {LNCS},
 +
  publisher = {Springer},
 +
  isbn = {3-540-34546-9},
 +
  url = {http://dx.doi.org/10.1007/11761679_12},
 +
}
 +
</bibtex>
  
 
----
 
----

Latest revision as of 15:26, 10 November 2008

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 2t 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 2t-multicollision is actually t*2n/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 2t 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 2n against birthday based collision search attacks. Generating a 2n/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 <math>2^{n/2+log(n)}</math>.

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

CRYPTO 3152:306-316,2004
http://springerlink.metapress.com/openurl.asp?genre=article{\&}issn=0302-9743{\&}volume=3152{\&}spage=306
Bibtex
Author : Antoine Joux
Title : Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions
In : CRYPTO -
Address :
Date : 2004

Don Coppersmith - Another Birthday Attack

CRYPTO 218:14-17,1985
http://link.springer.de/link/service/series/0558/bibs/0218/02180014.htm
Bibtex
Author : Don Coppersmith
Title : Another Birthday Attack
In : CRYPTO -
Address :
Date : 1985


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 <math>2^k</math>, the same number of different target hash values will speed-up the search for second preimages (of potentially different length) to <math>2^{n-k}</math> trials.

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

Robert S. Winternitz - A Secure One-Way Hash Function Built from DES

IEEE Symposium on Security and Privacy pp. 88-90,1984
http://doi.ieeecomputersociety.org/10.1109/SP.1984.10027
Bibtex
Author : Robert S. Winternitz
Title : A Secure One-Way Hash Function Built from DES
In : IEEE Symposium on Security and Privacy -
Address :
Date : 1984

Xuejia Lai, James L. Massey - Hash Function Based on Block Ciphers

EUROCRYPT 658:55-70,1993
http://link.springer.de/link/service/series/0558/bibs/0658/06580055.htm
Bibtex
Author : Xuejia Lai, James L. Massey
Title : Hash Function Based on Block Ciphers
In : EUROCRYPT -
Address :
Date : 1993

Bart Preneel - Analysis and Design of Cryptographic Hash Functions

Ph.D. Thesis, ,1999
Bibtex
Author : Bart Preneel
Title : Analysis and Design of Cryptographic Hash Functions
In : Ph.D. Thesis, -
Address :
Date : 1999


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 2n-k+1word.

Very recently, Andreeva et al. extended this to cases in which there are multiple (say <math>2^t</math>) first preimages. Assuming a length of <math>2^k</math> of each of them, it turns out that finding a single second preimage is equivalent to finding a second preimage for a message of <math>2^{k+t}</math> 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

Ph.D. Thesis, ,1999
Bibtex
Author : Richard D. Dean
Title : Formal Aspects of Mobile Code Security
In : Ph.D. Thesis, -
Address :
Date : 1999

John Kelsey, Bruce Schneier - Second Preimages on n-Bit Hash Functions for Much Less than 2^n Work

EUROCRYPT 3494:474-490,2005
http://dx.doi.org/10.1007/11426639_28
Bibtex
Author : John Kelsey, Bruce Schneier
Title : Second Preimages on n-Bit Hash Functions for Much Less than 2^n Work
In : EUROCRYPT -
Address :
Date : 2005

Elena Andreeva, Charles Bouillaguet, Pierre-Alain Fouque, Jonathan J. Hoch, John Kelsey, Adi Shamir, Sebastien Zimmer - Second Preimage Attacks on Dithered Hash Functions

EUROCRYPT 4965:270-288,2008
Bibtex
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 : EUROCRYPT -
Address :
Date : 2008

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 2n- invocations of h.

For short suffixes, the workfactor for a herding attack on an 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 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 <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 the feasibility in practice of this attack. In the case of SHA-1, and without partial knowledge of P, a pre-computation effort of <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 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.

In order to exploit dedicated collision-search attacks on SHA-1, a 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 <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 <math>cv_1</math> and <math>cv_2</math>. Such an algorithm is not known to date.

John Kelsey, Tadayoshi Kohno - Herding Hash Functions and the Nostradamus Attack

EUROCRYPT 4004:183-200,2006
http://dx.doi.org/10.1007/11761679_12
Bibtex
Author : John Kelsey, Tadayoshi Kohno
Title : Herding Hash Functions and the Nostradamus Attack
In : EUROCRYPT -
Address :
Date : 2006