The ECRYPT Hash Function Website - User contributions [en]

Skein

2012-10-02T10:26:15Z

Crechberger: Added results of four recent cryptanalysis papers

== 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-256 and 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
|-
| collision || 256 || 2 rounds || 285 || - || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
|-
| collision || 256 || 12 rounds || 2126.5 || - || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
|-
| collision || 512 || 5 rounds || 2192 || - || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
|-
| collision || 512 || 14 rounds || 2254.5 || - || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
|-
| preimage || 512 || 22 rounds || 2511.0 || 26 || [http://eprint.iacr.org/2011/286.pdf Khovratovich,Rechberger,Savelieva]
|-
| preimage || 512 || 72 rounds || 2511.76 || - || [http://eprint.iacr.org/2011/286.pdf Khovratovich,Rechberger,Savelieva]
|-
|}

=== 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
|-
| preimage || compression function || 512 || 22 rounds || 2508 || 26 || [http://eprint.iacr.org/2011/286.pdf Khovratovich,Rechberger,Savelieva]
|-
| preimage || compression function || 512 || 37 rounds || 2511.2 || 264 || [http://eprint.iacr.org/2011/286.pdf Khovratovich,Rechberger,Savelieva]
|-
| distinguisher || compression function || 512 || 32 rounds || 2104.5 || - || [http://eprint.iacr.org/2012/238.pdf Yu,Chen,Wang]
|-
| distinguisher || compression function || 512 || 36 rounds || 2454 || - || [http://eprint.iacr.org/2012/238.pdf Yu,Chen,Wang]
|-
| key recovery || block cipher || 512 || 32 rounds || 2181 || - || [http://eprint.iacr.org/2012/238.pdf Yu,Chen,Wang]
|-
| key recovery || block cipher || 512 || 34 rounds || 2424 || - || [http://eprint.iacr.org/2012/238.pdf Yu,Chen,Wang]
|-
| near-collision || compression function || 256 || 32 rounds || 2105 || - || [http://eprint.iacr.org/2011/148.pdf Yu,Chen,Jia,Wang]
|-
| 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{skeinK12,
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{skeinKRS12,
author = {Dmitry Khovratovich and Christian Rechberger and Alexandra Savelieva},
title = {Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family},
booktitle = {Fast Software Encryption (FSE)},
year = {2012},
publisher = {Springer},
series = {LNCS},
url = {http://eprint.iacr.org/2011/286.pdf},
abstract = {We present the new concept of biclique as a tool for preimage attacks, which
employs many powerful techniques from differential cryptanalysis of block ciphers and hash
functions.
The new tool has proved to be widely applicable by inspiring many authors to publish new re-
sults of the full versions of AES, KASUMI, IDEA, and Square. In this paper, we demonstrate
how our concept results in the first cryptanalysis of the Skein hash function, and describe an
attack on the SHA-2 hash function with more rounds than before.}
}
</bibtex>
<bibtex>
@misc{skeinY+12,
author = {Hongbo Yu and Jiazhe Chen and Xiaoyun Wang},
title = {The Boomerang Attacks on the Round-Reduced Skein-512},
howpublished = {Cryptology ePrint Archive, Report 2012/238},
year = {2012},
url = {http://eprint.iacr.org/2012/238.pdf},
abstract = {The hash function Skein is one of the five finalists of the NIST SHA-3 competition;it is based on the block cipher Threefish which only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). This paper studies the boomerang attacks on Skein-512. Boomerang distinguishers on the compression function reduced to 32 and 36 rounds are proposed, with complexities 2^{104.5} and 2^{454} respectively. Examples of the distinguishers on 28-round and 31-round are also given. In addition, the boomerang distinguishers are applicable to the key-recovery attacks on reduced Threefish-512. The complexities for key-recovery attacks reduced to 32-/33-/34-round are about 2^{181}, 2^{305} and 2^{424}. Because Laurent et al. [14] pointed out that the previous boomerang distinguishers for Threefish-512 are in fact not compatible, our attacks are the first valid boomerang attacks for the final round Skein-512. }
}
</bibtex>
<bibtex>
@misc{skeinY+12,
author = {Hongbo Yu and Jiazhe Chen and Ketingjia and Xiaoyun Wang},
title = {Near-Collision Attack on the Step-Reduced Compression Function of Skein-256},
howpublished = {Cryptology ePrint Archive, Report 2011/148},
year = {2011},
url = {http://eprint.iacr.org/2011/148.pdf},
abstract = {The Hash function Skein is one of the 5 finalists of NIST SHA-3 competition. It is designed based on the threefish block cipher and it only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). In this paper, we combine two short differential paths to a long differential path using the modular differential technique. And we present the semi-free start near-collision attack up to the 32-step Skein-256 with the Hamming difference 51. The complexity of our attack is about $2^{105}$. }
}
</bibtex>
<bibtex>
@inproceedings{skeinKNR10,
author = {Dmitry Khovratovich and Ivica Nikolić and Christian Rechberger},
title = {Rotational Rebound Attacks on Reduced Skein},
booktitle = {ASIACRYPT},
year = {2010},
pages = {1-19},
publisher = {Springer},
series = {LNCS},
volume = {6477},
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>
@inproceedings{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},
booktitle = {CANS},
year = {2010},
pages = {124-139},
publisher = {Springer},
series = {LNCS},
volume = {6467},
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},
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},
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>
@inproceedings{cryptoeprint:2009:526,
author = {Dmitry Khovratovich and Ivica Nikolic},
title = {Rotational Cryptanalysis of ARX},
pages = {333-346},
booktitle = {FSE},
publisher = {Springer},
series = {LNCS},
volume = {6147},
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},
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>
@inproceedings{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},
booktitle = {ASIACRYPT},
year = {2009},
pages = {542-559},
publisher = {Springer},
series = {LNCS},
volume = {5912},
url = {http://eprint.iacr.org/2009/438.pdf},
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>

SHA-3 related events

2011-11-03T19:41:09Z

Crechberger: added ISI Kolkata workshop

On this page, we list events like conferences, workshops, panel discussions, etc. that are especially interesting in the context of the SHA-3 competition.

Upcoming:

[http://www.isical.ac.in/~coec/workshop/hash2011.html Hash Workshop on SHA3 Finalists] December 9-10, 2011, Kolkata.

[http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/March2012/index.html Third SHA-3 Candidate Conference] March 22-23, 2012, Washington D.C.

Archive:

[http://www.ecrypt.eu.org/stvl/hfw/ ECRYPT Conference on Hashfunctions 2005]

[http://csrc.nist.gov/groups/ST/hash/first_workshop.html NIST Cryptographic Hash Workshop 2005]

[http://csrc.nist.gov/groups/ST/hash/second_workshop.html NIST Cryptographic Hash Workshop 2006]

[http://events.iaik.tugraz.at/HashWorkshop07/ ECRYPT Hash Workshop 2007]

[http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/Feb2009/index.html First SHA-3 Candidate Conference]

[https://www.cosic.esat.kuleuven.be/ecrypt/courses/tenerife09/program.shtml Hash³: Proofs, Analysis, and Implementation]

[http://www.iwsec.org/2009/program.html#pd Cryptographic hash functions: SHA-3 and beyond]

[http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/index.html Second SHA-3 Candidate Conference]

[http://www.ecrypt.eu.org/hash2011/ ECRYPT2 Hash Workshop 2011] May 19-20, 2011, Tallinn, Estonia

[http://cryptography.gmu.edu/quovadis/ Quo Vadis Cryptology 2011] May 23-24, 2011, Warsaw, Poland

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

SHA-3 related events

2011-05-08T05:26:42Z

Crechberger: added Quo Vadis Cryptology

On this page, we list events like conferences, workshops, panel discussions, etc. that are especially interesting in the context of the SHA-3 competition.

Upcoming:

[http://www.ecrypt.eu.org/hash2011/ ECRYPT2 Hash Workshop 2011] May 19-20, 2011, Tallinn, Estonia

[http://cryptography.gmu.edu/quovadis/ Quo Vadis Cryptology 2011] May 23-24, 2011, Warsaw, Poland

[http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/March2012/index.html Third SHA-3 Candidate Conference] March 22-23, 2012, Washington D.C.

Archive:

[http://www.ecrypt.eu.org/stvl/hfw/ ECRYPT Conference on Hashfunctions 2005]

[http://csrc.nist.gov/groups/ST/hash/first_workshop.html NIST Cryptographic Hash Workshop 2005]

[http://csrc.nist.gov/groups/ST/hash/second_workshop.html NIST Cryptographic Hash Workshop 2006]

[http://events.iaik.tugraz.at/HashWorkshop07/ ECRYPT Hash Workshop 2007]

[http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/Feb2009/index.html First SHA-3 Candidate Conference]

[https://www.cosic.esat.kuleuven.be/ecrypt/courses/tenerife09/program.shtml Hash³: Proofs, Analysis, and Implementation]

[http://www.iwsec.org/2009/program.html#pd Cryptographic hash functions: SHA-3 and beyond]

[http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/index.html Second SHA-3 Candidate Conference]

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

The SHA-3 Zoo

2011-04-27T18:21:04Z

Crechberger: added events page

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], 14 submissions have made it into [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/index.html round 2] and 5 candidates have been selected for the [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/index.html final].

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

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

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

new:[[SHA-3 related events]]

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

Call for contribution:
A subgroup of STVL in ECRYPT2 started working on an Ecrypt report on the status of the SHA-3 finalists. The report will contain a survey of the results published on the finalists. If you recently obtained new results, which are not public yet and you want to see them included in the report, please contact vincent.rijmen@iaik.tugraz.at .

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

SHA-3 related events

2011-04-27T18:20:31Z

Crechberger: Start of events page

On this page, we list events like conferences, workshops, panel discussions, etc. that are especially interesting in the context of the SHA-3 competition.

Upcoming:

[http://www.ecrypt.eu.org/hash2011/ ECRYPT2 Hash Workshop 2011] May 19-20, 2011, Tallinn, Estonia

[http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/March2012/index.html Third SHA-3 Candidate Conference] March 22-23, 2012, Washington D.C.

Archive:

[http://www.ecrypt.eu.org/stvl/hfw/ ECRYPT Conference on Hashfunctions 2005]

[http://csrc.nist.gov/groups/ST/hash/first_workshop.html NIST Cryptographic Hash Workshop 2005]

[http://csrc.nist.gov/groups/ST/hash/second_workshop.html NIST Cryptographic Hash Workshop 2006]

[http://events.iaik.tugraz.at/HashWorkshop07/ ECRYPT Hash Workshop 2007]

[http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/Feb2009/index.html First SHA-3 Candidate Conference]

[https://www.cosic.esat.kuleuven.be/ecrypt/courses/tenerife09/program.shtml Hash³: Proofs, Analysis, and Implementation]

[http://www.iwsec.org/2009/program.html#pd Cryptographic hash functions: SHA-3 and beyond]

[http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/index.html Second SHA-3 Candidate Conference]

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

User:Crechberger

2011-04-27T18:20:22Z

Crechberger:

[http://groestl.info/rechberger Christian Rechberger]

Shabal

2010-07-27T00:58:34Z

Crechberger: added Novotney distinguisher

== The algorithm ==

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

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

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

== Cryptanalysis ==

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

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

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

=== 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
|-
| | non-randomness(1) || permutation || all || || 212 || || [http://131002.net/data/papers/Aum09.pdf Aumasson]
|-
| | non-randomness(1) || permutation || all || || 1 || || [http://www.mat.dtu.dk/people/S.Thomsen/shabal/shabal.pdf Knudsen,Matusiewicz,Thomsen]
|-
| | non-randomness(1) || permutation || all || || 2 || || [http://131002.net/data/papers/AMM09.pdf Aumasson,Mashatan,Meier]
|-
| | non-randomness || permutation || all || || 2159 || || [http://gva.noekeon.org/papers/ShabalRotation.pdf Van Assche]
|-
| | non-randomness || permutation || all || || 221 || || [http://eprint.iacr.org/2010/398.pdf Novotney]
|-
|}
(1)The Shabal team commented on these analyses and provide an update of their security proofs in [http://eprint.iacr.org/2009/199.pdf this note].

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

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

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

<bibtex>
@misc{shabalVA10,
author = {Gilles Van Assche},
title = {A rotational distinguisher on Shabal's keyed permutation and its impact on the security proofs},
url = {http://gva.noekeon.org/papers/ShabalRotation.pdf},
howpublished = {Available online},
year = {2010},
abstract = {In this short note, we apply a rotational distinguisher to the keyed permutation of the SHA-3 candidate Shabal. We then discuss its applicability in the scope of Shabal's mode of operation and its impact on the security proofs.},
}
</bibtex>

<bibtex>
@misc{shabalNov10,
author = {Peter Novotney},
title = {Distinguisher for Shabal's Permutation Function},
howpublished = {Cryptology ePrint Archive, Report 2010/398},
year = {2010},
note = {\url{http://eprint.iacr.org/}},
abstract = {In this note we consider the Shabal permutation function $\mathcal{P}$ as a block cipher with input $A_p$,$B_p$ and key $C$,$M$ and describe a distinguisher with a data complexity of $2^{23}$ random inputs with a given difference. If the attacker can control one chosen bit of $B_p$, only $2^{21}$ inputs with a given difference are required on average. This distinguisher does not appear to lead directly to an attack on the full Shabal construction. },
}
</bibtex>

Fugue

2010-06-21T11:10:20Z

Crechberger: Added Aumasson/Phan distinguisher of output transformation

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

File:Fugue designers reply to AumassonPhan Distinguisher.txt

2010-06-21T11:05:06Z

Crechberger:

File:Fig7.pdf

2010-06-21T11:04:10Z

Crechberger:

File:Fugue path.pdf

2010-06-21T10:56:48Z

Crechberger:

Fugue

2010-04-12T15:52:51Z

Crechberger: added SAC2009 paper

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

=== Hash function ===

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

Recommended security parameters: (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)

{| 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
|-
| internal collision || 256 || (2,5,13) || 2352 || 2352 || [http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf Khovratovich]
|-
| internal collision || 512 || (4,8,13) || 2480 || 2480 || [http://cryptolux.org/mediawiki/uploads/9/99/Struct2.pdf Khovratovich]
|-
|}

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

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

Hamsi

2010-02-15T19:04:41Z

Crechberger: New result on Hamsi: Message Recovery and Pseudo-Preimage Attacks on the Compression Function of Hamsi-256

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

ECHO

2010-02-15T16:15:47Z

Crechberger:

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

=== Hash function ===

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

Recommended security parameters: '''8''' rounds (n=224,256); '''10''' 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).

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

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

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

Skein

2010-02-15T16:01:44Z

Crechberger: added rotational attack on reduced threefish

BLAKE

2010-01-28T14:40:58Z

Crechberger: split tables template

== 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 the building blocks.
A description of these 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.
{| 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/10 rounds || 2n-15 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| preimage || 384 || 2.5/10 rounds || 2355 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| preimage || 512 || 2.5/10 rounds || 2481 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
|}

=== Underlying building blocks ===
Here we list results that 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/10 rounds || 2n/2-16 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| free-start collision || hash || 384,512 || 2.5/10 rounds || 2n/2-32 || - || [http://eprint.iacr.org/2009/238.pdf Ji,Liangyu]
|-
| near-collision || compression function || 256 || 4/10 rounds (nb. 6-9) || 242 || - || [http://www.jguo.org/docs/blake-col.pdf Guo,Matusiewicz]
|-
|}

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

The Hash Function Zoo

2009-07-30T12:53:49Z

Crechberger: Update on Vortex

{| border="1" cellpadding="2" cellspacing="0" align="center" class="wikitable"
|+'''The Hash Function Zoo, a collection of cryptographic hash functions (in alphabetical order)'''

 
Also check out Paulo Barreto's [http://paginas.terra.com.br/informatica/paulobarreto/hflounge.html Hash Function Lounge].
 
For the recent submissions to the SHA-3 competition, there is a separate [[The_SHA-3_Zoo| SHA-3 Zoo]]

|- style="background:#efefef;"
! width="150"| Hash Function Name !! Designer(s) !! Issued in !! Status Cryptanalysis
|-
| [[AR]] || ISO || align="center"|1992 || broken
|-
| [[Boognish]] || Daemen || align="center"|1992 || broken
|-
| [[Cellhash]] || Daemen, Govaerts, Vandewalle || align="center"|1991 || ?
|-
| [[DASH]] || Billet, Robshaw, Seurin, Yin || align="center"|2008 || ?
|-
| [[DHA-256]] || Lee, Chang, Kim, Lee, Hong || align="center"|2006 || ?
|-
| [[Edon-R]] || Gligoroski, Markovski, Kocarev || align="center"|2006 || ?
|-
| [[FFT-Hash I]] || Schnorr || align="center"|1991 || broken
|-
| [[FFT-Hash II]] || Schnorr || align="center"|1992 || broken
|-
| [[FORK-256]] || Hong, Chang, Sung, Lee, Hong, Lee, Moon, Chee || align="center"|2006 || broken
|-
| [[FSB]] || Augot, Finiasz, Sendrier || align="center"|2005 || ?
|-
| [[GOST | GOST 34.11-94]] || Government Committee of Russia for Standards || align="center"|1990 || broken
|-
| [[Grindahl-256]] || Knudsen, Rechberger, Thomsen || align="center"|2007 || broken
|-
| [[Grindahl-512]] || Knudsen, Rechberger, Thomsen || align="center"|2007 || ?
|-
| [[HAS-160]] || Telecommunications Technology Association of Korea || align="center"| 2000 || ?
|-
| [[HAS-V]] || Park, Hwang, Lee || align="center"|2000 || broken
|-
| [[HAVAL]] || Zheng, Pieprzyk, Seberry || align="center"|1994 || broken
|-
| [[LAKE]] || Aumasson, Meier, Phan|| align="center"|2008|| ?
|-
| [[LASH-n]] || Bentahar, Page, Saarinen, Silverman, Smart || align="center"|2006 || broken
|-
| [[MAME]] || Yoshida, Watanabe, Okeya, Kitahara, Wu, Kucuk, Preneel || align="center"|2007 || ?
|-
| [[MD2]] || Rivest || align="center"|1989 || broken
|-
| [[MD4]] || Rivest || align="center"|1990 || broken
|-
| [[MD5]] || Rivest || align="center"|1992 || broken
|-
| [[N-Hash]] || Miyaguchi, Ohta, Iwata || align="center"|1990 || broken
|-
| [[PANAMA]] || Daemen, Clapp || align="center"|1998 || broken
|-
| [[Parallel FFT-Hash]] || Schnorr, Vaudenay || align="center"|1993 || ?
|-
| [[PARSHA-256]] || Pal, Sarkar || align="center"|2003 || ?
|-
| [[PKC-HASH]] || Shin, Rhee, Ryu, Lee || align="center"|1998 || broken
|-
| [[RadioGatun]] || Bertoni, Daemen, Peeters, van Assche || align="center"|2006 || ?
|-
| [[RC4-HASH]] || Chang, Gupta, Nandi || align="center"|2006 || broken
|-
| [[RIPEMD]] || The RIPE Consortium || align="center"|1990 || broken
|-
| [[RIPEMD-128]] || Dobbertin, Bosselaers, Preneel || align="center"|1996 || ?
|-
| [[RIPEMD-160]] || Dobbertin, Bosselaers, Preneel || align="center"|1996 || ?
|-
| [[SHA-0]] || NIST/NSA || align="center"|1991 || broken
|-
| [[SHA-1]] || NIST/NSA || align="center"|1993 || broken
|-
| [[SHA-256/224]] || NIST/NSA || align="center"|2000 || ?
|-
| [[SHA-512/384]] || NIST/NSA || align="center"|2000 || ?
|-
| [[SMASH]] || Knudsen || align="center"|2005 || broken
|-
| [[Snefru-n]] || Merkle || align="center"|1990 || broken
|-
| [[StepRightUp]] || Daemen || align="center"|1995 || broken
|-
| [[SubHash]] || Daemen || align="center"|1992 || ?
|-
| [[SWIFFT]] || Lyubashevsky, Micciancio, Peikert, Rosen || align="center"|2008 || ?
|-
| [[Tiger]] || Anderson, Biham || align="center"|1996 || broken
|-
| [[Vortex]] || Gueron, Kounavis || align="center"|2008 || broken
|-
| [[VSH]] || Contini, Lenstra, Steinfeld || align="center"|2005 || ?
|-
| [[Whirlpool]] || Barreto and Rijmen || align="center"|2000 || ?
|}

Regarding the column cryptanalysis status, for simplicity reasons we take the following view.
As soon as there are results suggesting that an expected property of a hash function is less than ideal, we list it as 'broken'. Resulting attacks may be by no means practical.

Note that the source for most of the data collected here (proposals and analysis results) is published in one of the following venues. Journal of Cryptology, IEEE Transactions on Information Theory, proceedings of IACR conferences like Crypto, Eurocrypt, Asiacrypt, Africacrypt, FSE. Additionally also SAC, ISC, CT-RSA, PKCS, FIPS and ISO Standards are used.

Vortex

2009-07-30T12:50:45Z

Crechberger: Update on Vortex

== Specification ==

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

<bibtex>
@inproceedings{iswGueronK08,
author = {Shay Gueron and Michael E. Kounavis},
title = {Vortex: A New Family of One-Way Hash Functions Based on AES Rounds and Carry-Less Multiplication},
booktitle = {ISC},
year = {2008},
pages = {331-340},
abstract = {We present Vortex a new family of one way hash functions that can produce message digests of 256 bits. The main idea behind the design of these hash functions is that we use well known algorithms that can support very fast diffusion in a small number of steps. We also balance the cryptographic strength that comes from iterating block cipher rounds with SBox substitution and diffusion (like Whirlpool) against the need to have a lightweight implementation with as small number of rounds as possible. We use only 3 AES rounds but with a stronger key schedule. Our goal is not to protect a secret symmetric key but to support perfect mixing of the bits of the input into the hash value. Three AES rounds are followed by our variant of Galois Field multiplication. This achieves cross-mixing between 128-bit sets. We present a set of qualitative arguments why we believe Vortex is secure.},
url = {http://dx.doi.org/10.1007/978-3-540-85886-7_23},
editor = {Tzong-Chen Wu and Chin-Laung Lei and Vincent Rijmen and Der-Tsai Lee},
publisher = {Springer},
series = {LNCS},
volume = {5222},
isbn = {978-3-540-85884-3},
}
</bibtex>

== Cryptanalysis ==

=== Best Known Results ===
Collision attacks and distinguishing attacks were found.
----

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

----

=== Collision Attacks ===
A collision attack is described in
<bibtex>
@inproceedings{ADMRT09,
author = {Jean-Philippe Aumasson and Orr Dunkelman and Florian Mendel and Christian Rechberger and Søren S. Thomsen},
title = {Cryptanalysis of Vortex},
booktitle = {AFRICACRYPT},
year = {2009},
publisher = {Springer},
editor = {Bart Preneel},
series = {LNCS},
pages = {14-28},
volume = {5580},
url = {http://www.131002.net/data/papers/ADMRT09.pdf},
abstract = {Vortex is a hash function that was first presented at ISC’2008, then submitted to the NIST SHA-3 competition after some modifications. This paper describes several attacks on both versions of Vortex, including collisions, second preimages, preimages, and distinguishers. Our attacks exploit flaws both in the high-level design and in the lower-level algorithms.},
}
</bibtex>

----

----

=== Preimage Attacks ===

----

=== Others ===
A distinguisher is described in
<bibtex>
@inproceedings{ADMRT09,
author = {Jean-Philippe Aumasson and Orr Dunkelman and Florian Mendel and Christian Rechberger and Søren S. Thomsen},
title = {Cryptanalysis of Vortex},
booktitle = {AFRICACRYPT},
year = {2009},
publisher = {Springer},
editor = {Bart Preneel},
series = {LNCS},
pages = {14-28},
volume = {5580},
url = {http://www.131002.net/data/papers/ADMRT09.pdf},
abstract = {Vortex is a hash function that was first presented at ISC’2008, then submitted to the NIST SHA-3 competition after some modifications. This paper describes several attacks on both versions of Vortex, including collisions, second preimages, preimages, and distinguishers. Our attacks exploit flaws both in the high-level design and in the lower-level algorithms.},
}
</bibtex>

Lesamnta

2009-07-30T08:16:31Z

Crechberger: Update on Lesamta

== The algorithm ==

* Author(s): Shoichi Hirose, Hidenori Kuwakado, Hirotaka Yoshida
* Website: [http://www.sdl.hitachi.co.jp/crypto/lesamnta/ http://www.sdl.hitachi.co.jp/crypto/lesamnta/]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Lesamnta.zip Lesamnta.zip]

<bibtex>
@misc{sha3HiroseKY08,
author = {Shoichi Hirose and Hidenori Kuwakado and Hirotaka Yoshida},
title = {SHA-3 Proposal: Lesamnta},
url = {http://ehash.iaik.tugraz.at/uploads/5/5c/Lesamnta.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

<bibtex>
@misc{sha3HiroseKY09,
author = {Shoichi Hirose and Hidenori Kuwakado and Hirotaka Yoshida}
title = {Security Analysis of the Compression Function
of Lesamnta and its Impact},
url = {http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/LESAMNTA_Comments.pdf},
howpublished = {Official comment},
year = {2009},
</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 || 256 || full || O(264) || - || Bouillaguet, Dunkelman, Leurent, Fouque
|-
|}

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

<bibtex>
@misc{privateHiroseKY09,
author = {C. Bouillaguet and O. Dunkelman and G. Leurent and P. A. Fouque}
title = {Personal communication},
howpublished = {Cited in Shoichi Hirose, Hidenori Kuwakado, Hirotaka Yoshida: "Security Analysis of the Compression Function of Lesamnta and its Impact"},
year = {2009},
</bibtex>

FSB (SHA-3 submission)

2009-07-20T12:20:18Z

Crechberger: Added Bernstein et al. implementation of generic attack against FSB

== The algorithm ==

* Author(s): Daniel Augot, Matthieu Finiasz, Philippe Gaborit, Stéphane Manuel, Nicolas Sendrier
* Website: [http://www-rocq.inria.fr/secret/CBCrypto/index.php?pg=fsb http://www-rocq.inria.fr/secret/CBCrypto/index.php?pg=fsb]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/FSB.zip FSB.zip]

<bibtex>
@misc{sha3AFGMS08,
author = {Daniel Augot and Matthieu Finiasz and Philippe Gaborit and Stéphane Manuel and Nicolas Sendrier},
title = {SHA-3 proposal: FSB},
url = {http://www-rocq.inria.fr/secret/CBCrypto/fsbdoc.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

<bibtex>
@misc{cryptoeprint:2009:292,
author = {Daniel J. Bernstein and Tanja Lange and Christiane Peters and Ruben Niederhagen and Peter Schwabe},
title = {Implementing Wagner's generalized birthday attack against the SHA-3 candidate FSB},
howpublished = {Cryptology ePrint Archive, Report 2009/292},
year = {2009},
note = {\url{http://eprint.iacr.org/}},
url = {http://eprint.iacr.org/2009/292.pdf},
abstract = {The hash function FSB is one of the candidates submitted to NIST's competition to find the new standard hash function, SHA-3. The compression function of FSB is based on error correcting codes. In this paper we show how to use Wagner's generalized birthday attack to find collisions in FSB's compression function. In particular, we present details on our implementation attacking FSB_48, a toy version of FSB which was proposed by the FSB submitters as a training case for FSB. Our attack does not make use of any properties of the particular linear code used within FSB. FSB_48 was chosen as a target where generalized birthday attacks would be one of the strongest attacks and which could be attacked in practice.

We show how to adapt this attack so that it runs on our computer cluster of only 10 PCs which provides far less memory than the usual implementation of generalized birthday attacks would require. This situation is very interesting for estimating the security of systems against distributed attacks using contributed off-the-shelf PCs.

For the SHA-3 competition this result is meaningful in that it allows to assess the security of FSB against the strongest non-structural attack; it does not provide any insight in the security of this particular choice of linear code. }
}
}
</bibtex>

TIB3

2009-05-05T07:03:37Z

Crechberger: Tweak on TIB3

== The algorithm ==

* Author(s): Daniel Penazzi, Miguel Montes
* Website: [http://www.famaf.unc.edu.ar/~penazzi/tib3/ http://www.famaf.unc.edu.ar/~penazzi/tib3/]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/TIB3.zip TIB3.zip]

<bibtex>
@misc{sha3TIB308,
author = {Miguel Montes and Daniel Penazzi},
title = {The TIB3 Hash},
url = {http://www.famaf.unc.edu.ar/~penazzi/tib3/submitted/Supporting_Documentation/TIB3_Algorithm_Specification.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

<bibtex>
@misc{sha3TIB309,
author = {Miguel Montes and Daniel Penazzi},
title = {Tweak on TIB3},
url = {http://www.famaf.unc.edu.ar/~penazzi/tib3/TweakofTIB3/Supporting_Documentation/TIB3_Tweak.pdf},
howpublished = {Available online},
year = {2009},
}
</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 || || 224 || - || [http://ehash.iaik.tugraz.at/uploads/2/2b/Tib3-pseudo.pdf Mendel,Schläffer]
|-
| style="background:greenyellow" | collision || hash || 256 || || 2122.5 || 2122.5 || [http://ehash.iaik.tugraz.at/uploads/2/2b/Tib3-pseudo.pdf Mendel,Schläffer]
|-
| style="background:yellow" | collision || hash || 512 || || 2244.5 || 2244.5 || [http://ehash.iaik.tugraz.at/uploads/2/2b/Tib3-pseudo.pdf Mendel,Schläffer]
|-
|}

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

<bibtex>
@misc{twisterMRS08,
author = {Florian Mendel and Martin Schläffer},
title = {On Pseudo-Collisions and Collisions for TIB3},
url = {http://ehash.iaik.tugraz.at/uploads/2/2b/Tib3-pseudo.pdf},
howpublished = {Available online},
year = {2009},
abstract = {In this paper, we present a pseudo-collision for TIB3 with a complexity of about $2^{32}$ compression function evaluations. By using message modification techniques the complexity can be further reduced. Furthermore, we show how to construct collisions for TIB3 slightly faster than brute force search using the fact that we can construct several (different) pseudo-collisions for the compression function. The complexity to construct collisions is about $2^{122.5}$ for TIB3-256 and $2^{244.5}$ for TIB3-512 with neglible memory requirements.
This attack shows that compression function attacks have been underestimated in the design of TIB3. Although the practicality of the proposed attacks might be debatable, it nevertheless exhibits non-random properties that are not present in the SHA-2 family and opens the possibility for further improved attacks.}
</bibtex>

LUX

2009-05-05T07:00:50Z

Crechberger: Specification Update of LUX

== The algorithm ==

* Author(s): Ivica Nikolić, Alex Biryukov, and Dmitry Khovratovich
* Website: [http://cryptolux.org/LUX http://cryptolux.org/LUX]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/LUX.zip LUX.zip]

<bibtex>
@misc{sha3BiryukovKN08,
author = {Ivica Nikolić and Alex Biryukov and Dmitry Khovratovich},
title = {Hash family LUX - Algorithm Specifications and
Supporting Documentation},
url = {http://ehash.iaik.tugraz.at/uploads/f/f3/LUX.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

<bibtex>
@misc{sha3BiryukovKN09,
author = {Ivica Nikolić and Alex Biryukov and Dmitry Khovratovich},
title = {Specification Update of the Hash Family LUX},
url = {http://ehash.iaik.tugraz.at/uploads/c/c6/LUXadd.pdf},
howpublished = {Available online (local link)},
year = {2009},
}
</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 || reduced hash || 224 || 3 blank rounds || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
|-
| | near-collision || reduced hash || 256 || 3 blank rounds || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
|-
| | free-start collision || compression || ? || || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
|-
| | free-start preimage || compression || ? || || 280 || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
|-
| | distinguisher || hash|| all || || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu],[http://ehash.iaik.tugraz.at/uploads/7/78/Lux_nicky.txt Mouha]
|-
| | distinguisher || reduced hash || 256 || 8 blank rounds || example, 28 || - || [http://ehash.iaik.tugraz.at/uploads/3/3b/LUXATTACKNext.pdf Schmidt-Nielsen],[http://ehash.iaik.tugraz.at/uploads/f/f9/LUXdistinguisher.zip Bjørstad]
|-
| | distinguisher || reduced hash || 512 || 9 blank rounds || example, 28 || - || [http://ehash.iaik.tugraz.at/uploads/3/3b/LUXATTACKNext.pdf Schmidt-Nielsen],[http://ehash.iaik.tugraz.at/uploads/f/f9/LUXdistinguisher.zip Bjørstad]
|-
| | slide-attack || hash || all || salt size: 31 mod 32 || - || - || [http://ehash.iaik.tugraz.at/uploads/6/62/Lux_peyrin.txt Peyrin]
|-
| style="background:orange" | collision|| hash || 256 || || 2100 || - || [http://ehash.iaik.tugraz.at/uploads/e/ec/Lux_dai.txt Watanabe],[http://ehash.iaik.tugraz.at/uploads/2/21/Lux_niels.txt Ferguson]
|-
| style="background:orange" | second preimage|| hash || 256 || || 2200 || - || [http://ehash.iaik.tugraz.at/uploads/e/ec/Lux_dai.txt Watanabe]
|-
| style="background:orange" | collision|| hash || 512|| || 2228 || - || [http://ehash.iaik.tugraz.at/uploads/e/ec/Lux_dai.txt Watanabe],[http://ehash.iaik.tugraz.at/uploads/2/21/Lux_niels.txt Ferguson]
|-
| style="background:orange" | second preimage|| hash || 512|| || 2456 || - || [http://ehash.iaik.tugraz.at/uploads/e/ec/Lux_dai.txt Watanabe]
|-
| | distinguisher || HMAC, DRBG|| all || || - || - || [http://ehash.iaik.tugraz.at/uploads/2/21/Lux_niels.txt Ferguson]
|-
|}

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

<bibtex>
@misc{luxWFW08,
author = {Shuang Wu and Dengguo Feng and Wenling Wu},
title = {Cryptanalysis of the Hash Function LUX-256},
url = {http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf},
howpublished = {Available online},
year = {2008},
abstract = {LUX is a new hash function submitted to NIST's SHA-3 competition. In this paper, we found some non-random properties of LUX due to the weakness of origin shift vector. We also give reduced blank round collision attack, free-start collision attack and free-start preimage attack on LUX-256. The two collision attacks are trivial. The free-start preimage attack has complexity of about 2^{80} and requires negligible memory.},
}
</bibtex>

<bibtex>
@misc{luxS09,
author = {Peter Schmidt-Nielsen},
title = {A distinguisher for reduced-round LUX},
url = {http://ehash.iaik.tugraz.at/uploads/3/3b/LUXATTACKNext.pdf},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{luxB09,
author = {Tor E. Bjørstad},
title = {A distinguisher for reduced-round LUX (source code)},
url = {http://ehash.iaik.tugraz.at/uploads/f/f9/LUXdistinguisher.zip},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{luxP08,
author = {Thomas Peyrin},
title = {Slide attacks on LUX},
url = {http://ehash.iaik.tugraz.at/uploads/6/62/Lux_peyrin.txt},
howpublished = {NIST mailing list (local link)},
year = {2008},
}
</bibtex>

<bibtex>
@misc{luxD09,
author = {Watanabe Dai},
title = {OFFICIAL COMMENT: LUX},
url = {http://ehash.iaik.tugraz.at/uploads/e/ec/Lux_dai.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{luxF09,
author = {Niels Ferguson},
title = {RE: OFFICIAL COMMENT: LUX},
url = {http://ehash.iaik.tugraz.at/uploads/2/21/Lux_niels.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{luxM09,
author = {Nicky Mouha},
title = {RE: OFFICIAL COMMENT: LUX},
url = {http://ehash.iaik.tugraz.at/uploads/7/78/Lux_nicky.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

File:LUXadd.pdf

2009-05-05T07:00:22Z

Crechberger:

The SHA-3 Zoo

2009-04-14T09:59:13Z

Crechberger:

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 [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/submissions_rnd1.html submissions] have advanced to the first round.
So far, 10 out of 51 first round candidates have been officially conceded broken or withdrawn by the designers.

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]

{| 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
|-
| [[ARIRANG]] || Jongin Lim || ||
|-
| [[AURORA]] || Masahiro Fujita || style="background:orange"| 2nd preimage ||
|-
| [[BLAKE]] || Jean-Philippe Aumasson || ||
|-
| [[Blender]] || Colin Bradbury || style="background:orange" | collision, preimage || near-collision
|-
| [[Blue Midnight Wish]] || Svein Johan Knapskog || ||
|-
| [[Cheetah]] || Dmitry Khovratovich || || length-extension
|-
| [[CHI]] || Phillip Hawkes || ||
|-
| [[CRUNCH]] || Jacques Patarin || || length-extension
|-
| [[CubeHash]] || Daniel J. Bernstein || style="background:greenyellow" | preimage ||
|-
| [[Dynamic SHA]] || Xu Zijie || style="background:orange"|collision || length-extension
|-
| [[Dynamic SHA2]] || Xu Zijie || || length-extension
|-
| [[ECHO]] || Henri Gilbert || ||
|-
| [[ECOH]] || Daniel R. L. Brown || style="background:orange"| 2nd preimage ||
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || Danilo Gligoroski || style="background:yellow" | preimage ||
|-
| [[EnRUPT]] || Sean O'Neil || style="background:red" | collision ||
|-
| [[ESSENCE]] || Jason Worth Martin || ||
|-
| [[FSB (SHA-3 submission) | FSB]] || Matthieu Finiasz || ||
|-
| [[Fugue]] || Charanjit S. Jutla || ||
|-
| [[Groestl|Grøstl]] || Lars R. Knudsen || ||
|-
| [[Hamsi]] || <nowiki>Özgül Küçük</nowiki> || ||
|-
| [[JH]] || Hongjun Wu || style="background:greenyellow" | preimage ||
|-
| [[Keccak]] || The Keccak Team || ||
|-
| [[LANE]] || Sebastiaan Indesteege || ||
|-
| [[Lesamnta]] || Hirotaka Yoshida || ||
|-
| [[Luffa]] || Dai Watanabe || ||
|-
| [[LUX]] || <nowiki>Ivica Nikolić</nowiki> || style="background:orange" | collision, 2nd preimage || DRBG,HMAC
|-
| [[MCSSHA-3]] || Mikhail Maslennikov || style="background:orange" | collision ||
|-
| [[MD6]] || Ronald L. Rivest || ||
|-
| [[NaSHA]] || Smile Markovski || style="background:orange" | collision ||
|-
| [[SANDstorm]] || Rich Schroeppel || ||
|-
| [[Sarmal]] || <nowiki>Kerem Varıcı</nowiki> || style="background:yellow" | preimage ||
|-
| [[Sgàil]] || Peter Maxwell|| style="background:red" | collision ||
|-
| [[Shabal]] || <nowiki>Jean-François Misarsky</nowiki> || ||
|-
| [[SHAvite-3]] || Orr Dunkelman || ||
|-
| [[SIMD]] || <nowiki>Gaëtan Leurent</nowiki> || ||
|-
| [[Skein]] || Bruce Schneier || ||
|-
| [[Spectral Hash]] || <nowiki>Çetin Kaya Koç</nowiki> || style="background:red" | collision ||
|-
| [[SWIFFTX]] || Daniele Micciancio || ||
|-
| [[TIB3]] || Daniel Penazzi || style="background:yellow" | collision ||
|-
| [[Twister]] || Michael Gorski || style="background:orange" | preimage ||
|-
| [[Vortex (SHA-3 submission)|Vortex]] || Michael Kounavis || style="background:yellow" | preimage ||
|}

The following hash functions have been submitted to the NIST competition but did not advance to the first round, or have been conceded broken or withdrawn by the designers:

{| 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="120" | Best Attack on Main NIST Requirements
|-
| [[Abacus]] || Neil Sholer || conceded broken || style="background:orange" | 2nd-preimage
|-
| [[Boole]] || Greg Rose || conceded broken || style="background:red" | collision
|-
| [[DCH]] || David A. Wilson || conceded broken || style="background:red" | collision
|-
| [[HASH 2X]] || Jason Lee || not in round 1 || style="background:red" | 2nd-preimage
|-
| [[Khichidi-1]] || M. Vidyasagar || conceded broken || style="background:red" | collision
|-
| [[Maraca]] || Robert J. Jenkins || not in round 1 || style="background:red" | preimage
|-
| [[MeshHash]] || Björn Fay || conceded broken || style="background:orange" | 2nd preimage
|-
| [[NKS2D]] || Geoffrey Park || not in round 1 || style="background:red" | collision
|-
| [[Ponic]] || Peter Schmidt-Nielsen || not in round 1 || style="background:yellow" | 2nd-preimage
|-
| [[SHAMATA]] || Orhun Kara || conceded broken || style="background:red" | collision
|-
| [[StreamHash]] || Michal Trojnara || conceded broken || style="background:red" | collision
|-
| [[Tangle]] || Rafael Alvarez || conceded broken || style="background:red" | collision
|-
| [[WaMM]] || John Washburn || conceded broken || style="background:red" | collision
|-
| [[Waterfall]] || Bob Hattersley || conceded broken || 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!

The SHA-3 Zoo

2009-04-14T09:57:32Z

Crechberger:

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 [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/submissions_rnd1.html submissions] have advanced to the first round.
So far, 10 out of 51 first round candidates have been officially conceded broken or withdrawn by the designers.

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]

{| 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"| Best Attack on Main NIST Requirements !! width="160"| Best Attack on other Hash Requirements
|-
| [[ARIRANG]] || Jongin Lim || ||
|-
| [[AURORA]] || Masahiro Fujita || style="background:orange"| 2nd preimage ||
|-
| [[BLAKE]] || Jean-Philippe Aumasson || ||
|-
| [[Blender]] || Colin Bradbury || style="background:orange" | collision, preimage || near-collision
|-
| [[Blue Midnight Wish]] || Svein Johan Knapskog || ||
|-
| [[Cheetah]] || Dmitry Khovratovich || || length-extension
|-
| [[CHI]] || Phillip Hawkes || ||
|-
| [[CRUNCH]] || Jacques Patarin || || length-extension
|-
| [[CubeHash]] || Daniel J. Bernstein || style="background:greenyellow" | preimage ||
|-
| [[Dynamic SHA]] || Xu Zijie || style="background:orange"|collision || length-extension
|-
| [[Dynamic SHA2]] || Xu Zijie || || length-extension
|-
| [[ECHO]] || Henri Gilbert || ||
|-
| [[ECOH]] || Daniel R. L. Brown || style="background:orange"| 2nd preimage ||
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || Danilo Gligoroski || style="background:yellow" | preimage ||
|-
| [[EnRUPT]] || Sean O'Neil || style="background:red" | collision ||
|-
| [[ESSENCE]] || Jason Worth Martin || ||
|-
| [[FSB (SHA-3 submission) | FSB]] || Matthieu Finiasz || ||
|-
| [[Fugue]] || Charanjit S. Jutla || ||
|-
| [[Groestl|Grøstl]] || Lars R. Knudsen || ||
|-
| [[Hamsi]] || <nowiki>Özgül Küçük</nowiki> || ||
|-
| [[JH]] || Hongjun Wu || style="background:greenyellow" | preimage ||
|-
| [[Keccak]] || The Keccak Team || ||
|-
| [[LANE]] || Sebastiaan Indesteege || ||
|-
| [[Lesamnta]] || Hirotaka Yoshida || ||
|-
| [[Luffa]] || Dai Watanabe || ||
|-
| [[LUX]] || <nowiki>Ivica Nikolić</nowiki> || style="background:orange" | collision, 2nd preimage || DRBG,HMAC
|-
| [[MCSSHA-3]] || Mikhail Maslennikov || style="background:orange" | collision ||
|-
| [[MD6]] || Ronald L. Rivest || ||
|-
| [[NaSHA]] || Smile Markovski || style="background:orange" | collision ||
|-
| [[SANDstorm]] || Rich Schroeppel || ||
|-
| [[Sarmal]] || <nowiki>Kerem Varıcı</nowiki> || style="background:yellow" | preimage ||
|-
| [[Sgàil]] || Peter Maxwell|| style="background:red" | collision ||
|-
| [[Shabal]] || <nowiki>Jean-François Misarsky</nowiki> || ||
|-
| [[SHAvite-3]] || Orr Dunkelman || ||
|-
| [[SIMD]] || <nowiki>Gaëtan Leurent</nowiki> || ||
|-
| [[Skein]] || Bruce Schneier || ||
|-
| [[Spectral Hash]] || <nowiki>Çetin Kaya Koç</nowiki> || style="background:red" | collision ||
|-
| [[SWIFFTX]] || Daniele Micciancio || ||
|-
| [[TIB3]] || Daniel Penazzi || style="background:yellow" | collision ||
|-
| [[Twister]] || Michael Gorski || style="background:orange" | preimage ||
|-
| [[Vortex (SHA-3 submission)|Vortex]] || Michael Kounavis || style="background:yellow" | preimage ||
|}

The following hash functions have been submitted to the NIST competition but did not advance to the first round, or have been conceded broken or withdrawn by the designers:

{| 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="120" | Best Attack on Main NIST Requirements
|-
| [[Abacus]] || Neil Sholer || conceded broken || style="background:orange" | 2nd-preimage
|-
| [[Boole]] || Greg Rose || conceded broken || style="background:red" | collision
|-
| [[DCH]] || David A. Wilson || conceded broken || style="background:red" | collision
|-
| [[HASH 2X]] || Jason Lee || not in round 1 || style="background:red" | 2nd-preimage
|-
| [[Khichidi-1]] || M. Vidyasagar || conceded broken || style="background:red" | collision
|-
| [[Maraca]] || Robert J. Jenkins || not in round 1 || style="background:red" | preimage
|-
| [[MeshHash]] || Björn Fay || conceded broken || style="background:orange" | 2nd preimage
|-
| [[NKS2D]] || Geoffrey Park || not in round 1 || style="background:red" | collision
|-
| [[Ponic]] || Peter Schmidt-Nielsen || not in round 1 || style="background:yellow" | 2nd-preimage
|-
| [[SHAMATA]] || Orhun Kara || conceded broken || style="background:red" | collision
|-
| [[StreamHash]] || Michal Trojnara || conceded broken || style="background:red" | collision
|-
| [[Tangle]] || Rafael Alvarez || conceded broken || style="background:red" | collision
|-
| [[WaMM]] || John Washburn || conceded broken || style="background:red" | collision
|-
| [[Waterfall]] || Bob Hattersley || conceded broken || 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!

The SHA-3 Zoo

2009-04-14T09:56:00Z

Crechberger: collision, 2nd-preimage and other attacks on LUX

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 [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/submissions_rnd1.html submissions] have advanced to the first round.
So far, 10 out of 51 first round candidates have been officially conceded broken or withdrawn by the designers.

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]

{| 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"| Best Attack on Main NIST Requirements !! width="140"| Best Attack on other Hash Requirements
|-
| [[ARIRANG]] || Jongin Lim || ||
|-
| [[AURORA]] || Masahiro Fujita || style="background:orange"| 2nd preimage ||
|-
| [[BLAKE]] || Jean-Philippe Aumasson || ||
|-
| [[Blender]] || Colin Bradbury || style="background:orange" | collision, preimage || near-collision
|-
| [[Blue Midnight Wish]] || Svein Johan Knapskog || ||
|-
| [[Cheetah]] || Dmitry Khovratovich || || length-extension
|-
| [[CHI]] || Phillip Hawkes || ||
|-
| [[CRUNCH]] || Jacques Patarin || || length-extension
|-
| [[CubeHash]] || Daniel J. Bernstein || style="background:greenyellow" | preimage ||
|-
| [[Dynamic SHA]] || Xu Zijie || style="background:orange"|collision || length-extension
|-
| [[Dynamic SHA2]] || Xu Zijie || || length-extension
|-
| [[ECHO]] || Henri Gilbert || ||
|-
| [[ECOH]] || Daniel R. L. Brown || style="background:orange"| 2nd preimage ||
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || Danilo Gligoroski || style="background:yellow" | preimage ||
|-
| [[EnRUPT]] || Sean O'Neil || style="background:red" | collision ||
|-
| [[ESSENCE]] || Jason Worth Martin || ||
|-
| [[FSB (SHA-3 submission) | FSB]] || Matthieu Finiasz || ||
|-
| [[Fugue]] || Charanjit S. Jutla || ||
|-
| [[Groestl|Grøstl]] || Lars R. Knudsen || ||
|-
| [[Hamsi]] || <nowiki>Özgül Küçük</nowiki> || ||
|-
| [[JH]] || Hongjun Wu || style="background:greenyellow" | preimage ||
|-
| [[Keccak]] || The Keccak Team || ||
|-
| [[LANE]] || Sebastiaan Indesteege || ||
|-
| [[Lesamnta]] || Hirotaka Yoshida || ||
|-
| [[Luffa]] || Dai Watanabe || ||
|-
| [[LUX]] || <nowiki>Ivica Nikolić</nowiki> || style="background:orange" | collision, 2nd preimage || DRBG,HMAC
|-
| [[MCSSHA-3]] || Mikhail Maslennikov || style="background:orange" | collision ||
|-
| [[MD6]] || Ronald L. Rivest || ||
|-
| [[NaSHA]] || Smile Markovski || style="background:orange" | collision ||
|-
| [[SANDstorm]] || Rich Schroeppel || ||
|-
| [[Sarmal]] || <nowiki>Kerem Varıcı</nowiki> || style="background:yellow" | preimage ||
|-
| [[Sgàil]] || Peter Maxwell|| style="background:red" | collision ||
|-
| [[Shabal]] || <nowiki>Jean-François Misarsky</nowiki> || ||
|-
| [[SHAvite-3]] || Orr Dunkelman || ||
|-
| [[SIMD]] || <nowiki>Gaëtan Leurent</nowiki> || ||
|-
| [[Skein]] || Bruce Schneier || ||
|-
| [[Spectral Hash]] || <nowiki>Çetin Kaya Koç</nowiki> || style="background:red" | collision ||
|-
| [[SWIFFTX]] || Daniele Micciancio || ||
|-
| [[TIB3]] || Daniel Penazzi || style="background:yellow" | collision ||
|-
| [[Twister]] || Michael Gorski || style="background:orange" | preimage ||
|-
| [[Vortex (SHA-3 submission)|Vortex]] || Michael Kounavis || style="background:yellow" | preimage ||
|}

The following hash functions have been submitted to the NIST competition but did not advance to the first round, or have been conceded broken or withdrawn by the designers:

{| 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="120" | Best Attack on Main NIST Requirements
|-
| [[Abacus]] || Neil Sholer || conceded broken || style="background:orange" | 2nd-preimage
|-
| [[Boole]] || Greg Rose || conceded broken || style="background:red" | collision
|-
| [[DCH]] || David A. Wilson || conceded broken || style="background:red" | collision
|-
| [[HASH 2X]] || Jason Lee || not in round 1 || style="background:red" | 2nd-preimage
|-
| [[Khichidi-1]] || M. Vidyasagar || conceded broken || style="background:red" | collision
|-
| [[Maraca]] || Robert J. Jenkins || not in round 1 || style="background:red" | preimage
|-
| [[MeshHash]] || Björn Fay || conceded broken || style="background:orange" | 2nd preimage
|-
| [[NKS2D]] || Geoffrey Park || not in round 1 || style="background:red" | collision
|-
| [[Ponic]] || Peter Schmidt-Nielsen || not in round 1 || style="background:yellow" | 2nd-preimage
|-
| [[SHAMATA]] || Orhun Kara || conceded broken || style="background:red" | collision
|-
| [[StreamHash]] || Michal Trojnara || conceded broken || style="background:red" | collision
|-
| [[Tangle]] || Rafael Alvarez || conceded broken || style="background:red" | collision
|-
| [[WaMM]] || John Washburn || conceded broken || style="background:red" | collision
|-
| [[Waterfall]] || Bob Hattersley || conceded broken || 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!

LUX

2009-04-14T09:47:34Z

Crechberger: collision, 2nd-preimage, and other attacks on LUX

== The algorithm ==

* Author(s): Ivica Nikolić, Alex Biryukov, and Dmitry Khovratovich
* Website: [http://cryptolux.org/LUX http://cryptolux.org/LUX]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/LUX.zip LUX.zip]

<bibtex>
@misc{sha3BiryukovKN,
author = {Ivica Nikolić and Alex Biryukov and Dmitry Khovratovich},
title = {Hash family LUX - Algorithm Specifications and
Supporting Documentation},
url = {http://ehash.iaik.tugraz.at/uploads/f/f3/LUX.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 || reduced hash || 224 || 3 blank rounds || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
|-
| | near-collision || reduced hash || 256 || 3 blank rounds || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
|-
| | free-start collision || compression || ? || || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
|-
| | free-start preimage || compression || ? || || 280 || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
|-
| | distinguisher || hash|| 256/512 || || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu],[http://ehash.iaik.tugraz.at/uploads/7/78/Lux_nicky.txt Mouha]
|-
| | distinguisher || reduced hash || 256 || 8 blank rounds || example, 28 || - || [http://ehash.iaik.tugraz.at/uploads/3/3b/LUXATTACKNext.pdf Schmidt-Nielsen],[http://ehash.iaik.tugraz.at/uploads/f/f9/LUXdistinguisher.zip Bjørstad]
|-
| | distinguisher || reduced hash || 512 || 9 blank rounds || example, 28 || - || [http://ehash.iaik.tugraz.at/uploads/3/3b/LUXATTACKNext.pdf Schmidt-Nielsen],[http://ehash.iaik.tugraz.at/uploads/f/f9/LUXdistinguisher.zip Bjørstad]
|-
| | slide-attack || hash || all || salt size: 31 mod 32 || - || - || [http://ehash.iaik.tugraz.at/uploads/6/62/Lux_peyrin.txt Peyrin]
|-
| style="background:orange" | collision|| hash || 256 || || 2100 || - || [http://ehash.iaik.tugraz.at/uploads/e/ec/Lux_dai.txt Watanabe],[http://ehash.iaik.tugraz.at/uploads/2/21/Lux_niels.txt Ferguson]
|-
| style="background:orange" | second preimage|| hash || 256 || || 2200 || - || [http://ehash.iaik.tugraz.at/uploads/e/ec/Lux_dai.txt Watanabe]
|-
| style="background:orange" | collision|| hash || 512|| || 2228 || - || [http://ehash.iaik.tugraz.at/uploads/e/ec/Lux_dai.txt Watanabe],[http://ehash.iaik.tugraz.at/uploads/2/21/Lux_niels.txt Ferguson]
|-
| style="background:orange" | second preimage|| hash || 512|| || 2456 || - || [http://ehash.iaik.tugraz.at/uploads/e/ec/Lux_dai.txt Watanabe]
|-
| | distinguisher || HMAC, DRBG|| all || || - || - || [http://ehash.iaik.tugraz.at/uploads/2/21/Lux_niels.txt Ferguson]
|-
|}

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

<bibtex>
@misc{luxWFW08,
author = {Shuang Wu and Dengguo Feng and Wenling Wu},
title = {Cryptanalysis of the Hash Function LUX-256},
url = {http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf},
howpublished = {Available online},
year = {2008},
abstract = {LUX is a new hash function submitted to NIST's SHA-3 competition. In this paper, we found some non-random properties of LUX due to the weakness of origin shift vector. We also give reduced blank round collision attack, free-start collision attack and free-start preimage attack on LUX-256. The two collision attacks are trivial. The free-start preimage attack has complexity of about 2^{80} and requires negligible memory.},
}
</bibtex>

<bibtex>
@misc{luxS09,
author = {Peter Schmidt-Nielsen},
title = {A distinguisher for reduced-round LUX},
url = {http://ehash.iaik.tugraz.at/uploads/3/3b/LUXATTACKNext.pdf},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{luxB09,
author = {Tor E. Bjørstad},
title = {A distinguisher for reduced-round LUX (source code)},
url = {http://ehash.iaik.tugraz.at/uploads/f/f9/LUXdistinguisher.zip},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{luxP08,
author = {Thomas Peyrin},
title = {Slide attacks on LUX},
url = {http://ehash.iaik.tugraz.at/uploads/6/62/Lux_peyrin.txt},
howpublished = {NIST mailing list (local link)},
year = {2008},
}
</bibtex>

<bibtex>
@misc{luxD09,
author = {Watanabe Dai},
title = {OFFICIAL COMMENT: LUX},
url = {http://ehash.iaik.tugraz.at/uploads/e/ec/Lux_dai.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{luxF09,
author = {Niels Ferguson},
title = {RE: OFFICIAL COMMENT: LUX},
url = {http://ehash.iaik.tugraz.at/uploads/2/21/Lux_niels.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

<bibtex>
@misc{luxM09,
author = {Nicky Mouha},
title = {RE: OFFICIAL COMMENT: LUX},
url = {http://ehash.iaik.tugraz.at/uploads/7/78/Lux_nicky.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

File:Lux nicky.txt

2009-04-14T09:37:54Z

Crechberger:

File:Lux niels.txt

2009-04-14T09:32:46Z

Crechberger:

File:Lux dai.txt

2009-04-14T09:13:46Z

Crechberger:

Shabal

2009-04-09T09:29:41Z

Crechberger: new nonrandomness observations on the Shabal permutation

The SHA-3 Zoo

2009-04-01T07:08:16Z

Crechberger: near-collision resistance is a NIST requirement, added practical attack on Blender

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 [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/submissions_rnd1.html submissions] have advanced to the first round.
So far, 10 out of 51 first round candidates have been officially conceded broken or withdrawn by the designers.

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]

{| 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"| Best Attack on Main NIST Requirements !! width="140"| Best Attack on other Hash Requirements
|-
| [[ARIRANG]] || Jongin Lim || ||
|-
| [[AURORA]] || Masahiro Fujita || style="background:orange"| 2nd preimage ||
|-
| [[BLAKE]] || Jean-Philippe Aumasson || ||
|-
| [[Blender]] || Colin Bradbury || style="background:orange" | preimage || near-collision
|-
| [[Blue Midnight Wish]] || Svein Johan Knapskog || ||
|-
| [[Cheetah]] || Dmitry Khovratovich || || length-extension
|-
| [[CHI]] || Phillip Hawkes || ||
|-
| [[CRUNCH]] || Jacques Patarin || || length-extension
|-
| [[CubeHash]] || Daniel J. Bernstein || style="background:greenyellow" | preimage ||
|-
| [[Dynamic SHA]] || Xu Zijie || style="background:orange"|collision || length-extension
|-
| [[Dynamic SHA2]] || Xu Zijie || || length-extension
|-
| [[ECHO]] || Henri Gilbert || ||
|-
| [[ECOH]] || Daniel R. L. Brown || ||
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || Danilo Gligoroski || style="background:yellow" | preimage ||
|-
| [[EnRUPT]] || Sean O’Neil || style="background:red" | collision ||
|-
| [[ESSENCE]] || Jason Worth Martin || ||
|-
| [[FSB (SHA-3 submission) | FSB]] || Matthieu Finiasz || ||
|-
| [[Fugue]] || Charanjit S. Jutla || ||
|-
| [[Groestl|Grøstl]] || Lars R. Knudsen || ||
|-
| [[Hamsi]] || Ozgul Kucuk || ||
|-
| [[JH]] || Hongjun Wu || style="background:greenyellow" | preimage ||
|-
| [[Keccak]] || The Keccak Team || ||
|-
| [[LANE]] || Sebastiaan Indesteege || ||
|-
| [[Lesamnta]] || Hirotaka Yoshida || ||
|-
| [[Luffa]] || Dai Watanabe || ||
|-
| [[LUX]] || Ivica Nikolic || ||
|-
| [[MCSSHA-3]] || Mikhail Maslennikov || style="background:orange" | collision ||
|-
| [[MD6]] || Ronald L. Rivest || ||
|-
| [[NaSHA]] || Smile Markovski || style="background:orange" | collision ||
|-
| [[SANDstorm]] || Rich Schroeppel || ||
|-
| [[Sarmal]] || Kerem Varici || style="background:yellow" | preimage ||
|-
| [[Sgàil]] || Peter Maxwell|| style="background:red" | collision ||
|-
| [[Shabal]] || Jean-Francois Misarsky || ||
|-
| [[SHAvite-3]] || Orr Dunkelman || ||
|-
| [[SIMD]] || Gaetan Leurent || ||
|-
| [[Skein]] || Bruce Schneier || ||
|-
| [[Spectral Hash]] || Cetin Kaya Koc || style="background:red" | collision ||
|-
| [[SWIFFTX]] || Daniele Micciancio || ||
|-
| [[TIB3]] || Daniel Penazzi || style="background:yellow" | collision ||
|-
| [[Twister]] || Michael Gorski || style="background:orange" | preimage ||
|-
| [[Vortex (SHA-3 submission)|Vortex]] || Michael Kounavis || style="background:yellow" | preimage ||
|}

The following hash functions have been submitted to the NIST competition but did not advance to the first round, or have been conceded broken or withdrawn by the designers:

{| 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="120" | Best Attack on Main NIST Requirements
|-
| [[Abacus]] || Neil Sholer || conceded broken || style="background:orange" | 2nd-preimage
|-
| [[Boole]] || Greg Rose || conceded broken || style="background:red" | collision
|-
| [[DCH]] || David A. Wilson || conceded broken || style="background:red" | collision
|-
| [[HASH 2X]] || Jason Lee || not in round 1 || style="background:red" | 2nd-preimage
|-
| [[Khichidi-1]] || M. Vidyasagar || conceded broken || style="background:red" | collision
|-
| [[Maraca]] || Robert J. Jenkins || not in round 1 || style="background:red" | preimage
|-
| [[MeshHash]] || Björn Fay || conceded broken || style="background:orange" | 2nd preimage
|-
| [[NKS2D]] || Geoffrey Park || not in round 1 || style="background:red" | collision
|-
| [[Ponic]] || Peter Schmidt-Nielsen || not in round 1 || style="background:yellow" | 2nd-preimage
|-
| [[SHAMATA]] || Orhun Kara || conceded broken || style="background:red" | collision
|-
| [[StreamHash]] || Michal Trojnara || conceded broken || style="background:red" | collision
|-
| [[Tangle]] || Rafael Alvarez || conceded broken || style="background:red" | collision
|-
| [[WaMM]] || John Washburn || conceded broken || style="background:red" | collision
|-
| [[Waterfall]] || Bob Hattersley || conceded broken || 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!

ARIRANG

2009-03-31T14:41:48Z

Crechberger:

== The algorithm ==

* Author(s): Donghoon Chang, Seokhie Hong, Changheon Kang, Jinkeon Kang, Jongsung Kim, Changhoon Lee, Jesang Lee, Jongtae Lee, Sangjin Lee, Yuseop Lee, Jongin Lim, Jaechul Sung

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

<bibtex>
@misc{sha3ChangHKK+08,
author = {Donghoon Chang and Seokhie Hong and Changheon Kang and Jinkeon Kang and Jongsung Kim and Changhoon Lee and Jesang Lee and Jongtae Lee and Sangjin Lee and Yuseop Lee and Jongin Lim and Jaechul Sung},
title = {ARIRANG},
url = {http://ehash.iaik.tugraz.at/uploads/2/2c/Arirang.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|| reduced compression || 256/512 || 26 steps || example, 1 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-
| | near-collision|| compression || 256/512 || full || example, 1 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-
| | pseudo-collision|| hash|| 224|| full || example, 223 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-
| | pseudo-collision|| hash|| 384|| full || example, 1 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-

|}

<bibtex>
@misc{ArirangGMKLW09,
author = {Jian Guo, Krystian Matusiewicz, Lars R. Knudsen, San Ling, and
Huaxiong Wang},
title = {Practical pseudo-collisions for hash functions
ARIRANG-224/384},
url = {http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf },
howpublished = {Available online},
year = {2009},
</bibtex>

ARIRANG

2009-03-30T13:29:20Z

Crechberger:

== The algorithm ==

* Author(s): Donghoon Chang, Seokhie Hong, Changheon Kang, Jinkeon Kang, Jongsung Kim, Changhoon Lee, Jesang Lee, Jongtae Lee, Sangjin Lee, Yuseop Lee, Jongin Lim, Jaechul Sung

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

<bibtex>
@misc{sha3ChangHKK+08,
author = {Donghoon Chang and Seokhie Hong and Changheon Kang and Jinkeon Kang and Jongsung Kim and Changhoon Lee and Jesang Lee and Jongtae Lee and Sangjin Lee and Yuseop Lee and Jongin Lim and Jaechul Sung},
title = {ARIRANG},
url = {http://ehash.iaik.tugraz.at/uploads/2/2c/Arirang.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|| reduced compression || 256/512 || 26 steps || example, 1 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-
| | near-collision|| compression || 256/512 || full || example, 1 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-
| | pseudo-collision|| hash|| 224|| full || example, 223 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-
| | pseudo-collision|| hash|| 384|| full || example, 1 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-

|}

<bibtex>
@misc{ArirangGMKLW09,
author = {Jian Guo, Krystian Matusiewicz, Lars R. Knudsen, San Ling, and
Huaxiong Wan},
title = {Practical pseudo-collisions for hash functions
ARIRANG-224/384},
url = {http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf },
howpublished = {Available online},
year = {2009},
</bibtex>

ARIRANG

2009-03-30T13:24:15Z

Crechberger: Practical compression function attacks on Arirang

== The algorithm ==

* Author(s): Donghoon Chang, Seokhie Hong, Changheon Kang, Jinkeon Kang, Jongsung Kim, Changhoon Lee, Jesang Lee, Jongtae Lee, Sangjin Lee, Yuseop Lee, Jongin Lim, Jaechul Sung

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

<bibtex>
@misc{sha3ChangHKK+08,
author = {Donghoon Chang and Seokhie Hong and Changheon Kang and Jinkeon Kang and Jongsung Kim and Changhoon Lee and Jesang Lee and Jongtae Lee and Sangjin Lee and Yuseop Lee and Jongin Lim and Jaechul Sung},
title = {ARIRANG},
url = {http://ehash.iaik.tugraz.at/uploads/2/2c/Arirang.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|| reduced compression || 256/512 || 26 steps || 1 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-
| | near-collision|| compression || 256/512 || full || 1 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-
| | pseudo-collision|| hash|| 224|| full || 223 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-
| | pseudo-collision|| hash|| 384|| full || 1 || - || [http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf Guo, Matusiewicz, Knudsen, Ling, Wang]
|-

|}

<bibtex>
@misc{ArirangGMKLW09,
author = {Jian Guo, Krystian Matusiewicz, Lars R. Knudsen, San Ling, and
Huaxiong Wan},
title = {Practical pseudo-collisions for hash functions
ARIRANG-224/384},
url = {http://ehash.iaik.tugraz.at/uploads/9/9a/Arirang-pseudo-sha3zoo.pdf },
howpublished = {Available online},
year = {2009},
</bibtex>

File:Arirang-pseudo-sha3zoo.pdf

2009-03-30T12:57:34Z

Crechberger:

Vortex (SHA-3 submission)

2009-03-24T10:22:47Z

Crechberger: color of collision attacks to green

== The algorithm ==

* Author(s): Michael Kounavis, Shay Gueron

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

<bibtex>
@misc{sha3KounavisG08,
author = {Michael Kounavis and Shay Gueron},
title = {Vortex: A New Family of One Way Hash Functions based on Rijndael Rounds and Carry-less Multiplication},
url = {http://eprint.iacr.org/2008/464.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
|-
| | correlation analysis || hash || all || || - || - || [http://ehash.iaik.tugraz.at/uploads/6/6d/Vortex_correlation.txt Ferguson]
|-
| style="background:yellow"| preimage || hash || 256 || || 2195 || 264 || [http://www.131002.net/data/papers/ADMRT09.pdf Aumasson,Dunkelman,Mendel,Rechberger,Thomsen]
|-
| style="background:yellow"| preimage || hash || 512 || || 2387 || 2128 || [http://www.131002.net/data/papers/ADMRT09.pdf Aumasson,Dunkelman,Mendel,Rechberger,Thomsen]
|-
| style="background:greenyellow"| collision || hash || 256 || || 2124.5 || 2124.5 || [http://www.131002.net/data/papers/ADMRT09.pdf Aumasson,Dunkelman,Mendel,Rechberger,Thomsen]
|-
| style="background:greenyellow"| collision || hash || 512 || || 2251.7 || 2251.7 || [http://www.131002.net/data/papers/ADMRT09.pdf Aumasson,Dunkelman,Mendel,Rechberger,Thomsen]
|-
| | distinguisher || hash || 256 || || 297 || - || [http://www.131002.net/data/papers/ADMRT09.pdf Aumasson,Dunkelman,Mendel,Rechberger,Thomsen]
|-
| | 2nd preimage || hash || 256 || weak messages || 2129 || - || [http://www.131002.net/data/papers/ADMRT09.pdf Aumasson,Dunkelman,Mendel,Rechberger,Thomsen]
|-
| | 2nd preimage || hash || 256 || weak messages || 233 || 2135 || [http://www.131002.net/data/papers/ADMRT09.pdf Aumasson,Dunkelman,Mendel,Rechberger,Thomsen]
|-
|}

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

<bibtex>
@misc{VortexF08,
author = {Niels Ferguson},
title = {Simple correlation on some of the output bits of Vortex},
url = {http://ehash.iaik.tugraz.at/uploads/6/6d/Vortex_correlation.txt},
howpublished = {OFFICIAL COMMENT (local link)},
year = {2008},
}
</bibtex>

<bibtex>
@inproceedings{ADMRT09,
author = {Jean-Philippe Aumasson and Orr Dunkelman and Florian Mendel and Christian Rechberger and Søren S. Thomsen},
title = {Cryptanalysis of Vortex},
booktitle = {AFRICACRYPT},
year = {2009},
publisher = {Springer},
editor = {Bart Preneel},
note = {to appear},
url = {http://www.131002.net/data/papers/ADMRT09.pdf},
pages = {?},
}
</bibtex>

===Archive===

<bibtex>
@misc{vortexK+08,
author = {Lars R. Knudsen and Florian Mendel and Christian Rechberger and Søren S. Thomsen},
title = {Collision and Preimage Attacks on Vortex as submitted to the SHA-3 competition},
url = {http://ehash.iaik.tugraz.at/uploads/5/5c/Vortex_Collisions_and_Preimages_note.txt},
howpublished = {Available online},
year = {2008},
}
</bibtex>

<bibtex>
@misc{vortexAD08,
author = {Jean-Philippe Aumasson and Orr Dunkelman},
title = {A note on Vortex' security},
url = {http://www.131002.net/data/papers/AD08.pdf},
howpublished = {Available online},
year = {2008},
abstract = {Vortex is a hash function based on the AES that was presented at
ISC’2008, and submitted to the NIST SHA-3 competition after some modiﬁcations
that aim to strengthen it. This note ﬁrst shows that the original Vortex is not
collision-resistant, by describing an attack running in about 2^{58} compressions, in-
stead of $2^{128}$ ideally. In the new version submitted to NIST, we present several prop-
erties that seem to render it unsuitable for the new hash standard. In particular,
both versions of Vortex have the undesirable property of impossible images, which
gives distinguishers for a HMAC based on Vortex and slightly speeds up preimage
search.},
}
</bibtex>

LUX

2009-03-03T15:25:22Z

Crechberger:

Cheetah

2009-03-03T15:22:34Z

Crechberger:

== The algorithm ==

* Author(s): Dmitry Khovratovich, Alex Biryukov, Ivica Nikolić
* Website: [http://cryptolux.org/Cheetah http://cryptolux.org/Cheetah]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Cheetah.zip Cheetah.zip]

<bibtex>
@misc{sha3KhovratovichBN08,
author = {Dmitry Khovratovich and Alex Biryukov and Ivica Nikolić},
title = {The Hash Function Cheetah: Speciﬁcation and Supporting Documentation},
url = {http://ehash.iaik.tugraz.at/uploads/c/ca/Cheetah.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
|-
| length-extension || hash || all || || - || - || [http://ehash.iaik.tugraz.at/uploads/d/d9/Cheetah_length-extension.txt Gligoroski]
|-
|}

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

<bibtex>
@misc{CheetahG08,
author = {Danilo Gligoroski},
title = {Cheetah hash function is not resistant against length-extension attack},
url = {http://ehash.iaik.tugraz.at/uploads/d/d9/Cheetah_length-extension.txt},
howpublished = {OFFICIAL COMMENT (local link)},
year = {2008},
}
</bibtex>

MD6

2009-03-03T15:16:29Z

Crechberger: 33 rounds of the MD6 permutation

== The algorithm ==

* Authors: Ron Rivest, Benjamin Agre, Daniel V. Bailey, Christopher Crutchfield, Yevgeniy Dodis, Kermin Elliott Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Drew Sutherland, Eran Tromer, Yiqun Lisa Yin
* Website: [http://groups.csail.mit.edu/cis/md6/ http://groups.csail.mit.edu/cis/md6/]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/MD6.zip MD6.zip]

<bibtex>
@misc{sha3Rivest08,
author = {Ronald L. Rivest},
title = {The MD6 hash function -- A proposal to NIST for SHA-3},
url = {http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.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
|-
| | non-randomness || reduced compression || || 18 rounds || ? || ? || [http://groups.csail.mit.edu/cis/md6/supmitted-2008-10-27/Supporting_Documentation/md6_report.pdf Aumasson,Meier]
|-
| | key-recovery || reduced compression || || 15 rounds || ? || ? || [http://groups.csail.mit.edu/cis/md6/supmitted-2008-10-27/Supporting_Documentation/md6_report.pdf Dinur,Shamir]
|-
| | non-randomness || reduced permutation|| || 30 rounds || ? || ? || [http://www.dagstuhl.de/Materials/index.en.phtml?09031#Khovratovich,Dimitry Khovratovich]
|-
| | non-randomness || reduced permutation|| || 33 rounds || ? || ? || [http://fse2009rump.cr.yp.to/fe1a0e11287a9864c1d897a3110ebaa2.pdf, Khovratovich]
|-
| | collision || reduced compression || || 16 rounds || 230 || - || [http://ehash.iaik.tugraz.at/uploads/9/91/Khazaei_md6.txt Khazaei,Meier]
|-
|}

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

<bibtex>
@misc{md6AM08,
author = {Jean-Philippe Aumasson and Willi Meier},
title = {Personal communication (nonrandomness on the reduced-round compression function)},
url = {http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf},
howpublished = {Reported in the supporting documentation},
year = {2008},
}
</bibtex>

<bibtex>
@misc{md6DS08,
author = {Itai Dinur and Adi Shamir},
title = {Personal communication (key recovery on the reduced-round compression function)},
url = {http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf},
howpublished = {Reported in the supporting documentation},
year = {2008},
}
</bibtex>

<bibtex>
@misc{md6K,
author = {Dimitry Khovratovich},
title = {Gaussian cryptanalysis of hash functions: collisions,
preimages, distinguishers},
url = {http://www.dagstuhl.de/Materials/index.en.phtml?09031#Khovratovich,%20Dimitry},
howpublished = {Available online, abstract only},
year = {2009},
abstract = {Many attacks on hash functions can be reformulated in finding a hash
execution with constraints being fixed values of internal variables. Those
variables can be input or output bits, input of active S-boxes or AND
operations, etc..

The constraints lead to a system of nonlinear equations, which sometimes
can be solved with a fast algorithm resembling the Gaussian elimination. If a
system has been solved then solutions can be produced with negligible time
costs.

The main condition for the algorithm to succeed is relatively slow diffusion in
the attacked primitive. Provided this we show how to attack AES as a hash
function and prove that a 30-round MD6 compression function can be
distinguished from the random oracle.

I will also show how it worked in practice in a GUI-tool.},
}
</bibtex>

<bibtex>
@misc{md6K2,
author = {Dimitry Khovratovich},
title = {Nonrandomness of the 33-round MD6},
url = {http://fse2009rump.cr.yp.to/fe1a0e11287a9864c1d897a3110ebaa2.pdf},
howpublished = {FSE 2009 rump session, slides only},
year = {2009},
}
</bibtex>

<bibtex>
@misc{cubehashA08,
author = {Shahram Khazaei and Willi Meier},
title = {Collisions for 16-round MD6},
url = {http://ehash.iaik.tugraz.at/uploads/9/91/Khazaei_md6.txt},
howpublished = {NIST mailing list (local link)},
year = {2009},
}
</bibtex>

The SHA-3 Zoo

2009-03-02T14:12:32Z

Crechberger: Collision and Preimage Attacks on Dynamic SHA

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 [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/submissions_rnd1.html submissions] have advanced to the first round.
So far, 10 out of 51 first round candidates have been officially conceded broken or withdrawn by the designers.

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]

{| 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"| Best Attack on Main NIST Requirements !! width="120"| Best Attack on other Hash Requirements
|-
| [[ARIRANG]] || Jongin Lim || ||
|-
| [[AURORA]] || Masahiro Fujita || ||
|-
| [[BLAKE]] || Jean-Philippe Aumasson || ||
|-
| [[Blender]] || Colin Bradbury || style="background:orange" | preimage ||
|-
| [[Blue Midnight Wish]] || Svein Johan Knapskog || ||
|-
| [[Cheetah]] || Dmitry Khovratovich || || length-extension
|-
| [[CHI]] || Phillip Hawkes || ||
|-
| [[CRUNCH]] || Jacques Patarin || || length-extension
|-
| [[CubeHash]] || Daniel J. Bernstein || style="background:greenyellow" | preimage ||
|-
| [[Dynamic SHA]] || Xu Zijie || style="background:orange"|collision || length-extension
|-
| [[Dynamic SHA2]] || Xu Zijie || || length-extension
|-
| [[ECHO]] || Henri Gilbert || ||
|-
| [[ECOH]] || Daniel R. L. Brown || ||
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || Danilo Gligoroski || style="background:yellow" | preimage ||
|-
| [[EnRUPT]] || Sean O’Neil || style="background:red" | collision ||
|-
| [[ESSENCE]] || Jason Worth Martin || ||
|-
| [[FSB (SHA-3 submission) | FSB]] || Matthieu Finiasz || ||
|-
| [[Fugue]] || Charanjit S. Jutla || ||
|-
| [[Groestl|Grøstl]] || Lars R. Knudsen || ||
|-
| [[Hamsi]] || Ozgul Kucuk || ||
|-
| [[JH]] || Hongjun Wu || style="background:greenyellow" | preimage ||
|-
| [[Keccak]] || The Keccak Team || ||
|-
| [[LANE]] || Sebastiaan Indesteege || ||
|-
| [[Lesamnta]] || Hirotaka Yoshida || ||
|-
| [[Luffa]] || Dai Watanabe || ||
|-
| [[LUX]] || Ivica Nikolic || ||
|-
| [[MCSSHA-3]] || Mikhail Maslennikov || style="background:orange" | collision ||
|-
| [[MD6]] || Ronald L. Rivest || ||
|-
| [[NaSHA]] || Smile Markovski || style="background:orange" | collision ||
|-
| [[SANDstorm]] || Rich Schroeppel || ||
|-
| [[Sarmal]] || Kerem Varici || style="background:yellow" | preimage ||
|-
| [[Sgàil]] || Peter Maxwell|| style="background:red" | collision ||
|-
| [[Shabal]] || Jean-Francois Misarsky || ||
|-
| [[SHAvite-3]] || Orr Dunkelman || ||
|-
| [[SIMD]] || Gaetan Leurent || ||
|-
| [[Skein]] || Bruce Schneier || ||
|-
| [[Spectral Hash]] || Cetin Kaya Koc || ||
|-
| [[SWIFFTX]] || Daniele Micciancio || ||
|-
| [[TIB3]] || Daniel Penazzi || style="background:yellow" | collision ||
|-
| [[Twister]] || Michael Gorski || style="background:yellow" | 2nd preimage ||
|-
| [[Vortex (SHA-3 submission)|Vortex]] || Michael Kounavis || style="background:yellow" | preimage ||
|}

The following hash functions have been submitted to the NIST competition but did not advance to the first round, or have been conceded broken or withdrawn by the designers:

{| 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="120" | Best Attack on Main NIST Requirements
|-
| [[Abacus]] || Neil Sholer || conceded broken || style="background:orange" | 2nd-preimage
|-
| [[Boole]] || Greg Rose || conceded broken || style="background:red" | collision
|-
| [[DCH]] || David A. Wilson || conceded broken || style="background:red" | collision
|-
| [[HASH 2X]] || Jason Lee || not in round 1 || style="background:red" | 2nd-preimage
|-
| [[Khichidi-1]] || M. Vidyasagar || conceded broken || style="background:red" | collision
|-
| [[Maraca]] || Robert J. Jenkins || not in round 1 || style="background:red" | preimage
|-
| [[MeshHash]] || Björn Fay || conceded broken || style="background:orange" | 2nd preimage
|-
| [[NKS2D]] || Geoffrey Park || not in round 1 || style="background:red" | collision
|-
| [[Ponic]] || Peter Schmidt-Nielsen || not in round 1 || style="background:yellow" | 2nd-preimage
|-
| [[SHAMATA]] || Orhun Kara || conceded broken || style="background:red" | collision
|-
| [[StreamHash]] || Michal Trojnara || conceded broken || style="background:red" | collision
|-
| [[Tangle]] || Rafael Alvarez || conceded broken || style="background:red" | collision
|-
| [[WaMM]] || John Washburn || conceded broken || style="background:red" | collision
|-
| [[Waterfall]] || Bob Hattersley || conceded broken || 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!

Dynamic SHA

2009-03-02T14:10:41Z

Crechberger: Collision and Preimage Attacks on Dynamic SHA

== The algorithm ==

* Author(s): Zijie Xu

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

<bibtex>
@misc{sha3Xu08,
author = {Zijie Xu},
title = {Dynamic SHA},
url = {http://ehash.iaik.tugraz.at/uploads/e/e2/DyamicSHA.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:orange" | collision|| hash || 256|| || 2114 || - || [http://ehash.iaik.tugraz.at/uploads/c/c2/Dsha.pdf Indesteege]
|-
| style="background:orange" | collision|| hash || 512|| || 2170 || - || [http://ehash.iaik.tugraz.at/uploads/c/c2/Dsha.pdf Indesteege]
|-
| preimage|| compression|| 256|| || 2216 || - || [http://ehash.iaik.tugraz.at/uploads/c/c2/Dsha.pdf Indesteege]
|-
| preimage|| compression|| 512|| || 2256 || - || [http://ehash.iaik.tugraz.at/uploads/c/c2/Dsha.pdf Indesteege]
|-
| length-extension || hash || all || || - || - || [http://ehash.iaik.tugraz.at/uploads/e/e7/Dynamic-sha_length-extension.txt Klima]
|-
|}

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

<bibtex>
@misc{DynamicSHAI09,
author = {Sebastiaan Indesteege},
title = {Cryptanalysis of Dynamic SHA},
url = {http://ehash.iaik.tugraz.at/uploads/c/c2/Dsha.pdf},
howpublished = {presentation slides available online (local link)},
year = {2008},
}
</bibtex>

<bibtex>
@misc{DynamicSHAK08,
author = {Vlastimil Klima},
title = {Dynamic SHA is vulnerable to generic attacks},
url = {http://ehash.iaik.tugraz.at/uploads/e/e7/Dynamic-sha_length-extension.txt},
howpublished = {OFFICIAL COMMENT (local link)},
year = {2008},
}
</bibtex>

File:Dsha.pdf

2009-03-02T14:08:07Z

Crechberger:

Edon-R (SHA-3 submission)

2009-02-11T07:51:23Z

Crechberger: added V. Klima as co-author

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

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

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

Maraca

2009-01-13T12:31:38Z

Crechberger:

== The algorithm ==

* Author(s): Robert J. Jenkins Jr.
* Website: [http://burtleburtle.net/bob/crypto/maraca/nist/ http://burtleburtle.net/bob/crypto/maraca/nist/]

<bibtex>
@misc{sha3Jenkins08,
author = {Robert J. Jenkins Jr.},
title = {Algorithm Specification},
url = {http://burtleburtle.net/bob/crypto/maraca/nist/Supporting_Documentation/specification.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" | collision || internal state || 512 || || 2237 || 2230.5 || [http://ehash.iaik.tugraz.at/uploads/5/52/Maraca.pdf Canteaut,Naya-Plasencia]
|-
| style="background:red" | preimage|| hash || 512 || || ? || ? || [http://homes.esat.kuleuven.be/~sindeste/maraca.html Indesteege]
|-
|}

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

<bibtex>
@misc{maracaCN08,
author = {Anne Canteaut and María Naya-Plasencia},
title = {Internal collision attack on Maraca},
url = {http://ehash.iaik.tugraz.at/uploads/5/52/Maraca.pdf},
howpublished = {Available online},
year = {2008},
abstract = {We present an internal collision attack against the new hash
function Maraca which has been submitted to the SHA-3 competition.
This attack requires 2^{237} calls to the round function and its complexity is
lower than the complexity of the generic collision attack when the length
of the message digest is greater than or equal to 512. The cryptanalysis
mainly exploits two features of Maraca: the fact that the message block
inserted at each round has the same size as the internal state, and some
particular differential properties of the inner permutation.},
}
</bibtex>

<bibtex>
@misc{maracaI09,
author = {Sebastiaan Indesteege},
title = {Practical Preimages for Maraca},
url = {http://homes.esat.kuleuven.be/~sindeste/maraca.html},
howpublished = {Available online},
year = {2009},
abstract = {We show a practical (seconds on a PC) preimage attack on the hash function Maraca.},
}
</bibtex>

Maraca

2009-01-11T14:18:56Z

Crechberger:

== The algorithm ==

* Author(s): Robert J. Jenkins Jr.
* Website: [http://burtleburtle.net/bob/crypto/maraca/nist/ http://burtleburtle.net/bob/crypto/maraca/nist/]

<bibtex>
@misc{sha3Jenkins08,
author = {Robert J. Jenkins Jr.},
title = {Algorithm Specification},
url = {http://burtleburtle.net/bob/crypto/maraca/nist/Supporting_Documentation/specification.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" | collision || internal state || 512 || || 2237 || 2230.5 || [http://ehash.iaik.tugraz.at/uploads/5/52/Maraca.pdf Canteaut,Naya-Plasencia]
|-
| style="background:orange" | preimage|| hash || 512 || || ? || ? || [http://www.dagstuhl.de/Materials/index.en.phtml?09031#Indesteege,%20Sebastiaan Indesteege]
|-
|}

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

<bibtex>
@misc{maracaCN08,
author = {Anne Canteaut and María Naya-Plasencia},
title = {Internal collision attack on Maraca},
url = {http://ehash.iaik.tugraz.at/uploads/5/52/Maraca.pdf},
howpublished = {Available online},
year = {2008},
abstract = {We present an internal collision attack against the new hash
function Maraca which has been submitted to the SHA-3 competition.
This attack requires 2^{237} calls to the round function and its complexity is
lower than the complexity of the generic collision attack when the length
of the message digest is greater than or equal to 512. The cryptanalysis
mainly exploits two features of Maraca: the fact that the message block
inserted at each round has the same size as the internal state, and some
particular differential properties of the inner permutation.},
}
</bibtex>

<bibtex>
@misc{maracaI09,
author = {Sebastiaan Indesteege},
title = {Practical Preimages for Maraca},
url = {http://www.dagstuhl.de/Materials/index.en.phtml?09031#Indesteege,%20Sebastiaan},
howpublished = {Available online, abstract only},
year = {2009},
abstract = {We show a practical (seconds on a PC) preimage attack on the hash function Maraca.},
}
</bibtex>

MD6

2009-01-11T11:43:15Z

Crechberger: added new distinguisher

== The algorithm ==

* Authors: Ron Rivest, Benjamin Agre, Daniel V. Bailey, Christopher Crutchfield, Yevgeniy Dodis, Kermin Elliott Fleming, Asif Khan, Jayant Krishnamurthy, Yuncheng Lin, Leo Reyzin, Emily Shen, Jim Sukha, Drew Sutherland, Eran Tromer, Yiqun Lisa Yin
* Website: [http://groups.csail.mit.edu/cis/md6/ http://groups.csail.mit.edu/cis/md6/]
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/MD6.zip MD6.zip]

<bibtex>
@misc{sha3Rivest08,
author = {Ronald L. Rivest},
title = {The MD6 hash function -- A proposal to NIST for SHA-3},
url = {http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.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
|-
| | non-randomness || reduced compression || || 30 rounds || ? || ? || [http://www.dagstuhl.de/Materials/index.en.phtml?09031#Khovratovich,%20Dimitry Khovratovich]
|-
| | non-randomness || reduced compression || || 18 rounds || ? || ? || [http://groups.csail.mit.edu/cis/md6/supmitted-2008-10-27/Supporting_Documentation/md6_report.pdf Aumasson,Meier]
|-
| | key-recovery || reduced compression || || 15 rounds || ? || ? || [http://groups.csail.mit.edu/cis/md6/supmitted-2008-10-27/Supporting_Documentation/md6_report.pdf Dinur,Shamir]
|-
|}

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

<bibtex>
@misc{md6AM08,
author = {Jean-Philippe Aumasson and Willi Meier},
title = {Personal communication (nonrandomness on the reduced-round compression function)},
url = {http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf},
howpublished = {Reported in the supporting documentation},
year = {2008},
}
</bibtex>

<bibtex>
@misc{md6DS08,
author = {Itai Dinur and Adi Shamir},
title = {Personal communication (key recovery on the reduced-round compression function)},
url = {http://groups.csail.mit.edu/cis/md6/submitted-2008-10-27/Supporting_Documentation/md6_report.pdf},
howpublished = {Reported in the supporting documentation},
year = {2008},
}
</bibtex>

<bibtex>
@misc{md6K,
author = {Dimitry Khovratovich},
title = {Gaussian cryptanalysis of hash functions: collisions,
preimages, distinguishers},
url = {http://www.dagstuhl.de/Materials/index.en.phtml?09031#Khovratovich,%20Dimitry},
howpublished = {Available online, abstract only},
year = {2009},
abstract = {Many attacks on hash functions can be reformulated in finding a hash
execution with constraints being fixed values of internal variables. Those
variables can be input or output bits, input of active S-boxes or AND
operations, etc..

The constraints lead to a system of nonlinear equations, which sometimes
can be solved with a fast algorithm resembling the Gaussian elimination. If a
system has been solved then solutions can be produced with negligible time
costs.

The main condition for the algorithm to succeed is relatively slow diffusion in
the attacked primitive. Provided this we show how to attack AES as a hash
function and prove that a 30-round MD6 compression function can be
distinguished from the random oracle.

I will also show how it worked in practice in a GUI-tool.},
}
</bibtex>

Maraca

2009-01-11T11:22:44Z

Crechberger: new preimage attack

== The algorithm ==

* Author(s): Robert J. Jenkins Jr.
* Website: [http://burtleburtle.net/bob/crypto/maraca/nist/ http://burtleburtle.net/bob/crypto/maraca/nist/]

<bibtex>
@misc{sha3Jenkins08,
author = {Robert J. Jenkins Jr.},
title = {Algorithm Specification},
url = {http://burtleburtle.net/bob/crypto/maraca/nist/Supporting_Documentation/specification.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" | collision || internal state || 512 || || 2237 || 2230.5 || [http://ehash.iaik.tugraz.at/uploads/5/52/Maraca.pdf Canteaut,Naya-Plasencia]
|-
| style="background:red" | preimage|| hash || 512 || || ? || ? || [http://www.dagstuhl.de/Materials/index.en.phtml?09031#Indesteege,%20Sebastiaan Indesteege]
|-
|}

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

<bibtex>
@misc{maracaCN08,
author = {Anne Canteaut and María Naya-Plasencia},
title = {Internal collision attack on Maraca},
url = {http://ehash.iaik.tugraz.at/uploads/5/52/Maraca.pdf},
howpublished = {Available online},
year = {2008},
abstract = {We present an internal collision attack against the new hash
function Maraca which has been submitted to the SHA-3 competition.
This attack requires 2^{237} calls to the round function and its complexity is
lower than the complexity of the generic collision attack when the length
of the message digest is greater than or equal to 512. The cryptanalysis
mainly exploits two features of Maraca: the fact that the message block
inserted at each round has the same size as the internal state, and some
particular differential properties of the inner permutation.},
}
</bibtex>

<bibtex>
@misc{maracaI09,
author = {Sebastiaan Indesteege},
title = {Practical Preimages for Maraca},
url = {http://www.dagstuhl.de/Materials/index.en.phtml?09031#Indesteege,%20Sebastiaan},
howpublished = {Available online, abstract only},
year = {2009},
abstract = {We show a practical (seconds on a PC) preimage attack on the hash functin Maraca.},
}
</bibtex>

Cryptanalysis Categories

2008-12-30T13:43:42Z

Crechberger:

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 || align="left" | The time*memory product is below generic attacks 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 attack on collision, 2nd-preimage and preimage resistant 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. 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.
|-
|}

Twister

2008-12-30T13:41:51Z

Crechberger:

== The algorithm ==

* Author(s): Ewan Fleischmann, Christian Forler and Michael Gorski
* Website: http://www.twister-hash.com
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Twister.zip Twister.zip]

<bibtex>
@misc{sha3FleischmannFG08,
author = {Ewan Fleischmann, Christian Forler and Michael Gorski},
title = {The Twister Hash Function Family},
url = {http://ehash.iaik.tugraz.at/uploads/3/39/Twister.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 || || 226.5 || 228 || [http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf Mendel,Rechberger,Schläffer]
|-
| style="background:greenyellow" | collision || hash || 512 || || 2252 || - || [http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf Mendel,Rechberger,Schläffer]
|-
| style="background:yellow" | 2nd preimage || hash || 512 || || 2448 || 264 || [http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf Mendel,Rechberger,Schläffer]
|-
|}

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

<bibtex>
@misc{twisterMRS08,
author = {Florian Mendel and Christian Rechberger and Martin Schläffer},
title = {Cryptanalysis of Twister},
url = {http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf},
howpublished = {Available online},
year = {2008},
abstract = {In this paper, we present a pseudo-collision attack on the compression function of all
Twister variants (224,256,384,512) with complexity of about 2^26.5 compression function evalua-
tions. We show how the compression function attack can be extended to construct collisions for
Twister-512 slightly faster than brute force search. Furthermore, we present a second-preimage at-
tack for Twister-512 with complexity of about 2^448 compression function evaluations and memory
requirement of 2^64.
}
</bibtex>