<div dir="ltr"><br>On Mon, Sep 16, 2013 at 4:02 PM, Jerry Leichter <<a href="mailto:leichter@lrw.com">leichter@lrw.com</a>> wrote:<br>> On Sep 16, 2013, at 6:20 PM, Bill Frantz wrote:<br>>>> Joux's paper "Multicollisions in iterated hash functions" <a href="http://www.iacr.org/archive/crypto2004/31520306/multicollisions.ps">http://www.iacr.org/archive/crypto2004/31520306/multicollisions.ps</a><br>
>>> shows that "finding ... r-tuples of messages that all hash to the same value is not much harder than finding ... pairs of messages".  This has some surprising implications.  In particular, Joux uses it to show that, if F(X) and G(X) are cryptographic hash functions, then H(X) = F(X) || G(X) (|| is concatenation) is about as hard as the harder of F and G - but no harder.<br>
>> This kind of result is why us crypto plumbers should always consult real cryptographers. :-)<br>> Yes, this is the kind of thing that makes crypto fun.<br>><br>> The feeling these days among those who do such work is that unless you're going to use a specialized combined encryption and authentication mode, you might as well use counter mode (with, of course, required authentication).  For the encryption part, counter mode with multiple ciphers and independent keys has the nice property that it's trivially as strong as the strongest of the constituents.  (Proof:  If all the ciphers except one are cracked, the attacker is left with a known-plaintext attack against the remaining one.  The need for independent keys is clear since if I use two copies of the same cipher with the same key, I end up sending plaintext!  You'd need some strong independence statements about the ciphers in the set if you want to reuse keys.  Deriving them from a common key with a one-way hash function is probably safe in practice, though you'd now need some strong statements about the hash function to get any theoretical result.  Why rely on such things when you<br>
>  don't need to?)<br>><br>> It's not immediately clear to me what the right procedure for multiple authentication is.<br>>                                                         -- Jerry<div>The right procedure would be to use a universal hash function together with counter mode encryption. This has provable security relatable to the difficulty of finding linear approximations to the encryption function.</div>
<div><br></div><div>But I personally don't think this is much use. We have ciphers that have stood up to lots of analysis. The real problems have been in modes of operation, key negotiation, and deployment.</div><div>
Sincerely,<br>Watson Ladd<br>><br>> _______________________________________________<br>> The cryptography mailing list<br>> <a href="mailto:cryptography@metzdowd.com">cryptography@metzdowd.com</a><br>> <a href="http://www.metzdowd.com/mailman/listinfo/cryptography">http://www.metzdowd.com/mailman/listinfo/cryptography</a><br>
<br><br><br>-- <br>"Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither  Liberty nor Safety."<br>-- Benjamin Franklin<br></div></div>