NIST Announces Round 1 Candidates For SHA-3 Competition

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?"

Comments

I'd ignore the Europeans too

[the eric conspiracy]

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

[Tony Hoyle]

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.

Re:I'd ignore the Europeans too

[spud603]

Not if it isn't shown to be secure

Rather: Not if it is shown to be insecure.

Re:I'd ignore the Europeans too

[PolygamousRanchKid]

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

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.

Re:I'd ignore the Europeans too

[Anonymous Coward]

So why the hell is the parent modded flamebait? It is a perfectly reasonable comment.

Re:I'd ignore the Europeans too

[ikegami]

The grandparent had it right. The starting position in security should be an assumption of insecurity.

Re:I'd ignore the Europeans too

[Phroggy]

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.

Re:I'd ignore the Europeans too

[Anpheus]

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.

Re:I'd ignore the Europeans too

[Anonymous Coward]

Which doesn't mean that the rest is "secure" by any stretch of the imagination.

Re:I'd ignore the Europeans too

[Anonymous Coward]

It's not about proving, it's about plausibility. If the world's top cryptographers try to break or attack a hash function for years without anyone making any progress, then the assumption of security is strong enough for you to use it as a standard.

That's even though nothing's been proven and even though technically, nothing has changed from when you started (initially, you had no proof of security OR insecurity; in the end, you still don't have either).

Re:I'd ignore the Europeans too

[Anonymous Coward]

"security against a number of known types of attacks" != "secure"

Re:I'd ignore the Europeans too

[Golddess]

But that still doesn't prove that it is 100% secure, only that it can withstand those kinds of attacks.

Think scientific theories. You can perform individual tests to see if the theory holds true, but you can never say with 100% certainty that something is true.

Re:I'd ignore the Europeans too

[RichiH]

To quote grandparent: "Yes, but you can't prove that it's secure, only that it's not."

Re:I'd ignore the Europeans too

[OeLeWaPpErKe]

You can prove security by using information theory. For example, it is trivial to prove that OTP's the length of the plaintext are secure.

There's just not enough information to hack anything at all. Every last bit is random.

The problem is that you want to encrypt 512 gig of known data using a 1kb key and still have it impossible to determinte the key given both the ciphertext and the plaintext.

That said, many algorithms (including DES) are known to be secure IF the plaintext (what you encrypt) is kept secret (CBC variant, obviously ECB is not).

Of course "plaintext kept secret" means SECRET. In other words if the plaintext starts with "GET / HTTP/1.1" 50% of the time (like any VPN connection), it's not secret. Secret means that there isn't a single predictable bit in the plaintext, which tends to be a rather harsh demand (although zipping plaintext first really adds a lot to the security in practice).

Re:I'd ignore the Europeans too

[Anpheus]

I don't get why people misread what I'm saying. There are a number of established cryptographic techniques for 'breaking' an encryption or hashing algorithm. A tentative first step to finding a new algorithm is to, duh, make sure it's resistant to all the old techniques.

-I- never said you could prove the security of anything other than a one time pad, everyone loves to infer that though.

We know how md5 is broken

[rtfa-troll]

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.

Re:We know how md5 is broken

[Anonymous Coward]

I think you mean 'flawed', 'insecure', 'weak' or whatever. It isn't actually broken before someone breaks it, as hinted at by phrasing like "some hashes got broken".
And knowing some of the ways MD5 are flawed gives no guarantees against any additional attacks. The only security advantage it has over any other cipher is the far greater attention it has received. If some new hash function was equally scrutinized and no attacks were discovered, you wouldn't say MD5 was better since you knew what was wrong with it, as hash functions aren't allotted a fixed number of unknown weaknesses at the time of creation. That's the gambler's fallacy.
And does 'start phasing out now' really count as a rule that makes it possible to use MD5 in a safe way? That's more like a rule for being safe by not using MD5.

Re:We know how md5 is broken

[jd]

All hash functions, no matter how carefully reviewed by however many experts, are broken in unknown ways. The winner of the SHA-3 contest will be broken in unknown ways. It won't stop you using it once it's circulated and part of the "standard". You will and you know you will. So your usage has nothing to do with whether people know where the breaks are, it has to do only with whether it is circulated. If Joe Cracker is so good at breaking hashes that we need fear for the safety of Skein or MD6, then I would have thought the sooner we can get Joe Cracker onto the task, the better off we will all be. The more eyes, the better, right? And if Joe Cracker is as lazy and incompetent as I suspect, then they're not this Big Awful Threat in the first place. You win, both ways. Using what is broken, especially if you know how and why, is like putting mission-critical data on an unfirewalled Windows box and advertising the version. You know how it's broken - and so does everyone else. This gains you what?

Re:We know how md5 is broken

[OeLeWaPpErKe]

This is only true if you consider math to be "discovered" as opposed to "made".

That way the cracks were only "non-existant" in the same way america was non-existant in the 14th century.

Re:We know how md5 is broken

[rtfa-troll]

If some new hash function was equally scrutinized and no attacks were discovered, you wouldn't say MD5 was better

agreed. but the point is that the new ones haven't been scrutinised.

The only security advantage it has over any other cipher is the far greater attention it has received.

well, that's a big advantage. For example, a hash function could have a weakness that there are certain "special" values which are very bad but detectable. By always using the hash with salt and then trying again if a bad value came up, I could avoid that weakness. The currently known "weakness" of MD5 means we know which particular usages are really bad (validating large messages from a potential enemy) and which usages aren't yet bad (checking I still have the same known file I had before).

does 'start phasing out now' really count as a rule that makes it possible to use MD5 in a safe way?

I'd say the alternative isn't safe :-) Right now I guess that MD5 cracking, even by the military / NSA is quite limited. If I have a hash I want to be valid for the next two years, I'd not be too worried about it (of course I may be completely wrong, but that's life..). On the other hand, if I'm generating a hash now, that I plan to use in twenty years time; I'd look a avoiding MD5 and using SHA256. So, yes, I do think 'start phasing out now' is a good reasonably safe way to use MD5. At the very least you'll have a good idea which applications you need to be able to change if MD5 gets completely broken. In the end, this is all about your definition of safe. Good enough to make sure nobody messes with your porn collection: yes (unless you've been reading Slashdot for a long time in which case this might be a touchy issue). Good enough for use in your planned invasion of California: probably not.

If you know the hash isn't it game over?

[Anonymous Coward]

Why do I need to break the algorithm when I can "guess" it more quickly once I generated a rainbow table?

Re:If you know the hash isn't it game over?

[tukang]

Because rainbow tables are useless if the hash is salted

Re:If you know the hash isn't it game over?

[blueg3]

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:If you know the hash isn't it game over?

[compro01]

Not completely useless. It becomes far, far, far less practical (You need a much larger table), but it will still work.

Re:If you know the hash isn't it game over?

[lgw]

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 only element providing security. The physical token, the ability to invalidate or capture the physical token, the camera in the ATM, and the daily withdrawal limit are all important there.

Hash functions are more interesting for digital signatures. Depending on a hash not being reversible given a very short input is a bit silly. That's not really the point of a hash function. The point is to make it practically impossible to create a document that matches a given signature.

Re:If you know the hash isn't it game over?

[jgtg32a]

Fun fact about your debit card and PIN numbers.

Fraudulent transactions using your pin number aren't covered by the law so you're SOL

Re:If you know the hash isn't it game over?

[Chrisq]

Fraudulent transactions using your pin number aren't covered by the law

Of course they are! If you steal pin numbers and withdraw other people's money do you think the cops will just say "let him go, he's not covered". Its still fraud!

What you mean is that the banks won't automatically reimburse you. They often will reimburse when its shown to be a crime but they are wary because of the large number of "same address" offences where the victim does not want to press charges.

Re:If you know the hash isn't it game over?

[OeLeWaPpErKe]

But salting only protects against rainbow tables. It does not protect -at all- against, say a wordlist or brute force attack, nor does it slow that attack down.

In other words, salting or no salting, weak password are easily cracked given the hash.

With a salt you encrypt "$salt$password" and then store both the result and the salt : "$salt$hash"

Re:If you know the hash isn't it game over?

[OeLeWaPpErKe]

The problem with what you "advise" is that it's impossible for most people on the internet. 2 factor security is prohibitiverly expensive for just about everyone. The only thing semi-doable for personal security is using an rfid token.

You cannot secure websites or fora using 2 factor security. It's not reasonable. Therefore, the hash is all you have.

Re:If you know the hash isn't it game over?

[blueg3]

Not only did I not say anything about other attacks, but hashing passwords is probably the second-least-interesting application of a hash algorithm. None of the attacks against common hashes (MD5, SHA1) are even applicable to passwords. (The least interesting application is its use as a checksum.)

What does slow down a guessing attack is increasing the computational requirements of generating the hash, as is done with multi-round PBKDF. Alternately, all guessing attacks are rendered useless by selecting passwords out of a space that has sufficiently large entropy -- however, that's largely a nontechnical problem.

Re:If you know the hash isn't it game over?

[lgw]

You cannot secure websites or fora using 2 factor security. It's not reasonable. Therefore, the hash is all you have.

Well, if you just decide that's true, of course your security will be a joke. If the "fora" (forum is an English word now, pluralized normally) you care about is the comments for your blog, joke security is probably enough, but if there's risk of financial loss then may be worth spending a little money to get it right.

My bank uses 2-factor security, and the RSA key thingy is free - the bank comes out ahead on not eating fraud losses, plus it's good marketing. There are also software-only 2-factor solutions, which can be helpful in securing a business network (you share a secret in some secure way when the client computer is provisioned).

If you're talking about a B2C website, where you can't force anything on your customers, then ask youself how anyone going to get the set of password hashes to begin with. You should be strongly encrypting all of your customer data at rest in the first place (including password hashes). And of course credit cards come with a second factor: make use of the CCV2 code.

Re:If you know the hash isn't it game over?

[blueg3]

Both World of Warcraft and PayPal have (optional) two-factor authentication.

Why can't we mod down submitters?

[CajunArson]

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?

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:Why can't we mod down submitters?

[ezzzD55J]

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:Why can't we mod down submitters?

[Ant P.]

That's the biggest WHOOSH I've ever seen on Slashdot.

Re:Why can't we mod down submitters?

[Anonymous Coward]

Well said. Also the rest of your post is spot on. I'm going for the 'ignorantsummary' tag myself.

It needs a !encryption tag too.

Re:Why can't we mod down submitters?

[Loibisch]

you just WHIISH that was true...

Re:Why can't we mod down submitters?

[houghi]

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....

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 what you need to do yourself.

Re:Why can't we mod down submitters?

[mattwarden]

> 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:Why can't we mod down submitters?

[Omnifarious]

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 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 algorithm would be permanently erased from every single storage location on the planet. I can't understand why people use it at all anymore. People who defend it on any grounds I generally label complete idiots and dismiss anything they say about cryptography as utter nonsense.

