Talk:The SHA-3 Zoo

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

Hash Function Name	Status	External Cryptanalysis	Tentative Classification
BLAKE	submitted	none	HAIFA/? [narrow pipe]
Blue Midnight Wish	submitted	none	sponge? [wide pipe]
Boole	submitted	☠	streaming
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]
DCH	submitted	☠	Merkle-Damgård/Miyaguchi-Preneel [narrow pipe]
Edon-R	submitted	yes	streaming
EnRUPT	submitted	☠	streaming
ESSENCE	submitted	none	Merkle tree [narrow pipe]
FSB	submitted	none	Merkle-Damgård/concatenate-permute-truncate [wide pipe]
Fugue	submitted	none	sponge? [wide pipe]
Grøstl	submitted	yes	sponge? Merkle-Damgård/Davies-Meyer? [wide pipe]
HASH 2X	submitted	☠	streaming?
Keccak	submitted	none	sponge [wide pipe]
Maraca	submitted	none	sponge? [wide pipe]
MCSSHA-3	submitted	☠	streaming
MD6	submitted	yes	Merkle tree [wide pipe]
NaSHA	submitted	none	sponge? [narrow pipe]
NKS2D	submitted	☠	cellular automaton
Ponic	submitted	none	streaming
Sarmal	submitted	yes	HAIFA/Davies-Meyer [narrow pipe]
Sgàil	submitted	☠	Merkle-Damgård/Davies-Meyer [wide pipe]
SHAMATA	submitted	none	sponge [wide pipe]
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]
Vortex	submitted	yes	Merkle-Damgård/Vortex-block? [wide pipe]
WaMM	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