9
$\begingroup$

I was recently reading that MD5 is "broken" because it's pretty easy to generate collisions (like 2^(L/2)). And the SHA1 (theoretically) fares no better. The solution seems to be hash algorithms that are very slow in comparison.

I am wondering why can't people combine these fast algorithms to get the best of both security and speed? What would be the time complexity to generate a simultaneous MD5 and SHA1 collision? And if it's hard enough, would these make a viable candidate for collision resistant hash applications?

(By simultaneous collision I mean generating a string with same MD5 and SHA1)

Improve this question
$\endgroup$
5
  • $\begingroup$ Do you have a specific use case in mind where you would like to use two different hash functions? $\endgroup$
    – Jedi
    Jun 10, 2016 at 18:57
  • 3
    $\begingroup$ @Jedi: I believe his idea is "if we generate a hash of the form $MD5(M) || SHA(M)$, wouldn't this be stronger than MD5 or SHA1 individually?" $\endgroup$
    – poncho
    Jun 10, 2016 at 19:00
  • 3
    $\begingroup$ Yes, it would definitely lead to fewer collisions. But, there are other hashing algorithms which are faster and have better collision resistance (than MD5...), which might be more suitable. Basically The solution seems to be hash algorithms that are very slow in comparison may not be an accurate assertion. $\endgroup$
    – Jedi
    Jun 10, 2016 at 19:05
  • $\begingroup$ Possible duplicate post from sister site $\endgroup$
    – Jedi
    Jun 10, 2016 at 19:10
  • $\begingroup$ SHA-1 collisions have now been found. SHA-1 is still slightly less broken than MD5. But SHA-1 is now officially broken in practice as well as in theory. security.googleblog.com/2017/02/… $\endgroup$
    – phylae
    Mar 2, 2017 at 3:22

1 Answer 1

Reset to default
20
$\begingroup$

Surprisingly enough, it would appear that generating a simultaneous collision wouldn't be that much more expensive than generating a single collision for SHA-1.

The basic idea is to form a $2^{64}$ wide multicollision on SHA-1; that is, $2^{64}$ distinct messages that all SHA-1 hash to the same value. We can do this by using Joux's idea of forming finding 64 different colliding blocks $B_{i, 0}, B_{i, i}$ such that all sequences $B_{0, a}, B_{1, b}, B_{2, c}, ..., B_{63, z}$ all share the same SHA-1 hash; this can be done by finding 64 successive SHA-1 collisions. The best estimate on finding a single SHA-1 collision is $2^{61}$ SHA-1 compression function calls (Stevens); hence the effort to find 64 such collisions is $2^{67}$ compression function calls.

Once we have such a $2^{64}$ wide multicollision, we just do an MD5 hash of each, and look for an MD5 collision; this takes $2^{65}$ MD5 compression function calls, and yields a collision with good probability.

This yields a simultaneous SHA-1 and MD5 collision with an expected $2^{67}$ computational effort.

Improve this answer
$\endgroup$
5
  • $\begingroup$ What I find potentially prohibitive is storage complexity or storage costs. The naive approach is some (distributed) Map<Hash, Preimage> structure with up to 2^64 items. It can be optimized in various ways, but the lower estimate for the naive structure is 128*2^64 bits = 2^71 bits = 2^68 bytes = 2^28 TiB. Maybe further optimization similar to rainbow tables is possible, but I am curious how far could we go in some time/space tradeoff. $\endgroup$
    – v6ak
    Mar 13, 2017 at 19:19
  • $\begingroup$ @v6ak: I suspect that you could use a Rho cycle-finding algorithm to find a collision with limited memory, at the cost of a (moderate) constant factor to the number of MD5 hashes required... $\endgroup$
    – poncho
    Mar 13, 2017 at 19:29
  • $\begingroup$ @poncho Isn't the number of MD5 compressions to hash $2^{64}$ messages, each $64$ blocks long, closer to $2^{70}$? (And by the way, the SHAttered paper mentions $2^{63.1}$ SHA1 compressions, so it seems the earlier estimates of $2^{61}$ were slightly optimistic.) $\endgroup$
    – yyyyyyy
    Aug 13, 2019 at 0:15
  • $\begingroup$ @yyyyyyy: Actually, you can optimize the MD5 compression step, as you don't need to MD5 hash each 64 (actually, 128, the SHA-1 collision finds 2 block collisions I believe) block segment from scratch; the first $2k$ segments are repeated between $2^{64-k}$ different hashes... $\endgroup$
    – poncho
    Aug 13, 2019 at 11:59
  • $\begingroup$ @poncho Good point, I hadn't realized this optimization has such a big impact. So the actual cost is $2\cdot\sum_{i=1}^{64}2^i \approx 2^{66}$ MD5 compressions? $\endgroup$
    – yyyyyyy
    Aug 13, 2019 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.