Re: [Cfrg] matching AES security

["D. J. Bernstein" <[e-mail]>]

Benjamin Black writes:
> The goal is matching security levels of the suite components as designed

I understand that you have this goal. What I'm saying is that---never
mind the disputes about whether this goal is appropriate---pairing
AES-128 with 256-bit ECC is failing to achieve this goal. It isn't even
close. Compared to the quantitative security level of 256-bit ECC, there
are _huge_ and undisputed weaknesses in AES-128. Similar comments apply
to AES-256 and 512-bit ECC.

> AES is not the only symmetric cipher in use today and we can expect
> new ciphers to supersede it during the service life of the new curves
> under discussion.

Replacing AES-128 with another 128-bit cipher, or replacing AES-256 with
another 256-bit cipher, has no effect on my point here.

Blumenthal, Uri - 0558 - MITLL writes:
> "Multiple-key attacks" reference please?

The central idea comes from Hellman's classic "Cryptanalytic time-memory
trade-off". After Hellman there were many followup papers on improved
algorithms that exploit multiple inputs ("time-memory-data tradeoffs"),
reduce precomputation, reduce communication cost, reduce other
overheads, etc. Public multiple-target attacks tend to use Oechslin's
"rainbow tables", but attackers carrying out mass exploitation obtain
lower cost from Rivest's "distinguished points".

The word "tradeoff" turned out to be misleading in this context: a
properly optimized multiple-target parallel machine using these ideas is
fundamentally better for the attacker than any single-target machine can
possibly be. http://cr.yp.to/snuffle/bruteforce-20050425.pdf contains a
detailed cost evaluation and various references. 

Peter Gutmann writes:
> a custom device with 2^42 bytes of memory and 2^32 keysearch engines
> that required 2^36 inputs. That's 100 terabytes of RAM, 4 billion
> keysearch engines, and around 70 billion sets of input data.
> I'm not overly concerned.

http://blog.cr.yp.to/20140602-saber.html shows how we put together a
cluster from off-the-shelf components with around 1TB RAM and more than
100000 ALUs, each running at nearly 1GHz, for a total of just 50000 EUR.
You're talking about 100x more RAM and 40000x more ALUs, raising the
cost to about 2 billion EUR, but this is well within the supercomputing
budget of some existing adversaries. At that scale it's also no problem
to build application-specific chips. The attack parallelizes without
trouble and has very low communication costs.

As for "sets of input data": If you check what the paper actually says,
you'll see that this example is targeting 1024 keys. The "inputs" are
generated internally. Even for such a small number of keys, the
effective security level of AES-128 drops from 2^128 to just 2^118.

More importantly, RFC 7258 says

   The IETF community has expressed strong agreement that PM [pervasive
   monitoring] is an attack that needs to be mitigated where possible,
   via the design of protocols that make PM significantly more expensive
   or infeasible.
   
Surely you're not arguing that 70 billion encryptions would be
_infeasible_ (or even hard!) for this type of attacker to collect---and
the security consequences seem to be something where IETF needs advice
from IRTF, specifically CFRG.

ECC doesn't have the same weakness. One way to think about this is that
"random self-reduction" already turns one ECC target into many targets
(see http://cr.yp.to/talks/2007.09.03-2/slides-djb-20070903-2-a4.pdf)
producing square-root attacks; this is the reason that ECC keys are
chosen to be larger than 128 bits in the first place. For the same
reason, having more ECC targets doesn't improve the attacker's success
chance---the attacker already had as many targets as desired---while
having more AES targets makes an important difference in security level.

Paul Lambert writes:
> So, would this attack be mitigated by a change in algorithm mode?

Sufficient input randomization would stop the basic AES attack---but it
would also make the cryptography unnecessarily complex, unnecessarily
hard to test, and unnecessarily error-prone, not to mention issues of
randomness as a covert channel (see http://eprint.iacr.org/2014/438 and
http://blog.cr.yp.to/20140205-entropy.html) performance problems, etc.
Switching to a larger cipher key is almost certainly cheaper, and is
clearly much more robust system engineering.

More to the point, we _already have_ standard, widely deployed, provably
secure cipher modes that provide predictable input blocks to ciphers
(such as input block 0 in counter mode), and it's not as if these modes
are going away. Anyone proposing AES-128 as part of a general-purpose
"2^128 security" cipher suite is ignoring the undisputed fact that
AES-128 used in these standard modes will leak some user keys to an
attack costing vastly less than 2^128.

Dan Brown writes:
> 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.

Correct. One reference for this success-rate comparison is

   http://cr.yp.to/talks/2005.09.19/slides.pdf

particularly the last slide. This is also what I was alluding to when I
mentioned "lucky attacks" in my CFRG slides.

---Dan