Subject: [TLS] Collision issue in ciphertexts.

From: "Dang, Quynh" <[email-masked]>
Date: Mon, 2 Nov 2015 07:13:39 +0000

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.

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.

Quynh.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 2 Nov 2015 05:07:45 -0500

On Nov 2, 2015 2:14 AM, "Dang, Quynh" <[email-masked]> 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
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Dang, Quynh" <[email-masked]>
Date: Mon, 2 Nov 2015 20:00:27 +0000

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 <[email-masked]>
Sent: Monday, November 2, 2015 5:07 AM
To: Dang, Quynh
Cc: [email-masked]; [email-masked]; Eric Rescorla
Subject: Re: [Cfrg] Collision issue in ciphertexts.

> 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…

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

> [email-masked]<mailto:[email-masked]>

---

From: "Dang, Quynh" <[email-masked]>
Date: Wed, 4 Nov 2015 19:29:55 +0000

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: [email-masked]; [email-masked]; Eric Rescorla
Subject: Re: [Cfrg] Collision issue in ciphertexts.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 4 Nov 2015 15:17:00 -0500

On Wed, Nov 4, 2015 at 2:29 PM, Dang, Quynh <[email-masked]> 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.
>
>
>
>
> 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.
>
>
>> 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.
>
>> 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.
>
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

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

---

From: "Dang, Quynh" <[email-masked]>
Date: Wed, 4 Nov 2015 20:43:15 +0000

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

Quynh.
________________________________________
From: Watson Ladd <[email-masked]>
Sent: Wednesday, November 4, 2015 3:17:00 PM
To: Dang, Quynh
Cc: Eric Rescorla; [email-masked]
Subject: Re: [TLS] Data limit for GCM under a given key.

---

From: Watson Ladd <[email-masked]>
Date: Fri, 6 Nov 2015 19:27:52 -0500

> 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?

---

From: Tony Arcieri <[email-masked]>
Date: Fri, 6 Nov 2015 16:59:08 -0800

On Friday, November 6, 2015, Watson Ladd <[email-masked]> wrote:

> On Wed, Nov 4, 2015 at 3:43 PM, Dang, Quynh <[email-masked]
> <javascript:;>> wrote:
> > I did not talk  under indistinguishability framework. My discussion was
> about confidentiality protection and authentication.
>

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

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 6 Nov 2015 17:13:44 -0800

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

---

From: Dave Garrett <[email-masked]>
Date: Fri, 6 Nov 2015 21:39:10 -0500

> 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

---

From: Yoav Nir <[email-masked]>
Date: Sat, 7 Nov 2015 12:46:18 +0900

> On 7 Nov 2015, at 11:39 AM, Dave Garrett <[email-masked]> wrote:
> 

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

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 6 Nov 2015 19:50:03 -0800

On Fri, Nov 6, 2015 at 7:46 PM, Yoav Nir <[email-masked]> wrote:

> > 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).
>

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

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 6 Nov 2015 19:54:02 -0800

> 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

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 6 Nov 2015 19:59:48 -0800

On Fri, Nov 6, 2015 at 7:50 PM, Eric Rescorla <[email-masked]> wrote:

>> > 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).
>>

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

---

From: Dave Garrett <[email-masked]>
Date: Fri, 6 Nov 2015 23:21:44 -0500

> situation specific rather than derived from reasoning about the properties

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

---

From: "Dang, Quynh" <[email-masked]>
Date: Sat, 7 Nov 2015 05:07:43 +0000

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 <[email-masked]>
Sent: Friday, November 6, 2015 7:59 PM
To: Watson Ladd
Cc: Dang, Quynh; [email-masked]
Subject: Re: [TLS] Data limit for GCM under a given key.

On Friday, November 6, 2015, Watson Ladd <[email-masked]<mailto:[email-masked]>> wrote:

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

---

From: Quynh Dang <[email-masked]>
Date: Sat, 7 Nov 2015 16:16:09 +0900

Hi Eric and Watson,

> given algorithm (where safe is defined by an analysis like the one Watson

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).

>> Do we want forward secrecy so another diffie-hellamn exchange?

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.

---

From: Yoav Nir <[email-masked]>
Date: Sat, 7 Nov 2015 19:38:45 +0100

> On 7 Nov 2015, at 12:50 PM, Eric Rescorla <[email-masked]> wrote:
> 
> 
> 
> On Fri, Nov 6, 2015 at 7:46 PM, Yoav Nir <[email-masked] <mailto:[email-masked]>> wrote:
> 
> > On 7 Nov 2015, at 11:39 AM, Dave Garrett <[email-masked] <mailto:[email-masked]>> wrote:
> >
> 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

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