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.
What makes you extrapolate from "It's safe against the most likely issues SHA-2 might have" to "We chose it because of that but for the rest didn't bother to study it at all?" You surely are not a cryptographer, given that you can't even spell the word.
I did not extrapolate that, I just said that this sentence in the summary does not sound impressive. In fact it should be a given that SHA-X does not suffer from the same vulnerabilities as SHA-X-1.
Oh and thanks for the spell check.
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?
Perhaps this secure hashing algorithm was chosen above the others because it was more secure than the others?
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.
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.
It makes it somewhat more impressive when the vulnerabilities of SHA-2 are not known yet.
What?
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.
Security is only one of the factors. Speed is one of the big reasons AES was chosen IIRC.
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.
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
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)
you're trying (poorly) to troll, but for those who actually are curious, no, you should not do anything of the sort. you should use a proper password hashing framework which makes use of hash functions actually intended for use with authentication systems, such as phpass.
Innovation is a means to an end, not an end in itself. "Most innovative" on its own should not be a criterion in choosing a hash function.
"Having a good SHA algorithm is a good thing."
still using the ATM machine?
In fact it should be a given that SHA-X does not suffer from the same vulnerabilities as SHA-X-1.
No, it shouldn't. Both SHA-1 and SHA-2 are based on the Merkle–Damgard construction. If there's something really wrong with it (not that there's any reason to believe so, today), both SHA-1 and SHA-2 would be affected.
Keccak (SHA-3) has a completely different design based on the sponge construction.
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.
We do have a bit of a problem with patriotism :s
Sounds like we should send Nigel Farage to give you a pep talk.
It's a new design, so without further knowledge all we can say is that it replaces "unknown vulnerabilities" with "unknown vulnerabities". Great :P
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
The same companies that are vulnerable to SQL injection exploits because they don't even have pen testing as part of their development cycle.
I think he's targeting major corporations.
Change is certain; progress is not obligatory.
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.
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!
Agreed. I intend to use Skein in my cryptographic protocol anyway, because Skein has native signature pinning, native tree hashes, and a native keyed hash mode. It's also much faster, and no less secure.
NIST's stamp of SHA-3 approval frankly doesn't mean that much to me anymore, particularly if they chose it because it'd work on smartcard processors. That's not my use case, and I have no particular need to comply with any standards: indeed, a Skein Tree Hash makes a very fine replacement for a Tiger Tree Hash...
"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?
"php" and "proper" should never be in the same sentence.
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.
Did you even READ the article you're quoting? Merkle-Damgard is known to have many undesirable properties. They're even mentioned in that same WIkipedia article...
And yet, NIST has no plans to phase-out of SHA-2, because SHA-2 is fine. There's a reason I wrote "If there's something really wrong with it": as far as we know, there's nothing really wrong with it. Cryptographic algorithms are all about trade-offs, and SHA-2 is certainly not perfect, but the same is true of almost everything else we use.
When Scheier said "we don't need SHA-3" last week, he was lambasted by the remaining cryptographic community for ignoring exacly that.
Don't be silly. If that was true, people would be recommending moving away from SHA-2, and nobody is saying that.
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!
So is SHA1 unsafe now?
Noone has actually found any collisions yet but there is a risk they may do so in the not too distant future. So if your system relies on collision resistance you probablly want to look into migration plans to something stronger.
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('********')
Not really, collisions aren't really too much of an issue in this application, the attacker would need a preimage attack which is much harder. Generally in password hashing systems the hash function is far from the weakest link however for this use you should.
1: make sure you salt your passwords. Ideally with both a per-installation salt which is stored separately from the password DB and a per-password salt in the password db.
2: consider using a deliberately slow hash function to slow down dictionary/brute force attacks on your passwords.
3: consider privilage seperation between the part of your system that handled password validation and the rest of your system so a break in your webapp doesn't let someone download a copy of the stuff they need to start work on password craking.
note: i'm known as plugwash most places but i screwd up registering that here somehow in the past and now can't register
Well actually three encryptions should give you 512 bits of security, like 3-DES is 112 bits.
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.
Then replace phpass with bCrypt or sCrypt.
Not a sentence!
It still works somehow.
In case SHA3 is broken: whatever, we'll make a new one.
In case SHA2 is broken: whatever, we have SHA3.
What?
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.