Subject: [TLS] Proposal: Simplified Key Schedule

From: Eric Rescorla <[email-masked]>
Date: Thu, 18 Feb 2016 14:05:24 -0700

Hi folks,

TL;DR.
Let's simplify the key schedule.

DETAILS
This is the second in a series of proposed simplifications to TLS 1.3
based on implementation experience and analysis once the protocol
starts to harden.  The following suggestion comes out of conversations
with Richard Barnes, Karthik Bhargavan, Antoine Delignat-Lavaud,
Cedric Fournet, Markus Kohlweiss, Martin Thomson, Santiago Zanella and
others.

The current key schedule is elegant but it is actually more than we
need in that it allows SS to be known either before or after ES. If we
assume (as is always true in the current TLS 1.3 modes) that SS is
known before or at the same time as ES, then we can design a simpler
scheme which looks more like a ladder. Something like:

                        0
                        |
                 SS -> HKDF [ClientHello + Context]
                        |  \
                        |   \
                        v    v
                        X1   0-RTT Traffic Keys *
                        |
                        |
                        v
                 ES -> HKDF [ClientHello, ServerHello]
                        |  \
                        |   \
                        v    v
                        X2    1-RTT Traffic Keys *
                        |
                        |
                        v
                  0 -> HKDF [ClientHello...ClientFinished]
                        |
                        |
                        v
                        RMS, EMS

As should be apparent, this key schedule is well-suited to the
simplified key change schedule in my previous message.

Note 1: It might be attractive to not even bother with the first stage
if you aren't doing 0-RTT. It's not necessary then.  However, this is
just an optimization. Also, if you don't want to extract an RMS or an
EMS you can skip the last stage (this is compatible).

Note 2: The IKM for the final HKDF is 0, but in principle we could use
it to add some sort of new keying material, for instance g^xs if we
were using static DH certificates (see below).

In line with Hugo's message earlier today, the major argument against
this design is that it is more oriented towards a signature-based
system, which TLS 1.3 is today, than towards a DH certificate-based
system. To elaborate on this a bit, in a DH certificate-based system,
the server authenticates by proving knowledge of g^xs (and hence
s). In the current TLS 1.3 design you can do this trivially by
replacing the signature in the server CertificateVerify with a MAC
over the transcript (using g^xs as the key) [again, analysis needed.]
This is straightforward and doesn't require rearchitecting the
protocol really at all. However, this (as with the current
signature-based mode) does not provide confidentiality of the
connection if y is later revealed.

As Hugo has noted several times, if you mix both g^xy and g^xs into
the traffic keys, then you are protected if either y or s is leaked,
which gives you somewhat stronger security properties with a DH
cetificate The current key schedule accommodates that by allowing for
SS to come before *or* after ES, but the simplified schedule does not
quite so easily.

With that said, TLS 1.3 doesn’t support *any* pure static DH design
now and will do so even less well if we remove the key change as
discussed above. There are at least three ways forward to incorporate
them in future:

- Just do as I suggest above.
- Define a new DH cipher suite that adds an additional key change.
  This would allow us only to have the key change complexity in
  that mode.
- Replace the 0 in the above schedule with g^xs and then define that
  the key for KeyUpdate is actually coming out of the final HKDF.

Any of those seem like they wouldn’t be too hard to do, if and when
we start having a lot of demand for DH certificates.

Please discuss.

-Ekr

* Note that as I indicated in my previous message, it is possible to
generate multiple sets of keys at the same stage, if that is necessary
to handle the analysis concerns.

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 18 Feb 2016 22:20:04 -0500

I agree that once you remove the requirement to derive a key from g^xy (=ES)
for protecting a static DH key then the KDF scheme can be simplified as
shown
(or even further - see below).

