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

[Martin Thomson <[e-mail]>]

On Sat, Mar 8, 2025, at 06:35, Mihir Bellare wrote:
> "Rekeying uses a lightweight transform to produce new keys." Not sure 
> what is meant; is a function being applied to an existing key to derive 
> subkeys? If so, I am not sure it is quite true that "Rekeying 
> effectively resets progress toward single-key limits". Analyses of 
> rekeying that I know (eg. [AB00] 
> <https://cseweb.ucsd.edu/~mihir/papers/rekey.pdf>) do show some 
> improvement but not to the extent of resetting to single-key limits, 
> and it also depends on how the rekeying is done. But I may be missing 
> other analyses or what is meant by rekeying or what is meant by the 
> phrase in quotes.

I think that Felix already replied to others about how we had some text about rekeying that was flat-out wrong, or at least misleading.

> The attacker success probability also depends on its running time, 
> denoted o in the table, but I am not sure if, or how, this is getting 
> taken into account in the bounds. Yet it does (or should) affect them. 
> For example, 5.1.1 says 
>
> CA <= ((s + q + 1)^2) / 2^129
>
> So if s=q=1 this says CA <= 9/2^{129} but this isn't true for any 
> realistic running time for the attacker. For example if o = 2^{64} 
> (which may even be over optimistic) then even with s=q=1 we have CA > 
> 2^{64}/2^k which is 1/2^{64} if k=128. So running time sets some lower 
> limits on CA regardless of s,q, and this will also affect the bound on 
> q+s which would be a function of o in addition to p. Another dimension 
> is that currently Section 5 gives the same bounds for AEAD_AES_128_GCM 
> and AEAD_AES_256_GCM but when attacker running time is considered we 
> would expect to see differences due to the different values of k, and 
> the bounds should be better for k=256. Perhaps the draft is making some 
> assumptions or approximations here that I am missing?

The draft currently says that offline work, o, is only a factor for our multi-user analysis, which seems wrong for exactly the reasons you state.  The MU analysis sets out its assumptions about o, such as assuming that o <= q + v in the GCM analysis (that is, the attacker is assumed to be unable to out spend all other users of the cipher); ChaCha20Poly1305 would require absurd values for o (or extremely low attack probability) to clear its 2^247.

Of course, I can see why the GCM result is questionable if you consider that the point of the exercise is to place an upper bound on both q and p.  If you look at the tables, you might choose a value of p + q of ~2^37, which is clearly a long way short of a difficult task.

As for the single user analysis, it seems like we should integrate o into estimates, if only to pick a value that we think sets a reasonable bound on the advantage.  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, which is easy to look past when it isn't the main contributor to advantage.  (It's possible I haven't correctly restored state regarding the necessary papers here; the translation of notation is thorny, but I think that's right.)

With that in mind, we can make some pretty firm general statements about the limits implied by relying on a PRP and the amount of offline work that might be deployed.  That is, if you set a target advantage of 2^-50, then you are inherently assuming that o is significantly less than 2^n*2^-50 or that term would be what determines the advantage that an attacker gains.  Would that sort of thing help?