SHA-3 Finalist Candidates Known

Skuto writes "NIST just announced the final selection of algorithms in the SHA-3 hash competition. The algorithms that are candidates to replace SHA-2 are BLAKE, Grøstl, JH, Keccak and Skein. The selection criteria included performance in software and hardware, hardware implementation size, best known attacks and being different enough from the other candidates. Curiously, some of the faster algorithms were eliminated as they were felt to be 'too fast to be true.' A full report with the (non-)selection rationale for each candidate is forthcoming."

Comments

"Too fast to be true"

[MrEricSir]

Well that's mathematically sound reasoning!

Re:"Too fast to be true"

[icebike]

Exactly my reaction.

Is this a beauty contest or what?

There may be some tendency to think that something that hashes too quickly would be trivial, but without even a glance at the methodology and a modicum of trials this is just like assuming the cute girl is an air-head without so much as a conversation.

Who are these guys anyway? You expect better from NIST.

Re:"Too fast to be true"

[Anonymous Coward]

what if they were optimized? would sleep(10) make them finalists?

Re:"Too fast to be true"

[Omnifarious]

Tangential? What are you talking about? The cryptographic uses of hashes are the whole reason SHA-1, SHA-2 224,256,384,512 were created in the first place. It's also the reason the competition is being run.

I would also submit that your use case is not as security insensitive as you might think.

Re:"Too fast to be true"

[Anonymous Coward]

There are some cryptographic uses of hashs but they are tangential for the most part.

This is the Secure Hash Algorithm - 3 selection competition. The cryptographic uses are pretty much at the forefront of the judges' minds.

A perfectly acceptable hash for error correction purposes can be doomed for cryptographic purposes. For example, being able to find "a different plaintext input that would have given the same hash as input X" is not a problem for an error correction hash provided that the pair of inputs are not similar (and so transmission errors are unlikely to turn one into the other). However it would make many uses of cryptographic hashes totally unviable.

Re:"Too fast to be true"

[nedlohs]

You believe what you read in a slashdot summary???

Re:"Too fast to be true"

[Skuto]

"We preferred to be conservative about security, and in some cases did not select algorithms with exceptional performance, largely because something about them made us “nervous,” even though we knew of no clear attack against the full algorithm."

William Burr, NIST

good!

[larry bagina]

Our lawyers won't let us convert our svn repositories to git since git uses SHA-1, which is known to be vulnerable to collisions. Hopefully, they pick a SHA-3 soon!

Re:good!

[John Hasler]

The only thing you get from SHA-2 or SHA-3 over SHA-1 is better probability of not colliding, and a more difficult time of deliberately creating a collision.

And the risk of accidental collisions is negligible while deliberate collisions are irrelevant to the use of hashes in Git as they have no security-related function there.

Re:good!

[Anonymous Coward]

The only thing you get from SHA-2 or SHA-3 over SHA-1 is better probability of not colliding, and a more difficult time of deliberately creating a collision.

And the risk of accidental collisions is negligible while deliberate collisions are irrelevant to the use of hashes in Git as they have no security-related function there.

Actually SHA-1s do have a security related function. I don't remember where I read this explanation, but it is plausible, although difficult.

SHA-1s are used to uniquely identify the object in GIT. An attacker could write a new patch and generate a collision for it. The attacker would then submit the good patch and get the maintainers to accept the patch and sign it with their GPG key. The attacker would then create a rogue mirror site and replace the good patch with the malicious collision. Because the SHA-1s would match this would not invalidate the GPG signature of the maintainers. If anyone went to the rogue site they would receive a poisoned copy of the git repository that appears cryptographically valid.

Now the collision would be pretty easy to see if the replaced object was plain source code, because generating a collision usually involves writing out a whole bunch of garbage to a file. However if the replaced object was a binary blob for a driver or a checked in library or something, then it would be much less obvious.

Re:good!

[Mysteray]

An attacker could write a new patch and generate a collision for it. The attacker would then submit the good patch and get the maintainers to accept the patch and sign it with their GPG key. The attacker would then create a rogue mirror site and replace the good patch with the malicious collision.

That would definitely win you the prize for "the most absurdly over-complicated and difficult way of pwning a Linux box".

Why don't you just watch [Full-disclosure] for the 0-day of the week like everyone else?

The bear only has to be faster than the first of the two hunters.

Bah!

[jd]

None of the good names survived!