Note that this is (almost) exactly the original KDF scheme of OPTLS as I
presented in Dallas
https://www.ietf.org/proceedings/92/slides/slides-92-tls-4.pdf
See slide 4 for the KDF scheme and slide 3 for the key names; it can be
confusing as what I call ES (for Ephemeral-Static, or g^xs) is now called
SS and what I call EE (for Ephemeral-Ephemeral, or g^xy) is now called ES.
Also note that I simplified the presentation in these slides by referring to
both HKDF-extract and HKDF-expand by PRF.

Anyway, from here you can see that the last HKDF in your scheme (with 0
salt)
is not needed. You can derive the RMS, EMS keys directly from the second
HKDF
(as siblings of 1-RTT Traffic Keys). Am I missing something?
If the third HKDF is only to accommodate a DH-cert variant then I don't
think
it's worth it (if in that variant we will need a special key derivation
step
anyway then no need to plan for it now).
If this third HKDF is needed for other reasons let me know.

What I do miss in this scheme is the derivation of the Finished keys. I hope
you do not intend to use the application key for this!

I also want to stress, for the record, that this simplification has nothing
to
do with using the application keys for handshake protection. That
"optimization"
is orthogonal to this KDF simplification and hopefully will be reverted (*).

(*) You may say I'm a dreamer, But I may not be the only one :-)

Hugo

PS: I have a disagreement with you in terms of the protocol now being
"signature based". Yes there are signatures in the protocol but not all
modes
use them and they are not always needed. In my eyes the logic of the
protocol
is best seen as DH-based with authentication occurring through the server
Finished MAC (with a key derived from SS which can take the values of g^xs,
g^xy or PSK). That is common to *all* modes, including 0-RTT and PSK which
do
not build on signatures. This is how the protocol was built originally and
that structure remains in spite of the added signatures.

On Thu, Feb 18, 2016 at 4:05 PM, Eric Rescorla <[email-masked]> wrote:

> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>
>

---

From: Karthikeyan Bhargavan <[email-masked]>
Date: Fri, 19 Feb 2016 10:12:09 +0100

> Note that this is (almost) exactly the original KDF scheme of OPTLS as I

Indeed, Ekr’s proposed scheme looks much like you original diagram.

> Anyway, from here you can see that the last HKDF in your scheme (with 0 salt)
> is not needed. You can derive the RMS, EMS keys directly from the second HKDF

The purpose of the third HKDF is to bind the handshake context (the full transcript) into
the resumption and exporter keys. It adds no new key material.

> you do not intend to use the application key for this!

Indeed those are missing in the picture, but I believe Ekr means to derive separate
finished keys alongside the 1-RTT Traffic keys (right after the ServerHello)

> I also want to stress, for the record, that this simplification has nothing to
> do with using the application keys for handshake protection.

I agree, this key schedule simplification seems orthogonal.
For what it’s worth, I am building a symbolic model of this new key schedule and will
report my analysis results at TRON. It’s not a cryptographic proof, but it should shake
out early logical bugs in the design, if any.

Best,
Karthik

> That "optimization"
> "signature based". Yes there are signatures in the protocol but not all modes
> use them and they are not always needed. In my eyes the logic of the protocol
> g^xy or PSK). That is common to *all* modes, including 0-RTT and PSK which do
> On Thu, Feb 18, 2016 at 4:05 PM, Eric Rescorla <[email-masked] <mailto:[email-masked]>> wrote:
> Hi folks,
> 
> TL;DR.
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/tls <https://www.ietf.org/mailman/listinfo/tls>
> 
>

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 19 Feb 2016 07:14:44 -0700

> Indeed, Ekr’s proposed scheme looks much like you original diagram.

I would like to clarify that this isn't *my* scheme, though I think it's a
good
one. It came out of a long discussion with the people listed in my original
message and probably is most closely derived from something Karthik
drew. Sorry if I gave an impression to the contrary!

In any case, I'm glad to see that it's close to Hugo's original diagram,
since that's a good indication that we're on the right track!

> the resumption and exporter keys. It adds no new key material.

