Subject: [CFRG] Review of draft-irtf-cfrg-aead-limits-01

From: John Mattsson <[email-masked]>
Date: Tue, 17 Nov 2020 23:32:44 +0000

Hi,

Great that you are taking the time to summarize all this information. Very useful.

Comments:

-- "plaintext, and optional associated data"
 
P and A are both optional in RFC 5116.

-- It would be good if the document states that it only focuses on "single forgery attacks"

I think some readers might believe that a second forgery is as hard as the first, which it is not. It it typically much easier. It might also vary drastically between algorithms as calculated in [1].

-- I think the document should briefly explain the assumptions about the adversary. For both CA and IA, one assumption worth explaining is that the adversary has access to an encryption oracle and can freely encrypt chosen-plaintexts.

-- The table defines l as "length of each message" while a paragraph further down writes "maximum message size (l)".

-- ”passive attacker”

For a reader that does now the IND-CPA game by heart it might be good to point out that the “passive” attacker does not just eavesdrop but also choses all the encrypted plaintexts.

-- “Integrity limit (IL): The number ciphertexts an application can decrypt, either successfully or not”

That IL also count successful decryptions seems to contradict other parts of the document that links IL to v which by definition only counts failed attempts.

-- “This implies the following usage limit: q + s <= p^(1/2) * 2^(129/2) – 1”
   “This implies the following limit: v <= (p * 2^127) / (l + 1)”

This does not follow with the current definition of p (p = CA or p = IA). To make the inequalities hold I think you need to define p as:
 
"Upper bound on adversary attack success probability"

just like the parameter epsilon in [AEBounds].

-- I think the document should briefly explain the assumptions about the algorithms. In [GCMProofs] it is e.g. assumed that AES is a PRP. Future cryptanalysis that does not make these ideal assumptions could make the limits worse.

-- The document should make it clear that formulas for CA and IA (at least for GCM) are upper bounds. Future analysis could make the limits better. That they are just bounds also make any direct comparision between algorithms tricky as some bounds might be tigher than others.

- The draft briefly mention that small limits lead to denial-of-service attacks. The DTLS 1.3 draft does that.

-- The draft seems to make the assumption that l is fixed like n, k, r. I don't think this needs to be the case. My understanding is that for the GCM limits, l_max_allowed can be replaced by l_max_seen being the largest length processed. The encryption or decryption function would then terminate when CA or IA can not be verified to be under the chosen bound. This would make a big difference for applications typically processing much smaller messages than for example 2^14. For the CCM integrity bounds, the formula would probably have to involve (2 * l_max_allowed * q + 2 * l_max_seen_* v). The DoS problem would still be tied to l_max_allowed.

Cheers,
John

[1]  https://csrc.nist.gov/CSRC/media/Projects/Block-Cipher-Techniques/documents/BCM/Comments/CWC-GCM/multi-forge-01.pdf

---

From: John Mattsson <[email-masked]>
Date: Mon, 23 Nov 2020 14:00:52 +0000

Hi,

Some more comments on the document:

- "However, in practice, there are often many users with
independent keys.  The "multi-user" security setting hence considers
an attacker's advantage in breaking security of any of these many
keys, further assuming the attacker may have done some offline work
to help break security."

I think the term "multi-user" is a quite misleading term. It was coined by Belallare, Boldyreva, Micali trying to provide a theoretical framework against Håstad's attack on public key RSA and even then they used quotes ("") as a user might have several public keys. When applied to symmetric keys in security protocols with frequent rekeying it becomes a bit misleading as the attack scenario is really for multi-key and each user definitly has several keys. In strongly think the term "multi-user" should be replaced with "multi-key", but I know that "multi-user" is what is used i several academic papers... At a minimum I think you should define "multi-user" in terms of multiple keys and write that the keys can belong to one, two, or many users.

- "single-user". I think this terminology should definitly go away. Luykx et al. use "single-key". When applied to e.g. TLS there is already 2 users.

- "Number of attacker forgery attempts (failed AEAD decryption invocations)"

Note that Iwata et al. defines q' as the number of decryption queries, while your document defines it as number of failed decryption queries. In theory that could mean that the inequality 

IA <= 2 * (v * (l + 1)) / 2^128

does not hold anymore. In practice it holds anyway. I think you should keep the definition of v, but you should alert the reader that you have modified this, and maybe give some justification.

- "LS aims to keep CA below 2^-60 and IA below 2^-57"

This indicates that you might want two different variables p_ca a p_ia for the two different bounds.

- "AES-GCM without nonce randomization is also discussed in [GCM-MU2], though this section does not include those results as they do not apply to protocols such as TLS 1.3 [RFC8446]." 

The negation of "AES-GCM without nonce randomization" is not well defined. It would be good to now if the results apply only for the constructions where the salt is secret (TLS 1.3, DTLS 1.3, QUIC, OSCORE), or only to constructions where the salt has the same length as the nonce, or if it apply to all constructions with a random component. It would be good if the document is also useful for protocols like ESP, SRTP, CMS, JOSE, COSE, etc...

Cheers,
John

-----Original Message-----
From: John Mattsson <[email-masked]>
Date: Wednesday, 18 November 2020 at 00:32
To: CFRG <[email-masked]>
Subject: Review of draft-irtf-cfrg-aead-limits-01

Hi,

Comments:

-- ”passive attacker”

Cheers,
John

---

From: Felix Günther <[email-masked]>
Date: Fri, 27 Nov 2020 10:02:29 +0100

Hi John,

Thanks for your further helpful comments. For reference, we're tracking
them at https://github.com/cfrg/draft-irtf-cfrg-aead-limits/issues/28.
Let me respond to a few points here already.

> -- It would be good if the document states that it only focuses on "single forgery attacks"

The document actualy considers multiple forgeries (parameter v accounts
for their number) and was in parts motivated by work on the robustness
of protocols like DTLS and QUIC to those. We'll make this clearer.

> -- The document should make it clear that formulas for CA and IA (at least for GCM) are upper bounds. Future analysis could make the limits better. That they are just bounds also make any direct co…

There's indeed a subtle interplay between bounds and models/assumptions.
E.g., for some bounds are indeed tight/cannot be improved _in the given
model_, and then things depend on which assumptions one is willing to
make.  We will expand on this, although there are obviously limits to
what can be reasonably discussed in this document.

> - The draft briefly mention that small limits lead to denial-of-service attacks. The DTLS 1.3 draft does that.

Yes, for small limits DoS attacks have to be weighed. For DLTS 1.3 I
assume you refer to Appendix B.3, whose analysis supports the view that
small limits as for AES-CCM make such AE schemes unsuitable for general
use when DoS attacks are a concern.

Cheers,
Felix