But, you are right, SHA-1 is only sort of vaguely weakened against chosen pre-image attacks. And people are only uncomfortable with the SHA-2 because it uses the same design philosophy as SHA-1 and someone may discover a related vulnerability.

Then again, attacks only get better, not worse. I would count SHA-1's days as numbered.

Re:Why can't we mod down submitters?

[jd]

1. You cannot "lead" from behind. Ergo, you cannot both be a leader AND and follower at the same time. If you are waiting until someone else tells you it's ok, you're a follower.
2. In a race, the ones who look behind them fall over. Those who look ahead at least finish (a key requirement in winning).
3. Skein was hardly designed by Joe Punk. Neither was MD6. Both have sample code. So who is doing all this DIY stuff you speak of?
4. You can either know you are safe or you can be ahead of the game. You can't have both, it's a choice. (You can in fact be safe, when ahead of the game, you just can't know it.)
5. Unless you suspect an attack on your home computer stash of downloaded music by the NSA, would you care to name any skript kiddies who have the maths noggin to break a system they can't just download the hack for?
6. Cryptography professors, as with all professors, are not generally that smart. Some are and they do well enough in research or are hired by three-letter agencies or really big companies involved in crypto. The majority teach because they lack the brains or the guts (it takes both) to innovate.

Oh, and I would remind you that Torvalds ignored HIS professors when it came to kernel design and opted to write his own code rather than use the publicly-available BSD4.3 or MACH tapes. I wouldn't claim to be his equal, but I would claim to have infinitely more parallels that some gutless 6-digit UIDer who, if they'd been the inventor of Linux, would have based it on TOPS-20 and never ported it to platforms never "tested" by experts for a true multitasking OS. Assuming they ever ported it from the "safe" minicomputer of their choice at all.

According to one expert in such matters, "If you want to be the best, if you want to beat the rest, dedication is what you need." Cautious types need not apply.

Re:Why can't we mod down submitters?

[Anonymous Coward]

You seem to be of the same type of people the GP was attacking. So you can either know you are safe or ahead of the game... For what are you using cryptography again? Showing off your tech or securing your data?

Re:Why can't we mod down submitters?

[Anonymous Coward]

Dude, he is the person the GGP was attacking. He was the one who submitted the article.

Re:Why can't we mod down submitters?

[jd]

The Victorian "thief lock" is well-tested, has been around for ages, is well understood by experts, and is used by exactly no-one to secure their belongings. The high-end, high-quality locks that security experts rave about are, by comparison, barely tested by anyone, have had minimal serious testing, are probably not understood by many experts owing to IP laws, and are used by people serious about keeping their belongings. Which camp did you say you fall into, again?

If you prefer to look at other industries, take a squint at Formula 1, where those who don't move forwards go backwards. The designs are barely tested, have no peer-review, are infinitely more complex than a one-way function and are punished far more severely than any two or three rounds of testing by NIST can achieve. True, many break. But if nobody drove them at all in case they would break, they'd be racing nothing more advanced than a horse and cart.

And like I said, who said anything about MY tech skills? I happen to like the tech skills of the guys who wrote Skein and MD6, and I happen to know that most modular crypto libraries out there take modules with nearly identical APIs to the sample implementations. What the F do =my= tech skills have to do with this? A blind onion could make the marginal changes needed. If you can't out-program a vegetable, that's hardly my problem, is it?

Re:Why can't we mod down submitters?

[jd]

If the rest of his post is so well-said (such as wondering why they can't mod down submissions), why am I able to go to the Firehose and, well, mod down submissions? Far as I'm concerned, if his argument is so easily broken, it can't be treated as the least bit reliable. True, you will find "bling" on my computer. It'll be in the form of kernel patches I've ported or "adjusted". Assuming you consider "bling" to mean anything that isn't strictly necessary but is great fun to exercise and which sometimes actually leads to performance or security improvements. Remember, improvement is not "necessary", but I think nice to have and I don't give a rat's arse if that means digging through obscure work that has never seen the LKML, never mind actual peer-review. I'm quite capable of reviewing source code myself and don't need your help to do so. In fact, given how many broken packages I've found in mainstream distributions, I'd rather review source-code myself than take anyone else's word for it. I may not be a coder guru, but I trust my ability to test and debug software far more than I'll ever trust the incompetents who write and fail to test the majority of code (both Open Source and proprietary) that is out there. I may not be the best, but I'm better than than that. A dead haddock could write better code than some of the stuff I've endured, so if I wouldn't trust that, why should I trust you?

Re:Why can't we mod down submitters?

[ion.simon.c]

...I happen to know that most modular crypto libraries out there take modules with nearly identical APIs to the sample implementations. ... A blind onion could make the marginal changes needed.

The marginal changes need to... what? Create a new crypto module?
Sorry for not understanding. I'm a blind onion. :(

Re:Why can't we mod down submitters?

[mollymoo]

What a load of empty, bullshit rhetoric. "In a race, the ones who look behind them fall over. Those who look ahead at least finish (a key requirement in winning)."? Fuck off.

Re:Why can't we mod down submitters?

[jd]

The submitted example code for this contest uses a standardized API that is 99.99% the same as that used by mhash, libgcrypt and others. Likewise, submissions for the AES contest used a standardized API that was 99.99% the same as used by mcrypt, libgcrypt and others. The differences largely consist of the prefix used on the function names and restrictions on the naming of global variables. Search-and-replace should be almost sufficient. Adding some means of registering the function with the library (usually a standardized function call added to the API) should do the rest. If that is too difficult for a blind onion, I suggest less of their beer and more of their pizza.

'One-way' functions

[Frozen Void]

They are not secure.What are hashes relying on is reversible,with clever algorithmic tricks and without quantum computing.Today we know about rainbow tables,but tomorrow there would be far faster ways to break hashes.The complexity of some hash algorithm is just "security by obscurity"(the secret is not in expensive computation/bruteforce required ).The point about the approach is that sooner or later the algorithm would be "refactored" by people who understand the idea behind the algorithm far better then its designers.
Then all this security gets out the window.

Re:'One-way' functions

[Zironic]

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.

Re:'One-way' functions

[cbrocious]

No hash, even the very worst, is reversible. The reason for this is that an infinite number of input strings will produce the same, finite, output string. See http://stackoverflow.com/questions/330207/how-come-md5-hash-values-are-not-reversible for more information.

Re:'One-way' functions

[Anonymous Coward]

Ug, this is pretty trollish of me - but please learn something about math. Then go ahead and post regarding crypto.

Re:'One-way' functions

[Anonymous Coward]

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.

Re:'One-way' functions

[cbrocious]

The fact that people still think hashes are reversible makes it pretty clear that they need more than "no, you can't do that".

Re:'One-way' functions

[Frozen Void]

Could you read the post carefully? Especially the words 7-10.

Re:'One-way' functions

[Chandon Seldon]

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.

Re:'One-way' functions

[Anonymous Coward]

Have you ever done any real cryptanalysis? For practical purposes, the application of a hash function might very well be reversible. For example, suppose that the attacker knows that the original input is below 20 characters in length, that it is of low entropy, and that it is much more likely to contain a certain small number of character sequences than others. Under these circumstances, it can be possible to completely reverse an appplication of a cryptographically insecure hash function.

Never underestimate your adversary.

Re:'One-way' functions

[Omnifarious]

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.

Re:'One-way' functions

[haggais]

I tried reading your comment carefully, honest. I even focused on words 7-10, "hashes relying on is", because they seemed to almost make sense. But I'm afraid the bottom line is that there just isn't enough English, sense, and/or cryptography in that paragraph.

Re:'One-way' functions

[jd]

True enough, but by the same token, the inverse of a hash can then be considered any synonym if you only need one of the possible inputs to generate the same output. If a hash is badly broken, then it may be possible to algorithmically produce an infinite series of synonyms given some seed value that is one of those synonyms. If it is horribly horribly beyond broken, you can also show that there are no synonyms that are not in that series.

At present, there are methods by which, given one synonym, it is possible to produce any number of other synonyms. From this, it is necessarily true that MD5 is capable of being badly broken even if it is still extremely hard to produce the synonym in the first place. You've X-Rayed this apple and it has a core that isn't just rotten, the bacteria and fungi have evolved an entire civilization and are busy in a reality TV ratings war. Continual use of MD5 is simply biting into the apple on the grounds that the rot hasn't reached the surface yet.

Re:'One-way' functions

[PsychicX]

Except that's totally irrelevant, because in most cases we don't CARE about regenerating the original input. You can usually create a useful attack simply by finding SOME input that generates the same output, and that's what you want to build a hash function to resist.

Hashes in general

[zysus]

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.

Re:Hashes in general

[scientus]

its if those bits that come out have a truely random distrobution which being unpredictible. The outputs of hash functions are weakened from theoretical (perfect) (apparent) entropy by a need to do things fast. Distrobutions are not perfectly distrobuted and randomness is removed through the passes.

But both of these things can be completely solved with even crappy systems simply by using larger keys. The most import thing is a (CPU+RAM/bit of entropy). If want something secure do a triple blowfish-whirlpool-AES or ust double AES, or do a SHA-512 instead of a SHA-1. Then only huge problems in the mathimatics can hamper it

Re:Hashes in general

[Goaway]

I hate to state the obvious

Then why do you do it?

Re:Hashes in general

[jd]

You are absolutely correct, which means that the difference between one hash that is currently secure because nobody has found any weaknesses and another which also has no currently-known weaknesses is one of confidence that a weakness won't be found soon. SHA-1 has vulnerabilities which (should) reduce the confidence levels. MD5 is considered completely broken within such things as validating a file is untampered with. But SHA-1 is likely used for classified data (which it should no longer be, it's no longer NIST-approved for such stuff) and MD5 is used for P2P (despite making it trivial for people to poison the share pools in undetectable ways).

This is, according to the hard-boiled cynics who have posted here, a better situation than using Skein and MD6. In the military, quite possibly. SHA-512 and Whirlpool are the sensible choices there, but that always supposes they are sensible. They'd also be good for any other operation, though Whirlpool is a little slow for SSL. Still, I'd rather a page took a few tenths of a second longer to load (given that the variance is already much longer) than have credit card data in the hands of any skript kiddie with the latest black hat toolkits.

But if those two existing "trusted" hashes aren't good enough for you, Skein and MD6 would offer you better security today - unproven as they are - than MD4 or MD5 could hope to do. Same as an unproven (but quite likely good) car will offer you better protection than a rusted-up wreck with leaky fuel tank. Sure, the wreck has been tested in crashes. Sure, it's been around longer and inspected by more people. It's also a write-off and I don't consider write-offs acceptable no matter how many eyes have inspected it.

Re:Hashes in general

[Anonymous Coward]

I realize that the well-used shortened form is distro, but the actual full spelling is distribution. Notice there is only one o, which is the second to last letter.

Re:Hashes in general

[IpalindromeI]

Because he loves to do things he hates. Masochism at its finest.

Re:Hashes in general

[Anonymous Coward]

I hate to state the obvious, but the mere existence of multiple messages that hash to the same thing is not what "breakable" means in relation to hashes.

There are several basic criteria for judging whether a hash is breakable in a meaningful way. They are roughly described here

Furthermore, there are some instances of a cypher or hash function being broken theoretically, yet the attack takes too many resources and so the cypher/hash is not considered broken for practical purposes.

Passwords typically generate more bits, so different rules apply.

What are you talking about? I hope you're not involved in cryptography, because your concept of hashes makes me fearful for the security of anyone who listens to your advice.

Look at MD6

[ivoras]

MD6 (similarity in name to MD5 is entirely intentional) looks very interesting:

• Security: MD6 is by design very conservative. We aim for provable security whenever possible; we provide reduction proofs for the security of the MD6 mode of operation, and prove that standard differential attacks against the compression function are less efficient than birthday attacks for finding collisions. We also show that when used as a MAC within NIST recommendations, the keyed version of MD6 is not vulnerable to linear cryptanalysis. The compression function and the mode of operation are each shown to be indifferentiable from a random oracle under reasonable assumptions.
• MD6 has good efficiency: 22.4-44.1M bytes/second on a 2.4GHz Core 2 Duo laptop with 32-bit code compiled with Microsoft Visual Studio 2005 for digest sizes in the range 160-512 bits. When compiled for 64-bit operation, it runs at 61.8-120.8M bytes/second, compiled with MS VS, running on a 3.0GHz E6850 Core Duo processor.
• MD6 works extremely well for multicore and parallel processors; we have demonstrated hash rates of over 1GB/second on one 16-core system, and over 427MB/sec on an 8-core system, both for 256-bit digests. We have also demonstrated MD6 hashing rates of 375 MB/second on a typical desktop GPU (graphics processing unit) card. We also show that MD6 runs very well on special-purpose hardware.

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:Look at MD6

[Chris_Jefferson]

I don't find the multi-core so useful, it's rare that I want to hash one, very large file. More often I want to hash many things, which naturally parallelises. In your SSL web traffic example, if you app isn't dealing with as many connections as it has cores, then you probably don't have to worry about performance, and if you do then you already have one compression per core.

Re:Look at MD6

[Omnifarious]

I would like proofs of security to assume the availability of quantum computation. Do your proofs of security assume this?

Re:Look at MD6

[owlstead]

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.

Re:Look at MD6

[Dan Ost]

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

[Omnifarious]

Yes, but not a major threat. Quantum computers allow the search time to be cut to the square root of the normal search time. This effectively halves the key length. A 256 bit key now takes only an average of 2^127 operations to find instead of 2^255.

This isn't nearly so much of a problem though as for public key encryption schemes. For RSA, for example, quantum computing changes the time from super-polynomial but sub-exponential to being polynomial with a very low exponent.

I would be really curious to see a study of the effect of quantum computing algorithms on one-way hash functions.

Re:Look at MD6

[Dan Ost]

Thank you for your great response.

Salts...

[Manip]

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:Salts...

[jd]

True, a good dose of salt will improve the hashes. (But it may lead to higher blood pressure.) My concern is that the vast majority of "hackers"/crackers are either skript kiddies or macho wannabes. They can exploit known weaknesses, they can use known techniques, they can download known black hat toolkits, but they will never discover or write anything worth a damn themselves.

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 (only might) marginally increase the risks with the remaining 1% for the short timespan it takes for you to plug in a different PAM module and re-enter the passwords.

You are entirely correct in saying that heavy salting will have the same effect as using a different algorithm, at least as far as pre-existing cracking tools are concerned and probably as far as any future cracking tools are concerned, provided there are no major function weaknesses found and the hash lengths are the same.

However, your salting method then becomes just as much of an unknown as the alternative algorithm, and all you do is rename the problem of using an untested algorithm without actually changing it. In fact, a sufficiently complex salting method will transform any hash function into any other hash function, provided they have the same basis and produce the same length of hash.

In the end, given that both proprietary and open source software have been subject to numerous zero-day vulnerabilities over the years, given that both have retroactively removed features, functions and capabilities with both regular and emergency patches, and that both expressly deny any "fitness for use" guarantee, the excuse of "but it might not work" sounds, well, feeble and ever so amusing. It's a "who dares, wins" world and those who do nothing will go nowhere.

Re:Salts...

[Anonymous Coward]

There are also solutions out there that can create collisions to an arbitrary message by adding random data to the end of the file. Check the Xiaoyun Wang and Hongbo Yu papers and the follow-up solutions to that.

My favorites: Keccak and Skein

[Ex-Linux-Fanboy]

I spent a few hours the other day looking over all of the submissions; Keccak and Skein are my favorite contributions. My criteria was "does the hash generate a fixed-length output, or is the hash capable of also being used as a stream cipher".

There are only four unbroken contributions that can generate arbitrarily long streams of numbers: Keccak, LUX, MeshHash, and Skein. 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

[Anonymous Coward]

32-bit is dead, that shouldn't be the reason behind choosing one over the other. For embedded systems you can always use dedicated hardware.
Some submissions require several processors in parallel to reach a decent bitrate.
That said, those two submissions sound pretty similar when you read their descriptions.

Re:My favorites: Keccak and Skein

[Anonymous Coward]

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.

Re:My favorites: Keccak and Skein

[hypersql]

A better overview: The SHA-3 Zoo. Did you look at Edon-R? It is not be the most flexible, but it's the fastest one. Followed by Skein. I agree to what Bruce Schneier wrote: sort the algorithms based on performance and features, and then focus on the top 12.

Re:My favorites: Keccak and Skein

[tangent3]

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.

Re:My favorites: Keccak and Skein

[ultranova]

My criteria was "does the hash generate a fixed-length output, or is the hash capable of also being used as a stream cipher".

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 function anyway.

Re:My favorites: Keccak and Skein

[collinstocks]

The problem with this, of course, is that due to the Birthday Paradox, you will start creating a loop after (on average) sqrt(NUMBER_OF_POSSIBLE_HASH_OUTPUTS). For short messages, this is usually okay, but for long streams of "random" bytes, this is totally unacceptable.

On the other hand, you could use a stream based on the following:

hash("1"+SEED)+
hash("2"+SEED)+
hash("3"+SEED)+
hash("4"+SEED)+ ...
hash("1231142"+SEED)+
hash("1231143"+SEED)+ ...

assuming that your hash has a distribution indistinguishable from a random distribution.

By the way, the reason you put the SEED after the consecutive strings is that if two different seeds result in the same hash state, it will not matter since they are editing the state instead of creating it initially. Assuming a secure hash, hash(A)==hash(B) does not imply that hash(C+A)==hash(C+B) although in all modern hashes that I know of, it usually implies that hash(A+C)==hash(B+C) since new data edits the old state, and old data has no chance of editing the new state.

I hope my explanation makes sense, but if it doesn't, ask questions and I'd be happy to elaborate.

Re:My favorites: Keccak and Skein

[ultranova]

The problem with this, of course, is that due to the Birthday Paradox, you will start creating a loop after (on average) sqrt(NUMBER_OF_POSSIBLE_HASH_OUTPUTS). For short messages, this is usually okay, but for long streams of "random" bytes, this is totally unacceptable.

Good point. I assumed that you'd loop after 2^hashlength, but of course even that has the same problem. I guess it just goes to once again show that cryptography should be implemented by real experts :).

How about using hash(n + previous_hash) ?-)

