The ECRYPT Hash Function Website - User contributions [en]

Groestl

2011-08-31T09:43:37Z

GVanAssche:

== The algorithm ==

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

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

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

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

== Cryptanalysis ==

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

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

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

=== Hash function ===

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

{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements || Reference
|-
| collision || 224,256 || 3 rounds || 264 || - || [http://groestl.info/groestl-analysis.pdf Schläffer]
|-
| collision || 512 || 3 rounds || 2192 || - || [http://groestl.info/groestl-analysis.pdf Schläffer]
|-
|}

=== Building blocks ===

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

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

{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference
|-
| distinguisher || permutation || 256 || 10 rounds || 2509 || || [http://fse2011.mat.dtu.dk/slides/Higher-order%20differential%20properties%20of%20Keccak%20and%20Luffa.pdf Boura,Canteaut,DeCannière]
|-
| semi-free-start collision || compression function || 256 || 6 rounds || 2112 || 264 || [http://groestl.info/groestl-analysis.pdf Schläffer]
|-
| semi-free-start collision || compression function || 384,512 || 6 rounds || 2180 || 264 || [http://groestl.info/groestl-analysis.pdf Schläffer]
|-
| collision || hash function || 224,256 || 5 rounds (Round 1/2) || 248 || 232 || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| collision || hash function || 256 || 6 rounds (Round 1/2) || 2112 || 232 || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| collision || hash function || 224,256 || 4 rounds (Round 1/2) || 264 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| collision || hash function || 224,256 || 3 rounds (Round 1/2) || 264 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| collision || hash function || 384,512 || 5 rounds (Round 1/2) || 2176 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| collision || hash function || 384,512 || 4 rounds (Round 1/2) || 264 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| distinguisher || compression function || 256 || 10 rounds (Round 1/2) || 2175 || 264 || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
|-
| distinguisher || compression function || 512 || 11 rounds (Round 1/2) || 2630 || 264 || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
|-
| distinguisher || permutation || 256 || 8 rounds || 248 || 28 || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf Sasaki,Li,Wang,Sakiyama,Ohta]
|-
| semi-free-start collision || compression function || 512 || 7 rounds || 2152 || 256 || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf Sasaki,Li,Wang,Sakiyama,Ohta]
|-
| semi-free-start collision || compression function || 224,256 || 7 rounds (Round 1/2) || 280 || 232 || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| semi-free-start collision || compression function || 224,256 || 8 rounds (Round 1/2) || 2192 || 264 || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| distinguisher || permutation || 224,256 || 7 rounds || 219 || - || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| distinguisher || permutation || 224,256 || 8 rounds || 264 || 264 || [http://eprint.iacr.org/2010/375.pdf Ideguchi,Tischhauser,Preneel]
|-
| distinguisher || compression function || 256 || 10 rounds (Round 1/2) || 2192 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| distinguisher || compression function || 256 || 9 rounds (Round 1/2) || 280 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| distinguisher || compression function || 512 || 11 rounds (Round 1/2) || 2640 || 264 || [http://eprint.iacr.org/2010/223.pdf Peyrin]
|-
| semi-free-start collision || compression function || 256 || 7 rounds (Round 1/2) || 2120 || 264 || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
|-
| distinguisher || compression function || 256 || 8 rounds (Round 1/2) || 2112 || 264 || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
|-
| distinguisher || permutation || 256 || 8 rounds || 2112 || 264 || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
|-
| semi-free-start collision || compression function || 256 || 7 rounds (Round 1/2) || 2120 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| semi-free-start collision || compression function|| 384,512 || 7 rounds (Round 1/2) || 2152 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
|-
| semi-free-start collision || compression function || 224,256 || 6 rounds (Round 1/2) || 264 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
|-
| distinguisher || output transformation || 224,256 || 7 rounds || 256 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
|-
| distinguisher || permutation || 224,256 || 7 rounds || 255 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
|-
| semi-free-start collision || compression function || 256 || 6 rounds (Round 1/2) || 2120 || 264 || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
|-
| semi-free-start collision || compression function || 224,256 || 5 rounds (Round 1/2) || 264 || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
|-
| observation || hash || all || || || || [http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf Kelsey]
|-
| observation || block cipher || all || || || || [http://www.larc.usp.br/~pbarreto/Grizzly.pdf Barreto]
|-
| free-start collision || compression function || all || any || 22n/3 || 22n/3 || [http://www.groestl.info/Groestl.pdf submission document]
|-
| pseudo-preimage || compression function || all || any || 2n || - || [http://www.groestl.info/Groestl.pdf submission document]
|-
|}

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

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

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

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

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

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

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

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

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

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

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

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

Shabal

2010-03-31T10:06:07Z

GVanAssche: Added the rotational 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].

=== Hash function ===

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

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

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

=== Building blocks ===

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

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

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

{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash 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]
|-
|}
(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>

Keccak

2010-01-20T10:15:39Z

GVanAssche:

== The algorithm ==

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

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

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

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

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

== Cryptanalysis ==

{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements || Reference
|-
| observations || permutation || all || || || || [http://131002.net/data/papers/AK09.pdf Aumasson,Khovratovich]
|-
| cube attack || partial preimage || 224 || 4 rounds || 219 || ? || [http://www.cs.rit.edu/~jal6806/thesis/thesis.pdf Joel,Lathrop]
|-
| distinguisher(1) || permutation || all || 16 rounds || 21023.88 || || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
|-
| distinguisher(1) || permutation || all || 18 rounds || 21370 || || [http://www-roc.inria.fr/secret/Anne.Canteaut/Publications/zero_sum.pdf Boura,Canteaut]
|-
|}

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

(1)The Keccak team commented on these distinguishers and provide generic constructions in [http://keccak.noekeon.org/NoteZeroSum.pdf this note].

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

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

<bibtex>
@misc{keccakAM09,
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{keccakBC10,
author = {Christina Boura and Anne Canteaut},
title = {A Zero-Sum property for the Keccak-f Permutation with 18 Rounds},
url = {http://www-roc.inria.fr/secret/Anne.Canteaut/Publications/zero_sum.pdf},
howpublished = {NIST mailing list}
year = {2010},
abstract = {A new type of distinguishing property, named the zero-sum property
has been recently presented by Aumasson and Meier [1]. It has
been applied to the inner permutation of the hash function Keccak
and it has led to a distinguishing property for the Keccak-f permutation
up to 16 rounds, out of 24 in total. Here, we additionally exploit
some spectral properties of the Keccak-f permutation and we improve
the previously known upper bounds on the degree of the inverse
permutation after a certain number of rounds. This result enables us
to extend the zero-sum property to 18 rounds of the Keccak-f permutation,
which was the number of rounds in the previous version of
Keccak submitted to the SHA-3 competition..},
</bibtex>

<bibtex>
@misc{KeccakNoteZeroSum,
author = {G. Bertoni and J. Daemen and M. Peeters and G. Van Assche},
title = {Note on zero-sum distinguishers of Keccak-f},
url = {http://keccak.noekeon.org/NoteZeroSum.pdf},
howpublished = {NIST mailing list},
year = {2010},
}
</bibtex>

Keccak

2009-05-04T08:02:37Z

GVanAssche: Updated main document entry now refers to version 1.2

Keccak

2009-02-23T09:40:08Z

GVanAssche: Added updated main document

Talk:The SHA-3 Zoo

2008-12-12T15:04:01Z

GVanAssche:

I'm thinking about introducing another column to the list of submissions to provide a rough, overall classification of the candidates (e.g. classical Merkle-Damgaard vs. HAIFA vs. sponge vs. tree-based vs. streaming vs. ...), motivated by private messages I've got comparing the current SHA-3 Zoo with my old hash lounge.

However, finding the most appropriate category for some submissions may be a tough task; paradigms may be so distorted as to be nearly unrecognizable. Still, other candidates exhibit a much more transparent structure, and I think this information may be useful (e.g. comparing submissions that fall on distinct categories may not be as fair as comparing functions that share a high-level structure).

Would such a modification be welcome to the SHA-3 Zoo contributors?

Paulo.

I think this would be a lot of effort for a relatively minor added value; as you observe, many candidates are likely to use "uncategorizable" modes of operations. How one would classify CubeHash? It has similarities with a sponge constructions, but is not a sponge in general. Also, both MD6 and ESSENCE have a tree construction, but with different arities, parameters, etc. Finding the best tradeoff precision/readability seems difficult...

JP

Well, I don't see it as too much effort -- for me at any rate; I'm not asking that somebody else do the hard work ☺. Rather, I think it's part of trying to understand how each submission works, and it could also suggest lines of attack (particularly where the actual functions deviate from previously analyzed constructions). Besides, in cases where the authors disagree of a tentative category it might shed new light on those authors' original intent.

Paulo.

Addendum: as far as I could tell, the overall structure of the currently known proposals seems to be the following (disclaimer: I may be completely mistaken in many cases): 

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable"
|- style="background:#efefef;"
! width="150"| Hash Function Name !! width="150"| Status !! width="150"| [[External Cryptanalysis Categories| External Cryptanalysis]]!! width="150"| Tentative Classification
|-
| [[Abacus]] || submitted || none || ? [?]
|-
| [[ARIRANG]] || submitted || none || ? [?]
|-
| [[AURORA]] || submitted || none || ? [?]
|-
| [[BLAKE]] || submitted || none || HAIFA/? [narrow pipe]
|-
| [[Blender]] || submitted || none || ? [?]
|-
| [[Blue Midnight Wish]] || submitted || yes || sponge? [wide pipe]
|-
| <s>[[Boole]]</s> || submitted || ☠|| streaming
|-
| [[Cheetah]] || submitted || none || ? [?]
|-
| [[CHI]] || submitted || none || Merkle-Damgård/Davies-Meyer [wide pipe]
|-
| [[CRUNCH]] || submitted || none || Merkle-Damgård/concatenate-permute-truncate [narrow pipe]
|-
| [[CubeHash]] || submitted || yes || sponge [wide pipe]
|-
| <s>[[DCH]]</s> || submitted || ☠|| Merkle-Damgård/Miyaguchi-Preneel [narrow pipe]
|-
| [[Dynamic SHA]] || submitted || none || ? [?]
|-
| [[Dynamic SHA2]] || submitted || none || ? [?]
|-
| [[ECHO]] || submitted || none || ? [?]
|-
| [[ECOH]] || submitted || none || ? [?]
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || submitted || yes || streaming
|-
| <s>[[EnRUPT]]</s> || submitted || ☠|| streaming
|-
| [[ESSENCE]] || submitted || none || Merkle tree [narrow pipe]
|-
| [[FSB (SHA-3 submission) | FSB]] || submitted || none || Merkle-Damgård/concatenate-permute-truncate [wide pipe]
|-
| [[Fugue]] || submitted || none || sponge? [wide pipe]
|-
| [[Groestl|Grøstl]] || submitted || yes || sponge? Merkle-Damgård/Davies-Meyer? [wide pipe]
|-
| [[Hamsi]] || submitted || none || ? [?]
|-
| <s>[[HASH 2X]]</s> || submitted || ☠|| streaming?
|-
| [[JH]] || submitted || none || sponge [wide pipe]
|-
| [[Keccak]] || submitted || none || sponge [wide pipe]
|-
| [[Khichidi-1]] || submitted || none || ? [?]
|-
| [[LANE]] || submitted || none || HAIFA/concatenate-permute-truncate or Damgård interleaving [narrow pipe]
|-
| [[Lesamnta]] || submitted || none || ? [?]
|-
| [[Luffa]] || submitted || none || ? [?]
|-
| [[LUX]] || submitted || none || ? [?]
|-
| [[Maraca]] || submitted || none || sponge? [wide pipe]
|-
| <s>[[MCSSHA-3]]</s> || submitted || ☠|| streaming
|-
| [[MD6]] || submitted || yes || bounded-height Merkle tree [wide pipe]
|-
| [[MeshHash]] || submitted || none || ? [?]
|-
| [[NaSHA]] || submitted || none || sponge? [narrow pipe]
|-
| [[SANDstorm]] || submitted || none || ? [?]
|-
| <s>[[NKS2D]]</s> || submitted || ☠|| cellular automaton
|-
| [[Ponic]] || submitted || yes || streaming
|-
| [[Sarmal]] || submitted || yes || HAIFA/Davies-Meyer [narrow pipe]
|-
| <s>[[Sgàil]]</s> || submitted || ☠|| Merkle-Damgård/Davies-Meyer [wide pipe]
|-
| [[Shabal]] || submitted || none || ? [?]
|-
| [[SHAMATA]] || submitted || none || sponge [wide pipe]
|-
| [[SHAvite-3]] || submitted || none || ? [?]
|-
| [[SIMD]] || submitted || none || ? [?]
|-
| [[Skein]] || submitted || none || Merkle-Damgård/UBI? Merkle tree? [narrow pipe]
|-
| [[Spectral Hash]] || submitted || yes || Merkle-Damgård/prism? [narrow pipe]
|-
| [[SWIFFTX]] || submitted || none || HAIFA/concatenate-permute-truncate [wide pipe]
|-
| [[Tangle]] || submitted || none || ? [?]
|-
| [[TIB3]] || submitted || none || ? [?]
|-
| [[Twister]] || submitted || none || ? [?]
|-
| [[Vortex (SHA-3 submission)|Vortex]] || submitted || yes || Merkle-Damgård/Vortex-block? [wide pipe]
|-
| <s>[[WaMM]]</s> || submitted || ☠|| sponge [wide pipe]
|-
| [[Waterfall]] || submitted || none || streaming
|}

I'm in favour of adding more infos to this page. Seems like a good first shot. But surely we have to put a disclaimer to this category saying something like "this column can never we entirely correct as we would need almost 64 categories...".

Regarding your current categorization. Why not distinguish designs that are based on a small number of permutations from designs based on a huge number of permutations (e.g. block-cipher based). This seems a crucial difference to me.
On the other hand, do we really want to distinguish HAIFA from Merkle-Damgaard? The former is an extension of the later.
Also, what is your way to distinguish between sponge and streaming?

-Christian

Oh, I'm definitely thinking about adding a disclaimer. Regarding HAIFA vs. MD, I wrote HAIFA when the authors explicitly state so in the documentation. I tend to call "sponge" a construction that inserts a message in "blocks" (related to the abstract design) in a "simple" way (e.g. via some block-oriented group operation), and "stream" a construction oriented toward "words" (related to popular target platforms) mixed into the state through a "complicated" operation (I admit this is rather informal to say the least); also, I again adhere to the authors' statement when they claim a design is streaming. As for permutations vs. block ciphers, I've been thinking about this... but perhaps it's better to discuss the subject privately before, so I can check my own understanding of a few concepts. And of course I'm entirely open to revising a classification if there is evidence of a mistaken prior assessment.

Paulo.

We can follow Orr and say that "everything is HAIFA" ;)

More seriously: more info would of course be valuable, but accurate information seems in this case difficult (and maybe impossible) to provide. All the functions are based on a compression function (whatever the designers say to sound original), then the variations are: how the iteration is performed? (linear or tree), how large is the state?, how many rounds are recommended and how many are broken? (it would be interesting to give this ratio, but often there's more than the "round" parameter, see eg CubeHash), are there additional inputs? (salt, key, counter, etc.).

The iteration mode seems to be linear in most of the submissions, so providing this info may not be that useful. However it could be interesting and easy to add a column "state bitsize". If we want to say how many rounds are broken, we'll reduce to the same problem as we have with the "external cryptanalysis" column with "what is broken".

JP

I just wish to say that the terminology about ''sponge'' sometimes seems to spread across things that are not sponge functions according to the definition in our paper [http://sponge.noekeon.org Sponge Functions]. I have not checked all the entries marked "sponge" in the table above, but I have some doubts about whether these hash functions actually use the sponge construction. For instance, I checked JH and it does not seem they use the sponge construction. Instead, they use MD and a compression function (built on top of a permutation). Also, RadioGatún seems to be sometimes described as a sponge function, when it is not, see [http://radiogatun.noekeon.org/index.html#notasponge].

Gilles

Talk:The SHA-3 Zoo

2008-12-12T13:18:42Z

GVanAssche:

I'm thinking about introducing another column to the list of submissions to provide a rough, overall classification of the candidates (e.g. classical Merkle-Damgaard vs. HAIFA vs. sponge vs. tree-based vs. streaming vs. ...), motivated by private messages I've got comparing the current SHA-3 Zoo with my old hash lounge.

However, finding the most appropriate category for some submissions may be a tough task; paradigms may be so distorted as to be nearly unrecognizable. Still, other candidates exhibit a much more transparent structure, and I think this information may be useful (e.g. comparing submissions that fall on distinct categories may not be as fair as comparing functions that share a high-level structure).

Would such a modification be welcome to the SHA-3 Zoo contributors?

Paulo.

I think this would be a lot of effort for a relatively minor added value; as you observe, many candidates are likely to use "uncategorizable" modes of operations. How one would classify CubeHash? It has similarities with a sponge constructions, but is not a sponge in general. Also, both MD6 and ESSENCE have a tree construction, but with different arities, parameters, etc. Finding the best tradeoff precision/readability seems difficult...

JP

Well, I don't see it as too much effort -- for me at any rate; I'm not asking that somebody else do the hard work ☺. Rather, I think it's part of trying to understand how each submission works, and it could also suggest lines of attack (particularly where the actual functions deviate from previously analyzed constructions). Besides, in cases where the authors disagree of a tentative category it might shed new light on those authors' original intent.

Paulo.

Addendum: as far as I could tell, the overall structure of the currently known proposals seems to be the following (disclaimer: I may be completely mistaken in many cases): 

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable"
|- style="background:#efefef;"
! width="150"| Hash Function Name !! width="150"| Status !! width="150"| [[External Cryptanalysis Categories| External Cryptanalysis]]!! width="150"| Tentative Classification
|-
| [[Abacus]] || submitted || none || ? [?]
|-
| [[ARIRANG]] || submitted || none || ? [?]
|-
| [[AURORA]] || submitted || none || ? [?]
|-
| [[BLAKE]] || submitted || none || HAIFA/? [narrow pipe]
|-
| [[Blender]] || submitted || none || ? [?]
|-
| [[Blue Midnight Wish]] || submitted || yes || sponge? [wide pipe]
|-
| <s>[[Boole]]</s> || submitted || ☠|| streaming
|-
| [[Cheetah]] || submitted || none || ? [?]
|-
| [[CHI]] || submitted || none || Merkle-Damgård/Davies-Meyer [wide pipe]
|-
| [[CRUNCH]] || submitted || none || Merkle-Damgård/concatenate-permute-truncate [narrow pipe]
|-
| [[CubeHash]] || submitted || yes || sponge [wide pipe]
|-
| <s>[[DCH]]</s> || submitted || ☠|| Merkle-Damgård/Miyaguchi-Preneel [narrow pipe]
|-
| [[Dynamic SHA]] || submitted || none || ? [?]
|-
| [[Dynamic SHA2]] || submitted || none || ? [?]
|-
| [[ECHO]] || submitted || none || ? [?]
|-
| [[ECOH]] || submitted || none || ? [?]
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || submitted || yes || streaming
|-
| <s>[[EnRUPT]]</s> || submitted || ☠|| streaming
|-
| [[ESSENCE]] || submitted || none || Merkle tree [narrow pipe]
|-
| [[FSB (SHA-3 submission) | FSB]] || submitted || none || Merkle-Damgård/concatenate-permute-truncate [wide pipe]
|-
| [[Fugue]] || submitted || none || sponge? [wide pipe]
|-
| [[Groestl|Grøstl]] || submitted || yes || sponge? Merkle-Damgård/Davies-Meyer? [wide pipe]
|-
| [[Hamsi]] || submitted || none || ? [?]
|-
| <s>[[HASH 2X]]</s> || submitted || ☠|| streaming?
|-
| [[JH]] || submitted || none || sponge [wide pipe]
|-
| [[Keccak]] || submitted || none || sponge [wide pipe]
|-
| [[Khichidi-1]] || submitted || none || ? [?]
|-
| [[LANE]] || submitted || none || HAIFA/concatenate-permute-truncate or Damgård interleaving [narrow pipe]
|-
| [[Lesamnta]] || submitted || none || ? [?]
|-
| [[Luffa]] || submitted || none || ? [?]
|-
| [[LUX]] || submitted || none || ? [?]
|-
| [[Maraca]] || submitted || none || sponge? [wide pipe]
|-
| <s>[[MCSSHA-3]]</s> || submitted || ☠|| streaming
|-
| [[MD6]] || submitted || yes || bounded-height Merkle tree [wide pipe]
|-
| [[MeshHash]] || submitted || none || ? [?]
|-
| [[NaSHA]] || submitted || none || sponge? [narrow pipe]
|-
| [[SANDstorm]] || submitted || none || ? [?]
|-
| <s>[[NKS2D]]</s> || submitted || ☠|| cellular automaton
|-
| [[Ponic]] || submitted || yes || streaming
|-
| [[Sarmal]] || submitted || yes || HAIFA/Davies-Meyer [narrow pipe]
|-
| <s>[[Sgàil]]</s> || submitted || ☠|| Merkle-Damgård/Davies-Meyer [wide pipe]
|-
| [[Shabal]] || submitted || none || ? [?]
|-
| [[SHAMATA]] || submitted || none || sponge [wide pipe]
|-
| [[SHAvite-3]] || submitted || none || ? [?]
|-
| [[SIMD]] || submitted || none || ? [?]
|-
| [[Skein]] || submitted || none || Merkle-Damgård/UBI? Merkle tree? [narrow pipe]
|-
| [[Spectral Hash]] || submitted || yes || Merkle-Damgård/prism? [narrow pipe]
|-
| [[SWIFFTX]] || submitted || none || HAIFA/concatenate-permute-truncate [wide pipe]
|-
| [[Tangle]] || submitted || none || ? [?]
|-
| [[TIB3]] || submitted || none || ? [?]
|-
| [[Twister]] || submitted || none || ? [?]
|-
| [[Vortex (SHA-3 submission)|Vortex]] || submitted || yes || Merkle-Damgård/Vortex-block? [wide pipe]
|-
| <s>[[WaMM]]</s> || submitted || ☠|| sponge [wide pipe]
|-
| [[Waterfall]] || submitted || none || streaming
|}

I'm in favour of adding more infos to this page. Seems like a good first shot. But surely we have to put a disclaimer to this category saying something like "this column can never we entirely correct as we would need almost 64 categories...".

Regarding your current categorization. Why not distinguish designs that are based on a small number of permutations from designs based on a huge number of permutations (e.g. block-cipher based). This seems a crucial difference to me.
On the other hand, do we really want to distinguish HAIFA from Merkle-Damgaard? The former is an extension of the later.
Also, what is your way to distinguish between sponge and streaming?

-Christian

Oh, I'm definitely thinking about adding a disclaimer. Regarding HAIFA vs. MD, I wrote HAIFA when the authors explicitly state so in the documentation. I tend to call "sponge" a construction that inserts a message in "blocks" (related to the abstract design) in a "simple" way (e.g. via some block-oriented group operation), and "stream" a construction oriented toward "words" (related to popular target platforms) mixed into the state through a "complicated" operation (I admit this is rather informal to say the least); also, I again adhere to the authors' statement when they claim a design is streaming. As for permutations vs. block ciphers, I've been thinking about this... but perhaps it's better to discuss the subject privately before, so I can check my own understanding of a few concepts. And of course I'm entirely open to revising a classification if there is evidence of a mistaken prior assessment.

Paulo.

We can follow Orr and say that "everything is HAIFA" ;)

More seriously: more info would of course be valuable, but accurate information seems in this case difficult (and maybe impossible) to provide. All the functions are based on a compression function (whatever the designers say to sound original), then the variations are: how the iteration is performed? (linear or tree), how large is the state?, how many rounds are recommended and how many are broken? (it would be interesting to give this ratio, but often there's more than the "round" parameter, see eg CubeHash), are there additional inputs? (salt, key, counter, etc.).

The iteration mode seems to be linear in most of the submissions, so providing this info may not be that useful. However it could be interesting and easy to add a column "state bitsize". If we want to say how many rounds are broken, we'll reduce to the same problem as we have with the "external cryptanalysis" column with "what is broken".

JP

I just wish to say that the terminology about ''sponge'' sometimes seems to spread across things that are not sponge functions according to the definition in our paper [http://sponge.noekeon.org Sponge Functions]. I have not checked all the entries marked "sponge" in the table above, but I have some doubts about whether these hash functions actually use the sponge construction. For instance, I checked JH and it does not seem they use the sponge construction. Instead, they use a compression function (built on top of a permutation). Also, RadioGatún seems to be sometimes described as a sponge function, when it is not, see [http://radiogatun.noekeon.org/index.html#notasponge].

Gilles