Still, there was a lot of debate on the SHA3 mailing list governing the criteria as it was felt that some of the criteria were being abused and others were being ignored. I, and a few others, advocated an approach where the best compromise solution was the "winner" for SHA3 but the runner-up that was best for some specific specialist problem (and still ok at everything else, since it's a runner-up, and also free of known issues) would then be considered the winner as "SHA3b". That way, you'd also get a strong specialist hash. The idea for this compromise was due to SHA2 not being widely adopted because it IS ok for everything but not good for anything. Some people wanted SHA3 to be wholly specialised, others wanted it to be as true to the original specs as possible, the compromise was suggested as a means of providing both without making the bake-off unnecessarily complex or having to have a whole parallel SHA3 contest for the specialist system.

The main problem with the finalists is the inclusion of Skein. The use of narrow-pipe algorithms has been widely criticised by people far more knowledgable than myself because it violates some of the security guarantees that are supposed to be present. The argument for Skein is that the objection is theoretical.

Yet another crappy summary...

[msauve]

Curiously, some of the faster algorithms were eliminated as they were felt to be "too fast to be true."

Not only is the claimed quote ("too fast to be true") nowhere to be found in the linked article, but there isn't even a basis for that claim.

Re:Yet another crappy summary...

[udittmer]

Not only is the claimed quote ("too fast to be true") nowhere to be found in the linked article, but there isn't even a basis for that claim.

There is in fact a basis for that claim, even if it isn't mentioned in that particular article. See http://crypto.junod.info/2010/12/10/sha-3-finalists-announced-by-nist/ for more about that.

Re:Yet another crappy summary...

[Skuto]

>Not only is the claimed quote ("too fast to be true") nowhere to be found in the linked article, but there isn't even a basis for that claim.

People read the articles? That's new.

My original post had no links, because the original announcement was on a password protected mailing list. If you read that (it's been posted elsewhere since), you will see the statement it refers to.

Some fast algorithms were eliminated based on partial attacks or observations that are not real attacks. This means there's a potential we miss out on a faster but good algorithm, because most partial attacks never make it to full attacks. Using this to eliminate ciphers means the selection is a bit of a black art (that shouldn't surprise insiders too much).

Some people were advocating the opposite approach, namely to just pick the fastest/smallest ciphers and then see which one wasn't broken at the end of the process. Clearly, NIST is taken a very different approach. And given hash function history, an understandable one.

Re:SHA-SHA-SHA-KE YOUR BOOTY !!

[larry bagina]

That's funny, but SHAKEs ("elder") are arabic, SHAs ("king") are persian/iranian. There is a difference and they get mad when you confuse them. They all look alike to me, but whatever.

For those of us that didn't read the article, wikileaks revealed that the SHA has terminal cancer and will die soon. That's why they're looking for a new SHA-3. The SHA is kind of like the Dalai Lama, but with a unix greybeard. I'm glad they've narrowed down the candidates. Hopefully, the next one will bring peace in the middle east.

Re:SHA-SHA-SHA-KE YOUR BOOTY !!

[Martin Blank]

SHA-1 was not "cracked." A weakness was found in it that reduced the strength by 2^11 to 2^69 instead of 2^80 when conducting preimage attacks. Even on specialized hardware, this is not a practical attack, requiring thousands of years to come up with a message that hashes to the same value. Papers since then have found variations on the weakness, but they have only been demonstrated in reduced-round variants of SHA-1, not in full implementations due to the processing power required.

The weakness was recognized as a potential problem, hence the recommended move to SHA-2, particularly the stronger variants of it. The SHA-3 competition was born out of concern that SHA-2 could suffer from similar weaknesses, which may doom the SHA-3 contestants that draw from SHA-2 at a political level if not a technical level.

Skein break by Bernstein

[Skuto]

UNOFFICIAL COMMENT: Cryptanalysis of Skein

http://cr.yp.to/hash/skein-20101206.pdf

Re:Skein break by Bernstein

[Anonymous Coward]

...that's a joke. :)

CubeHash was eliminated due to poor short-message MAC performance. A parameter tweak could have fixed that, but was too late for the selection to change their mind, and would have had security implications.

Still, it was a fascinating design that degraded extremely well to reduced versions for some fascinating simplified cryptanalysis. I think we all learned a lot from it.

Skein's ThreeFish needed a rotational constant tweak. That's done, and it's through.

Now that the suspiciously fast has gone, I suspect they'll choose the fastest which survives with no severe attacks. My money's on Skein (which, if it survives the competition as a finalist with no severe attacks, I will use anyway because it has a native tree-hash mode which is extremely useful to me) or at a push Keccak (which can derive advantage from AES round function hardware acceleration, at the cost of using the AES round function, which is a bit like putting your eggs in one possibly dodgy basket).