Re: [TLS] New draft: draft-ietf-tls-tls13-14.txt

Hey Quynh,

> How can one use the distinguishing attack with the data complexity 
> bound I
> suggested for recovering 1 bit of the encryption key in the context of 
> TLS
> ?
You cannot recover any bits of the encryption key unless you attack AES.

No-one, as far as I know, has analyzed what kind of attacks one can 
perform against GCM around and beyond the birthday bound (except for the 
forgery attacks, which require repeated nonces or known forgeries). 
However, for CTR mode, the underlying encryption of GCM, David McGrew 
typed up a document describing an attack one could perform to recover 
information about the plaintext:
http://eprint.iacr.org/2012/623
He describes it for 64 bit block ciphers, but the attacks work equally 
well for 128 bit block ciphers, at a higher data complexity of course.

Basically, there are a lot of unknowns, and it could be that the bounds 
you recommend will be good enough in practice. However, it's important 
to be clear about the risks involved in venturing into unknown 
territory.

Atul

On 2016-07-13 13:14, Dang, Quynh (Fed) wrote:
> Hi Atul,
> 
> On 7/12/16, 3:50 PM, "Atul Luykx" <Atul.Luykx@esat.kuleuven.be> wrote:
> 
>>> To be clear, this probability is that an attacker would be able to
>>> take a huge (4+ Petabyte) ciphertext, and a compatibly sized 
>>> potential
>>> (but incorrect) plaintext, and with probability 2^{-32}, be able to
>>> determine that this plaintext was not the one used for the ciphertext
>>> (and with probability 0.999999999767..., know nothing about whether
>>> his guessed plaintext was correct or not).
>> 
>> You need to be careful when making such claims. There are schemes for
>> which when you reach the birthday bound you can perform partial key
>> recovery.
>> 
>> The probabilities we calculated guarantee that there won't be any
>> attacks (with the usual assumptions...). Beyond the bounds, there are 
>> no
>> guarantees. In particular, you cannot conclude that one, for example,
>> loses 1 bit of security once beyond the birthday bound.
> 
> How can one use the distinguishing attack with the data complexity 
> bound I
> suggested for recovering 1 bit of the encryption key in the context of 
> TLS
> ?
> 
> 
> Regards,
> Quynh.
> 
> 
> 
> 
>> 
>> Atul
>> 
>> On 2016-07-12 20:06, Scott Fluhrer (sfluhrer) wrote:
>>>> -----Original Message-----
>>>> From: Paterson, Kenny [mailto:Kenny.Paterson@rhul.ac.uk]
>>>> Sent: Tuesday, July 12, 2016 1:17 PM
>>>> To: Dang, Quynh (Fed); Scott Fluhrer (sfluhrer); Eric Rescorla;
>>>> tls@ietf.org
>>>> Subject: Re: [TLS] New draft: draft-ietf-tls-tls13-14.txt
>>>> 
>>>> Hi
>>>> 
>>>> On 12/07/2016 18:04, "Dang, Quynh (Fed)" <quynh.dang@nist.gov> 
>>>> wrote:
>>>> 
>>>> >Hi Kenny,
>>>> >
>>>> >On 7/12/16, 12:33 PM, "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
>>>> wrote:
>>>> >
>>>> >>Finally, you write "to come to the 2^38 record limit, they assume
>>>> that
>>>> >>each record is the maximum 2^14 bytes". For clarity, we did not
>>>> >>recommend a limit of 2^38 records. That's Quynh's preferred number,
>>>> >>and is unsupported by our analysis.
>>>> >
>>>> >What is problem with my suggestion even with the record size being the
>>>> >maximum value?
>>>> 
>>>> There may be no problem with your suggestion. I was simply trying to
>>>> make it
>>>> clear that 2^38 records was your suggestion for the record limit and
>>>> not ours.
>>>> Indeed, if one reads our note carefully, one will find that we do 
>>>> not
>>>> make any
>>>> specific recommendations. We consider the decision to be one for the
>>>> WG;
>>>> our preferred role is to supply the analysis and help interpret it 
>>>> if
>>>> people
>>>> want that. Part of that involves correcting possible misconceptions
>>>> and
>>>> misinterpretations before they get out of hand.
>>>> 
>>>> Now 2^38 does come out of our analysis if you are willing to accept
>>>> single key
>>>> attack security (in the indistinguishability sense) of 2^{-32}. So 
>>>> in
>>>> that limited
>>>> sense, 2^38 is supported by our analysis. But it is not our
>>>> recommendation.
>>>> 
>>>> But, speaking now in a personal capacity, I consider that security
>>>> margin to be
>>>> too small (i.e. I think that 2^{-32} is too big a success
>>>> probability).
>>> 
>>> To be clear, this probability is that an attacker would be able to
>>> take a huge (4+ Petabyte) ciphertext, and a compatibly sized 
>>> potential
>>> (but incorrect) plaintext, and with probability 2^{-32}, be able to
>>> determine that this plaintext was not the one used for the ciphertext
>>> (and with probability 0.999999999767..., know nothing about whether
>>> his guessed plaintext was correct or not).
>>> 
>>> I'm just trying to get people to understand what we're talking about.
>>> This is not "with probability 2^{-32}, he can recover the plaintext"
>>> 
>>> 
>>>> 
>>>> Regards,
>>>> 
>>>> Kenny
>>> 
>>> _______________________________________________
>>> TLS mailing list
>>> TLS@ietf.org
>>> https://www.ietf.org/mailman/listinfo/tls