Difference between revisions of "Talk:The SHA-3 Zoo"

From The ECRYPT Hash Function Website
 
m (→‎new tables)
 
(62 intermediate revisions by 7 users not shown)
Line 4: Line 4:
  
 
Would such a modification be welcome to the SHA-3 Zoo contributors?
 
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 <i>me</i> at any rate; I'm not asking that somebody else do the hard work &#9786;. 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 <b>seems</b> to be the following (disclaimer: I may be completely mistaken in many cases):<br>
 +
 +
{| 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 || &#9760;|| streaming
 +
|-
 +
| [[Cheetah]]                          || submitted || none  || ? [?]
 +
|-
 +
| [[CHI]]                              || submitted || none  || Merkle-Damg&aring;rd/Davies-Meyer [wide pipe]
 +
|-
 +
| [[CRUNCH]]                          || submitted || none  || Merkle-Damg&aring;rd/concatenate-permute-truncate [narrow pipe]
 +
|-
 +
| [[CubeHash]]                        || submitted || yes    || sponge [wide pipe]
 +
|-
 +
| <s>[[DCH]]</s>                      || submitted || &#9760;|| Merkle-Damg&aring;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 || &#9760;|| streaming
 +
|-
 +
| [[ESSENCE]]                          || submitted || none  || Merkle tree [narrow pipe]
 +
|-
 +
| [[FSB (SHA-3 submission) | FSB]]    || submitted || none  || Merkle-Damg&aring;rd/concatenate-permute-truncate [wide pipe]
 +
|-
 +
| [[Fugue]]                            || submitted || none  || sponge? [wide pipe]
 +
|-
 +
| [[Groestl|Gr&oslash;stl]]            || submitted || yes    || sponge? Merkle-Damg&aring;rd/Davies-Meyer? [wide pipe]
 +
|-
 +
| [[Hamsi]]                            || submitted || none  || ? [?]
 +
|-
 +
| <s>[[HASH 2X]]</s>                  || submitted || &#9760;|| 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&aring;rd interleaving [narrow pipe]
 +
|-
 +
| [[Lesamnta]]                        || submitted || none  || ? [?]
 +
|-
 +
| [[Luffa]]                            || submitted || none  || ? [?]
 +
|-
 +
| [[LUX]]                              || submitted || none  || ? [?]
 +
|-
 +
| [[Maraca]]                          || submitted || none  || sponge? [wide pipe]
 +
|-
 +
| <s>[[MCSSHA-3]]</s>                  || submitted || &#9760;|| 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 || &#9760;|| cellular automaton
 +
|-
 +
| [[Ponic]]                            || submitted || yes    || streaming
 +
|-
 +
| [[Sarmal]]                          || submitted || yes    || HAIFA/Davies-Meyer [narrow pipe]
 +
|-
 +
| <s>[[Sg&agrave;il]]</s>              || submitted || &#9760;|| Merkle-Damg&aring;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&aring;rd/UBI? Merkle tree? [narrow pipe]
 +
|-
 +
| [[Spectral Hash]]                    || submitted || yes    || Merkle-Damg&aring;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&aring;rd/Vortex-block? [wide pipe]
 +
|-
 +
| <s>[[WaMM]]</s>                      || submitted || &#9760;|| 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
 +
 +
Hi, I agree with those saying that a categorization can never be exact. A possibility is to collect a list of headlines such as "Merkle-Damgård", "Sponge", "Block cipher-based", "Permutation-based" etc., and state an indication as to which degree each hash function can be said to fall into each category. As an example, we say that Grøstl is permutation-based, but as Paulo showed, it can also be seen as being block cipher-based, so on a scale from, e.g., 0-4, Grøstl may be permutation-based to a degree of 3, and block cipher-based to a degree of 1 (just an example!). It is "almost" an MD construction, but not quite, so we may say it is MD to a degree of 2 or 3. The question is whether such a categorization will be more fair, more useful, etc., than a true/false categorization.
 +
 +
However, my personal opinion is that we should avoid completely to categorize hash functions (except in 100% objective ways such as internal state size, message block size, status in the competition etc. - some of which you may also argue are not 100% objective). I also think we should not deem hash functions as being "broken" or "damaged", we should just link to all published results, and let people make up their own minds. I am assuming we did not build the SHA-3 Zoo in an attempt to have an influence on NIST's decisions.
 +
 +
/Søren
 +
 +
== new tables ==
 +
 +
This is a draft for the new tables to show the analysis and complexities of each hash function. The first table is shown at the main page, the entries of the second table are only shown at the Wiki page of each hash function.
 +
 +
Martin
 +
 +
 +
--------
 +
 +
 +
The main idea of the SHA-3 Zoo is to give a good overview of cryptanalytic results. We try to avoid additional judgement whether a submission is broken. The answer to this question is left to NIST. However, we categorize the cryptanalytic results by their impact from very theoretic to practical attacks. A detailed description is given in [[Cryptanalysis Categories]].
 +
 +
At this time, 55 out of 64 submissions to the SHA-3 competition are publicly known and available. 51 submissions have advanced to the first round.
 +
So far, 3 out of 51 first round candidates have been officially conceded broken or withdrawn by the designers.
 +
 +
The following table should give a first impression on the remaining SHA-3 candidates. It shows only the best known attack, more detailed results are collected at the individual hash function pages.
 +
 +
[http://ehash.iaik.tugraz.at/index.php?title=Special:Recentchangeslinked&target=The_SHA-3_Zoo&days=7&limit=50&hideminor=1 Recent updates of the SHA-3 Zoo]
 +
 +
 +
{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
 +
|- style="background:#efefef;"
 +
! width="120"| Hash Name !! width="160" | Principal Submitter !! width="120"| Best Attack on Main NIST Requirements !! width="120"| Best Attack on other Hash Requirements
 +
|-
 +
| [[Abacus]]      || Neil Sholer || style="background:orange" | 2nd-preimage ||
 +
|-
 +
| [[ARIRANG]]      || Jongin Lim || ||
 +
|-                                                                                                           
 +
| [[AURORA]]      || Masahiro Fujita (Sony) || ||
 +
|-
 +
| [[BLAKE]]        || Jean-Philippe Aumasson || ||
 +
|-
 +
| [[Blender]]      || Dr. Colin Bradbury || style="background:orange" | preimage ||
 +
|-                                                                                                           
 +
| [[Blue Midnight Wish]] || Svein Johan Knapskog || ||
 +
|-
 +
| [[Cheetah]]      || Dmitry Khovratovich || || length-extension
 +
|-
 +
| [[CHI]]          || Phillip Hawkes || ||
 +
|-                                                                                                           
 +
| [[CRUNCH]]      || Jacques Patarin || ||
 +
|-
 +
| [[CubeHash]]    || D. J. Bernstein || style="background:greenyellow" | preimage ||
 +
|-
 +
| [[DCH]]          || David A. Wilson || style="background:red" | collision ||
 +
|-                                                                                                           
 +
| [[Dynamic SHA]]  || Xu Zijie || || length-extension
 +
|-
 +
| [[Dynamic SHA2]] || Xu Zijie || || length-extension
 +
|-
 +
| [[ECHO]]        || Henri Gilbert || ||
 +
|-                                                                                                           
 +
| [[ECOH]]        || Daniel R. L. Brown || ||
 +
|-
 +
| [[Edon-R (SHA-3 submission)|Edon-R]] || Danilo Gligoroski || style="background:yellow" | preimage ||
 +
|-
 +
| [[EnRUPT]]      || Sean O’Neil || style="background:red" | collision ||
 +
|-                                                                                                           
 +
| [[ESSENCE]]      || Jason Worth Martin || ||
 +
|-
 +
| [[FSB (SHA-3 submission) | FSB]] || Matthieu Finiasz || ||
 +
|-
 +
| [[Fugue]]        || Charanjit S. Jutla || ||
 +
|-                                                                                                           
 +
| [[Groestl|Grøstl]] || Lars Ramkilde Knudsen || ||
 +
|-
 +
| [[Hamsi]]        || Ozgul Kucuk || ||
 +
|-
 +
| [[JH]]          || Hongjun Wu || style="background:greenyellow" | preimage ||
 +
|-                                                                                                           
 +
| [[Keccak]]      || Joan Daemen || ||
 +
|-
 +
| [[Khichidi-1]]  || M Vidyasagar || style="background:red" | collision ||
 +
|-
 +
| [[LANE]]        || Sebastiann Indesteege || ||
 +
|-                       
 +
| [[Lesamnta]]    || Hirotaka Yoshida || ||
 +
|-
 +
| [[Luffa]]        || Dai Watanabe || ||
 +
|-
 +
| [[LUX]]          || Ivica Nikolic || ||
 +
|-                                                                                                           
 +
| [[MCSSHA-3]]    || Mikhail Maslennikov || style="background:yellow" | collision ||
 +
|-
 +
| [[MD6]]          || Ronald L. Rivest || ||
 +
|-
 +
| [[MeshHash]]    || Björn Fay || style="background:yellow" | 2nd preimage ||
 +
|-                                                                                                           
 +
| [[NaSHA]]        || Smile Markovski || style="background:yellow" | collision ||
 +
|-
 +
| [[SANDstorm]]    || Rich Schroeppel || ||
 +
|-
 +
| [[Sarmal]]      || Kerem VARICI ||  style="background:yellow" | preimage ||
 +
|-                                                                                                           
 +
| [[Sgàil]]        || Peter Maxwell|| style="background:red" | collision ||
 +
|-
 +
| [[Shabal]]      || Jean-Francois Misarsky || ||
 +
|-
 +
| [[SHAMATA]]      || Orhun Kara || ||
 +
|-                       
 +
| [[SHAvite-3]]    || Orr Dunkelman || ||
 +
|-
 +
| [[SIMD]]        || Gaetan Leurent || ||
 +
|-
 +
| [[Skein]]        || Bruce Schneier || ||
 +
|-                                                                                                           
 +
| [[Spectral Hash]] || Cetin Kaya Koc || ||
 +
|-
 +
| [[StreamHash]]  || Michal Trojnara || style="background:red" | collision ||
 +
|-
 +
| [[SWIFFTX]]      || Daniele Micciancio || ||
 +
|-                                                                                                           
 +
| [[Tangle]]      || Rafael Alvarez || style="background:red" | collision ||
 +
|-
 +
| [[TIB3]]        || Daniel Penazzi || ||
 +
|-
 +
| [[Twister]]      || Michael Gorski || style="background:orange" | collision ||
 +
|-                                                                                                           
 +
| [[Vortex (SHA-3 submission)|Vortex]] || Michael Kounavis || style="background:yellow" | preimage ||
 +
|}
 +
 +
 +
The following hash functions have been submitted to the NIST competition but did not advance to the first round or have been conceded broken by the designers:
 +
 +
{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
 +
|- style="background:#efefef;"
 +
! width="120"| Hash Name !! width="160" | Principal Submitter !! width="120" | Status !! width="120" | Best Attack on Main NIST Requirements
 +
|-
 +
| [[Boole]]      || Greg Rose || conceded broken || style="background:red" | collision
 +
|-
 +
| [[HASH 2X]]    || || submitted || style="background:red" | 2nd-preimage
 +
|-
 +
| [[Maraca]]      || || submitted ||
 +
|-
 +
| [[NKS2D]]      || || submitted || style="background:red" | collision
 +
|-
 +
| [[Ponic]]      || || submitted || style="background:yellow" | 2nd-preimage
 +
|-
 +
| [[WaMM]]        || John Washburn || conceded broken || style="background:red" | collision
 +
|-
 +
| [[Waterfall]]  || Bob Hattersley || conceded broken || style="background:orange" | collision
 +
|}
 +
 +
 +
--------
 +
 +
 +
The following entries are shown at the individual hash function pages only:
 +
 +
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                 
 +
|- style="background:#efefef;"                 
 +
| Hash Function Name ||  Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference
 +
|-                   
 +
| Abacus  || style="background:orange" | 2nd preimage || hash ||  ||  || 2<sup>344</sup> || - || [http://web.mit.edu/dwilson/www/hash/abacus_attack.pdf Wilson]
 +
|-                   
 +
| Abacus  || style="background:orange" | collision || hash ||  ||  || 2<sup>172</sup> || - || [http://web.mit.edu/dwilson/www/hash/abacus_attack.pdf Wilson]
 +
|-                   
 +
| Abacus  || style="background:orange" | 2nd preimage || hash ||  ||  || 2<sup>172</sup> || - || [http://lj.streamclub.ru/papers/hash/abacus.pdf Nikolić,Khovratovich]
 +
|-                   
 +
| Blender || style="background:orange" | preimage || hash || all ||  || n*2<sup>n/2</sup> || - || [http://ehash.iaik.tugraz.at/uploads/4/48/Blender-preimage.pdf Mendel]
 +
|-                   
 +
| Blender ||  | near-collision || hash || all ||  || example || - || [http://cryptography.hyperlink.cz/BMW/near_collision_blender.pdf Klima]
 +
|-                   
 +
| Blender ||  | semi-free start collision || hash || all ||  || example || - || [http://eprint.iacr.org/2008/532.pdf Xu]
 +
|-                   
 +
| Blender || style="background:orange" | preimage || hash || all ||  || n*2<sup>(n+w)/2</sup> || - || [http://ehash.iaik.tugraz.at/uploads/2/20/Observations_on_Blender.pdf Newbold]
 +
|-                   
 +
| Blue Midnight Wish ||  | near-collision || compression || all ||  || example || - || [http://www2.mat.dtu.dk/people/S.Thomsen/bmw/nc-compress.pdf Thomsen]
 +
|-                   
 +
| Boole || style="background:orange" | preimage || hash || all ||  || 2<sup>9n/16</sup> || - || [http://ehash.iaik.tugraz.at/uploads/2/2f/Boole.pdf Nikolić]
 +
|-                   
 +
| Boole || style="background:red" | collision || hash || 224,256 ||  || example, 2<sup>34</sup> || - || [http://ehash.iaik.tugraz.at/uploads/0/0b/BooleCollision.txt Mendel,Nad,Schläffer]
 +
|-                   
 +
| Boole || style="background:red" | collision || hash || 384,512 ||  || 2<sup>66</sup> || - || [http://ehash.iaik.tugraz.at/uploads/0/0b/BooleCollision.txt Mendel,Nad,Schläffer]
 +
|-                   
 +
| Cheetah ||  | length-extension || hash || all ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/d/d9/Cheetah_length-extension.txt Gligoroski]
 +
|-                   
 +
| CubeHash ||  | observations ||  || all ||  ||  ||  || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
 +
|-                   
 +
| CubeHash || style="background:greenyellow" | preimage ||  || all ||  || 2<sup>513-4b</sup> || ? || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
 +
|-                   
 +
| CubeHash ||  | multi-collision ||  || all ||  || 2<sup>513-4b</sup> || ? || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
 +
|-                   
 +
| CubeHash || style="background:greenyellow" | preimage || hash || 512 ||  || 2<sup>511</sup> || 2<sup>508</sup> || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
 +
|-                   
 +
| CubeHash ||  | preimage || hash || 512 || r/4 || 2<sup>496</sup> || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
 +
|-                   
 +
| CubeHash ||  | preimage || hash || 512 || r/8 || 2<sup>480</sup> || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
 +
|-                   
 +
| CubeHash ||  | collision || hash || 512 || 2/120 || example || - || [http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt Aumasson]
 +
|-                   
 +
| DCH || style="background:red" | collision || hash || all ||  || 521 || - || [http://ehash.iaik.tugraz.at/uploads/9/9b/Dch.pdf Mendel,Lamberger]
 +
|-                   
 +
| DCH || style="background:red" | preimage || hash || all ||  || 521 || - || [http://ehash.iaik.tugraz.at/uploads/9/9b/Dch.pdf Mendel,Lamberger]
 +
|-                   
 +
| DCH || style="background:orange" | collision || hash || all ||  || 2<sup>45</sup> || 2<sup>45</sup> || [http://ehash.iaik.tugraz.at/uploads/b/b7/Dch1.pdf Khovratovich,Nikolić]
 +
|-                   
 +
| DCH || style="background:orange" | preimage || hash || all ||  || 2<sup>45</sup> || 2<sup>45</sup> || [http://ehash.iaik.tugraz.at/uploads/b/b7/Dch1.pdf Khovratovich,Nikolić]
 +
|-                   
 +
| DCH || style="background:yellow" | 2nd preimage || hash || 512 ||  || 2<sup>450</sup> || ? || [http://web.mit.edu/dwilson/www/hash/ Rechberger]
 +
|-                   
 +
| Dynamic SHA ||  | length-extension || hash || all ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/e/e7/Dynamic-sha_length-extension.txt Klima]
 +
|-                   
 +
| Dynamic SHA2 ||  | length-extension || hash || all ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/0/0e/Dynamic-sha2_length-extension.txt Klima]
 +
|-                   
 +
| Edon-R ||  | collision || compression ||  ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
 +
|-                   
 +
| Edon-R ||  | 2nd preimage || compression ||  ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
 +
|-                   
 +
| Edon-R ||  | preimage || compression ||  ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
 +
|-                   
 +
| Edon-R || style="background:yellow" | preimage || hash ||  ||  || 2<sup>2n/3</sup> || 2<sup>2n/3</sup> || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
 +
|-                   
 +
| Edon-R ||  | multi-collision (2<sup>K</sup>) || hash || 256,512 ||  || K*2<sup>n/2</sup> || 2<sup>n/2</sup> || [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf Klima]
 +
|-                   
 +
| Edon-R ||  | multi-preimage || hash || 256,512 ||  || ? || ? || [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf Klima]
 +
|-                   
 +
| EnRUPT || style="background:yellow" | preimage || hash || 512 ||  || 2<sup>480</sup> || 2<sup>480</sup> || [http://ehash.iaik.tugraz.at/uploads/9/9b/Enrupt.pdf Khovratovich,Nikolić]
 +
|-                   
 +
| EnRUPT || style="background:red" | collision || hash || 256 ||  || example, 2<sup>47</sup> || - || [http://homes.esat.kuleuven.be/~sindeste/enrupt.html Indesteege]
 +
|-                   
 +
| Grøstl ||  | observation || block cipher || all ||  ||  ||  || [http://www.larc.usp.br/~pbarreto/Grizzly.pdf Barreto]
 +
|-                   
 +
| Hash 2X || style="background:red" | 2nd preimage || hash ||  ||  || example || - || [http://tibasicdev.wikidot.com/archives:hash-2x/comments/show#post-302617 Aumasson]
 +
|-                   
 +
| JH ||  | pseudo-collision || compression || all ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt Bagheri]
 +
|-                   
 +
| JH ||  | pseudo-2nd preimage || compression || all ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/a/a8/Jh1.txt Bagheri]
 +
|-                   
 +
| JH || style="background:greenyellow" | preimage || hash || all ||  || 2<sup>510.3</sup> || 2<sup>510.3</sup> || [http://ehash.iaik.tugraz.at/uploads/d/da/Jh_preimage.pdf Mendel,Thomsen]
 +
|-                   
 +
| KhiChidi-1 || style="background:red" | collision || hash || 256 ||  || example || - || [http://ehash.iaik.tugraz.at/uploads/8/89/Khichidi-1.txt Mouha]
 +
|-                   
 +
| LUX ||  | collision || reduced hash || 224 || 3 blank rounds || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
 +
|-                   
 +
| LUX ||  | near-collision || reduced hash || 256 || 3 blank rounds || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
 +
|-                   
 +
| LUX ||  | free-start collision || compression || ? ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
 +
|-                   
 +
| LUX ||  | free-start preimage || compression || ? ||  || 2<sup>80</sup> || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
 +
|-                   
 +
| LUX ||  | slide-attack || hash || all || salt size: 31 mod 32 || - || - || [http://ehash.iaik.tugraz.at/uploads/6/62/Lux_peyrin.txt Peyrin]
 +
|-                   
 +
| Maraca ||  | internal collision || internal state || 512 ||  || 2<sup>237</sup> || 2<sup>230.5</sup> || [http://ehash.iaik.tugraz.at/uploads/5/52/Maraca.pdf Canteaut,Naya-Plasencia]
 +
|-                   
 +
| MCSSHA-3 || style="background:yellow" | collision || hash || all ||  || 2<sup>3n/8</sup> || ? || [http://131002.net/data/papers/AN08.pdf Aumasson,Naya-Plasencia]
 +
|-                   
 +
| MCSSHA-3 || style="background:yellow" | 2nd preimage || hash || all ||  || 2<sup>3n/4</sup> || ? || [http://131002.net/data/papers/AN08.pdf Aumasson,Naya-Plasencia]
 +
|-                   
 +
| MD6 ||  | non-randomness || reduced compression ||  || 18 rounds || ? || ? || [http://groups.csail.mit.edu/cis/md6/supmitted-2008-10-27/Supporting_Documentation/md6_report.pdf Aumasson,Meier]
 +
|-                   
 +
| MD6 ||  | key-recovery || reduced compression ||  || 15 rounds || ? || ? || [http://groups.csail.mit.edu/cis/md6/supmitted-2008-10-27/Supporting_Documentation/md6_report.pdf Dinur,Shamir]
 +
|-                   
 +
| MeshHash || style="background:orange" | 2nd preimage || hash || 256 ||  || 2<sup>192</sup> || - || [http://www.mat.dtu.dk/people/S.Thomsen/meshhash/2ndpreimage.pdf Thomsen]
 +
|-                   
 +
| MeshHash || style="background:orange" | 2nd preimage || hash || 512 ||  || 2<sup>320</sup> || - || [http://www.mat.dtu.dk/people/S.Thomsen/meshhash/2ndpreimage.pdf Thomsen]
 +
|-                   
 +
| NaSHA ||  | free-start collision || compression || all ||  || 2<sup>32</sup> || ? || [http://ehash.iaik.tugraz.at/uploads/3/33/Free-start_attacks_on_Nasha.pdf Nikolić,Khovratovich]
 +
|-                   
 +
| NaSHA ||  | free-start preimage || compression || 224,256 ||  || ~2<sup>128</sup> || ? || [http://ehash.iaik.tugraz.at/uploads/3/33/Free-start_attacks_on_Nasha.pdf Nikolić,Khovratovich]
 +
|-                   
 +
| NaSHA ||  | free-start preimage || compression || 384,512 ||  || ~2<sup>256</sup> || ? || [http://ehash.iaik.tugraz.at/uploads/3/33/Free-start_attacks_on_Nasha.pdf Nikolić,Khovratovich]
 +
|-                   
 +
| NaSHA ||  | free-start collision || compression || all ||  || - || - || [http://eprint.iacr.org/2008/519.pdf Ji,Liangyu,Xu]
 +
|-                   
 +
| NaSHA || style="background:yellow" | collision || hash || 512 ||  || 2<sup>192</sup> || ? || [http://eprint.iacr.org/2008/519.pdf Ji,Liangyu,Xu]
 +
|-                   
 +
| NKS2D || style="background:red" | collision || hash || 224 ||  || example || - || [http://ehash.iaik.tugraz.at/uploads/3/3f/NK2SD-224.txt De Cannière]
 +
|-                   
 +
| NKS2D || style="background:red" | collision || hash || 512 ||  || example || - || [http://ehash.iaik.tugraz.at/uploads/9/93/NK2SD-512.txt Enright]
 +
|-                   
 +
| Ponic || style="background:yellow" | 2nd preimage || hash || 512 ||  || 2<sup>265</sup> || 2<sup>256</sup> || [http://131002.net/data/papers/ponic.pdf Naya-Plasencia]
 +
|-                   
 +
| Sarmal || style="background:yellow" | preimage || hash || 512 ||  || max(2<sup>512-s</sup>,2<sup>256+s</sup>) || 2<sup>s</sup> || [http://ehash.iaik.tugraz.at/uploads/7/77/Sarmal.pdf Nikolić]
 +
|-                   
 +
| Sarmal ||  | collision with salt || hash || 224,256,384 ||  || 2<sup>n/3</sup> || 2<sup>n/3</sup> || [http://ehash.iaik.tugraz.at/uploads/d/d1/Salt-collision.pdf Mendel,Schläffer]
 +
|-                   
 +
| Sgàil || style="background:red" | collision || hash ||  ||  || example || - || [http://www.allicient.co.uk/2008/11/05/aww-psh/ Maxwell]
 +
|-                   
 +
| SHAMATA ||  | observation || block cipher ||  ||  ||  ||  || [http://www.uni-weimar.de/cms/fileadmin/medien/medsicherheit/Research/SHA3/Observations_for_SHAMATA.pdf Fleischmann,Gorski]
 +
|-                   
 +
| SHAMATA ||  | observation || block cipher ||  ||  ||  ||  || [http://www.uekae.tubitak.gov.tr/uekae_content_files/crypto/improved_analysis_of_Shamata-BC.pdf Atalay,Kara,Karakoc]
 +
|-                   
 +
| SpectralHash ||  | near-collision || hash || 224,512 || reference impl. || example || - || [http://ehash.iaik.tugraz.at/uploads/2/27/Near_and_truncated_collisions_in_Spectral_Hash_%28shash----%29.txt Enright]
 +
|-                   
 +
| SpectralHash ||  | truncated collision || hash || 512 || reference impl. || example || - || [http://ehash.iaik.tugraz.at/uploads/2/27/Near_and_truncated_collisions_in_Spectral_Hash_%28shash----%29.txt Enright]
 +
|-                   
 +
| SpectralHash ||  | collision || hash ||  || reference impl. || example || - || [http://ehash.iaik.tugraz.at/uploads/6/64/Spectralhash.txt Bjørstad]
 +
|-                   
 +
| StreamHash || style="background:yellow" | collision || hash || all ||  || n/2*2<sup>n/4</sup> || ? || [http://lj.streamclub.ru/papers/hash/streamhash.pdf Khovratovich,Nikolić]
 +
|-                   
 +
| StreamHash || style="background:yellow" | preimage || hash || all ||  || n/2*2<sup>n/2</sup> || ? || [http://lj.streamclub.ru/papers/hash/streamhash.pdf Khovratovich,Nikolić]
 +
|-                   
 +
| StreamHash || style="background:red" | collision || hash || 256 ||  || example || - || [http://ehash.iaik.tugraz.at/uploads/7/7b/Streamhash.txt Bjørstad]
 +
|-                   
 +
| Tangle ||  | observation ||  ||  ||  ||  ||  || [http://ehash.iaik.tugraz.at/uploads/c/c9/Tangle_Observation.pdf Esmaeili]
 +
|-                   
 +
| Tangle || style="background:red" | collision || hash || all ||  || example, 2<sup>13</sup> - 2<sup>28</sup> || - || [http://www2.mat.dtu.dk/people/S.Thomsen/tangle/tangle-coll.pdf Thomsen]
 +
|-                   
 +
| Twister ||  | pseudo-collision || compression || all ||  || 2<sup>26.5</sup> || 2<sup>28</sup> || [http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf Mendel,Rechberger,Schläffer]
 +
|-                   
 +
| Twister || style="background:orange" | collision || hash || 512 ||  || 2<sup>252</sup> || - || [http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf Mendel,Rechberger,Schläffer]
 +
|-                   
 +
| Twister || style="background:yellow" | 2nd preimage || hash || 512 ||  || 2<sup>448</sup> || 2<sup>64</sup> || [http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf Mendel,Rechberger,Schläffer]
 +
|-                   
 +
| Vortex ||  | pseudo collision || compression || all ||  || 2<sup>n/4</sup> || - || [http://ehash.iaik.tugraz.at/uploads/5/5c/Vortex_Collisions_and_Preimages_note.txt Knudsen,Mendel,Rechberger,Thomsen]
 +
|-                   
 +
| Vortex || style="background:yellow" | preimage || hash || all ||  || 2<sup>3n/4</sup> || 2<sup>n/4</sup> || [http://ehash.iaik.tugraz.at/uploads/5/5c/Vortex_Collisions_and_Preimages_note.txt Knudsen,Mendel,Rechberger,Thomsen]
 +
|-                   
 +
| Vortex || style="background:yellow" | collision || hash || 256 ||  || 2<sup>122.5</sup> || 2<sup>122.5</sup> || [http://ehash.iaik.tugraz.at/uploads/5/5c/Vortex_Collisions_and_Preimages_note.txt Knudsen,Mendel,Rechberger,Thomsen]
 +
|-                   
 +
| Vortex ||  | observation ||  || all ||  ||  ||  || [http://www.131002.net/data/papers/AD08.pdf Aumasson,Dunkelman]
 +
|-                   
 +
| Vortex ||  | correlation analysis || hash || all ||  || - || - || [http://ehash.iaik.tugraz.at/uploads/6/6d/Vortex_correlation.txt Ferguson]
 +
|-                   
 +
| WaMM || style="background:red" | collision || hash || all ||  || example || - || [http://web.mit.edu/dwilson/www/hash/wamm.html Wilson]
 +
|-                   
 +
| Waterfall || style="background:orange" | collision || hash || all ||  || 2<sup>70</sup> || - || [http://eprint.iacr.org/2008/531.pdf Fluhrer]
 +
|-                   
 +
|}                   
 +
 +
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
 +
 +
--------
 +
 +
 +
This looks fine to me. The only editorial aspect I'm a bit unsure of is the inclusion of rejected submissions on the same table; they are only reducing the S/N ratio, since they don't contribute anything to the ongoing SHA-3 process (and hence are not likely to received any further attention at least until the competition is over). I suggest moving them to an appendix table.
 +
 +
Paulo.

Latest revision as of 21:30, 29 December 2008

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

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 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 [1].

Gilles

Hi, I agree with those saying that a categorization can never be exact. A possibility is to collect a list of headlines such as "Merkle-Damgård", "Sponge", "Block cipher-based", "Permutation-based" etc., and state an indication as to which degree each hash function can be said to fall into each category. As an example, we say that Grøstl is permutation-based, but as Paulo showed, it can also be seen as being block cipher-based, so on a scale from, e.g., 0-4, Grøstl may be permutation-based to a degree of 3, and block cipher-based to a degree of 1 (just an example!). It is "almost" an MD construction, but not quite, so we may say it is MD to a degree of 2 or 3. The question is whether such a categorization will be more fair, more useful, etc., than a true/false categorization.

However, my personal opinion is that we should avoid completely to categorize hash functions (except in 100% objective ways such as internal state size, message block size, status in the competition etc. - some of which you may also argue are not 100% objective). I also think we should not deem hash functions as being "broken" or "damaged", we should just link to all published results, and let people make up their own minds. I am assuming we did not build the SHA-3 Zoo in an attempt to have an influence on NIST's decisions.

/Søren

new tables

This is a draft for the new tables to show the analysis and complexities of each hash function. The first table is shown at the main page, the entries of the second table are only shown at the Wiki page of each hash function.

Martin



The main idea of the SHA-3 Zoo is to give a good overview of cryptanalytic results. We try to avoid additional judgement whether a submission is broken. The answer to this question is left to NIST. However, we categorize the cryptanalytic results by their impact from very theoretic to practical attacks. A detailed description is given in Cryptanalysis Categories.

At this time, 55 out of 64 submissions to the SHA-3 competition are publicly known and available. 51 submissions have advanced to the first round. So far, 3 out of 51 first round candidates have been officially conceded broken or withdrawn by the designers.

The following table should give a first impression on the remaining SHA-3 candidates. It shows only the best known attack, more detailed results are collected at the individual hash function pages.

Recent updates of the SHA-3 Zoo


Hash Name Principal Submitter Best Attack on Main NIST Requirements Best Attack on other Hash Requirements
Abacus Neil Sholer 2nd-preimage
ARIRANG Jongin Lim
AURORA Masahiro Fujita (Sony)
BLAKE Jean-Philippe Aumasson
Blender Dr. Colin Bradbury preimage
Blue Midnight Wish Svein Johan Knapskog
Cheetah Dmitry Khovratovich length-extension
CHI Phillip Hawkes
CRUNCH Jacques Patarin
CubeHash D. J. Bernstein preimage
DCH David A. Wilson collision
Dynamic SHA Xu Zijie length-extension
Dynamic SHA2 Xu Zijie length-extension
ECHO Henri Gilbert
ECOH Daniel R. L. Brown
Edon-R Danilo Gligoroski preimage
EnRUPT Sean O’Neil collision
ESSENCE Jason Worth Martin
FSB Matthieu Finiasz
Fugue Charanjit S. Jutla
Grøstl Lars Ramkilde Knudsen
Hamsi Ozgul Kucuk
JH Hongjun Wu preimage
Keccak Joan Daemen
Khichidi-1 M Vidyasagar collision
LANE Sebastiann Indesteege
Lesamnta Hirotaka Yoshida
Luffa Dai Watanabe
LUX Ivica Nikolic
MCSSHA-3 Mikhail Maslennikov collision
MD6 Ronald L. Rivest
MeshHash Björn Fay 2nd preimage
NaSHA Smile Markovski collision
SANDstorm Rich Schroeppel
Sarmal Kerem VARICI preimage
Sgàil Peter Maxwell collision
Shabal Jean-Francois Misarsky
SHAMATA Orhun Kara
SHAvite-3 Orr Dunkelman
SIMD Gaetan Leurent
Skein Bruce Schneier
Spectral Hash Cetin Kaya Koc
StreamHash Michal Trojnara collision
SWIFFTX Daniele Micciancio
Tangle Rafael Alvarez collision
TIB3 Daniel Penazzi
Twister Michael Gorski collision
Vortex Michael Kounavis preimage


The following hash functions have been submitted to the NIST competition but did not advance to the first round or have been conceded broken by the designers:

Hash Name Principal Submitter Status Best Attack on Main NIST Requirements
Boole Greg Rose conceded broken collision
HASH 2X submitted 2nd-preimage
Maraca submitted
NKS2D submitted collision
Ponic submitted 2nd-preimage
WaMM John Washburn conceded broken collision
Waterfall Bob Hattersley conceded broken collision



The following entries are shown at the individual hash function pages only:

Hash Function Name Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
Abacus 2nd preimage hash 2344 - Wilson
Abacus collision hash 2172 - Wilson
Abacus 2nd preimage hash 2172 - Nikolić,Khovratovich
Blender preimage hash all n*2n/2 - Mendel
Blender near-collision hash all example - Klima
Blender semi-free start collision hash all example - Xu
Blender preimage hash all n*2(n+w)/2 - Newbold
Blue Midnight Wish near-collision compression all example - Thomsen
Boole preimage hash all 29n/16 - Nikolić
Boole collision hash 224,256 example, 234 - Mendel,Nad,Schläffer
Boole collision hash 384,512 266 - Mendel,Nad,Schläffer
Cheetah length-extension hash all - - Gligoroski
CubeHash observations all Aumasson,Meier,Naya-Plasencia,Peyrin
CubeHash preimage all 2513-4b ? Aumasson,Meier,Naya-Plasencia,Peyrin
CubeHash multi-collision all 2513-4b ? Aumasson,Meier,Naya-Plasencia,Peyrin
CubeHash preimage hash 512 2511 2508 Khovratovich,Nikolić,Weinmann
CubeHash preimage hash 512 r/4 2496 - Khovratovich,Nikolić,Weinmann
CubeHash preimage hash 512 r/8 2480 - Khovratovich,Nikolić,Weinmann
CubeHash collision hash 512 2/120 example - Aumasson
DCH collision hash all 521 - Mendel,Lamberger
DCH preimage hash all 521 - Mendel,Lamberger
DCH collision hash all 245 245 Khovratovich,Nikolić
DCH preimage hash all 245 245 Khovratovich,Nikolić
DCH 2nd preimage hash 512 2450 ? Rechberger
Dynamic SHA length-extension hash all - - Klima
Dynamic SHA2 length-extension hash all - - Klima
Edon-R collision compression - - Khovratovich,Nikolić,Weinmann
Edon-R 2nd preimage compression - - Khovratovich,Nikolić,Weinmann
Edon-R preimage compression - - Khovratovich,Nikolić,Weinmann
Edon-R preimage hash 22n/3 22n/3 Khovratovich,Nikolić,Weinmann
Edon-R multi-collision (2K) hash 256,512 K*2n/2 2n/2 Klima
Edon-R multi-preimage hash 256,512 ? ? Klima
EnRUPT preimage hash 512 2480 2480 Khovratovich,Nikolić
EnRUPT collision hash 256 example, 247 - Indesteege
Grøstl observation block cipher all Barreto
Hash 2X 2nd preimage hash example - Aumasson
JH pseudo-collision compression all - - Bagheri
JH pseudo-2nd preimage compression all - - Bagheri
JH preimage hash all 2510.3 2510.3 Mendel,Thomsen
KhiChidi-1 collision hash 256 example - Mouha
LUX collision reduced hash 224 3 blank rounds - - Wu,Feng,Wu
LUX near-collision reduced hash 256 3 blank rounds - - Wu,Feng,Wu
LUX free-start collision compression ? - - Wu,Feng,Wu
LUX free-start preimage compression ? 280 - Wu,Feng,Wu
LUX slide-attack hash all salt size: 31 mod 32 - - Peyrin
Maraca internal collision internal state 512 2237 2230.5 Canteaut,Naya-Plasencia
MCSSHA-3 collision hash all 23n/8 ? Aumasson,Naya-Plasencia
MCSSHA-3 2nd preimage hash all 23n/4 ? Aumasson,Naya-Plasencia
MD6 non-randomness reduced compression 18 rounds ? ? Aumasson,Meier
MD6 key-recovery reduced compression 15 rounds ? ? Dinur,Shamir
MeshHash 2nd preimage hash 256 2192 - Thomsen
MeshHash 2nd preimage hash 512 2320 - Thomsen
NaSHA free-start collision compression all 232 ? Nikolić,Khovratovich
NaSHA free-start preimage compression 224,256 ~2128 ? Nikolić,Khovratovich
NaSHA free-start preimage compression 384,512 ~2256 ? Nikolić,Khovratovich
NaSHA free-start collision compression all - - Ji,Liangyu,Xu
NaSHA collision hash 512 2192 ? Ji,Liangyu,Xu
NKS2D collision hash 224 example - De Cannière
NKS2D collision hash 512 example - Enright
Ponic 2nd preimage hash 512 2265 2256 Naya-Plasencia
Sarmal preimage hash 512 max(2512-s,2256+s) 2s Nikolić
Sarmal collision with salt hash 224,256,384 2n/3 2n/3 Mendel,Schläffer
Sgàil collision hash example - Maxwell
SHAMATA observation block cipher Fleischmann,Gorski
SHAMATA observation block cipher Atalay,Kara,Karakoc
SpectralHash near-collision hash 224,512 reference impl. example - Enright
SpectralHash truncated collision hash 512 reference impl. example - Enright
SpectralHash collision hash reference impl. example - Bjørstad
StreamHash collision hash all n/2*2n/4 ? Khovratovich,Nikolić
StreamHash preimage hash all n/2*2n/2 ? Khovratovich,Nikolić
StreamHash collision hash 256 example - Bjørstad
Tangle observation Esmaeili
Tangle collision hash all example, 213 - 228 - Thomsen
Twister pseudo-collision compression all 226.5 228 Mendel,Rechberger,Schläffer
Twister collision hash 512 2252 - Mendel,Rechberger,Schläffer
Twister 2nd preimage hash 512 2448 264 Mendel,Rechberger,Schläffer
Vortex pseudo collision compression all 2n/4 - Knudsen,Mendel,Rechberger,Thomsen
Vortex preimage hash all 23n/4 2n/4 Knudsen,Mendel,Rechberger,Thomsen
Vortex collision hash 256 2122.5 2122.5 Knudsen,Mendel,Rechberger,Thomsen
Vortex observation all Aumasson,Dunkelman
Vortex correlation analysis hash all - - Ferguson
WaMM collision hash all example - Wilson
Waterfall collision hash all 270 - Fluhrer

A description of this table is given here.



This looks fine to me. The only editorial aspect I'm a bit unsure of is the inclusion of rejected submissions on the same table; they are only reducing the S/N ratio, since they don't contribute anything to the ongoing SHA-3 process (and hence are not likely to received any further attention at least until the competition is over). I suggest moving them to an appendix table.

Paulo.

Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Talk:The_SHA-3_Zoo&oldid=2804"