On Dec 16, 2015 5:26 PM, "Brian Smith" <br...@briansmith.org> wrote: > > 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.
We've already decided to add a far more complicated support for new authentication. Reykeyinh is not that complicated. > > 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. There are likely to be over 2^40 tls connections globally. > > 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. The claim may be true. But I'm saying 2^-18 is insufficient. > > [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
