Talk:The SHA-3 Zoo

From The ECRYPT Hash Function Website
Revision as of 22:55, 19 November 2008 by Crechberger (talk | contribs)

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?


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


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.


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

Hash Function Name Status External Cryptanalysis Tentative Classification
BLAKE submitted none HAIFA/?
Blue Midnight Wish submitted none sponge
Boole submitted yes streaming
CHI submitted none Merkle-Damgaard/Davies-Meyer
CRUNCH submitted none sponge?
CubeHash submitted yes sponge
Edon-R submitted yes sponge?
EnRUPT submitted broken streaming
ESSENCE submitted none Merkle tree
FSB submitted none sponge?
Fugue submitted none sponge?
Grøstl submitted none sponge
HASH 2X submitted broken streaming?
Keccak submitted none sponge
Maraca submitted none sponge?
MCSSHA-3 submitted broken streaming
MD6 submitted yes Merkle tree
NaSHA submitted none sponge?
NKS2D submitted broken cellular automaton
Ponic submitted none streaming
Sarmal submitted none HAIFA/Davies-Meyer
Sgàil submitted broken Merkle-Damgaard/Davies-Meyer
SHAMATA submitted none sponge
Skein submitted none Merkle-Damgaard/UBI?
Spectral Hash submitted yes Merkle-Damgaard/prism?
Vortex submitted yes Merkle-Damgaard/Vortex-block?
WaMM submitted broken sponge
Waterfall submitted none streaming

I'm in favour of adding more infos to this page. Seems like a good first shot. But sureley 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 distingush HAIFA from Merkle-Damgaard? The former is mereley an extension of the later. If we distinguish at this level of detail, I'm afraid we end up with many categories... Also, what is the difference between sponge and streaming?