Re: [Cfrg] matching AES security

[Dan Brown <[e-mail]>]

I mostly agree with the discussions on this thread, but want to add one more 
theoretical (*) point.

(*) This is not something to lose sleep over, rather something for insomniacs 
to ponder at night.

It seems to me that even in the single-key setting, a 256-bit ECC key fares 
better than a 128-bit AES key, because of the tradeoff between computation and 
success rate.

To make it concrete, consider a TLS session protected with a one-use ECDHE key 
and a one-use AES key.

The following simplistic back-of-the-envelope calculation shows that a typical 
adversary would far prefer to attack the AES key.

Some variables:
- v = value of session plaintext to adversary
- s = success rate of adversary
- g = sv = expected gain of adversary
- c = computational cost of adversary
- r = g/c = sv/c = overall return on investment for adversary [left as an 
exercise]
- j = dg/dc = incremental return on investment for adversary computation

Consider a form of exhaustive search algorithm: pick a random 128-bit key AES 
against a target session ciphertext, decrypting it to confirm the guessed key. 
This assumes that the plaintext has an easily checkable form of redundancy of 
at least 128 bits, enabling the adversary to confirm the correctness of a 
guessed key.  Repeat ~c times.  This algorithm is such that

c/s ~ 2^128

So, s ~ c / 2^128.  I'm using ~ for proportional: so multiply the RHS by the 
cost of AES decryption plus plaintext redundancy verification.

Now, ignoring memory costs, Shank's baby-step-giant-step algorithm against a 
256-bit ECC is such that

c^2 / s ~ 2^256

against with other constants of proportion to be multiplied onto the RHS.  I'm 
guessing that memory-efficient algorithms like Pollard rho have the similar 
tradeoff, but please correct me if I'm wrong.

Solving for s gives s ~ c^2 / 2^256.

Plugging this back into the incremental ROI per computation gives

j_aes128 ~ v / 2^128
j_ecc256 ~ 2vc / 2^256

So, when c ~ 2^128 these are about the same, but for smaller c values, 
j_ecc256 is smaller, and thus the adversary gets more return from attacking 
the AES128 key.

In other words, the adversary's initial computation are most effectively spent 
on the AES key, because if the adversary gets lucky.  That is, *IF* the 
adversary has the computational power such that it pays off to try exhaustive 
search on AES128, then this pays off much more than trying to solve the DLP on 
ECC256 using a generic algorithm.  Of course, that's a big if.

Note that I used a heuristic of differentiation to get the j values.  This is 
inaccurate, especially for j_aes128 as c approaches 2^128.  More precisely, a 
better exhaustive search algorithm than above does try random keys, but rather 
loops through keys, never repeating, so the incremental return on investment 
actually improves per guessed key.  This means that even for large c ~2^128, 
it may still be better to run the algorithm against AES128 instead of DLP 
ECC256.

Note that in the setting above, the DH and AES keys are used once only for the 
same purpose.  In other situations, such as key transport or DH key re-use, 
the value of v would differ for the different keys, and thus may significantly 
alter the adversary's optimal strategy.

Note that the 256-bit ECC DLP algorithm cost can also be written as c/ sqrt(s) 
~ 2^128, hence the label 128-bit security for 256-bit ECC.

Note that I ignored the option of using the MAC tag to confirm AES128 key 
guesses.  Since the MAC would use a different key, I deferred its use to 
further discussion.