Slashdot Log In
NIST Announces Round 1 Candidates For SHA-3 Competition
Posted by
Soulskill
on Sun Dec 21, 2008 09:27 AM
from the time-to-pick-them-apart dept.
from the time-to-pick-them-apart dept.
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?"
Related Stories
[+]
NIST Opens Competition for a New Hash Algorithm 187 comments
Invisible Pink Unicorn writes "The National Institute of Standards and Technology has opened a public competition for the development of a new cryptographic hash algorithm, which will be called Secure Hash Algorithm-3 (SHA-3), and will augment the current algorithms specified in the Federal Information Processing Standard (FIPS) 180-2. This is in response to serious attacks reported in recent years against cryptographic hash algorithms, including SHA-1, and because SHA-1 and the SHA-2 family share a similar design. Submissions are being accepted through October 2008, and the competition timeline indicates that a winner will be announced in 2012."
[+]
Security Review Summary of NIST SHA-3 Round 1 146 comments
FormOfActionBanana writes "The security firm Fortify Software has undertaken an automated code review of the NIST SHA-3 round 1 contestants (previously Slashdotted) reference implementations. After a followup audit, the team is now reporting summary results. According to the blog entry, 'This just emphasizes what we already knew about C, even the most careful, security conscious developer messes up memory management.' Of particular interest, Professor Ron Rivest's (the "R" in RSA) MD6 team has already corrected a buffer overflow pointed out by the Fortify review. Bruce Schneier's Skein, also previously Slashdotted, came through defect-free."
[+]
SHA-3 Second Round Candidates Released 62 comments
Jeremy A. Hansen writes "NIST just announced their selections for algorithms going to the second round of the SHA-3 competition. Quoting: 'NIST received 64 SHA-3 candidate hash function submissions and accepted 51 first round candidates as meeting our minimum acceptance criteria. We have now selected 14 second round candidates to continue in the competition. Information about the second round candidate algorithms will be available here. We were pleased by the amount and quality of the cryptanalysis we received on the first round candidates, and more than a little amazed by the ingenuity of some of the attacks. ... In selecting this set of second round candidates we tried to include only algorithms that we thought had a chance of being selected as SHA-3. We were willing to extrapolate higher performance for conservative designs with apparently large safety factors, but comparatively unforgiving of aggressive designs that were broken, or nearly broken during the course of the review. We were more willing to accept disquieting properties of the hash function if the designer had apparently anticipated them, than if they were discovered during the review period, even if there were apparent fixes. We were generally alarmed by attacks on compression functions that seemed unanticipated by the submitters.'"
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
I'd ignore the Europeans too (Score:3, Insightful)
What is the point if they only got one submission for the Hash contest? Doesn't that make it the automatic winner?
Surely you want to do better than have to pick from more than one choice.
And yes it will take years to pick the winner. Duh. You don't want to just throw something out there that will get broken immediately.
Re:I'd ignore the Europeans too (Score:5, Insightful)
What is the point if they only got one submission for the Hash contest? Doesn't that make it the automatic winner?
Not if it isn't shown to be secure. If needs to be tested first.. it may be they have no winner.
Parent
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.
Parent
Re: (Score:2)
Re:I'd ignore the Europeans too (Score:5, Insightful)
The grandparent had it right. The starting position in security should be an assumption of insecurity.
Yes, but you can't prove that it's secure, only that it's not.
Parent
Re:I'd ignore the Europeans too (Score:4, Insightful)
You can prove its security against a number of known types of attacks, which is how there's already 1, up to 4 disqualified hashing algorithms in the NIST competition.
Parent
Re:I'd ignore the Europeans too (Score:4, Funny)
What is the point if they only got one submission for the Hash contest?
Europe's top contenders in the hash competition were devastated by some new laws in Amsterdam, banning whores and space-cake cafes: http://news.ninemsn.com.au/article.aspx?id=683353 [ninemsn.com.au]
Well, duh, do you think people travel there to look at the wooden shoes and windmills? What have their politicians been smoking?
And yes it will take years to pick the winner.
If the stuff is good, and the judges supply of Doritos hold out, it could take decades.
Parent
We know how md5 is broken (Score:5, Insightful)
Actually, it's probably much better to have MD5 which is known broken in understood ways, than Jo3#a$# which is broken but we don't know how, where and why. There are fairly simple rules for MD5 (start phasing out now; only use in situations where you in some way control the input, not your adversary) which make it possible to use in a relatively safe way. If you don't know what way the hash is broken you don't know how to avoid those problems. Having said that, SHA256 should probably be considered the minimum for a temporarily secure system with a lifetime limited until something better has been available and tested. As Mr Schneier says "attacks only get better; they never get worse".
It's also not a surprise that some hashes got broken. There are many entries and they come from all types of cryptographer from teenager to aged expert; from unknown to known mostly by initials (e.g. A, S or R). There was not much hope that all of them would be of good quality.
Why can't we mod down submitters? (Score:5, Insightful)
s/geekier/stupid and irresponsible
Let me guess, the submitter likes to enable all the useless bling effects on Compiz but never gets any work done, and has racing stripes on his Civic....
I went to Carnegie Mellon and took classes from a bunch of professors who were all freakin' geniuses and here is the second most important lesson I learned about cryptography: NEVER DO IT YOURSELF. And a corollary to that is never use a cryptographic system someone else cooked up until it has been through the vigorous peer review that these hash functions will go through. This was an important lesson to a bunch of egotistical CMU students, and I hope the ones who were actually smart listened. (The first most important lesson is an old one: if you think cryptography is the solution to all your security problems, you don't understand cryptography or your security problems).
"Whaa! But the ciphers we have now are already broken!!" The current hash functions that are "broken" like SHA-1 are not trivially broken, but broken in a sense that in some scenarios might make it somewhat easier to conduct either a pre-image attack (useful if you know somebody's password hash and want to make a password that will hit the same hash) or a collision attack (useful in some cases where you are trying to forge a messsage to match a digital signature.... but if the fake message has to contain lots of garbage bytes even a successful collision might not pass the smell test). "Somewhat Easier" does not mean you can do it on your iPhone, it just means that it might take a supercomputer 100 years instead of the heat death of the universe to do it. This is still very important, but it is a world apart from an algorithm that has never been tested... those could be blown wide open and cracked almost instantly with trivial computing power. To use a bad car analogy, just because a seat belt won't save your life in every car accident doesn't mean it's just as safe to strap plastic explosives to your gas tank and hook them up to a mercury switch detonator.
As for "open source" making these cryptographic models available quickly, I wasn't aware that text editors froze up and stopped you from writing code if it wasn't going to be open source. The reason commercial vendors won't jump on a new cryptographic protocol before they are validated is that their customers would (rightly) go ballistic and their credibility would be smashed. Fortunately for all of us the leaders of the open source community have a little more sense that you and you won't see any of these hashes in the Linux kernel or OpenSSL until they are at least in the final rounds of competition and there is some evidence that they have value. OSS has the advantage that its software implementation can be publicly validated and peer reviewed, but having your code opened up to the world is actually much MORE dangerous if you are just screwing around because you think a hash function has a badass sounding name. I'm glad Torvalds is in charge of Linux and not "jd".
Re: (Score:2)
Let me guess, the submitter likes to enable all the useless bling effects on Compiz but never gets any work done, and has racing stripes on his Civic....
Well said. Also the rest of your post is spot on. I'm going for the 'ignorantsummary' tag myself.
Re: (Score:2, Funny)
Reminds me of the manager who works a whole week on his presentation. 90% of the time is used for special effects. And then when he gives the presentation realizes he needs to move on, but can't because his nice slides force him to show every special effect he has put into it.
Other people realise that Powerpoint is just a tool. Giving the presentation is wh
Re: (Score:2)
> As for "open source" making these cryptographic models available quickly,
> I wasn't aware that text editors froze up and stopped you from writing
> code if it wasn't going to be open source.
You know, you were making some nice points, and here all you do is hurt your credibility. You know exactly what he was saying, and he was right.
Re: (Score:2)
The whole point of the contest is to give all the candidates testing and scrutiny. Sure, I would currently choose one of the SHA-2 family (256, 384 or 512) for any current thing I was doing where it mattered. But I fully expect that in 2-5 years time I will instead choose one of the algorithms that was recently submitted to NIST.
I am disappointed though to not see Whirlpool [wikipedia.org] in the list.
And MD5 is just plain out broken, and there are alternatives that are better in every respect. If I had my way the algor
Re: (Score:2, Insightful)
Re: (Score:2, Redundant)
you just WHIISH that was true...
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: (Score:2)
Re: (Score:2)
I would like proofs of security to assume the availability of quantum computation. Do your proofs of security assume this?
Re: (Score:2)
I was under the impression that quantum computing was only a threat to some public key schemes (like RSA).
Is quantum computing a threat to AES or any other popular symmetric key encryption method?
Re:Look at MD6 (Score:4, Insightful)
MD6 is definitely a serious contender. Its very conservative and well researched. It's main contender is probably Skein at the moment, although there are a few others to consider. MD6 is however not as fast as some contenders, not as flexible as some and its internal state is, as I believe, larger, which makes it more of a pain on embedded and smart card processors. In all this, Skein beats MD6. It's parallel design is using a typical hash tree, which can be used for many other hash methods as well, although MD6 uses it in its main operation.
Parent
It looks slow. (Score:3, Interesting)
IIRC, Skein is getting about 6 cycles a byte in 512-bit mode on 64 bit platforms, which on a 2.4GHz dual core CPU would yield a theoretical 800 MB/s in a parallel tree hashing mode, 400 MB/s in standard mode. Apparently MD6 has a parallel mode also, and it's striking that both hash functions are trying to be minimalist by employing only three fundamental operations (AND, XOR, SHIFT for MD6; XOR, ADD, ROLL for Skein) and lots of rounds. It's odd that MD6 should be so much slower. Perhaps it hasn't been fu
Salts... (Score:3, Interesting)
In answer to - "have passwords in Blue Midnight Wish or SANDstorm rather than boring old MD5, even if it makes no practical difference whatsoever?"
I'm going into the "no practical difference whatsoever" camp. In fact you're taking a huge risk if any of them are broken and you gain nothing that simply salting your hashes doesn't already give you.
We know that MD5 is secure to a degree. Just salt that bad boy up so rainbow tables no longer have any impact.
Re: (Score:2)
If 99% of the risk comes from people with 1% of a functioning brain, it makes no sense to not take simple precautions that might (
My favorites: Keccak and Skein (Score:5, Insightful)
There are only four unbroken contributions that can generate arbitrarily long streams of numbers: Keccak [noekeon.org], LUX [tugraz.at], MeshHash [tugraz.at], and Skein [skein-hash.info]. Of these contributions, LUX and MeshHash, while not broken, already have cryptanalysis done against them that make me a little uneasy using them.
I prefer Keccak over Skein, for the simple reason there is a bonda-fide 32-bit variant of Keccak that can run quickly on 32-bit systems. Skein is designed to run well only on 64-bit systems. Part 5.4 of the Skein paper talks about the possibility of making a 32-bit variant of Skein but that they need to come up with rotation and permutation constants, and figure out how many rounds a 32-bit Skein variant would need. I would like to see Schneier, et al (the team responsible for Skein) actually do this. Skein is more flexible that Keccak (I think threefish is the first tweakable block cipher since the somewhat broken Hasty Pudding Cipher), and is faster on 64-bit systems, but I would like to see it run on embedded and legacy systems better.
Re:My favorites: Keccak and Skein (Score:4, Informative)
Parent
Re: (Score:3, Insightful)
Every hash function can be used as a stream cipher: you simply hash the password, then hash the resulting hash, and so on, and use each intermediate hash as input to a stream you then XOR the cleartext stream with to produce the ciphertext.
Of course for this to be secure, the hashes must be undistinguishable from random strings, but I'd imagine that's a requirement for a good hash fu
Re: (Score:2)
Add dedicated hardware to an embedded system just so that it can perform hashing?
Given a choice between the above and picking a hash function that can run decently on the 32 bit processors like ARM, MIPS and x86, I highly doubt the first option will be chosen.
in case of slashdotting, bittorrent (Score:2, Informative)
Here is a torrent of all 51 submissions: http://thepiratebay.org/torrent/4592403 [thepiratebay.org]
Popular wisdom has a very good reason... (Score:5, Insightful)
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?
It matters a lot. Say OpenSSL added all of these algorithms tomorrow. Some idiot developer (hint: go read DailyWTF) will build on top of it. OpenSSL now has to maintain backwards compatibility - so they can never take out the algorithm. A month from now, the algorithm gets broken completely. But because OpenSSL shipped with it, they can never take it back out.
The "popular wisdom" standard for proliferating a new algorithm is not how shiny it looks at first glance. Popular wisdom waits months or years until algorithms seem good enough. MD5 (or even MD4), SHA1 - all are good enough for some purposes (generally, when attacker does not control input). And if the attacker does control the input, the only sure solution is to send the whole thing - anyone believing otherwise needs to review the meaning of the word "hash". A secure hash is merely an irreversible hash with a very low risk of collision.
Even this article is mostly "security theater". There are very, very few uses of secure hashes where SHA1 (or even MD5, for that matter) is not good enough.
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.
does a bear poo in the woods? (Score:3, Insightful)
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?
does it matter? does it matter?? fuck me it fucking matters.
example 1
there's a type of encryption algorithm principle - the feistel cipher - see http://en.wikipedia.org/wiki/Feistel_cipher [wikipedia.org] - where you perform one simple transform function as "round 1", then for rounds 2 and 3 you do a one-way hash function, and then for round 4 you do a simple transform function.
if the one-way has is ever broken, your encryption cipher is also broken.
game over: any traffic that's ever been using that cipher can be decrypted.
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).
if MD5 is ever cracked...
game over: anyone can get your PIN number.
example 3
your peer-to-peer filesystem, your git source control system, they use one-way hashes to store an index of the data blocks. let's say that someone deliberately wants to break deployed systems, they work out what file chunks could end up being mapped to the same one-way hash...
game over: anyone can corrupt the database or the peer-to-peer filesystem by _deliberately_ making file or file chunks write to the same block.
i could go on with the list of examples - authentication systems that would fall over; internet bank systems that could be broken in to - we _totally_ rely on one-way hashes working correctly.
it's important beyond _belief_ that these one-way hash functions work, so much so that i was staggered that the question even had to be asked as part of the article-announcement.
Re: (Score:2)
Welcome to the world of cryptography where nitwits feel free to bandy about the most ridiculously stupid assertions because they don't actually understand what they're talking about.
I have a theory that many geeks are so threatened by knowledge they don't have and think might require a lot of effort to acquire that they will go thr
Triple MD5 Anyone? (Score:3, Interesting)
(Triple MD5 is is composed of the XOR of standard MD5 first byte to last byte, MD5 last byte to first byte, MD5 middle out to the ends. Faster hardware makes this feasible now.)
Re: (Score:3, Insightful)
It is very doubtful that this is more secure, and it certainly more of a hassle. I would not want to hash a stream with a method like that.
Re: (Score:3, Interesting)
Replying on myself here, but any algorithm that starts with encoding the hash size is bad as well, IMHO, and there are some examples of that in the SHA-3 zoo. If you have e.g. XML base 64 encoding you may not know the full length before decoding, so you cannot hash at the same time.
Re: (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
Re:If you know the hash isn't it game over? (Score:4, Informative)
Parent
Re: (Score:3, Insightful)
Not strictly true. Rainbow tables are only feasible for very small inputs -- like 8-character-or-less passwords. Salting makes the minimum input larger (much larger, since salts are usually full binary, wheras password characters are almost always out of a small subset of possible characters). Of course, rainbow tables are absolutely useless if what you're hashing is, say, an entire file for a digital signature.
Re: (Score:3, Insightful)
Anyone who has access to a set of password hashes will break some of them quickly. Just make sure your system is robust despite that (i.e., make sure that you can't get to a given set of password hashes unless you can already get to everything accessible using every password in that set).
Humans choose short, weak passwords, and always will. Make your system OK with that. There are plenty of ways, from limiting retries to using physical tokens. 4-digit PINs *work* for ATM cards, because the PIN isn't the
Re: (Score:2)
Not completely useless. It becomes far, far, far less practical (You need a much larger table), but it will still work.
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.
Parent
Re:'One-way' functions (Score:5, Informative)
Parent
Re:'One-way' functions (Score:4, Insightful)
Did you really need a link to explain that? I mean, the fact that I'm deriving a 16-byte hash from a multi-gigabyte file should be a pretty good indication that there's no way to turn it around. Otherwise we'd have some really cool compression algorithms.
Parent
Re:'One-way' functions (Score:4, Insightful)
Parent
Re: (Score:2)
Could you read the post carefully? Especially the words 7-10.
Re: (Score:2)
There is reversible and there's reversible. If you can conclude any interesting properties of the input message from the output that counts as being broken from the standpoint of being reversible. One example would be if you could conclude the input's last few bits must've contained an equivalent number of 0s and 1s, or the input was one of infinitely many prime numbers.
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..
Parent
Re: (Score:2)
Since the whole idea of /etc/shadow is that it is not readable by anyone besides the root, rainbow tables would be of no use whatsoever against it. Well, I suppose you could use them as an optimized dictionary...
Besides, doesn't the use of salt prohibit the use of rainbow tables, or at least grow them beyond any feasibility; or did you take that into effect in those
Re: (Score:2)
It does seem like that would be true, but in practice it's entirely possible that cracking hash functions (and block ciphers) is a computationally hard problem (in the "you can't do it" sense). The class of problem, in the general case, is NP-complete [wikipedia.org].