Talk:The SHA-3 Zoo

From The ECRYPT Hash Function Website
Revision as of 10:49, 11 December 2008 by Mschlaeffer (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?

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
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]
Boole 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]
DCH submitted Merkle-Damgård/Miyaguchi-Preneel [narrow pipe]
Dynamic SHA submitted none ? [?]
Dynamic SHA2 submitted none ? [?]
ECHO submitted none ? [?]
ECOH submitted none ? [?]
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]
Hamsi submitted none ? [?]
HASH 2X 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]
MCSSHA-3 submitted streaming
MD6 submitted yes bounded-height Merkle tree [wide pipe]
MeshHash submitted none ? [?]
NaSHA submitted none sponge? [narrow pipe]
SANDstorm submitted none ? [?]
NKS2D submitted cellular automaton
Ponic submitted yes streaming
Sarmal submitted yes HAIFA/Davies-Meyer [narrow pipe]
Sgàil 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 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