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

Hey Quynh,

> When someone says AES-128 has 128 bits of security he or she means
> that 2^128 AES operations will break the cipher with probability 100%:
> finding the key and the plaintext.
The claim is stronger: regardless of the number of plaintext-ciphertext 
pairs available to the adversary, it will still take roughly 2^128 
operations to recover the key with AES. This contrasts with any mode of 
operation, where adversarial success probability increases according to 
the amount of data available and the computational complexity required 
to perform such an attack is not the limiting factor (which is the core 
of the problem we're discussing right now).

Regardless, correct me if I'm wrong Quynh, but you seem to have two 
issues with Eric's text:
1. the data limit recommendation is too strict, and
2. it only gives a data limit in terms of full records.

For point 1 it seems like most people would rather err on the side of 
caution instead of recommending that people switch when adversaries have 
success probability 2^{-32}. I don't see the discussion progressing on 
this point, and basically a decision needs to be made.

I don't think point 2 is a problem because it gives people a good enough 
heuristic, however this can be fixed easily by minimally modifying the 
original text.

Atul

On 2017-02-14 03:59, Dang, Quynh (Fed) wrote:
> Hi Markulf and all,
> 
> I provided more explanation below.
> 
>  From: 'Quynh' <Quynh.Dang@nist.gov>
> Date: Monday, February 13, 2017 at 10:45 AM
> To: Markulf Kohlweiss <markulf@microsoft.com>, "Paterson, Kenny"
> <Kenny.Paterson@rhul.ac.uk>, Sean Turner <sean@sn3rd.com>
> Cc: Antoine Delignat-Lavaud <antdl@microsoft.com>, IRTF CFRG
> <cfrg@irtf.org>, "<tls@ietf.org>" <tls@ietf.org>
> Subject: Re: [TLS] [Cfrg] Closing out tls1.3 "Limits on key usage" PRs
> (#765/#769)
> 
>> Hi Markulf,
>> 
>> The probability of a bad thing to happen is actually below (or
>> about) 2^(-33). It practically won’t happen when the chance is 1
>> in 2^32. And, to achieve that chance, you must collect 2^48 128-bit
>> blocks.
>> 
>> Regards,
>> Quynh.
>> 
>> From: TLS <tls-bounces@ietf.org> on behalf of Markulf Kohlweiss
>> <markulf@microsoft.com>
>> Date: Monday, February 13, 2017 at 10:34 AM
>> To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>, Sean Turner
>> <sean@sn3rd.com>
>> Cc: Antoine Delignat-Lavaud <antdl@microsoft.com>, IRTF CFRG
>> <cfrg@irtf.org>, "<tls@ietf.org>" <tls@ietf.org>
>> Subject: Re: [TLS] [Cfrg] Closing out tls1.3 "Limits on key usage"
>> PRs (#765/#769)
>> 
>>> Hello,
>>> 
>>> Our analysis of miTLS also supports option a)
>>> 
>>> A security level of 2^-32 seems too low from a provable security
>>> point of view, especially for a confidentiality bound.
> 
> When someone says AES-128 has 128 bits of security he or she means
> that 2^128 AES operations will break the cipher with probability 100%:
> finding the key and the plaintext.  It does not mean that attackers
> have only 2^(-128) chance of success. If an attacker could run 2^100
> AES operations, his or her chance of success is way below 2^(-32):
> this does not mean that AES has a security level of 2^(-32) or
> 2^(-28).
> 
> The success probability 1/2^32 means that after 2^48 AES operations,
> the attacker has a success probability of 2^-32 which is practically
> zero.
> 
> Also, many users don’t know what “confidentiality bound” means.
> 
> The current text Eric wrote talks about a number 2^24.5 of full-size
> records. In many situations, the record sizes are not full size, but
> different sizes. My latest suggestion text does not assume full size
> records, it covers variable record sizes, it just counts AES-input
> blocks or AES operations.
> 
> Regards,
> Quynh.
> 
>> We verified an implementation of the TLS 1.3 record
>> (https://eprint.iacr.org/2016/1178, to appear at Security & Privacy
>> 2017) where we arrive at a combined bound for authenticity and
>> confidentiality that is compatible with the Iwata et al. bound.
>> 
>> Regards,
>> Markulf (for the miTLS team)
>> 
>> 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.
>> 
>> Regards,
>> 
>> Kenny
>> 
>> On 10/02/2017 05:44, "Cfrg on behalf of Martin Thomson"
>> <cfrg-bounces at irtf.org on behalf of martin.thomson at gmail.com>
>> wrote:
>> 
>> On 10 February 2017 at 16:07, Sean Turner <sean at sn3rd.com> wrote:
>> 
>> a) Close these two PRs and go with the existing text [0]
>> b) Adopt PR#765 [1]
>> c) Adopt PR#769 [2]
>> 
>> a) I'm happy enough with the current text (I've implemented that any
>> 
>> it's relatively easy).
>> 
>> I could live with c, but I'm opposed to b. It just doesn't make
>> sense.
>> It's not obviously wrong any more, but the way it is written it is
>> very confusing and easily open to misinterpretation.
>> 
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg at irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
> 
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls