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 | yes | streaming |
| CHI | submitted | none | Merkle-Damgâaard/Davies-Meyer [wide pipe] |
| CRUNCH | submitted | none | sponge? [narrow pipe] |
| CubeHash | submitted | yes | sponge [wide pipe] |
| DCH | submitted | none | Merkle-Damgâaard/Miyaguchi-Preneel |
| Edon-R | submitted | yes | streaming |
| EnRUPT | submitted | broken | streaming |
| ESSENCE | submitted | none | Merkle tree [narrow pipe] |
| FSB | submitted | none | sponge? [wide pipe] |
| Fugue | submitted | none | sponge? [wide pipe] |
| Grøstl | submitted | none | sponge? Merkle-Damgaard/Davies-Meyer? [wide pipe] |
| HASH 2X | submitted | broken | streaming? |
| Keccak | submitted | none | sponge [wide pipe] |
| Maraca | submitted | none | sponge? [wide pipe] |
| MCSSHA-3 | submitted | broken | streaming |
| MD6 | submitted | yes | Merkle tree [wide pipe] |
| NaSHA | submitted | none | sponge? [narrow pipe] |
| NKS2D | submitted | broken | cellular automaton |
| Ponic | submitted | none | streaming |
| Sarmal | submitted | none | HAIFA/Davies-Meyer [narrow pipe] |
| Sgàil | submitted | broken | Merkle-Damgaard/Davies-Meyer [wide pipe] |
| SHAMATA | submitted | none | sponge [wide pipe] |
| Skein | submitted | none | Merkle-Damgaard/UBI? Merkle tree? [narrow pipe] |
| Spectral Hash | submitted | yes | Merkle-Damgaard/prism? [narrow pipe] |
| SWIFFTX | submitted | none | HAIFA/? [wide pipe] |
| Vortex | submitted | yes | Merkle-Damgaard/Vortex-block? [wide pipe] |
| WaMM | submitted | broken | Merkle-Damgaard? 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'm a bit unsure about the nature of a "sponge" hash. Sometimes the message is inserted via a group operation like XOR or addition mod 2^n; sometimes (à la Snefru) it's concatenated with the state or replaces part of it, hence it's irreversible. The behavior against attacks may be different in the two cases even though the difference is superficially small. Yet I wouldn't like to establish too fine distinctions if they are not necessary. Opinions?
Paulo.
