[Cryptography] The paranoid approach to crypto-plumbing

Jerry Leichter leichter at lrw.com
Mon Sep 16 19:02:16 EDT 2013


On Sep 16, 2013, at 6:20 PM, Bill Frantz wrote:
>> Joux's paper "Multicollisions in iterated hash functions" http://www.iacr.org/archive/crypto2004/31520306/multicollisions.ps
>> 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.
> This kind of result is why us crypto plumbers should always consult real cryptographers. :-)
Yes, this is the kind of thing that makes crypto fun.

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 don't need to?)

It's not immediately clear to me what the right procedure for multiple authentication is.
                                                        -- Jerry



More information about the cryptography mailing list