SHA-3 Second Round Candidates Released

Jeremy A. Hansen writes "NIST just announced their selections for algorithms going to the second round of the SHA-3 competition. Quoting: 'NIST received 64 SHA-3 candidate hash function submissions and accepted 51 first round candidates as meeting our minimum acceptance criteria. We have now selected 14 second round candidates to continue in the competition. Information about the second round candidate algorithms will be available here. We were pleased by the amount and quality of the cryptanalysis we received on the first round candidates, and more than a little amazed by the ingenuity of some of the attacks. ... In selecting this set of second round candidates we tried to include only algorithms that we thought had a chance of being selected as SHA-3. We were willing to extrapolate higher performance for conservative designs with apparently large safety factors, but comparatively unforgiving of aggressive designs that were broken, or nearly broken during the course of the review. We were more willing to accept disquieting properties of the hash function if the designer had apparently anticipated them, than if they were discovered during the review period, even if there were apparent fixes. We were generally alarmed by attacks on compression functions that seemed unanticipated by the submitters.'"

Comments

I was a little worried

[Omnifarious]

I was a little worried by the plethora of submissions. I was worried it would take them forever to decide. But luckily they've been rather ruthless in culling for the third round. Given the data available on the The SHA-3 Zoo they chose wisely.

Personally, I think Skein is interestingly feature rich, which both worries and intrigues me. Looking it appears that all the features are built on a core in which the real security lies, so I'm not too worried. Skein's core in fact appears to be extremely simple.

Re:I was a little worried

[OverlordQ]

Well Bruce Schneier helped write it, this is the same man that once decrypted a box of AlphaBits.

Re:I was a little worried

[Omnifarious]

I consider Bruce Scheier as a cryptographer to be sort of like Carl Sagan as an astronomer. I think he is a competent cryptographer, but I think he has much greater value as a person who can speak cogently about the issues surrounding cryptography.

In this case, my guess is that he led the overall vision of how Skein should work but that the other people who worked on the algorithm filled in the details. In particular, I strongly suspect that Niels Ferguson is principally responsible for the core algorithm. Of course, pulling apart any particular collaboration and looking for the efforts of individuals can be tricky and error prone at best.

Re:I was a little worried

[mTor]

Skein is getting a lot of attention because Bruce Schneier is one of it's authors. It's a fine algorithm. Personally, after going through a bunch of them, I like BLAKE the best since its extremely simple and relies on old and proven functions that have withstood the test of time. Not to mention that it's extremely fast. I also like Blue Midnight Wish. I think the NIST will pick one of these three.

Re:I was a little worried

[FooAtWFU]

Well Bruce Schneier helped write it, this is the same man that once decrypted a box of AlphaBits.

That's actually bad news: Anybody can invent a cryptosystem he cannot break himself. Except Bruce Schneier.

Re:I was a little worried

[Omnifarious]

The thing I like about Skein is its tree mode. I've been working on a parallelizing version of sha256sum to see if I can speed up the generation of hashes 4-fold with my dual-core dual-processor system.

I also like the ways you can make it unique for a given usage. This will help make it more resistant to various kinds of attacks when used in particular applications and mitigate the effect of certain kinds of algorithm weaknesses if they're discovered.

But yeah, there are other candidates, and I'm more interested in the highest possible quality algorithm coming out of the process than I am in having my particular horse win.

Re:I was a little worried

[Martin Blank]

I knew about Schneier being involved from early on, but I just noticed Bernstein made the last cut. Considering Bernstein's thoroughness (64-bit timestamps in his programs, and didn't he once talk about writing his own filesystem to address an external limitation that slowed down qmail?), I am very intrigued at how well CubeHash will do. He apparently admits that it suffers from some performance problems, but also says that he over-engineered it, and that it can be scaled back to improve speed while losing little in the way of security.

Of the 14 candidates going into this round, his is one of only six that hasn't had to be revised so far. Of course, that he seems to have designed it completely on his own may work against him.

Re:I was a little worried

