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"

[jewelises]

When you want to slow down a fast hash you just do it a lot of times. See PBKDF2, for example.

Re:"Too fast to be true"

[Fry-kun]

FTFA: "Cryptologist Ron 'The R in RSA' Rivest withdrew his MD6 process - it was highly-rated but conspicuously sluggish"

Someone simply misread or misunderstood "sluggish" for "too fast"

Re:"Too fast to be true"

[nedlohs]

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

Re:"Too fast to be true"

[Surt]

Technically, if your hash algorithm is too fast, it gets easier to brute force. So it isn't completely unscientific.

Re:"Too fast to be true"

[Anonymous Coward]

checksum != hash table function != cryptographic hash != hashish

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

Re:"Too fast to be true"

[moderatorrater]

It's not unreasonable to leave out an algorithm that's as secure mathematically as the others as far as we can tell but that has a concerning characteristic. Previously, they've eliminated competitors for having simple mathematical representations and things like that. Since those algorithms were no more secure than the ones without the worrisome attribute, they could be eliminated without much problem. Remember, these are security guys, so they're paranoid about stuff like that.

I'm a little curious about that portion of the summary, though, since one of Skein's distinguishing features is that it runs nearly as fast on a processor as it would on specialized hardware due to the way that it's designed. If those algorithms were much faster than that then I would probably agree with the committee that the speed was suspicious.

Re:"Too fast to be true"

[LainTouko]

If you're only concerned about accidental corruption, you should use a CRC, which will be much faster than a cryptographic hash. Spending a load of extra CPU time on acquiring good cryptographic properties is silly if you're not interested in any cryptographic properties.

Re:"Too fast to be true"

[Stellian]

Well that's mathematically sound reasoning!

In cryptographic lingo, it means that although the algorithms aren't broken, they have a small security margin, for example 14 of 16 rounds are broken. Since attacks always get better, it's a good idea to pick an algorithm twice as slow with, say, 32 rounds, then to be on the bleeding edge. Sure, you get twice the speed, but you are only one good research paper away from hell.
In regard to AES, it's largely agreed in the crypto community that NIST went for the performance, and we now trust an algorithm with a comparatively low security margin. If advances in cryptography continue at the same rate as the did in the past 30 years, then surely AES will be insecure 30 years from now [citation needed]. That's not sound mathematical reasoning, but it is sound pragmatic reasoning to reject an algorithm that's "too fast".

Re:"Too fast to be true"

[kasperd]

Technically, if your hash algorithm is too fast, it gets easier to brute force.

Let's assume somebody came up with a hash function that is 10 times faster than what we would otherwise use, and let's assume it is just as secure except from the minor detail that by being 10 times faster it also becomes 10 times faster to perform a brute force attack. If those assumptions are true, then instead of discarding it altogether, we should find a way to make the brute force attacks slower again. Making the algorithm slower would of course achieve that, but that's not a good idea because it would become less useful. Instead we can use the same principles for the hash function, but increase the size of the output with one byte. That extra byte makes the time to find a collision 16 times larger (and preimage attacks takes 256 times longer). But why stop at one byte, we could make the hash value a lot larger. Even if that meant it would slow down by a factor of two, it would still be five times faster than the alternatives and a lot more secure.

This is exactly the reason why modern hash functions no longer output just 128 bits. These days nobody in his right mind would try to design a new cryptographic hash that output less than 256 bits.

Re:"Too fast to be true"

[amorsen]

The "something" which made them nervous wasn't the speed, and it wasn't necessarily the same for each algorithm...

Re:"Too fast to be true"

[kasperd]

That only matters if the hashes output is perfectly distributed. Unless they have some proof of that, a 256 bit hash is actually much less than 256 bits of security.

That's part of what this whole process is about. If anybody can show that one of the hashes has a skewed distribution of the outputs, then that hash is very likely to leave the competition. However giving a proof that a hash has a uniform output is not easy unless it has a very simple structure, that is likely to suffer from other weaknesses. Even proving that all 2^256 combinations are possible is difficult, because if there was a constructive proof for that, then you would have given a preimage attack.

Now if you start from a 4K hash, I'd stop worrying about brute force.

That large a hash value would make a lot of the use cases totally impractical. And increasing the size doesn't guarantee you a better hash. I think the current peer review process does more for the security than increasing the size would.

Sure, if the same people would go through the same process to design a hash with a 4K output, then it probably would also end up being very collision resistant, but also very slow. Most people think it is more useful to spend the time on designing a hash with a smaller output.

Re:"Too fast to be true"

[kasperd]

OpenBSD slowed an internal hash function down to slow possible brute force attacks against the passwd file

A slower implementation of the same hash doesn't add any security. You should expect the attackers to use the fastest possible implementation of the hash. Some uses of hashes for passwords will apply the hash multiple times (each iteration should use both the output from the previous iteration and the password itself). This makes the calculation equally slower for both the system using it and the attackers. The purpose of this is not to protect against weaknesses in the hash, but rather to protect against weak passwords. This is a very special use case for a hash function, and the requirements are quite different from what hash functions are usually used for.

Re:"Too fast to be true"

[mbkennel]

Read the above very very carefully. This is superb government misdirection.

The reader is encouraged to infer that the exceptional performance made them nervous. That is not what he claimed.

I suspect (without insider knowledge) that forthcoming statement would be:

"We preferred to be conservative about security, and in some cases did not select algorithms with exceptional performance, largely because an attack and theory known to government scientists but not to the public can crack a variant or limited case. Even though we knew of no clear attack against the full algorithm we did have suspicions of potential strategies in the future based on this knowledge that I know that you don't. "

Re:"Too fast to be true"

[swillden]

Actually, to defeat a hash, you need only defeat the last repetition, so, no, iteration doesn't help.

