Watson Ladd <watsonbl...@gmail.com> wrote:
> Brian Smith <br...@briansmith.org> wrote:
> > So, if [2] is correct, then we can take Watson's 2^36 and multiply it by
> > 2^17 to get 2^53 bytes as the limit? It seems so, since [2] claims that
> > they've improved the bounds by 2^17. Note that 3 out of 4 of the authors
> of
> > [2] are the same authors as [1], which is the paper that defined the
> formula
> > that the 2^36 number was calculated from.
>
> You need to actually read the papers and understand which formulas are
> modified. If you did you would see the improvement is in AES-GCM with
> funny nonce sizes, not the confidentiality issue.
>
Great. Thank you for pointing out my mistake. First, I'll correct my
mistake in understanding [2]. Then, I'll verify your derivation how we can
get the "2^36 bytes" figure. Lastly, I'll ask whether the initial premise
under which we derived that number is meaningful. In particular, many
people seem to be using a limit of 2^-18 for the attackers
distinguishability advantage to allow (over) 2^48 bytes to be sent, but the
2^36 limit we derived comes from using the number 2^-60 instead. But, is
2^-60 really the right number to use? It seems like we can likely tolerate
a much higher probability of distinguishability. However, it isn't clear
what probability of distinguishability is sufficient. In other words, there
is a tension between the strictness in demanding proof of IND-* security
vs. the simplicity of the protocol (rekeying or now) for AES-GCM. I believe
it is worth asking more cryptographers for help in determining this limit.
First, my mistake in understanding [2]: The improvements to [2] are for
Theorem 1 in [1], which is about AES-GCM in general, for all nonce lengths.
However, [1] also defined Corollary 3 that tightens the bound for the case
where the nonce length is 96 bits, which completely avoids the term with
factor 2^22. So, the 2^17 improvement in [2] for Theorem 1 is not relevant
because we're using Corollary 3, which is already even tighter. Sorry for
wasting people's time with that.
Second, let's go back to how we got 2^36. We used Corollary 3 from [1],
which has this formula:
0.5(σ + q + 1)^2 / 2^n
We rename σ to s:
0.5(s + q + 1)^2 / 2^n
substitute n == 128:
0.5(s + q + 1)^2 / 2^128
and simplify:
(s + q + 1)^2 / 2^127
we get the formula in Watson's email [3]. In that email, Watson then
claimed that we want to keep this quantity under 2^-60:
(s + q + 1)^2 / 2^127 < 2^-60.
Simplified:
(s + q + 1)^2 < 2^67.
Further simplified:
s + q + 1 < 2^33.5.
So, Watson's point in [3], as I understand it, is that even if we ignore q,
s must be less than 2^32. 2^32 blocks * 2^4 bytes per block = 2^36 bytes in
order to have a proof of IND-* security for AES-GCM, So we'd need to send
2^36 or fewer bytes to have proven IND-* security.
Lastly, let's reconsider Watson's claim in [3] that 1/2^60 is the correct
bound. In [0], the authors wrote: "To provide a concrete example, these
results show that, if AES is indistinguishable from a random permutation,
and fewer than 2^48 packets are protected, then the attacker’s advantage is
no more than 2^−18." This implies that David thought that 2^-18 was a
sufficient bound.
Note that even the conclusion of [1] says that its bounds for the 96-bit
nonce case is tighter than the bounds from the original proof [0]. So, it
seems strange to use [1] to refute the above claim from [0], when in fact
[1] strengthens [0] for the case of 96-nonces, which is what TLS uses.
[0] https://eprint.iacr.org/2004/193.pdf
> [1] https://eprint.iacr.org/2012/438.pdf
> > [2] https://eprint.iacr.org/2015/214.pdf
[3] https://www.ietf.org/mail-archive/web/tls/current/msg18240.html
Cheers,
Brian
--
https://briansmith.org/
_______________________________________________
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls
