Re: [TLS] Data limit for GCM under a given key.

[Yoav Nir]

> On 7 Nov 2015, at 12:50 PM, Eric Rescorla  wrote:
> 
> 
> 
> On Fri, Nov 6, 2015 at 7:46 PM, Yoav Nir  > wrote:
> 
> > On 7 Nov 2015, at 11:39 AM, Dave Garrett  > > wrote:
> >
> > On Friday, November 06, 2015 08:13:44 pm Eric Rescorla wrote:
> >> Update: we discussed this extensively in Yokohama and based on Watson's
> >> feedback and offline comments from David McGrew, the consensus was that we
> >> needed to add some sort of rekeying mechanism to support long-lived flows.
> >> Expect a PR on this next week.
> >>
> >> Note: We'll still need guidance to implementations on when to re-key, but
> >> we don't expect to have a hard protocol limit.
> >
> > If re-keying is back up for discussion, let me restate my request for it to 
> > be routine, rather than only an niche-case feature. Any re-key schedule 
> > should be considered valid, but the spec should set a "SHOULD"-level 
> > requirement that the minimum be once every N hours or M terabytes, 
> > whichever comes first (where N & M are some bike-shedable numbers with some 
> > expectation of randomization in values for each period).
> 
> N and M will be different depending on the algorithms, no?
> 
> I think before we start with pull requests we should be certain of what the 
> requirements are for this rekeying.
> 
> These were discussed extensively both in the interim and at IETF. The purpose 
> of rekeying in this context is to deal with cryptographic exhaustion, namely 
> having more ciphertext under the same key than is safe for a
> given algorithm (where safe is defined by an analysis like the one Watson
> has posted upthread).

Sure, but once you provide a rekeying capability, the connection can keep going 
forever. That means you could be running for weeks and terabytes without 
injecting any freshness, and the the internal state remains in memory for all 
that time. A compromise of the state in the future allows decrypting everything 
since the beginning of the connection. This is not the same as having to tear 
down the connection at the cryptographic exhaustion.

It is possible to get this kind of forward secrecy if the rekeying includes 
modifying the internal state in a non-reversible way such as hashing the master 
secret into a new master secret (or using HKDF-Extract), but that hurts the 
goal of having each side recycle the keys at its own pace (which is a strange 
goal, because my security depends on the security of my receiving keys as much 
as it depends on the security of my transmitting keys).

Yoav

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Data limit for GCM under a given key.

[Quynh Dang]

Hi Eric and Watson,

On Sat, Nov 7, 2015 at 12:50 PM, Eric Rescorla  wrote:

>
>
> On Fri, Nov 6, 2015 at 7:46 PM, Yoav Nir  wrote:
>
>>
>> > On 7 Nov 2015, at 11:39 AM, Dave Garrett 
>> wrote:
>> >
>> > On Friday, November 06, 2015 08:13:44 pm Eric Rescorla wrote:
>> >> Update: we discussed this extensively in Yokohama and based on Watson's
>> >> feedback and offline comments from David McGrew, the consensus was
>> that we
>> >> needed to add some sort of rekeying mechanism to support long-lived
>> flows.
>> >> Expect a PR on this next week.
>> >>
>> >> Note: We'll still need guidance to implementations on when to re-key,
>> but
>> >> we don't expect to have a hard protocol limit.
>> >
>> > If re-keying is back up for discussion, let me restate my request for
>> it to be routine, rather than only an niche-case feature. Any re-key
>> schedule should be considered valid, but the spec should set a
>> "SHOULD"-level requirement that the minimum be once every N hours or M
>> terabytes, whichever comes first (where N & M are some bike-shedable
>> numbers with some expectation of randomization in values for each period).
>>
>> N and M will be different depending on the algorithms, no?
>>
>> I think before we start with pull requests we should be certain of what
>> the requirements are for this rekeying.
>>
>
> These were discussed extensively both in the interim and at IETF. The
> purpose of rekeying in this context is to deal with cryptographic
> exhaustion, namely having more ciphertext under the same key than is safe
> for a
> given algorithm (where safe is defined by an analysis like the one Watson
> has posted upthread).
>

You basically said here was that what I described was not safe. Show me how
to break the following:

