4 ms·

> But as far as I know, any two different hashing schemes applied sequentially has never been broken. Suppose you used SHA256(MD5(x)) as your sequential hashin

> But as far as I know, any two different hashing schemes applied sequentially has never been broken. Suppose you used SHA256(MD5(x)) as your sequential hashing function. If I can find two messages m1, and m2 that have the same MD5 digest, the outer SHA256 will also collide. MD5 is sufficiently broken that finding such messages is easy: https://github.com/thereal1024/python-md5-collision https://github.com/thereal1024/python-md5-collision Two different hashing schemes applied in parallel is better. However even there many uses of hashing functions require all the bits in the output digest to be equally unpredictable.

tptacek 6y ago
If one of your hashes is iterated, you also have the multicollision problem: once you find a collision in your weak, iterated hash, you can quickly produce more collisions, so that the strength of your construction just devolves to that of the stronger hash.
- delhanty 6y ago
  For clarity, which part of petertodd's comment are you replying to? (I'm learning a little cryptography from this thread, so the above is a straight question.)
  - bawolff 6y ago
    I believe he is responding to "Two different hashing schemes applied in parallel is better." My understanding is if you have a collision in the stronger function, you have an infinite family of collisions in the stronger function due to the length extension attack, from there you should be able to base the collision for the weaker function on one of the stronger function's (length extended) collisions.
    - delhanty 6y ago
      Thank you for that reply - particularly the informative explanation. I was sort of assuming it must be a reference to the parallel schemes because with SHA256(MD5(x)), once you had an MD5 collision you would be done.
- deleted 6y ago
  [deleted]
nayuki 6y ago
Two hashing schemes in parallel has problems too. Suppose your parallel hash is SHA3+Ident, where Ident is either the first 100 bytes of the message or the message padded with NUL up to 100 bytes. Because Ident has no preimage resistance, the combo SHA3+Ident has very poor preimage resistance too. This thread has relevant info: https://crypto.stackexchange.com/questions/270/guarding-against-cryptanalytic-breakthroughs-combining-multiple-hash-functions https://crypto.stackexchange.com/questions/270/guarding-agai...
- deleted 6y ago
  [deleted]
- mehrdadn 6y ago
  I still don't understand what you're claiming is wrong with XOR. As I understand it, the XOR of two secure hashes should be at least as strong as each one. Of course you can find ways to deliberately come up with a broken scheme if you really want to do something spectacularly dumb (like XORing a variation of the same algorithm with itself...), at which point the problem isn't really XOR, but assuming you're being reasonable and showing some sense in the process, the likelihood of someone somehow finding an exploitable correlation between them without breaking either one should be astronomically small to not even warrant a second thought.
  - rawoke083600 6y ago
    Just as a mental exercise (im no expert) how about. GoodHash=HF(input) + HF(reversed-input) Your final hash value will still be twice as bjg yes, but reversing the input should yield a different result ? This is of course for non-crypto usage.
- petertodd 6y ago
  By "in parallel" I don't mean XOR. I mean concatenation. So in my example sha256+md5 would concatenate sha256's 256 bit digest, and md5's 128 bit digest, to form a 384 bit digest. The intuitive explanation for why XOR instead of concatenation doesn't work, is it lets the output of the broken hash function influence the output of the remaining good hash function. That is obviously cause for concern!
sjwright 6y ago
> Suppose you used SHA256(MD5(x)) as your sequential hashing function. SHA256(concat(MD5(x), x)) would be significantly more effective at the possible expense of performance. Of course I’m sure that if you’re willing to make a performance trade-off there’s going to be a better single hashing algorithm out there.

tptacek 6y ago

If one of your hashes is iterated, you also have the multicollision problem: once you find a collision in your weak, iterated hash, you can quickly produce more collisions, so that the strength of your construction just devolves to that of the stronger hash.

delhanty 6y ago
For clarity, which part of petertodd's comment are you replying to? (I'm learning a little cryptography from this thread, so the above is a straight question.)
- bawolff 6y ago
  I believe he is responding to "Two different hashing schemes applied in parallel is better." My understanding is if you have a collision in the stronger function, you have an infinite family of collisions in the stronger function due to the length extension attack, from there you should be able to base the collision for the weaker function on one of the stronger function's (length extended) collisions.
  - delhanty 6y ago
    Thank you for that reply - particularly the informative explanation. I was sort of assuming it must be a reference to the parallel schemes because with SHA256(MD5(x)), once you had an MD5 collision you would be done.
deleted 6y ago
[deleted]

nayuki 6y ago

Two hashing schemes in parallel has problems too. Suppose your parallel hash is SHA3+Ident, where Ident is either the first 100 bytes of the message or the message padded with NUL up to 100 bytes. Because Ident has no preimage resistance, the combo SHA3+Ident has very poor preimage resistance too. This thread has relevant info: https://crypto.stackexchange.com/questions/270/guarding-against-cryptanalytic-breakthroughs-combining-multiple-hash-functions https://crypto.stackexchange.com/questions/270/guarding-agai...

deleted 6y ago
[deleted]
mehrdadn 6y ago
I still don't understand what you're claiming is wrong with XOR. As I understand it, the XOR of two secure hashes should be at least as strong as each one. Of course you can find ways to deliberately come up with a broken scheme if you really want to do something spectacularly dumb (like XORing a variation of the same algorithm with itself...), at which point the problem isn't really XOR, but assuming you're being reasonable and showing some sense in the process, the likelihood of someone somehow finding an exploitable correlation between them without breaking either one should be astronomically small to not even warrant a second thought.
- rawoke083600 6y ago
  Just as a mental exercise (im no expert) how about. GoodHash=HF(input) + HF(reversed-input) Your final hash value will still be twice as bjg yes, but reversing the input should yield a different result ? This is of course for non-crypto usage.
petertodd 6y ago
By "in parallel" I don't mean XOR. I mean concatenation. So in my example sha256+md5 would concatenate sha256's 256 bit digest, and md5's 128 bit digest, to form a 384 bit digest. The intuitive explanation for why XOR instead of concatenation doesn't work, is it lets the output of the broken hash function influence the output of the remaining good hash function. That is obviously cause for concern!

sjwright 6y ago

> Suppose you used SHA256(MD5(x)) as your sequential hashing function. SHA256(concat(MD5(x), x)) would be significantly more effective at the possible expense of performance. Of course I’m sure that if you’re willing to make a performance trade-off there’s going to be a better single hashing algorithm out there.