[letsief]

Depending on what you call a revision, Bernstein just revised CubeHash. A few days ago he posted a parameter tweak that significantly increases performance at the cost of some security. You can read about his tweak on his website at: http://cubehash.cr.yp.to/submission/tweak.pdf

Re:I was a little worried

[Skuto]

>The thing I like about Skein is its tree mode.

Pretty much every hash in the competition can work in tree mode. Not all submitters defined a tree mode, but that shouldn't stop NIST from defining a good one.

There are better performers than Skein, so unless those are all seriously weakened I doubt it can win. Skein looks good on high end hardware, and not so good on anything else (compared to some other top competitors).

Re:I was a little worried

[letsief]

In a practical sense, yes, but the generic preimage attacks against the 512-bit variant of CubeHash work better as the "b" parameter increases. It's still well above the birthday bound, so maybe people shouldn't care. But, it does mean CubeHash16/32-512 "only" provides 384 bits of preimage resistance. That's probably beyond theoretical computation limits for the universe, so I think there's a pretty good argument we shouldn't care. At the same time, all the attacks, and preimage attacks in particular, we're likely to see on 512-bit variants are likely to be well beyond anything that could seen as remotely practical.

Hey, cool!

[jd]

One of my favourites (Blue Midnight Wish) made it through, and one of the others with a really cool name (SandSTORM) wasn't broken in the 1st round.

Yes, I know, that's NOT how to pick hash functions, but you've got to admit that cryptography isn't capturing the popular imagination at the present time, leaving data dangerously insecure. I believe that part of this is because most popular crypto-related functions (and cryptographic hashing is definitely one) have names that are a turnoff.

Once upon a time, computing was for "the Egg Heads" and anyone daring to mention computers was automatically One Of Them. The Apple made computing sexy and it became fashionable.

Cryptography has to do the same thing, if security is to be meaningful. Otherwise, it will remain for "Egg Heads Only" and we will continue to see horrific losses from naive and pathetic practices by people trying to avoid being tarred as geeky.

Re:Hey, cool!

[jd]

Military grade, according to ITAR, means the key is more than 56 bits (used to be 40 bits). Which, you're right, means nothing.

Now, if I use the term "military-grade" for crypto, I would mean an algorithm that is certified NIST/NESSIE-approved for Secret or above (for mundane usage) or NIST/NESSIE-approved for Top Secret (for information that is commercially sensitive). That is still arguably market-babble, but at least it has a measure of respectability because NIST and NESSIE are reasonably trustworthy organizations for evaluating crypto.

Re:Where's Whirlpool?

[compro01]

It appears that whirlpool was never submitted to the competition.

Re:Where's Whirlpool?

[Skuto]

Because the Rijndael guys submitted something much better: Keccak.

MD6

[imbaczek]

I'm quite surprised Rivest didn't make it to round 2. Could anybody share some details about this decision?

Re:MD6

[Dj]

It was withdrawn from the contest

Re:MD6

[six]

Nobody in their right mind is using both MD5 and SHA-1 together, and even if they do they are both standardized hash methods. Combining hash methods is dangerous at least and should not be done haphazardly. It would be much better to use SHA-2 256 instead, if only because it is a standardized hash and not some weird combination of two.

I think the author doesn't mean to combine SHA-1 and MD5 to make one hash, but instead using both hashes. This may be weaker for preimage attacks, but a lot stronger against collisions, so if it's what you're after it's one of the best ways to achieve it.

Re:But can we "prove" that any of these are "one w

[TheTurtlesMoves]

It is trivial to prove that a function is one way. If the input is from a larger domain than the output. ie a^b=c is one way. given c I cannot recover a and b. Of course this is not a good function to use for other reasons....

If however the input is the same length then its a little harder...The only way we know how to do is the way this competition is doing it. Propose a "one way" function, others then try and break it. Otherwise you need a collision which in this context is a bad thing due to reduced randomness. ie f(a)=b and f(a')=b which a b and a' are the same bit length.