[CFRG] Re: RGLC on draft-irtf-cfrg-aead-limits

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

Martin Thomson writes:
> In most of the papers we cite, offline work is not considered
> directly, so presumably it is inherent in the baseline PRP (or PRF)
> advantage

Yes, that's where computation contributes to attack success in these
theorems. A billion dollars today is far below some attacker budgets
(e.g., NSA's yearly budget was $10.8 billion in 2013) and buys more than
2^94 AES-128 computations, so the single-target success probability is
above 2^-34, and the multi-target success probability is basically 100%
in the common situation that many keys encrypt a known plaintext.

I spotted a comment indicating that the draft looks only at particular
protocols with lower multi-target success probability. I'd think that
most readers looking at the tables will miss this restriction and won't
realize that AES-128 is already breakable today for other protocols.

Anyway, the draft says the tables are supposed to limit the attacker's
success probability to 2^-50; but a billion-dollar attack will break an
AES-128 key with probability far above 2^-50 even if the protocol puts
severe limits on q and v and is never used for another key. So there's
definitely a major problem with the draft's AES-128 table entries.

Another reason not to ignore PRF terms is that there's a fast PRF attack
against both AES-128 and AES-256 with probability about (q+v)^2/2^129.
This isn't an issue for ChaCha20, and maybe all of the cited AES bounds
are in the part of the literature that removes the issue by starting
with PRP instead of PRF, but this is something to check carefully;
otherwise there can be real attacks, scaling up https://sweet32.info.
Note that https://nvlpubs.nist.gov/nistpubs/ir/2024/NIST.IR.8537.pdf
says "Paul Crowley emphasized that Google is moving petabytes of data
with a single key".

Yet another proof gap comes from the fact that even faster attacks exist
against PRP and PRF, at least for some cost metrics; see generally
https://cr.yp.to/papers.html#nonuniform. These aren't real-world attacks
against PRP and PRF, but they _can_ turn into real-world attacks against
protocols that have non-constructive proofs. Formalizing constructivity
is tricky, so you can't expect to detect it from the theorem statement.
My own proofs in this area are constructive, but some other proofs such
as https://eprint.iacr.org/archive/2006/043/20060206:214630 aren't, as
https://eprint.iacr.org/2012/074 pointed out.

There are quite a few proofs cited in this draft, and I wonder how
carefully they've been reviewed, not just for constructivity but for
whether the stated theorems have in fact been proven. We've just seen
devastating breaks of XCB version 2, despite years of standardization
and two refereed provable-security papers; should we really be assuming
that theorems are correct? See https://cr.yp.to/proofs/errors.html for
XCB links and further examples of errors. For the question of how often
proofs are correct, see https://cr.yp.to/papers.html#eraa.

---D. J. Bernstein