[Cryptography] The paranoid approach to crypto-plumbing

Mon Sep 16 19:52:04 EDT 2013

```On Mon, Sep 16, 2013 at 4:02 PM, Jerry Leichter <leichter at lrw.com> wrote:
> 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
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.

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.
Sincerely,
>
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography

--
"Those who would give up Essential Liberty to purchase a little Temporary
Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20130916/62056956/attachment.html>
```