The ECRYPT Hash Function Website - User contributions [en]

Talk:The SHA-3 Zoo

2008-12-20T13:49:35Z

PBarreto:

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

{| 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 || ☠|| 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]
|-
| <s>[[DCH]]</s> || submitted || ☠|| Merkle-Damgå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 || ☠|| streaming
|-
| [[ESSENCE]] || submitted || none || Merkle tree [narrow pipe]
|-
| [[FSB (SHA-3 submission) | FSB]] || submitted || none || Merkle-Damgård/concatenate-permute-truncate [wide pipe]
|-
| [[Fugue]] || submitted || none || sponge? [wide pipe]
|-
| [[Groestl|Grøstl]] || submitted || yes || sponge? Merkle-Damgård/Davies-Meyer? [wide pipe]
|-
| [[Hamsi]] || submitted || none || ? [?]
|-
| <s>[[HASH 2X]]</s> || 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]
|-
| <s>[[MCSSHA-3]]</s> || submitted || ☠|| 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 || ☠|| cellular automaton
|-
| [[Ponic]] || submitted || yes || streaming
|-
| [[Sarmal]] || submitted || yes || HAIFA/Davies-Meyer [narrow pipe]
|-
| <s>[[Sgàil]]</s> || 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 (SHA-3 submission)|Vortex]] || submitted || yes || Merkle-Damgård/Vortex-block? [wide pipe]
|-
| <s>[[WaMM]]</s> || 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 [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

main table:

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
! width="120"| Hash Name !! width="100"| Status !! width="100"| External Cryptanalysis !! width="100"| practical example !! width="100"| time*memory < generic !! width="100"| compr. calls < generic
|-
| [[Abacus]] || 1st round || style="background:orange" | yes || || X || X
|-
| [[ARIRANG]] || 1st round || none || || ||
|-
| [[AURORA]] || 1st round || none || || ||
|-
| [[BLAKE]] || 1st round || none || || ||
|-
| [[Blender]] || 1st round || none || || ||
|-
| [[Blue Midnight Wish]] || 1st round || style="background:green" | yes || || ||
|-
| [[Boole]] || 1st round || style="background:red" | yes || X || X || X
|-
| [[Cheetah]] || 1st round || none || || ||
|-
| [[CHI]] || 1st round || none || || ||
|-
| [[CRUNCH]] || 1st round || none || || ||
|-
| [[CubeHash]] || 1st round || style="background:yellow" | yes || || || X
|-
| [[DCH]] || 1st round || style="background:red" | yes || X || X || X
|-
| [[Dynamic SHA]] || 1st round || none || || ||
|-
| [[Dynamic SHA2]] || 1st round || none || || ||
|-
| [[ECHO]] || 1st round || none || || ||
|-
| [[ECOH]] || 1st round || none || || ||
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || 1st round || style="background:yellow" | yes || || || X
|-
| [[EnRUPT]] || 1st round || style="background:red" | yes || X || X || X
|-
| [[ESSENCE]] || 1st round || none || || ||
|-
| [[FSB (SHA-3 submission) | FSB]] || 1st round || none || || ||
|-
| [[Fugue]] || 1st round || none || || ||
|-
| [[Groestl|Grøstl]] || 1st round || style="background:green" | yes || || ||
|-
| [[HASH 2X]] || submitted || style="background:black" | yes || X || X || X
|-
| [[Hamsi]] || 1st round || none || || ||
|-
| [[JH]] || 1st round || style="background:yellow" | yes || || || X
|-
| [[Keccak]] || 1st round || none || || ||
|-
| [[Khichidi-1]] || 1st round || style="background:red" | yes || X || X || X
|-
| [[LANE]] || 1st round || none || || ||
|-
| [[Lesamnta]] || 1st round || none || || ||
|-
| [[Luffa]] || 1st round || none || || ||
|-
| [[LUX]] || 1st round || style="background:green" | yes || || ||
|-
| [[Maraca]] || submitted || style="background:black" | yes || || ||
|-
| [[MCSSHA-3]] || 1st round || style="background:yellow" | yes || || || X
|-
| [[MD6]] || 1st round || style="background:green" | yes || || ||
|-
| [[MeshHash]] || 1st round || style="background:yellow" | yes || || || X
|-
| [[NaSHA]] || 1st round || style="background:yellow" | yes || || || X
|-
| [[NKS2D]] || submitted || style="background:black" | yes || X || X || X
|-
| [[Ponic]] || submitted || style="background:black" | yes || || || X
|-
| [[SANDstorm]] || 1st round || none || || ||
|-
| [[Sarmal]] || 1st round || style="background:green" | yes || || ||
|-
| [[Sgàil]] || 1st round || style="background:red" | yes || X || X || X
|-
| [[Shabal]] || 1st round || none || || ||
|-
| [[SHAMATA]] || 1st round || style="background:green" | yes || || ||
|-
| [[SHAvite-3]] || 1st round || none || || ||
|-
| [[SIMD]] || 1st round || none || || ||
|-
| [[Skein]] || 1st round || none || || ||
|-
| [[Spectral Hash]] || 1st round || style="background:green" | yes || || ||
|-
| [[StreamHash]] || 1st round || style="background:yellow" | yes || || || X
|-
| [[SWIFFTX]] || 1st round || none || || ||
|-
| [[Tangle]] || 1st round || style="background:red" | yes || X || X || X
|-
| [[TIB3]] || 1st round || none || || ||
|-
| [[Twister]] || 1st round || style="background:orange" | yes || || X || X
|-
| [[Vortex (SHA-3 submission)|Vortex]] || 1st round || style="background:yellow" | yes || || || X
|-
| [[WaMM]] || 1st round || style="background:red" | yes || X || X || X
|-
| [[Waterfall]] || 1st round || none || || ||
|}

