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."
2^69 attempts instead of 2^80 seems like only 11 times faster, then again, thats just me.
2^80 = 2^11 * 2^69 = 2048 * 2^69
2^69 = 590295810358705651712
2^80 = 1208925819614629174706176
2^80 / 2 ^ 69 = 2^11, which = 2048.
Yep. 2000 times faster.
The new SHA-1 break only affects very carefully constructed messages. This means that it is completely useless for an attacker impersonating an existing message, unless that message was purposely constructed to be attackable. The attack is only useful if the attacker creates both messages, and the attacker can choose the exact format of both messages.
- Sam Ruby
"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.
SHA-1? pshhhh. They should be using SHA+1. Thats 2 more!
Jesus Christ. In the time it took to write my post (all of 30 seconds), five other people replied to you.
Just goes to show, the quickest and most effective way to get information on the net is to post something that is wrong.
The findings are that SHA-1 is not collision free and can be broken in 2^69 attempts instead of 2^80.
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.
We need to develop algorithms aside of SHA. SHA-256 only postpones the problem...
It takes a man to suffer ignorance and smile
Be yourself no matter what they say
I bet $50 that a hard drive manufacturer came up with that!
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. ]
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.
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.
It costs $38M to crack SHA-1 now. According to Moore's law, this will be cut by 25% every 3 years.
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
My Blog Sucks.
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.
Yes, but say someone creates a document (such as a contract) for you to digitally sign.
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.
Remember kids, it's all fun and games until someone commits wholesale galactic genocide.
The attack has nothing to do with trying to discover contents based on the hash, it has to do with generating intentional collisions.
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).
The concern is not so much that the method described in this break is feasible on today's hardware, or even that this method will get cheaper and cheaper as hardware gets faster. The BIG concern is that this method provides insight in to the SHA-1 in general, and will be used by others to come up with more efficient breaks or more egregious flaws.
I'll take that bet! (And you owe me $64 if you lose.)
http://netlab.fe.up.pt/~ei01024/sha-1/
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
Creating pseudo-random numbers that hash to the same value != making any arbitrary document hash to the same value.
It's tragic. Laugh.
As far as anybody knows, no. If such a technique were known, this article wouldn't be very big news. Before this technique, the best way anybody knew of to generate two pieces of data with the same SHA-1 hash was to just try a ton of random data until you found two pieces with the same hash.
Mod down posts with a "Free Mac Mini/iPod" sig, they're spam!
No. It means that it took 2^80 "computations" and it now takes 2^69 "computations".n ode17.html.
O(2^80) = O(2^69) = O(1). See for example http://mitpress.mit.edu/sicp/full-text/sicp/book/
SHA-2 in 256 and 512 bit flavors isn't the only alternative folks. Among other nifty hashes, there's whirlpool: Linux 2.6 kernel crypto API entry for whirlpool and a page with whirlpool details.
http://tinyurl.com/4ny52
All crypto algorithms age, and even if the news of SHA-1's death is somewhat dramaticised by people who make their living from security work, it's important to see _all_ crypto algorithms as temporary shims.
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.
Sig for sale or rent. One previous user. Inquire within.
The £38mn is to build the machine. It is in 1-time use for 56 hours.
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.
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
http://it.slashdot.org/comments.pl?sid=139602&cid= 11685615
(no, it's not even the same nickname)
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
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
is to speak of averages. So, it is likely that 56 hours is the time to search half the keyspace on such a machine, as over a large number of uses, that will be the average time required per use.
I forget what 8 was for.
>>> 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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Whenever I can't figure out how to do something in Linux, I just make a post saying, "Linux sucks because it can't do XXX like Windows can!"
Within 10 minutes, I'll have 50 replies from Linux gurus around the world telling me, "You idiot, Linux's implementation is better than Windows! You just do YYY and ZZZ and boom! Bill Gates sucks!"
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 to a different hashing algorithm (assuming you consider this recent discovery to be a concern for such usage of SHA-1).
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
While the bumbers are only 11 difference yes, 69 is a much slower method for most 80, though I'm not sure its 2000 either.
Wow. That's an absolutely amazing post. It's so wrong, on so many different levels, in so many different ways, and in so *few* words... impressive as hell. You have my respect, sir.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Or, and this is a good one, you could do that. For any message that I create, and sign for SHA-1, it's now possible that I created another duplicate message, and that I could, at any point in the future, say "Oh no, I didn't sign _that_!"
So, there are two lessons to be learned.
1. Don't trust SHA1 as part of an algorithm for signing a document that someone else gave you. Actually, this is not so much of a risk, because any reasonable signature algorithm signs more than just a straight hash of the document.
2. Don't trust any document signed by someone else with an algorithm using SHA1, if they created that document themselves; they might have a way to repudiate that signature, leaving you out in the cold. This one is actually more dangerous.
The findings are that SHA-1 is not collision free
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.
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.
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).
The is that as soon as you try to place specific content in the message, it becomes *much* harder to find a collision that meets your requirements (especially if there are length requirements too).
Now.... Let me bring up one possible use of these issues. If you store passwords as SHA hashes, and if someone can get a list of hashes, then they can find colliding passwords.
LedgerSMB: Open source Accounting/ERP
There are, however, 2^296 messages that are 37 bytes in length, which means that for any 37-byte message, there are by necessity 255 other 37-byte messages that yield the exact same hashes. Sure, most (all?) of the others will be binary gibberish, but there are nonetheless 255 colliding messages for any given 37-byte message.
And that's just for 37-byte messages. If you send a 1 KiB message, there are 2^7904, or around 10^2379 colliding messages.
as soon as you try to place specific content in the message, it becomes *much* harder to find a collision
It's pretty easy to put a whole lot of garbage data in a document. Changing this data wouldn't affect how the document looks, but would of course affect the hash. With this to modify, you could create a collision with the ease mentioned in the article.
If you store passwords as SHA hashes, and if someone can get a list of hashes, then they can find colliding passwords.
No, they can't. You can create a hash collision with a known piece of data, not with a known hash. You would have to know the original password (from which of course the hash is easily computable) to create a password with a colliding hash.
> "Me and my friend went to the store" will never be proper because it makes
> no logical sense.
You clearly have not been paying close attention to the direction the English
language has been headed. Noun inflection has been in the process of dropping
out of the language for several hundred years now, because, frankly, we
mostly don't need it; we have word-order mechanisms for indicating case, so
the inflection is redundant. We've already lost the distinction between the
subjective and objective (not to mention singular and plural) in the second
person pronouns; we're now beginning to lose the distinction between
subjective and objective in the first person singular and are already well
on our way to losing the inflections for gender and number in the third
person. Chart follows...
1650:
1st I, me, my/mine we, us, our/ours
2nd thou, thee, thy/thine ye, you, your/yours
3rd m he, him, his they, them, their/theirs
3rd f she, her, her/hers they, them, their/theirs
3rd n it, it, its they, them, their/theirs
1950:
1st I, me, my/mine we, us, our/ours
2nd you, you/ you/yours you, you, your/yours
3rd m he, him, his they, them, their/theirs
3rd f she, her, her/hers they, them, their/theirs
3rd n it, it, its they, them, their/theirs
2150 (projected):
1st me, me, my/mine we/us, us, our/ours
2nd you, you/ you/yours you, you, your/yours
3rd they, them, their/theirs they, them, their/theirs
We might also lose the attributive possessive and keep only the predicate
form of it, reusing the same form as the subjective and objective for the
attributive possessive. You can already see that starting to happen
colloquially; for now it still sounds very wrong to most of us, but the
change has already begun, albeit gradually.
FWIW, I agree with most of your points in principle, including the one
about begging the question, but I felt the need to point out that the
distinction between the subjective and the objective is more and more
carried only by position in the sentence, rather than by form. The days
when you can say "Him I like" or "Him like I" or "Like him do I" are
rapidly passing; it already sounds pretty odd and Yoda-esque -- but if
we don't do that any more, then we don't need distinct forms for the
subjective and objective case any longer; they are archaisms and will pass
out of use.
Cut that out, or I will ship you to Norilsk in a box.
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.
The findings are that SHA-1 is not collision free
NO hash algorithm which is capable of reducing an arbitrary number of bits to a smaller message digest, is ever going to be collision free when the input is larger than the digest. Ever.
The difficulty is normally in finding a collision, whether through brute force or algorithmically.
It would be possible to design a hash algorithm to have no collisions with input of a length smaller than or equal to the message digest. But that is of pretty limited use when we're talking about lengths like 160 bits.
War crimes, torture, lies, illegal spying... Would someone give Bush a blowjob, already, so he can be impeached?