Slashdot Mirror
SHA-3 Winner Announced
An anonymous reader writes "The National Institute of Standards and Technology (NIST) has just announced the winner of the SHA-3 competition: Keccak, created by Guido Bertoni, Joan Daemen and Gilles Van Assche of STMicroelectronics and Michaël Peeters of NXP Semiconductors. 'Keccak has the added advantage of not being vulnerable in the same ways SHA-2 might be,' says NIST computer security expert Tim Polk. 'An attack that could work on SHA-2 most likely would not work on Keccak because the two algorithms are designed so differently.' For Joan Daemen it must be a 'two in a row' feeling, since he also is one of the authors of AES."
It's time to start building some new rainbow tables?
Congratulations to the whole Keccak team! I happen to know some of them in person and have all confidence that this is an excellent piece of work. True quality always wins in the end.
Out of all the ways a hash function could be vulnerable, not being vulnerable to a few of them hardly looks impressive without more context... But what do I know, I'm not a crytographer.
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
Having a good SHA algorithm is a good thing. Yes, hash collisions may not seem to be something that can happen often, but if there is a chance that one can make a document saying "hell no" be changed to "yes, definitely", that can bankrupt a company.
Hashes also have other uses, especially as "bit blenders", so if one is able to figure out a way to decrease entropy, then keys generated from a device like /dev/random can be significantly less secure.
Each crypto algorithm is important. I just wish NIST would not just pick one candidate, but perhaps 2-3 at a time [1]. The reason for this is that if something happened that made the algorithm insecure, the standard libraries would have a backup. It also means that embedded controllers that are made to the standard wouldn't have to be chucked and replaced should one algorithm be cracked.
[1]: Not just hashing, but encryption as well. I wish NIST went wish not just Rijndael, but Serpent and Twofish for a standard. Similar with not just going with just RSA, but RSA, Merkel, DSA, ElGamel, and elliptic encryption. That way, should an attack like TWIRL or quantum computers make RSA pointless, people can switch over to Merkel or another algorithm without needing a hardware upgrade. Plus, for high security work, multiple algorithms can be cascaded [2] to ensure that one weak link won't compromise everything.
[2]: No, three 256-bit algorithms will not get you 768 bits. In reality, you end up with 258 bits of security. However, if one of the algos ends up being broken and only offering 32 bits of unique keys, the other two would continue to keep at least 256 bits of keylength.
According to the (extensive) benchmark data here, this is even slower than the previous SHAx.
Somewhat disappointing, when both Skein and Blake are about twice as fast, and appear to be perfectly acceptable from a security standpoint. (From what I have read anyway.) So, out of curiosity, what is the argument for keccak that puts it ahead?
Thank you very much for your great contribution to the quality of the discussion. It always helps to have people who know how to keep Slashdot up to the right level.
Perhaps this secure hashing algorithm was chosen above the others because it was more secure than the others?
NIST have not yet published the details, but the press release is pretty clear concerning speed: HW implementations of Keccak are much faster than equally large/costly HW implementations of the other candidates.
Since none of the remaining candidates in round 3 where broken this is probably not the case. I think that the simplicity of the design (which makes analysis more easy) was the real reason. However we do not know yet since the report from round 3 hasn't been released yet.
We do need a new UI for Windows GN. I can't even unlock the password screen without the fingerprint reader!
Who would go out of their way to use a new and bleeding edge hash function, but not employ basic best practices like salting and key stretching?
Are you targeting hash function hipsters?
' For Joan Daemen it must be a 'two in a row' feeling, since he also is one of the authors of AES."
As someone who works in cryptography (no, I'm nothing like these guys, never will be) there are a limited number of people in the world qualified to design these algorithms. They are ALWAYS going to be the ones involved in the design process. Bruce Schneier is another person who is ALWAYS going to be in these sorts of competitions. There may be a new guy come in and an old guy go out over time but in general its going to be a select few people that have the type of mind to work with this sort of stuff.
Persistent Volume manager for Kubernetes - https://github.com/dwimsey/openshift-pvmanager
How can a strange Balinese dance perform better than SHA2 as a hash algorithm. I'm sure that hash had something to do with the creation of the Kecak dance, but not the cryptographic sort.
Sorry for the newbie question but should I replace:
INSERT INTO users SET username='admin', password=sha1('********')
for:
INSERT INTO users SET username='admin', password=sha3('********')
That is a strange criteria though, as 99.9% of the people using SHA3 and depending on it's security will use a software implementation. Practically the only people who deal with hardware implementations anymore are those trying to break a cryptosystem. Of course all the speed measures for the SHA-3 contenders (hw and sw implementation) are relatively small constant multiples/divisors of SHA2, so it really isn't a big deal from a security or convenience factor.
Looking forward to reading the final report.
I mentioned that Aesop said it best, when he said 'those were sour grapes anyways,' but I guess I got modded into irrelevance. I guess that's what happens when you frame the Chuck Norris of cryptography in a negative light.
(also interesting coincidence, AESop)
Security is only one of the factors. Speed is one of the big reasons AES was chosen IIRC.
All(?) Via CPUs have SHA and AES hardware acceleration provided by Via's 'Padlock'.
Users != uses. I doubt the NIST would consider the speed of HW implementations so carefully if it didn't matter much. Mainframes come with heavy-duty hardware crypto assists.
As always, all IMO. Insert "I think" everywhere grammatically possible.
The same holds for security processors in payment cards etc. They all have dedicated HW accelerators on board.
I just wish NIST would not just pick one candidate, but perhaps 2-3 at a time [1]. The reason for this is that if something happened that made the algorithm insecure, the standard libraries would have a backup. It also means that embedded controllers that are made to the standard wouldn't have to be chucked and replaced should one algorithm be cracked.
As with anything, be careful what you wish for. I've seen successful attacks on protocols that support multiple versions or algorithms, made possible by devices that support them all for various compatibility reasons. Let's suppose someone does discover an attack on SHA-3A but SHA-3B remains secure. Everybody switches their servers to SHA-3B. A flexible protocol might allow an attacker to generate an error that forces clients to re-hash their passwords with SHA-3A. This has happened more often than you might think; NTLMv2 implementations falling back to NTLM being one of the more spectacular of the exemplary failures.
Your example creates a theoretical weakness - a failure in either SHA-3A or SHA-3B could put such a device at risk. If you try to prevent this by building in an environmental protocol switch, so the device could be set in the future as to which algorithm to use, why not initially design the device to support loading a more modern algorithm in the future?
John
Personally, I was hoping Skein would win; it was the most flexible and, in my opinion, the most innovative of the finalists. Anyway, congrats to the winner. This selection will hopefully make good hashing popular and widely-implemented (and therefore convenient enough that those in information industries will slowly adopt it).
If you try to prevent this by building in an environmental protocol switch, so the device could be set in the future as to which algorithm to use, why not initially design the device to support loading a more modern algorithm in the future?
The algorithms are implemented in hardware, e.g. Intel's AES-NI. If rijndael is found to be weak, you can't just make a that CPU do Twofish in hardware. If Intel implemented rijndael, twofish, and serpent in hardware, then if an attack is found on rijndael there would be somewhere to go. If an app becomes dependent on AES-NI and it's broken, then there's a 2-year waiting period before anything can be done about it. Which is essentially forever.
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
Ah, some decent achievement for Belgium.... Usually the nationallity is always mentioned in such achievements but noo, not in our small country. We do have a bit of a problem with patriotism :s
"Having a good SHA algorithm is a good thing."
still using the ATM machine?
Not true, the x86 has a hardware implementation of AES ... https://en.wikipedia.org/wiki/AES_instruction_set
It's not unreasonable for hardware accelerators for SHA-3 to get embedded into normal microprocessors if it's cheap enough.
"Having a good SHA algorithm is a good thing."
still using the ATM machine?
Yes, I use it to withdraw money from my ISA account. I might by myself a new PC computer.
It was chosen because of speed on a variety of hardware (desktop/server CPUs, embedded, smart cards, ...), because it has very low gate/memory requirements (making it implementable on really small stuff), because it's secure, and because the design is very different from SHA-2.
The choice makes it clear that the last was an important criterion. When the SHA-3 competition was announced, everyeone expected SHA-2 to fall soon. It didn't, so likely SHA-2 won't go away anytime soon. However if it were to be broken, the replacement is already lined up.
Without that consideration, BLAKE was a clear favorite, IMHO.
In addition to what plover noted, an important problem (especially for hardware) is cost and complexity. And we all know how more code generally leads to more bugs.
Why go through the trouble of finding a hardware efficient function that can be implemented in smart cards and embedded devices, and then more than triple the footprint by chucking them all in?
Nothing is stopping anyone from implementing SHA-3 finalists to their heart's content for their own software, but putting additional algorithms in silicon has a real cost.
Having a good SHA algorithm is a good thing. Yes, hash collisions may not seem to be something that can happen often, but if there is a chance that one can make a document saying "hell no" be changed to "yes, definitely", that can bankrupt a company.
Hash collisions happen all the time.
You're enormously reducing the number of bits of information present, so you will get collisions (unless you've tuned the hash algorithm to exactly the sets of data being hashed, which is a total drag in practice). What you don't want though is the ability to say "I have the hash of something, let's easily find something else useful to me with the same hash"; preventing that is a key feature of cryptographic hashes. (Other kinds of hashes exist, where collisions are more likely between related data but the cost of calculation is much lower; there's a lot of code where that trade-off makes a huge amount of sense.)
"Little does he know, but there is no 'I' in 'Idiot'!"
However we already know that this isn't really how modern cryptography works. There would be enormous forewarning in the literature that a practical attack of some sort was coming - these things aren't made out of whole cloth by lone geniuses, they're developed, analysed and slowly implemented over time.
There are some theoretical attacks against AES for example, but nothing practical has been implemented yet, and by the time it is we'll most certainly have moved on to a newer cryptography standard.
Chip and pin (EMV) credit cards falling back to signature verification!
I guess none of the people involved speaks Spanish, because "keccak" is pronunced almost like "'qué caca!" ("what a piece of shit!")...
"Hash collisions happen all the time." Really? A 512bit hash collides "all the time"? We have systems generating tens to hundreds of thousands of 128bit GUIDs all the time for years, and don't have issues colliding. How is a 512bit hash supposed to collide regularly short of identical data?
http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo
But what a lousy name. I still say Blue Midnight Wish had a far cooler title. Yeah, yeah, I know, that's not what you pick hash algorithms for. But to judge from the number of skull-and-crossbones on the Hash Function Lounge, security has never been that high on the list, so why not go with the cool names?
http://www.larc.usp.br/~pbarreto/hflounge.html
Seriously, congrats to Keccak, although watch that inner permutation glitch.
http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Keccak_Comments.pdf
Hardware manufacturers especially like taking shortcuts that lower cost without lowering the illusion of security (even if actual security is reduced to bugger all).
My reaction is a variation of "Stop talking and take my money": Stop discussing this long enough to give me the code. Here it is: Reference and optimized code in C, from the article The Keccak sponge function family.
That is a strange criteria though, as 99.9% of the people using SHA3 and depending on it's security will use a software implementation. Practically the only people who deal with hardware implementations anymore are those trying to break a cryptosystem.
...and there you have the answer. *cue mysterious conspiracy music* :)
Coffee-driven development.
Maybe because a GUID isn't a hash ?
GUID's are kind of 'sequential' numbers based on the time and either a MAC address or a random number. By design it's (theoretically) impossible to generate the same GUID twice because either the time will have progressed in sequential calculations and/or different 'base' numbers are used when running on different hardware as to 'force' the generation happen to simultaneously.
Hash functions are based on a block of data being 'examined' and will return the same result over and over again for the same blocks of data. If the hash-result changes, the source-data must have changed, period.But! vice versa is not necessarily true : it is well possible that 2 different blocks of data return the same hash function, but are not identical and we then have a so-called Hash-collision.
If you truly believe we could safely assume that a hash represents one and only one potential data-block, you would have the ultimate compression-software in your hands ! Admittedly, decompressing would take a while because you'd have to iterate over I don't know how many blocks of random data until you find the right hash, but how often do you really need eg. backups anyway ? Just hash your entire disk, write the hash on some napkin and feel safe.
If there is one thing to be learned on slashdot, it has to be sarcasm.
You're enormously reducing the number of bits of information present
True
so you will get collisions
No
It is true that collisions must exist but if the output of the hash function is large enough then the number of inputs you would have to try to find a collision by brute force becomes unfeasiblly large even if you don't care what it's a collision with.
Finding any collision at all is considered very bad news for a secure hashing algorithm as it is often quickly extended to finding collisions with common prefixes. From there you can construct two documents in a format like pdf with very different content but the same hash, then you can get someone to sign one using the hash algorithm and their signature will verify on the other.
note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
I've seen successful attacks on protocols that support multiple versions or algorithms, made possible by devices that support them all for various compatibility reasons.
And I've seen attack ships on fire off the shoulder of Orion and watched C-beams glitter in the dark near the Tannhauser gate.
So there!
Well actually three encryptions should give you 512 bits of security, like 3-DES is 112 bits.
The NSA I am certain has been instrumental in any and all security and cryptographic testing and evaluation to ensure that they, the NSA can easily crack or decode the cypher text. Do NOT for a minute think that the winner has any leg up over the NSA experts. If it doesn't have a back door it will when finished. Any cryptographic algorithm is guaranteed to have some easy was to decode, otherwise the NSA is NOT doing their job. The only way to guarantee NSA non-involvement is get the algorithm from some non-aligned nation; Russia and China come to mind.
Hash collisions happen all the time.
Oh, really? Can you post just ONE example of a 512-bit hash collision? I mean two different pieces of data (no matter how long or short) that have the same 512-bit hash? Or even just 384-bit perhaps? 256 maybe? 224? 160?
Wouldn't it be safe to just always use multiple hashes (e.g. SHA-2 and SHA-3 and Whirlpool) and XOR the results to generate one final hash? A weakness in one of the algorithms would not weaken the combined hash. And even if *all* hashes would be effectively broken, it would still be far from trivial to forge arbitrary data that results in the same final hash.
It's called being collision resistant hash function. And its a primary security requirement for "cryptographic hash functions" such as the SHA family and MD* family of hash functions. For some we know how to produce collisions with varying degrees efficiency (MD5, SHA-1) and for some we don't like SHA2 and 3.
But collision resistance doesn't mean its invertible. In other words after you hash ur HD down there's no known efficient way to recover the original even if we can't find another HD that will hash to the same value. In fact if there were then it would be trivial to break collision resistance.
Hash some long random string. Invert the result. Since many (infinite) strings hash to any given output chances are u don't back the original string. Any different preimage is a collision.
Incidental a similar trick shows that taking square roots mod a composite is essentially equivalent to factoring...
Which is more ore less what I was trying to convey...?!? Maybe I should have added a smiley or 'sarcasm-tag' at the end of my 'feel safe' sentence.
If there is one thing to be learned on slashdot, it has to be sarcasm.