By the way, the reason you put the SEED after the consecutive strings is that if two different seeds result in the same hash state, it will not matter since they are editing the state instead of creating it initially. Assuming a secure hash, hash(A)==hash(B) does not imply that hash(C+A)==hash(C+B) although in all modern hashes that I know of, it usually implies that hash(A+C)==hash(B+C) since new data edits the old state, and old data has no chance of editing the new state.

/blockquote>

Why would that matter ? The attacker still knows the state of the hash just prior to inserting the SEED, so what do we gain from this ?

Re:My favorites: Keccak and Skein

[collinstocks]

Why would that matter ? The attacker still knows the state of the hash just prior to inserting the SEED, so what do we gain from this ?

You're right. I hadn't thought of it that way. I suppose that the only real solution to this would be to double the message, such that every part of the message has a chance to affect the resultant state after every other part of the message has been hashed, ie:

hash(n+SEED+n+SEED) or hash((n+SEED)*2) depending on your personal preferences for pseudocode.

I will now assume that a truly secure hash algorithm does this automatically and move on.

How about using hash(n + previous_hash) ?-)

hash(n+previous_hash) is also totally unacceptable. Each new hash value has a 1/(2^hashlength) chance of colliding with another sequence created using an arbitrarily chosen SEED. Again, I invoke the birthday paradox. After 2^(1/2*hashlength)==sqrt(2^hashlength) new numbers there will be a 50% probability of the two sequences colliding and being the same sequence thereafter.

