Slashdot Log In
More on Newly Broken SHA-1
Posted by
CowboyNeal
on Sat Feb 19, 2005 09:32 AM
from the all-hands-abandon-ship dept.
from the all-hands-abandon-ship dept.
AnonymousStudent writes "Details are out about the reported broken SHA-1 hash function. The findings are that SHA-1 is not collision free and can be broken in 2^69 attempts instead of 2^80. This is about 2000 times faster. With todays computing power and Moores Law, a SHA-1 hash does not last too long. Using a modified DES Cracker, for the small sum of up to $38M, SHA-1 can be broken in 56 hours, with current computing power. In 18 months, the cost should go down by half. Jon Callas, PGP's CTO, put it best: 'It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off.' As Schneier suggests, 'It's time for us all to migrate away from SHA-1.' Alternatives include SHA-256 and SHA-512."
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.
Break only affects carefully constructed messages (Score:5, Informative)
Re:Break only affects carefully constructed messag (Score:5, Insightful)
Once an algorithms strength is in doubt by the presence of even one weakness people feel very reluctant to trust it.
Its probably up to everyone to see how this affects their own circumstances. Crypto is always about Knowing your enemy (the paranoia has now kicked in !). When picking a scheme one always makes a number of assumptions - Who are you keeping the information hidden from, what resources do they have, how badly do they want it.
No crypto is powerful, or clever enough (yet!) to be completely unbreakable so its all down to making assumptions:
1)
Would someone be willing to pay $38 million (assuming this is correct) to get my credit card number - probably not.
2)
Would someone be willing to pay $38 million to get insider info on a merger between two banks - each worth over $10 billion.
What unsettles people is that their previous assumptions on SHA-1 are now invalid.
Parent
Price (Score:3, Interesting)
There are 8776 hours in a year. Assume the machine has a life of 3 years before it becomes obselete. That means (discouting TVM at 0% for simplicity) the machine can do 470 problems of this type in three years, breaking even at a little over $80 per problem.
Damn that just got a lot lot cheaper.
Re:Price (Score:5, Informative)
Parent
Re:Break only affects carefully constructed messag (Score:5, Insightful)
2)
Would someone be willing to pay $38 million to get insider info on a merger between two banks - each worth over $10 billion.
Except SHA-1 isn't an encryption scheme, it's a hashing algorithm. For your 38 million you could construct an machine that would create two random messages that hash to the same value. Totally useless. Really what you want to do is find a message that hashes to the same value of a specific message. Or even better you'd want to create an arbitrary message, tack on some header or footer and have that hash to some chosen hash.
If I understand message signing and digital signatures, an attacker wants to make it look like they're the intended target. Say I send a signed message to my bank saying "please transfer $1,000,000 to account 123456". An attacker wants to generate a message like "please transfer $1,000,000 to account -attacker account number- that will hash to the same value, so he/she can use the same signed digital signature. The 38 million dollar device won't be able to do that in 56 hours, I doubt you could do it in 56 years (and I highly suspect it would take MUCH MUCH longer).
Parent
Re:"begs the question" (Score:4, Insightful)
sure You ? are
Parent
Re:Break only affects carefully constructed messag (Score:5, Informative)
If they're prepared to spend a realistic level of time on it they could create two of them that hash to the same thing, with a small but effective change to the second.
You sign the first with SHA-1, but your signature also matches on the second, putting you in a weak position when you try and claim "I didn't sign _that_!"
The time/money requirements to do this aren't really practical yet, but they will be soon.
As the sub says, time to start shifting off SHA-1.
Parent
Re:Break only affects carefully constructed messag (Score:3, Informative)
Creating pseudo-random numbers that hash to the same value != making any arbitrary document hash to the same value.
Making collisions easy (Score:5, Insightful)
Write the contract in MS Word and use huge uncompressed BMPs for the company logos. You have instantly enough space for subtile changes to create collisions.
Parent
Collision free hash? (Score:5, Insightful)
Since when is it possible to have a collision free hash when the hashed data has more possibile bit combinations than the hash itself?
Genuine question.
Re:Collision free hash? (Score:4, Interesting)
With 160 bits of hash, the probability that two pieces of data will hash to the same value is incredibly low. Using a brute-force technique, you'd have to use all of the computers on the planet for thousands of years to find a collision. This is, for all intents and purposes, "impossible", and thus the hash is effectively collision-free.
With the new findings, a wealthy organization could actually find a collision with a reasonable amount of money and time.
Parent
Re:Collision free hash? (Score:5, Interesting)
The width of hash has little to do with the probability of a collision by an attacker. The cleverness of the hash algorithm is the key to collision resistance. For example, a checksum is a hash that merely breaks the int into 160 bit chunks, adds each chunk to together, takes the lower 160 bits of the sum, resulting a 160 bit hash. It is trivial to find for any given message, multiple messages that checksum hash to the same value. Thus far, no one has proven they can do that with SHA-1 (or MD5 for that matter), at least not trivially.
Of course, once one has a clever algorithm, width of the hash can be a nice factor in building up its strength, assuming the hash algorithm lends itself to scaling that way, as SHA apparently does, with SHA-256, SHA-512 being available.
Of course, for random data corruption due to faulty hardware or software, a 160 bit checksum would be excellent (if costly) protection. But that isn't what we are talking about here.
Parent
Re:Collision free hash? (Score:5, Informative)
Parent
Re:orders of growth (Score:3, Informative)
Re:Collision free hash? (Score:3, Insightful)
(Stupid Mean Girls quote)"Anything else is like...against the laws of feminism or something!"
Re:Collision free hash? (Score:3, Insightful)
Re:Collision free hash? (Score:3, Informative)
SHA-1 (Score:5, Funny)
Re:SHA-1 (Score:4, Funny)
Parent
Hmmm (Score:5, Informative)
Well, doh - it's a hash you silly, there will always be collisions.
Anyway, it's nothing to panic about really. The ammount of computer power needed to crack it is still massive. Unless you're investigated by the NSA, SHA-1 will be fine for quite a while.
Follow-on work (Score:5, Informative)
Parent
This is big... (Score:4, Interesting)
Re:This is big... (Score:5, Informative)
Parent
Re:This is big... (Score:3, Informative)
56 Hours? (Score:3, Informative)
Is that assuming that that the collision will be found on the last (or in this case, 590,295,810,358,705,651,712nd time) try?
Because statistically it's just as likely you will find a collision on the first try as you are on the last try.
Crypto custom... (Score:3, Informative)
Re:Crypto custom... (Score:5, Informative)
It takes roughly 56 hours to go from a message of which hashes to 0xAABBCCDD11223344, to a message of whichh also hashes to 0xAABBCCDD11223344, which means that it would have an identical signature, meaning that the original signature would validate the fake message.
Personally its not the huge end-of-the-world scenario everyone thinks it is. It would probably take tens of thousands of years for this machine to output a well-formatted message that had a hash collision and could not be trivially discarded as gibberish.
Parent
The True Deadline (Score:4, Interesting)
The cost of cracking SHA-1 in...
3 Years - $9.5 Million
6 Years - $2.3 Million
9 Years - $600,000
12 Years - $150,000
15 Years - $37,000
18 Years - $9,000
21 Years - $2,500
Re:The True Deadline (Score:4, Insightful)
Parent
Theoretical security concerns... (Score:5, Insightful)
Great.
So, presumably, this devious (and very rich) hacker might produce the following two messages:
"bma p3 rjphta,-9p.u2#H50982u.yha,cp. hxasnip"
and
"BUEQXBBX2 jma93#9g5xbaida htuEXOAhkra1255,y"
And then, of course, he'd somehow trick me into signing "bma p3 rjphta,-9p.u2#H50982u.yha,cp. hxasnip". Because I sign random pieces of gibberish all the time, if asked. And then, having done this, he could go around claiming that I had actually signed "BUEQXBBX2 jma93#9g5xbaida htuEXOAhkra1255,y".
OH NO!
Sure. Moving to SHA-256 is all well and good. But, frankly, I think these reports are horribly overblown. Crypto geeks are jumping up and down with their hair on fire (just like George Tenet!) because their perfect algorithm is slighly less perfect in a way that doesn't have any real practical meaning in most situations.
Meanwhile, there are real security problems out there in the form of poorly written software and poorly administered systems. Please, please do not spend your time rewriting your software to use SHA-256 when you could be patching real security holes. Leave SHA-256 until you have nothing better to do.
Re:Theoretical security concerns... (Score:4, Informative)
It might not be that much harder to generate a collision like this:
- I, John Smith, agree to sell my coin collection to Fred Jones for $10. -- JonesCo internal business form bma p3 rjphta,-9p.u2#H50982u.yha,cp. hxasnip
and- I, John Smith, agree to sell my nubile teenage daughter to Fred Jones for $10. JonesCo internal business form BUEQXBBX2 jma93#9g5xbaida htuEXOAhkra1255,y
And if cryptographers are finding stronger and stronger attacks against SHA1, it's foolish to assume the attacks won't get any stronger.Parent
Re:Theoretical security concerns... (Score:3, Informative)
It is because given any string, I can produce another string with the same hash faster.
No, that would be a pre-image attack. This is a collision attack. To perform it, the attacker needs to be able to choose both strings.
Re:Theoretical security concerns... (Score:5, Interesting)
So this means that I can generate a colliding pair in 2^69, but I have to generate pairs of strings without fixing any of them.
That's it exactly. In the case of an unbroken hash that outputs 160-bit blocks like SHA-1, you'd need to generate 2^80 hashes, on average to find a collision. The reason this is 2^80 and not 2^159th is the effect of the birthday paradox [wikipedia.org].
Interestingly enough...if the hash is perfect then the collision attack and pre-image attack would require the same computational complexity....which makes me think is usually not the case given any hash function in P memory and time.
That's a very interesting statement. What do you mean by "perfect" and can you elaborate on how a hash that is "perfect" has the same collision and pre-image attack complexity? It seems to me that a "perfect" (my definition) hash that produces n-bit outputs should have no pre-image attack that has better than 2^(n-1) complexity, whereas the birthday paradox will allow a collision attack with approximately 2^(n/2) complexity (that's a really rough approximation, but it's close enough for most purposes).
Obviously it is the case in the perfect hash function...but the only perfect hash that I can think of requires exponential space.
Not so obvious to me, unfortunately, but it could be that I'm just slow. Not an infrequent occurrence, unfortunately :-/
What's the perfect hash function you're thinking of?
Parent
Here is the paper!! (Score:3, Informative)
whirlpool anyone? (Score:3, Informative)
Advice: use toolkits like SASL (Score:5, Informative)
That is why anyone developing new protocols and products that rely on security should use SASL, which abstracts the crypto layers in such a way that it's easy to change them over time.
SASL is an IETF standard and there are open source implementations like Cyrus.
Clearing up some myths... (Score:5, Insightful)
Hash algorithms are one of the least understood principles in cryptography. The established mathematics around them is contemporarily vague, but under constant research. Therefore, anytime a new publication illustrates a flaw, technique, weakness, etc. we should be pleased that our understanding has grown and that a new, more advanced algorithm can be created with the knowledge gained.
This discovery is a not something to panic about, but rather an achievement that will bring about newer, stronger encryption technology.
Re:2000 times faster? (Score:5, Interesting)
2^80 = 2^11 * 2^69 = 2048 * 2^69
Parent
Re:2000 times faster? (Score:3, Insightful)
Re:2000 times faster? (Score:5, Funny)
Just goes to show, the quickest and most effective way to get information on the net is to post something that is wrong.
Parent
Re:2000 times faster? (Score:5, Funny)
Parent
Re:2000 times faster? (Score:3, Funny)
Re:2000 times faster? (Score:3, Funny)
>>> FIRST CORRECTION
>> 15th actually, and you were wrong anyway.
> Depends on the desired precision.
Certainly. Because 1 is approximately equal to 15 for large values of 1 and small values of 15. If you squint.
Re:Yet Another Overblown Crypto Hack (Score:4, Informative)
Attacks on hashes have absolutely nothing to do with discovering any kind of content, they have to do with the reliability of digital signatures, key exchange, data integrity, authentication etc.
As for any kind of cryptography being sufficient...no, not really. Consider CSS...the encryption used on DVDs is no longer considered any kind of barrier to access.
Similarly publicly visible hashes in password files on Unix systems haven't been considered secure for over 10 years, due to the simplicity and success rate of dictionary attacks (plus more recently, brute force is becoming increasingly easy).
Parent
Re:Question about bit-flipping in SHA-1 (Score:3, Informative)
Re:Unrealistic? (Score:4, Insightful)
Read the whole comment: By "impossible", Bruce means "so hard it isn't worth trying." Obviously, there is no way to make an absolutely one-to-one correspondence between arbitrary-length messages and fixed-length hashes. The idea, therefore, is to make it so difficult to generate two messages with the same hash that it isn't worth anyone's effort to try.
Absolute security is almost always a chimera. You can only really achieve it with one-time pads, which aren't practical for the vast majority of cases. So you try to make things so difficult to crack that by the time anyone has succeeded, nobody still cares about the security of that message. Ideally, therefore, breaking one message does nothing to help you break any other message.
The crack of SHA-1 does help an attacker break any security system that uses SHA-1 by making it much easier to generate two messages that map to the same hash. This kind of thing makes cryptographers sit up and take notice, and hopefully develop some new algorithms. We have algorithms better than SHA, but until now nobody's had much reason to use them. This should change that.
Parent
Re:Why use SHA at all? (Score:3, Informative)
Hmm...but SHA is a hashing (i.e. one way) algorithm, and Blowfish is an encryption (i.e. bidirectional) algorithm. (For more on this, see the page you actually linked to.)
So you don't use SHA-1 as an encryption algorithm for stuff like SSH, etc., because, well, you can't. Well, you can encrypt, but good luck decrypting :-)
But you might use SHA-1 to generate crypto keys from plaintext data (e.g. passwords) for use by an encryption algorithm. So 'switching to Blowfish' won't help - you need to switch t
not yet a fire alarm. (Score:4, Informative)
What, is that new? That already follows from the fact that there are only N possible hashes, and M possible messages, and NM. In other words, if you have an 8-bit hash (256 values) for a, say, 1K message, then you must get a lot of collisions.
If it takes only three days or so to find a collision, what does that mean practically? Almost nothing. Because the collision that you would find is most likely meaningless. The modification that you'd like to apply to the message (while sticking with the same, given hash) is likely to be something very specific, for example, change $1000 to $10.000. And that, unfortunately, is not easy. This vulnerability can't be easily exploited at this point.
But even saying that "if the algorithm has one vulnerability, then it's likely to have others" is totally illogical - unless a whole class of vulnerabilities has been pointed out.
It's not even time to 'walk to the door' because the fire alarm has gone off, as someone said later down in the comments. Instead, it's time to read the Chinese paper, produce more truthful descriptions of how much of a problem we are going to get with this (does it lead to more severe vulnerabilities), and start working on better hashing algorithms.
Parent
Re:not yet a fire alarm. (Score:4, Insightful)
What, is that new? That already follows from the fact that there are only N possible hashes, and M possible messages, and NM. In other words, if you have an 8-bit hash (256 values) for a, say, 1K message, then you must get a lot of collisions.
Thank you for addressing this early in the postings. I was about to go insane when I read that in the story post.
Come on, it's the basic Pigeonhole Principle. Computers Science students should have learned this in Discrete Mathematics. If you didn't, it says this: If you've got 10 holes and 11 pigeons in them, then one hole has two pigeons.
If it takes only three days or so to find a collision, what does that mean practically? Almost nothing. Because the collision that you would find is most likely meaningless. The modification that you'd like to apply to the message (while sticking with the same, given hash) is likely to be something very specific, for example, change $1000 to $10.000. And that, unfortunately, is not easy. This vulnerability can't be easily exploited at this point.
Precisely. Really, it doesn't matter if it is easy to find a message with the same hash, if the new message is obviously incorrect or unintelligible.
What I don't understand is why nobody has simply suggested using two distict hashes in any particular application. Say, MD5 and SHA-1 together. The ability to find a collision in a few days for either one may exist, but finding a message that causes a collision for both should be very hard.
Parent
Re:not yet a fire alarm. (Score:4, Informative)
To be precise, one hole has at least two pigeons.
Parent