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

[Mihir Bellare <[e-mail]>]

>
> 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?
>

Fixing a particular target advantage, and hence a value of o, feels a bit
arbitrary and hard for non-cryptographers to understand intuitively. What
if instead one fixes a target work factor w, defined by 2^w =
adversary-effort / advantage = o/e ? Intuitively this can be interpreted as
the time needed to break the system totally, meaning get advantage about
e=1, which may be more intuitive. An example is w=80 representing 2^{80}
time, although Dan points out that it could be as high as w=94. For
AES-GCM-k, a bound that explicitly reflects time (o) can be extracted from
p.5 of [HTT18 <https://eprint.iacr.org/2018/993.pdf>]. For u=1 user and in
the notation of the draft document it says roughly e \leq o * 2^{-k} + s^2
* 2^{-128}. To ensure the w work factor, the first term just implies w < k,
which we can assume, and from the second we need s/(s^2 * 2^{-128}) \geq
2^w which gives the limit s \leq 2^{128-w}. So for example for w=80 the
limit is s \leq 2^{128-80} = 2^{48}.

Now in this case the advantage is 2^{96} * 2^{-128} = 2^{-32} which is
above your bar of 2^{-50} so would not be admissible in that view but I
think what this view neglects is that the attacker has to invest 2^{48}
time to mount this attack, so the work factor is 2^{48}/2^{-32} = 2^{80} as
desired, meaning it stays in the ballpark of intuitively needing 2^{80}
time. So just another approach, not sure exactly how valid or realistic it
is; I'm sure it has its issues and limitations!

Orthogonally I have a philosophical question. The document gives multi-user
(mu) bounds and Dan has given convincing arguments in their favor, and I
agree with both. My question is, what incentive do individual users have to
use mu limits rather than single-user ones (su) ones? If it is up to a user
(owner of one key) to pick their own limits, they may (selfishly) argue
that they only care that the probability of cracking their key is low
enough and it does not matter if, across all users, there is a break with
probability nearly 1, so they will use su limits. As a rough analogy, if we
consider the set of all people who will drive more than 20 miles tomorrow,
it is nearly certain that, across the planet, one of them will die in a
traffic accident, but an individual driver does not let this preclude them
from driving 20 miles because they are pretty sure that this one person
will not be them. To be clear, I am not at all arguing against mu being the
right metric, and indeed it is and should be in the document; I'm just
curious as to whether mu limits will actually have any impact on choices of
limits made in the wild.

Regards

Mihir