caption for main table:

{| border="1" cellpadding="4" cellspacing="0" align="center" class="wikitable" style="text-align:center"
|- style="background:#efefef;"
! width="100"| color !! External Cryptanalysis or Status !! Explanation
|-
| || no external cryptanalysis || no external cryptanalysis for this hash function has been published
|-
| style="background:green" | || external cryptanalysis || external cryptanalysis published but does not violate the NIST requirements
|-
| style="background:yellow" | || compr. calls < generic || the number of compression function calls is below generic attacks for collision, 2nd preimage or preimage
|-
| style="background:orange" | || time*memory < generic || the time*memory product is below generic attacks for collision, 2nd preimage or preimage
|-
| style="background:red" | || practical example || a practical (collision) example is given for the hash function
|-
| style="background:black" | || not in round 1 || this hash function did not advance to round 1 of the NIST competition
|-
|}

Individual hash function tables:
{| border="1" cellpadding="4" cellspacing="0" align="center" 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 || ? || || 2344 || - || [http://web.mit.edu/dwilson/www/hash/abacus_attack.pdf Wilson]
|-
| Abacus || style="background:orange" | collision || hash || ? || || 2172 || - || [http://web.mit.edu/dwilson/www/hash/abacus_attack.pdf Wilson]
|-
| Abacus || style="background:orange" | 2nd preimage || hash || ? || || 2172 || - || [http://lj.streamclub.ru/papers/hash/abacus.pdf Nikolić,Khovratovich]
|-
| Blue Midnight Wish || | near collision || compression || all || || - || - || [http://www2.mat.dtu.dk/people/S.Thomsen/bmw/nc-compress.pdf Thomsen]
|-
| Boole || style="background:orange" | preimage || hash || all || || 29n/16 || - || [http://ehash.iaik.tugraz.at/uploads/2/2f/Boole.pdf Nikolić]
|-
| Boole || style="background:red" | collision || hash || 224,256 || || example, 234 || - || [http://ehash.iaik.tugraz.at/uploads/0/0b/BooleCollision.txt Mendel,Nad,Schläffer]
|-
| Boole || style="background:red" | collision || hash || 384,512 || || 266 || - || [http://ehash.iaik.tugraz.at/uploads/0/0b/BooleCollision.txt Mendel,Nad,Schläffer]
|-
| CubeHash || | observations || || all || 8/1 || || || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
|-
| CubeHash || style="background:yellow" | preimage || hash || 512 || || 2511 || 2508 || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
|-
| CubeHash || | preimage || hash || 512 || r/4 || 2496 || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
|-
| CubeHash || | preimage || hash || 512 || r/8 || 2480 || - || [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 || || 245 || 245 || [http://ehash.iaik.tugraz.at/uploads/b/b7/Dch1.pdf Khovratovich,Nikolić]
|-
| DCH || style="background:orange" | preimage || hash || all || || 245 || 245 || [http://ehash.iaik.tugraz.at/uploads/b/b7/Dch1.pdf Khovratovich,Nikolić]
|-
| DCH || style="background:yellow" | 2nd preimage || hash || 512 || || 2450 || ? || [http://web.mit.edu/dwilson/www/hash/ Rechberger]
|-
| 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 || ? || || 22n/3 || 22n/3 || [http://ehash.iaik.tugraz.at/uploads/7/74/Edon.pdf Khovratovich,Nikolić,Weinmann]
|-
| Edon-R || | multicollision (2K) || hash || 256,512 || || K*2n/2 || 2n/2 || [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf Klima]
|-
| Edon-R || | multipreimage || hash || 256,512 || || ? || ? || [http://cryptography.hyperlink.cz/BMW/EDONR_analysis_vk.pdf Klima]
|-
| EnRUPT || style="background:yellow" | preimage || hash || 512 || || 2480 || 2480 || [http://ehash.iaik.tugraz.at/uploads/9/9b/Enrupt.pdf Khovratovich,Nikolić]
|-
| EnRUPT || style="background:red" | collision || hash || 256 || || example, 247 || - || [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:yellow" | preimage || hash || all || || 2510.3 || 2510.3 || [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 || ? || || 280 || - || [http://ehash.iaik.tugraz.at/uploads/3/36/Analysis_LUX_1.pdf Wu,Feng,Wu]
|-
| Maraca || | internal collision || internal state || 512 || || 2237 || 2230.5 || [http://ehash.iaik.tugraz.at/uploads/5/52/Maraca.pdf Canteaut,Naya-Plasencia]
|-
| MCSSHA-3 || style="background:yellow" | collision || hash || all || || 23n/8 || ? || [http://131002.net/data/papers/AN08.pdf Aumasson,Naya-Plasencia]
|-
| MCSSHA-3 || style="background:yellow" | 2nd preimage || hash || all || || 23n/4 || ? || [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:yellow" | 2nd preimage || hash || 256 || || 2194.3 || 2128 || [http://www.mat.dtu.dk/people/S.Thomsen/meshhash/2ndpreimage.pdf Thomsen]
|-
| MeshHash || style="background:yellow" | 2nd preimage || hash || 512 || || 2323.2 || 2256 || [http://www.mat.dtu.dk/people/S.Thomsen/meshhash/2ndpreimage.pdf Thomsen]
|-
| NaSHA || | free-start collision || compression || all || || 232 || ? || [http://ehash.iaik.tugraz.at/uploads/3/33/Free-start_attacks_on_Nasha.pdf Nikolić,Khovratovich]
|-
| NaSHA || | free-start preimage || compression || 224,256 || || ~2128 || ? || [http://ehash.iaik.tugraz.at/uploads/3/33/Free-start_attacks_on_Nasha.pdf Nikolić,Khovratovich]
|-
| NaSHA || | free-start preimage || compression || 384,512 || || ~2256 || ? || [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 || || 2192 || ? || [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 || || 2265 || 2256 || [http://131002.net/data/papers/ponic.pdf Naya-Plasencia]
|-
| Sarmal || | preimage (salt size s) || hash || 512 || || max(2512-s,2256+s) || 2s || [http://ehash.iaik.tugraz.at/uploads/7/77/Sarmal.pdf Nikolić]
|-
| 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*2n/4 || ? || [http://lj.streamclub.ru/papers/hash/streamhash.pdf Khovratovich,Nikolić]
|-
| StreamHash || style="background:yellow" | preimage || hash || all || || n/2*2n/2 || ? || [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, 213 - 228 || - || [http://www2.mat.dtu.dk/people/S.Thomsen/tangle/tangle-coll.pdf Thomsen]
|-
| Twister || | pseudo collision || compression || all || || 226.5 || 228 || [http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf Mendel,Rechberger,Schläffer]
|-
| Twister || style="background:orange" | collision || hash || 512 || || 2252 || - || [http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf Mendel,Rechberger,Schläffer]
|-
| Twister || style="background:yellow" | 2nd preimage || hash || 512 || || 2448 || 264 || [http://ehash.iaik.tugraz.at/uploads/d/dd/Twister_attack.pdf Mendel,Rechberger,Schläffer]
|-
| Vortex || | observation || || all || || || || [http://www.131002.net/data/papers/AD08.pdf Aumasson,Dunkelman]
|-
| Vortex || | pseudo collision || compression || all || || 2n/4 || - || [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 || || 23n/4 || 2n/4 || [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 || || 2122.5 || 2122.5 || [http://ehash.iaik.tugraz.at/uploads/5/5c/Vortex_Collisions_and_Preimages_note.txt Knudsen,Mendel,Rechberger,Thomsen]
|-
| WaMM || style="background:red" | collision || hash || all || || example || - || [http://web.mit.edu/dwilson/www/hash/wamm.html Wilson]
|-
|}

caption for individual tables:

A dash (-) in the individual table means that the complexities are neglible. A question mark (?) means the information is not given or unclear.

The "Parameters/Variants" column gives the parameters for attacks on reduced variants. If the column is empty, the attack is on the recommended parameters of the designers.

The "Type of Analyses" column is left white, if the attack is on reduced variants or parts of the hash function.

--------

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.

TIB3

2008-11-29T00:14:52Z

PBarreto: Fixing the link to TIB3 spec

== The algorithm ==

* Author(s): Daniel Penazzi, Miguel Montes
* Website: [http://www.famaf.unc.edu.ar/~penazzi/tib3/ http://www.famaf.unc.edu.ar/~penazzi/tib3/]
* Specification:

<bibtex>
@misc{sha3TIB308,
author = {Miguel Montes and Daniel Penazzi},
title = {The TIB3 Hash},
url = {http://www.famaf.unc.edu.ar/~penazzi/tib3/submitted/Supporting_Documentation/TIB3_Algorithm_Specification.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

* None yet

HashFunctions

The SHA-3 Zoo

2008-11-21T14:24:50Z

PBarreto:

The SHA-3 Zoo is a collection of cryptographic hash functions (in alphabetical order) submitted to the [http://www.nist.gov/hash-competition SHA-3 contest] (work in progress). It aims to provide an overview of design and cryptanalysis of all submissions. A list of all [[SHA-3 submitters]] is also available. For a software performance related overview, see [http://bench.cr.yp.to/ebash.html eBASH]. At a separate page, we also collect [[SHA-3_Hardware_Implementations | hardware implementation results]] of the candidates.
 
At this time, 29 out of 64 submissions to the SHA-3 competition are publicly known and available, and hence take advantage of early external cryptanalysis (so far, 7 submissions have been broken).

{| 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]]
|-
| [[BLAKE]] || submitted || none
|-
| [[Blue Midnight Wish]] || submitted || none
|-
| [[Boole]] || submitted || broken
|-
| [[CHI]] || submitted || none
|-
| [[CRUNCH]] || submitted || none
|-
| [[CubeHash]] || submitted || yes
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || submitted || yes
|-
| [[EnRUPT]] || submitted || broken
|-
| [[ESSENCE]] || submitted || none
|-
| [[FSB (SHA-3 submission) | FSB]] || submitted || none
|-
| [[Fugue]] || submitted || none
|-
| [[Groestl|Grøstl]] || submitted || yes
|-
| [[HASH 2X]] || submitted || broken
|-
| [[Keccak]] || submitted || none
|-
| [[Maraca]] || submitted || none
|-
| [[MCSSHA-3]] || submitted || broken
|-
| [[MD6]] || submitted || yes
|-
| [[NaSHA]] || submitted || none
|-
| [[NKS2D]] || submitted || broken
|-
| [[Ponic]] || submitted || none
|-
| [[Sarmal]] || submitted || yes
|-
| [[Sgàil]] || submitted || broken
|-
| [[SHAMATA]] || submitted || none
|-
| [[Skein]] || submitted || none
|-
| [[Spectral Hash]] || submitted || yes
|-
| [[SWIFFTX]] || submitted || none
|-
| [[Vortex (SHA-3 submission)|Vortex]] || submitted || yes
|-
| [[WaMM]] || submitted || broken
|-
| [[Waterfall]] || submitted || none
|}

Your submission is not on this list? Drop a line at sha3zoo@iaik.tugraz.at to let us know!

Groestl

2008-11-21T14:24:27Z

PBarreto: added "An observation on Grøstl"

== The algorithm ==

* Author(s): Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
* Website: [http://www.groestl.info http://www.groestl.info]
* Specification: [http://www.groestl.info/specification.html http://www.groestl.info/specification.html]
<bibtex>
@misc{sha3groestl,
author = {Praveen Gauravaram and Lars R. Knudsen and Krystian Matusiewicz and Florian Mendel and Christian Rechberger and Martin Schläffer and Søren S. Thomsen},
title = {Grøstl -- a SHA-3 candidate},
url = {http://www.groestl.info/Groestl.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

* P. S. L. M. Barreto, An observation on Grøstl. Details: [http://www.larc.usp.br/~pbarreto/Grizzly.pdf here]

Talk:Boole

2008-11-21T10:37:56Z

2008-11-18T13:22:13Z

PBarreto:

Talk:The SHA-3 Zoo

2008-11-18T13:21:12Z

PBarreto:

The SHA-3 Zoo

2008-11-18T13:02:54Z

PBarreto: Added ref to "Near and truncated collisions in Spectral Hash" by Brandon Enright

The SHA-3 Zoo is a collection of cryptographic hash functions (in alphabetical order) submitted to the [http://www.nist.gov/hash-competition SHA-3 contest] (work in progress). It aims to provide an overview of design and cryptanalysis of all submissions. A list of all [[SHA-3 submitters]] is also available. For a software performance related overview, see [http://bench.cr.yp.to/ebash.html eBASH]. At a separate page, we also collect [[SHA-3_Hardware_Implementations | hardware implementation results]] of the candidates.
 
At this time, 28 out of 64 submissions to the SHA-3 competition are publicly known and available, and hence take advantage of early external cryptanalysis (so far, 6 submissions have been broken).

{| 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]]
|-
| [[BLAKE]] || submitted || none
|-
| [[Blue Midnight Wish]] || submitted || none
|-
| [[Boole]] || submitted || yes
|-
| [[CHI]] || submitted || none
|-
| [[CRUNCH]] || submitted || none
|-
| [[CubeHash]] || submitted || none
|-
| [[Edon-R (SHA-3 submission)|Edon-R]] || submitted || yes
|-
| [[EnRUPT]] || submitted || broken
|-
| [[ESSENCE]] || submitted || none
|-
| [[FSB (SHA-3 submission) | FSB]] || submitted || none
|-
| [[Fugue]] || submitted || none
|-
| [[Groestl|Grøstl]] || submitted || none
|-
| [[HASH 2X]] || submitted || broken
|-
| [[Keccak]] || submitted || none
|-
| [[Maraca]] || submitted || none
|-
| [[MCSSHA-3]] || submitted || broken
|-
| [[MD6]] || submitted || yes
|-
| [[NaSHA]] || submitted || none
|-
| [[NKS2D]] || submitted || broken
|-
| [[Ponic]] || submitted || none
|-
| [[Sarmal]] || submitted || none
|-
| [[Sgàil]] || submitted || broken
|-
| [[SHAMATA]] || submitted || none
|-
| [[Skein]] || submitted || none
|-
| [[Spectral Hash]] || submitted || yes
|-
| [[Vortex (SHA-3 submission)|Vortex]] || submitted || yes
|-
| [[WaMM]] || submitted || broken
|-
| [[Waterfall]] || submitted || none
|}

Your submission is not on this list? Drop a line at sha3zoo@iaik.tugraz.at to let us know!

Spectral Hash

2008-11-18T13:01:13Z

PBarreto: Near and truncated collisions in Spectral Hash, by Brandon Enright

== The algorithm ==

* Author(s): Gokay Saldamlı, Cevahir Demirkıran, Megan Maguire, Carl Minden, Jacob Topper, Alex Troesch, Cody Walker, Çetin Kaya Koç

* Website: [http://www.cs.ucsb.edu/~koc/shash/index.html http://www.cs.ucsb.edu/~koc/shash/index.html]
* Specification:

<bibtex>
@misc{sha3Saldamli+08,
author = {Gokay Saldamlı, Cevahir Demirkıran, Megan Maguire, Carl Minden, Jacob Topper, Alex Troesch, Cody Walker, Çetin Kaya Koç},
title = {Spectral Hash},
url = {http://www.cs.ucsb.edu/~koc/shash/sHash.pdf},
howpublished = {Submission to NIST},
year = {2008},
}
</bibtex>

== Cryptanalysis ==

Brandon Enright: Near and truncated collisions in Spectral Hash (shash-###),
[http://ehash.iaik.tugraz.at/uploads/2/27/Near_and_truncated_collisions_in_Spectral_Hash_%28shash----%29.txt Local link]

File:Near and truncated collisions in Spectral Hash (shash----).txt

2008-11-18T12:59:33Z

PBarreto: Near and truncated collisions in Spectral Hash. NIST SHA-3 forum communication by Brandon Enright.

Near and truncated collisions in Spectral Hash. NIST SHA-3 forum communication by Brandon Enright.