NIST Announces Round 1 Candidates For SHA-3 Competition 125
jd writes "NIST has announced the round 1 candidates for the Cryptographic Hash Algorithm Challenge. Of the 64 who submitted entries, 51 were accepted. Of those, in mere days, one has been definitely broken, and three others are believed to have been. At this rate, it won't take the couple of years NIST was reckoning to whittle down the field to just one or two. (In comparison, the European Union version, NESSIE, received just one cryptographic hash function for its contest. One has to wonder if NIST and the crypto experts are so concerned about being overwhelmed with work for this current contest, why they all but ignored the European effort. A self-inflicted wound might hurt, but it's still self-inflicted.) Popular wisdom has it that no product will have any support for any of these algorithms for years — if ever. Of course, popular wisdom is ignoring all Open Source projects that support cryptography (including the Linux kernel) which could add support for any of these tomorrow. Does it really matter if the algorithm is found to be flawed later on, if most of these packages support algorithms known to be flawed today? Wouldn't it just be geekier to have passwords in Blue Midnight Wish or SANDstorm rather than boring old MD5, even if it makes no practical difference whatsoever?"
Re:If you know the hash isn't it game over? (Score:4, Informative)
Re:I'd ignore the Europeans too (Score:5, Informative)
Not if it isn't shown to be secure
Rather: Not if it is shown to be insecure.
Re:'One-way' functions (Score:5, Informative)
Wikipedia:
"The ideal hash function has four main properties: it is easy to compute the hash for any given data, it is extremely difficult to construct a text that has a given hash, it is extremely difficult to modify a given text without changing its hash, and it is extremely unlikely that two different messages will have the same hash. These requirements call for the use of advanced cryptography techniques, hence the name."
The whole point of the exercise is to find an algorithm that can't be easily reversed and that's far from impossible.
Besides, hashes are never completely broken, at most you can make various collision attacks, you never get away with putting in arbitrary data.
Hashes in general (Score:3, Informative)
I hate to state the obvious, but a hash by nature is breakable. You are (typically) distilling a large number of unique bits down to a smaller number of bits.
Of course there will be more than one set of inputs that generate the same output.
Its more an issue of:
1. How hard it is to find colliding inputs.
2. What the hash is used for.
Passwords typically generate more bits, so different rules apply.
Look at MD6 (Score:5, Informative)
MD6 (similarity in name to MD5 is entirely intentional) looks very interesting:
While raw speed isn't great (the default single-threaded 32-bit md5sum in Linux can do 325 MB/s on a 2.4 GHz CPU) maybe its multi-core friendly design is the right way to do it right now. The original MD5 will probably not entirely disappear because of its speed.
(OTOH if you're hashing SSL web traffic it's probably worse to have your hash bog down other CPUs that are busy with their own jobs)
Re:'One-way' functions (Score:5, Informative)
Re:My favorites: Keccak and Skein (Score:1, Informative)
bonda-fide
Just for your own records, the phrase you want is bona fide (lit. "In good faith.").
I have no ability to comment on the rest of your post, though.
in case of slashdotting, bittorrent (Score:2, Informative)
Here is a torrent of all 51 submissions: http://thepiratebay.org/torrent/4592403 [thepiratebay.org]
Re:My favorites: Keccak and Skein (Score:4, Informative)
Article is out of date (Score:5, Informative)
The article is already out of date. The round 1 candidates were announced back on December 11. Since that time, 11 candidates have been broken. For the latest information, I recommend visiting the SHA-3 Zoo [tugraz.at].
Also, the article suggests that candidates will continue to be broken quickly, but I doubt this will happen. The weak hashes will be broken quickly, but there are likely to be many strong candidates which will not be broken during the contest. Other factors (speed, simplicity, etc.) will determine the ultimate winner.
Ugh.. (Score:4, Informative)
I'll ignore your misuse of the term 'reversible', others have explained it.
Rainbow tables are only feasible against poor implementations. I.e. the windows SAM hashes. Even the stored LM2 hash is susceptible to a rainbow table that can fit on a dual layer DVD for over 99% of the keyspace. The old crypt in Unix systems is similarly weak (though still not nearly as much). The implementation on MD5 crypt on /etc/shadow would require about 10^73 yottabytes of a rainbow table to achieve the same end in the same way.
In other words, a dictionary attack on the password space rather than precomputed tables of hashes remain the biggest threat to /etc/shadow. No application in their right mind would not use a similar strategy to remember how to prove client knowledge of a password.
MD5 is not sufficiently broken yet to induce panic. As far as I understand, there is no attack yet that has sufficient control over the colliding data to be of consequence yet.
Besides, what would your proposal be? The other logical class of cryptography would be two-way, which fundamentally provides no security in these instances. Hashes passwords are so a server can prove a password is valid without having to know the password. If it were two way, the crypted data and the key would both have to be accessible, making it trivial to break if you achieve privilege to get the password file today. The other major application is download verification, to enable a small amount of data to be distributed in a more trustworthy way to validate data transmitted in the most expedient way, or to validate future transfers once trust is established..
Re:Triple MD5 Anyone? (Score:3, Informative)
Several points about this:
-DES was never algorithmically broken--it was just designed with too small a key size. 3DES effectively doubles the key size to something reasonable. MD5, however, is actually broken--it has algorithmic weaknesses that can be exploited. Thus, it's not an analogous case.
-We know a lot more about hash functions now than was known when MD5 was designed. From new attacks (e.g. multicollisions) to new design techniques (e.g. HAIFA), there's a lot more knowledge for cryptographers to use.
-As a corollary to the above, any new algorithm, even your 3MD5, would require application support. If we're going to ask people to code that up, why not get something entirely new?
-Finally, practical considerations. NIST wants something flexible for SHA-3, and there are various requirements that are not met by the above proposal. (Digest size from 224 to 512 bits, for example.) There are additional implementation considerations that make your proposal worse than MD5 itself--notably, the requirement that the bytes be read three times in various orders. Just about every practical hash function proposal (including all the major existing ones, and all the SHA-3 candidates I've looked at) is computable "online"--that is, it can be computed in a single pass reading through the message. It doesn't require multiple passes or even keeping the entire message in memory at once.
In short: NIST is looking for something better than SHA-2 (and definitely better than SHA-1). 3DES was a good idea because DES itself was still good, but in this case it's better to start fresh than throw a random patch on an old-and-broken algorithm.
Read the Federal Register notice [nist.gov] to get an idea of what NIST wants out of this. It's a lot broader than "a patch on MD5."
Credit Card fallacy (Score:1, Informative)
example 2
your credit cards you carry around? the PIN number isn't stored on the card - but an MD5 hash of the PIN number *is* stored on the card (making replay attacks possible, believe it or not).
A common fallacy. The standards for PIN generation on magnetic cards were developed long before MD5 became common. The 'IBM' methods (guess who makes the security processor at the other end of the ATM links?) are based on your PIN being a hash of your account number and a bank secret key, known only to the bank and the ATM. This lets the ATM work offline but not know your personal PIN.
Later they let your PIN be changed by also storing an 'offset' between the 'real' PIN and CSP (customer select PIN) for each digit.
Later, all ATMS came to be considered 'online' and they pretty much gave up with the hashing and just encrypt the PIN and send it to the bank for comparing against the central copy.
The hashes and crypto in these protocols have pretty much always been DES or 3DES - none of this new fangled MD5 stuff. SHA1 is making slow inroads.