The ECRYPT Hash Function Website - User contributions [en]

Groestl

2013-08-01T09:12:02Z

Fmendel:

== The algorithm ==

* Author(s): Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
* Website: [http://www.groestl.info http://www.groestl.info]
* NIST submission package:
** Round 3: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Groestl_FinalRnd.zip Groestl_FinalRnd.zip]
** Round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Grostl_Round2.zip Grostl_Round2.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Grostl.zip Grostl.zip])

<bibtex>
@misc{sha3groestl,
author = {Praveen Gauravaram and Lars R. Knudsen and Krystian Matusiewicz and Florian Mendel and Christian Rechberger and Martin Schläffer and Søren S. Thomsen},
title = {Grøstl -- a SHA-3 candidate},
url = {http://www.groestl.info/Groestl.pdf},
howpublished = {Submission to NIST (Round 3)},
year = {2011},
}
</bibtex>

<bibtex>
@misc{sha3groestl,
author = {Praveen Gauravaram and Lars R. Knudsen and Krystian Matusiewicz and Florian Mendel and Christian Rechberger and Martin Schläffer and Søren S. Thomsen},
title = {Grøstl Addendum},
url = {http://groestl.info/Groestl-addendum.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3groestl,
author = {Praveen Gauravaram and Lars R. Knudsen and Krystian Matusiewicz and Florian Mendel and Christian Rechberger and Martin Schläffer and Søren S. Thomsen},
title = {Grøstl -- a SHA-3 candidate},
url = {http://groestl.info/Groestl-0.pdf},
howpublished = {Submission to NIST (Round 1/2)},
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: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)

=== 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
|-
| collision || 224,256 || 3 rounds || 264 || - || [http://groestl.info/groestl-analysis.pdf Schläffer]
|-
| collision || 512 || 3 rounds || 2192 || - || [http://groestl.info/groestl-analysis.pdf Schläffer]
|-
|}

=== 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
|-
| distinguisher || permutation || 256 || 9 rounds || 2368 || 264 || [http://link.springer.com/chapter/10.1007%2F978-3-642-34047-5_7 Jean,Naya-Plasencia,Peyrin]
|-
| distinguisher || permutation || 512 || 8 rounds || 2280 || 264 || [http://link.springer.com/chapter/10.1007%2F978-3-642-34047-5_7 Jean,Naya-Plasencia,Peyrin]
|-
| distinguisher || permutation || 512 || 9 rounds || 2328 || 264 || [http://link.springer.com/chapter/10.1007%2F978-3-642-34047-5_7 Jean,Naya-Plasencia,Peyrin]
|-
| distinguisher || permutation || 512 || 10 rounds || 2392 || 264 || [http://link.springer.com/chapter/10.1007%2F978-3-642-34047-5_7 Jean,Naya-Plasencia,Peyrin]
|-
| preimage|| output transformation || 256 || 5 rounds || 2206 || 248 || [http://eprint.iacr.org/2012/206.pdf Wu,Feng,Wu,Guo,Dong,Zou]
|-
| pseudo preimage|| hash function || 256 || 5 rounds || 2244.85 || 2230.13 || [http://eprint.iacr.org/2012/206.pdf Wu,Feng,Wu,Guo,Dong,Zou]
|-
| preimage|| output transformation || 512 || 8 rounds || 2495 || 216 || [http://eprint.iacr.org/2012/206.pdf Wu,Feng,Wu,Guo,Dong,Zou]
|-
| pseudo preimage|| hash function || 512 || 8 rounds || 2507.32 || 2507 || [http://eprint.iacr.org/2012/206.pdf Wu,Feng,Wu,Guo,Dong,Zou]
|-
| preimage || output transformation || 256 || 6 rounds || 2251 || || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
|-
| preimage || compression function || 256 || 6 rounds || 2128 || || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || compression function || 256 || 6 rounds / 264 targets || 264 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || compression function || 256 || 6 rounds / 28 targets || 2120 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || compression function || 256 || 7 rounds / 280 targets || 264 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || compression function || 256 || 7 rounds / 224 targets || 2120 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || compression function || 256 || 8 rounds / 2192 targets || 264 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || compression function || 256 || 8 rounds / 2136 targets || 2120 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || compression function || 256 || 9 rounds / 2192 targets || 2120 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || hash function || 256 || 5 rounds / 264 targets || 280 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || hash function || 256 || 6 rounds / 216 targets || 2136 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || hash function || 256 || 6 rounds / 264 targets || 264 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || hash function || 256 || 6 rounds / 28 targets || 2120 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || hash function || 256 || 7 rounds / 280 targets || 264 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| chosen multitarget preimage || hash function || 256 || 7 rounds / 224 targets || 2120 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| preimage || hash function || 256 || 5 rounds || 2144 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| preimage || hash function || 256 || 6 rounds || 2144 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| pseudo preimage || hash function || 256 || 6 rounds || 2128 || 264 || [http://web.science.mq.edu.au/~rons/preimageattack-final.pdf Emami,Guaravaram,Pieprzyk,Steinfeld]
|-
| distinguisher || permutation || 256 || 10 rounds || 2509 || || [http://fse2011.mat.dtu.dk/slides/Higher-order%20differential%20properties%20of%20Keccak%20and%20Luffa.pdf Boura,Canteaut,DeCannière]
|-
| semi-free-start collision || compression function || 256 || 6 rounds || 2120 || 264 || [http://groestl.info/groestl-analysis.pdf Schläffer]
|-
| semi-free-start collision || compression function || 384,512 || 6 rounds || 2180 || 264 || [http://groestl.info/groestl-analysis.pdf Schläffer]
|-
| collision || hash function || 224,256 || 5 rounds (Round 1/2) || 248 || 232 || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| collision || hash function || 256 || 6 rounds (Round 1/2) || 2112 || 232 || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| collision || hash function || 224,256 || 4 rounds (Round 1/2) || 264 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| collision || hash function || 224,256 || 3 rounds (Round 1/2) || 264 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| collision || hash function || 384,512 || 5 rounds (Round 1/2) || 2176 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| collision || hash function || 384,512 || 4 rounds (Round 1/2) || 264 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| distinguisher || compression function || 256 || 10 rounds (Round 1/2) || 2175 || 264 || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
|-
| distinguisher || compression function || 512 || 11 rounds (Round 1/2) || 2630 || 264 || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
|-
| distinguisher || permutation || 256 || 8 rounds || 248 || 28 || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf Sasaki,Li,Wang,Sakiyama,Ohta]
|-
| semi-free-start collision || compression function || 512 || 7 rounds || 2152 || 256 || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf Sasaki,Li,Wang,Sakiyama,Ohta]
|-
| semi-free-start collision || compression function || 224,256 || 7 rounds (Round 1/2) || 280 || 232 || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| semi-free-start collision || compression function || 224,256 || 8 rounds (Round 1/2) || 2192 || 264 || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| distinguisher || permutation || 224,256 || 7 rounds || 219 || - || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| distinguisher || permutation || 224,256 || 8 rounds || 264 || 264 || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| distinguisher || compression function || 256 || 10 rounds (Round 1/2) || 2192 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| distinguisher || compression function || 256 || 9 rounds (Round 1/2) || 280 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| distinguisher || compression function || 512 || 11 rounds (Round 1/2) || 2640 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| semi-free-start collision || compression function || 256 || 7 rounds (Round 1/2) || 2120 || 264 || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
|-
| distinguisher || compression function || 256 || 8 rounds (Round 1/2) || 2112 || 264 || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
|-
| distinguisher || permutation || 256 || 8 rounds || 2112 || 264 || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
|-
| semi-free-start collision || compression function || 256 || 7 rounds (Round 1/2) || 2120 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| semi-free-start collision || compression function|| 384,512 || 7 rounds (Round 1/2) || 2152 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| semi-free-start collision || compression function || 224,256 || 6 rounds (Round 1/2) || 264 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
|-
| distinguisher || output transformation || 224,256 || 7 rounds || 256 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
|-
| distinguisher || permutation || 224,256 || 7 rounds || 255 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
|-
| semi-free-start collision || compression function || 256 || 6 rounds (Round 1/2) || 2120 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
|-
| semi-free-start collision || compression function || 224,256 || 5 rounds (Round 1/2) || 264 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
|-
| observation || hash || all || || || || [http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf Kelsey]
|-
| observation || block cipher || all || || || || [http://www.larc.usp.br/~pbarreto/Grizzly.pdf Barreto]
|-
| free-start collision || compression function || all || any || 22n/3 || 22n/3 || [http://www.groestl.info/Groestl.pdf submission document]
|-
| pseudo-preimage || compression function || all || any || 2n || - || [http://www.groestl.info/Groestl.pdf submission document]
|-
|}

<bibtex>
@inproceedings{DBLP:dblp_conf/fse/JeanNP12,
author = {Jérémy Jean and
María Naya-Plasencia and
Thomas Peyrin and
Thomas Peyrin},
title = {Improved Rebound Attack on the Finalist Grøstl.},
booktitle = {FSE},
year = {2012},
pages = {110-126},
url = {http://dx.doi.org/10.1007/978-3-642-34047-5_7},
crossref = {2012},
abstract = {Grøstl is one of the five finalist hash functions of the SHA-3 competition. For entering this final phase, the designers have tweaked the submitted versions. This tweak renders inapplicable the best known distinguishers on the compression function presented by Peyrin [18] that exploited the internal permutation properties. Since the beginning of the final round, very few analysis have been published on Grøstl. Currently, the best known rebound-based results on the permutation and the compression function for the 256-bit version work up to 8 rounds, and up to 7 rounds for the 512-bit version. In this paper, we present new rebound distinguishers that work on a higher number of rounds for the permutations of both 256 and 512-bit versions of this finalist, that is 9 and 10 respectively. Our distinguishers make use of an algorithm that we propose for solving three fully active states in the middle of the differential characteristic, while the Super-Sbox technique only handles two.}
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2012:206,
author = {Shuang Wu and Dengguo Feng and Wenling Wu and Jian Guo and Le Dong and Jian Zou},
title = {(Pseudo) Preimage Attack on Round-Reduced Gr{\o}stl Hash Function and Others (Extended Version)},
howpublished = {Cryptology ePrint Archive, Report 2012/206},
year = {2012},
url = {http://eprint.iacr.org/2012/206.pdf},
abstract = {The Gr{\o}stl hash function is one of the 5 final round candidates of the SHA-3 competition hosted by NIST. In this paper, we study the preimage resistance of the Gr{\o}stl hash function. We propose pseudo preimage attacks on Gr{\o}stl hash function for both 256-bit and 512-bit versions, i.e. we need to choose the initial value in order to invert the hash function. Pseudo preimage attack on 5(out of 10)-round Gr{\o}stl-256 has a complexity of $(2^{244.85},2^{230.13})$ (in time and memory) and pseudo preimage attack on 8(out of 14)-round Gr{\o}stl-512 has a complexity of $(2^{507.32},2^{507.00})$. To the best of our knowledge, our attacks are the first (pseudo) preimage attacks on round-reduced Gr{\o}stl hash function, including its compression function and output transformation. These results are obtained by a variant of meet-in-the-middle preimage attack framework by Aoki and Sasaki. We also improve the time complexities of the preimage attacks against 5-round Whirlpool and 7-round AES hashes by Sasaki in FSE~2011.}
}
</bibtex>

<bibtex>
@misc{emami-multitarget,
author = {Sareh Emami and Praveen Gauravaram and Josef Pieprzyk and Ron Steinfeld},
title = {(Chosen-multi-target) preimage attacks on reduced Grøstl-0},
url = {http://web.science.mq.edu.au/~rons/preimageattack-final.pdf},
abstract = {The cryptographic hash function Grøstl is a finalist in the NIST’s SHA-3 hash function
competition and it is a tweaked variant of its predecessor called Grøstl-0, a second round SHA-3 candidate.
In this article, we consider 256-bit Grøstl-0 and its 512-bit compression function. We show that
internal differential trails built between the two almost similar looking permutations of the compression
function can be coverted to chosen-multi-target-preimage attacks, a variant of multi-target preimage
attacks. Consequently, we show chosen-multi-target-preimage attacks for up to 9 out of 10 rounds of
the compression function and up to 7 rounds of the hash function. Finally, we use these attacks as a
tool to find preimages and pseudo preimages for 6 rounds of the 256-bit Grøstl-0 hash function.}
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2012:141,
author = {Dmitry Khovratovich},
title = {Bicliques for permutations: collision and preimage attacks in stronger settings},
howpublished = {Cryptology ePrint Archive, Report 2012/141},
year = {2012},
url = {http://eprint.iacr.org/2012/141.pdf},
abstract = {We extend and improve biclique attacks, which were recently introduced for the cryptanalysis of block ciphers and hash functions. While previous attacks required a primitive to have a key or a message schedule, we show how to mount attacks on the primitives with these parameters fixed, i.e. on permutations. We introduce the concept of sliced bicliques, which is a translation of regular bicliques to the framework with permutations.

The new framework allows to convert preimage attacks into collision attacks and derive the first collision attacks on the reduced SHA-3 finalist Skein in the hash function setting up to 11 rounds. We also demonstrate new preimage attacks on the reduced Skein and the output transformation of the reduced Gr{\o}stl. Finally, the sophisticated technique of message compensation gets a simple explanation with bicliques.}
}
</bibtex>

<bibtex>
@inproceedings{fseBCD11,
author = {Christina Boura and Anne Canteaut and Christophe De Cannière},
title = {Higher-order differential properties of Keccak and Luffa},
url = {http://fse2011.mat.dtu.dk/slides/Higher-order%20differential%20properties%20of%20Keccak%20and%20Luffa.pdf},
booktitle = {FSE},
year = {2011},
series = {LNCS},
pages = {252-269},
publisher = {Springer},
volume = {6733},
abstract = {In this paper, we identify higher-order differential and zero-sum properties in the full Keccak-f permutation, in the Luffa v1 hash function, and in components of the Luffa v2 algorithm. These structural properties rely on a new bound on the degree of iterated permutations with a nonlinear layer composed of parallel applications of smaller balanced Sboxes. These techniques yield zero-sum partitions of size $2^{1590}$ for the full Keccak-f permutation and several observations on the Luffa hash family. We first show that Luffa v1 applied to one-block messages is a function of 255 variables with degree at most 251. This observation leads to the construction of a higher-order differential distinguisher for the full Luffa v1 hash function, similar to the one presented by Watanabe et al. on a reduced version. We show that similar techniques can be used to find all-zero higher-order differentials in the Luffa v2 compression function, but the additional blank round destroys this property in the hash function.},
</bibtex>

<bibtex>
@misc{groestlSchlaeffer11,
author = {Martin Schläffer},
title = {Updated Differential Analysis of Grøstl},
howpublished = {Grøstl website},
month = {January},
year = {2011},
url = {http://groestl.info/groestl-analysis.pdf},
abstract = {Grøstl is a SHA-3 finalist with clear proofs against a large class of differential attacks, similar to those of MD6. Furthermore, in this note we provide an update also regarding more advanced types of differential attacks that have been developed in recent years. We apply the rebound attacks on the initial submission to the tweaked version of Grøstl. We have analyzed the round-reduced hash function and compression function of Grøstl-256 (10 rounds) and Grøstl-512 (14 rounds). For both versions, we get collisions for 3 rounds of the hash function and collisions for 6 rounds of the compression function. We hope that our own efforts on improving the cryptanalysis will continue to motivate and accelerate external cryptanalysis.},
}
</bibtex>

<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},
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>
@inproceedings{groestlechoSLWSO10,
author = {Yu Sasaki and Yang Li and Lei Wang and Kazuo Sakiyama and Kazuo Ohta},
title = {New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl},
booktitle = {ASIACRYPT},
year = {2010},
pages = {38-55},
publisher = {Springer},
series = {LNCS},
volume = {6477},
url = {http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf},
abstract = {In this paper, we present non-full-active Super-Sbox analysis which can detect non-ideal
properties of a class of AES-based permutations with a low complexity. We apply this framework
to SHA-3 round-2 candidates ECHO and Grøstl. The ﬁrst application is for the full-round (8-round)
ECHO permutation, which is a building block for 256-bit and 224-bit output sizes. By combining several
observations speciﬁc to ECHO, our attack detects a non-ideal property with a time complexity of 2^182
and 2^37 amount of memory. The complexity, especially in terms of the product of time and memory,
is drastically reduced from the previous best attack which required 2^512 x 2^512. To the best of our knowledge, this is the ﬁrst result on the full-round ECHO permutation with both time and memory below 2^256 or 2^224. Note that this result does not impact the security of the ECHO compression function nor the overall hash function. We also show that our method can detect non-ideal properties of the 8-round Grøstl-256 permutation with a practical complexity, and ﬁnally show that our approach leads
to an improvement on a semi-free-start collision attack on the 7-round Grøstl-512 compression function.
Our approach is based on a series of attacks on AES-based hash functions such as rebound attack and
Super-Sbox analysis. The core idea is using a new diﬀerential path consisting of only non-full-active
states.}
}
</bibtex>

<bibtex>
@inproceedings{ITP10,
author = {Kota Ideguchi and Elmar Tischhauser and Bart Preneel},
title = {Improved Collision Attacks on the Reduced-Round Grøstl Hash Function},
howpublished = {Cryptology ePrint Archive, Report 2010/375},
booktitle = {ISC},
year = {2010},
pages = {1-16},
publisher = {Springer},
series = {LNCS},
volume = {6531},
url = {http://eprint.iacr.org/2010/375.pdf},
abstract = {We analyze the Gr{\o}stl hash function, which is a 2nd-round candidate of the SHA-3 competition. Using the start-from-the-middle variant of the rebound technique, we show collision attacks on the Gr{\o}stl-256 hash function reduced to 5 and 6 out of 10 rounds with time complexities $2^{48}$ and $2^{112}$, respectively. Furthermore, we demonstrate semi-free-start collision attacks on the Gr{\o}stl-224 and -256 hash functions reduced to 7 rounds and the Gr{\o}stl-224 and -256 compression functions reduced to 8 rounds. Our attacks are based on differential paths between the two permutations $P$ and $Q$ of Gr{\o}stl, a strategy introduced by Peyrin to construct distinguishers for the compression function. In this paper, we extend this approach to construct collision and semi-free-start collision attacks for both the hash and the compression function. Finally, we present improved distinguishers for reduced-round versions of the Gr{\o}stl-224 and -256 permutations.},
}
</bibtex>

<bibtex>
@inproceedings{Pey10,
author = {Thomas Peyrin},
title = {Improved Differential Attacks for ECHO and Grostl},
booktitle = {CRYPTO},
year = {2010},
pages = {370-392},
publisher = {Springer},
series = {LNCS},
volume = {6223},
url = {http://eprint.iacr.org/2010/223.pdf},
abstract = {We present improved cryptanalysis of two second-round SHA-3 candidates: the AES-based hash functions ECHO and Grostl. We explain methods for building better differential trails for ECHO by increasing the granularity of the truncated differential paths previously considered. In the case of Grostl, we describe a new technique, the internal differential attack, which shows that when using parallel computations designers should also consider the differential security between the parallel branches. Then, we exploit the recently introduced start-from-the-middle or Super-Sbox attacks, that proved to be very efficient when attacking AES-like permutations, to achieve a very efficient utilization of the available freedom degrees. Finally, we obtain the best known attacks so far for both ECHO and Grostl. In particular, we are able to mount a distinguishing attack for the full Grostl-256 compression function.},
}
</bibtex>

<bibtex>
@inproceedings{fseGP10,
author = {Henri Gilbert and Thomas Peyrin},
title = {Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations},
booktitle = {FSE},
year = {2010},
series = {LNCS},
volume = {6147},
publisher = {Springer},
pages = {365-383},
url = {http://eprint.iacr.org/2009/531.pdf},
abstract = {In this paper, we improve the recent rebound and start-from-the-middle attacks on AES-like permutations. Our new cryptanalysis technique uses the fact that one can view two rounds of such permutations as a layer of big Sboxes preceded and followed by simple affine transformations. The big Sboxes encountered in this alternative representation are named Super-Sboxes. We apply this method to two second-round SHA-3 candidates Grostl and ECHO, and obtain improvements over the previous cryptanalysis results for these two schemes. Moreover, we improve the best distinguisher for the AES block cipher in the known-key setting, reaching 8 rounds for the 128-bit version.}
</bibtex>

<bibtex>
@inproceedings{ctrsaMRST10,
author = {Florian Mendel and Christian Rechberger and Martin Schläffer and Søren S. Thomsen},
title = {Rebound Attacks on the Reduced Grøstl Hash Function},
url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053},
booktitle = {CT-RSA},
year = {2010},
publisher = {Springer},
series = {LNCS},
volume = {5985},
pages = {350-365},
abstract = {Grøstl is one of 14 second round candidates of the
NIST SHA-3 competition. Cryptanalytic results on the wide-pipe compression
function of Grøstl-256 have already been published. However, little is known
about the hash function, arguably a much more interesting cryptanalytic
setting. Also, Grøstl-512 has not been analyzed yet. In this paper, we show
the first cryptanalytic attacks on reduced-round versions of the Grøstl hash
functions. These results are obtained by several extensions of the rebound
attack. We present a collision attack on 4/10 rounds of the Grøstl-256 hash
function and 5/14 rounds of the Grøstl-512 hash functions. Additionally, we
give the best collision attack for reduced-round (7/10 and 7/14) versions of the
compression function of Grøstl-256 and Grøstl-512.}
</bibtex>

<bibtex>
@inproceedings{sacMPRS09,
author = {Florian Mendel and Thomas Peyrin and Christian
Rechberger and Martin Schläffer},
title = {Improved Cryptanalysis of the Reduced Grøstl
Compression Function, ECHO Permutation and AES Block Cipher},
url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420},
booktitle = {SAC},
year = {2009},
series = {LNCS},
publisher = {Springer},
volume = {5867},
pages = {16-35},
abstract = {In this paper, we propose two new ways to mount attacks
on the SHA-3 candidates Gr{\o}stl, and ECHO, and apply these attacks
also to the AES. Our results improve upon and extend the rebound
attack. Using the new techniques, we are able to extend the number of
rounds in which available degrees of freedom can be used. As a result,
we present the first attack on 7 rounds for the Gr{\o}stl-256 output
transformation and improve the semi-free-start collision attack on 6
rounds. Further, we present an improved known-key distinguisher for 7
rounds of the AES block cipher and the internal permutation used in
ECHO.}
</bibtex>

<bibtex>
@inproceedings{fseMRST09,
author = {Florian Mendel and Christian Rechberger and Martin Schläffer and Søren S. Thomsen},
title = {The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl},
url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943},
booktitle = {FSE},
editor = {Orr Dunkelman},
year = {2009},
publisher = {Springer},
series = {LNCS},
volume = {5665},
pages = {260-276},
abstract = {In this work, we propose the rebound attack, a new tool
for the cryptanalysis of hash functions. The idea of the rebound
attack is to use the available degrees of freedom in a collision
attack to efficiently bypass the low probability parts of a
differential trail. The rebound attack consists of an inbound phase
with a match-in-the-middle part to exploit the available degrees of
freedom, and a subsequent probabilistic outbound phase. Especially on
AES based hash functions, the rebound attack leads to new attacks for
a surprisingly high number of
rounds.
We use the rebound attack to construct collisions for 4.5 rounds of
the 512-bit hash function Whirlpool with a complexity of $2^{120}$
compression function evaluations and negligible memory requirements.
The attack can be extended to a near-collision on 7.5 rounds of the
compression function of Whirlpool and 8.5 rounds of the similar hash
function Maelstrom. Additionally, we apply the rebound attack to the
SHA-3 submission Gr{\o}stl, which leads to an attack on 6 rounds of
the Gr{\o}stl-256 compression function with a complexity of $2^{120}$
and memory requirements of about $2^{64}$.}
</bibtex>

<bibtex>
@misc{groestlK09,
author = {John Kelsey},
title = {Some notes on Grøstl},
url = {http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf},
howpublished = {NIST hash function mailing list},
month = {April},
year = {2009},
abstract = {These are some quick notes on some properties and
observations of Grøstl. Nothing in this note threatens the hash
function; instead, I'm pointing out some properties that are a bit
surprising, and some broad approaches someone might take to get
attacks to work.},
}
</bibtex>

<bibtex>
@misc{groestlB08,
author = {Paulo S. L. M. Barreto},
title = {An observation on Grøstl},
url = {http://www.larc.usp.br/~pbarreto/Grizzly.pdf},
howpublished = {NIST hash function mailing list},
month = {November},
year = {2008},
abstract = {An alternative view of the Groestl SHA-3 submission is
presented. It does not lead to an effective attack nor reveals a
weakness in the design, but illustrates the importance of the
double-width pipe in this construction.},
}
</bibtex>

Skein

2011-03-22T18:37:56Z

Fmendel:

== The algorithm ==

* Author(s): Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker
* Website: [http://www.schneier.com/skein.html http://www.schneier.com/skein.html]; [http://skein-hash.info/ http://skein-hash.info/]
* NIST submission package:
** round 3: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Skein_FinalRnd.zip Skein_FinalRnd.zip]
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Skein_Round2.zip Skein_Round2.zip]
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SkeinUpdate.zip SkeinUpdate.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Skein.zip Skein.zip])

<bibtex>
@misc{sha3F+10,
author = {Niels Ferguson and Stefan Lucks and Bruce Schneier and Doug Whiting and Mihir Bellare and Tadayoshi Kohno and Jon Callas and Jesse Walker},
title = {The Skein Hash Function Family},
url = {http://www.skein-hash.info/sites/default/files/skein1.3.pdf},
howpublished = {Submission to NIST (Round 3)},
year = {2010},
}
</bibtex>

<bibtex>
@misc{sha3F+09,
author = {Niels Ferguson and Stefan Lucks and Bruce Schneier and Doug Whiting and Mihir Bellare and Tadayoshi Kohno and Jon Callas and Jesse Walker},
title = {The Skein Hash Function Family},
url = {http://www.skein-hash.info/sites/default/files/skein1.2.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3F+08,
author = {Niels Ferguson and Stefan Lucks and Bruce Schneier and Doug Whiting and Mihir Bellare and Tadayoshi Kohno and Jon Callas and Jesse Walker},
title = {The Skein Hash Function Family},
url = {http://www.skein-hash.info/sites/default/files/skein1.1.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: '''72''' rounds (Skein-512)

=== 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
|-
| distinguisher || compression function || all || 57 rounds (Round 2) || 2503 || - || [http://eprint.iacr.org/2010/538.pdf Khovratovich,Nikolić,Rechberger]
|-
| distinguisher || compression function || 256 || 53 rounds (Round 2) || 2251, Skein-256 || - || [http://eprint.iacr.org/2010/538.pdf Khovratovich,Nikolić,Rechberger]
|-
| near-collision || compression function || all || 24 rounds (No. 20-43) || 2230 || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
|-
| near-collision || compression function || 256 || 24 rounds (No. 12-35), Skein-256 || 260 || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
|-
| near-collision || compression function || all || 24 rounds, Skein-1024 || 2395 || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
|-
| observations || hash || all || || || || [http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf Gligoroski]
|-
| observations || block cipher || all || - || - || - || [http://eprint.iacr.org/2010/282.pdf McKay,Vora]
|-
| observations || compression function || all || - || - || - || [http://eprint.iacr.org/2010/262.pdf Kaminsky]
|-
| key recovery || block cipher || 256 || 39 rounds || 2254.1 || - || [http://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf Khovratovich,Nikolic]
|-
| key recovery || block cipher || 512 || 42 rounds|| 2507 || - || [http://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf Khovratovich,Nikolic]
|-
| key recovery || block cipher || 512 || 32 rounds (Round 1) || 2226 (2222) || 212 || [http://eprint.iacr.org/2009/526.pdf Chen,Jia]
|-
| key recovery || block cipher || 512 || 33 rounds (Round 1) || 2352.17 (2355.5) || - || [http://eprint.iacr.org/2009/526.pdf Chen,Jia]
|-
| near collision || compression function || 512 || 17 rounds (Round 1) || 224 || - || [http://eprint.iacr.org/2009/438.pdf Aumasson,Calik,Meier,Ozen,Phan,Varici]
|-
| distinguisher || block cipher || 512 || 35 rounds (Round 1) || 2478 || - || [http://eprint.iacr.org/2009/438.pdf Aumasson,Calik,Meier,Ozen,Phan,Varici]
|-
| impossible differential || block cipher || 512 || 21 rounds (Round 1) || - || - || [http://eprint.iacr.org/2009/438.pdf Aumasson,Calik,Meier,Ozen,Phan,Varici]
|-
| key recovery || block cipher || 512 || 32 rounds (Round 1) || 2312 || - || [http://eprint.iacr.org/2009/438.pdf Aumasson,Calik,Meier,Ozen,Phan,Varici]
|-
|}

<bibtex>
@misc{skeinKNR10,
author = {Dmitry Khovratovich and Ivica Nikolić and Christian Rechberger},
title = {Rotational Rebound Attacks on Reduced Skein},
howpublished = {Cryptology ePrint Archive, Report 2010/538},
year = {2010},
url = {http://eprint.iacr.org/2010/538.pdf},
abstract = {In this paper we combine the recent rotational cryptanalysis with the rebound attack, which results in the best cryptanalysis of Skein, a candidate for the SHA-3 competition. The rebound attack approach was so far only applied to AES-like constructions. For the first time, we show that this approach can also be applied to very different constructions. In more detail, we develop a number of techniques that extend the reach of both the inbound and the outbound phase, leading to rotational collisions for about 53/57 out of the 72 rounds of the Skein-256/512 compression function and the Threefish cipher. At this point, the results do not threaten the security of the full-round Skein hash function.

The new techniques include an analytical search for optimal input values in the rotational cryptanalysis, which allows to extend the outbound phase of the attack with a precomputation phase, an approach never used in any rebound-style attack before. Further we show how to combine multiple inside-out computations and neutral bits in the inbound phase of the rebound attack, and give well-defined rotational distinguishers as certificates of weaknesses for the compression functions and block ciphers.}
}
</bibtex>

<bibtex>
@misc{skeinSuWWD10,
author = {Bozhan Su and Wenling Wu and Shuang Wu and Le Dong},
title = {Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE},
howpublished = {Cryptology ePrint Archive, Report 2010/355},
year = {2010},
url = {http://eprint.iacr.org/2010/355.pdf},
abstract = {The SHA-3 competition organized by NIST aims to find a new hash standard as a replacement of SHA-2. Till now, 14 submissions have been selected as the second round candidates, including Skein and BLAKE, both of which have components based on modular addition, rotation and bitwise XOR (ARX). In this paper, we propose improved near-collision attacks on the reduced-round compression functions of Skein and a variant of BLAKE. The attacks are based on linear differentials of the modular additions. The computational complexity of near-collision attacks on a 4-round compression function of BLAKE-32, 4-round and 5-round compression functions of BLAKE-64 are 2^{21}, 2^{16} and 2^{216} respectively, and the attacks on a 24-round compression functions of Skein-256, Skein-512 and Skein-1024 have a complexity of 2^{60}, 2^{230} and 2^{395} respectively.}
}
</bibtex>

<bibtex>
@misc{skeinGli10,
author = {Danilo Gligoroski},
title = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains},
url = {http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf},
howpublished = {NIST mailing list},
year = {2010},
}
</bibtex>

<bibtex>
@misc{skeinMV10,
author = {Kerry A. McKay and Poorvi L. Vora},
title = {Pseudo-Linear Approximations for ARX Ciphers: With Application to Threefish},
howpublished = {Cryptology ePrint Archive, Report 2010/282},
year = {2010},
url = {http://eprint.iacr.org/2010/282.pdf},
note = {\url{http://eprint.iacr.org/}},
abstract = {The operations addition modulo 2^n and exclusive-or have recently been combined to obtain an efficient mechanism for nonlinearity in block cipher design. In this paper, we show that ciphers using this approach may be approximated by pseudo-linear expressions relating groups of contiguous bits of the round key, round input, and round output. The bias of an approximation can be large enough for known plaintext attacks. We demonstrate an application of this concept to a reduced-round version of the Threefish block cipher, a component of the Skein entry in the secure hash function competition.}
}
</bibtex>

<bibtex>
@misc{skeinKam10,
author = {Alan Kaminsky},
title = {Cube Test Analysis of the Statistical Behavior of CubeHash and Skein},
howpublished = {Cryptology ePrint Archive, Report 2010/262},
year = {2010},
url = {http://eprint.iacr.org/2010/262.pdf},
note = {\url{http://eprint.iacr.org/}},
abstract = {This work analyzes the statistical properties of the SHA-3 candidate cryptographic hash algorithms CubeHash and Skein to try to find nonrandom behavior. Cube tests were used to probe each algorithm's internal polynomial structure for a large number of choices of the polynomial input variables. The cube test data were calculated on a 40-core hybrid SMP cluster parallel computer. The cube test data were subjected to three statistical tests: balance, independence, and off-by-one. Although isolated statistical test failures were observed, the balance and off-by-one tests did not find nonrandom behavior overall in either CubeHash or Skein. However, the independence test did find nonrandom behavior overall in both CubeHash and Skein. }
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2009:526,
author = {Dmitry Khovratovich and Ivica Nikolic},
title = {Rotational Cryptanalysis of ARX},
howpublished = {Preproceedings of FSE 2010},
year = {2010},
url = {http://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf},
abstract = {In this paper we analyze the security of systems based on
modular additions, rotations, and XORs (ARX systems). We provide
both theoretical support for their security and practical cryptanalysis of
real ARX primitives. We use a technique called rotational cryptanalysis,
that is universal for the ARX systems and is quite efficient. We illustrate
the method with the best known attack on reduced versions of the block
cipher Threeﬁsh (the core of Skein). Additionally, we prove that ARX
with constants are functionally complete, i.e. any function can be realized
with these operations.
},
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2009:526,
author = {Jiazhe Chen and Keting Jia},
title = {Improved Related-key Boomerang Attacks on Round-Reduced Threefish-512},
howpublished = {Cryptology ePrint Archive, Report 2009/526},
year = {2009},
url = {http://eprint.iacr.org/2009/526.pdf},
note = {\url{http://eprint.iacr.org/}},
abstract = {Hash function Skein is one of the 14 NIST SHA-3 second round candidates. Threefish is a tweakable block cipher as the core of Skein, defined with a 256-, 512-, and 1024-bit block size. The 512-bit block size is the primary proposal of the authors. In this paper we construct two related-key boomerang distinguishers on round-reduced Threefish-512 using the method of \emph{modular differential}. With a distinguisher on 32 rounds of Threefish-512, we improve the key recovery attack on 32 rounds of Threefish-512 proposed by Aumasson et al. Their attack requires $2^{312}$ encryptions and $2^{71}$ bytes of memory. However, our attack has a time complexity of $2^{226}$ encryptions with memory of $2^{12}$ bytes. Furthermore, we give a key recovery attack on Threefish-512 reduced to 33 rounds using a 33-round related-key boomerang distinguisher, with $2^{352.17}$ encryptions and negligible memory. Skein had been updated after it entered the second round and the results above are based on the original version. However, as the only differences between the original and the new version are the rotation constants, both of the methods can be applied to the new version with modified differential trails. For the new rotation constants, our attack on 32-round Threefish-512 has a time complexity $2^{222}$ and $2^{12}$ bytes' memory. Our attack on 33-round Threefish-512 has a time complexity $2^{355.5}$ and negligible memory.},
}
</bibtex>

<bibtex>
@misc{skeinA+09,
author = {Jean-Philippe Aumasson and Cagdas Calik and Willi Meier and Onur Ozen and Raphael C.-W. Phan and Kerem Varici},
title = {Improved Cryptanalysis of Skein},
howpublished = {Cryptology ePrint Archive, Report 2009/438},
year = {2009},
url = {http://eprint.iacr.org/2009/438.pdf},
note = {\url{http://eprint.iacr.org/}},
abstract={The hash function Skein is the submission of Ferguson et al. to the NIST Hash Competition, and is arguably a serious candidate for selection as SHA-3. This paper presents the first third-party analysis of Skein, with an extensive study of its main component: the block cipher Threefish. We notably investigate near collisions, distinguishers, impossible differentials, key recovery using related-key differential and boomerang attacks. In particular, we present near collisions on up to 17 rounds, an impossible differential on 21 rounds, a related-key boomerang distinguisher on 34 rounds, a known-related-key boomerang distinguisher on 35 rounds, and key recovery attacks on up to 32 rounds, out of 72 in total for Threefish-512. None of our attacks directly extends to the full Skein hash. However, the pseudorandomness of Threefish is required to validate the security proofs on Skein, and our results conclude that at least 36 rounds of Threefish seem required for optimal security guarantees.},
}
</bibtex>

<bibtex>
@misc{SkeinAum09,
author = {Jean-Philippe Aumasson and Willi Meier and Raphael Phan},
title = {Improved analyis of Threefish},
url = {http://131002.net/data/talks/threefish_rump.pdf},
howpublished = {FSE 2009 rump session, slides available online},
year = {2009},
}
</bibtex>

The SHA-3 Zoo

2010-12-13T07:58:04Z

Fmendel:

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://eprint.iacr.org/2008/511.pdf here].
 
The idea of the SHA-3 Zoo is to give a good overview of cryptanalytic results. We try to avoid additional judgement whether a submission is broken. The answer to this question is left to NIST. However, we categorize the cryptanalytic results by their impact from very theoretic to practical attacks. A detailed description is given in [[Cryptanalysis Categories]].

At this time, 56 out of 64 submissions to the SHA-3 competition are publicly known and available. 51 submissions have advanced to [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/index.html round 1] and 14 submissions have made it into [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/index.html round 2].

The following table should give a first impression on the remaining SHA-3 candidates. It shows only the best known attack, more detailed results are collected at the individual hash function pages. A description of the main table is given [[Cryptanalysis_Categories#Main_Cryptanalysis_Table | here]].

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

The 5 finalists of the SHA-3 competition are:

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
! width="120"| Hash Name !! width="160" | Principal Submitter !! width="150"| Best Attack on Main NIST Requirements !! width="140"| Best Attack on other Hash Requirements
|-
| [[BLAKE]] || Jean-Philippe Aumasson || ||
|-
| [[Groestl|Grøstl]] || Lars R. Knudsen || ||
|-
| [[JH]] || Hongjun Wu || style="background:greenyellow" | preimage ||
|-
| [[Keccak]] || The Keccak Team || ||
|-
| [[Skein]] || Bruce Schneier || ||
|-
|}

The following SHA-3 candidates advanced to round 2 but did not get into the final:

[http://ehash.iaik.tugraz.at/uploads/c/ce/20090922-2230_SHA-3_round2_tweaks.pdf Round 2 tweaks for all candidates]

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
! width="120"| Hash Name !! width="160" | Principal Submitter !! width="150"| Best Attack on Main NIST Requirements !! width="140"| Best Attack on other Hash Requirements
|-
| [[Blue Midnight Wish]] || Svein Johan Knapskog || ||
|-
| [[CubeHash]] || Daniel J. Bernstein || style="background:greenyellow" | preimage ||
|-
| [[ECHO]] || Henri Gilbert || ||
|-
| [[Fugue]] || Charanjit S. Jutla || ||
|-
| [[Hamsi]] || <nowiki>Özgül Küçük</nowiki> || ||
|-
| [[Luffa]] || Dai Watanabe || ||
|-
| [[Shabal]] || <nowiki>Jean-François Misarsky</nowiki> || ||
|-
| [[SHAvite-3]] || Orr Dunkelman || ||
|-
| [[SIMD]] || <nowiki>Gaëtan Leurent</nowiki> || ||
|-
|}

The following submitted hash functions have not advanced to round 2:

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
! width="120"| Hash Name !! width="160" | Principal Submitter !! width="120" | Status !! width="150"| Best Attack on Main NIST Requirements !! width="140"| Best Attack on other Hash Requirements
|-
| [[Abacus]] || Neil Sholer || in round 1 || style="background:orange" | 2nd-preimage ||
|-
| [[ARIRANG]] || Jongin Lim || in round 1 || ||
|-
| [[AURORA]] || Masahiro Fujita || in round 1|| style="background:orange"| 2nd preimage ||
|-
| [[Blender]] || Colin Bradbury || in round 1|| style="background:orange" | collision, preimage || near-collision
|-
| [[Boole]] || Greg Rose || in round 1 || style="background:red" | collision ||
|-
| [[Cheetah]] || Dmitry Khovratovich || in round 1|| || length-extension
|-
| [[CHI]] || Phillip Hawkes || in round 1|| ||
|-
| [[CRUNCH]] || Jacques Patarin || in round 1|| || length-extension
|-
| [[DCH]] || David A. Wilson || in round 1 || style="background:red" | collision ||
|-
| [[Dynamic SHA]] || Xu Zijie || in round 1|| style="background:red"|collision || length-extension
|-
| [[Dynamic SHA2]] || Xu Zijie || in round 1|| style="background:orange"|collision || length-extension
|-
| [[ECOH]] || Daniel R. L. Brown || in round 1|| style="background:orange"| 2nd preimage ||
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || Danilo Gligoroski || in round 1|| style="background:yellow" | preimage ||
|-
| [[EnRUPT]] || Sean O'Neil || in round 1|| style="background:red" | collision ||
|-
| [[ESSENCE]] || Jason Worth Martin || in round 1|| style="background:orange" | collision ||
|-
| [[FSB (SHA-3 submission) | FSB]] || Matthieu Finiasz || in round 1|| ||
|-
| [[HASH 2X]] || Jason Lee || not in round 1 || style="background:red" | 2nd-preimage ||
|-
| [[Khichidi-1]] || M. Vidyasagar || in round 1 || style="background:red" | collision ||
|-
| [[LANE]] || Sebastiaan Indesteege || in round 1|| ||
|-
| [[Lesamnta]] || Hirotaka Yoshida || in round 1|| ||
|-
| [[LUX]] || <nowiki>Ivica Nikolić</nowiki> || in round 1|| style="background:orange" | collision, 2nd preimage || DRBG,HMAC
|-
| [[Maraca]] || Robert J. Jenkins || not in round 1 || style="background:red" | preimage ||
|-
| [[MCSSHA-3]] || Mikhail Maslennikov || in round 1|| style="background:orange" | 2nd preimage ||
|-
| [[MD6]] || Ronald L. Rivest || in round 1|| ||
|-
| [[MeshHash]] || Björn Fay || in round 1 || style="background:orange" | 2nd preimage ||
|-
| [[NaSHA]] || Smile Markovski || in round 1|| style="background:orange" | collision ||
|-
| [[NKS2D]] || Geoffrey Park || not in round 1 || style="background:red" | collision ||
|-
| [[Ponic]] || Peter Schmidt-Nielsen || not in round 1 || style="background:yellow" | 2nd-preimage
|-
| [[SANDstorm]] || Rich Schroeppel || in round 1|| ||
|-
| [[Sarmal]] || <nowiki>Kerem Varıcı</nowiki> || in round 1|| style="background:yellow" | preimage ||
|-
| [[Sgàil]] || Peter Maxwell|| in round 1|| style="background:red" | collision ||
|-
| [[SHAMATA]] || Orhun Kara || in round 1 || style="background:red" | collision ||
|-
| [[Spectral Hash]] || <nowiki>Çetin Kaya Koç</nowiki> || in round 1|| style="background:red" | collision ||
|-
| [[StreamHash]] || Michal Trojnara || in round 1 || style="background:red" | collision ||
|-
| [[SWIFFTX]] || Daniele Micciancio || in round 1|| ||
|-
| [[Tangle]] || Rafael Alvarez || in round 1 || style="background:red" | collision ||
|-
| [[TIB3]] || Daniel Penazzi || in round 1|| style="background:yellow" | collision ||
|-
| [[Twister]] || Michael Gorski || in round 1|| style="background:orange" | preimage ||
|-
| [[Vortex (SHA-3 submission)|Vortex]] || Michael Kounavis || in round 1|| style="background:yellow" | preimage ||
|-
| [[WaMM]] || John Washburn || in round 1 || style="background:red" | collision ||
|-
| [[Waterfall]] || Bob Hattersley || in round 1 || style="background:orange" | collision ||
|-
| [[ZK-Crypt]] || Carmi Gressel || not in round 1 || ||
|}

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

Hamsi

2010-07-05T12:55:44Z

Fmendel:

== The algorithm ==

* Author(s): Özgül Kücük
* Website: [http://homes.esat.kuleuven.be/~okucuk/hamsi/ http://homes.esat.kuleuven.be/~okucuk/hamsi/]
* NIST submission package:
**round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Hamsi_Round2.zip Hamsi_Round2.zip] (old versions: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Hamsi.zip Hamsi.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/HamsiUpdate.zip HamsiUpdate.zip])

<bibtex>
@misc{sha3Kucuk09,
author = {Özgül Küçük},
title = {The Hash Function Hamsi},
url = {http://www.cosic.esat.kuleuven.be/publications/article-1203.pdf},
howpublished = {Submission to NIST (updated)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3Kucuk08,
author = {Özgül Küçük},
title = {The Hash Function Hamsi},
url = {http://ehash.iaik.tugraz.at/uploads/9/95/Hamsi.pdf},
howpublished = {Submission to NIST},
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 parameters: '''(3,6)''' P,Pf rounds (n=224,256); '''(6,12)''' P,Pf rounds (n=384,512).

=== Hash function ===

Here we list results on the actual hash function. 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 Function Part || Hash Size (n) || Parameters/Variants || 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
|-
| observations || hash || all || || || || [http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf Gligoroski]
|-
| non-randomness || compression function || 224, 256 || 5 rounds || || || [http://ehash.iaik.tugraz.at/uploads/d/db/Hamsi_nonrandomness.txt Aumasson]
|-
| near-collision || compression function || 224, 256 || 3 rounds || 221 || || [http://rump2009.cr.yp.to/936779b3afb9b48a404b487d6865091d.pdf Nikolic]
|-
| distinguisher || compression function || 224, 256 || 6 rounds || 227 || || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
|-
| distinguisher || compression function || 384, 512 || 12 rounds || 2729 || || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
|-
| near-collision || compression function || 224, 256 || 3 rounds || 25 || || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
|-
| near-collision || compression function || 224, 256 || 4 rounds || 232 || || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
|-
| near-collision || compression function || 224, 256 || 5 rounds || 2125 || || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
|-
| message-recovery || compression function || 224, 256 || 3 rounds || 210.48 || || [http://eprint.iacr.org/2010/057.pdf Calik,Turan]
|-
| pseudo-2nd-preimage || hash function || 256 || (3,6) rounds || 2254.25 || || [http://eprint.iacr.org/2010/057.pdf Calik,Turan]
|-
|}

<bibtex>
@misc{hamsiGli10,
author = {Danilo Gligoroski},
title = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains},
url = {http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf},
howpublished = {NIST mailing list},
year = {2010},
}
</bibtex>

<bibtex>
@misc{hamsiAum09,
author = {Jean-Philippe Aumasson},
title = {On the pseudorandomness of Hamsi},
url = {http://ehash.iaik.tugraz.at/uploads/d/db/Hamsi_nonrandomness.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{hamsiN09,
author = {Ivica Nikolic},
title = {Near Collisions for the Compression Function of Hamsi-256},
url = {http://rump2009.cr.yp.to/936779b3afb9b48a404b487d6865091d.pdf},
howpublished = {CRYPTO rump session},
year = {2009},
}
</bibtex>

<bibtex>
@misc{hamsiAM9,
author = {Jean-Philippe Aumasson and Willi Meier},
title = {Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi},
url = {http://www.131002.net/data/papers/AM09.pdf},
howpublished = {NIST mailing list},
year = {2009},
abstract = {We present a new type of distinguisher, called zero-sum distinguisher, and apply it to reduced versions of the Keccak-f permutation. We obtain practical and deterministic distinguishers on up to 9 rounds, and shortcut distinguishers on up to 16 rounds, out of 18 in total. These observations do not seem to affect the security of Keccak. We also briefly describe application of zero-sum distinguishers to the core permutations of Luffa and Hamsi.},
}
</bibtex>

<bibtex>
@misc{hamsiWWJW09,
author = {Meiqin Wang, Xiaoyun Wang, Keting Jia, Wei Wang},
title = {New Pseudo-Near-Collision Attack on Reduced-Round of Hamsi-256},
howpublished = {Cryptology ePrint Archive, Report 2009/484},
year = {2009},
note = {\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2009/484.pdf},
abstract = {Hamsi-256 is designed by Özgül Kücük and it has been a candidate Hash function for the second round of SHA-3. The compression function of Hamsi-256 maps a 256-bit chaining value and a 32-bit message to a new 256-bit chaining value. As hashing a message, Hamsi-256 operates 3-round except for the last message it operates 6-round. In this paper, we will give the pseudo-near-collision for 5-round Hamsi-256. By the message modifying, the pseudo-near-collision for 3, 4 and 5 rounds can be found with $2^5$, $2^{32}$ and $2^{125}$ compression function computations respectively.},
}
</bibtex>

<bibtex>
@misc{hamsiWWJW09,
author = {Cagdas Calik and Meltem Sonmez Turan},
title = {Message Recovery and Pseudo-Preimage Attacks on the Compression Function of Hamsi-256},
howpublished = {Cryptology ePrint Archive, Report 2010/057}},
year = {2010},
note = {\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2010/057.pdf},
abstract = {Hamsi is one of the second round candidates of the SHA-3
competition. In this study, we present non-random differential proper-
ties for the compression function of the hash function Hamsi-256. Based
on these properties, we first demonstrate a distinguishing attack that
requires a few evaluations of the compression function and extend the
distinguisher to 5 rounds with complexity 2^83 . Then, we present a mes-
sage recovery attack with complexity of 2^10.48 compression function evaluations. Also, we present a pseudo-preimage attack for the compression
function with complexity 2^254.25 . The pseudo-preimage attack on the
compression function is easily converted to a pseudo second preimage
attack on Hamsi-256 hash function with the same complexity.},
}
</bibtex>

Groestl

2010-07-05T12:55:25Z

Fmendel:

Fugue

2010-07-05T12:55:03Z

Fmendel:

== The algorithm ==

* Author(s): Shai Halevi and William E. Hall and Charanjit S. Jutla
* Website: [http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html]
* NIST submission package:
** round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Fugue_Round2_Update.zip Fugue_Round2_Update.zip] (old versions: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Fugue.zip Fugue.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/FugueUpdate.zip FugueUpdate.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Fugue_Round2.zip Fugue_Round2.zip])

<bibtex>
@misc{sha3Halevi09,
author = {Shai Halevi and William E. Hall and Charanjit S. Jutla},
title = {The Hash Function Fugue},
url = {http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html/$FILE/fugue_09.pdf},
howpublished = {Submission to NIST (updated)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3Halevi08,
author = {Shai Halevi and William E. Hall and Charanjit S. Jutla},
title = {The Hash Function Fugue},
url = {http://domino.research.ibm.com/comm/research_projects.nsf/pages/fugue.index.html/$FILE/NIST-submission-Oct08-fugue.pdf},
howpublished = {Submission to NIST},
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 parameters: (k,r,t) = '''(2,5,13)''' for (n=224,256); (k,r,t) = '''(3,5,13)''' for (n=384); (k,r,t) = '''(4,8,13)''' for (n=512)

=== 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
|-
| distinguisher(1) || output transformation || 256 || || 1 || - || [http://ehash.iaik.tugraz.at/uploads/c/cd/Fugue_path.pdf Aumasson,Phan]
|-
| internal collision || hash function || 256 || (2,5,13) || 2352 || 2352 || [http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf Khovratovich]
|-
| internal collision || hash function || 512 || (4,8,13) || 2480 || 2480 || [http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf Khovratovich]
|-
|}
(1)The Fugue team commented on these distinguishers in [http://ehash.iaik.tugraz.at/uploads/d/d7/Fugue_designers_reply_to_AumassonPhan_Distinguisher.txt this note] using [http://ehash.iaik.tugraz.at/uploads/c/c8/Fig7.pdf this figure].

<bibtex>
@misc{nistAP10,
author = {Jean-Philippe Aumasson and Raphael C.-W. Phan},
title = {Analysis of Fugue-256},
howpublished = {Posting to NIST hash mailing list},
year = {2010},
url = {http://ehash.iaik.tugraz.at/uploads/c/cd/Fugue_path.pdf},
abstract = {We would like to report our analysis results on the final round algorithm of
Fugue-256 (i.e., the function called "G"):

The attached pdf note shows an example differential characteristic of
probability 1, on 15 intermediate rounds of G, as well as an extended
characteristic that can be used as a distinguisher for the full
18-round G. It also shows how differences propagate on an
augmented-round version of G (i.e. if more G2 rounds were added).

A detailed analysis as well as further observations will be reported
in a subsequent paper.
},
}
</bibtex>

<bibtex>
@misc{sacKhovratovich09,
author = {Dmitry Khovratovich},
title = {Cryptanalysis of hash functions with structures},
howpublished = {Proceedings of Selected Areas in Cryptography},
year = {2009},
url = {http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf},
abstract = {Hash function cryptanalysis has acquired many methods,
tools and tricks from other areas, mostly block ciphers. In this paper
another trick from block cipher cryptanalysis, the structures, is used for
speeding up the collision search. We investigate the memory and the time
complexities of this approach under different assumptions on the round
functions. The power of the new attack is illustrated with the crypt-
analysis of the hash functions Grindahl and the analysis of the SHA-3
candidate Fugue (both functions as 256 and 512 bit versions). The collision attack on Grindahl-512 is the first collision attack on this function.
},
}
</bibtex>

CubeHash

2010-07-05T12:54:06Z

Fmendel:

== The algorithm ==

* Author(s): Dan Bernstein
* Website: [http://cubehash.cr.yp.to/ http://cubehash.cr.yp.to/]
* NIST submission package:
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/CubeHash.zip CubeHash.zip]
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/CubeHash_Round2.zip CubeHash_Round2.zip]

<bibtex>
@misc{sha3Bernstein09a,
author = {Daniel J. Bernstein},
title = {CubeHash specification (2.B.1)},
url = {http://cubehash.cr.yp.to/submission2/spec.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3Bernstein09,
author = {Daniel J. Bernstein},
title = {CubeHash parameter tweak: 16 times faster},
url = {http://cubehash.cr.yp.to/submission/tweak.pdf},
howpublished = {Available online},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3Bernstein08,
author = {Daniel J. Bernstein},
title = {CubeHash Specification (2.B.1)},
url = {http://cubehash.cr.yp.to/submission/spec.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 parameters: r/b = '''16/32''' (n=224,256); '''16/32''' (n=384,512)

=== 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/Variants || Compression Function Calls || Memory Requirements || Reference
|-
| style="background:greenyellow" | preimage || 384,512 || r/32 || 2383.7 || - || [http://eprint.iacr.org/2010/273.pdf Ferguson,Lucks,McKay]
|-
| preimage || 384,512 || r/33 || 2257.6 || - || [http://eprint.iacr.org/2010/273.pdf Ferguson,Lucks,McKay]
|-
| collision || 512 || 7/64 || 2203 || - || [http://eprint.iacr.org/2009/382.pdf Brier,Khazaei,Meier,Peyrin]
|-
| collision || all || 4/48 || example (237) || - || [http://ehash.iaik.tugraz.at/uploads/5/50/Bkmp_ch448.txt Brier,Khazaei,Meier,Peyrin]
|-
| collision || all || 4/64 || example (234) || - || [http://ehash.iaik.tugraz.at/uploads/9/93/Bkmp_ch464.txt Brier,Khazaei,Meier,Peyrin]
|-
| collision || all || 3/64 || example (224) || - || [http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt Brier,Khazaei,Meier,Peyrin]
|-
| collision || 512 || 2/2 || 2196 || - || [http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt Brier,Khazaei,Meier,Peyrin]
|-
| collision || 512 || 5/64 || 2231 || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || all || 3/64 || 289 || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || 512 || 4/3 || 2207 || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || 384,512 || 4/4 || 2189 || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || all || 2/3 || 246 || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || 512 || 2/4 || example || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || 512 || 1/45, 2/89 || example || - || [http://www.cryptopp.com/sha3/cubehash.pdf Dai]
|-
| collision || 512 || 2/120 || example || - || [http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt Aumasson]
|-
| preimage || 512 || r/8 || 2480 || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolic',Weinmann]
|-
| preimage || 512 || r/4 || 2496 || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolic',Weinmann]
|-
| style="background:greenyellow" | preimage || 512 || r/1 (round 1) || 2511 || 2508 || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolic',Weinmann]
|-
| style="background:greenyellow" | preimage || all || r/b || 2513-4b || - || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
|-
| collision || all || r/b || 2521-4b-log b || - || [http://cubehash.cr.yp.to/submission/generic.pdf submission document]
|-
| style="background:greenyellow" | preimage || all || r/b || 2522-4b-log b || - || [http://cubehash.cr.yp.to/submission/generic.pdf submission document]
|-
|}

=== 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
|-
| observations || hash || all || || || || [http://eprint.iacr.org/2010/262.pdf Kaminsky]
|-
| observations || hash || all || || || || [http://eprint.iacr.org/2009/407.pdf Bloom,Kaminsky]
|-
| multi-collision || hash || all || || 2513-4b || - || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
|-
| observations || permutation|| all || || || || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
|-
|}

<bibtex>
@misc{cubehashFLM10,
author = {Niels Ferguson and Stefan Lucks and Kerry A. McKay},
title = {Symmetric States and their Structure: Improved Analysis of CubeHash},
howpublished = {Cryptology ePrint Archive, Report 2010/273},
year = {2010},
url = {http://eprint.iacr.org/2010/273.pdf},
note = {\url{http://eprint.iacr.org/}},
abtract = {This paper provides three improvements over previous work on analyzing CubeHash, based on its classes of symmetric states: (1) We present a detailed analysis of the hierarchy of symmetry classes. (2) We point out some flaws in previously claimed attacks which tried to exploit the symmetry classes. (3) We present and analyze new multicollision and preimage attacks. For the default parameter setting of CubeHash, namely for a message block size of b = 32, the new attacks are slightly faster than 2^384 operations. If one increases the size of a message block by a single byte to b = 33, our multicollision and preimage attacks become much faster – they only require about 2^256 operations. This demonstrates how sensitive the security of CubeHash is, depending on minor changes of the tunable security parameter b. }
}
</bibtex>

<bibtex>
@misc{cubehashKam10,
author = {Alan Kaminsky},
title = {Cube Test Analysis of the Statistical Behavior of CubeHash and Skein},
howpublished = {Cryptology ePrint Archive, Report 2010/262},
year = {2010},
url = {http://eprint.iacr.org/2010/262.pdf},
note = {\url{http://eprint.iacr.org/}},
abstract = {This work analyzes the statistical properties of the SHA-3 candidate cryptographic hash algorithms CubeHash and Skein to try to find nonrandom behavior. Cube tests were used to probe each algorithm's internal polynomial structure for a large number of choices of the polynomial input variables. The cube test data were calculated on a 40-core hybrid SMP cluster parallel computer. The cube test data were subjected to three statistical tests: balance, independence, and off-by-one. Although isolated statistical test failures were observed, the balance and off-by-one tests did not find nonrandom behavior overall in either CubeHash or Skein. However, the independence test did find nonrandom behavior overall in both CubeHash and Skein. }
}
</bibtex>

<bibtex>
@misc{cubehashBK09,
author = {Benjamin Bloom and Alan Kaminsky},
title = {Single Block Attacks and Statistical Tests on CubeHash},
howpublished = {Cryptology ePrint Archive, Report 2009/407},
year = {2009},
url = {http://eprint.iacr.org/2009/407.pdf},
note = {\url{http://eprint.iacr.org/}},
abstract = {This paper describes a second preimage attack on the CubeHash cryptographic one-way hash function. The attack finds a second preimage in less time than brute force search for these CubeHash variants: CubeHash $r$/$b$-224 for $b > 100$; CubeHash$r$/$b$-256 for $b > 96$; CubeHash$r$/$b$-384 for $b > 80$; and CubeHash$r$/$b$-512 for $b > 64$. However, the attack does not break the CubeHash variants recommended for SHA-3. The attack requires minimal memory and can be performed in a massively parallel fashion. This paper also describes several statistical randomness tests on CubeHash. The tests were unable to disprove the hypothesis that CubeHash behaves as a random mapping. These results support CubeHash's viability as a secure cryptographic hash function.},
}
</bibtex>

<bibtex>
@misc{cubehashBKMP09b,
author = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
title = {Linearization Framework for Collision Attacks: Application to CubeHash and MD6},
howpublished = {Cryptology ePrint Archive, Report 2009/382},
year = {2009},
url = {http://eprint.iacr.org/2009/382.pdf},
note = {\url{http://eprint.iacr.org/}},
abstract = {In this paper, an improved differential cryptanalysis framework for finding collisions in hash functions is provided. Its principle is based on linearization of compression functions in order to find low weight differential characteristics as initiated by Chabaud and Joux. This is formalized and refined however in several ways: for the problem of finding a conforming message pair whose differential trail follows a linear trail, a condition function is introduced so that finding a collision is equivalent to finding a preimage of the zero vector for the condition function. Then, the dependency table concept shows how much influence every input bit of the condition function has on its output bits. Careful analysis of the dependency table reveals degrees of freedom that can be exploited in accelerated preimage reconstruction of the condition function. These concepts are applied to an in-depth collision analysis of reduced-round versions of the two SHA-3 candidates CubeHash and MD6, and are demonstrated to give by far the best currently known collision attacks on these SHA-3 candidates.},
}
</bibtex>

<bibtex>
@misc{cubehashBKMP09a,
author = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
title = {Real Collisions for CubeHash-4/48},
url = {http://ehash.iaik.tugraz.at/uploads/5/50/Bkmp_ch448.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{cubehashBKMP09a,
author = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
title = {Real Collisions for CubeHash-4/64},
url = {http://ehash.iaik.tugraz.at/uploads/9/93/Bkmp_ch464.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{cubehashBKMP09,
author = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
title = {Attack for CubeHash-2/2 and collision for CubeHash-3/64},
url = {http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>


<bibtex>
@misc{cubehashBP09,
author = {Eric Brier and Thomas Peyrin},
title = {Cryptanalysis of CubeHash},
url = {http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf},
howpublished = {Available online},
year = {2009},
abstract = {CubeHash is a family of hash functions submitted by Bern stein as a SHA-3 candidate. In this paper, we provide two different cryptanalysis approaches concerning its collision resistance. Thanks to the first approach, related to truncated differentials, we computed a collision for the CubeHash-1/36 hash function, i.e. when for each iteration 36 bytes of message are incorporated and one call to the permutation is applied. Then, the second approach, already used by Dai, much more efficient and simply based on a linearization of the scheme, allowed us to compute a collision for the CubeHash-2/4 hash function. Finally, a theoretical collision attack against CubeHash-2/3, CubeHash-4/4 and CubeHash-4/3 is described. This is currently the best known cryptanalysis result on this SHA-3 candidate.},
}
</bibtex>

<bibtex>
@misc{cubehashD08,
author = {Wei Dai},
title = {Collisions for CubeHash1/45 and CubeHash2/89},
url = {http://www.cryptopp.com/sha3/cubehash.pdf},
howpublished = {Available online},
year = {2008},
abstract = {Collisions were found for the hash functions CubeHash1/45-512 and CubeHash2/89-512. Attack code is included.},
}
</bibtex>

<bibtex>
@misc{cubehashA08,
author = {Jean-Philippe Aumasson},
title = {Collision for CubeHash2/120-512},
url = {http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt},
howpublished = {NIST mailing list (local link)},
year = {2008},
}
</bibtex>

<bibtex>
@misc{cubehashKNW08,
author = {Dmitry Khovratovich and Ivica Nikolic' and Ralf-Philipp Weinmann},
title = {Preimage attack on CubeHash512-r/4 and CubeHash512-r/8},
url = {http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf},
howpublished = {Available online},
year = {2008},
}
</bibtex>

<bibtex>
@inproceedings{cubehashAMPP09,
author = {Jean-Philippe Aumasson and Eric Brier and Willi Meier and María Naya-Plasencia and Thomas Peyrin},
title = {Inside the Hypercube},
booktitle = {ACISP},
publisher = {Springer},
editor = {Colin Boyd and Juan Manuel Gonz{\'a}lez Nieto},
series = {LNCS},
pages = {202-213},
volume = {5594},
url = {http://www.131002.net/data/papers/ABMNP08.pdf},
year = {2009},
abstract = {Bernstein’s CubeHash is a hash function family that includes four functions submitted to the NIST Hash Competition. A CubeHash function is parametrized by a number of rounds r, a block byte size b, and a digest bit length h. The 1024-bit internal state of CubeHash is represented as a five-dimension hypercube. Submissions to NIST have r = 8, b = 1, and $h \in {224, 256, 384, 512}$.
This paper gives the first external analysis of CubeHash, with
- improved standard generic attacks for collisions and preimages
- a multicollision attack that exploits fixed points
- a study of the round function symmetries
- a preimage attack that exploits these symmetries
- a practical collision attack on a weakened version of CubeHash
- high-probability truncated differentials over the 8-round transform
Our results do not contradict the security claims about CubeHash.},
}
</bibtex>

Blue Midnight Wish

2010-07-05T12:53:29Z

Fmendel:

== 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
|-
| 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]
|-
|}

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

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

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

BLAKE

2010-07-05T12:53:01Z

Fmendel:

== The algorithm ==

* Author(s): Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
* Website: [http://131002.net/blake/ http://131002.net/blake/]
* NIST submission package:
** round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/BLAKE_Round2.zip BLAKE_Round2.zip] (old versions: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/BLAKE.zip BLAKE.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/BLAKEUpdate.zip BLAKEUpdate.zip])

<bibtex>
@misc{sha3AumassonHMP08,
author = {Jean-Philippe Aumasson and Luca Henzen and Willi Meier and Raphael C.-W. Phan},
title = {SHA-3 proposal BLAKE},
url = {http://131002.net/blake/blake.pdf},
howpublished = {Submission to NIST},
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: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)

=== 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
|-
| preimage || 224,256 || 2.5 rounds || 2n-15 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| preimage || 384 || 2.5 rounds || 2355 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| preimage || 512 || 2.5 rounds || 2481 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
|}

=== 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
|-
| near-collision || compression function || 256 || 4 rounds (No. 4-7) || 221 || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
|-
| near-collision || compression function || 512 || 4 rounds (No. 7-10) || 216 || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
|-
| near-collision || compression function || 512 || 5 rounds (No. 7-11) || 2216 || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
|-
| observations || hash || all || || || || [http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf Gligoroski]
|-
| impossible differential || permutation || 224,256 || 5 rounds || - || - || [http://eprint.iacr.org/2010/043.pdf Aumasson,Guo,Knellwolf,Matusiewicz,Meier]
|-
| impossible differential || permutation || 384,512 || 6 rounds || - || - || [http://eprint.iacr.org/2010/043.pdf Aumasson,Guo,Knellwolf,Matusiewicz,Meier]
|-
| near-collision || compression function || 256 || 4 rounds (No. 3-6) || 256 || - || [http://www.jguo.org/docs/blake-col.pdf Guo,Matusiewicz]
|-
| free-start collision || hash || 224,256 || 2.5 rounds || 2n/2-16 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| free-start collision || hash || 384,512 || 2.5 rounds || 2n/2-32 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
|}

<bibtex>
@misc{blakeSuWWD10,
author = {Bozhan Su and Wenling Wu and Shuang Wu and Le Dong},
title = {Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE},
howpublished = {Cryptology ePrint Archive, Report 2010/355},
year = {2010},
url = {http://eprint.iacr.org/2010/355.pdf},
abstract = {The SHA-3 competition organized by NIST aims to find a new hash standard as a replacement of SHA-2. Till now, 14 submissions have been selected as the second round candidates, including Skein and BLAKE, both of which have components based on modular addition, rotation and bitwise XOR (ARX). In this paper, we propose improved near-collision attacks on the reduced-round compression functions of Skein and a variant of BLAKE. The attacks are based on linear differentials of the modular additions. The computational complexity of near-collision attacks on a 4-round compression function of BLAKE-32, 4-round and 5-round compression functions of BLAKE-64 are 2^{21}, 2^{16} and 2^{216} respectively, and the attacks on a 24-round compression functions of Skein-256, Skein-512 and Skein-1024 have a complexity of 2^{60}, 2^{230} and 2^{395} respectively.}
}
</bibtex>

<bibtex>
@misc{blakeGli10,
author = {Danilo Gligoroski},
title = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains},
url = {http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf},
howpublished = {NIST mailing list},
year = {2010},
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2010:043,
author = {Jean-Philippe Aumasson and Jian Guo and Simon Knellwolf
and Krystian Matusiewicz and Willi Meier},
title = {Differential and invertibility properties of BLAKE (full version)},
howpublished = {Cryptology ePrint Archive, Report 2010/043},
year = {2010},
url = {http://eprint.iacr.org/2010/043.pdf},
abstract = {BLAKE is a hash function selected by NIST as one of
the 14 second round candidates for the SHA-3 Competition. In this
paper, we follow a bottom-up approach to exhibit properties of BLAKE
and of its building blocks: based on differential properties of the
internal function G, we show that a round of BLAKE is a permutation on
the message space, and present an efficient inversion algorithm. For
1.5 rounds we present an algorithm that finds preimages faster than in
previous attacks. Discovered properties lead us to describe large
classes of impossible differentials for two rounds of BLAKE’s internal
permutation, and particular impossible differentials for five and six
rounds, respectively for BLAKE- 32 and BLAKE-64. Then, using a linear
and rotation-free model, we describe near-collisions for four rounds
of the compression function. Finally, we discuss the problem of
establishing upper bounds on the probability of differential
characteristics for BLAKE.},
}
</bibtex>

<bibtex>
@misc{blakeGM09,
author = {Jian Guo and Krystian Matusiewicz},
title = {Round-Reduced Near-Collisions of BLAKE-32},
url = {http://www.jguo.org/docs/blake-col.pdf},
howpublished = {Available online},
note = {Accepted for presentation at WEWoRC 2009},
year = {2009}
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2009:238,
author = {Li Ji and Xu Liangyu },
title = {Attacks on Round-Reduced BLAKE},
howpublished = {Cryptology ePrint Archive, Report 2009/238},
year = {2009},
note = {\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2009/238.pdf},
abstract = {BLAKE is a new hash family proposed for SHA-3. The
core of compression function reuses the core function of ChaCha. A
round-dependent permutation is used as message schedule. BLAKE is
claimed to achieve full diffusion after 2 rounds. However, message
words can be controlled on the first several founds. By exploiting
properties of message permutation, we can attack 2.5 reduced rounds.
The results do not threat the security claimed in the specification.
},
}
</bibtex>

ECHO

2010-07-05T12:52:41Z

Fmendel:

== The algorithm ==

* Author(s): Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin
* Website: http://crypto.rd.francetelecom.com/echo/
* NIST submission package:
** round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/ECHO_Round2.zip ECHO_Round2.zip] (old version [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/ECHO.zip ECHO.zip])

<bibtex>
@misc{sha3BBG+09,
author = {Ryad Benadjila and Olivier Billet and Henri Gilbert and Gilles Macario-Rat and Thomas Peyrin and Matt Robshaw and Yannick Seurin},
title = {SHA-3 Proposal: ECHO},
url = {http://crypto.rd.francetelecom.com/echo/doc/echo_description_1-5.pdf},
howpublished = {Submission to NIST (updated)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3BBG+08,
author = {Ryad Benadjila and Olivier Billet and Henri Gilbert and Gilles Macario-Rat and Thomas Peyrin and Matt Robshaw and Yannick Seurin},
title = {SHA-3 Proposal: ECHO},
url = {http://crypto.rd.francetelecom.com/echo/doc/echo_description.pdf},
howpublished = {Submission to NIST},
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: '''8''' rounds (n=224,256); '''10''' rounds (n=384,512)

=== 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
|-
| distinguisher || 256 || 5 rounds || 296 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| near-collision|| 256 || 4.5 rounds || 296 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| collision|| 256 || 4 rounds || 264 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
|}

=== 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
|-
| distinguisher (chosen salt) || compression function || 256 || 7 rounds || 2107 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| free-start near-collision (chosen salt) || compression function || 256 || 6.5 rounds || 296 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| distinguisher (chosen salt) || compression function || 512 || 7 rounds || 2106 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| free-start near-collision (chosen salt) || compression function || 512|| 6.5 rounds || 296 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| semi-free-start collision || compression function || 256 || 3 rounds || 264 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| distinguisher || compression function || 256 || 4 rounds || 264 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| semi-free-start collision || compression function || 512 || 3 rounds || 296 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| distinguisher || compression function || 512 || 6 rounds || 296 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| distinguisher || permutation || all || 8 rounds || 2768 || 2512 || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
|-
| distinguisher || permutation || all || 7 rounds || 2384 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=110408 Mendel,Peyrin,Rechberger,Schläffer]
|-
| distinguisher || permutation || all || 7 rounds || 2896 || - || [http://crypto.rd.francetelecom.com/echo/doc/echo_description_1-5.pdf submission document]
|-
|}

<bibtex>
@misc{Pey10,
author = {Thomas Peyrin},
title = {Improved Differential Attacks for ECHO and Grostl},
howpublished = {Cryptology ePrint Archive, Report 2010/223},
year = {2010},
note = {\url{http://eprint.iacr.org/}},
abstract = {We present improved cryptanalysis of two second-round SHA-3 candidates: the AES-based hash functions ECHO and Grostl. We explain methods for building better differential trails for ECHO by increasing the granularity of the truncated differential paths previously considered. In the case of Grostl, we describe a new technique, the internal differential attack, which shows that when using parallel computations designers should also consider the differential security between the parallel branches. Then, we exploit the recently introduced start-from-the-middle or Super-Sbox attacks, that proved to be very efficient when attacking AES-like permutations, to achieve a very efficient utilization of the available freedom degrees. Finally, we obtain the best known attacks so far for both ECHO and Grostl. In particular, we are able to mount a distinguishing attack for the full Grostl-256 compression function.},
}
</bibtex>

<bibtex>
@inproceedings{fseGP10,
author = {Henri Gilbert and Thomas Peyrin},
title = {Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations},
url = {http://eprint.iacr.org/2009/531.pdf},
booktitle = {FSE},
year = {2010},
series = {LNCS},
note = {To appear}
abstract = {In this paper, we improve the recent rebound and start-from-the-middle attacks on AES-like permutations. Our new cryptanalysis technique uses the fact that one can view two rounds of such permutations as a layer of big Sboxes preceded and followed by simple affine transformations. The big Sboxes encountered in this alternative representation are named Super-Sboxes. We apply this method to two second-round SHA-3 candidates Grostl and ECHO, and obtain improvements over the previous cryptanalysis results for these two schemes. Moreover, we improve the best distinguisher for the AES block cipher in the known-key setting, reaching 8 rounds for the 128-bit version.}
</bibtex>

<bibtex>
@inproceedings{sacMPRS09,
author = {Florian Mendel and Thomas Peyrin and Christian
Rechberger and Martin Schläffer},
title = {Improved Cryptanalysis of the Reduced Grøstl
Compression Function, ECHO Permutation and AES Block Cipher},
url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420},
booktitle = {SAC},
year = {2009},
volume = {5867},
pages = {16-35},
abstract = {In this paper, we propose two new ways to mount attacks
on the SHA-3 candidates Gr{\o}stl, and ECHO, and apply these attacks
also to the AES. Our results improve upon and extend the rebound
attack. Using the new techniques, we are able to extend the number of
rounds in which available degrees of freedom can be used. As a result,
we present the first attack on 7 rounds for the Gr{\o}stl-256 output
transformation and improve the semi-free-start collision attack on 6
rounds. Further, we present an improved known-key distinguisher for 7
rounds of the AES block cipher and the internal permutation used in
ECHO.}
</bibtex>

<bibtex>
@misc{cryptoeprint:2010:321,
author = {Martin Schläffer},
title = {Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function},
howpublished = {Cryptology ePrint Archive, Report 2010/321},
year = {2010},
note = {\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2010/321.pdf},
abstract = {In this work we present the first results for the ECHO hash function. We provide a subspace distinguisher for 5/8 rounds, near-collisions on 4.5/8 rounds and collisions for 4/8 rounds of the ECHO-256 hash function. The complexities are $2^{96}$ compression function calls for the distinguisher and near-collision attack, and $2^{64}$ for the collision attack. The memory requirements are $2^{64}$ for all attacks. Furthermore, we provide improved compression function attacks on ECHO-256 to get a distinguisher on 7/8 rounds and near-collisions for 6.5/8 rounds with chosen salt. The compression function attacks also apply to ECHO-512. To get these results, we consider new and sparse truncated differential paths through ECHO. We are able to construct these paths by analyzing the combined MixColumns and BigMixColumns transformation. Since in these sparse truncated differential paths at most 1/4 of all bytes of each ECHO state are active, missing degrees of freedom are not a problem. Therefore, we are able to mount a rebound attack with multiple inbound phases to efficiently find according message pairs for ECHO.},
}
</bibtex>

ECHO

2010-07-05T12:34:16Z

Fmendel: Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function

== The algorithm ==

* Author(s): Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin
* Website: http://crypto.rd.francetelecom.com/echo/
* NIST submission package:
** round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/ECHO_Round2.zip ECHO_Round2.zip] (old version [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/ECHO.zip ECHO.zip])

<bibtex>
@misc{sha3BBG+09,
author = {Ryad Benadjila and Olivier Billet and Henri Gilbert and Gilles Macario-Rat and Thomas Peyrin and Matt Robshaw and Yannick Seurin},
title = {SHA-3 Proposal: ECHO},
url = {http://crypto.rd.francetelecom.com/echo/doc/echo_description_1-5.pdf},
howpublished = {Submission to NIST (updated)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3BBG+08,
author = {Ryad Benadjila and Olivier Billet and Henri Gilbert and Gilles Macario-Rat and Thomas Peyrin and Matt Robshaw and Yannick Seurin},
title = {SHA-3 Proposal: ECHO},
url = {http://crypto.rd.francetelecom.com/echo/doc/echo_description.pdf},
howpublished = {Submission to NIST},
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: '''8''' rounds (n=224,256); '''10''' rounds (n=384,512)

=== 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" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements || Reference
|-
| distinguisher || 256 || 5 rounds || 296 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| near-collision|| 256 || 4.5 rounds || 296 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| collision|| 256 || 4 rounds || 264 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
|}

=== 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
|-
| distinguisher (chosen salt) || compression function || 256 || 7 rounds || 2107 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| free-start near-collision (chosen salt) || compression function || 256 || 6.5 rounds || 296 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| distinguisher (chosen salt) || compression function || 512 || 7 rounds || 2106 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| free-start near-collision (chosen salt) || compression function || 512|| 6.5 rounds || 296 || 264 || [http://eprint.iacr.org/2010/321.pdf Schläffer]
|-
| semi-free-start collision || compression function || 256 || 3 rounds || 264 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| distinguisher || compression function || 256 || 4 rounds || 264 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| semi-free-start collision || compression function || 512 || 3 rounds || 296 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| distinguisher || compression function || 512 || 6 rounds || 296 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| distinguisher || permutation || all || 8 rounds || 2768 || 2512 || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
|-
| distinguisher || permutation || all || 7 rounds || 2384 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=110408 Mendel,Peyrin,Rechberger,Schläffer]
|-
| distinguisher || permutation || all || 7 rounds || 2896 || - || [http://crypto.rd.francetelecom.com/echo/doc/echo_description_1-5.pdf submission document]
|-
|}

<bibtex>
@misc{Pey10,
author = {Thomas Peyrin},
title = {Improved Differential Attacks for ECHO and Grostl},
howpublished = {Cryptology ePrint Archive, Report 2010/223},
year = {2010},
note = {\url{http://eprint.iacr.org/}},
abstract = {We present improved cryptanalysis of two second-round SHA-3 candidates: the AES-based hash functions ECHO and Grostl. We explain methods for building better differential trails for ECHO by increasing the granularity of the truncated differential paths previously considered. In the case of Grostl, we describe a new technique, the internal differential attack, which shows that when using parallel computations designers should also consider the differential security between the parallel branches. Then, we exploit the recently introduced start-from-the-middle or Super-Sbox attacks, that proved to be very efficient when attacking AES-like permutations, to achieve a very efficient utilization of the available freedom degrees. Finally, we obtain the best known attacks so far for both ECHO and Grostl. In particular, we are able to mount a distinguishing attack for the full Grostl-256 compression function.},
}
</bibtex>

<bibtex>
@inproceedings{fseGP10,
author = {Henri Gilbert and Thomas Peyrin},
title = {Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations},
url = {http://eprint.iacr.org/2009/531.pdf},
booktitle = {FSE},
year = {2010},
series = {LNCS},
note = {To appear}
abstract = {In this paper, we improve the recent rebound and start-from-the-middle attacks on AES-like permutations. Our new cryptanalysis technique uses the fact that one can view two rounds of such permutations as a layer of big Sboxes preceded and followed by simple affine transformations. The big Sboxes encountered in this alternative representation are named Super-Sboxes. We apply this method to two second-round SHA-3 candidates Grostl and ECHO, and obtain improvements over the previous cryptanalysis results for these two schemes. Moreover, we improve the best distinguisher for the AES block cipher in the known-key setting, reaching 8 rounds for the 128-bit version.}
</bibtex>

<bibtex>
@inproceedings{sacMPRS09,
author = {Florian Mendel and Thomas Peyrin and Christian
Rechberger and Martin Schläffer},
title = {Improved Cryptanalysis of the Reduced Grøstl
Compression Function, ECHO Permutation and AES Block Cipher},
url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420},
booktitle = {SAC},
year = {2009},
volume = {5867},
pages = {16-35},
abstract = {In this paper, we propose two new ways to mount attacks
on the SHA-3 candidates Gr{\o}stl, and ECHO, and apply these attacks
also to the AES. Our results improve upon and extend the rebound
attack. Using the new techniques, we are able to extend the number of
rounds in which available degrees of freedom can be used. As a result,
we present the first attack on 7 rounds for the Gr{\o}stl-256 output
transformation and improve the semi-free-start collision attack on 6
rounds. Further, we present an improved known-key distinguisher for 7
rounds of the AES block cipher and the internal permutation used in
ECHO.}
</bibtex>

<bibtex>
@misc{cryptoeprint:2010:321,
author = {Martin Schläffer},
title = {Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function},
howpublished = {Cryptology ePrint Archive, Report 2010/321},
year = {2010},
note = {\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2010/321.pdf},
abstract = {In this work we present the first results for the ECHO hash function. We provide a subspace distinguisher for 5/8 rounds, near-collisions on 4.5/8 rounds and collisions for 4/8 rounds of the ECHO-256 hash function. The complexities are $2^{96}$ compression function calls for the distinguisher and near-collision attack, and $2^{64}$ for the collision attack. The memory requirements are $2^{64}$ for all attacks. Furthermore, we provide improved compression function attacks on ECHO-256 to get a distinguisher on 7/8 rounds and near-collisions for 6.5/8 rounds with chosen salt. The compression function attacks also apply to ECHO-512. To get these results, we consider new and sparse truncated differential paths through ECHO. We are able to construct these paths by analyzing the combined MixColumns and BigMixColumns transformation. Since in these sparse truncated differential paths at most 1/4 of all bytes of each ECHO state are active, missing degrees of freedom are not a problem. Therefore, we are able to mount a rebound attack with multiple inbound phases to efficiently find according message pairs for ECHO.},
}
</bibtex>

Groestl

2010-06-15T14:23:18Z

Fmendel: fixed bibtex entry

SIMD

2010-05-27T11:25:42Z

Fmendel: Cryptanalysis of the Compression Function of SIMD

== The algorithm ==

* Author(s): Gaëtan Leurent, Charles Bouillaguet, Pierre-Alain Fouque
* Website: [http://www.di.ens.fr/~leurent/simd.html http://www.di.ens.fr/~leurent/simd.html]
* NIST submission package:
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SIMDUpdate.zip SIMDUpdate.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SIMD.zip SIMD.zip])
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/SIMD_Round2.zip SIMD_Round2.zip]

<bibtex>
@misc{sha3LBF09,
author = {Gaëtan Leurent and Charles Bouillaguet and Pierre-Alain Fouque},
title = {SIMD Is a Message Digest},
url = {http://www.di.ens.fr/~leurent/files/SIMD.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3LBF08,
author = {Gaëtan Leurent and Charles Bouillaguet and Pierre-Alain Fouque},
title = {SIMD Is a Message Digest},
url = {http://ehash.iaik.tugraz.at/uploads/4/4e/Simd.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: total number of steps = '''32'''

=== 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" 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
|-
| free-start near-collision || compression || 256 || 20 steps || 2107 || - || [http://eprint.iacr.org/2010/304.pdf Yu, Wang]
|-
| free-start near-collision || compression || 512 || 24 steps || 2208 || - || [http://eprint.iacr.org/2010/304.pdf Yu, Wang]
|-
| distinguisher || compression || 512 || full || 2398 || - || [http://eprint.iacr.org/2010/304.pdf Yu, Wang]
|-
| distinguisher || compression || 512 || 12 steps || 2236 || - || [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 || 512 || linear message exp., 24 steps || 2497 || - || [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 || 512 || full (Round 1) || 5*2425.28 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=125658 Mendel, Nad]
|-
|}

<bibtex>
@misc{cryptoeprint:2010:304,
author = {Hongbo Yu and Xiaoyun Wang},
title = {Cryptanalysis of the Compression Function of SIMD},
howpublished = {Cryptology ePrint Archive, Report 2010/304},
url={http://eprint.iacr.org/2010/304.pdf},
year = {2010},
note = {\url{http://eprint.iacr.org/}},
abstract={SIMD is one of the second round candidates of the SHA-3 competition hosted by NIST. In this paper, we present some results on the compression function of SIMD 1.1 (the tweaked version) using the modular difference method. For SIMD-256, We give a free-start near collision attack on the compression function reduced to 20 steps with complexity $2^{-107}$. And for SIMD-512, we give a free-start near collision attack on the 24-step compression function with complexity $2^{208}$. Furthermore, we give a distinguisher attack on the full compression function of SIMD-512 with complexity $2^{398}$. Our attacks are also applicable for the final compression function of SIMD.},
}
</bibtex>

<bibtex>
@misc{bmwNikolicPST,
author = {Ivica Nikolić, Josef Pieprzyk, 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>
@inproceedings{indocryptMendelN09,
author = {Florian Mendel and
Tomislav Nad},
title = {A Distinguisher for the Compression Function of SIMD-512},
booktitle = {INDOCRYPT},
editor = {Bimal K. Roy and
Nicolas Sendrier},
publisher = {Springer},
series = {LNCS},
year = {2009},
pages = {219-232},
volume = {5922},
url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=125658},
abstract = {SIMD is one of the round 2 candidates of the public SHA-3
competition hosted by NIST. It was designed by Leurent et al.. In this
paper, we present a distinguisher attack on the compression function of
SIMD-512. By linearizing the compression function we construct a linear
code. Using techniques from coding theory to search for low Hamming
weight codewords, we can find differential characteristics with low Hamming
weight (and hence high probability). In the attack the differences
are introduced only in the IV . Such a characteristic is the base for our distinguisher,
which can distinguish the compression function of SIMD-512
from random with a complexity of 5*2^425.28 compression function calls.
Furthermore, we can distinguish the output transformation of SIMD-512
from random with a complexity of about 22*2^425.28 compression function
calls. So far this is the first cryptanalytic result for the SIMD hash
function}
}
</bibtex>

Hamsi

2010-03-08T15:28:59Z

Fmendel:

== The algorithm ==

* Author(s): Özgül Kücük
* Website: [http://homes.esat.kuleuven.be/~okucuk/hamsi/ http://homes.esat.kuleuven.be/~okucuk/hamsi/]
* NIST submission package:
**round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Hamsi_Round2.zip Hamsi_Round2.zip] (old versions: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Hamsi.zip Hamsi.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/HamsiUpdate.zip HamsiUpdate.zip])

<bibtex>
@misc{sha3Kucuk09,
author = {Özgül Küçük},
title = {The Hash Function Hamsi},
url = {http://www.cosic.esat.kuleuven.be/publications/article-1203.pdf},
howpublished = {Submission to NIST (updated)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3Kucuk08,
author = {Özgül Küçük},
title = {The Hash Function Hamsi},
url = {http://ehash.iaik.tugraz.at/uploads/9/95/Hamsi.pdf},
howpublished = {Submission to NIST},
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 parameters: '''(3,6)''' P,Pf rounds (n=224,256); '''(6,12)''' P,Pf rounds (n=384,512).

=== Hash function ===

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

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

=== 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 || compression function || 224, 256 || 5 rounds || || || [http://ehash.iaik.tugraz.at/uploads/d/db/Hamsi_nonrandomness.txt Aumasson]
|-
| | near-collision || compression function || 224, 256 || 3 rounds || 221 || || [http://rump2009.cr.yp.to/936779b3afb9b48a404b487d6865091d.pdf Nikolic]
|-
| | distinguisher || compression function || 224, 256 || 6 rounds || 227 || || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
|-
| | distinguisher || compression function || 384, 512 || 12 rounds || 2729 || || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
|-
| | near-collision || compression function || 224, 256 || 3 rounds || 25 || || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
|-
| | near-collision || compression function || 224, 256 || 4 rounds || 232 || || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
|-
| | near-collision || compression function || 224, 256 || 5 rounds || 2125 || || [http://eprint.iacr.org/2009/484.pdf Wang,Wang,Jia,Wang]
|-
| | message-recovery || compression function || 224, 256 || 3 rounds || 210.48 || || [http://eprint.iacr.org/2010/057.pdf Calik,Turan]
|-
| | pseudo-2nd-preimage || hash function || 256 || (3,6) rounds || 2254.25 || || [http://eprint.iacr.org/2010/057.pdf Calik,Turan]
|-
|}

<bibtex>
@misc{hamsiAum09,
author = {Jean-Philippe Aumasson},
title = {On the pseudorandomness of Hamsi},
url = {http://ehash.iaik.tugraz.at/uploads/d/db/Hamsi_nonrandomness.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{hamsiN09,
author = {Ivica Nikolic},
title = {Near Collisions for the Compression Function of Hamsi-256},
url = {http://rump2009.cr.yp.to/936779b3afb9b48a404b487d6865091d.pdf},
howpublished = {CRYPTO rump session},
year = {2009},
}
</bibtex>

<bibtex>
@misc{hamsiAM9,
author = {Jean-Philippe Aumasson and Willi Meier},
title = {Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi},
url = {http://www.131002.net/data/papers/AM09.pdf},
howpublished = {NIST mailing list},
year = {2009},
abstract = {We present a new type of distinguisher, called zero-sum distinguisher, and apply it to reduced versions of the Keccak-f permutation. We obtain practical and deterministic distinguishers on up to 9 rounds, and shortcut distinguishers on up to 16 rounds, out of 18 in total. These observations do not seem to affect the security of Keccak. We also briefly describe application of zero-sum distinguishers to the core permutations of Luffa and Hamsi.},
}
</bibtex>

<bibtex>
@misc{hamsiWWJW09,
author = {Meiqin Wang, Xiaoyun Wang, Keting Jia, Wei Wang},
title = {New Pseudo-Near-Collision Attack on Reduced-Round of Hamsi-256},
howpublished = {Cryptology ePrint Archive, Report 2009/484},
year = {2009},
note = {\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2009/484.pdf},
abstract = {Hamsi-256 is designed by Özgül Kücük and it has been a candidate Hash function for the second round of SHA-3. The compression function of Hamsi-256 maps a 256-bit chaining value and a 32-bit message to a new 256-bit chaining value. As hashing a message, Hamsi-256 operates 3-round except for the last message it operates 6-round. In this paper, we will give the pseudo-near-collision for 5-round Hamsi-256. By the message modifying, the pseudo-near-collision for 3, 4 and 5 rounds can be found with $2^5$, $2^{32}$ and $2^{125}$ compression function computations respectively.},
}
</bibtex>

<bibtex>
@misc{hamsiWWJW09,
author = {Cagdas Calik and Meltem Sonmez Turan},
title = {Message Recovery and Pseudo-Preimage Attacks on the Compression Function of Hamsi-256},
howpublished = {Cryptology ePrint Archive, Report 2010/057}},
year = {2010},
note = {\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2010/057.pdf},
abstract = {Hamsi is one of the second round candidates of the SHA-3
competition. In this study, we present non-random differential proper-
ties for the compression function of the hash function Hamsi-256. Based
on these properties, we first demonstrate a distinguishing attack that
requires a few evaluations of the compression function and extend the
distinguisher to 5 rounds with complexity 2^83 . Then, we present a mes-
sage recovery attack with complexity of 2^10.48 compression function evaluations. Also, we present a pseudo-preimage attack for the compression
function with complexity 2^254.25 . The pseudo-preimage attack on the
compression function is easily converted to a pseudo second preimage
attack on Hamsi-256 hash function with the same complexity.},
}
</bibtex>

Groestl

2010-02-17T08:26:28Z

Fmendel: fixed bibtex entry

Skein

2010-02-16T08:30:05Z

Fmendel:

JH

2010-02-16T07:59:36Z

Fmendel:

== The algorithm ==

* Author(s): Hongjun Wu
* Website: [http://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/ http://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/]
* NIST submission package:
** 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://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/jh_round2.pdf},
howpublished = {Submission to NIST (updated)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3W08,
author = {Hongjun Wu},
title = {The Hash Function JH},
url = {http://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/jh.pdf},
howpublished = {Submission to NIST},
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].

=== 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 parameter: '''35.5''' rounds

{| 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
|-
| 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" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference
|-
| | pseudo-collision || compression || 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{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>

Fugue

2010-02-16T07:58:29Z

Fmendel:

SHAvite-3

2010-02-16T07:57:54Z

Fmendel:

== The algorithm ==

* Author(s): Eli Biham and Orr Dunkelman
* Website: [http://www.cs.technion.ac.il/~orrd/SHAvite-3/ http://www.cs.technion.ac.il/~orrd/SHAvite-3/]
* NIST submission package:
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SHAvite3Update.zip SHAvite3Update.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SHAvite-3.zip SHAvite-3.zip])
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/SHAvite-3_Round2.zip SHAvite-3_Round2.zip]

<bibtex>
@misc{sha3BihamD09,
author = {Eli Biham and Orr Dunkelman},
title = {The SHAvite-3 Hash Function},
url = {http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<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 (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].

=== 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 parameter: '''12''' rounds (n=224,256); '''14''' rounds (n=384,512)

{| 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
|-
| second preimage || 512 || 9 rounds || 2496 || 216 || [http://eprint.iacr.org/2009/634.pdf Bouillaguet et al.]
|-
|}

=== 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
|-
| pseudo-collision || compression || all || full (Round 1) || || || [http://ehash.iaik.tugraz.at/uploads/e/ea/Peyrin-SHAvite-3.txt Peyrin]
|-
| pseudo-collision || compression || 256 || full (Round 1) || || || [http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt Nandi,Paul]
|-
| impossible differential || block cipher || 224,256 || 5 rounds || - || - || [http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf submission document]
|-
| impossible differential || block cipher || 384,512 || 9 rounds || - || - || [http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf submission document]
|-
|}

<bibtex>
@misc{cryptoeprint:2009:634,
author = {Charles Bouillaguet and Orr Dunkelman and Ga\"etan Leurent and Pierre-Alain Fouque},
title = {Attacks on Hash Functions based on Generalized Feistel - Application to Reduced-Round Lesamnta and SHAvite-3_{512}},
howpublished = {Cryptology ePrint Archive, Report 2009/634},
year = {2009},
url= {http://eprint.iacr.org/2009/634.pdf},
abstract = {In this paper we study the strength of two hash functions which are based on Generalized Feistels. Our proposed attacks themselves are mostly independent of the round function in use, and can be applied to similar hash functions which share the same structure but have different round functions.

We start with a 22-round generic attack on the structure of Lesamnta, and adapt it to the actual round function to attack 24-round Lesamnta. We then show a generic integral attack on 20-round Lesamnta (which can be used against the block cipher itself). We follow with an attack on 9-round SHAvite-3_{512} which is the first cryptanalytic result on the hash function (which also works for the tweaked version of SHAvite-3_{512}).},
}
</bibtex>

<bibtex>
@misc{Peyrin-SHAvite-3,
author = {Thomas Peyrin},
title = {Chosen-salt, chosen-counter, pseudo-collision on SHAvite-3 compression function},
url = {http://ehash.iaik.tugraz.at/uploads/e/ea/Peyrin-SHAvite-3.txt},
howpublished = {Available online},
year = {2009},
}
</bibtex>

<bibtex>
@misc{NandiP-SHAvite-3,
author = {Mridul Nandi and Souradyuti Paul},
title = {OFFICIAL COMMENT: SHAvite-3},
url = {http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt},
howpublished = {Available online},
year = {2009},
}
</bibtex>

Blue Midnight Wish

2010-02-15T10:50:28Z

Fmendel:

SHAvite-3

2010-02-15T10:19:11Z

Fmendel: Attacks on Hash Functions based on Generalized Feistel - Application to Reduced-Round Lesamnta and SHAvite-3

== The algorithm ==

* Author(s): Eli Biham and Orr Dunkelman
* Website: [http://www.cs.technion.ac.il/~orrd/SHAvite-3/ http://www.cs.technion.ac.il/~orrd/SHAvite-3/]
* NIST submission package:
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SHAvite3Update.zip SHAvite3Update.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SHAvite-3.zip SHAvite-3.zip])
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/SHAvite-3_Round2.zip SHAvite-3_Round2.zip]

<bibtex>
@misc{sha3BihamD09,
author = {Eli Biham and Orr Dunkelman},
title = {The SHAvite-3 Hash Function},
url = {http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<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 (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].

=== Hash function ===

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

Recommended security parameter: '''12''' rounds (n=224,256); '''14''' rounds (n=384,512)

{| 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
|-
| second preimage || 512 || 9 rounds || 2496 || 216 || [http://eprint.iacr.org/2009/634.pdf Bouillaguet et al.]
|-
|}

=== 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
|-
| pseudo-collision || compression || all || full (Round 1) || || || [http://ehash.iaik.tugraz.at/uploads/e/ea/Peyrin-SHAvite-3.txt Peyrin]
|-
| pseudo-collision || compression || 256 || full (Round 1) || || || [http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt Nandi,Paul]
|-
| impossible differential || block cipher || 224,256 || 5 rounds || - || - || [http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf submission document]
|-
| impossible differential || block cipher || 384,512 || 9 rounds || - || - || [http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf submission document]
|-
|}

<bibtex>
@misc{cryptoeprint:2009:634,
author = {Charles Bouillaguet and Orr Dunkelman and Ga\"etan Leurent and Pierre-Alain Fouque},
title = {Attacks on Hash Functions based on Generalized Feistel - Application to Reduced-Round Lesamnta and SHAvite-3_{512}},
howpublished = {Cryptology ePrint Archive, Report 2009/634},
year = {2009},
url= {http://eprint.iacr.org/2009/634.pdf},
abstract = {In this paper we study the strength of two hash functions which are based on Generalized Feistels. Our proposed attacks themselves are mostly independent of the round function in use, and can be applied to similar hash functions which share the same structure but have different round functions.

We start with a 22-round generic attack on the structure of Lesamnta, and adapt it to the actual round function to attack 24-round Lesamnta. We then show a generic integral attack on 20-round Lesamnta (which can be used against the block cipher itself). We follow with an attack on 9-round SHAvite-3_{512} which is the first cryptanalytic result on the hash function (which also works for the tweaked version of SHAvite-3_{512}).},
}
</bibtex>

<bibtex>
@misc{Peyrin-SHAvite-3,
author = {Thomas Peyrin},
title = {Chosen-salt, chosen-counter, pseudo-collision on SHAvite-3 compression function},
url = {http://ehash.iaik.tugraz.at/uploads/e/ea/Peyrin-SHAvite-3.txt},
howpublished = {Available online},
year = {2009},
}
</bibtex>

<bibtex>
@misc{NandiP-SHAvite-3,
author = {Mridul Nandi and Souradyuti Paul},
title = {OFFICIAL COMMENT: SHAvite-3},
url = {http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt},
howpublished = {Available online},
year = {2009},
}
</bibtex>

SHAvite-3

2010-02-15T10:03:14Z

Fmendel:

== The algorithm ==

* Author(s): Eli Biham and Orr Dunkelman
* Website: [http://www.cs.technion.ac.il/~orrd/SHAvite-3/ http://www.cs.technion.ac.il/~orrd/SHAvite-3/]
* NIST submission package:
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SHAvite3Update.zip SHAvite3Update.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SHAvite-3.zip SHAvite-3.zip])
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/SHAvite-3_Round2.zip SHAvite-3_Round2.zip]

<bibtex>
@misc{sha3BihamD09,
author = {Eli Biham and Orr Dunkelman},
title = {The SHAvite-3 Hash Function},
url = {http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<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 (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].

=== Hash function ===

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

Recommended security parameter: '''12''' rounds (n=224,256); '''14''' rounds (n=384,512)

{| 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
|-
| | pseudo-collision || compression || all || full (Round 1) || || || [http://ehash.iaik.tugraz.at/uploads/e/ea/Peyrin-SHAvite-3.txt Peyrin]
|-
| | pseudo-collision || compression || 256 || full (Round 1) || || || [http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt Nandi,Paul]
|-
| impossible differential || block cipher || 224,256 || 5 rounds || - || - || [http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf submission document]
|-
| impossible differential || block cipher || 384,512 || 9 rounds || - || - || [http://www.cs.technion.ac.il/~orrd/SHAvite-3/Spec.15.09.09.pdf submission document]
|-
|}

<bibtex>
@misc{Peyrin-SHAvite-3,
author = {Thomas Peyrin},
title = {Chosen-salt, chosen-counter, pseudo-collision on SHAvite-3 compression function},
url = {http://ehash.iaik.tugraz.at/uploads/e/ea/Peyrin-SHAvite-3.txt},
howpublished = {Available online},
year = {2009},
}
</bibtex>

<bibtex>
@misc{NandiP-SHAvite-3,
author = {Mridul Nandi and Souradyuti Paul},
title = {OFFICIAL COMMENT: SHAvite-3},
url = {http://ehash.iaik.tugraz.at/uploads/5/5c/NandiP-SHAvite-3.txt},
howpublished = {Available online},
year = {2009},
}
</bibtex>

BLAKE

2010-02-04T14:56:06Z

Fmendel: fixed bibtex entry

== The algorithm ==

* Author(s): Jean-Philippe Aumasson, Luca Henzen, Willi Meier, Raphael C.-W. Phan
* Website: [http://131002.net/blake/ http://131002.net/blake/]
* NIST submission package:
** round 1/2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/BLAKE_Round2.zip BLAKE_Round2.zip] (old versions: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/BLAKE.zip BLAKE.zip], [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/BLAKEUpdate.zip BLAKEUpdate.zip])

<bibtex>
@misc{sha3AumassonHMP08,
author = {Jean-Philippe Aumasson and Luca Henzen and Willi Meier and Raphael C.-W. Phan},
title = {SHA-3 proposal BLAKE},
url = {http://131002.net/blake/blake.pdf},
howpublished = {Submission to NIST},
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].

=== Hash function ===

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

Recommended security parameters: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)

{| 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
|-
| preimage || 224,256 || 2.5 rounds || 2n-15 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| preimage || 384 || 2.5 rounds || 2355 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| preimage || 512 || 2.5 rounds || 2481 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
|}

=== 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
|-
| free-start collision || hash || 224,256 || 2.5 rounds || 2n/2-16 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| free-start collision || hash || 384,512 || 2.5 rounds || 2n/2-32 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| near-collision || compression function || 256 || 4 rounds (nb. 6-9) || 242 || - || [http://www.jguo.org/docs/blake-col.pdf Guo,Matusiewicz]
|-
| impossible differential || permutation || 224,256 || 5 rounds || - || - || [http://eprint.iacr.org/2010/043.pdf Aumasson,Guo,Knellwolf,Matusiewicz,Meier]
|-

| impossible differential || permutation || 384,512 || 6 rounds || - || - || [http://eprint.iacr.org/2010/043.pdf Aumasson,Guo,Knellwolf,Matusiewicz,Meier]
|-
|}

<bibtex>
@misc{cryptoeprint:2009:238,
author = {Li Ji and Xu Liangyu },
title = {Attacks on Round-Reduced BLAKE},
howpublished = {Cryptology ePrint Archive, Report 2009/238},
year = {2009},
note = {\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2009/238.pdf},
abstract = {BLAKE is a new hash family proposed for SHA-3. The core of compression function reuses the core function of ChaCha. A round-dependent permutation is used as message schedule. BLAKE is claimed to achieve full diffusion after 2 rounds. However, message words can be controlled on the first several founds. By exploiting properties of message permutation, we can attack 2.5 reduced rounds. The results do not threat the security claimed in the specification. },
}
</bibtex>

<bibtex>
@misc{blakeGM09,
author = {Jian Guo and Krystian Matusiewicz},
title = {Round-Reduced Near-Collisions of BLAKE-32},
url = {http://www.jguo.org/docs/blake-col.pdf},
howpublished = {Available online},
note = {Accepted for presentation at WEWoRC 2009},
year = {2009}
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2010:043,
author = {Jean-Philippe Aumasson and Jian Guo and Simon Knellwolf and Krystian Matusiewicz and Willi Meier},
title = {Differential and invertibility properties of BLAKE (full version)},
howpublished = {Cryptology ePrint Archive, Report 2010/043},
year = {2010},
url = {http://eprint.iacr.org/2010/043.pdf},
abstract = {BLAKE is a hash function selected by NIST as one of the 14 second round candidates for the SHA-3 Competition. In this paper, we follow a bottom-up approach to exhibit properties of BLAKE and of its building blocks: based on differential properties of the internal function G, we show that a round of BLAKE is a permutation on the message space, and present an efficient inversion algorithm. For 1.5 rounds we present an algorithm that finds preimages faster than in previous attacks. Discovered properties lead us to describe large classes of impossible differentials for two rounds of BLAKE’s internal permutation, and particular impossible differentials for five and six rounds, respectively for BLAKE- 32 and BLAKE-64. Then, using a linear and rotation-free model, we describe near-collisions for four rounds of the compression function. Finally, we discuss the problem of establishing upper bounds on the probability of differential characteristics for BLAKE.},
}
</bibtex>

Cryptanalysis Categories

2010-02-01T09:25:31Z

Fmendel:

For presentation reasons, we provide a ''simplified'' overview of cryptanalytic results in The SHA-3 Zoo. We only consider cryptanalytic results that have not been performed by the designers themselves and are included in the initial proposal. Exceptions are cryptanalytic results by non-designers and cryptanalytic results by designers that are not mentioned in the proposal.

== Color Codes ==

Different color codes should give a better overview of the impact of cryptanalytic results. The color codes are only used for results on the main NIST requirements of the full hash function with recommended parameters.

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
! width="100"| color !! Complexity of Result !! Explanation
|-
| style="background:greenyellow" | || compr. calls < generic || align="left" | The number of compression function calls (or equivalents) is below generic attacks for collision, 2nd preimage or preimage. The complexity of the attack is very close to generic attacks and is therefore of lesser relevance. Additionally, attacks in this simple model may neglect memory considerations. However, attacks of this type do not exist for the SHA-2 hash functions.
|-
| style="background:yellow" | || compr. calls < generic * 1/n || align="left" | The number of compression function calls (or equivalents) is below generic attacks reduced by a factor of n (hash size) for collision, 2nd preimage or preimage. Attacks in this simple model may neglect memory considerations. However, attacks of this type do not exist for the SHA-2 hash functions.
|-
| style="background:orange" | || time * memory < generic * 1/n || align="left" | The time*memory product is below generic attacks reduced by a factor of n (hash size) for collision, 2nd preimage or preimage.
|-
| style="background:red" | || practical example || align="left" | A practical example is given for the attack on this hash function. This is an extra category since practical examples improve the confidence in an attack.
|-
|}

== Main Cryptanalysis Table ==

The main table should give a first impression on the remaining SHA-3 candidates. It shows only the best known attack, more detailed results are given in the individual hash function tables.

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
! width="140"| column !! Explanation
|-
| style="background:#efefef;"| Hash Name || align="left" | More detailed information about this SHA-3 candidate is given at its WikiPage.
|-
| style="background:#efefef;"| Principal Submitter || align="left" | This column shows only the principal submitter. Additional contributors are listed at the individual hash function pages and all submitters are listed [http://ehash.iaik.tugraz.at/wiki/SHA-3_submitters here].
|-
| style="background:#efefef;"| Best Attack on Main NIST Requirements || align="left" | In this column the best collision, 2nd-preimage or preimage attack is shown. To give a quick overview of the complexity of the best attack, the cells are labeled with different colors.
|-
| style="background:#efefef;"| Best Attack on other Hash Requirements || align="left" | Best attack on additional requirements for a hash function not unambiguously specified by NIST yet.
|-
|}

== Individual Hash Function Tables ==

The individual hash function tables give a more detailed overview of the cryptanalytic results with its complexity. The order of entries does not imply a ranking of the attacks. A dash (-) in the individual table means that the complexities are neglible. A question mark (?) means that the information is not given or unclear. We ask the authors to include these results in the abstract of their publication.

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
! width="140"| column !! Explanation
|-
| style="background:#efefef;"| Type of Analysis || align="left" | This column gives a first impression what (requirement) has been analyzed. Some results do not violate any security requirements. Only attacks on the main NIST requirements and for the full hash function with recommended parameters are highlighted.
|-
| style="background:#efefef;"| Hash Function Part || align="left" | Shows which part of the hash function has been attacked.
|-
| style="background:#efefef;"| Hash Size (n) || align="left" | The hash sizes for which the attack applies with the given complexity.
|-
| style="background:#efefef;"| Parameters/Variants || align="left" | Gives the parameters for attacks on reduced variants. The column is left empty if the attack is on the recommended parameters of the designers.
|-
| style="background:#efefef;"| Compression Function Calls || align="left" | The number of compression function calls (or equivalents) as given by the authors.
|-
| style="background:#efefef;"| Memory Requirements || align="left" | The memory requirements of the attack as given by the authors.
|-
| style="background:#efefef;"| Reference || align="left" | A link the published result.
|-
|}

SHAvite-3

2009-11-24T08:16:25Z

Fmendel: fixed typo

Skein

2009-11-23T15:41:31Z

Fmendel: updated link to round 2 submission

SIMD

2009-11-23T15:37:36Z

Fmendel: updated link to round 2 submission

File:Simd.pdf

2009-11-23T15:37:16Z

Fmendel:

SHAvite-3

2009-11-23T15:27:01Z

Fmendel: updated link to round 2 submission

Shabal

2009-11-23T15:21:01Z

Fmendel: updated link to round 2 submission

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

{| 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 || permutation || all || (p,r)=(3,12) || 212 || || [http://131002.net/data/papers/Aum09.pdf Aumasson]
|-
| | non-randomness || permutation || all || any (p,r) || 1 || || [http://www.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf Knudsen,Matusiewicz,Thomsen]
|-
| | non-randomness || permutation || all || any (p,r) || 2 || || [http://131002.net/data/papers/AMM09.pdf Aumasson,Mashatan,Meier]
|-
|}

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

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

Luffa

2009-11-23T15:19:06Z

Fmendel: updated link to round 2 submission

== The algorithm ==

* Author(s): Christophe De Canniere, Hisayoshi Sato, Dai Watanabe
* Website: [http://www.sdl.hitachi.co.jp/crypto/luffa/ http://www.sdl.hitachi.co.jp/crypto/luffa/]
* NIST submission package:
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/LuffaUpdate.zip LuffaUpdate.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Luffa.zip Luffa.zip])
**round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Luffa_Round2_Update.zip Luffa_Round2_Update.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Luffa_Round2.zip Luffa_Round2.zip])

<bibtex>
@misc{sha3CHSW09,
author = {Christophe De Canniere and Hisayoshi Sato and Dai Watanabe},
title = {Hash Function Luffa: Specification},
url = {http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_Specification_20091002.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3CHSW09a,
author = {Christophe De Canniere and Hisayoshi Sato and Dai Watanabe},
title = {Hash Function Luffa: Supporting Document},
url = {http://www.sdl.hitachi.co.jp/crypto/luffa/Luffa_v2_SupportingDocument_20090915.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3CHSW08,
author = {Christophe De Canniere and Hisayoshi Sato and Dai Watanabe},
title = {Hash Function Luffa: Specification},
url = {http://ehash.iaik.tugraz.at/uploads/e/ea/Luffa_Specification.pdf},
howpublished = {Submission to NIST (Round 1)},
year = {2008},
}
</bibtex>

<bibtex>
@misc{sha3CHSW08a,
author = {Christophe De Canniere and Hisayoshi Sato and Dai Watanabe},
title = {Hash Function Luffa: Supporting Document},
url = {http://ehash.iaik.tugraz.at/uploads/f/fe/Luffa_SupportingDocument.pdf},
howpublished = {Submission to NIST (Round 1)},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

{| 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
|-
| pseudo-2nd preimage || hash || all || || 1 || - || [http://eprint.iacr.org/2009/224.pdf Jia]
|-
| pseudo-preimage || hash || 256 || || 2127 || - || [http://eprint.iacr.org/2009/224.pdf Jia]
|-
| pseudo-preimage || hash || 512 || || 2171 || - || [http://eprint.iacr.org/2009/224.pdf Jia]
|-
| distinguisher || permutation || || 4 rounds || ? || - || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
|-
|}

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

<bibtex>
@misc{cryptoeprint:2009:224,
author = {Keting Jia},
title = {Pseudo-Collision, Pseudo-Preimage and Pseudo-Second-Preimage Attacks on Luffa},
howpublished = {Cryptology ePrint Archive, Report 2009/224},
year = {2009},
note = {\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2009/224.pdf},
abstract = {In this paper, we show some pseudo-collision and pseudo-second-preimage examples for the SHA-3 candidate algorithm Luffa. The pseudo-collision and pseudo-second-preimage can be obtained easily by the message injection function. At the same time, the pseudo-preimage attacks are shown in this paper. For Luffa-224/256, only two iteration functions is needed to get the pseudo-preimage. We need $2^{127}$ and $2^{171}$ to get the pseudo-preimage for Luffa-384 and Luffa-512 respectively. },
}
</bibtex>

<bibtex>
@misc{hamsiAM9,
author = {Jean-Philippe Aumasson and Willi Meier},
title = {Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi},
url = {http://www.131002.net/data/papers/AM09.pdf},
howpublished = {NIST mailing list}
year = {2009},
abstract = {We present a new type of distinguisher, called zero-sum distinguisher, and apply it to reduced versions of the Keccak-f permutation. We obtain practical and deterministic distinguishers on up to 9 rounds, and shortcut distinguishers on up to 16 rounds, out of 18 in total. These observations do not seem to affect the security of Keccak. We also briefly describe application of zero-sum distinguishers to the core permutations of Luffa and Hamsi.},
</bibtex>

Keccak

2009-11-23T15:13:05Z

Fmendel: updated link to round 2 submission

== The algorithm ==

* Author(s): Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche
* Website: [http://keccak.noekeon.org/ http://keccak.noekeon.org/]
* NIST submission package:
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Keccak.zip Keccak.zip]
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Keccak_Round2.zip Keccak_Round2.zip]

<bibtex>
@misc{KeccakSpecs2,
author = {G. Bertoni and J. Daemen and M. Peeters and G. Van Assche},
title = {Keccak specifications},
url = {http://keccak.noekeon.org/Keccak-specifications-2.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{KeccakMain2,
author = {G. Bertoni and J. Daemen and M. Peeters and G. Van Assche},
title = {Keccak sponge function family main document},
url = {http://keccak.noekeon.org/Keccak-main-2.0.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{KeccakSpecs,
author = {G. Bertoni and J. Daemen and M. Peeters and G. Van Assche},
title = {Keccak specifications},
url = {http://keccak.noekeon.org/Keccak-specifications.pdf},
howpublished = {Submission to NIST (Round 1)},
year = {2008},
}
</bibtex>

<bibtex>
@misc{KeccakMain,
author = {G. Bertoni and J. Daemen and M. Peeters and G. Van Assche},
title = {Keccak sponge function family main document},
url = {http://keccak.noekeon.org/Keccak-main-1.0.pdf},
howpublished = {Submission to NIST (Round 1)},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

{| 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
|-
| observations || permutation || all || || || || [http://131002.net/data/papers/AK09.pdf Aumasson,Khovratovich]
|-
| cube attack || partial preimage || 224 || 4 rounds || 219 || ? || [http://www.cs.rit.edu/~jal6806/thesis/thesis.pdf Joel,Lathrop]
|-
| distinguisher || permutation || all || 16 rounds || 21023.88 || || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
|-
|}

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

<bibtex>
@misc{keccakAK09,
author = {Jean-Philippe Aumasson and Dmitry Khovratovich},
title = {First Analysis of Keccak},
url = {http://131002.net/data/papers/AK09.pdf},
howpublished = {Available online},
year = {2009},
abstract = {We apply known automated cryptanalytic tools to the Keccak-f[1600] permutation, using
a triangulation tool to solve the CICO problem, and cube testers to detect some structure in the
algebraic description of the reduced Keccak-f[1600]. The applicability of our tools was notably limited
by the strength of the inverse permutation.},
}
</bibtex>

<bibtex>
@misc{keccakAK09,
author = {Joel Lathrop},
title = {Cube Attacks on Cryptographic Hash Functions},
url = {http://www.cs.rit.edu/~jal6806/thesis/thesis.pdf},
howpublished = {Available online},
year = {2009},
abstract = {The thesis includes a successful cube attack against 4-round Keccak complete with a table of maxterms, analysis of the attack, and the estimated limits of its extension to higher numbers of rounds.},
}
</bibtex>

<bibtex>
@misc{hamsiAM9,
author = {Jean-Philippe Aumasson and Willi Meier},
title = {Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi},
url = {http://www.131002.net/data/papers/AM09.pdf},
howpublished = {NIST mailing list}
year = {2009},
abstract = {We present a new type of distinguisher, called zero-sum distinguisher, and apply it to reduced versions of the Keccak-f permutation. We obtain practical and deterministic distinguishers on up to 9 rounds, and shortcut distinguishers on up to 16 rounds, out of 18 in total. These observations do not seem to affect the security of Keccak. We also briefly describe application of zero-sum distinguishers to the core permutations of Luffa and Hamsi.},
</bibtex>

JH

2009-11-23T15:06:28Z

Fmendel: updated link to round 2 submission

== The algorithm ==

* Author(s): Hongjun Wu
* Website: [http://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/ http://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/]
* NIST submission package:
** 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://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/jh_round2.pdf},
howpublished = {Submission to NIST (updated)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3W08,
author = {Hongjun Wu},
title = {The Hash Function JH},
url = {http://icsd.i2r.a-star.edu.sg/staff/hongjun/jh/jh.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

{| 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
|-
| | pseudo-collision || compression || 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]
|-
| style="background:greenyellow" | preimage(1) || hash || 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]
|-
|}

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

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

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

Hamsi

2009-11-23T15:01:29Z

Fmendel: updated link to round 2 submission

Groestl

2009-11-23T14:58:05Z

Fmendel: updated link to round 2 submission

ECHO

2009-11-23T14:53:57Z

Fmendel:

ECHO

2009-11-23T14:53:50Z

Fmendel:

Fugue

2009-11-23T14:52:22Z

Fmendel:

Fugue

2009-11-23T14:49:12Z

Fmendel: updated link to round 2 submission

ECHO

2009-11-23T14:46:20Z

Fmendel: updated link to round 2 submission

CubeHash

2009-11-23T14:39:44Z

Fmendel: updated link to round 2 submission

== The algorithm ==

* Author(s): Dan Bernstein
* Website: [http://cubehash.cr.yp.to/ http://cubehash.cr.yp.to/]
* NIST submission package:
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/CubeHash.zip CubeHash.zip]
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/CubeHash_Round2.zip CubeHash_Round2.zip]

<bibtex>
@misc{sha3Bernstein09a,
author = {Daniel J. Bernstein},
title = {CubeHash specification (2.B.1)},
url = {http://cubehash.cr.yp.to/submission2/spec.pdf},
howpublished = {Submission to NIST (Round 2)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3Bernstein09,
author = {Daniel J. Bernstein},
title = {CubeHash parameter tweak: 16 times faster},
url = {http://cubehash.cr.yp.to/submission/tweak.pdf},
howpublished = {Available online},
year = {2009},
}
</bibtex>

<bibtex>
@misc{sha3Bernstein08,
author = {Daniel J. Bernstein},
title = {CubeHash Specification (2.B.1)},
url = {http://cubehash.cr.yp.to/submission/spec.pdf},
howpublished = {Submission to NIST (Round 1)},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

{| 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
|-
| style="background:greenyellow" | preimage || hash || all || || 2513-4b || ? || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
|-
| multi-collision || || all || || 2513-4b || ? || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
|-
| observations || || all || || || || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
|-
| style="background:greenyellow" | preimage || hash || 512 || || 2511 || 2508 || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
|-
| preimage || hash || 512 || r/4 || 2496 || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
|-
| preimage || hash || 512 || r/8 || 2480 || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
|-
| collision || hash || 512 || 2/120 || example || - || [http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt Aumasson]
|-
| collision || hash || 512 || 1/45, 2/89 || example || - || [http://www.cryptopp.com/sha3/cubehash.pdf Dai]
|-
| collision || hash || 512 || 2/4 || example || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || hash || all || 2/3 || 246 || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || hash || 384/512 || 4/4 || 2189 || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || hash || 512 || 4/3 || 2207 || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || hash || all || 3/64 || 289 || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || hash || 512 || 5/64 || 2231 || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
|-
| collision || hash || 512 || 2/2 || 2196 || - || [http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt Brier,Khazaei,Meier,Peyrin]
|-
| collision || hash || all || 3/64 || example (224) || - || [http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt Brier,Khazaei,Meier,Peyrin]
|-
| collision || hash || all || 4/64 || example (234) || - || [http://ehash.iaik.tugraz.at/uploads/9/93/Bkmp_ch464.txt Brier,Khazaei,Meier,Peyrin]
|-
| collision || hash || all || 4/48 || example (237) || - || [http://ehash.iaik.tugraz.at/uploads/5/50/Bkmp_ch448.txt Brier,Khazaei,Meier,Peyrin]
|-
| collision || hash || 512 || 7/64 || 2203 || - || [http://eprint.iacr.org/2009/382.pdf Brier,Khazaei,Meier,Peyrin]
|-
| observations || || all || || || || [http://eprint.iacr.org/2009/407.pdf Bloom,Kaminsky]
|-
|}

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

<bibtex>
@inproceedings{cubehashAMPP09,
author = {Jean-Philippe Aumasson and Eric Brier and Willi Meier and María Naya-Plasencia and Thomas Peyrin},
title = {Inside the Hypercube},
booktitle = {ACISP},
publisher = {Springer},
editor = {Colin Boyd and Juan Manuel Gonz{\'a}lez Nieto},
series = {LNCS},
pages = {202-213},
volume = {5594},
url = {http://www.131002.net/data/papers/ABMNP08.pdf},
year = {2009},
abstract = {Bernstein’s CubeHash is a hash function family that includes four functions submitted to the NIST Hash Competition. A CubeHash function is parametrized by a number of rounds r, a block byte size b, and a digest bit length h. The 1024-bit internal state of CubeHash is represented as a five-dimension hypercube. Submissions to NIST have r = 8, b = 1, and $h \in {224, 256, 384, 512}$.
This paper gives the first external analysis of CubeHash, with
- improved standard generic attacks for collisions and preimages
- a multicollision attack that exploits fixed points
- a study of the round function symmetries
- a preimage attack that exploits these symmetries
- a practical collision attack on a weakened version of CubeHash
- high-probability truncated differentials over the 8-round transform
Our results do not contradict the security claims about CubeHash.},
}
</bibtex>

<bibtex>
@misc{cubehashKNW08,
author = {Dmitry Khovratovich and Ivica Nikolić and Ralf-Philipp Weinmann},
title = {Preimage attack on CubeHash512-r/4 and CubeHash512-r/8},
url = {http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf},
howpublished = {Available online},
year = {2008},
}
</bibtex>

<bibtex>
@misc{cubehashA08,
author = {Jean-Philippe Aumasson},
title = {Collision for CubeHash2/120-512},
url = {http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt},
howpublished = {NIST mailing list (local link)},
year = {2008},
}
</bibtex>

<bibtex>
@misc{cubehashD08,
author = {Wei Dai},
title = {Collisions for CubeHash1/45 and CubeHash2/89},
url = {http://www.cryptopp.com/sha3/cubehash.pdf},
howpublished = {Available online},
year = {2008},
abstract = {Collisions were found for the hash functions CubeHash1/45-512 and CubeHash2/89-512. Attack code is included.},
}
</bibtex>


<bibtex>
@misc{cubehashBP09,
author = {Eric Brier and Thomas Peyrin},
title = {Cryptanalysis of CubeHash},
url = {http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf},
howpublished = {Available online},
year = {2009},
abstract = {CubeHash is a family of hash functions submitted by Bern stein as a SHA-3 candidate. In this paper, we provide two different cryptanalysis approaches concerning its collision resistance. Thanks to the first approach, related to truncated differentials, we computed a collision for the CubeHash-1/36 hash function, i.e. when for each iteration 36 bytes of message are incorporated and one call to the permutation is applied. Then, the second approach, already used by Dai, much more efficient and simply based on a linearization of the scheme, allowed us to compute a collision for the CubeHash-2/4 hash function. Finally, a theoretical collision attack against CubeHash-2/3, CubeHash-4/4 and CubeHash-4/3 is described. This is currently the best known cryptanalysis result on this SHA-3 candidate.},
}
</bibtex>

<bibtex>
@misc{cubehashBKMP09,
author = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
title = {Attack for CubeHash-2/2 and collision for CubeHash-3/64},
url = {http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{cubehashBKMP09a,
author = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
title = {Real Collisions for CubeHash-4/64},
url = {http://ehash.iaik.tugraz.at/uploads/9/93/Bkmp_ch464.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{cubehashBKMP09a,
author = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
title = {Real Collisions for CubeHash-4/48},
url = {http://ehash.iaik.tugraz.at/uploads/5/50/Bkmp_ch448.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{cubehashBKMP09b,
author = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
title = {Linearization Framework for Collision Attacks: Application to CubeHash and MD6},
howpublished = {Cryptology ePrint Archive, Report 2009/382},
year = {2009},
url = {http://eprint.iacr.org/2009/382.pdf},
note = {\url{http://eprint.iacr.org/}},
abstract = {In this paper, an improved differential cryptanalysis framework for finding collisions in hash functions is provided. Its principle is based on linearization of compression functions in order to find low weight differential characteristics as initiated by Chabaud and Joux. This is formalized and refined however in several ways: for the problem of finding a conforming message pair whose differential trail follows a linear trail, a condition function is introduced so that finding a collision is equivalent to finding a preimage of the zero vector for the condition function. Then, the dependency table concept shows how much influence every input bit of the condition function has on its output bits. Careful analysis of the dependency table reveals degrees of freedom that can be exploited in accelerated preimage reconstruction of the condition function. These concepts are applied to an in-depth collision analysis of reduced-round versions of the two SHA-3 candidates CubeHash and MD6, and are demonstrated to give by far the best currently known collision attacks on these SHA-3 candidates.},
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2009:407,
author = {Benjamin Bloom and Alan Kaminsky},
title = {Single Block Attacks and Statistical Tests on CubeHash},
howpublished = {Cryptology ePrint Archive, Report 2009/407},
year = {2009},
note = {\url{http://eprint.iacr.org/}},
abstract = {This paper describes a second preimage attack on the CubeHash cryptographic one-way hash function. The attack finds a second preimage in less time than brute force search for these CubeHash variants: CubeHash $r$/$b$-224 for $b > 100$; CubeHash$r$/$b$-256 for $b > 96$; CubeHash$r$/$b$-384 for $b > 80$; and CubeHash$r$/$b$-512 for $b > 64$. However, the attack does not break the CubeHash variants recommended for SHA-3. The attack requires minimal memory and can be performed in a massively parallel fashion. This paper also describes several statistical randomness tests on CubeHash. The tests were unable to disprove the hypothesis that CubeHash behaves as a random mapping. These results support CubeHash's viability as a secure cryptographic hash function.},
}
</bibtex>

BLAKE

2009-11-23T14:30:47Z

Fmendel: updated link to round 2 submission

Blue Midnight Wish

2009-11-23T14:30:32Z

Fmendel: added link to round 2 submission

Tiger

2009-09-18T13:10:25Z

Fmendel: Preimage Attacks on Reduced Tiger and SHA-2

== Specification ==

* digest size: 192/160/128 bits
* max. message length: < 264 bits
* compression function: 512-bit message block, 192-bit chaining variable
* Specification: [http://www.cs.technion.ac.il/~biham/Reports/Tiger/ Tiger: A Fast New Cryptographic Hash Function]
<bibtex>
@inproceedings{fseAndersonB96,
author = {Ross J. Anderson and Eli Biham},
title = {TIGER: A Fast New Hash Function},
pages = {89-97},
editor = {Dieter Gollmann},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {1039},
year = {1996},
isbn = {3-540-60865-6},
abstract = {Among those cryptographic hash function which are not based on block ciphers,
MD4 and Snefru seemed initially quite attractive for applications requiring fast
software hashing. However collisions for Snefru were found in 1990, and recently a collision of MD4
was also found. This casts doubt on how long these functions' variants, such as
RIPE-MD, MD5, SHA, SHA1 and Snefru-8, will remain unbroken. Furthermore, all
these functions were designed for 32-bit processors, and cannot be implemented
efficiently on the new generation of 64-bit processors such as the DEC Alpha.
We therefore present a new hash function which we believe to be secure; it is
designed to run quickly on 64-bit processors, without being too slow on existing machines.},
url = {http://dx.doi.org/10.1007/3-540-60865-6}
}
</bibtex>

== Cryptanalysis ==

=== Best Known Results ===

The best known attack is a 1-bit circular pseudo-near-collision for Tiger with a complexity of about 247 of Mendel and Rijmen. The best collision attack on Tiger was presented by Mendel et al. for Tiger reduced to 19 out of 24 rounds. The attack has a complexity of about 262.

----

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

----

=== Collision Attacks ===

<bibtex>
@inproceedings{asiacryptMendelR07,
author = {Florian Mendel and Vincent Rijmen},
title = {Cryptanalysis of the Tiger Hash Function},
booktitle = {ASIACRYPT},
year = {2007},
editor = {Kaoru Kurosawa},
publisher = {Springer},
series = {LNCS},
volume = {4833},
isbn = {978-3-540-76899-9},
pages = {536-550},
url = {http://dx.doi.org/10.1007/978-3-540-76900-2_33},
abstract = {Tiger is a cryptographic hash function with a 192-bit hash value. It was proposed by Anderson and Biham in 1996. Recently, weaknesses have been shown in round-reduced variants of the Tiger hash function. First, at FSE 2006, Kelsey and Lucks presented a collision attack on Tiger reduced to 16 and 17 (out of 24) rounds with a complexity of about $2^44$ and a pseudo-near-collision for Tiger reduced to 20 rounds. Later, Mendel et al. extended this attack to a collision attack on Tiger reduced to 19 rounds with a complexity of about $2^62$. Furthermore, they show a pseudo-near-collision for Tiger reduced to 22 rounds with a complexity of about $2^44$. No attack is known for the full Tiger hash function. In this article, we show a pseudo-near-collision for the full Tiger hash function with a complexity of about $2^47$ hash computations and a pseudo-collision (free-start-collision) for Tiger reduced to 23 rounds with the same complexity.},
}
</bibtex>

<bibtex>
@inproceedings{indocryptMendelPRYW06,
author = {Florian Mendel and Bart Preneel and Vincent Rijmen and Hirotaka Yoshida and Dai Watanabe},
title = {Update on Tiger},
booktitle = {INDOCRYPT},
year = {2006},
pages = {63-79},
url = {http://dx.doi.org/10.1007/11941378_6},
editor = {Rana Barua and Tanja Lange},
publisher = {Springer},
series = {LNCS},
volume = {4329},
isbn = {3-540-49767-6},
abstract = {Tiger is a cryptographic hash function with a 192-bit hash value which was proposed by Anderson and Biham in 1996. At FSE 2006, Kelsey and Lucks presented a collision attack on Tiger reduced to 16 (out of 24) rounds with complexity of about 2^{44}. Furthermore, they showed that a pseudo-near-collision can be found for a variant of Tiger with 20 rounds with complexity of about 2^{48}. In this article, we show how their attack method can be extended to construct a collision in the Tiger hash function reduced to 19 rounds. We present two different attack strategies for constructing collisions in Tiger-19 with complexity of about 2^{62} and 2^{69}. Furthermore, we present a pseudo-near-collision for a variant of Tiger with 22 rounds with complexity of about 2^{44}.},
}
</bibtex>

<bibtex>
@inproceedings{fseKelseyL06,
author = {John Kelsey and Stefan Lucks},
title = {Collisions and Near-Collisions for Reduced-Round Tiger},
pages = {111-125},
url = {http://dx.doi.org/10.1007/11799313_8},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {4047},
year = {2006},
isbn = {3-540-36597-4},
abstract = {We describe a collision-finding attack on 16 rounds of the
Tiger hash function requiring the time for about 244 compression function
invocations. This extends to a collision-finding attack on 17 rounds of the
Tiger hash function in time of about 249 compression function invocations.
Another attack generates circular near-collisions, for 20 rounds of Tiger
with work less than that of 249 compression function invocations. Since Tiger
has only 24 rounds, these attacks may raise some questions about the security
of Tiger. In developing these attacks, we adapt the ideas of message modification
attacks and neutral bits, developed in the analysis of MD4 family hashes,
to a completely different hash function design.},
}
</bibtex>
----

=== Second Preimage Attacks ===

----

=== Preimage Attacks ===

<bibtex>
@INPROCEEDINGS{fseIsobeS09,
author = {Takanori Isobe and Kyoji Shibutani},
title = {Preimage Attacks on Reduced Tiger and SHA-2},
booktitle = {Fast Software Encryption},
year = {2009},
editor = {Dunkelman, Orr},
volume = {5665},
series = {LNCS},
pages = {139-155},
publisher = {Springer},
url = {http://dx.doi.org/10.1007/978-3-642-03317-9}
abstract = {This paper shows new preimage attacks on reduced Tiger and SHA-2.
Indesteege and Preneel presented a preimage attack on Tiger reduced
to 13 rounds (out of 24) with a complexity of 2^{128.5}. Our new
preimage attack finds a one-block preimage of Tiger reduced to 16
rounds with a complexity of 2^{161}. The proposed attack is based
on meet-in-the-middle attacks. It seems difficult to find “independent
words” of Tiger at first glance, since its key schedule function
is much more complicated than that of MD4 or MD5. However, we developed
techniques to find independent words efficiently by controlling its
internal variables. Surprisingly, the similar techniques can be applied
to SHA-2 including both SHA-256 and SHA-512. We present a one-block
preimage attack on SHA-256 and SHA-512 reduced to 24 (out of 64 and
80) steps with a complexity of 2^{240} and 2^{480}, respectively.
To the best of our knowledge, our attack is the best known preimage
attack on reduced-round Tiger and our preimage attack on reduced-step
SHA-512 is the first result. Furthermore, our preimage attacks can
also be extended to second preimage attacks directly, because our
attacks can obtain random preimages from an arbitrary IV and an arbitrary
target.},
}
</bibtex>

<bibtex>
@inproceedings{africacryptMendel09,
author = {Florian Mendel},
title = {Two Passes of Tiger Are Not One-Way},
year = {2009},
pages = {29-40},
url = {http://dx.doi.org/10.1007/978-3-642-02384-2_3},
publisher = {Springer},
series = {LNCS},
booktitle = {AFRICACRYPT},
publisher = {Springer},
volume = {5580},
abstract = {Tiger is a cryptographic hash function proposed by Anderson and Biham in 1996 and produces a 192-bit hash value. Recently, weaknesses have been shown in round-reduced variants of the Tiger hash function. Collision attacks have been presented for Tiger reduced to 16 and 19 (out of 24) rounds at FSE 2006 and Indocrypt 2006. Furthermore, Mendel and Rijmen presented a 1-bit pseudo-near-collision for the full Tiger hash function at ASIACRYPT 2007. The attack has a complexity of about 2^47 compression function evaluations. While there exist several collision-style attacks for Tiger, the picture is different for preimage attacks. At WEWoRC 2007, Indesteege and Preneel presented a preimage attack on Tiger reduced to 12 and 13 rounds with a complexity of 2^64.5 and 2^128.5, respectively.
In this article, we show a preimage attack on Tiger with two passes (16 rounds) with a complexity of about 2^174 compression function evaluations. Furthermore, we show how the attack can be extended to 17 rounds with a complexity of about 2^185. Even though the attacks are only slightly faster than brute force search, they present a step forward in the cryptanalysis of Tiger.
}
</bibtex>

<bibtex>
@inproceedings{DBLP:conf/weworc/IndesteegeP07,
author = {Sebastiaan Indesteege and
Bart Preneel},
title = {Preimages for Reduced-Round Tiger},
year = {2007},
pages = {90-99},
url = {http://dx.doi.org/10.1007/978-3-540-88353-1_8},
editor = {Stefan Lucks and
Ahmad-Reza Sadeghi and
Christopher Wolf},
booktitle = {WEWoRC},
publisher = {Springer},
series = {LNCS},
volume = {4945},
abstract = {The cryptanalysis of the cryptographic hash function Tiger has, until now, focussed on finding collisions. In this paper we describe a preimage attack on the compression function of Tiger-12, i.e., Tiger reduced to 12 rounds out of 24, with a complexity of 2^63.5 compression function evaluations. We show how this can be used to construct second preimages with complexity 2^63.5 and first preimages with complexity 2^64.5 for Tiger-12. These attacks can also be extended to Tiger-13 at the expense of an additional factor of 2^64 in complexity. },
}

</bibtex>

----

=== Others ===

SHAvite-3

2009-09-17T10:26:05Z

Fmendel: added link to website

LANE

2009-09-15T06:17:48Z

Fmendel:

== The algorithm ==

* Author(s): Sebastiaan Indesteege, Elena Andreeva, Christophe De Cannière, Orr Dunkelman, Emilia Käsper, Svetla Nikova, Bart Preneel, Elmar Tischhauser
* Website: [http://www.cosic.esat.kuleuven.be/lane/ http://www.cosic.esat.kuleuven.be/lane/]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/LANE.zip LANE.zip]

<bibtex>
@misc{sha3IP08,
author = {Sebastiaan Indesteege},
title = {The LANE hash function},
url = {http://www.cosic.esat.kuleuven.be/publications/article-1181.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

{| 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
|-
| collision || hash || 384,512 || 3 P-rounds || 294 || 2133 || [http://sac.ucalgary.ca/sites/sac.math.ucalgary.ca/files/u5/09_swu.pdf Wu,Feng,Wu]
|-
| semi-free-start collision || compression || 224,256 || 3 P-rounds || 262 || 269 || [http://sac.ucalgary.ca/sites/sac.math.ucalgary.ca/files/u5/09_swu.pdf Wu,Feng,Wu]
|-
| semi-free-start collision || compression || 384,512 || 3 P-rounds || 262 || 269 || [http://sac.ucalgary.ca/sites/sac.math.ucalgary.ca/files/u5/09_swu.pdf Wu,Feng,Wu]
|-
| semi-free-start collision || compression || 224,256 || 6 P-rounds || 296 || 288 || [http://eprint.iacr.org/2009/443.pdf Matusiewicz,Naya-Plasencia,Nikolic,Sasaki,Schläffer]
|-
| semi-free-start collision || compression || 512 || 8 P-rounds || 2224 || 2128 || [http://eprint.iacr.org/2009/443.pdf Matusiewicz,Naya-Plasencia,Nikolic,Sasaki,Schläffer]
|-
|}

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

<bibtex>
@misc{laneWFW09,
author = {Shuang Wu and Dengguo Feng and Wenling Wu},
title = {Cryptanalysis of the LANE Hash Function},
url = {http://sac.ucalgary.ca/sites/sac.math.ucalgary.ca/files/u5/09_swu.pdf},
howpublished = {Presentation, SAC},
year = {2009},
abstract = {The LANE hash function is designed by Sebastiaan Indesteege and Bart Preneel. It is now a first round candidate of NIST's SHA-3 competition. The LANE hash function contains four concrete designs with different digest length of 224, 256, 384 and 512.
The LANE hash function uses two permutations P and Q, which consist of different number of AES-like rounds. LANE-224/256 uses 6-round P and 3-round Q. LANE-384/512 uses 8-round P and 4-round Q. We will use LANE-n-(a,b) to denote a variant of LANE with a-round P, b-round Q and a digest length n.
We have found a semi-free start collision attack on reduced-round LANE-256-(3,3) with complexity of 2^62 compression function evaluations and 2^69 memory. This technique can be applied to LANE-512-(3,4) to get a semi-free start collision attack with the same complexity of 2^62 and 2^69 memory. We also propose a collision attack on LANE-512-(3,4) with complexity of 2^94 and 2^133 memory.},
}
</bibtex>

<bibtex>
@misc{laneMNNSS09,
author = {Krystian Matusiewicz and Maria Naya-Plasencia and Ivica Nikolic and Yu Sasaki and Martin Schläffer},
title = {Rebound Attack on the Full LANE Compression Function},
url = {http://eprint.iacr.org/2009/443.pdf},
howpublished = {Cryptology ePrint Archive, Report 2009/443},
year = {2009},
abstract = {In this work, we apply the rebound attack to the AES based SHA-3 candidate LANE. The hash function LANE uses a permutation based compression function, consisting of a linear message expansion and 6 parallel lanes. In the rebound attack on LANE, we apply several new techniques to construct a collision for the full compression function of LANE-256 and LANE-512. Using a relatively sparse truncated differential path, we are able to solve for a valid message expansion and colliding lanes independently. Additionally, we are able to apply the inbound phase more than once by exploiting the degrees of freedom in the parallel AES states. This allows us to construct semi-free-start collisions for full LANE-256 with $2^{96}$ compression function evaluations and $2^{88}$ memory, and for full LANE-512 with $2^{224}$ compression function evaluations and $2^{128}$ memory.},
}
</bibtex>

ESSENCE

2009-09-11T07:45:19Z

Fmendel: fixed bibtex entry

== The algorithm ==

* Authors: Jason Worth Martin
* Website: [http://www.math.jmu.edu/~martin/essence/ http://www.math.jmu.edu/~martin/essence/]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/ESSENCE.zip ESSENCE.zip]

<bibtex>
@misc{sha3Martin08,
author = {Jason Worth Martin},
title = {ESSENCE: A Candidate Hashing Algorithm for the NIST Competition},
url = {http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_NIST.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

<bibtex>
@misc{sha3Martin08a,
author = {Jason Worth Martin},
title = {ESSENCE: A Family of Cryptographic Hashing Algorithms},
url = {http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_compression.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

<bibtex>
@misc{sha3Martin08b,
author = {Jason Worth Martin},
title = {ESSENCE: Errata},
url = {http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_errata.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

{| 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
|-
| observation || compression function || all || || - || - || [http://www.mat.dtu.dk/people/S.Thomsen/essence/Essence-obs.pdf Mouha,Thomsen,Turan]
|-
| observation || compression function || all || || - || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
|-
| key recovery || block cipher || 256 || 14 rounds || 2225 || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
|-
| key recovery || block cipher || 512 || 14 rounds || 2450 || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
|-
| pseudo-collision || hash || 512 || 31 rounds || 2254.6 || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
|-
| style="background:orange" | collision || hash || 224/256 || || 267.4 || - || [http://www.131002.net/data/papers/NRALLMP09.pdf Naya-Plasencia et al.]
|-
| style="background:orange" | collision || hash || 384/512 || || 2134.7 || - || [http://www.131002.net/data/papers/NRALLMP09.pdf Naya-Plasencia et al.]
|-
|}

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

<bibtex>
@misc{essenceMTT09,
author = {Nicky Mouha and Søren S. Thomsen and Meltem Sönmez Turan},
title = {Observations of non-randomness in the ESSENCE compression function},
url = {http://www.mat.dtu.dk/people/S.Thomsen/essence/Essence-obs.pdf},
howpublished = {Available online},
year = {2009},
abstract= {ESSENCE is a candidate for the SHA-3 hash function competition initiated by NIST. In this note we describe some non-random behaviour in the ESSENCE compression function, including an input leading to the all-zero output. The results do not seem directly extensible to the full hash function, and hence they do not seem to break any security claims of ESSENCE.},
}
</bibtex>

<bibtex>
@misc{essenceMSAPTMP09,
author = {Nicky Mouha and Gautham Sekar and Jean-Philippe Aumasson and Thomas Peyrin and Søren S. Thomsen and Meltem Sönmez Turan and Bart Preneel},
title = {Cryptanalysis of the ESSENCE Family of Hash Functions},
url = {http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf},
howpublished = {Available online},
year = {2009},
abstract = {ESSENCE is a family of cryptographic hash functions, accepted to the first round of NIST’s SHA-3 competition. This paper presents the first known attacks on ESSENCE. We present a pseudo-collision attack on 31 out of 32 rounds of ESSENCE-512, invalidating the design claim that at least 24 rounds of ESSENCE are secure against differential cryptanalysis. We develop a novel technique to satisfy the first nine rounds of the differential characteristic. Non-randomness in the outputs of the feedback function F is used to construct several distinguishers on a 14-round ESSENCE block cipher and the corresponding compression function, each requiring only 2^17 output bits. This observation is extended to key-recovery attacks on the block ciphers. Next, we show that the omission of round constants allows slid pairs and fixed points to be found. These attacks are independent of the number of rounds. Finally, we suggest several countermeasures against these attacks, while still keeping the design simple and easy to analyze.},
}
</bibtex>

<bibtex>
@misc{essenceNRALLMP09,
author = {María Naya-Plasencia and Andrea Röck and Jean-Philippe Aumasson and Yann Laigle-Chapuy and Gaëtan Leurent and Willi Meier and Thomas Peyrin},
title = {Cryptanalysis of ESSENCE},
howpublished = {Cryptology ePrint Archive, Report 2009/302},
year = {2009},
url = {http://eprint.iacr.org/2009/302.pdf},
note = {\url{http://eprint.iacr.org/}},
abstract = {ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly parallelizable design, and that has thus far remained unbroken. Preliminary analysis in its documentation argues that it resists standard differential cryptanalysis. This paper disproves this claim, showing that advanced techniques can be used to significantly reduce the cost of such attacks: using a manually found differential path and a nontrivial search algorithm, we obtain shortcut collision attacks on the full ESSENCE-256 and ESSENCE-512, with respective complexities $2^{67.4}$ and $2^{134.7}$. As an aside, we show how to use these attacks for forging valid message/MAC pairs for HMAC-ESSENCE-256 and HMAC-ESSENCE-512, essentially at the same cost as a collision.},
}

ESSENCE

2009-09-11T07:41:04Z

Fmendel: fixed bibtex entry

== The algorithm ==

* Authors: Jason Worth Martin
* Website: [http://www.math.jmu.edu/~martin/essence/ http://www.math.jmu.edu/~martin/essence/]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/ESSENCE.zip ESSENCE.zip]

<bibtex>
@misc{sha3Martin08,
author = {Jason Worth Martin},
title = {ESSENCE: A Candidate Hashing Algorithm for the NIST Competition},
url = {http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_NIST.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

<bibtex>
@misc{sha3Martin08a,
author = {Jason Worth Martin},
title = {ESSENCE: A Family of Cryptographic Hashing Algorithms},
url = {http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_compression.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

<bibtex>
@misc{sha3Martin08b,
author = {Jason Worth Martin},
title = {ESSENCE: Errata},
url = {http://www.math.jmu.edu/~martin/essence/Supporting_Documentation/essence_errata.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

{| 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
|-
| observation || compression function || all || || - || - || [http://www.mat.dtu.dk/people/S.Thomsen/essence/Essence-obs.pdf Mouha,Thomsen,Turan]
|-
| observation || compression function || all || || - || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
|-
| key recovery || block cipher || 256 || 14 rounds || 2225 || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
|-
| key recovery || block cipher || 512 || 14 rounds || 2450 || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
|-
| pseudo-collision || hash || 512 || 31 rounds || 2254.6 || - || [http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf Mouha et al.]
|-
| style="background:orange" | collision || hash || 224/256 || || 267.4 || - || [http://www.131002.net/data/papers/NRALLMP09.pdf Naya-Plasencia et al.]
|-
| style="background:orange" | collision || hash || 384/512 || || 2134.7 || - || [http://www.131002.net/data/papers/NRALLMP09.pdf Naya-Plasencia et al.]
|-
|}

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

<bibtex>
@misc{essenceMTT09,
author = {Nicky Mouha and Søren S. Thomsen and Meltem Sönmez Turan},
title = {Observations of non-randomness in the ESSENCE compression function},
url = {http://www.mat.dtu.dk/people/S.Thomsen/essence/Essence-obs.pdf},
howpublished = {Available online},
year = {2009}
}
</bibtex>

<bibtex>
@misc{essenceMSAPTMP09,
author = {Nicky Mouha and Gautham Sekar and Jean-Philippe Aumasson and Thomas Peyrin and Søren S. Thomsen and Meltem Sönmez Turan and Bart Preneel},
title = {Cryptanalysis of the ESSENCE Family of Hash Functions},
url = {http://www.nickymouha.be/papers/Essence-MouhaSekar.pdf},
howpublished = {Available online},
year = {2009}
}
</bibtex>

<bibtex>
@misc{essenceNRALLMP09,
author = {María Naya-Plasencia and Andrea Röck and Jean-Philippe Aumasson and Yann Laigle-Chapuy and Gaëtan Leurent and Willi Meier and Thomas Peyrin},
title = {Cryptanalysis of ESSENCE},
howpublished = {Cryptology ePrint Archive, Report 2009/302},
year = {2009},
url = {http://eprint.iacr.org/2009/302.pdf}
note = {\url{http://eprint.iacr.org/}},
abstract = {ESSENCE is a hash function submitted to the NIST Hash Competition that stands out as a hardware-friendly and highly parallelizable design, and that has thus far remained unbroken. Preliminary analysis in its documentation argues that it resists standard differential cryptanalysis. This paper disproves this claim, showing that advanced techniques can be used to significantly reduce the cost of such attacks: using a manually found differential path and a nontrivial search algorithm, we obtain shortcut collision attacks on the full ESSENCE-256 and ESSENCE-512, with respective complexities $2^{67.4}$ and $2^{134.7}$. As an aside, we show how to use these attacks for forging valid message/MAC pairs for HMAC-ESSENCE-256 and HMAC-ESSENCE-512, essentially at the same cost as a collision.},
}

Edon-R (SHA-3 submission)

2009-08-06T07:35:20Z

Fmendel: Detectable correlations in Edon-R

== The algorithm ==

* Author(s): Danilo Gligoroski, Rune Steinsmo Ødegård, Marija Mihova, Svein Johan Knapskog, Ljupco Kocarev, Aleš Drápal, Vlastimil Klima
* Website: [http://www.item.ntnu.no/people/personalpages/fac/danilog/edon-r http://www.item.ntnu.no/people/personalpages/fac/danilog/edon-r]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/EDON-R.zip EDON-R.zip]

<bibtex>
@misc{sha3G+08,
author = {Danilo Gligoroski and Rune Steinsmo Ødegård and Marija Mihova and Svein Johan Knapskog and Ljupco Kocarev and Aleš Drápal and Vlastimil Klima},
title = {Cryptographic Hash Function EDON-R},
url = {http://people.item.ntnu.no/~danilog/Hash/Edon-R/Supporting_Documentation/EdonRDocumentation.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

{| 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
|-
| style="background:yellow" | preimage(1) || hash || || || 22n/3 || 22n/3 || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
|-
| multi-collision (2K) || hash || 256,512 || || K*2n/2 || 2n/2 || [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf Klima]
|-
| multi-preimage || hash || 256,512 || || ? || ? || [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf Klima]
|-
| collision || compression || || || - || - || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
|-
| 2nd preimage || compression || || || - || - || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
|-
| preimage || compression || || || - || - || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
|-
| key recovery || secret-prefix MAC|| || || 25n/8 || - || [http://eprint.iacr.org/2009/135.pdf Leurent]
|-
| correlation analysis || hash || all || || - || - || [http://eprint.iacr.org/2009/378.pdf Novotney, Ferguson]
|-
|}

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

(1) [http://eprint.iacr.org/2009/120.pdf Gligoroski,Ødegård] dispute the validity of the model in which the attack of Khovratovich et. al is compared to generic attacks.

<bibtex>
@misc{edonKNW08,
author = {Dmitry Khovratovich and Ivica Nikolić and Ralf-Philipp Weinmann},
title = {Cryptanalysis of Edon-R},
url = {http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf},
howpublished = {Available online},
year = {2008},
abstract = {We present various types of attacks on the hash family Edon-R. In a free start attack scenario, with the initial chaining value not xored, all three main attacks (collisions, second preimage, and preimage) can be launched on Edon-R with negligible effort. In these attacks we exploit the asymmetrical diffusion of the chaining values in the compression function. Also, by partially inverting the compression function and xoring one part of the chaining value, we launch a meet-in-the-middle attack on Edon-R-n to find real preimages. The attack requires $2^{2n/3}$ effort and the same amount of memory. The attacks are applicable to all digest sizes.},
}
</bibtex>

<bibtex>
@misc{edonK08,
author = {Vlastimil Klima},
title = {Multicollisions of EDON-R hash function and other observations},
url = {http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf},
howpublished = {Available online},
year = {2008},
abstract = {The main principle how to make n-bit EDON-R hash functions [1] resistant to generic multicollisions and multipreimages attacks ([2], [3]) is the 2n-bit width of internal chaining value. We show how to degenerate 2n-bit chaining value to n-bit chaining value (for n = 256, 512) by keeping the half of chaining value constant from the beginning. It circumvents the main principle and make EDON-R hash functions (for n = 256, 512) vulnerable to generic multicollisions and multipreimages attacks ([2], [3]) with small additional work factor. We show several properties of EDON-R compression function, which could be interesting for the next study of collisions and preimages. The first cryptanalysis of EDON-R was made in [4]. We present an independent research, partially overlaping with [4]. We want to note that this is preliminary version, that we present here only sketches of the proofs and that not all of the accompanied problems are completely solved.},
}
</bibtex>

<bibtex>
@misc{edonGO09,
author = {Danilo Gligoroski and Rune Steinsmo Ødegård},
title = {On the Complexity of Khovratovich et. al's Preimage Attack on EDON-R},
url = {http://eprint.iacr.org/2009/120.pdf},
howpublished = {Available online},
year = {2009},
abstract = {Based on the analysis made by van Oorschot and Wiener for the complexity of parallel memoryless collision search [5], we show that the memoryless meet-in-the-middle attack which is one part of the whole preimage attack of Khovratovich et. al. [3] on EDON-R hash function has complexity bigger than $2^n$.},
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2009:135,
author = {Gaëtan Leurent},
title = {Key Recovery Attack against Secret-prefix Edon-R},
howpublished = {Cryptology ePrint Archive, Report 2009/135},
year = {2009},
url = {http://eprint.iacr.org/2009/135.pdf},
abstract = {Edon-R is a SHA-3 candidate. In this paper we show that using Edon-R as a MAC with the secret prefix construction is unsafe. Our attack requires 2 queries, $2^{5n/8}$ computations, and negligible memory.},
}
</bibtex>

<bibtex>
@misc{cryptoeprint:2009:378,
author = {Peter Novotney and Niels Ferguson},
title = {Detectable correlations in Edon-R},
howpublished = {Cryptology ePrint Archive, Report 2009/378},
year = {2009},
url={http://eprint.iacr.org/2009/378.pdf},
note = {\url{http://eprint.iacr.org/}},
abstract = {The Edon-R compression function has a large set of useful differentials that produce easily detectable output bit biases. We show how to construct such differentials, and use them to create a distinguisher for Edon-R-512 that requires around $2^{54}$ compression function evaluations (or $2^{28}$ evaluations after a pre-computation of $2^{66}$ evaluations). The differentials can also be used to attack a variety of MAC and KDF constructions when they use Edon-R-512.},
}
</bibtex>

Skein

2009-07-30T07:24:56Z

Fmendel: added link to SkeinUpdate.zip