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