Slashdot Mirror
More on Newly Broken SHA-1
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."
"The findings are that SHA-1 is not collision free"
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.
Kidding about math on /.? You should know better...
Totally agree, however in the crypto community (which I cannot claim to be part of) the consensus is generally that if a weakness if found in an algorithm then it begs the question - "what other weaknesses are there".
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.
[ Monday is a terrible way to spend one seventh of your life. ]
So someone with $36 million to throw around can, in 56 hours, produce two random messages with the same SHA-1.
::cough::
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.
Moore predicted that the number of transistors per integrated circuit would double every eighteen months, not that the cost of computing would halve every eighteen months. More strictly speaking it's corollary that some people draw from Moore's law.
Having worked in the crypto field, I thought I would take some time to clear up a few misconceptions. First off, the results of this paper in no way compromise the security of email or other data encrypted with algorithms that use this hash. As an extension of Moore's law prevails, these characteristics of any hash function are bound to be discovered. However, with that said, it is important to realize that this new discovery in mathematics allows us to move forward with hash technology to develop better algorithms.
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.
I presume that finding two colliding contracts both written in a meaningful and legally binding language is harder than finding a simple collision.
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.
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.
How can you use my intestines as a gift? -Actual Hong Kong subtitle.
Or a pdf-file, i bet there is more that 69 bits of entropy there that is not visible to the reader.
FRA: STFU GTFO
Never attribute to wittiness what can be attributed to plain, near infinite, stupidity. Yes, the typical /. poster is _that_ dumb.
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).
AccountKiller
it look prescriptive. passe is Grammar up
sure You ? are
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
For your 38 million you could construct an machine that would create two random messages that hash to the same value. Totally useless.
Not true. The use of that is creating one legitimate document and apply a certification to it, with the authority of a trusted certifier (who would have verified it, because it is legitimate).
At the same time your $38M machine would create a second document, with whatever information you care to put in, which that certifier would never touch. They have the same hash, so you could substitute in the bad document for the real one, and the certification would be entirely indistinguishable from authentic.
and start working on better hashing algorithms.
Something tells me that the work on better hacking algorithms has already been started.
In theory there is no difference between theory and practice. In practice there is. - Yogi Berra
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.
"Alcohol, Tobacco, Firearms, and Explosives" should be a convenience store, not a government agency.
I didn't bother following the "bastardizing English" link, but whatever it says, ignore it, because you understand the "to beg the question" controversy correctly.
The bastardized definition of "begs the question" was spawned in the minds of ignorant people and draws life from the thick-skulled arrogance of the same.