I suppose you probably already understood this to some degree, as you put a "?-)" after your question, but I decided to answer seriously anyway.

By the way, IANACE (I am not a cryptology expert), but I have read some books on it and taken a course at CTY, and have also done some of my own research online and theoretically (ie, thought experiments having to do with ideal systems AND practical systems).

I CALL BULLSHIT/FLAMEBITE!

[Anonymous Coward]

NESSIE has never had a competition _specificly_ for hash function.

Re:I CALL BULLSHIT/FLAMEBITE!

[Anonymous Coward]

Furthermore, how can only one submitted entry resulted in so many "winners"?

** MAC algorithms and cryptographic hash functions **
Two-Track-MAC: Katholieke Universiteit Leuven and debis AG
UMAC: Intel Corp, Univ. of Nevada at Reno, IBM Research Laboratory, Technion Institute, and Univ. of California at Davis
CBC-MAC*: (ISO/IEC 9797-1);
HMAC*: ( ISO/IEC 9797-1);
WHIRLPOOL: Scopus Tecnologia S.A. and K.U.Leuven
SHA-256*, SHA-384* and SHA-512*: NSA, (US FIPS 180-2)

???

in case of slashdotting, bittorrent

[scervisiae]

Here is a torrent of all 51 submissions: http://thepiratebay.org/torrent/4592403

