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