I encrypt 2^64 plaintext blocks with 2^64 different IVs with AES (with the
same key), then give you the 2^64 ciphertext blocks. Show me an attack that
you can recover any of the plaintext blocks. All of the plaintext blocks
can be the same block, they can be all different or some of them are
repeated block(s) of other block(s).


>
>
>
>> Are we OK with just generating new keys from the same internal state (so
>> the handshake message is pretty much only “rekey now”),
>
>
> I believe this is what we agreed both in Seattle and in Prague.
>
> -Ekr
>
>
>
>> or
>> Do we want freshness (usually in the form of new mutual nonces, or
>> Do we want forward secrecy so another diffie-hellamn exchange?
>>
>> Yoav
>> ___
>> 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


I support rekeying often to avoid disaster to keep going on just in case
there is something wrong with the key or IV as I stated before.

Quynh.
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Data limit for GCM under a given key.

[Dang, Quynh]

Tony,


You are correct. An Indistinguishability bound promises you no attacks will be 
below the bound assuming the claimed property(ies) of the underline function in 
the construction (mode) hold(s).


A distinguishing attack below the bound tells you that the construction or the 
underlined function is not strong or ideal as you would like, but it does not 
directly (100%) lead to a break of plaintext confidentiality or authenticity.  
Here, confidentiality protection of plaintext(s) is that an attacker who does 
not know the key can not find out any part of the plaintext(s) by decryption. 
And, I explained the point in the previous emails.


Under indistinguishability framework, one should not even go to 2^32 blocks 
with GCM when the IV space is 2^64 because there is a high probability of 
ciphertext collision with 2^32 ciphertexts.


Quynh.





From: Tony Arcieri 
Sent: Friday, November 6, 2015 7:59 PM
To: Watson Ladd
Cc: Dang, Quynh; tls@ietf.org
Subject: Re: [TLS] Data limit for GCM under a given key.

On Friday, November 6, 2015, Watson Ladd 
mailto:watsonbl...@gmail.com>> wrote:
On Wed, Nov 4, 2015 at 3:43 PM, Dang, Quynh  wrote:
> I did not talk  under indistinguishability framework. My discussion was about 
> confidentiality protection and authentication.

What is the definition of "confidentiality protection" being used here?

I too am confused by Quynh's statement. Indistinguishability is the modern bar 
for confidentiality and authentication.

Quynh, are you talking about anything less than IND-CCA2? If you are, that is 
less than the modern bar I would personally consider acceptable.


--
Tony Arcieri

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Data limit for GCM under a given key.

[Dave Garrett]

On Friday, November 06, 2015 10:54:02 pm Eric Rescorla wrote:
> I don't believe time-based guidance is useful here, given that it's highly
> situation specific rather than derived from reasoning about the properties
> of the cipher.

One reason to have a regular interval between rekeys is to ensure that it's a 
standard operation, rather than something implementations in many use-cases 
never see and possibly muck up when they eventually do. The time does not need 
to be short, though, and can vary by algorithm and implementation discretion.


Dave

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Data limit for GCM under a given key.

[Eric Rescorla]

On Fri, Nov 6, 2015 at 7:50 PM, Eric Rescorla  wrote:

>
>
> On Fri, Nov 6, 2015 at 7:46 PM, Yoav Nir  wrote:
>
>>
>> > On 7 Nov 2015, at 11:39 AM, Dave Garrett 
>> wrote:
>> >
>> > On Friday, November 06, 2015 08:13:44 pm Eric Rescorla wrote:
>> >> Update: we discussed this extensively in Yokohama and based on Watson's
>> >> feedback and offline comments from David McGrew, the consensus was
>> that we
>> >> needed to add some sort of rekeying mechanism to support long-lived
>> flows.
>> >> Expect a PR on this next week.
>> >>
>> >> Note: We'll still need guidance to implementations on when to re-key,
>> but
>> >> we don't expect to have a hard protocol limit.
>> >
>> > If re-keying is back up for discussion, let me restate my request for
>> it to be routine, rather than only an niche-case feature. Any re-key
>> schedule should be considered valid, but the spec should set a
>> "SHOULD"-level requirement that the minimum be once every N hours or M
>> terabytes, whichever comes first (where N & M are some bike-shedable
>> numbers with some expectation of randomization in values for each period).
>>
>> N and M will be different depending on the algorithms, no?
>>
>> I think before we start with pull requests we should be certain of what
>> the requirements are for this rekeying.
>>
>
> These were discussed extensively both in the interim and at IETF. The
> purpose of rekeying in this context is to deal with cryptographic
> exhaustion, namely having more ciphertext under the same key than is safe
> for a
> given algorithm (where safe is defined by an analysis like the one Watson
> has posted upthread).
>

To be clear, I'm not saying that there aren't other reasons for rekeying,
just that the problem agreed to address is the one above.

-Ekr


> Are we OK with just generating new keys from the same internal state (so
>> the handshake message is pretty much only “rekey now”),
>
>
> I believe this is what we agreed both in Seattle and in Prague.
>
> -Ekr
>
>
>
>> or
>> Do we want freshness (usually in the form of new mutual nonces, or
>> Do we want forward secrecy so another diffie-hellamn exchange?
>>
>> Yoav
>> ___
>> 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

Re: [TLS] Data limit for GCM under a given key.

[Eric Rescorla]

On Fri, Nov 6, 2015 at 6:39 PM, Dave Garrett  wrote:

> On Friday, November 06, 2015 08:13:44 pm Eric Rescorla wrote:
> > Update: we discussed this extensively in Yokohama and based on Watson's
> > feedback and offline comments from David McGrew, the consensus was that
> we
> > needed to add some sort of rekeying mechanism to support long-lived
> flows.
> > Expect a PR on this next week.
> >
> > Note: We'll still need guidance to implementations on when to re-key, but
> > we don't expect to have a hard protocol limit.
>
> If re-keying is back up for discussion, let me restate my request for it
> to be routine, rather than only an niche-case feature. Any re-key schedule
> should be considered valid, but the spec should set a "SHOULD"-level
> requirement that the minimum be once every N hours or M terabytes,
> whichever comes first (where N & M are some bike-shedable numbers with some
> expectation of randomization in values for each period).


As I said above, I agree that the specification should provide some
guidance on how often you should re-key for a given cipher based on the
number of records/cipher blocks (whatever is more convenient for analysis).
This guidance should be derived from the kind of analysis Watson and Dave
McGrew have done for these algorithms, and, as Watson's analysis suggests,
is likely to be algorithm specific.

I don't believe time-based guidance is useful here, given that it's highly
situation specific rather than derived from reasoning about the properties
of the cipher.

-Ekr
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Data limit for GCM under a given key.

[Eric Rescorla]

On Fri, Nov 6, 2015 at 7:46 PM, Yoav Nir  wrote:

>
> > On 7 Nov 2015, at 11:39 AM, Dave Garrett  wrote:
> >
> > On Friday, November 06, 2015 08:13:44 pm Eric Rescorla wrote:
> >> Update: we discussed this extensively in Yokohama and based on Watson's
> >> feedback and offline comments from David McGrew, the consensus was that
> we
> >> needed to add some sort of rekeying mechanism to support long-lived
> flows.
> >> Expect a PR on this next week.
> >>
> >> Note: We'll still need guidance to implementations on when to re-key,
> but
> >> we don't expect to have a hard protocol limit.
> >
> > If re-keying is back up for discussion, let me restate my request for it
> to be routine, rather than only an niche-case feature. Any re-key schedule
> should be considered valid, but the spec should set a "SHOULD"-level
> requirement that the minimum be once every N hours or M terabytes,
> whichever comes first (where N & M are some bike-shedable numbers with some
> expectation of randomization in values for each period).
>
> N and M will be different depending on the algorithms, no?
>
> I think before we start with pull requests we should be certain of what
> the requirements are for this rekeying.
>

These were discussed extensively both in the interim and at IETF. The
purpose of rekeying in this context is to deal with cryptographic
exhaustion, namely having more ciphertext under the same key than is safe
for a
given algorithm (where safe is defined by an analysis like the one Watson
has posted upthread).



> Are we OK with just generating new keys from the same internal state (so
> the handshake message is pretty much only “rekey now”),


I believe this is what we agreed both in Seattle and in Prague.

-Ekr



> or
> Do we want freshness (usually in the form of new mutual nonces, or
> Do we want forward secrecy so another diffie-hellamn exchange?
>
> Yoav
> ___
> 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

Re: [TLS] Data limit for GCM under a given key.

[Yoav Nir]

> On 7 Nov 2015, at 11:39 AM, Dave Garrett  wrote:
> 
> On Friday, November 06, 2015 08:13:44 pm Eric Rescorla wrote:
>> Update: we discussed this extensively in Yokohama and based on Watson's
>> feedback and offline comments from David McGrew, the consensus was that we
>> needed to add some sort of rekeying mechanism to support long-lived flows.
>> Expect a PR on this next week.
>> 
>> Note: We'll still need guidance to implementations on when to re-key, but
>> we don't expect to have a hard protocol limit.
> 
> If re-keying is back up for discussion, let me restate my request for it to 
> be routine, rather than only an niche-case feature. Any re-key schedule 
> should be considered valid, but the spec should set a "SHOULD"-level 
> requirement that the minimum be once every N hours or M terabytes, whichever 
> comes first (where N & M are some bike-shedable numbers with some expectation 
> of randomization in values for each period).

N and M will be different depending on the algorithms, no?

I think before we start with pull requests we should be certain of what the 
requirements are for this rekeying.

Are we OK with just generating new keys from the same internal state (so the 
handshake message is pretty much only “rekey now”), or
Do we want freshness (usually in the form of new mutual nonces, or
Do we want forward secrecy so another diffie-hellamn exchange?

Yoav
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Data limit for GCM under a given key.

[Dave Garrett]

On Friday, November 06, 2015 08:13:44 pm Eric Rescorla wrote:
> Update: we discussed this extensively in Yokohama and based on Watson's
> feedback and offline comments from David McGrew, the consensus was that we
> needed to add some sort of rekeying mechanism to support long-lived flows.
> Expect a PR on this next week.
> 
> Note: We'll still need guidance to implementations on when to re-key, but
> we don't expect to have a hard protocol limit.

If re-keying is back up for discussion, let me restate my request for it to be 
routine, rather than only an niche-case feature. Any re-key schedule should be 
considered valid, but the spec should set a "SHOULD"-level requirement that the 
minimum be once every N hours or M terabytes, whichever comes first (where N & 
M are some bike-shedable numbers with some expectation of randomization in 
values for each period).


Dave

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Data limit for GCM under a given key.

[Eric Rescorla]

Update: we discussed this extensively in Yokohama and based on Watson's
feedback and offline comments from David McGrew, the consensus was that we
needed to add some sort of rekeying mechanism to support long-lived flows.
Expect a PR on this next week.

Note: We'll still need guidance to implementations on when to re-key, but
we don't expect to have a hard protocol limit.

-Ekr



On Fri, Nov 6, 2015 at 4:59 PM, Tony Arcieri  wrote:

> On Friday, November 6, 2015, Watson Ladd  wrote:
>
>> On Wed, Nov 4, 2015 at 3:43 PM, Dang, Quynh  wrote:
>> > I did not talk  under indistinguishability framework. My discussion was
>> about confidentiality protection and authentication.
>>
>> What is the definition of "confidentiality protection" being used here?
>>
>
> I too am confused by Quynh's statement. Indistinguishability is the modern
> bar for confidentiality and authentication.
>
> Quynh, are you talking about anything less than IND-CCA2? If you are, that
> is less than the modern bar I would personally consider acceptable.
>
>
> --
> Tony Arcieri
>
>
> ___
> 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

Re: [TLS] Data limit for GCM under a given key.

[Tony Arcieri]

On Friday, November 6, 2015, Watson Ladd  wrote:

> On Wed, Nov 4, 2015 at 3:43 PM, Dang, Quynh  > wrote:
> > I did not talk  under indistinguishability framework. My discussion was
> about confidentiality protection and authentication.
>
> What is the definition of "confidentiality protection" being used here?
>

I too am confused by Quynh's statement. Indistinguishability is the modern
bar for confidentiality and authentication.

Quynh, are you talking about anything less than IND-CCA2? If you are, that
is less than the modern bar I would personally consider acceptable.


-- 
Tony Arcieri
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

Re: [TLS] Data limit for GCM under a given key.

[Watson Ladd]

On Wed, Nov 4, 2015 at 3:43 PM, Dang, Quynh  wrote:
> I did not talk  under indistinguishability framework. My discussion was about 
> confidentiality protection and authentication.

What is the definition of "confidentiality protection" being used here?
>
> Quynh.
> 
> From: Watson Ladd 
> Sent: Wednesday, November 4, 2015 3:17:00 PM
> To: Dang, Quynh
> Cc: Eric Rescorla; tls@ietf.org
> Subject: Re: [TLS] Data limit for GCM under a given key.
>
> On Wed, Nov 4, 2015 at 2:29 PM, Dang, Quynh  wrote:
>> Hi Eric and all,
>>
>>
>> The limit of 2^48 packets under a given key for GCM you mentioned today is
>> the limit for SRTP
>> (https://tools.ietf.org/html/draft-ietf-avtcore-srtp-aes-gcm-17#section-6).
>> The nonce space of the IV construction is only 48 bits and that is why it
>> has the limit of 2^48. The limit here should be 2^48 blocks, not records as
>> stated in the document.
>>
>>
>> As I explained before, GCM is counter mode for encryption. For a given key,
>> the nonce never repeats globally, then confidentiality of the encrypted data
>> is preserved. When the nonce space is 2^n values, then 2^n message blocks
>> can have secure confidentiality protection.
>
> This is completely untrue. If you actually understood the definitions,
> and thought about the matter for 15 minutes, you would realize that
> permutations are distinguishable from functions after 2^(n/2) queries
> with high probabilities, and this breaks IND-$. This is an elementary
> result found on page 134 of Boneh-Shoup.
>
>>
>>
>> Regarding to authentication, as I explained before, if the tag size is n,
>> then you have collision issue among the tags when the number of tags goes
>> around 2^(n/2) which is not a good thing, but strictly speaking, this does
>> not break your authentication.
>
> Carter-Wegman security results are weaker than for PRF-based MACs.
>>
>>
>> However, rekeying often is a good thing which could help prevent disaster to
>> keep go on if there is something wrong with the IV or the key.
>>
>>
>> Quynh.
>>
>>
>>
>>
>> 
>> From: Dang, Quynh
>> Sent: Monday, November 2, 2015 3:00 PM
>> To: Watson Ladd
>> Cc: tls@ietf.org; c...@ietf.org; Eric Rescorla
>> Subject: Re: [Cfrg] Collision issue in ciphertexts.
>>
>>
>> Now, you talked about a MAC function (with AES). I previously talked about
>> encryption.
>>
>>
>> If I , the only person, uses the MAC key, when I generate more than 2^64 MAC
>> values (Let's say each MAC value is 96 bits), I have many collided MAC
>> pairs. But, I am the only one (beside the person(s) verifying my MACs) who
>> knows the MAC key in order to generate those  verified MAC values.
>>
>>
>> If the MAC length is k bits, an attacker is allowed to send 2^n failed
>> verifications, his or her chance of success is approximately 2^n / 2^k.
>> Let's imagine n is 64 and k is 96, the success chance is 1/2^36 which is
>> practically ZERO!
>>
>>
>> If I am an attacker, I would choose a message that I want to be verified,
>> and I keep changing the MAC key to generate different MAC values with
>> different keys and hope one of them will get verified.  Let's assume the MAC
>> key to be 96 bits ( 96 bits of random bits, the other 32 bits are known). In
>> theory, when I get close to 2^96 attempts, I would expect some chance of
>> success. To deal with this attacker, one would change the MAC key when the
>> number of failed attempts gets close to a number that you don't want. For
>> example, if you don't want a success chance of an attack to be above 1 /
>> 2^36, then you need to change your MAC key when the number of failed
>> verifications reaches 2^64 when your MAC length is 96 bits.
>>
>>
>> After you change the MAC key, I ( the attacker) will have to start
>> everything again because all of the failed MACs I generated before are
>> useless now.
>>
>>
>> 
>> From: Watson Ladd 
>> Sent: Monday, November 2, 2015 5:07 AM
>> To: Dang, Quynh
>> Cc: tls@ietf.org; c...@ietf.org; Eric Rescorla
>> Subject: Re: [Cfrg] Collision issue in ciphertexts.
>>
>>
>>
>> On Nov 2, 2015 2:14 AM, "Dang, Quynh"  wrote:
>>>
>>> Hi Eric,
>>>
>>>
>>> As you asked the question about how many ciphertext blocks should be safe
>>> under a single key, I think it is safe to have 2^96 b

Re: [TLS] Data limit for GCM under a given key.

[Dang, Quynh]

I did not talk  under indistinguishability framework. My discussion was about 
confidentiality protection and authentication.

Quynh.

From: Watson Ladd 
Sent: Wednesday, November 4, 2015 3:17:00 PM
To: Dang, Quynh
Cc: Eric Rescorla; tls@ietf.org
Subject: Re: [TLS] Data limit for GCM under a given key.

On Wed, Nov 4, 2015 at 2:29 PM, Dang, Quynh  wrote:
> Hi Eric and all,
>
>
> The limit of 2^48 packets under a given key for GCM you mentioned today is
> the limit for SRTP
> (https://tools.ietf.org/html/draft-ietf-avtcore-srtp-aes-gcm-17#section-6).
> The nonce space of the IV construction is only 48 bits and that is why it
> has the limit of 2^48. The limit here should be 2^48 blocks, not records as
> stated in the document.
>
>
> As I explained before, GCM is counter mode for encryption. For a given key,
> the nonce never repeats globally, then confidentiality of the encrypted data
> is preserved. When the nonce space is 2^n values, then 2^n message blocks
> can have secure confidentiality protection.

This is completely untrue. If you actually understood the definitions,
and thought about the matter for 15 minutes, you would realize that
permutations are distinguishable from functions after 2^(n/2) queries
with high probabilities, and this breaks IND-$. This is an elementary
result found on page 134 of Boneh-Shoup.

>
>
> Regarding to authentication, as I explained before, if the tag size is n,
> then you have collision issue among the tags when the number of tags goes
> around 2^(n/2) which is not a good thing, but strictly speaking, this does
> not break your authentication.

Carter-Wegman security results are weaker than for PRF-based MACs.
>
>
> However, rekeying often is a good thing which could help prevent disaster to
> keep go on if there is something wrong with the IV or the key.
>
>
> Quynh.
>
>
>
>
> 
> From: Dang, Quynh
> Sent: Monday, November 2, 2015 3:00 PM
> To: Watson Ladd
> Cc: tls@ietf.org; c...@ietf.org; Eric Rescorla
> Subject: Re: [Cfrg] Collision issue in ciphertexts.
>
>
> Now, you talked about a MAC function (with AES). I previously talked about
> encryption.
>
>
> If I , the only person, uses the MAC key, when I generate more than 2^64 MAC
> values (Let's say each MAC value is 96 bits), I have many collided MAC
> pairs. But, I am the only one (beside the person(s) verifying my MACs) who
> knows the MAC key in order to generate those  verified MAC values.
>
>
> If the MAC length is k bits, an attacker is allowed to send 2^n failed
> verifications, his or her chance of success is approximately 2^n / 2^k.
> Let's imagine n is 64 and k is 96, the success chance is 1/2^36 which is
> practically ZERO!
>
>
> If I am an attacker, I would choose a message that I want to be verified,
> and I keep changing the MAC key to generate different MAC values with
> different keys and hope one of them will get verified.  Let's assume the MAC
> key to be 96 bits ( 96 bits of random bits, the other 32 bits are known). In
> theory, when I get close to 2^96 attempts, I would expect some chance of
> success. To deal with this attacker, one would change the MAC key when the
> number of failed attempts gets close to a number that you don't want. For
> example, if you don't want a success chance of an attack to be above 1 /
> 2^36, then you need to change your MAC key when the number of failed
> verifications reaches 2^64 when your MAC length is 96 bits.
>
>
> After you change the MAC key, I ( the attacker) will have to start
> everything again because all of the failed MACs I generated before are
> useless now.
>
>
> 
> From: Watson Ladd 
> Sent: Monday, November 2, 2015 5:07 AM
> To: Dang, Quynh
> Cc: tls@ietf.org; c...@ietf.org; Eric Rescorla
> Subject: Re: [Cfrg] Collision issue in ciphertexts.
>
>
>
> On Nov 2, 2015 2:14 AM, "Dang, Quynh"  wrote:
>>
>> Hi Eric,
>>
>>
>> As you asked the question about how many ciphertext blocks should be safe
>> under a single key, I think it is safe to have 2^96 blocks under a given key
>> if the IV (counter) is 96 bits.
>
> This is wrong for PRP, right for PRF. It's not that hard to find the right
> result.
>
>>
>>
>> When there is a collision between two ciphertext blocks when two different
>> counter values are used , the chance of the same plaintext was used twice is
>> 1^128.  Collisions start to happen a lot when the number of ciphertext
>> blocks are above 2^64. However, each collision just reveals that the
>> corresponding plaintext blocks are probably different ones.
>
>

Re: [TLS] Data limit for GCM under a given key.

[Watson Ladd]

On Wed, Nov 4, 2015 at 2:29 PM, Dang, Quynh  wrote:
> Hi Eric and all,
>
>
> The limit of 2^48 packets under a given key for GCM you mentioned today is
> the limit for SRTP
> (https://tools.ietf.org/html/draft-ietf-avtcore-srtp-aes-gcm-17#section-6).
> The nonce space of the IV construction is only 48 bits and that is why it
> has the limit of 2^48. The limit here should be 2^48 blocks, not records as
> stated in the document.
>
>
> As I explained before, GCM is counter mode for encryption. For a given key,
> the nonce never repeats globally, then confidentiality of the encrypted data
> is preserved. When the nonce space is 2^n values, then 2^n message blocks
> can have secure confidentiality protection.

This is completely untrue. If you actually understood the definitions,
and thought about the matter for 15 minutes, you would realize that
permutations are distinguishable from functions after 2^(n/2) queries
with high probabilities, and this breaks IND-$. This is an elementary
result found on page 134 of Boneh-Shoup.

>
>
> Regarding to authentication, as I explained before, if the tag size is n,
> then you have collision issue among the tags when the number of tags goes
> around 2^(n/2) which is not a good thing, but strictly speaking, this does
> not break your authentication.

Carter-Wegman security results are weaker than for PRF-based MACs.
>
>
> However, rekeying often is a good thing which could help prevent disaster to
> keep go on if there is something wrong with the IV or the key.
>
>
> Quynh.
>
>
>
>
> 
> From: Dang, Quynh
> Sent: Monday, November 2, 2015 3:00 PM
> To: Watson Ladd
> Cc: tls@ietf.org; c...@ietf.org; Eric Rescorla
> Subject: Re: [Cfrg] Collision issue in ciphertexts.
>
>
> Now, you talked about a MAC function (with AES). I previously talked about
> encryption.
>
>
> If I , the only person, uses the MAC key, when I generate more than 2^64 MAC
> values (Let's say each MAC value is 96 bits), I have many collided MAC
> pairs. But, I am the only one (beside the person(s) verifying my MACs) who
> knows the MAC key in order to generate those  verified MAC values.
>
>
> If the MAC length is k bits, an attacker is allowed to send 2^n failed
> verifications, his or her chance of success is approximately 2^n / 2^k.
> Let's imagine n is 64 and k is 96, the success chance is 1/2^36 which is
> practically ZERO!
>
>
> If I am an attacker, I would choose a message that I want to be verified,
> and I keep changing the MAC key to generate different MAC values with
> different keys and hope one of them will get verified.  Let's assume the MAC
> key to be 96 bits ( 96 bits of random bits, the other 32 bits are known). In
> theory, when I get close to 2^96 attempts, I would expect some chance of
> success. To deal with this attacker, one would change the MAC key when the
> number of failed attempts gets close to a number that you don't want. For
> example, if you don't want a success chance of an attack to be above 1 /
> 2^36, then you need to change your MAC key when the number of failed
> verifications reaches 2^64 when your MAC length is 96 bits.
>
>
> After you change the MAC key, I ( the attacker) will have to start
> everything again because all of the failed MACs I generated before are
> useless now.
>
>
> 
> From: Watson Ladd 
> Sent: Monday, November 2, 2015 5:07 AM
> To: Dang, Quynh
> Cc: tls@ietf.org; c...@ietf.org; Eric Rescorla
> Subject: Re: [Cfrg] Collision issue in ciphertexts.
>
>
>
> On Nov 2, 2015 2:14 AM, "Dang, Quynh"  wrote:
>>
>> Hi Eric,
>>
>>
>> As you asked the question about how many ciphertext blocks should be safe
>> under a single key, I think it is safe to have 2^96 blocks under a given key
>> if the IV (counter) is 96 bits.
>
> This is wrong for PRP, right for PRF. It's not that hard to find the right
> result.
>
>>
>>
>> When there is a collision between two ciphertext blocks when two different
>> counter values are used , the chance of the same plaintext was used twice is
>> 1^128.  Collisions start to happen a lot when the number of ciphertext
>> blocks are above 2^64. However, each collision just reveals that the
>> corresponding plaintext blocks are probably different ones.
>
> Which breaks IND-$. Let's not be clever, but stick to ensuring proven
> definitions are true.
>
>>
>>
>>
>> Quynh.
>>
>>
>> ___
>> Cfrg mailing list
>> c...@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
> ___
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls
>



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls

[TLS] Data limit for GCM under a given key.

[Dang, Quynh]

Hi Eric and all,


The limit of 2^48 packets under a given key for GCM you mentioned today is the 
limit for SRTP 
(https://tools.ietf.org/html/draft-ietf-avtcore-srtp-aes-gcm-17#section-6). The 
nonce space of the IV construction is only 48 bits and that is why it has the 
limit of 2^48. The limit here should be 2^48 blocks, not records as stated in 
the document.


As I explained before, GCM is counter mode for encryption. For a given key, the 
nonce never repeats globally, then confidentiality of the encrypted data is 
preserved. When the nonce space is 2^n values, then 2^n message blocks can have 
secure confidentiality protection.


Regarding to authentication, as I explained before, if the tag size is n, then 
you have collision issue among the tags when the number of tags goes around 
2^(n/2) which is not a good thing, but strictly speaking, this does not break 
your authentication.


However, rekeying often is a good thing which could help prevent disaster to 
keep go on if there is something wrong with the IV or the key.


Quynh.




From: Dang, Quynh
Sent: Monday, November 2, 2015 3:00 PM
To: Watson Ladd
Cc: tls@ietf.org; c...@ietf.org; Eric Rescorla
Subject: Re: [Cfrg] Collision issue in ciphertexts.


Now, you talked about a MAC function (with AES). I previously talked about 
encryption.


If I , the only person, uses the MAC key, when I generate more than 2^64 MAC 
values (Let's say each MAC value is 96 bits), I have many collided MAC pairs. 
But, I am the only one (beside the person(s) verifying my MACs) who knows the 
MAC key in order to generate those  verified MAC values.


If the MAC length is k bits, an attacker is allowed to send 2^n failed 
verifications, his or her chance of success is approximately 2^n / 2^k. Let's 
imagine n is 64 and k is 96, the success chance is 1/2^36 which is practically 
ZERO!


If I am an attacker, I would choose a message that I want to be verified, and I 
keep changing the MAC key to generate different MAC values with different keys 
and hope one of them will get verified.  Let's assume the MAC key to be 96 bits 
( 96 bits of random bits, the other 32 bits are known). In theory, when I get 
close to 2^96 attempts, I would expect some chance of success. To deal with 
this attacker, one would change the MAC key when the number of failed attempts 
gets close to a number that you don't want. For example, if you don't want a 
success chance of an attack to be above 1 / 2^36, then you need to change your 
MAC key when the number of failed verifications reaches 2^64 when your MAC 
length is 96 bits.


After you change the MAC key, I ( the attacker) will have to start everything 
again because all of the failed MACs I generated before are useless now.


From: Watson Ladd 
Sent: Monday, November 2, 2015 5:07 AM
To: Dang, Quynh
Cc: tls@ietf.org; c...@ietf.org; Eric Rescorla
Subject: Re: [Cfrg] Collision issue in ciphertexts.


On Nov 2, 2015 2:14 AM, "Dang, Quynh" 
mailto:quynh.d...@nist.gov>> wrote:
>
> Hi Eric,
>
>
> As you asked the question about how many ciphertext blocks should be safe 
> under a single key, I think it is safe to have 2^96 blocks under a given key 
> if the IV (counter) is 96 bits.

This is wrong for PRP, right for PRF. It's not that hard to find the right 
result.

>
>
> When there is a collision between two ciphertext blocks when two different 
> counter values are used , the chance of the same plaintext was used twice is 
> 1^128.  Collisions start to happen a lot when the number of ciphertext blocks 
> are above 2^64. However, each collision just reveals that the corresponding 
> plaintext blocks are probably different ones.

Which breaks IND-$. Let's not be clever, but stick to ensuring proven 
definitions are true.

>
>
>
> Quynh.
>
>
> ___
> Cfrg mailing list
> c...@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>
___
TLS mailing list
TLS@ietf.org
https://www.ietf.org/mailman/listinfo/tls