[mistercow]

Ah, so in fact the naive concatenating solution I gave, in addition to being just as easy because the attacker only has to break half of it, is actually even easier because the attacker has two targets to collide with.

What about non-concatenative methods? For example, could you do something like "shift and xor". For example, say you have a 4-byte hash function, so that:

   hash(salt + input)             :  0x3AF9
   hash(salt + fixedSalt + input) :  0x8034

then you shift one by a byte and xor like so

       3AF90
   xor 08034
     = 32FA4

And then you could iterate that to extend to as many bytes as you want? And then maybe you'd want to xor the first and last byte together so that nothing from the first hash remains - although now I'm thinking intuitively which generally seems to be a bad idea with crytpography.

[sdevlin]

> Ah, so in fact the naive concatenating solution I gave, in addition to being just as easy because the attacker only has to break half of it, is actually even easier because the attacker has two targets to collide with.

I wouldn't say it's easier. Remember that we need to find a single message that generates a collision under both hash functions. So our strategy is to generate a massive number of collisions for the shorter function and hope that there's one pair of messages in there that collide under the longer function.

> What about non-concatenative methods?

I think this will again boil down to finding a single message that generates a collision under both hash functions. It won't matter too much whether you XOR the hashes or concatenate them.

[mistercow]

Hmm. It still seems to me that the simple concatenative method could still be broken at least slightly more quickly, since each function can be collision tested separately, but my brain is vaguely gesturing at comprehension about why xoring is still weak.

I feel like we should be teaching the principles of crypto to young children so that we end up with some humans that can grok it as easily as the rest of us do algebra. But there are a great many things I would want young children to be taught if I were made the Benevolent Dictator of All School Boards.