Cite?

The sort of attack you're talking about, where speed is a factor, is a dictionary attack. The attacker has reason to suspect that the input is from a relatively small set (e.g. it's a human-selected password) and it's therefore feasible to hash every element in the set and compare each output with the known hash value. If the hash is fast enough and the set is small enough, this may be feasible.

One way to defeat that attack is to increase the set size, but in many cases (like passwords) that's not feasible. So another way to defeat the attack is to use a slow hash, because then testing each dictionary entry will take long enough that searching the dictionary isn't practical. On the other hand, the computation required to compute one hash during a login is fast enough to be acceptable.

So, under that scenario, look at iterating your fast hash to create a slow one. How do you "defeat the last repetition"? What does that even mean? Are you assuming that you can actually reverse the hash, a pre-image attack? If that's the case, then brute force is the least of your worries. And without that, what does it even mean?

Suppose you could somehow find out what the output of the n-1 iteration on the actual input was. What have you achieved? Well, to find out which input to iteration 1 maps to that n-1 iteration output you need to... search your dictionary applying n-1 iterations to each entry.

Either you're talking about something completely different, or you're up in the night.

Bruce Schneier

[Jackanackanoree]

Bruce Schneier helped to make skein http://www.schneier.com/skein.html

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!

[icebike]

And if they were waiting for a lawyer who understood the issue they would be waiting longer.

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!

[Omnifarious]

People are always saying "Oh, collisions aren't important for this application.". And they're almost always wrong. Stop trying to be a security expert and just quit using an algorithm when it's broken instead of coming up with excuses not to change it.

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.

Re:Bah!

[Omnifarious]

I'm really curious as to why Blue Midnight Wish wasn't selected. I've read a bunch of the papers and nobody seemed to be able to come up with any reasonable reason it was weak, and it's very fast.

Re:Bah!

[jhnphm]

In addition, the NIST email said "No algorithm survived to become a finalist that did not have a clear round structure that could be readily adjusted to trade security for perfomance." This probably refers to BMW.

Re:Bah!

[TheRaven64]

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 would entirely defeat the point of the competition. The purpose is to select one, good, cryptographic hash that will be called SHA-3 and can therefore be used in places where US government regulations require a strong cryptographic hash.

The other algorithms aren't going away at the end of the competition. If you have a specialist purpose where one of them is better suited than SHA-3, then you can still pick your own algorithm. It just won't be called SHA-anything.

Re:Skein

[Omnifarious]

I've been following the progress on the SHA-3 Zoo and I haven't seen anything indicating Skein is broken. I've been following Skein with particular interest because I like how it can be tweaked in various ways to serve particular needs.

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 !!

[Anonymous Coward]

Sheik Yerbouti?

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

[morgan_greywolf]

For those of us that didn't read the article, wikileaks revealed that the SHA has terminal cancer and will die soon.

SHA-1 has had terminal cancer a very long time: it was cracked over 4 years ago. Anything Wikileaks may have revealed about SHA-1 is very old news indeed.

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.

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

[Anonymous Coward]

Wrong. The same year (2005) improvements reduced the complexity to 2^63. See http://www.rsa.com/rsalabs/node.asp?id=2927

Also, the attack was for finding collisions, not preimage attacks. A preimage attack would be more devastating, but collisions still allow for faking certificates and checksums, depending on the protocol.

SHA-1 might not be broken, but it's about as close to being broken as any crypto primitive can be without being official broken. Everybody should have begun the process of moving away from SHA-1 in 2005.

Re:Skein

[Anonymous Coward]

Woosh!

Definition of skein: A loosely-wound, oblong ball of yarn

Re:One of the many, many reasons why IANAL

[Zero__Kelvin]

"I'm going to have to ask for more concrete demonstrations of that claim than "Linus said so" before I believe it."

Damn. I was just about to go to sleep too. Now I have to stay up all night worrying what you think, and how I'm going to do that thinking for you 8-(

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

Re:Use them all!

[Mysteray]

It might help, it might not help much, it might make things slightly worse. It will be measurably slower and not measurably more secure.

You'll be on your own with it because it will not be an interoperable, accepted standard. Hashes are often used for data shared by multiple parties.

Re:"password"

[Mysteray]

http://en.wikipedia.org/wiki/SHA-2

So for SHA-256 the starting constants are the "first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19" and "first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311".

That only takes a few words to explain, and most of it is dictated by the design (e.g., "32 bits"). The hash designer is signaling that he only had freedom to select a few general concepts here and there.

http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number

You can be sure that the people who approve these kinds of things are pretty paranoid about the possibility of someone sneaking a back door in there. If the constants had been proposed as "bits from the base-2 representation of pi starting at bit position 2364826687681" there would have been some serious eyebrow raising.

Still, it's a pretty cool find. I can't wait for the upcoming holiday party, I will surely impress the ladies with that!

Re:git objects don't live in a vacuum

[pavon]

Here is a collection of real world implementations of a collision attacks in which two legitimate executable binaries were created to have the same MD5 hash and size.

Here is the post script collision attack that Omnifarious was referring to. Both files are the same length and have the same MD5 hash. Furthermore, postscript is a turing complete programing language, with as picky of a syntax as C.

All the collision attacks I have seen used fixed length blocks in both files which are modified. Inserting a fixed length comment block into a piece of code is not hard.

Preimage attacks (where you only modify one file not both) are harder, and to date, not even MD5 has any known practical preimage attacks. But if it did, it would be trivial to implement it by tweaking a block comment in a source code file, or a data segment in a binary file. There is no challenge there whatsoever.

It took me less than a minute to find those on Google. I don't expect people to know everything, but if you are going to run around insulting people and being an asshole, you better know what the fuck you are talking about.