Re:in case of slashdotting, bittorrent

[jd]

If NIST can get slashdotted, we have far more serious problems than just hash functions being broken and we should go back to being an agrarian culture. A far more likely outcome (and, IMHO, a better one) would be for the mailing list to explode in new members (a total of 51 + non-entering SHA3 Zoo contributors shouldn't be too hard to beat) asking totally obvious questions that weren't asked (because they were obvious) but should have been (because arguing a point is a superb way for the arguer to spot weaknesses in their own argument). We can then dispense with the more blatantly flawed algorithms far faster and far more reliably than by having a clique studying them over coffee breaks. (Professors teach first, do paid research second so that they can afford to feed their family, and do REAL research when no-one's looking. That's why so little real innovation ever happens, except by "accident", for which you should read that the research notes were sold to the CEO over a liquid lunch in exchange for immunity for the crime of thinking and a christmas bonus).

Popular wisdom has a very good reason...

[kscguru]

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.

Re:Popular wisdom has a very good reason...

[jd]

Err, well, no. They can take out features, they probably have in the past and they certainly will in the future. Linux is no different. Those who wrote code assuming Intermezzo or the kernel-based devfs would always be there are, well, victims of their own folly.

The same applies to hash functions. You have some mechanism for identifying which function you are using and then you use it. Hard-coding is for wimps and fools, and is almost always the true cause of backwards incompatibility. Correctly-engineered software either uses defines or, if it's really good, negotiates. Bad software, and pandering to it, is why Windows has accumulated more crud than a farmyard without the benefit of being able to use it to fertilize.

(Despite conventional wisdom, Windows is not popular because it supports bad software. It's popular because it's pre-installed and has enough good software that people can ignore all the bad crap. If Linux were to insist on supporting all of the bad crap written for it - do YOU use a.out binaries still? - for the indefinite future, it would not improve its popularity. If anything, it would risk the popularity it has gained and its forward momentum, all achieved by willingly sacrificing the bad from the past (with the exception of X11) in favour of developing the good for the future.

Article is out of date

[Argilo]

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.

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.

Re:Article is out of date

[jd]

I dunno. From th last time NIST updated its website to the last time SHA-3 zoo updated theirs, a whole bunch more functions got broken. And as the pool dwindles, the number of crypto experts studying each function increases and the value (both of breaking the hash and in terms of PR within crypto circles) rises. Sure, it won't be linear, but I don't expect the fall-off to happen for a while yet. IF anything, the breakage might rise for a brief time as the holidays afford precious extra thinking time and a whole bunch of extra CPU time.

(CPU time? Sure. No better way to look for relationships between inputs and output when changing inputs in predictable ways than to have a computer churn through input rules and output rules. Humans are great at analyzing the algebra which, despite having theorum solvers, computers suck at, but humans are horrible at tedious, repetitious tasks, and inobvious relationship detection often requires a lot of tedious, repetitious examining of raw data.)

Ugh..

[Junta]

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:Ugh..

[ultranova]

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.

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 yottabytes ?

Re:Ugh..

[Junta]

Both /etc/shadow and the SAM database should not be readable by users, correct. The assumption is that some offline attack or online exploit is leveraged first in either case. For example, a local hard disk from a workstation is extracted and the local administrator/root password cracked. Chances are high that the password is the same on other workstations that may be hard to mount an offline attack on.

I counted the salt in the 10^73 yottabytes. Which I agree is beyond any feasibility for presumably a long time to come.

I honestly don't understand why the hell MS fundamentally architected their security the way they did when they went to NTLMv2. They changed to MD4 hashing for local password store, but still didn't salt. In a network environment, the client doesn't even need to crack a compromised hash, just use it. The default now is to encrypt the SAM database, but that is kinda moot in most configurations as the password is in the clear on disk.. In effect, the hashing is just pointless on multiple levels in their architecture.

does a bear poo in the woods?

[lkcl]

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 - 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:does a bear poo in the woods?

[Omnifarious]

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.

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 through almost any mental contortion imaginable to be able to pretend it doesn't exist.

Re:does a bear poo in the woods?

[jd]

MD5 is effectively broken, replay attacks against debit and credit cards are commonplace (banks lose millions to it yearly), and the use of it in something as commercially sensitive as a credit card is the height of stupidity. "If" it is ever broken doesn't apply, because enough weaknesses have been established to prove conclusively that a total breakage is just a matter of time. If it hasn't already happened. I doubt organized crime or the NSA file the hashes they can break with the Hash Function Lounge.

Peer-to-peer is being broken all the time. P2P poisoning is a common technique for killing shares in a specific file.

Authentication systems -ARE- falling over, Internet banking systems -ARE- highly exposed, the International Monetary Fund is said to have been cracked! It's too late to say "if if if", the "if" has been, gone, and stolen your cup-a-soup. It was already too late when the first rumours of a breakage in MD5 were surfacing. As JRRT point out in LotR, it's too late to call for help when the enemy army is on your doorstep.

The time to change is before things break, but when the probability of them doing so soon exceeds acceptable thresholds. Anyone who waits until things break before fixing them might want to talk to the ghosts of airline pilots on the wisdom of such a strategy. Anyone who waits until many years after the disaster has struck to consider jumping ship might want to consider the re-arranging the deckchairs on the Titanic as a future profession.

Hell, how long has it been since the DNS vulnerability was found? And how many home users have patched their cable modems or DSL modems accordingly? Of those, how many have, or are likely to in the forseeable future, been subject to attacks by zombies, phishers, or other malware/malbeings who can exploit such flaws?

Are they being smart? Hell no. Are they being wise, in not installing less-tested, less-proved, newer alternatives? Hell no. Are they being so conservative that stupidity is oozing out their ears like rampaging earwax? Oh most definitely yes. Are they worthy of so much pity that all software should be backwards compatible with their defects of software and defects of character? Oh God I hope not! (If ever there was a place for a God in this world, it would be to throw lightning bolts at people whose brains resemble a TRS-80.)

Re:does a bear poo in the woods?

[jcam2]

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).

I sure as hell hope not! If that was the case, anyone with a card reader could brute-force your PIN in under a second by taking the MD5 hash of all 4 digit numbers, and comparing them to be hash that is supposedly on the card.

Re:does a bear poo in the woods?

[Bob of Dole]

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.

Bullshit and chips. Look, there are only 10,000 possible pins, do you know how long that would take to force? Hell, a complete rainbow table is only 156k. Even if salted, do you know how long it takes to hash 10,000 4 digit numbers?

There. Just did it. Took 0.1 seconds on my 800mhz laptop.

Your information does not pass a basic sanity test.

(Plus, it's debit cards which have PINs, not credit cards)

Re:does a bear poo in the woods?

[Anonymous Coward]

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).

I don't believe it, for the simple reason that my credit card (I've only got one) doesn't HAVE a PIN to begin with.

