Subject: [CFRG] Re: RGLC on draft-irtf-cfrg-aead-limits
From: Felix Günther <[email-masked]>
To: [email-masked]
Date: Fri, 7 Mar 2025 16:45:07 +0100
List-Id: Crypto Forum Research Group <cfrg.irtf.org>

Hi John,

Thanks for taking the time to read and comment on the document.

I understand your concerns are primarily about the interpretation of 
single-key bounds and advantage bounds generally. We believe these can 
be mitigated by appropriate rewording in the draft.

Let me reply inline to the major points you raised.

On 2025-03-06 10:38 +0100, John Mattsson 
<john.mattsson=[email-masked]> wrote:
> I do NOT think the document should be published in the current state. I 
> think it is great to publish confidentiality advantages and integrity 
> advantages for algorithms. I do not agree at all with the drafts 
> suggestion on how to use the sigle-key advantages. I think these 
> sections should be removed. I think publishing the document in this 
> state do more harm than good.

We agree that single-key bounds are at odds with rekeying. This is in 
line with the core recommendation already stated in the draft: "When 
considering rekeying, the multi-user limits should be applied." We'll 
make sure this is emphasized more prominently.
(There's a confusing sentence on rekeying in the intro which we'll fix.)

> 
> Major:
> 
> - Any focus on single-key attacks for practical protcols makes little or 
> no sense. Single-key seldom occur in practice and the single-key 
> thinking should be phased out. Attackers will go for most 
> bang-for-the-buck and will do whatever gives most benefit for the least 
> amount of cost. Single--key is a theoretical simplification. Rekeying 
> based on single-key advantages turn the system into multi-key and may 
> easily lower security instead of increasing security.

Whether single keys are theoretical is a matter of threat model, and 
we'd hence keep the single-key limits for completeness. We'll add 
according cautionary wording, further emphasizing that multi-user bounds 
are to be used when rekeying.

> 
> - A gedankenexperiment using the suggested process suggest that the 
> ideal MAC should be rekeyed. This makes no sense.
> 
> - I don't agree with basing the limits on probabilities. I think attack 
> complexity and how small fraction of a bit an attacker can recover are 
> much better targets.For a PRP in counter mode an attacker cannot recover 
> more than ≈ σ^2 / 2^b bits of the plaintext.

We don't agree with plaintext recovery as a security target; the 
document specifically treats IND-CPA-style confidentiality. Arguably, 
this is a strong goal, but I don't think we should get into the 
territory of "what average fraction of bits is okay to leak"? (cf. also 
Dan's response on that)

> 
> - I also very much disagree with the suggested q limits in Table 2. I 
> think ANSSI's requirement to not encrypt more than 2^(b/2 - 5) blocks is 
> a well-thought-out and balanced requirement, effectively limiting the 
> amount of plaintext an attacker could recover to ≈ 1 / 2^10.47 ≈ 0.0007 
> bits. The limits in TLS 1.3, DTLS 1.3, and QUIC appear to be far 
> stricter than necessary. There is no universally agreed-upon threshold 
> for how much information an attacker must recover for it to constitute a 
> meaningful attack. However, protecting against the recovery of 1 / 
> 2^58.47 bits, a practically negligible fraction, seems overly cautious 
> and unlikely to be a realistic threat.
> 
> https://groups.google.com/a/list.nist.gov/g/ciphermodes-forum/c/tNlV34n3Vqw

We will emphasize that the numbers in Table 2 are exemplary, referring 
to TLS/DTLS/QUIC where similar (arguably conservative) choices have been 
made. The goal of this document is not to prescribe what level of 
security / adversary advantage is acceptable for a specific application; 
we'll also make this (more) explicit.

> 
> - I also very much disagree with the suggested v limits in Table 2. 
> These limits makes both the Bernstein bound and the expected number of 
> succesfull forgeries explode.
> 
> https://www.ietf.org/archive/id/draft-mattsson-cfrg-aes-gcm-sst-18.html

Not sure I'm following. All Table 2 says is that one can decrypt up to v 
= 2^46 messages to maintain a forgery probability of <= 2^-50.

> 
> I suggest that all suggestions on how to use the advantages is removed 
> from the documentand that the document is published as an overview of 
> confidentiality and integrity advantages.

We disagree on this, but will expand on emphasizing that specific 
usage/limits are examples, for certain (conservative) choices of 
advantages.

Regards,
Felix