The ECRYPT Hash Function Website - User contributions [en]

Blender

2008-12-22T09:26:21Z

Mlamberger: /* Cryptanalysis */

== The algorithm ==

* Author(s): Colin Bradbury

* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Blender.zip Blender.zip]

<bibtex>
@misc{sha3Bradbury08,
author = {Colin Bradbury},
title = {BLENDER: A Proposed New Family of Cryptographic Hash Algorithms},
url = {http://ehash.iaik.tugraz.at/uploads/5/5e/Blender.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

<bibtex>
@misc{blenderN08,
author = {Craig Newbold},
title = {Observations and Attacks On The SHA-3 Candidate Blender },
howpublished = {Available online},
url = {http://ehash.iaik.tugraz.at/uploads/2/20/Observations_on_Blender.pdf},
year = {2008},
abstract = {51 candidates have been accepted as ﬁrst round candidates in NIST‘s
SHA-3 competition, to decide the new cryptographic hash standard. Many
of these submissions have no external cryptanalysis published, so the task
begins to analyse their security and eliminate those that have vulnerabili-
ties. In what we believe to be the ﬁrst published external cryptananalysis
of one candidate, Blender, we make observations on its structure, then
exploit these features to give a multicollision attack of time complex-
ity around $2^{\frac{n+w}2}$ , and a ﬁrst preimage attack of time complexity around
$n2^{\frac{n+w}2}$. Both attacks have minimal space requirements, so we believe that
this constitutes a break of Blender. We then leave possible improvements
on these attacks as open problems.},
}
</bibtex>

<bibtex>
@misc{blenderM08,
author = {Florian Mendel},
title = {Preimage Attack on Blender},
url = {http://ehash.iaik.tugraz.at/uploads/4/48/Blender-preimage.pdf},
howpublished = {Available Online},
abstract = {In this paper, we present a preimage attack on the hash function Blender for
all output sizes. It has a complexity of about n*2^(n/2) and negligible
memory requirements. The attack is based on structural weaknesses in the design
of the hash function and is independent of the underlying compression function.},
year = {2008},
}
</bibtex>

<bibtex>
@misc{blenderK08,
author = {Vlastimil Klima},
title = {A near-collision attack on Blender-256},
url = {http://cryptography.hyperlink.cz/BMW/near_collision_blender.pdf},
howpublished = {Available online},
year = {2008},
}
</bibtex>

<bibtex>
@misc{blenderXu08,
author = {Liangyu Xu},
title = {Semi-free start collision attack on Blender},
howpublished = {Available online},
url = {http://eprint.iacr.org/2008/532.pdf},
year = {2008},
abstract = {Blender is a cryptographic hash function submitted to NIST’s SHA3 competition. We
have found a semi-free start collision attack on Blender with trivial complexity. One pair of
semi-free start collision messages with zero initial values is presented.},
}
</bibtex>

Blender

2008-12-22T09:26:03Z

Mlamberger: /* Cryptanalysis */

Blender

2008-12-20T16:56:37Z

Mlamberger: /* Cryptanalysis */

Blender

2008-12-20T16:54:26Z

Mlamberger: /* Cryptanalysis */

Blender

2008-12-20T16:53:11Z

Mlamberger: /* Cryptanalysis */

Blender

2008-12-20T16:52:32Z

Mlamberger: /* Cryptanalysis */

The SHA-3 Zoo

2008-12-20T16:33:37Z

Mlamberger:

The SHA-3 Zoo (work in progress) is a collection of cryptographic hash functions (in alphabetical order) submitted to the [http://www.nist.gov/hash-competition SHA-3 contest] (see also [http://en.wikipedia.org/wiki/SHA-3 here]). It aims to provide an overview of design and cryptanalysis of all submissions. A list of all [[SHA-3 submitters]] is also available. For a software performance related overview, see [http://bench.cr.yp.to/ebash.html eBASH]. At a separate page, we also collect [[SHA-3_Hardware_Implementations | hardware implementation results]] of the candidates. Another categorization of the SHA-3 submissions can be found [http://www.uni-weimar.de/cms/fileadmin/medien/medsicherheit/Research/SHA3/Classification_of_the_SHA-3_Candidates.pdf here].
 
At this time, 55 out of 64 submissions to the SHA-3 competition are publicly known and available. [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/submissions_rnd1.html 51] submissions have advanced to the first round (so far, 15 of 55 published submissions have been broken).

[http://ehash.iaik.tugraz.at/index.php?title=Special:Recentchangeslinked&target=The_SHA-3_Zoo&days=7&limit=50&hideminor=1 Recent updates of the SHA-3 Zoo]

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable"
|- style="background:#efefef;"
! width="150"| Hash Function Name !! width="150"| Status !! width="150"| [[External Cryptanalysis Categories| External Cryptanalysis]]
|-
| [[Abacus]] || 1st round || broken
|-
| [[ARIRANG]] || 1st round || none
|-
| [[AURORA]] || 1st round || none
|-
| [[BLAKE]] || 1st round || none
|-
| [[Blender]] || 1st round || yes
|-
| [[Blue Midnight Wish]] || 1st round || yes
|-
| [[Boole]] || 1st round || broken
|-
| [[Cheetah]] || 1st round || none
|-
| [[CHI]] || 1st round || none
|-
| [[CRUNCH]] || 1st round || none
|-
| [[CubeHash]] || 1st round || yes
|-
| [[DCH]] || 1st round || broken
|-
| [[Dynamic SHA]] || 1st round || none
|-
| [[Dynamic SHA2]] || 1st round || none
|-
| [[ECHO]] || 1st round || none
|-
| [[ECOH]] || 1st round || none
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || 1st round || yes
|-
| [[EnRUPT]] || 1st round || broken
|-
| [[ESSENCE]] || 1st round || none
|-
| [[FSB (SHA-3 submission) | FSB]] || 1st round || none
|-
| [[Fugue]] || 1st round || none
|-
| [[Groestl|Grøstl]] || 1st round || yes
|-
| [[Hamsi]] || 1st round || none
|-
| [[HASH 2X]] || submitted || broken
|-
| [[JH]] || 1st round || yes
|-
| [[Keccak]] || 1st round || none
|-
| [[Khichidi-1]] || 1st round || broken
|-
| [[LANE]] || 1st round || none
|-
| [[Lesamnta]] || 1st round || none
|-
| [[Luffa]] || 1st round || none
|-
| [[LUX]] || 1st round || yes
|-
| [[Maraca]] || submitted || broken
|-
| [[MCSSHA-3]] || 1st round || broken
|-
| [[MD6]] || 1st round || yes
|-
| [[MeshHash]] || 1st round || yes
|-
| [[NaSHA]] || 1st round || yes
|-
| [[NKS2D]] || submitted || broken
|-
| [[Ponic]] || submitted || broken
|-
| [[SANDstorm]] || 1st round || none
|-
| [[Sarmal]] || 1st round || yes
|-
| [[Sgàil]] || 1st round || broken
|-
| [[Shabal]] || 1st round || none
|-
| [[SHAMATA]] || 1st round || yes
|-
| [[SHAvite-3]] || 1st round || none
|-
| [[SIMD]] || 1st round || none
|-
| [[Skein]] || 1st round || none
|-
| [[Spectral Hash]] || 1st round || yes
|-
| [[StreamHash]] || 1st round || broken
|-
| [[SWIFFTX]] || 1st round || none
|-
| [[Tangle]] || 1st round || broken
|-
| [[TIB3]] || 1st round || none
|-
| [[Twister]] || 1st round || yes
|-
| [[Vortex (SHA-3 submission)|Vortex]] || 1st round || yes
|-
| [[WaMM]] || 1st round || broken
|-
| [[Waterfall]] || 1st round || broken
|}

Your analysis is not mentioned? Drop a line at sha3zoo@iaik.tugraz.at to let us know!

File:Blender-preimage.pdf

2008-12-20T16:28:07Z

Mlamberger:

ECHO

2008-12-11T11:49:40Z

Mlamberger:

== The algorithm ==

* Author(s):Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin


* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/ECHO.zip .zip]

<bibtex>
@misc{sha3BBG+08,
author = {Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin},
title = {SHA-3 Proposal: ECHO},
url = {},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

* None yet

ECHO

2008-12-11T11:47:13Z

Mlamberger:

== ECHO ==

* Author(s):Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin


* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/ECHO.zip .zip]

<bibtex>
@misc{sha3BBG+08,
author = {Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin},
title = {SHA-3 Proposal: ECHO},
url = {},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

* None yet

Cheetah

2008-12-11T11:29:55Z

Mlamberger:

== The algorithm ==

* Author(s): Dmitry Khovratovich, Alex Biryukov, Ivica Nikolic

* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Cheetah.zip .zip]

<bibtex>
@misc{sha3KBN08,
author = {Dmitry Khovratovich, Alex Biryukov, Ivica Nikolic},
title = {The Hash Function Cheetah: Speciﬁcation and Supporting Documentation},
url = {},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

* None yet

SHA-1

2008-03-11T10:21:32Z

Mlamberger: /* Collision Attacks */

== Specification ==

* digest size: 160 bits
* max. message length: < 264 bits
* compression function: 512-bit message block, 160-bit chaining variable
* Specification: [http://csrc.nist.gov/publications/fips/fips180-2/fips180-2.pdf FIPS 180-2 Secure Hash Standard]

== Cryptanalysis ==

=== Best Known Results ===

The best collision attack on full SHA-1 was published by Wang et al. It has complexity of 269 hash evaluations. The best collision example, a 70-step collision for SHA-1, was published by DeCanniere, Mendel and Rechberger.
----

=== Collision Attacks ===

<bibtex>
@inproceedings{sacryptCanniereMR07,
author = {Christophe De Canni{\`e}re and Florian Mendel and Christian Rechberger},
title = {Collisions for 70-Step SHA-1: On the Full Cost of Collision Search},
booktitle = {Selected Areas in Cryptography},
year = {2007},
pages = {56-73},
url = {http://dx.doi.org/10.1007/978-3-540-77360-3_4},
editor = {Carlisle M. Adams and Ali Miri and Michael J. Wiener},
publisher = {Springer},
series = {LNCS},
volume = {4876},
isbn = {978-3-540-77359-7},
abstract = {The diversity of methods for fast collision search in SHA-1 and similar hash functions makes a comparison of them difficult. The literature is at times very vague on this issue, which makes comparison even harder. In situations where differences in estimates of attack complexity of a small factor might influence short-term recommendations of standardization bodies, uncertainties and ambiguities in the literature amounting to a similar order of magnitude are unhelpful. We survey different techniques and propose a simple but effective method to facilitate comparison. In a case study, we consider a newly developed attack on 70-step SHA-1, and give complexity estimates and performance measurements of this new and improved collision search method.},
}
</bibtex>
<bibtex>
@inproceedings{fseSugitaKPI07,
author = {Makoto Sugita and Mitsuru Kawazoe and Ludovic Perret and Hideki Imai},
title = {Algebraic Cryptanalysis of 58-Round SHA-1},
pages = {349-365},
url = {http://dx.doi.org/10.1007/978-3-540-74619-5_22},
editor = {Alex Biryukov},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {4593},
year = {2007},
isbn = {978-3-540-74617-1},
abstract = {In 2004, a new attack against SHA-1 has been proposed
by a team leaded by Wang [15]. The aim of this article is to sophisticate
and improve Wang’s attack by using algebraic techniques. We introduce
new notions, namely semi-neutral bit and adjuster and propose then an
improved message modification technique based on algebraic techniques.
In the case of the 58-round SHA-1, the experimental complexity of our
improved attack is 231 SHA-1 computations, whereas Wang’s method needs
234 SHA-1 computations. We have found many new collisions for the 58-round SHA-1.
We also study the complexity of our attack for the full SHA-1.}
}
</bibtex>
<bibtex>
@inproceedings{asiacryptCanniereR06,
author = {Christophe De Canni{\`e}re and Christian Rechberger},
title = {Finding SHA-1 Characteristics: General Results and Applications},
pages = {1-20},
url = {http://dx.doi.org/10.1007/11935230_1},
editor = {Xuejia Lai and Kefei Chen},
booktitle = {ASIACRYPT},
publisher = {Springer},
series = {LNCS},
volume = {4284},
year = {2006},
isbn = {3-540-49475-8},
abstract = {The most efficient collision attacks on members of the SHA family presented so far all use complex characteristics which were manually constructed by Wang et al. In this report, we describe a method to search for characteristics in an automatic way. This is particularly useful for multi-block attacks, and as a proof of concept, we give a two-block collision for 64-step SHA-1 based on a new characteristic. The highest number of steps for which a SHA-1 collision was published so far was 58. We also give a unified view on the expected work factor of a collision search and the needed degrees of freedom for the search, which facilitates optimization.},
}
</bibtex>

<bibtex>
@inproceedings{sacryptJutlaP06,
author = {Charanjit S. Jutla and Anindya C. Patthak},
title = {Provably Good Codes for Hash Function Design},
booktitle = {Selected Areas in Cryptography},
year = {2006},
pages = {376-393},
url = {http://dx.doi.org/10.1007/978-3-540-74462-7_26},
editor = {Eli Biham and Amr M. Youssef},
publisher = {Springer},
series = {LNCS},
volume = {4356},
isbn = {978-3-540-74461-0},
abstract = {We develop a new technique to lower bound the minimum distance of quasi-cyclic codes with large dimension by reducing the problem to lower bounding the minimum distance of a few significantly smaller dimensional codes. Using this technique, we prove that a code which is similar to the SHA-1 message expansion code has minimum distance at least 82, and that too in just the last 64 of the 80 expanded words. Further the minimum weight in the last 60 words (last 48 words) is at least 75 (52 respectively). We expect our technique to be helpful in designing future practical collision-resistant hash functions. We also use the technique to find the minimum weight of the SHA-1 code (25 in the last 60 words), which was an open problem.},
}
</bibtex>

<bibtex>
@inproceedings{sacryptPramstallerRR05a,
author = {Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
title = {Impact of Rotations in SHA-1 and Related Hash Functions},
booktitle = {Selected Areas in Cryptography},
year = {2005},
pages = {261-275},
url = {http://dx.doi.org/10.1007/11693383_18},
editor = {Bart Preneel and Stafford E. Tavares},
publisher = {Springer},
series = {LNCS},
volume = {3897},
isbn = {3-540-33108-5},
abstract = {SHA-1 uses a single set of rotation constants within the compression function. However, most other members of the MD4 family of hash functions use multiple sets of rotation constants, i.e. the rotation amounts change with the step being processed. To our knowledge, no design rationales on the choice of rotation constants are given on any of these hash functions. This is the first paper that analyzes rotations in iterated hash functions. We focus on SHA-1-like hash functions and use recent developments in the analysis of these hash functions to evaluate the security implications of using multiple sets of rotation constants in the compression function instead of a single set. Additionally, we give some observations on the set of constants used in SHA-0 and SHA-1.},
}
</bibtex>

<bibtex>
@inproceedings{eurocryptBihamCJCLJ05,
author = {Eli Biham and Rafi Chen and Antoine Joux and Patrick Carribault and Christophe Lemuet and William Jalby},
title = {Collisions of SHA-0 and Reduced SHA-1},
booktitle = {EUROCRYPT},
year = {2005},
pages = {36-57},
abstract = {In this paper we describe improvements to the techniques used to cryptanalyze SHA-0 and introduce the first results on SHA-1. The results include a generic multi-block technique that uses near-collisions in order to find collisions, and a four-block collision of SHA-0 found using this technique with complexity 251. Then, extension of this and prior techniques are presented, that allow us to find collisions of reduced versions of SHA-1. We give collisions of variants with up to 40 rounds, and show the complexities of longer variants. These techniques show that collisions up to about 53–58 rounds can still be found faster than by birthday attacks. Part of the results of this paper were given by the first author in an invited talk in SAC 2004, Waterloo, Canada.},
editor = {Ronald Cramer},
volume = {3494},
series = {LNCS},
publisher = {Springer},
isbn = {3-540-25910-4},
url = {http://dx.doi.org/10.1007/11426639_3},
}
</bibtex>

<bibtex>
@inproceedings{ctrsaRijmenO05,
author = {Vincent Rijmen and Elisabeth Oswald},
title = {Update on SHA-1},
booktitle = {CT-RSA},
year = {2005},
pages = {58-71},
publisher = {Springer},
series = {LNCS},
volume = {3376},
abstract = {We report on the experiments we performed in order to assess the security of SHA-1 against the attack by Chabaud and Joux [5]. We present some ideas for optimizations of the attack and some properties of the message expansion routine. Finally, we show that for a reduced version of SHA-1, with 53 rounds instead of 80, it is possible to find collisions in less than 2^80 operations.},
url = {http://dx.doi.org/10.1007/b105222}}
</bibtex>
----

=== Preimage Attacks ===
* We are not aware of any articles w.r.t. preimage attacks on SHA-1.
----

=== Others ===
<bibtex>
@inproceedings{fseMendelPRR06a,
author = {Florian Mendel and Norbert Pramstaller and Christian Rechberger and Vincent Rijmen},
title = {The Impact of Carries on the Complexity of Collision Attacks on SHA-1},
pages = {278-292},
url = {http://dx.doi.org/10.1007/11799313_18},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {4047},
year = {2006},
isbn = {3-540-36597-4},
abstract = {In this article we present a detailed analysis of
the impact of carries on the estimation of the attack complexity
for SHA-1. We build up on existing estimates and refine them. We
show that the attack complexity is slightly lower than estimated
in all published work to date. We point out that it is more accurate
to consider probabilities instead of conditions.},
}
</bibtex>

<bibtex>
@inproceedings{iswSatoh05,
author = {Akashi Satoh},
title = {Hardware Architecture and Cost Estimates for Breaking SHA-1},
booktitle = {ISC},
year = {2005},
pages = {259-273},
url = {http://dx.doi.org/10.1007/11556992_19},
editor = {Jianying Zhou and Javier Lopez and Robert H. Deng and Feng Bao},
publisher = {Springer},
series = {LNCS},
volume = {3650},
isbn = {3-540-29001-X},
abstract = {The cryptanalysis of hash functions has advanced rapidly, and many hash functions have been broken one after another. The most popular hash function SHA-1 has not been broken yet, but the new collision search techniques proposed by Wang et al. reduced the computational complexity down to $2^{69}$, which is only 1/2,000 of the $2^{80}$ operations needed for a birthday attack. The complexity is still too large even for today's supercomputers, but no feasibility study of breaking SHA-1 using specialized hardware has been reported. The well known brute force attack on DES simply repeats the DES operation $2^{56}$ times at a maximum, but the complexity of $2^{69}$ hash operations to break SHA-1 does not mean $2^{69}$ SHA-1 operations. Complex procedures using SHA-1 functions are required, and the total number of operations based on the probability of a collision occurrence is almost equivalent to the $2^{69}$ SHA-1 operations. Therefore, we describe a procedure and propose an LSI architecture to find real collisions for SHA-1 in this paper. The hardware core was synthesized by using a 0.13-$\micro m$ CMOS standard cell library, and its performances in speed, size, and power consumption were evaluated. A \$10 million budget can build a custom hardware system that would consist of 303 personal computers with 16 circuit boards each, in which 32 SHA-1-breaking LSIs are mounted. Each LSI has 64 SHA-1 cores that can run in parallel. This system would find a real collision in 127 days.},
}
</bibtex>

----

SHA-0

2008-03-11T10:18:12Z

Mlamberger: /* Collision Attacks */

== Specification ==

* digest size: 160 bits
* max. message length: < 264 bits
* compression function: 512-bit message block, 160-bit chaining variable
* Specification:

== Cryptanalysis ==

=== Best Known Results ===

----

=== Generic Attacks ===
* [[GenericAttacksMerkleDamgaard| Generic Attacks on the Merkle-Damgaard Construction ]]

----

=== Collision Attacks ===

<bibtex>
@inproceedings{asiacryptNaitoSSYKO06,
author = {Yusuke Naito and Yu Sasaki and Takeshi Shimoyama and Jun Yajima and Noboru Kunihiro and Kazuo Ohta},
title = {Improved Collision Search for SHA-0},
pages = {21-36},
url = {http://dx.doi.org/10.1007/11935230_2},
editor = {Xuejia Lai and Kefei Chen},
booktitle = {ASIACRYPT},
publisher = {Springer},
series = {LNCS},
volume = {4284},
year = {2006},
isbn = {3-540-49475-8},
abstract = {At CRYPTO 2005, Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin proposed a collision attack on SHA-0 that could generate a collision with complexity $2^39$ SHA-0 hash operations. Although the method of Wang et al. can find messages that satisfy the sufficient conditions in steps 1 to 20 by using message modification, it makes no mention of the message modifications needed to yield satisfaction of the sufficient conditions in steps 21 and onwards. In this paper, first, we give sufficient conditions for the steps from step 21, and propose submarine modification as the message modification technique that will ensure satisfaction of the sufficient conditions from steps 21 to 24. Submarine modification is an extension of the multi-message modification used in collision attacks on the MD-family. Next, we point out that the sufficient conditions given by Wang et al. are not enough to generate a collision with high probability; we rectify this shortfall by introducing two new sufficient conditions. The combination of our newly found sufficient conditions and submarine modification allows us to generate a collision with complexity $2^36$ SHA-0 hash operations. At the end of this paper, we show the example of a collision generated by applying our proposals.},
}
</bibtex>

<bibtex>
@inproceedings{eurocryptBihamCJCLJ05,
author = {Eli Biham and Rafi Chen and Antoine Joux and Patrick Carribault and Christophe Lemuet and William Jalby},
title = {Collisions of SHA-0 and Reduced SHA-1},
booktitle = {EUROCRYPT},
year = {2005},
pages = {36-57},
abstract = {In this paper we describe improvements to the techniques used to cryptanalyze SHA-0 and introduce the first results on SHA-1. The results include a generic multi-block technique that uses near-collisions in order to find collisions, and a four-block collision of SHA-0 found using this technique with complexity 251. Then, extension of this and prior techniques are presented, that allow us to find collisions of reduced versions of SHA-1. We give collisions of variants with up to 40 rounds, and show the complexities of longer variants. These techniques show that collisions up to about 53–58 rounds can still be found faster than by birthday attacks. Part of the results of this paper were given by the first author in an invited talk in SAC 2004, Waterloo, Canada.},
editor = {Ronald Cramer},
volume = {3494},
series = {LNCS},
publisher = {Springer},
isbn = {3-540-25910-4},
url = {http://dx.doi.org/10.1007/11426639_3},
}
</bibtex>

----

=== Second Preimage Attacks ===

----

=== Preimage Attacks ===

----

=== Others ===

VSH

2008-03-11T10:16:56Z

Mlamberger: /* Specification */

== Specification ==


* Specification: http://csrc.nist.gov/groups/ST/hash/documents/LENSTRA_vsh.pdf

<bibtex>
@inproceedings{eurocryptContiniLS06,
author = {Scott Contini and Arjen K. Lenstra and Ron Steinfeld},
title = {VSH, an Efficient and Provable Collision-Resistant Hash Function},
booktitle = {EUROCRYPT},
year = {2006},
pages = {165-182},
abstract = {We introduce VSH, very smooth hash, a new S-bit hash function that is provably collision-resistant assuming the hardness of finding nontrivial modular square roots of very smooth numbers modulo an S-bit composite. By very smooth, we mean that the smoothness bound is some fixed polynomial function of S. We argue that finding collisions for VSH has the same asymptotic complexity as factoring using the Number Field Sieve factoring algorithm, i.e., subexponential in S. VSH is theoretically pleasing because it requires just a single multiplication modulo the S-bit composite per Ω(S) message-bits (as opposed to O(logS) message-bits for previous provably secure hashes). It is relatively practical. A preliminary implementation on a 1GHz Pentium III processor that achieves collision resistance at least equivalent to the difficulty of factoring a 1024-bit RSA modulus, runs at 1.1 MegaByte per second, with a moderate slowdown to 0.7MB/s for 2048-bit RSA security. VSH can be used to build a fast, provably secure randomised trapdoor hash function, which can be applied to speed up provably secure signature schemes (such as Cramer-Shoup) and designated-verifier signatures.},
editor = {Serge Vaudenay},
volume = {4004},
series = {LNCS},
publisher = {Springer},
isbn = {3-540-34546-9},
url = {http://dx.doi.org/10.1007/11761679_11},
}
</bibtex>

== Cryptanalysis ==

=== Best Known Results ===

----

=== Generic Attacks ===
* [[GenericAttacksMerkleDamgaard| Generic Attacks on the Merkle-Damgaard Construction ]]

----

=== Collision Attacks ===

----

=== Second Preimage Attacks ===

----

=== Preimage Attacks ===

----

=== Others ===

<bibtex>
@inproceedings{indocryptSaarinen06,
author = {Markku-Juhani Olavi Saarinen},
title = {Security of VSH in the Real World},
booktitle = {INDOCRYPT},
year = {2006},
pages = {95-103},
url = {http://dx.doi.org/10.1007/11941378_8},
editor = {Rana Barua and Tanja Lange},
publisher = {Springer},
series = {LNCS},
volume = {4329},
isbn = {3-540-49767-6},
abstract = {In Eurocrypt 2006, Contini, Lenstra, and Steinfeld proposed a new hash function primitive, VSH, very smooth hash. In this brief paper we offer commentary on the resistance of VSH against some standard cryptanalytic attacks, including preimage attacks and collision search for a truncated VSH. Although the authors of VSH claim only collision resistance, we show why one must be very careful when using VSH in cryptographic engineering, where additional security properties are often required.},
}
</bibtex>

GenericAttacksMerkleDamgaard

2008-03-11T10:16:17Z

Mlamberger: /* Preimage Attacks */

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 [http://ehash.iaik.tugraz.at/index.php/GenericAttacksHash this page]

= 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 \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 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 (also given in~\cite{}) 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~\cite{DBLP:conf/crypto/Coppersmith85} on the Davies-Price
variant~\cite{} of Rabin's scheme~\cite{} builds already on exactly
this idea.

<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>

= Second Preimage Attacks =
Discoveries about second preimage attacks on iterated hash functions
span the last three decades. Merkle notes in 1979 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. \todo{Winternitz,lai}.

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~\cite{} 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, \ie 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.

<bibtex>
@inproceedings{eurocryptKelseyS05,
author = {John Kelsey and Bruce Schneier},
title = {Second Preimages on n-Bit Hash Functions for Much Less than 2$^{\mbox{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>

= 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 \cite{Kelsey2005HerdingHashFunctionsa}, 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]
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$.
\end{definition}

For short suffixes, the workfactor for a herding attack on an
iterative hash functions as shown in
\cite{Kelsey2005HerdingHashFunctionsa} 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 (as is the case when facing the challenge of predicting the
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
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(cv_1,m)=h_c(cv_2,m^*)$ where the attacker
has little control over the chaining variables $cv_1$ and $cv_2$.
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>

----

GenericAttacksMerkleDamgaard

2008-03-11T10:14:04Z

Mlamberger: /* Second Preimage Attacks */

MD5

2008-03-11T10:12:32Z

Mlamberger: /* Collision Attacks */

== Specification ==



== Cryptanalysis ==

=== Best Known Results ===

----

=== Generic Attacks ===
* [[GenericAttacksMerkleDamgaard| Generic Attacks on the Merkle-Damgaard Construction ]]

----

=== Collision Attacks ===

<bibtex>
@inproceedings{eurocryptStevensLW07,
author = {Marc Stevens and Arjen K. Lenstra and Benne de Weger},
title = {Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities},
booktitle = {EUROCRYPT},
year = {2007},
pages = {1-22},
abstract = {We present a novel, automated way to find differential paths for MD5. As an application we have shown how, at an approximate expected cost of 250 calls to the MD5 compression function, for any two chosen message prefixes P and P′, suffixes S and S′ can be constructed such that the concatenated values P||S and P′||S′ collide under MD5. Although the practical attack potential of this construction of chosen-prefix collisions is limited, it is of greater concern than random collisions for MD5. To illustrate the practicality of our method, we constructed two MD5 based X.509 certificates with identical signatures but different public keys and different Distinguished Name fields, whereas our previous construction of colliding X.509 certificates required identical name fields. We speculate on other possibilities for abusing chosen-prefix collisions. More details than can be included here can be found on www.win.tue.nl/hashclash/ChosenPrefixCollisions/.},
editor = {Moni Naor},
volume = {4515},
series = {LNCS},
publisher = {Springer},
isbn = {978-3-540-72539-8},
url = {http://dx.doi.org/10.1007/978-3-540-72540-4_1},
}
</bibtex>

<bibtex>
@inproceedings{eurocryptWangY05,
author = {Xiaoyun Wang and Hongbo Yu},
title = {How to Break MD5 and Other Hash Functions},
booktitle = {EUROCRYPT},
year = {2005},
pages = {19-35},
abstract = {MD5 is one of the most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4, and its security was widely studied since then by several authors. The best known result so far was a semi free-start collision, in which the initial value of the hash function is replaced by a non-standard value, which is the result of the attack. In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 minutes up to an hour computation time. The attack is a differential attack, which unlike most differential attacks, does not use the exclusive-or as a measure of difference, but instead uses modular integer subtraction as the measure. We call this kind of differential a modular differential. An application of this attack to MD4 can find a collision in less than a fraction of a second. This attack is also applicable to other hash functions, such as RIPEMD and HAVAL.},
editor = {Ronald Cramer},
volume = {3494},
series = {LNCS},
publisher = {Springer},
isbn = {3-540-25910-4},
url = {http://dx.doi.org/10.1007/11426639_2},
}
</bibtex>

<bibtex>
@inproceedings{eurocryptBoerB93,
author = {Bert den Boer and Antoon Bosselaers},
title = {Collisions for the Compression Function of MD5},
booktitle = {EUROCRYPT},
year = {1993},
pages = {293-304},
abstract = {At Crypto’ 91 Ronald L. Rivest introduced the MD5 Message Digest Algorithm as a strengthened version of MD4, differing from it on six points. Four changes are due to the two existing attacks on the two round versions of MD4. The other two changes should additionally strengthen MD5. However both these changes cannot be described as well-considered. One of them results in an approximate relation between any four consecutive additive constants. The other allows to create collisions for the compression function of MD5. In this paper an algorithm is described that finds such collisions. A C program implementing the algorithm establishes a work load of finding about 216 collisions for the first two rounds of the MD5 compression function to find a collision for the entire four round function. On a 33MHz 80386 based PC the mean run time of this program is about 4 minutes.},
url = {http://link.springer.de/link/service/series/0558/bibs/0765/07650293.htm},
}
</bibtex>

<bibtex>
@inproceedings{eurocryptBerson92,
author = {Thomas A. Berson},
title = {Differential Cryptanalysis Mod 2^32 with Applications to MD5},
booktitle = {EUROCRYPT},
year = {1992},
pages = {71-80},
abstract = {We introduce the idea of differential cryptanalysis mod 2^32 and apply it to the MD5 message digest algorithm. We derive a theory for differential cryptanalysis of the circular shift function. We demonstrate a high-probability differentials which leave the message digest register unchanged for each of MD5’s four rounds, and explain how more such differentials may be calculated.},
url = {http://link.springer.de/link/service/series/0558/bibs/0658/06580071.htm},
}
</bibtex>

----

=== Second Preimage Attacks ===

----

=== Preimage Attacks ===

----

=== Others ===
<bibtex>
@inproceedings{fseBlackCH06,
author = {John Black and Martin Cochran and Trevor Highland},
title = {A Study of the MD5 Attacks: Insights and Improvements},
pages = {262-277},
url = {http://dx.doi.org/10.1007/11799313_17},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {4047},
year = {2006},
isbn = {3-540-36597-4},
abstract = {MD5 is a well-known and widely-used cryptographic
hash function. It has received renewed attention from researchers
subsequent to the recent announcement of collisions found by Wang et al. [16].
To date, however, the method used by researchers in this work has been fairly
difficult to grasp. In this paper we conduct a study of all attacks on MD5 starting
from Wang. We explain the techniques used by her team, give insights on how to improve
these techniques, and use these insights to produce an even faster attack on MD5.
Additionally, we provide an “MD5 Toolkit” implementing these improvements that we
hope will serve as an open-source platform for further research. Our hope is that
a better understanding of these attacks will lead to a better understanding of our
current collection of hash functions, what their strengths and weaknesses are, and
where we should direct future efforts in order to produce even stronger primitives.}
}
</bibtex>

RIPEMD

2008-03-11T10:11:22Z

Mlamberger: /* Collision Attacks */

== Specification ==

* digest size: 128 bits
* max. message length: < 264 bits
* compression function: 512-bit message block, 2 streams with each 128-bit chaining variable
* Specification:

== Cryptanalysis ==

=== Best Known Results ===

----

=== Generic Attacks ===
* [[GenericAttacksMerkleDamgaard| Generic Attacks on the Merkle-Damgaard Construction ]]

----

=== Collision Attacks ===

<bibtex>
@inproceedings{eurocryptWangLFCY05,
author = {Xiaoyun Wang and Xuejia Lai and Dengguo Feng and Hui Chen and Xiuyuan Yu},
title = {Cryptanalysis of the Hash Functions MD4 and RIPEMD},
booktitle = {EUROCRYPT},
year = {2005},
pages = {1-18},
abstract = {MD4 is a hash function developed by Rivest in 1990. It serves as the basis for most of the dedicated hash functions such as MD5, SHAx, RIPEMD, and HAVAL. In 1996, Dobbertin showed how to find collisions of MD4 with complexity equivalent to 220 MD4 hash computations. In this paper, we present a new attack on MD4 which can find a collision with probability 2–2 to 2–6, and the complexity of finding a collision doesnrsquot exceed 28 MD4 hash operations. Built upon the collision search attack, we present a chosen-message pre-image attack on MD4 with complexity below 28. Furthermore, we show that for a weak message, we can find another message that produces the same hash value. The complexity is only a single MD4 computation, and a random message is a weak message with probability 2–122. The attack on MD4 can be directly applied to RIPEMD which has two parallel copies of MD4, and the complexity of finding a collision is about 218 RIPEMD hash operations.},
editor = {Ronald Cramer},
volume = {3494},
series = {LNCS},
publisher = {Springer},
isbn = {3-540-25910-4},
url = {http://dx.doi.org/10.1007/11426639_1},
}
</bibtex>

<bibtex>
@inproceedings{fseDebaertG01,
author = {Christophe Debaert and Henri Gilbert},
title = {The RIPEMD and RIPEMD Improved Variants of MD4 Are Not Collision Free},
pages = {52-65},
url = {http://link.springer.de/link/service/series/0558/bibs/2355/23550052.htm},
editor = {Mitsuru Matsui},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {2355},
year = {2002},
isbn = {3-540-43869-6},
abstract = {In 1992, the cryptographic hash function RIPEMD, a European proposal, was introduced as an improved variant of the MD4 hash function. RIPEMD involves two parallel lines of modified versions of the MD4 compression function. Three years later, an attack against a reduced version of RIPEMD in which the first or the last round of the RIPEMD compression function is omitted was described by Hans Dobbertin, who also published in 1998 a cryptanalysis of MD4. In this paper, we present a method for finding collisions in each of the parallel lines of RIPEMD. The collision search procedure requires only a few seconds computing time. We show that although the modifications of the MD4 compression function Used in RIPEMD introduce additional constraints in the cryptanalysis as Compared with Dobbertin’s attack of MD4, these modifications do not result in an increase of the collision search computation time. It is still an open question whether collisions can be found for the full RIPEMD function.},
}
</bibtex>

<bibtex>
@article{jocDobbertin97,
author = {Hans Dobbertin},
title = {RIPEMD with Two-Round Compress Function is Not Collision-Free},
journal = {J. Cryptology},
volume = {10},
number = {1},
year = {1997},
pages = {51-70},
url = {http://dx.doi.org/10.1007/s001459900019},
abstract = {In 1990 Rivest introduced the cryptographic hash function MD4. The compress function of MD4 has three rounds. After partial attacks against MD4 were found, the stronger mode RIPEMD was designed as a European proposal in 1992 (RACE project). Its compress function consists of two parallel lines of modified versions of MD4-compress. RIPEMD is currently being considered to become an international standard (ISO/IEC Draft 10118-3). However, in this paper an attack against RIPEMD is described, which leads to comparable results with the previously known attacks against MD4: The reduced versions of RIPEMD, where the first or the last round of the compress function is omitted, are not collision-free. Moreover, it turns out that the methods developed in this note can be applied to find collisions for the full MD4.},
}
</bibtex>

----

=== Second Preimage Attacks ===

----

=== Preimage Attacks ===

----

=== Others ===

MD5

2008-03-11T10:06:53Z

Mlamberger: /* Collision Attacks */

MD4

2008-03-11T10:05:19Z

Mlamberger: /* Collision Attacks */

== Specification ==

* digest size: 128 bits
* max. message length: < 264 bits
* compression function: 512-bit message block, 128-bit chaining variable
* Specification:
<bibtex>
@inproceedings{cryptoRivest90,
author = {Ronald L. Rivest},
title = {The MD4 Message Digest Algorithm},
booktitle = {CRYPTO},
year = {1990},
pages = {303-311},
url = {http://link.springer.de/link/service/series/0558/bibs/0537/05370303.htm},
editor = {Alfred Menezes and Scott A. Vanstone},
publisher = {Springer},
series = {LNCS},
volume = {537},
isbn = {3-540-54508-5},
editor = {Alfred Menezes and Scott A. Vanstone},
publisher = {Springer},
series = {LNCS},
volume = {537},
isbn = {3-540-54508-5},
}
</bibtex>

== Cryptanalysis ==

=== Best Known Results ===

----

=== Generic Attacks ===
* [[GenericAttacksMerkleDamgaard| Generic Attacks on the Merkle-Damgaard Construction ]]

----

=== Collision Attacks ===

<bibtex>
@inproceedings{eurocryptWangLFCY05,
author = {Xiaoyun Wang and Xuejia Lai and Dengguo Feng and Hui Chen and Xiuyuan Yu},
title = {Cryptanalysis of the Hash Functions MD4 and RIPEMD},
booktitle = {EUROCRYPT},
year = {2005},
pages = {1-18},
abstract = {MD4 is a hash function developed by Rivest in 1990. It serves as the basis for most of the dedicated hash functions such as MD5, SHAx, RIPEMD, and HAVAL. In 1996, Dobbertin showed how to find collisions of MD4 with complexity equivalent to 220 MD4 hash computations. In this paper, we present a new attack on MD4 which can find a collision with probability 2–2 to 2–6, and the complexity of finding a collision doesnrsquot exceed 28 MD4 hash operations. Built upon the collision search attack, we present a chosen-message pre-image attack on MD4 with complexity below 28. Furthermore, we show that for a weak message, we can find another message that produces the same hash value. The complexity is only a single MD4 computation, and a random message is a weak message with probability 2–122. The attack on MD4 can be directly applied to RIPEMD which has two parallel copies of MD4, and the complexity of finding a collision is about 218 RIPEMD hash operations.},
editor = {Ronald Cramer},
volume = {3494},
series = {LNCS},
publisher = {Springer},
isbn = {3-540-25910-4},
url = {http://dx.doi.org/10.1007/11426639_1},
}
</bibtex>

<bibtex>
@article{jocDobbertin98,
author = {Hans Dobbertin},
title = {Cryptanalysis of MD4},
journal = {J. Cryptology},
volume = {11},
number = {4},
year = {1998},
pages = {253-271},
url = {http://link.springer.de/link/service/journals/00145/bibs/11n4p253.html},
abstract = {In 1990 Rivest introduced the hash function MD4. Two years later RIPEMD, a European proposal, was designed as a stronger mode of MD4. In 1995 the author found an attack against two of three rounds of RIPEMD. As we show in the present note, the methods developed to attack RIPEMD can be modified and supplemented such that it is possible to break the full MD4, while previously only partial attacks were known. An implementation of our attack allows us to find collisions for MD4 in a few seconds on a PC. An example of a collision is given demonstrating that our attack is of practical relevance.},
}
</bibtex>

<bibtex>
@inproceedings{fseDobbertin96,
author = {Hans Dobbertin},
title = {Cryptanalysis of MD4},
pages = {53-69},
editor = {Dieter Gollmann},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {1039},
year = {1996},
isbn = {3-540-60865-6},
abstract = {In 1990 Rivest introduced the hash function MD4. Two years later RIPEMD,
a European proposal, was designed as a stronger mode of MD4. In 1995 the
author found an attack against two of three rounds of RIPEMD. As we show
in the present note, the methods developed to attack RIPEMD can be modified
and supplemented such that it is possible to break the full MD4, while
previously only partial attacks were known. An implementation of our attack
allows us to find collisions for MD4 in a few seconds on a PC.
An example of a collision is given demonstrating that our attack is of practical relevance.},
url = {http://dx.doi.org/10.1007/s001459900047}
}
</bibtex>

<bibtex>
@inproceedings{fseVaudenay94,
author = {Serge Vaudenay},
title = {On the Need for Multipermutations: Cryptanalysis of MD4 and SAFER},
pages = {286-297},
editor = {Bart Preneel},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {1008},
year = {1995},
abstract = {Cryptographic primitives are usually based on a network with boxes.
At EUROCRYPT'94, Schnorr and the author of this paper claimed that
all boxes should be multipermutations. Here, we investigate a few
combinatorial properties of multipermutations. We argue that boxes which
fail to be multipermutations can open the way to unsuspected attacks.
We illustrate this statement with two examples. Firstly,
we show how to construct collisions to MD4 restricted to
its first two rounds. This allows one to forge digests close
to each other using the full compression function of MD4. Secondly,
we show that variants of SAFER are subject to attack faster than
exhaustive search in 6.1% cases. This attack can be implemented if
we decrease the number of rounds from 6 to 4.},
url = {http://dx.doi.org/10.1007/3-540-60590-8_22}
}
</bibtex>

----

=== Second Preimage Attacks ===

----

=== Preimage Attacks ===

<bibtex>
@inproceedings{fseDobbertin98,
owner = {tnad},
author = {Hans Dobbertin},
title = {The First Two Rounds of MD4 are Not One-Way},
pages = {284-292},
editor = {Serge Vaudenay},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {1372},
year = {1998},
isbn = {3-540-64265-X},
abstract = {In [1] it was shown that there are very effective attacks leading
to collisions for the hash function MD4 designed by R. Rivest [3].
A summary of the status of hash functions of the MD4-family with respect to
collision-resistence can be found in [2] and [4]. However, attacking the one-wayness
of a hash function is a much more demanding challenge, and in case of success it has much more devastating
consequences. No result along this line is known for MD4 and its
successors. Therefore it is worth to explore how the recently developed
new analytic methods for finding collisions can be applied to construct
preimages or second preimages. As a first step, we state here the following partial result.},
url = {http://dx.doi.org/10.1007/3-540-69710-1_19}
}
</bibtex>

----

=== Others ===
<bibtex>
@inproceedings{fseSchlafferO06,
author = {Martin Schläffer and Elisabeth Oswald},
title = {Searching for Differential Paths in MD4},
pages = {242-261},
url = {http://dx.doi.org/10.1007/11799313_16},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {4047},
year = {2006},
isbn = {3-540-36597-4},
abstract = {The ground-breaking results of Wang et al.
have attracted a lot of attention to the collision resistance
of hash functions. In their articles, Wang et al. give input
differences, differential paths and the corresponding conditions
that allow to find collisions with a high probability. However,
Wang et al. do not explain how these paths were found. The common
assumption is that they were found by hand with a great deal of intuition.
In this article, we present an algorithm that allows to find paths
in an automated way. Our algorithm is successful for MD4. We have found
over 1000 differential paths so far. Amongst them, there are paths that
have fewer conditions in the second round than the path of Wang et al.
for MD4. This makes them better suited for the message modification techniques
that were also introduced by Wang et al.}
}