(Also, "PIN number" is redundant.)

Re:does a bear poo in the woods?

[mollymoo]

(Plus, it's debit cards which have PINs, not credit cards)

Most credit cards do, or at least can, have a PIN so you can use them to withdraw cash from a cash machine (ATM). In the UK, and increasingly in the rest of the world, you now enter your PIN rather than signing a piece of paper when making purchases too.

Triple MD5 Anyone?

[Nom du Keyboard]

Triple MD5 anyone? Hey it worked to extend DES!

(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:Triple MD5 Anyone?

[owlstead]

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:Triple MD5 Anyone?

[LargeMythicalReptile]

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 to get an idea of what NIST wants out of this. It's a lot broader than "a patch on MD5."

Re:Triple MD5 Anyone?

[owlstead]

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.

Security vulnerability

[Meor]

The fact that the OS community uses MD5 still just shows how slow it is to move to new technology. MD5 is broken, it's trivial to collide. There are free alternative hashing algorithms. Stop using MD5, stop using MD5, STOP USING MD5!

Credit Card fallacy

[Anonymous Coward]

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.

It looks slow.

[DamnStupidElf]

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 fully optimized yet?

2ROT13

[jgtg32a]

It's all you ever need

MS didn't go to CMU?

[Mathinker]

> I honestly don't understand why the hell MS fundamentally architected
> their security the way they did when they went to NTLMv2.

See CajunArson's comment above --- the section about "NEVER DO IT YOURSELF" and "peer review".

I cannot be sure about what caused that bad decision at MS, but two things come to my attention:

• Microsoft is largely obsessed by securing and obscuring its "IP", which probably doesn't encourage them to understand that in this case, the opposite philosophy (open review) would be better,
• As Bruce Schneier points out, insecurity of Microsoft products is largely an externality to the company (they lose face with a few geeks, or lose a few customers for whom security is the be-all and end-all), so there is little incentive to invest effort to do it correctly.

Er, what "class" is that?

[Mathinker]

> The class of problem, in the general case, is NP-complete

You lost me there --- what class of problem connected with the security of cryptographic hash functions is in general NP-complete?

HHGTTG

[Mathinker]

Wait, you haven't figured out that Slashdot is the compression function of the cryptographic hashes of an advanced extraterrestrial race (whose projections in our reality are, well, whatever you find most amusing)?

Re:HHGTTG

[Omnifarious]

That explains so much. Thank you!

Huh?

[RichiH]

The first third of the submission is interesting, relevant and sane. The rest, especially the question, is based on so much mis-understanding of the topic at hand, I just lack the time to point all of it out. I suggest OP re-thinks the effort of switching to new _and maintaining the old_ hashes for a second or twenty. That should be a good starting point for some relevations.

Test-burning every match

[wild_berry]

It's Schrodinger's cat: you might prove it secure by exhaustively mapping its function over the whole input range and then assessing the proximity of results and the psuedo-randomness of the mapping. The problem with that being that you then know how to recover any original text from a given encrypted result...

If you want a newer hash, use SHA-2

[Anonymous Coward]

"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?"

MD5 and SHA-1 both have attacks that break them, in theory. I'm not certain how practical any of those attacks are. Certainly, even if they are practical, they do not matter in all applications. For example, not in the HMAC used in IPsec.

There are no breaks yet for SHA-2 but its design is based on SHA-1 so it seems possible there might be at some point.

If you want something better than MD5/SHA now, use SHA-2. The SHA-3/AHS contest specificies an SHA-2 interface, so whatever wins that contest (in 2012) will be a drop-in replacement.

Some details at:
http://en.citizendium.org /wiki/Hash_(cryptography)#The_Advanced_Hash_Standard

I'm shocked...

[Anonymous Coward]

...that the attitude demonstrated by this post hasn't been blasted into submission. The writer seems to be illogically dismissive and adverse to any foundational research without immediate applicability.

First, as mentioned earlier, the weak algorithms submitted to the contest will be quickly broken. I wouldn't be shocked if well under half remain after only a short period. These contests draw attention to a problem, increasing the chance for insights. This is why experts are willing to endure the pain of going through these submissions, including the bad ones. Criticizing the contest on the basis of the number of submissions is absolutely backwards. If the contest discouraged quality submissions in some way, I might be more agreeable, but I see no such argument.

Second, sure it will be years before any proposals are used. Medical research may take years to result in useful treatments -- if ever. That fact doesn't mean that medical research should be abandoned. Although one could make an argument about the lifetime of existing cryptographic hash functions and expected value of developing new ones at this time, I see no such argument.

Finally, the post seems to suggest that we shouldn't try to develop new algorithms when we can instead devote effort to understanding old ones. Taken to its logical conclusion, no new algorithms would be developed: we'll always understand what is available today better. The point of this isn't to immediately replace what's available. The point is to have new, stronger algorithms that we might trust in a few years (and will become useful as more flaws emerge in today's algorithms).

As a cryptographer, I am well aware of the need to be extremely conservative in the algorithms used. I don't think that we should stop looking for positive results, however.