13 ms·

This is only as strong as the stronger of A and C. If we had picked MD2 and MD4 to xor in the 90's we'd be no better off today. If there was a trivial way to g

This is only as strong as the stronger of A and C. If we had picked MD2 and MD4 to xor in the 90's we'd be no better off today. If there was a trivial way to get much stronger hashing with double the compute time we'd do it.

adzm 6y ago
Couldn't you concatenate the two hashes? Twice the size but you'd have to find a collision for both algorithms.
- bawolff 6y ago
  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)
  - afiori 6y ago
    then we just need to use ALL of them
  - _kst_ 6y ago
    Is that true? 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.)
    - bawolff 6y ago
      https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf https://www.iacr.org/archive/crypto2004/31520306/multicollis... 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. Disclaimer: IANAC.
deleted 6y ago
[deleted]
labawi 6y ago
If you xor the hashes together, it may be as weak as the weaker of the two functions, though it probably depends on their structure. Getting much stronger hashing with double compute time is easy. Double the number of round - most alorithms have about 30-60% security margins. It would probably avoid any breaks of the hash (so 80 bits for SHA1), though it can't be enough if the hash is simply too small (64 bit security for MD5/4/2).

adzm 6y ago

Couldn't you concatenate the two hashes? Twice the size but you'd have to find a collision for both algorithms.

bawolff 6y ago
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)
- afiori 6y ago
  then we just need to use ALL of them
- _kst_ 6y ago
  Is that true? 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.)
  - bawolff 6y ago
    https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf https://www.iacr.org/archive/crypto2004/31520306/multicollis... 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. Disclaimer: IANAC.

deleted 6y ago

[deleted]

labawi 6y ago

If you xor the hashes together, it may be as weak as the weaker of the two functions, though it probably depends on their structure. Getting much stronger hashing with double compute time is easy. Double the number of round - most alorithms have about 30-60% security margins. It would probably avoid any breaks of the hash (so 80 bits for SHA1), though it can't be enough if the hash is simply too small (64 bit security for MD5/4/2).