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
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
This is cryptography, so it's always talking about possibilities.
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.
Mod down posts with a "Free Mac Mini/iPod" sig, they're spam!
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.
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/
Are there any dynamic length hash/one-way encryption functions out there? Would these provide greater collision prevention than SHA-1?
Why are hashes like CRC-32, MD5 and SHA-1 fixed length anyway?
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.
When the understanding on a domain starts to gather - in other words the nut to crack - it usually does all the way. It's quite commong to knownledge. In such a notion for instance going to SHA-2 would be moronic and keeping using SHA-1 plain suicidal.
This is a lot worse than many people understand. 38 millions for a cracking machine? Yes, providing there isn't someone who knows one tiny bit more from the domain an has took off more from the complexity. For instance 2^40 would be a disaster. The sad fact is that it is near. Way too near for anyone who really cares.
http://it.slashdot.org/comments.pl?sid=139602&cid= 11685615
(no, it's not even the same nickname)
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
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.
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.
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?
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
> "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.
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?