Yes, that was my understanding as well. I see that Ilari suggested that
this might
not be necessary (presumably as a consequence of having the full shares
included in the stage 2 transcript rather than just the nonces as in TLS
1.2.
The imperative here is to avoid creating an attack like triple handshake or
the Cremers et al. attack on the PSK-resumption. In any case, having the
EMS and RMS keys derived at the end also helps enforce the logic that you
should never be exporting/resuming until you have actually completed the
handshake.

> finished keys alongside the 1-RTT Traffic keys (right after the

Affirmative. Error in my diagram.

> I agree, this key schedule simplification seems orthogonal.

Yes, but... In the current 1-RTT mode, there is a derivation stage
that does not appear on this diagram, one that includes the transcript up
to the
server CertificateVerify and is used to derive the application traffic
keys. So,
if part of the intent of this diagram is to reduce the number of points at
which
we derive, we will need to derive the application traffic keys at stage 2
even if they are separate from the handshake traffic keys. I believe this
something you proposed, but I just want to clarify that this diagram would
entail
a change in the timing of key derivation, even if not the number of keys.

> Nothing to be reverted yet, it's just a proposal. If it's a bad idea (and
being prohibitively
hard to analyze is one reason it might be) then we shouldn't adopt it.

Hugo
> that structure remains in spite of the added signatures.
Sorry about the misleading terminology. I just meant that it presently has
signatures.
I'll try to be more precise in future.

-Ekr

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 19 Feb 2016 20:07:29 +0200

> should never be exporting/resuming until you have actually completed the

To be clear, RMS needs to include some data in "flight 3", so the most
straightforward is to take the hash to be ClientHello1...ClientFinished.

EMS needs to be secret and nonce versus ES and SS (otherwise you can get
Triple-Handshake-style attacks). And one can compute such values
immediately after ServerHello in main modes.

However, given that some more "exotic" modes might have attacks all the
way into ClientFinished, it would be good idea to take the EMS hash to
ClientFinished too.

Taking EMS to ClientFinished would prevent server from computing
authenticators immediately after getting into application data, but
usually those kinds of authenticators are used client-first so it won't
matter much.

And authentication TBS need to be nonce versus ES and SS. TBS failing to
be nonce with SS is what led to Cremers attack.

Also, where things can also get scary is server authentication. Whereas
with client auth, the TBS should become nonce versus SS via Server-
Finished, there is nothing corresponding for server authentication
(this is not problem in GDHE-CERT w/o Config because SS=ES, and TBS
is nonce versus ES).

There are some subtle caveats tho: In practicular, the HKDF salt needs
to be constant-length or one can obtain trivial collisions in HKDF. So
one can't feed raw SS as salt (but must extract it first).

> Affirmative. Error in my diagram.

There's question about if to use ES+SS or just SS. One of those might
make proofs of some kind easier, dunno.
 
> hard to analyze is one reason it might be) then we shouldn't adopt it.

I don't find it prohibitively hard (or even hard) to analyze unless
you get thigns like configurations or future modes involved.

(And I think one would get similar problems before the simplication
too).

-Ilari

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 19 Feb 2016 14:34:43 -0500

Couple of comments below.

>> the resumption and exporter keys. It adds no new key material.
​I am still confused about this. Call K the key output by the Extract part
of the second HKDF​

​.
You derive 1-RTT Traffic Keys as an output from Expand(K, whatever).
Why can't you use the same K to derive RMS and EMS?
Namely,
 compute RMS=Expand(K, label="RMS Derivation",
ClientHello....ClientFinished)​.
​Similarly for EMS.
This would include all the information you wanted in the derivation of each
key,
and it is still a valid HKDF computation (namely, it goes through extract
and expand).
Am I missing something?

> hard to analyze is one reason it might be) then we shouldn't adopt it.

​It complicates analysis, breaks generality and modularity, weakens the
security guarantee,
but d
efinitely not "
​
prohibitively
​ ​
hard to analyze​".

​Hugo
​