Re: [Cfrg] [TLS] Closing out tls1.3 "Limits on key usage" PRs (#765/#769)

["Paterson, Kenny" <[e-mail]>]

Hi,

On 10/02/2017 18:56, "Dang, Quynh (Fed)" <[e-mail]> wrote:

>Dear Kenny, 
>
>From: "Paterson, Kenny" <[e-mail]>
>Date: Friday, February 10, 2017 at 12:22 PM
>To: 'Quynh' <[e-mail]>, Sean Turner <[e-mail]>
>Cc: IRTF CFRG <[e-mail]>, "<[e-mail]>" <[e-mail]>
>Subject: Re: [TLS] [Cfrg] Closing out tls1.3 "Limits on key usage" PRs
>(#765/#769)
>
>
>
>>Dear Quynh,
>>
>>
>>On 10/02/2017 12:48, "Dang, Quynh (Fed)" <[e-mail]> wrote:
>>
>>
>>>Hi Kenny, 
>>>
>>>
>>>>Hi,
>>>>
>>>>
>>>>
>>>>
>>>>My preference is to go with the existing text, option a).
>>>>
>>>>
>>>>
>>>>
>>>>From the github discussion, I think option c) involves a less
>>>>conservative
>>>>security bound (success probability for IND-CPA attacker bounded by
>>>>2^{-32} instead of 2^{-60}). I can live with that, but the WG should be
>>>>aware of the weaker security guarantees it provides.
>>>>
>>>>
>>>>
>>>>
>>>>I do not understand option b). It seems to rely on an analysis of
>>>>collisions of ciphertext blocks rather than the established security
>>>>proof
>>>>for AES-GCM.
>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>>
>>>My suggestion was based on counting.  I analyzed AES-GCM in TLS 1.3  as
>>>being a counter-mode encryption and each counter is a 96-bit nonce ||
>>>32-bit counter. I don’t know if there is another kind of proof that is
>>>more precise than that.
>>
>>
>>Thanks for explaining. I think, then, that what you are doing is (in
>>effect) accounting for the PRP/PRF switching lemma that is used (in a
>>standard way) as part of the IND-CPA security proof of AES-GCM. One can
>>obtain a greater degree of precision by using the proven bounds for
>>IND-CPA security of AES-GCM. These incorporate the "security loss" coming
>>from the PRP/PRF switching lemma. The current best form of these bounds
>>is
>>due to Iwata et al.. This is precisely what we analyse in the note at
>>http://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf - specifically, see
>>equations (5) - (7) on page 6 of that note.
>>
>
>I reviewed the paper more than once. I highly value the work. I suggested
>to reference  your paper in the text.  I think the result in your paper
>is the same with what is being suggested when the collision probability
>allowed is 2^(-32).

Thanks for this feedback. I guess my confusion arises from wondering what
you mean by collision probability and why you care about it. There are no
collisions in the block cipher's outputs per se, because AES is a
permutation for each choice of key. And collisions in the ciphertext
blocks output by AES-GCM are irrelevant to its formal security analysis.

On the other hand, when in the proof of IND-CPA security of AES-GCM one
switches from a random permutation (which is how we model AES) to a random
function (which is what we need to argue in the end that the plaintext is
masked by a one-time pad, giving indistinguishability), then one needs to
deal with the probability that collisions occur in the function's outputs
but not in the permutation's. This ends up being the main contribution to
the security bound in the proof for IND-CPA security.

Is that what you are getting at?

If so, then we are on the same page, and what remains is to decide whether
a 2^{-32} bound is a good enough security margin.

Regards,

Kenny