Subject: Re: [TLS] Data volume limits

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 28 Dec 2015 20:51:01 +0000

When too much plaintext has been encrypted with the same key, the key needs to be changed. When the key is changed, the change procedure should involve new randomness. 

What's the confusion here???

Sent from my BlackBerry 10 smartphone on the Verizon Wireless 4G LTE network.
From: Eric Rescorla
Sent: Monday, December 28, 2015 15:47
To: Blumenthal, Uri - 0553 - MITLL
Cc: Florian Weimer; [email-masked]
Subject: Re: [TLS] Data volume limits

To be clear, the concern that we are trying to alleviate is encrypting too much plaintext with the
same key (see the discussion by Watson at the beginning of this thread). For that purpose,
I'm not following why we need to introduce new randomness (draft-11 doesn't do so,
but just cranks the KDF forward).

It's possible I've misunderstood something, though, so happy to be corrected.

-Ekr

On Mon, Dec 28, 2015 at 3:40 PM, Blumenthal, Uri - 0553 - MITLL <[email-masked]> wrote:
Off-hand, key update or re-key without new/fresh‎ randomness sounds weird.

Sent from my BlackBerry 10 smartphone on the Verizon Wireless 4G LTE network.
From: Eric Rescorla
Sent: Monday, December 28, 2015 15:37
To: Florian Weimer
Cc: [email-masked]
Subject: Re: [TLS] Data volume limits

On Mon, Dec 28, 2015 at 3:33 PM, Florian Weimer <[email-masked]> wrote:
On 12/28/2015 09:11 PM, Eric Rescorla wrote:

>> You still have the added complexity that during rekey, you need to
>> temporarily switch from mere sending or receiving to at least
>> half-duplex interaction.
>>
>
> That's not intended. Indeed, you need to be able to handle the old key
> in order to send/receive the KeyUpdate. Can you elaborate on your concern?

Ah, so you want to keep the current mechanism and not inject fresh
randomness?  Isn't this fairly risky?

Can you explain the risk you are concerned about in more detail?

-Ekr

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 28 Dec 2015 22:56:10 +0200

On Mon, Dec 28, 2015 at 08:51:01PM +0000, Blumenthal, Uri - 0553 - MITLL wrote:
> When too much plaintext has been encrypted with the same key, the
> key needs to be changed. When the key is changed, the change
> procedure should involve new randomness. 
> 

OTOH, you can't drop an attacker knowing older key without doing
new key exchange.

Introducing new randomness would complicate the rekeying _greatly_
as now you need to handle synchronization (which also causes nasty
problems at application layer). So one wouldn't want to do that
without really good reason.

Breaking the symmetry between rekeyings (including the rekey counter
in key derivation) might be feasible tho.

-Ilari

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 28 Dec 2015 21:09:42 +0000

> When the key is changed, the change procedure should involve new randomness. 

I don't think this is necessary, and I don't think the common crypto expertise agrees with you, either. But I am not a cryptographer, maybe one of the ones on this list can chime in.

"Crank the KDF" suffices.

---

From: Brian Smith <[email-masked]>
Date: Tue, 29 Dec 2015 09:10:25 -1000

> OTOH, you can't drop an attacker knowing older key without doing

I think it would be very unfortunate to have the complexity of key update
(the new keys are derived from the old keys) without having the benefits of
rekeying (the new keys are independent of the old keys).

Note that NIST Special Publication 800-133 [1] defines these separate
terms, and I suggest we use them in this conversation to avoid confusion:

Key update: A procedure in which a new cryptographic key is computed as a
function of the (old) cryptographic key that it will replace.

Rekey: A procedure in which a new cryptographic key is generated in a
manner that is independent of the (old) cryptographic key that it will
replace.

[1] http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-133.pdf
.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 29 Dec 2015 14:33:38 -0500

> rekeying (the new keys are independent of the old keys).

Note: the keys here are *not* derived from the old keys. Rather, they are
derived via
a KDF from the same secret that was used to generate the old keys. I.e.,

  K_send_0 = KDF(MK_0, <label1>)
  K_recv_0 = KDF(MK_0, <label2>)
  MK_1 = KDF(MK_0, <label3>)
  K_send_1 = KDF(MK_1, <label1>)
  K_recv_1 = KDF(MK_1, <label2>)

> manner that is independent of the (old) cryptographic key that it will

Hmm... It seems to me that there are three (at least) three separate
possible designs:

1. Generate the new keys by a new application of the KDF with no additional
inputs.
2. Generate the new keys by a new application of the KDF with additional
random inputs.
3. Generate the new keys by a new PK key exchange (potentially also using
the old
    keys and new random inputs).

These all have different security properties and it's not clear to me which
buckets
these fall into.

As far as complexity goes, 3 is more complicated than 2 which is more
complicated than 1.

-Ekr

---

From: Dave Garrett <[email-masked]>
Date: Tue, 29 Dec 2015 17:08:46 -0500

> [1] http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-133.pdf

The current spec mostly uses the former, so yes, I guess we really should stop saying "rekey" if this has been defined like this. The single use of "rekey" in the doc should probably be changed to "key update" if we keep things as-is, then.

On Tuesday, December 29, 2015 02:33:38 pm Eric Rescorla wrote:
> Note: the keys here are *not* derived from the old keys. Rather, they are derived via
> a KDF from the same secret that was used to generate the old keys.

Yes, but they are derived from the same entropy as the old keys. Yes, that's not the same thing, but they're not totally independent new keys either. If we're only doing this as a hack to fix ciphers that have problems (that really should just be fixed instead), then this is fine. I think it's just the fact that we _could_ add a full rekey mechanism without a fantastic amount of additional effort is what's giving some people pause.

If what we're really talking about is AES-GCM's data volume limits, what would be the best fix that just deals with precisely its issue, rather than doing a key update?

> 1. Generate the new keys by a new application of the KDF with no additional inputs.
> 2. Generate the new keys by a new application of the KDF with additional random inputs.
> 3. Generate the new keys by a new PK key exchange (potentially also using the old
> These all have different security properties and it's not clear to me which buckets
> these fall into.
> 

From a certain perspective, doing a full new (EC)DHE with new randoms for a full rekey is less of a change to the spec than a simple key update or something in between. It is somewhat akin to a stripped-down version of renegotiation to just renegotiate the ephemeral key, but not any of the other parameters. I think it's worth considering, but I don't know if we absolutely need something here at all.

Dave

---

From: Eric Rescorla <[email-masked]>
Date: Tue, 29 Dec 2015 18:11:02 -0500

On Tue, Dec 29, 2015 at 5:08 PM, Dave Garrett <[email-masked]>
wrote:

> > [1]
> http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-133.pdf
>
> The current spec mostly uses the former, so yes, I guess we really should
> stop saying "rekey" if this has been defined like this. The single use of
> "rekey" in the doc should probably be changed to "key update" if we keep
> things as-is, then.

Maybe. I don't find this taxonomy particularly evocative.

> Yes, but they are derived from the same entropy as the old keys.

Yes. I didn't say otherwise.

> Yes, that's not the same thing, but they're not totally independent new
> keys either. If we're only doing this as a hack to fix ciphers that have
> problems (that really should just be fixed instead), then this is fine. I
> think it's just the fact that we _could_ add a full rekey mechanism without
> a fantastic amount of additional effort is what's giving some people pause.
>

Well, i don't know what "fantastic" means here, but we did look at this
prior
to designing the present mechanism and it was a nontrivial amount of
additional complexity.

-Ekr