SHA-3 Finalist Candidates Known 194
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."
"Too fast to be true" (Score:5, Insightful)
Well that's mathematically sound reasoning!
Re:"Too fast to be true" (Score:5, Insightful)
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: (Score:2)
Beauty contest? Nah, this is fantasy football. Maybe Dancing with the Stars.
Anybody know what the point spread is on this SHA-3 hash competition? I'd like to get a bet down before the line moves.
SHAs decrypts just like a woman? (Score:2)
Re:"Too fast to be true" (Score:4, Insightful)
You believe what you read in a slashdot summary???
Re:"Too fast to be true" (Score:5, Informative)
"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: (Score:3)
The "something" which made them nervous wasn't the speed, and it wasn't necessarily the same for each algorithm...
Re: (Score:3)
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
Re: (Score:3, Insightful)
Technically, if your hash algorithm is too fast, it gets easier to brute force. So it isn't completely unscientific.
Re: (Score:2)
Technically, if your hash algorithm is too fast, it gets easier to brute force. So it isn't completely unscientific.
Only if the input is small, which translates to "only if the protocol designer is clueless". Also, you can always make a fast algorithm slower by iterating it, so your point is irrelevant.
Re: (Score:2)
Actually, to defeat a hash, you need only defeat the last repetition, so, no, iteration doesn't help.
Re: (Score:3)
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 no
Re: (Score:3)
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 s
Re: (Score:2)
By brute forcing, I assume you mean find another input that hashes to a predetermined value, not finding two inputs which happen to hash to the same value. Without some mathematical attacks, this very unlikely, no matter how fast the hash algorithm is.
A slower hash will make dictionary attacks on salted password tables more difficult - but generally you would simply run the hash many times to increase the computational load for an attacker. Again, the raw speed of the hash algorithm is unlikely to make mu
Re: (Score:3)
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. Ev
Re: (Score:3)
I'm a little curious abo
Re: (Score:3)
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 attack
Re: (Score:2)
Yeah I know that the increase is exponential (based on the string length) - but if you only do dictionary words... you'll still hit a few passwords.
Re: (Score:2)
Short strings are supposed to be salted anyway.
Re:"Too fast to be true" (Score:5, Insightful)
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" (Score:5, Informative)
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: (Score:2)
Re: (Score:2, Insightful)
checksum != hash table function != cryptographic hash != hashish
Re: (Score:2)
!= hash browns :(
Re: (Score:2)
Re: (Score:2)
You often have a cryptographically secure and reasonably fast hash algorithm available in some library, no matter what you program for. It's easier to just pick that by default instead of spending a lot of energy on developing and debugging something which might not end up all that much faster or smaller in the end. Skein is in the region of 6 cycles per byte on modern Intel CPUs. That should be fast enough for almost all uses. SHA is slow on modern CPUs, but even that is often fast enough.
Re: (Score:3)
Re:"Too fast to be true" (Score:4, Funny)
what if they were optimized? would sleep(10) make them finalists?
Re: (Score:2)
Re: (Score:3)
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: (Score:2)
Wait, so you're saying it was slow?
Re: (Score:3)
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
Bruce Schneier (Score:2)
Re: (Score:2)
Re: (Score:2)
That may well be true -- djb is one of the smartest guys out there -- but if he hasn't provided the proof to either NIST or the Skein team, it shouldn't really factor into the results.
Skein break by Bernstein (Score:4, Informative)
UNOFFICIAL COMMENT: Cryptanalysis of Skein
http://cr.yp.to/hash/skein-20101206.pdf [cr.yp.to]
Re:Skein break by Bernstein (Score:4, Informative)
...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: (Score:2)
>...that's a joke. :)
No shit!
>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).
Keccak has no relation to AES except for one of the authors, and is a new design. I think you are confusing it with another hash.
It has strong advantages over Skein in hardware and embedded platforms. In fact, I think Skein is weak enough there compared to the others that
good! (Score:3, Funny)
Re: (Score:2)
Isn't this the sort of decision that the IT staff take?
Re: (Score:2)
One of the many, many reasons why IANAL (Score:2)
That makes perfect sense. Better to use an SCM that gives no assurance that what you get back is the same as what committed [youtube.com] than use one that was designed in large part to fix that known problem with Subversion, and has been used to make hundreds of thousands of changes to one of the biggest software products on the planet without any such problem.
Re: (Score:3)
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-(
Re: (Score:2)
This is covered in the video. If you can't be bothered to watch and learn, don't expect others to go out of the way to teach you.
Re: (Score:2)
Re: (Score:2)
That issue has been debated and refuted before git even existed: http://www.monotone.ca/docs/Hash-Integrity.html [monotone.ca]
There's also venti of plan9 that uses SHA-1 for content addressing: http://en.wikipedia.org/wiki/Venti [wikipedia.org]
But of course, they must be all wrong.
Re: (Score:3)
And if they were waiting for a lawyer who understood the issue they would be waiting longer.
Re: (Score:2)
I don't know, there's been several cases where lawyers were arguing about the possibility of false DNA matches, which somewhat amounts to the same thing.
Re: (Score:2)
Collisions are a natural necessity of a hash function.
Not necessarily, no. If the hash is bigger than the hashed data, that's not a certainty.
And yes, hashes longer than the hashed data can be useful too. You don't have to look further than /etc/shadow or a .htpasswd file for practical examples.
Re:good! (Score:4, Insightful)
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! (Score:5, Informative)
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: (Score:3)
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.
It will never work (Score:2)
If you use source code it will not compile. If you use a blob it will not run. Even if those things were not true, whatever you came up with would certainly not do what you wanted it to do.
Re: (Score:2)
That's an ignorant defense. There is a really nice example of someone creating two Postscript files that both generate perfectly intelligible pages that contain the same hash. Doing this and still hiding the exploit just requires sticking it in code that nobody will review. You have the exploit code and the non-exploit code in the same file and have a decision based on a bunch of random garbage that's different in the two files.
Code is NOT English prose (FTFY) (Score:2)
Re: (Score:2)
I google for 'md5 postscript attack' and found this: Hash Collisions (The Poisoned Message Attack) [uni-mannheim.de]. Using this technique they were able to make either document say exactly and precisely what they wanted it to say. The postscript merely makes a decision about what display code to run based on the contents of some garbage in the middle of the file that's different in each file. The rest of both files are the same.
git objects don't live in a vacuum (Score:2)
Re: (Score:2)
So you have a situation where an attacker may substitute a patch with a malicious patch. That may or may not invalidate other hashes, depending on several circumstances of the attack, which are basically speculation. You can now either simply change the hash function, eliminating the problem, or ignore the problem and hope nothing will go wrong. Which option is better from a security standpoint?
Re: (Score:2)
There is no such situation. I am simply trying to explain why that is true. Your argument is that we should change from technique A to technique B to fix the situation where technique A works already ;-)
Re: (Score:2)
Unfortunately, the links to the postscript files in question are no longer valid. :-( If I recall correctly though, the blocks of garbage in the middle were exactly the same size in both files.
Re: (Score:2)
Your argument bases upon the assumption that the attacker can not generate a malicious patch the same size as the original patch. That may or may not be true, depending on how the attack works. And in security questions, it's usually better to go with the more pessimistic assumption.
Re: (Score:2)
Mod parent up and grandparent down. If you have a break and can generate hash collisions, making sure its the same size tends to be the EASY part of the break.
Re: (Score:2)
Re: (Score:2)
No, you're thick. Breaking SHA-1 is the difficult part, the things you keep bringing up are trivial in comparison.
Re: (Score:3)
Here is a collection of real world implementations [mscs.dal.ca] 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 [uni-mannheim.de] that Omnifarious was referring to. Both files are the same length and have the same MD5 hash. Furthermore, postscript is a turing complete [wikipedia.org] 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
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
That isn't an issue at all. Most collision generating attacks append filler data to the end of the desired file to get the desired hash. For source code you just insert the filler data in comment at the end of the file. It is a trivial modification to the existing algorithms.
Re: (Score:2)
Re: (Score:2)
Needing to match the length of the original object doesn't make the problem that much harder (unless the desired code is already close in length to the original code). In fact many collision attacks are designed for fixed size inputs, because it makes things easier.
Requiring valid formatting of the file is not a hard problem compared to the much more fundamental problem of finding a practical preimage attack in general. If SHA-1 were broken (it isn't yet), then it would certainly be plausible to attack git
Re: (Score:2)
They don't need to modify any internal files. You just submit a file to a repository and get the maintainers to check it in. The file has to look innocuous to any inspection. Once they do that, you put instead a rogue version of that file with the same hash and size on your own mirror, and get somebody to use that mirror. You make sure the rogue file is signed by the official maintainers so that end-users trust your mirror. Since the hash matches you can just extract their signature and put it on your
Re: (Score:2)
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.
That assumes people would actually 1) look at the source code and 2) notice the problem.
In most source code you can insert comments. So the whole bunch of garbage can be commented out.
Re:good! (Score:4, Insightful)
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.
Skein (Score:2)
Re: (Score:3)
I've been following the progress on the SHA-3 Zoo [tugraz.at] 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.
Re: (Score:2)
Well, that's amusing. But without details, it's only slightly better than saying "Skein sucks!".
Re: (Score:2, Insightful)
Woosh!
Definition of skein: A loosely-wound, oblong ball of yarn
Re: (Score:2)
It was broken, but it has been fixed.
Actually, Threefish was broken (which Skein relied upon.)
Re: (Score:2)
Is this the attack by djb that even he hasn't posted clear details of? Or is this a previous attack that Schneier and company solved with their 2nd round tweaks that improved diffusion?
Re: (Score:2)
I was referring to the previous attack which was solved in the 2nd round tweaks.
Bah! (Score:5, Interesting)
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: (Score:3)
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: (Score:2)
Re: (Score:2)
Which specialist problem would SHA3b have been for? Any random specialist problem or is there a particularly important specialist problem? The former doesn't sound very useful, but I don't know what the later would be.
Re: (Score:3)
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.
Yet another crappy summary... (Score:4, Informative)
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... (Score:5, Informative)
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/ [junod.info] for more about that.
Re:Yet another crappy summary... (Score:5, Informative)
>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 !! (Score:5, Funny)
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: (Score:2, Funny)
Re: (Score:2)
SHA-1 has had terminal cancer a very long time: it was cracked over 4 years ago [h-online.com]. Anything Wikileaks may have revealed about SHA-1 is very old news indeed.
Re:SHA-SHA-SHA-KE YOUR BOOTY !! (Score:5, Informative)
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: (Score:2, Informative)
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 fro
Re: (Score:2)
Yeah, must be noobs. They forgot the ROT13 step...pfffst, bloody amateurs.
Re: (Score:2)
The greater noobishness here would be storing the unsalted hash in plaintext.
Re: (Score:2)
Dunno. I had meant to also link it to the article, but I forgot.
I was thinking that it may not be a coincidence. What if, while developing the SHA256 algorithm, they needed an arbitrary starting point or seed, like deciding where to begin drawing a circle? And so, whoever made that choice chose the one that gave this hash for this string? And what if someone did something similar in the SHA3 algorithm? That would be cool to find.
But, I don't know how the SHA2 algorithms work, and there probably is not any a
Re: (Score:3)
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_sl
Re: (Score:2)
As it happens, you're doing it wrong, because the output of sha256sum is a hex string, not binary. You should have realised because 256 bits in base64 should be ceil(256/6) = 43 characters long, not the ~90 you get.
This produces the correct result:
$ echo -n password | sha256sum | perl -ane "print pack('H*', @F)" | base64
XohImNooBHFR0OVvjcYpJ3NgPQ1qq73WKhHvch0VQtg=
Re: (Score:2)
For extra security, use each of them twice!
Re: (Score:3)
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.