Re: [Cfrg] Task looming over the CFRG

[Watson Ladd <[e-mail]>]

On Mon, May 5, 2014 at 2:34 PM, Blumenthal, Uri - 0668 - MITLL
<[e-mail]> wrote:
> IMHO, the logic/reason of matching security levels of the cryptographic
> algorithms employed in a protocol suite is fairly obvious and does not need
> an explicit justification. There might be a reason to have the
> key-protecting/key-wrapping algorithm a bit (no pun intended! :) stronger
> than the one that uses that key. I can't think of a reason to protect a key
> with a weaker algorithm than the key-using one.
>
> You observed that strength-matching was not done with RSA (considering the
> key sizes involved, and where those keys may need to be stored and
> processed, one possible reason for that mismatch pops up automatically :).
>
> More surprisingly, matching was not done with ECC either. We don't have an
> explanation for this design choice. Copying designs we don't understand (or
> do we?) does not sound like a good recipe.

I'm not sure if everyone knows this, but given 2^64 AES-128
encryptions of say 0, under different keys, and 2^64 steps, I can
recover one of the keys with probability 1/2 by a trivial application
of the birthday bound.

There are variants of this attack that work with significantly less
data: http://cr.yp.to/snuffle/bruteforce-20050425.pdf explains this
well. The headline result is 2^10 input keys, 2^86 calculation, and
probability close to 1 of finding one of the keys. I can think of many
numbers to describe this situation, but 2^128 isn't one of them.

For discrete log based systems this phenomenon doesn't happen: I
cannot find one discrete log among many in time much faster than to
find a particular discrete log. That's why ChaCha (which uses 256 bit
keys) plus Curve25519 makes sense: an attacker who wants to break such
a combination has to take a discrete log over a group of size roughly
128 or do at least 2^128 trial encryptions, even if given a ludicrous
number of keys to pick from.

Sincerely,
Watson Ladd