Finding the two collisions are not independent of each other so its more like finding the collision in whichever function is stronger. (I.e. finding a collision in md5 + sha1 is roughly as hard as finding a collision in just sha1)
In the past (long enough ago that using md5 almost made sense), I used a combination of md5 and sha1 to verify file integrity. Both checksums had to match or the file was rejected.
It seems obvious that that's at least as strong as using sha1 by itself. I've always assumed it was significantly stronger than sha1 by itself, but you're saying it isn't.
Creating an md5 collision isn't terribly difficult these days, but I've never heard of an md5 collision that's also a sha1 collision.
Can you cite a source with more information on this?
(I'm not doubting what you say, I'd just like more information.)
Although looking over this again, there is some caveats in that if both hash functions suffer from shortcut attacks, you might not be able to combine both shortcut attacks depending on the details of the shortcut attack.
Regardless, in the sha1+md5 case, even if you cant combine both shortcut attacks (big if. Not sure if that's true or not), the complexity of the sha1 collision is roughly the same as a birthday attack on md5, so i think you still end up with close to same big-oh as if you could combine both shortcut attacks.
