The ECRYPT Hash Function Website - User contributions [en]

JH

2011-04-22T07:44:36Z

Tnad:

== The algorithm ==

* Author(s): Hongjun Wu
* Website: [http://www3.ntu.edu.sg/home/wuhj/research/jh/ http://www3.ntu.edu.sg/home/wuhj/research/jh/]
* NIST submission package:
** Round 3: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/JH_FinalRnd.zip JH_FinalRnd.zip]
** Round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/JH_Round2.zip JH_Round2.zip] (old versions: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/JH.zip JH.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/JHUpdate.zip JHUpdate.zip])

<bibtex>
@misc{sha3W09,
author = {Hongjun Wu},
title = {The Hash Function JH},
url = {http://www3.ntu.edu.sg/home/wuhj/research/jh/jh_round3.pdf},
howpublished = {Submission to NIST (round 3)},
year = {2011},
}
</bibtex>

<bibtex>
@misc{sha3W09a,
author = {Hongjun Wu},
title = {The Hash Function JH},
url = {http://ehash.iaik.tugraz.at/uploads/1/1d/Jh20090915.pdf},
howpublished = {Submission to NIST (Round 1/2)},
year = {2009},
}
</bibtex>

== Cryptanalysis ==

We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.

A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].

Recommended security parameter: '''42''' rounds

=== Hash function ===

Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.

{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements || Reference
|-
| style="background:greenyellow" | preimage || 512 || || 2507 || 2507 || [http://www.isical.ac.in/~rishi_r/FSE2010-146.pdf Bhattacharyya et al.]
|-
| style="background:greenyellow" | preimage(1) || 512 || || 2510.3 (+ 2524 MA + 2524 CMP) || 2510.3 (Wu: 2510.6) || [http://ehash.iaik.tugraz.at/uploads/d/da/Jh_preimage.pdf Mendel,Thomsen], [http://ehash.iaik.tugraz.at/uploads/6/6f/Jh_mt_complexity.pdf Wu]
|-
|}

(1) Wu has analyzed the exact memory requirements, additional memory accesses (MA) and comparisons (CMP) of the attack by Mendel and Thomsen.

=== Building blocks ===

Here we list results on underlying building blocks, and the hash function modified by other means than the security parameter.

Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).

{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference
|-
| semi-free-start collision || compression function || 256 || 16 rounds || 296.12 || 296.12 || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
|-
| semi-free-start near collision || compression function || 256 || 22 rounds || 295.63 || 295.63 || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
|-
| semi-free-start near collision || compression function || all || 10 rounds || 223.24 || - || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf Turan,Uyan]
|-
| semi-free-start collision || hash || 256 || 16 rounds || 2178.24 || 2101.12 || [http://www.cosic.esat.kuleuven.be/publications/article-1431.pdf Rijmen,Toz,Varıcı]
|-
| semi-free-start near collision || compression function || 256 || 22 rounds || 2156.77 || 2143.70 || [http://www.cosic.esat.kuleuven.be/publications/article-1431.pdf Rijmen,Toz,Varıcı]
|-
| semi-free-start near collision || compression function || 256 || 22 rounds || 2156.56 || 2143.70 || [http://www.cosic.esat.kuleuven.be/publications/article-1431.pdf Rijmen,Toz,Varıcı]
|-
| | pseudo-collision || compression function || all || || - || - || [http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt Bagheri]
|-
| | pseudo-2nd preimage || compression || all || || - || - || [http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt Bagheri]
|-
|}

<bibtex>
@misc{cryptoeprint:2010:607,
author = {María Naya-Plasencia},
title = {Scrutinizing rebound attacks: new algorithms for improving the complexities},
howpublished = {Cryptology ePrint Archive, Report 2010/607},
year = {2010},
note = {\\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2010/607.pdf},
abstract = {Rebound attacks are a state-of-the-art analysis method for hash functions. These cryptanalysis methods are based on a well chosen differential path and have been applied to several hash functions from the SHA-3 competition, providing the best known analysis in these cases. In this paper we study rebound attacks in detail and find for a great number of cases, that complexities of existing attacks can be improved. This is done by determining problems that adapt optimally to the cryptanalytic situation, and by using better algorithms to follow the differential path. These improvements are essentially based on merging big lists in a more efficient way, as well as on new ideas on how to reduce the complexities. As a result, we introduce general purpose new algorithms for enabling further rebound analysis to be as performant as possible. We illustrate our new algorithms for real hash functions and demonstrate how to reduce the complexities of the best known analysis on five hash functions: JH, Grøstl, ECHO, Luffa and Lane (the first four are round two SHA-3 candidates).},
}
</bibtex>

<bibtex>
@misc{blakeTU10,
author = {Meltem Sönmez Turan, Erdener Uyan},
title = {Practical Near-Collisions for Reduced Round Blake, Fugue, Hamsi and JH},
howpublished = {Second SHA-3 Candidate Conference},
year = {2010},
url = {http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/TURAN_Paper_Erdener.pdf},
abstract = {A hash function is near-collision resistant, if it is hard to find two messages with hash values that differ in only a small number of bits. In this study, we use hill climbing methods to evaluate the near-collision resistance of some of the round SHA-3 candidates. We practically obtained (i) 184/256-bit near-collision for the 2-round compression function of Blake-32; (ii) 192/256-bit near-collision for the 2-round compression function of Hamsi-256; (iii) 820/1024-bit near-collisions for 10-round compression function of JH. We also observed practical collisions and near-collisions for reduced versions of F-256 function used in Fugue.}
}
</bibtex>

<bibtex>
@inproceedings{BMN10,
author = {Rishiraj Bhattacharyya and Avradip Mandal and Mridul Nandi},
title = {Security Analysis of the Mode of JH Hash Function},
url = {http://www.isical.ac.in/~rishi_r/FSE2010-146.pdf},
booktitle = {FSE},
year = {2010},
series = {LNCS},
note = {To appear}
}
</bibtex>

<bibtex>
@inproceedings{RTV10,
author = {Vincent Rijmen and Denis Toz and Kerem Varıcı},
title = {Rebound Attack on Reduced-Round Versions of JH},
url = {http://www.cosic.esat.kuleuven.be/publications/article-1431.pdf},
booktitle = {FSE},
year = {2010},
series = {LNCS},
note = {To appear}
}
</bibtex>

<bibtex>
@misc{B08,
author = {Nasour Bagheri},
title = {Pseudo-collision and pseudo-second preimage on JH},
url = {http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt},
howpublished = {NIST mailing list (local link)},
year = {2008},
}
</bibtex>

<bibtex>
@misc{MT08,
author = {Florian Mendel, Søren S. Thomsen},
title = {An Observation on JH-512},
url = {http://ehash.iaik.tugraz.at/uploads/d/da/Jh_preimage.pdf},
howpublished = {Available online},
year = {2008},
abstract = {In this paper, we present a generic preimage attack on JH-512. We do not claim that
our attack breaks JH-512 (due to the high memory requirements), but it uses some interesting
properties in the design principles of JH-512 which do not exist in other hash functions, e.g., the
SHA-2 family.},
}
</bibtex>

<bibtex>
@misc{MT08,
author = {Hongjun Wu},
title = {The Complexity of Mendel and Thomsen's Preimage Attack on JH-512},
url = {http://ehash.iaik.tugraz.at/uploads/6/6f/Jh_mt_complexity.pdf},
howpublished = {Available online},
year = {2009},
abstract = {Mendel and Thomsen gave a preimage attack on JH-512 by finding a preimage through the collision search over the space of $2^{1024} elements. However, they did not estimate the cost of the collision search which is the most expensive part in their attack. Our analysis shows that their attack requires at least $2^{510.3}$ compression function computations, $2^{510.6}$ memory ($2^{516.6}$ bytes), $2^{524}$ memory accesses and $2^{524}$ comparisons. Such complexity is far more expensive than brute force
attack which requires $2^{512}$ compression function computations and almost no memory.},
}
</bibtex>

Blue Midnight Wish

2010-12-06T12:59:53Z

Tnad: /* Building blocks */

== The algorithm ==

* Author(s): Danilo Gligoroski, Vlastimil Klima, Svein Johan Knapskog, Mohamed El-Hadedy, Jørn Amundsen, Stig Frode Mjølsnes
* Website: [http://www.q2s.ntnu.no/sha3_nist_competition/start http://www.q2s.ntnu.no/sha3_nist_competition/start]
* NIST submission package:
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Blue_Midnight_Wish.zip Blue_Midnight_Wish.zip]
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Blue_Midnight_Wish_Round2.zip Blue_Midnight_Wish_Round2.zip]

<bibtex>
@misc{sha3GligoroskiKKH+09,
author = {Danilo Gligoroski and Vlastimil Klima and Svein Johan Knapskog and Mohamed El-Hadedy and J\o{}rn Amundsen and Stig Frode Mj\o{}lsnes},
title = {Cryptographic Hash Function BLUE MIDNIGHT WISH},
url = {http://people.item.ntnu.no/~danilog/Hash/BMW-SecondRound/Supporting_Documentation/BlueMidnightWishDocumentation.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3GligoroskiK09,
author = {Danilo Gligoroski and Vlastimil Klima },
title = {A Document describing all modifications made on the Blue Midnight Wish cryptographic hash function before entering the Second Round of SHA-3 hash competition},
url = {http://people.item.ntnu.no/~danilog/Hash/BMW-SecondRound/Supporting_Documentation/Round2Mods.pdf},
howpublished = {Available online},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3GligoroskiKKH+08,
author = {Danilo Gligoroski and Vlastimil Klima and Svein Johan Knapskog and Mohamed El-Hadedy and J\o{}rn Amundsen and Stig Frode Mj\o{}lsnes},
title = {Cryptographic Hash Function BLUE MIDNIGHT WISH},
url = {http://people.item.ntnu.no/~danilog/Hash/BMW/Supporting_Documentation/BlueMidnightWishDocumentation.pdf},
howpublished = {Submission to NIST (Round 1)},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.

A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].

Recommended security parameter: Expandrounds1 = '''2'''

=== Hash function ===

Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.

{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements || Reference
|-
| || || || || ||
|-
|}

=== Building blocks ===

Here we list results on underlying building blocks, and the hash function modified by other means than the security parameter.

Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).

{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference
|-
| partial-collision(1)|| compression function || 256,512 || || 232,264 || - || [http://www.di.ens.fr/~leurent/files/BMW_Distinguisher.pdf Leurent ,Thomsen]
|-
| observation|| compression function || all || || || - || [http://cryptography.hyperlink.cz/2009/BMWDecomposition04.pdf Gligoroski,Klima]
|-
| observation|| compression function || all || || || - || [http://cryptography.hyperlink.cz/BMW/BijectionsInBMW03-plain.pdf Gligoroski,Klima]
|-
| distinguisher || compression function || 256,512 || || 1 || - || [http://www2.mat.dtu.dk/people/S.Thomsen/bmw/bmw-distinguishers.pdf Guo,Thomsen]
|-
| distinguisher || compression function|| 512 || changed constant || 2278.2 || - || [https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_%28Nikolic%2C_Pieprzyk%2C_Sokolowski%2C_Steinfeld%29.pdf Nikolić,Pieprzyk,Sokołowski,Steinfeld]
|-
| distinguisher || compression function|| 512 || (Round 1) || 2223.5 || - || [https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_%28Nikolic%2C_Pieprzyk%2C_Sokolowski%2C_Steinfeld%29.pdf Nikolić,Pieprzyk,Sokołowski,Steinfeld]
|-
| distinguisher || compression function || 256,512 || || 219 || - || [http://131002.net/data/papers/Aum10.pdf Aumasson]
|-
| observation || hash || 256,512 || || - || - || [http://eprint.iacr.org/2009/453.pdf Klima,Susil]
|-
| pseudo-collision || hash || all || (Round 1) || 23n/8+1|| - || [http://eprint.iacr.org/2009/478.pdf Thomsen]
|-
| pseudo-preimage || hash || all || (Round 1) || 23n/4+1 || - || [http://eprint.iacr.org/2009/478.pdf Thomsen]
|-
| near-collision || compression || all || (Round 1) || example || - || [http://eprint.iacr.org/2009/478.pdf Thomsen]
|-
|}

(1)The BMW team commented on this partial-collision in [http://ehash.iaik.tugraz.at/uploads/7/7a/CommentNov2010.pdf this note]

<bibtex>
@misc{bmwAum10,
author = {Gaëtan Leurent and Søren S. Thomsen},
title = {Practical Partial-Collisions on the Compression Function of BMW},
url = {http://www.di.ens.fr/~leurent/files/BMW_Distinguisher.pdf},
howpublished = {Available online},
year = {2010},
abstract ={ Blue Midnight Wish (BMW) is one of the fastest SHA-3 candidates in the
second round of the competition. In this paper we study the compression function of BMW
and we obtain practical partial collisions in the case of BMW-256: we show a pair of inputs
so that 300 pre-speciﬁed bits of the outputs collide (out of 512 bits). Our attack requires
about 2^32 evaluations of the compression function. A similar attack can be developed for
BMW-512, which will gives message pairs with around 600 colliding bits for a cost of 2^64.
This analysis does not aﬀect the security of the iterated hash function, but it shows that
the compression function is far from ideal.
We also describe some tools for the analysis of systems of additions and rotations, which
are used in our attack, and which can be useful for the analysis of other systems}
</bibtex>

<bibtex>
@inproceedings{bmwGligoroskiK10,
author = {Danilo Gligoroski and Vlastimil Klima},
title = {On Blue Midnight Wish Decomposition},
booktitle = {SantaCrypt 2009},
pages = {41-51},
year = {2010},
url = {http://cryptography.hyperlink.cz/2009/BMWDecomposition04.pdf},
abstract ={Blue Midnight Wish is one of the 14 candidates in the second round of the NIST SHA-3 competition. In this paper we present a decomposition of the Blue Midnight Wish core functions, what gives
deeper look at the Blue Midnight Wish family of hash functions and a tool for their cryptanalysis. We
used this decomposition for better understanding the insights of Blue Midnight Wish functions and
to propose the tweak for the second round. We would like to encourage further cryptanalysis of Blue
Midnight Wish, as the quickest candidate in the second round.},
}
</bibtex>

<bibtex>
@inproceedings{bmwGligoroskiK102,
author = {Danilo Gligoroski and Vlastimil Klima},
title = {On the Computational Asymmetry of the S-Boxes Present in Blue Midnight Wish Cryptographic Hash},
booktitle = {ICT Innovations 2009},
editor = {Danco Davcev and Jorge Marx Gómez},
publisher = {Springer},
pages = {391-400},
year = {2010},
url = {http://cryptography.hyperlink.cz/BMW/BijectionsInBMW03-plain.pdf},
abstract ={Blue Midnight Wish hash function is one of 14 candidate functions that are continuing in the Second Round of the SHA-3 competition. In its design it has several S-boxes (bijective components) that transform 32-bit or 64-bit values. Although they look similar to the S-boxes in SHA-2, they are also different.
It is well known fact that the design principles of SHA-2 family of hash functions are still kept as a classified NSA information. However, in the open literature there have been several attempts to analyze those design principles. In this paper first we give an observation on the properties of SHA-2 S-boxes and then we investigate the same properties in Blue Midnight Wish.},
}
</bibtex>

<bibtex>
@misc{bmwGT10,
author = {Jian Guo and Søren S. Thomsen},
title = {Distinguishers for the Compression Function of Blue Midnight Wish with Probability 1},
url = {http://www2.mat.dtu.dk/people/S.Thomsen/bmw/bmw-distinguishers.pdf},
howpublished = {Available online},
year = {2010},
abstract ={In this paper, we give distinguishers for the compression function of SHA-3 candidate Blue Midnight Wish (tweaked version for round 2) with probability 1. The computational complexity is about 20 compression function calls. This applies to security parameters 0/16, 1/15, and 2/14. However, it does not threaten the security of the BMW hash functions.},
}
</bibtex>

<bibtex>
@misc{bmwNikolicPST,
author = {Ivica Nikolić and Josef Pieprzyk and Przemysław Sokołowski and Ron Steinfeld},
title = {Rotational Cryptanalysis of (Modified) Versions of BMW and SIMD},
url = {https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_%28Nikolic%2C_Pieprzyk%2C_Sokolowski%2C_Steinfeld%29.pdf},
howpublished = {Available online},
year = {2010},
abstract ={We extend the application of rotational distinguishers to
classes of primitives that besides ARX, may have substractions, shifts,
and boolean functions. This allows us to launch rotational attacks on
the compression functions of two SHA-3 candidates: BMW and SIMD.
Specifically, we find rotational distinguishers for the compression functions
of:
1. round 1 BMW-512,
2. round 2 BMW-512, with the constant modified in one byte
3. round 1,2 modified SIMD-512 reduced to 24 rounds, with linearized
key schedule
4. round 1,2, SIMD-512 reduced to 12 rounds
Our attacks do not contradict any security claims of the candidates.},
}
</bibtex>

<bibtex>
@misc{bmwAum10,
author = {Jean-Philippe Aumasson},
title = {Practical distinguisher for the compression function of Blue Midnight Wish},
url = {http://131002.net/data/papers/Aum10.pdf},
howpublished = {Available online},
year = {2010},
abstract ={This note presents distinguishers for the compression functions of Blue Midnight Wish-256 and -512, with data complexity of 2^19 pairs of images of uniformly random unknown inputs with a given difference.},
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2009:453,
author = {Vlastimil Klima and Petr Susil},
title = {A Note on Linear Approximations of BLUE MIDNIGHT WISH Cryptographic Hash Function},
howpublished = {Cryptology ePrint Archive, Report 2009/453},
year = {2009},
url = {http://eprint.iacr.org/2009/453.pdf},
abstract = {Abstract. BLUE MIDNIGHT WISH hash function is the fastest among 14 algorithms in the second round of SHA-3 competition [1]. At the beginning of this round authors were invited to add some tweaks before September 15th 2009. In this paper we discuss the tweaked version (BMW). The BMW algorithm [3] is of the type AXR, since it uses only operations ADD (sub), XOR and ROT (shift). If we substitute the operation ADD with operation XOR, we get a BMWlin, which is an affine transformation. In this paper we consider only a BMWlin function and its building blocks. These affine transformations can be represented as a linear matrix and a constant vector. We found that all matrices of main blocks of BMWlin have a full rank, or they have a rank very close to full rank. The structure of matrices was examined. Matrices of elementary blocks have an expected non-random structure, while main blocks have a random structure. We will also show matrices for different values of security parameter ExpandRounds1 (values between 0 and 16). We observed that increasing the number of rounds ExpandRounds1 tends to increase randomness as was intended by designers. These observations hold for both BMW256lin and BMW512lin. In this analysis we did not find any useful property, which would help in cryptanalysis, nor did we find any weaknesses of BMW. The study of all building blocks will follow.}
}
</bibtex>

<bibtex>
@inproceedings{fseThomsen10,
author = {Søren S. Thomsen},
title = {Pseudo-cryptanalysis of the Original Blue Midnight Wish},
url = {http://eprint.iacr.org/2009/478.pdf},
booktitle = {FSE},
year = {2010},
series = {LNCS},
note = {To appear}
abstract = {The hash function Blue Midnight Wish (BMW) is a candidate in the SHA-3 competition organised by the U.S. National Institute of Standards and Technology (NIST). BMW was selected for the second round of the competition, but the algorithm was tweaked in a number of ways. In this paper we describe cryptanalysis on the original version of BMW, as submitted to the SHA-3 competition in October 2008. When we refer to BMW, we therefore mean the original version of the algorithm.

The attacks described are (near-)collision, preimage and second preimage attacks on the BMW compression function. These attacks can also be described as pseudo-attacks on the full hash function, i.e., as attacks in which the adversary is allowed to choose the initial value of the hash function. The complexities of the attacks are about 2^{14} for the near-collision attack, about 2^{3n/8+1} for the pseudo-collision attack, and about 2^{3n/4+1} for the pseudo-(second) preimage attack, where n is the output length of the hash function. Memory requirements are negligible. Moreover, the attacks are not (or only moderately) affected by the choice of security parameter for BMW. }
</bibtex>

=== Archive ===

<bibtex>
@misc{Thomsen-bmw-compress,
author = {Søren S. Thomsen},
title = {Pseudo-cryptanalysis of Blue Midnight Wish},
url = {http://www.mat.dtu.dk/people/S.Thomsen/bmw/bmw-pseudo.pdf},
howpublished = {Available online},
year = {2009},
abstract ={We describe pseudo-collision and pseudo-(second) preimage attacks on the SHA-3 candidate Blue Midnight Wish. The complexity of the pseudo-collision attack is around 2^{3n/8+1}, and the complexity of the pseudo-(second) preimage attack is around 2^{3n/4+1}.},
}
</bibtex>

<bibtex>
@misc{Thomsen-bmw-nc-compress,
author = {Søren S. Thomsen},
title = {A near-collision attack on the Blue Midnight Wish compression function},
url = {http://www2.mat.dtu.dk/people/S.Thomsen/bmw/nc-compress.pdf},
howpublished = {Version 2.0, available online},
year = {2008},
}
</bibtex>

Blue Midnight Wish

2010-12-06T12:59:19Z

Tnad: /* Building blocks */

== The algorithm ==

* Author(s): Danilo Gligoroski, Vlastimil Klima, Svein Johan Knapskog, Mohamed El-Hadedy, Jørn Amundsen, Stig Frode Mjølsnes
* Website: [http://www.q2s.ntnu.no/sha3_nist_competition/start http://www.q2s.ntnu.no/sha3_nist_competition/start]
* NIST submission package:
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Blue_Midnight_Wish.zip Blue_Midnight_Wish.zip]
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Blue_Midnight_Wish_Round2.zip Blue_Midnight_Wish_Round2.zip]

<bibtex>
@misc{sha3GligoroskiKKH+09,
author = {Danilo Gligoroski and Vlastimil Klima and Svein Johan Knapskog and Mohamed El-Hadedy and J\o{}rn Amundsen and Stig Frode Mj\o{}lsnes},
title = {Cryptographic Hash Function BLUE MIDNIGHT WISH},
url = {http://people.item.ntnu.no/~danilog/Hash/BMW-SecondRound/Supporting_Documentation/BlueMidnightWishDocumentation.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3GligoroskiK09,
author = {Danilo Gligoroski and Vlastimil Klima },
title = {A Document describing all modifications made on the Blue Midnight Wish cryptographic hash function before entering the Second Round of SHA-3 hash competition},
url = {http://people.item.ntnu.no/~danilog/Hash/BMW-SecondRound/Supporting_Documentation/Round2Mods.pdf},
howpublished = {Available online},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3GligoroskiKKH+08,
author = {Danilo Gligoroski and Vlastimil Klima and Svein Johan Knapskog and Mohamed El-Hadedy and J\o{}rn Amundsen and Stig Frode Mj\o{}lsnes},
title = {Cryptographic Hash Function BLUE MIDNIGHT WISH},
url = {http://people.item.ntnu.no/~danilog/Hash/BMW/Supporting_Documentation/BlueMidnightWishDocumentation.pdf},
howpublished = {Submission to NIST (Round 1)},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.

A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].

Recommended security parameter: Expandrounds1 = '''2'''

=== Hash function ===

Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.

{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements || Reference
|-
| || || || || ||
|-
|}

=== Building blocks ===

Here we list results on underlying building blocks, and the hash function modified by other means than the security parameter.

Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).

{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference
|-
| partial-collision(1)|| compression function || 256,512 || || 232,264 || - || [http://www.di.ens.fr/~leurent/files/BMW_Distinguisher.pdf Leurent ,Thomsen]
|-
| observation|| compression function || all || || || - || [http://cryptography.hyperlink.cz/2009/BMWDecomposition04.pdf Gligoroski,Klima]
|-
| observation|| compression function || all || || || - || [http://cryptography.hyperlink.cz/BMW/BijectionsInBMW03-plain.pdf Gligoroski,Klima]
|-
| distinguisher || compression function || 256,512 || || 1 || - || [http://www2.mat.dtu.dk/people/S.Thomsen/bmw/bmw-distinguishers.pdf Guo,Thomsen]
|-
| distinguisher || compression function|| 512 || changed constant || 2278.2 || - || [https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_%28Nikolic%2C_Pieprzyk%2C_Sokolowski%2C_Steinfeld%29.pdf Nikolić,Pieprzyk,Sokołowski,Steinfeld]
|-
| distinguisher || compression function|| 512 || (Round 1) || 2223.5 || - || [https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_%28Nikolic%2C_Pieprzyk%2C_Sokolowski%2C_Steinfeld%29.pdf Nikolić,Pieprzyk,Sokołowski,Steinfeld]
|-
| distinguisher || compression function || 256,512 || || 219 || - || [http://131002.net/data/papers/Aum10.pdf Aumasson]
|-
| observation || hash || 256,512 || || - || - || [http://eprint.iacr.org/2009/453.pdf Klima,Susil]
|-
| pseudo-collision || hash || all || (Round 1) || 23n/8+1|| - || [http://eprint.iacr.org/2009/478.pdf Thomsen]
|-
| pseudo-preimage || hash || all || (Round 1) || 23n/4+1 || - || [http://eprint.iacr.org/2009/478.pdf Thomsen]
|-
| near-collision || compression || all || (Round 1) || example || - || [http://eprint.iacr.org/2009/478.pdf Thomsen]
|-
|}

(1)The BMW team commented on these partial-collisions in [http://ehash.iaik.tugraz.at/uploads/7/7a/CommentNov2010.pdf this note]

<bibtex>
@misc{bmwAum10,
author = {Gaëtan Leurent and Søren S. Thomsen},
title = {Practical Partial-Collisions on the Compression Function of BMW},
url = {http://www.di.ens.fr/~leurent/files/BMW_Distinguisher.pdf},
howpublished = {Available online},
year = {2010},
abstract ={ Blue Midnight Wish (BMW) is one of the fastest SHA-3 candidates in the
second round of the competition. In this paper we study the compression function of BMW
and we obtain practical partial collisions in the case of BMW-256: we show a pair of inputs
so that 300 pre-speciﬁed bits of the outputs collide (out of 512 bits). Our attack requires
about 2^32 evaluations of the compression function. A similar attack can be developed for
BMW-512, which will gives message pairs with around 600 colliding bits for a cost of 2^64.
This analysis does not aﬀect the security of the iterated hash function, but it shows that
the compression function is far from ideal.
We also describe some tools for the analysis of systems of additions and rotations, which
are used in our attack, and which can be useful for the analysis of other systems}
</bibtex>

<bibtex>
@inproceedings{bmwGligoroskiK10,
author = {Danilo Gligoroski and Vlastimil Klima},
title = {On Blue Midnight Wish Decomposition},
booktitle = {SantaCrypt 2009},
pages = {41-51},
year = {2010},
url = {http://cryptography.hyperlink.cz/2009/BMWDecomposition04.pdf},
abstract ={Blue Midnight Wish is one of the 14 candidates in the second round of the NIST SHA-3 competition. In this paper we present a decomposition of the Blue Midnight Wish core functions, what gives
deeper look at the Blue Midnight Wish family of hash functions and a tool for their cryptanalysis. We
used this decomposition for better understanding the insights of Blue Midnight Wish functions and
to propose the tweak for the second round. We would like to encourage further cryptanalysis of Blue
Midnight Wish, as the quickest candidate in the second round.},
}
</bibtex>

<bibtex>
@inproceedings{bmwGligoroskiK102,
author = {Danilo Gligoroski and Vlastimil Klima},
title = {On the Computational Asymmetry of the S-Boxes Present in Blue Midnight Wish Cryptographic Hash},
booktitle = {ICT Innovations 2009},
editor = {Danco Davcev and Jorge Marx Gómez},
publisher = {Springer},
pages = {391-400},
year = {2010},
url = {http://cryptography.hyperlink.cz/BMW/BijectionsInBMW03-plain.pdf},
abstract ={Blue Midnight Wish hash function is one of 14 candidate functions that are continuing in the Second Round of the SHA-3 competition. In its design it has several S-boxes (bijective components) that transform 32-bit or 64-bit values. Although they look similar to the S-boxes in SHA-2, they are also different.
It is well known fact that the design principles of SHA-2 family of hash functions are still kept as a classified NSA information. However, in the open literature there have been several attempts to analyze those design principles. In this paper first we give an observation on the properties of SHA-2 S-boxes and then we investigate the same properties in Blue Midnight Wish.},
}
</bibtex>

<bibtex>
@misc{bmwGT10,
author = {Jian Guo and Søren S. Thomsen},
title = {Distinguishers for the Compression Function of Blue Midnight Wish with Probability 1},
url = {http://www2.mat.dtu.dk/people/S.Thomsen/bmw/bmw-distinguishers.pdf},
howpublished = {Available online},
year = {2010},
abstract ={In this paper, we give distinguishers for the compression function of SHA-3 candidate Blue Midnight Wish (tweaked version for round 2) with probability 1. The computational complexity is about 20 compression function calls. This applies to security parameters 0/16, 1/15, and 2/14. However, it does not threaten the security of the BMW hash functions.},
}
</bibtex>

<bibtex>
@misc{bmwNikolicPST,
author = {Ivica Nikolić and Josef Pieprzyk and Przemysław Sokołowski and Ron Steinfeld},
title = {Rotational Cryptanalysis of (Modified) Versions of BMW and SIMD},
url = {https://cryptolux.org/mediawiki/uploads/0/07/Rotational_distinguishers_%28Nikolic%2C_Pieprzyk%2C_Sokolowski%2C_Steinfeld%29.pdf},
howpublished = {Available online},
year = {2010},
abstract ={We extend the application of rotational distinguishers to
classes of primitives that besides ARX, may have substractions, shifts,
and boolean functions. This allows us to launch rotational attacks on
the compression functions of two SHA-3 candidates: BMW and SIMD.
Specifically, we find rotational distinguishers for the compression functions
of:
1. round 1 BMW-512,
2. round 2 BMW-512, with the constant modified in one byte
3. round 1,2 modified SIMD-512 reduced to 24 rounds, with linearized
key schedule
4. round 1,2, SIMD-512 reduced to 12 rounds
Our attacks do not contradict any security claims of the candidates.},
}
</bibtex>

<bibtex>
@misc{bmwAum10,
author = {Jean-Philippe Aumasson},
title = {Practical distinguisher for the compression function of Blue Midnight Wish},
url = {http://131002.net/data/papers/Aum10.pdf},
howpublished = {Available online},
year = {2010},
abstract ={This note presents distinguishers for the compression functions of Blue Midnight Wish-256 and -512, with data complexity of 2^19 pairs of images of uniformly random unknown inputs with a given difference.},
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2009:453,
author = {Vlastimil Klima and Petr Susil},
title = {A Note on Linear Approximations of BLUE MIDNIGHT WISH Cryptographic Hash Function},
howpublished = {Cryptology ePrint Archive, Report 2009/453},
year = {2009},
url = {http://eprint.iacr.org/2009/453.pdf},
abstract = {Abstract. BLUE MIDNIGHT WISH hash function is the fastest among 14 algorithms in the second round of SHA-3 competition [1]. At the beginning of this round authors were invited to add some tweaks before September 15th 2009. In this paper we discuss the tweaked version (BMW). The BMW algorithm [3] is of the type AXR, since it uses only operations ADD (sub), XOR and ROT (shift). If we substitute the operation ADD with operation XOR, we get a BMWlin, which is an affine transformation. In this paper we consider only a BMWlin function and its building blocks. These affine transformations can be represented as a linear matrix and a constant vector. We found that all matrices of main blocks of BMWlin have a full rank, or they have a rank very close to full rank. The structure of matrices was examined. Matrices of elementary blocks have an expected non-random structure, while main blocks have a random structure. We will also show matrices for different values of security parameter ExpandRounds1 (values between 0 and 16). We observed that increasing the number of rounds ExpandRounds1 tends to increase randomness as was intended by designers. These observations hold for both BMW256lin and BMW512lin. In this analysis we did not find any useful property, which would help in cryptanalysis, nor did we find any weaknesses of BMW. The study of all building blocks will follow.}
}
</bibtex>

<bibtex>
@inproceedings{fseThomsen10,
author = {Søren S. Thomsen},
title = {Pseudo-cryptanalysis of the Original Blue Midnight Wish},
url = {http://eprint.iacr.org/2009/478.pdf},
booktitle = {FSE},
year = {2010},
series = {LNCS},
note = {To appear}
abstract = {The hash function Blue Midnight Wish (BMW) is a candidate in the SHA-3 competition organised by the U.S. National Institute of Standards and Technology (NIST). BMW was selected for the second round of the competition, but the algorithm was tweaked in a number of ways. In this paper we describe cryptanalysis on the original version of BMW, as submitted to the SHA-3 competition in October 2008. When we refer to BMW, we therefore mean the original version of the algorithm.

The attacks described are (near-)collision, preimage and second preimage attacks on the BMW compression function. These attacks can also be described as pseudo-attacks on the full hash function, i.e., as attacks in which the adversary is allowed to choose the initial value of the hash function. The complexities of the attacks are about 2^{14} for the near-collision attack, about 2^{3n/8+1} for the pseudo-collision attack, and about 2^{3n/4+1} for the pseudo-(second) preimage attack, where n is the output length of the hash function. Memory requirements are negligible. Moreover, the attacks are not (or only moderately) affected by the choice of security parameter for BMW. }
</bibtex>

=== Archive ===

<bibtex>
@misc{Thomsen-bmw-compress,
author = {Søren S. Thomsen},
title = {Pseudo-cryptanalysis of Blue Midnight Wish},
url = {http://www.mat.dtu.dk/people/S.Thomsen/bmw/bmw-pseudo.pdf},
howpublished = {Available online},
year = {2009},
abstract ={We describe pseudo-collision and pseudo-(second) preimage attacks on the SHA-3 candidate Blue Midnight Wish. The complexity of the pseudo-collision attack is around 2^{3n/8+1}, and the complexity of the pseudo-(second) preimage attack is around 2^{3n/4+1}.},
}
</bibtex>

<bibtex>
@misc{Thomsen-bmw-nc-compress,
author = {Søren S. Thomsen},
title = {A near-collision attack on the Blue Midnight Wish compression function},
url = {http://www2.mat.dtu.dk/people/S.Thomsen/bmw/nc-compress.pdf},
howpublished = {Version 2.0, available online},
year = {2008},
}
</bibtex>

2010-03-24T12:04:31Z

Shabal

2010-02-15T11:23:21Z

Tnad:

== The algorithm ==

* Author(s): Emmanuel Bresson, Anne Canteaut, Benoît Chevallier-Mames, Christophe Clavier, Thomas Fuhr, Aline Gouget, Thomas Icart, Jean-François Misarsky, Marìa Naya-Plasencia, Pascal Paillier, Thomas Pornin, Jean-René Reinhard, Céline Thuillet, Marion Videau
* Website: http://www.shabal.com/
* NIST submission package:
** round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Shabal_Round2.zip Shabal_Round2.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Shabal.zip Shabal.zip])

<bibtex>
@misc{sha3CanteautCGPP08,
author = {Emmanuel Bresson and Anne Canteaut and Benoît Chevallier-Mames and Christophe Clavier and Thomas Fuhr and Aline Gouget and Thomas Icart and Jean-François Misarsky and Marìa Naya-Plasencia and Pascal Paillier and Thomas Pornin and Jean-René Reinhard and Céline Thuillet and Marion Videau},
title = {Shabal, a Submission to NIST’s Cryptographic Hash Algorithm Competition},
url = {http://ehash.iaik.tugraz.at/uploads/6/6c/Shabal.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2009:199,
author = {Emmanuel Bresson and Anne Canteaut and Benoît Chevallier-Mames and Christophe Clavier and Thomas Fuhr and Aline Gouget and Thomas Icart and Jean-François Misarsky and Marìa Naya-Plasencia and Pascal Paillier and Thomas Pornin and Jean-René Reinhard and Céline Thuillet and Marion Videau},
title = {Indifferentiability with Distinguishers: Why Shabal Does Not Require Ideal Ciphers},
howpublished = {Cryptology ePrint Archive, Report 2009/199},
year = {2009},
url = {http://eprint.iacr.org/2009/199.pdf},
abstract = {Shabal is based on a new provably secure mode of operation. Some related-key distinguishers for the underlying keyed permutation have been exhibited recently by Aumasson et al. and Knudsen et al., but with no visible impact on the security of Shabal. This paper then aims at extensively studying such distinguishers for the keyed permutation used in Shabal, and at clarifying the impact that they exert on the security of the full hash function. Most interestingly, a new security proof for Shabal's mode of operation is provided where the keyed permutation is not assumed to be an ideal cipher anymore, but observes a distinguishing property i.e., an explicit relation verified by all its inputs and outputs. As a consequence of this extended proof, all known distinguishers for the keyed permutation are proven not to weaken the security of Shabal. In our study, we provide the foundation of a generalization of the indifferentiability framework to biased random primitives, this part being of independent interest.},
}
</bibtex>

== Cryptanalysis ==

We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.

A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].

=== Hash function ===

Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.

Recommended security parameters: (p,r)='''(3,12)'''

{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements || Reference
|-
| || || || || ||
|-
|}

=== Building blocks ===

Here we list results on underlying building blocks, and the hash function modified by other means than the security parameter.

Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).

{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference
|-
| | non-randomness(1) || permutation || all || || 212 || || [http://131002.net/data/papers/Aum09.pdf Aumasson]
|-
| | non-randomness(1) || permutation || all || || 1 || || [http://www.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf Knudsen,Matusiewicz,Thomsen]
|-
| | non-randomness(1) || permutation || all || || 2 || || [http://131002.net/data/papers/AMM09.pdf Aumasson,Mashatan,Meier]
|-
|}
(1)The Shabal team commented on these analyses and provide an update of their security proofs in [http://eprint.iacr.org/2009/199.pdf this note].

<bibtex>
@misc{shabalAum09,
author = {Jean-Philippe Aumasson},
title = {On the pseudorandomness of Shabal's keyed permutation},
url = {http://131002.net/data/papers/Aum09.pdf},
howpublished = {Available online},
year = {2009},
abstract = {
We report observations suggesting that the permutation used in
Shabal does not behave pseudorandomly. This does not affect the
security of Shabal as submitted to the NIST Hash Competition.},
}
</bibtex>

<bibtex>
@misc{shabalKMT09,
author = {Lars R. Knudsen and Krystian Matusiewicz and Søren S. Thomsen},
title = {Observations on the Shabal keyed permutation},
url = {http://www.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf },
howpublished = {OFFICIAL COMMENT},
year = {2009},
abstract = {
In this note we show that the permutation P used in the Shabal hash function, which is
a candidate in the SHA-3 competition, has some non-random properties. As an example,
it is easy to find a number of fixed points in the permutation. Moreover, large key-multicollisions
can be easily found; these are multi-collisions where only the key input contains
a difference. All observations are easily verified, and most of them are independent of the
choice of security parameters. Our observations, on the other hand, do not seem extensible
to the full hash function.
}
</bibtex>

<bibtex>
@misc{shabalAum09a,
author = {Jean-Philippe Aumasson and Atefeh Mashatan and Willi Meier},
title = {More on Shabal's permutation},
url = {http://131002.net/data/papers/AMM09.pdf},
howpublished = {OFFICIAL COMMENT},
year = {2009},
}
</bibtex>

Shabal

2010-02-15T10:59:06Z

StreamHash

2008-12-11T13:13:45Z

Tnad: /* The algorithm */

== The algorithm ==

* Author(s): Michal Trojnara

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

<bibtex>
@misc{sha3Trojnara08,
author = {Michal Trojnara},
title = {StreamHash Algorithm Specifications and Supporting Documentation},
url = {http://ehash.iaik.tugraz.at/uploads/0/09/Streamhash.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

* None yet

SHAvite-3

2008-12-11T13:13:29Z

Tnad: /* The algorithm */

== The algorithm ==

* Author(s): Eli Biham and Orr Dunkelman

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

<bibtex>
@misc{sha3BihamD08,
author = {Eli Biham and Orr Dunkelman},
title = {The SHAvite-3 Hash Function},
url = {http://ehash.iaik.tugraz.at/uploads/f/f5/Shavite.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

* None yet

2008-12-02T14:17:15Z

Tnad: /* Cryptanalysis */

== The algorithm ==

* Author(s): Greg Rose
* Website: [http://seer-grog.net/Boole.html http://seer-grog.net/Boole.html]
* Specification:


<bibtex>
@misc{sha3Rose08,
author = {Gregory G. Rose},
title = {Design and Primitive Specification for Boole},
url = {http://seer-grog.net/BoolePaper.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

<bibtex>
@misc{booleMNS08,
author = {Florian Mendel, Tomislav Nad, Martin Schläffer},
title = {Collision for Boole},
url = {http://ehash.iaik.tugraz.at/uploads/0/0b/BooleCollision.txt},
howpublished = {NIST mailing list (local link)},
year = {2008},

}
</bibtex>

<bibtex>
@misc{booleN08,
author = {Ivica Nikolić},
title = {Preimage attack on Boole-n},
url = {http://ehash.iaik.tugraz.at/uploads/2/2f/Boole.pdf},
howpublished = {Available online},
year = {2008},
abstract = {Boole is a family of hash functions proposed for SHA-3. In this paper we present a preimage attack on Boole-n that requires $2^{9n/16} computations and negligible memory.},
}
</bibtex>

2008-03-11T10:16:31Z

Tnad: /* 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{fseSasakiWOK07,
author = {Yu Sasaki and Lei Wang and Kazuo Ohta and Noboru Kunihiro},
title = {New Message Difference for MD4},
pages = {329-348},
url = {http://dx.doi.org/10.1007/978-3-540-74619-5_21},
editor = {Alex Biryukov},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {4593},
year = {2007},
isbn = {978-3-540-74617-1},
abstract = {This paper proposes several approaches to improve
the collision attack on MD4 proposed by Wang et al. First, we
propose a new local collision that is the best for the MD4 collision
attack. Selection of a good message difference is the most important
step in achieving effective collision attacks. This is the first paper
to introduce an improvement to the message difference approach of
Wang et al., where we propose a new local collision. Second, we propose
a new algorithm for constructing differential paths. While similar
algorithms have been proposed, they do not support the new local collision
technique.Finally, we complete a collision attack, and show that the
complexity is smaller than the previous best work.}
}
</bibtex>
<bibtex>
@inproceedings{fseLeurent07,
author = {Gaëtan Leurent},
title = {Message Freedom in MD4 and MD5 Collisions: Application to APOP},
pages = {309-328},
url = {http://dx.doi.org/10.1007/978-3-540-74619-5_20},
editor = {Alex Biryukov},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {4593},
year = {2007},
isbn = {978-3-540-74617-1},
abstract = {In Wang’s attack, message modifications allow to
deterministically satisfy certain sufficient conditions to find
collisions efficiently. Unfortunately, message modifications
significantly change the messages and one has little control
over the colliding blocks. In this paper, we show how to choose
small parts of the colliding messages. Consequently, we break a
security countermeasure proposed by Szydlo and Yin at CT-RSA ’06,
where a fixed padding is added at the end of each block. Furthermore,
we also apply this technique to recover part of the passwords in the
Authentication Protocol of the Post Office Protocol (POP). This shows
that collision attacks can be used to attack real protocols, which means that finding collisions is a real threat.}
}
</bibtex>

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

MD4

2008-03-11T10:16:19Z

Tnad: /* 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 ===
@inproceedings{fseSasakiWOK07,
author = {Yu Sasaki and Lei Wang and Kazuo Ohta and Noboru Kunihiro},
title = {New Message Difference for MD4},
pages = {329-348},
url = {http://dx.doi.org/10.1007/978-3-540-74619-5_21},
editor = {Alex Biryukov},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {4593},
year = {2007},
isbn = {978-3-540-74617-1},
abstract = {This paper proposes several approaches to improve
the collision attack on MD4 proposed by Wang et al. First, we
propose a new local collision that is the best for the MD4 collision
attack. Selection of a good message difference is the most important
step in achieving effective collision attacks. This is the first paper
to introduce an improvement to the message difference approach of
Wang et al., where we propose a new local collision. Second, we propose
a new algorithm for constructing differential paths. While similar
algorithms have been proposed, they do not support the new local collision
technique.Finally, we complete a collision attack, and show that the
complexity is smaller than the previous best work.}
}
</bibtex>
<bibtex>
@inproceedings{fseLeurent07,
author = {Gaëtan Leurent},
title = {Message Freedom in MD4 and MD5 Collisions: Application to APOP},
pages = {309-328},
url = {http://dx.doi.org/10.1007/978-3-540-74619-5_20},
editor = {Alex Biryukov},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {4593},
year = {2007},
isbn = {978-3-540-74617-1},
abstract = {In Wang’s attack, message modifications allow to
deterministically satisfy certain sufficient conditions to find
collisions efficiently. Unfortunately, message modifications
significantly change the messages and one has little control
over the colliding blocks. In this paper, we show how to choose
small parts of the colliding messages. Consequently, we break a
security countermeasure proposed by Szydlo and Yin at CT-RSA ’06,
where a fixed padding is added at the end of each block. Furthermore,
we also apply this technique to recover part of the passwords in the
Authentication Protocol of the Post Office Protocol (POP). This shows
that collision attacks can be used to attack real protocols, which means that finding collisions is a real threat.}
}
</bibtex>

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