Difference between revisions of "GenericAttacksMerkleDamgaard"
From The ECRYPT Hash Function Website
Crechberger (talk | contribs) |
|||
| Line 13: | Line 13: | ||
volume = {3494}, | 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.}, | 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> | ||
| + | @article{titNandiS07, | ||
| + | author = {Mridul Nandi and | ||
| + | Douglas R. Stinson}, | ||
| + | title = {{Multicollision Attacks on Some Generalized Sequential Hash | ||
| + | Functions}}, | ||
| + | journal = {IEEE Transactions on Information Theory}, | ||
| + | volume = {53}, | ||
| + | number = {2}, | ||
| + | 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> | ||
Revision as of 16:14, 7 March 2008
Second Preimage Attacks
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
BibtexAuthor : John Kelsey, Bruce Schneier
Title : Second Preimages on n-Bit Hash Functions for Much Less than $2^n$ Work.
In : EUROCRYPT -
Address :
Date : 2005
Mridul Nandi, Douglas R. Stinson - {Multicollision Attacks on Some Generalized Sequential Hash
Functions}
- IEEE Transactions on Information Theory 53(2):759-767,2007
- http://dx.doi.org/10.1109/TIT.2006.889721
BibtexAuthor : Mridul Nandi, Douglas R. Stinson
Title : {Multicollision Attacks on Some Generalized Sequential Hash Functions}
In : IEEE Transactions on Information Theory -
Address :
Date : 2007
Note: This artcle shows that second preimages can be found in much less than 2n work. This approach works for all iterated hash functions. Nevertheless, this attack is not practical since a huge amount of data is required.
