Subject: [TLS] AdditionalKeyShare Internet-Draft

From: Douglas Stebila <[email-masked]>
Date: Mon, 17 Apr 2017 14:23:32 -0400

Dear TLS mailing list,

We have posted an Internet-Draft
    https://tools.ietf.org/html/draft-schanck-tls-additional-keyshare-00
for using an additional key share in TLS 1.3.  The intended use case is to
provide support for transitional key exchange mechanisms in which both a
pre-quantum algorithm (e.g., ECDH) and a post-quantum algorithm are used.
(Google's experiment with New Hope in 2016 had such an arrangement.) Our draft
replicates the functionality of the KeyShare extension in a new extension called
AdditionalKeyShare. Like KeyShare, the client's AdditionalKeyShare contains a
vector of KeyShareEntry structs. The server can respond with a single matching
KeyShareEntry in the AdditionalKeyShare extension of its ServerHello. The
resulting additional shared secret is included in the TLS key schedule after the
ECDH shared secret.

While the motivation for our Internet-Draft is to facilitate the transition to
post-quantum algorithms, our Internet-Draft does not specify any post-quantum
algorithms.

There are a couple of items for discussion related to this draft:

- We only provide a mechanism for a single AdditionalKeyShare, thus leading to
  the session establishing at most PSK + ECDHE + 1 additional shared secret.  Is
  there a value in even more shared secrets than that?  Will someone want
  to include more than one post-quantum algorithm?  If so, our draft could be
  adapted to have AdditionalKeyShare1, AdditionalKeyShare2, etc., but we did not
  want to add that complexity unless there was desire for it.

- TLS 1.3 allows the client to restrict the use of PSKs that they provide in
  ClientHello through the "psk_key_exchange_modes" extension. The client may,
  for instance, request that the PSK only be used in a PSK+(EC)DHE mode, so as
  to ensure that the resumed session has forward secrecy.  It is unclear the
  best way to reconcile this with support for multiple key shares; we outline
  some possibilities in Section 4 of our Internet-Draft, and we welcome input.

We have also created a pull request to TLS 1.3 draft 19 which includes a
clarification on how additional secrets are to be included in the TLS key
schedule.
    https://github.com/jschanck/tls13-spec

John and Douglas

---

From: David Benjamin <[email-masked]>
Date: Mon, 17 Apr 2017 19:14:26 +0000

This seems overly complicated. Why implement a parallel key share mechanism
rather than merely defining a new NamedGroup value?

Using your example of Google's recent New Hope experiment, I would imagine
defining, say, NamedGroup.cecpq1. Let its key_shares be the concatenation
of New Hope and X25519 public values, and let the resulting shared secret
be some combination of the two resulting keys.

This avoids changing the key schedule or protocol logic and slots in nicely
into the existing arrangement. The AdditionalKeyShare proposal has more
moving parts and combinatorial combinations to test and worry about. It
also requires implementations answer silly questions like:
- What happens the server selects two New Hopes with no X25519? X25519 and
P-256 together?
- What happens if the client offers New Hope in the normal key shares slot
and X25519 in the additional one?
- What happens if the client only offers New Hope and not X25519?
- How does a client express that it's not willing to do New Hope without
ECDH? What if the server sends a HelloRetryRequest for New Hope in the main
slot and does not select X25519?
- How can I plausibly expose this complex array of options to the consumer
of my TLS library?

David

On Mon, Apr 17, 2017 at 2:23 PM Douglas Stebila <[email-masked]> wrote:

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

---

From: Douglas Stebila <[email-masked]>
Date: Mon, 17 Apr 2017 15:44:47 -0400

Hi David,

Thanks for the feedback.

> This seems overly complicated. Why implement a parallel key share mechanism rather than merely defining a new NamedGroup value?
> 
> Using your example of Google's recent New Hope experiment, I would imagine defining, say, NamedGroup.cecpq1. Let its key_shares be the concatenation of New Hope and X25519 public values, and let the resulting shared secret be some combination of the two resulting keys.
> 
> This avoids changing the key schedule or protocol logic and slots in nicely into the existing arrangement. The AdditionalKeyShare proposal has more moving parts and combinatorial combinations to test and worry about.

Defining combined NamedGroups, like in the Google New Hope experiment, also incurs a combinatorial explosion, this time in the number of NamedGroups.  Given that TLS 1.3 has taken the approach of splitting off each component of a TLS 1.2 ciphersuite into its own negotiable component to avoid combinatorial explosion in standardized values, separately negotiating each parallel key share mechanism seemed to us to follow the TLS 1.3 design approach.

> It also requires implementations answer silly questions like:
> - What happens the server selects two New Hopes with no X25519? X25519 and P-256 together?

In our draft, KeyShare and AdditionalKeyShare form disjoint pools of NamedGroups from which one element can be selected.  If the client offers say P256 and X5519 in KeyShare and NewHope in its AdditionalKeyShare, your first problem cannot happen.  If the client offers NewHope in both pools, then the situation you propose could happen.  This does not negatively impact compatibility or security, although there is obviously no value in doing two NewHopes compared to a single NewHope.  I don't think we've put in a MUST NOT/SHOULD NOT here, but we could add that.

> - What happens if the client offers New Hope in the normal key shares slot and X25519 in the additional one?

This is fine from the draft's perspective.  If the client does so and then interacts with a non-NewHope-compatible server that only speaks X25519, the connection would fail because the KeyShare slot contains no mutually compatible key shares.

> - How does a client express that it's not willing to do New Hope without ECDH?  What if the server sends a HelloRetryRequest for New Hope in the main slot and does not select X25519?

The server must pick exactly one NamedGroup from the KeyShare pool, and at most one NamedGroup from the AdditionalKeyShare pool.  The client could put ECDH in KeyShare and NewHope in AdditionalKeyShare to indicate this desire; the server would then have to use ECDH from the KeyShare slot and could optionally use NewHope from the AdditionalKeyShare slot.

If the client wants "ECDH (KeyShare) and NewHope (AdditionalKeyShare)" and the server says "retry with NewHope (KeyShare)", the client has the option of retrying with "NewHope (KeyShare) and ECDH (AdditionalKeyShare)".  If the server rejects, then the client knows its policy cannot be satisfied, and it should not continue.  If the server continues with NewHope but discards the AdditionalKeyShare (as it's allowed to do in our draft), the client learns the server is unwilling to satisfy its policy, and the client can drop the connection.

> - How can I plausibly expose this complex array of options to the consumer of my TLS library?

Yes, there is a complex array of options:
- which algorithm(s) the client views as "must have"
- which algorithm(s) the client views as "would like to have"
- which algorithm(s) should/should not happen at the same time

If this functionality is encapsulated anywhere in TLS, then that complexity needs to incorporated somewhere, either already in compound NamedGroups or in configuration of the parallel key share mechanism.  As I mentioned above, we thought that combinatorial explosion of NamedGroups was not the TLS 1.3 way.  However, we are open to considering that if there's a clear preference for it.

Douglas

> 
> 
> On Mon, Apr 17, 2017 at 2:23 PM Douglas Stebila <[email-masked] <mailto:[email-masked]>> wrote:
> Dear TLS mailing list,
> 
>     https://tools.ietf.org/html/draft-schanck-tls-additional-keyshare-00 <https://tools.ietf.org/html/draft-schanck-tls-additional-keyshare-00>
>     https://github.com/jschanck/tls13-spec <https://github.com/jschanck/tls13-spec>
> 
> John and Douglas
> 
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/tls <https://www.ietf.org/mailman/listinfo/tls>

---

From: Benjamin Kaduk <[email-masked]>
Date: Mon, 17 Apr 2017 15:14:27 -0500

On 04/17/2017 02:44 PM, Douglas Stebila wrote:
> Hi David,
>
> Thanks for the feedback.
>
>> This seems overly complicated. Why implement a parallel key share
>> mechanism rather than merely defining a new NamedGroup value?
>>
>> Using your example of Google's recent New Hope experiment, I would
>> imagine defining, say, NamedGroup.cecpq1. Let its key_shares be the
>> concatenation of New Hope and X25519 public values, and let the
>> resulting shared secret be some combination of the two resulting keys.
>>
>> This avoids changing the key schedule or protocol logic and slots in
>> nicely into the existing arrangement. The AdditionalKeyShare proposal
>> has more moving parts and combinatorial combinations to test and
>> worry about.
>
> Defining combined NamedGroups, like in the Google New Hope experiment,
> also incurs a combinatorial explosion, this time in the number of
> NamedGroups.  Given that TLS 1.3 has taken the approach of splitting
> off each component of a TLS 1.2 ciphersuite into its own negotiable
> component to avoid combinatorial explosion in standardized values,
> separately negotiating each parallel key share mechanism seemed to us
> to follow the TLS 1.3 design approach.
>

You only get the combinatorial explosion if you let it happen.  A lot of
the possible combinations wouldn't make much sense, and would not need
to be defined.  TLS 1.3 also tries to limit the possible combinations in
some aspects, presenting just a few good choices with clear trade-offs.

> In our draft, KeyShare and AdditionalKeyShare form disjoint pools of
> NamedGroups from which one element can be selected.  If the client
> offers say P256 and X5519 in KeyShare and NewHope in its
> AdditionalKeyShare, your first problem cannot happen.  If the client
> offers NewHope in both pools, then the situation you propose could
> happen.  This does not negatively impact compatibility or security,
> although there is obviously no value in doing two NewHopes compared to
> a single NewHope.  I don't think we've put in a MUST NOT/SHOULD NOT
> here, but we could add that.
>

That's pushing complexity from the spec into implementations; we have a
lot of evidence to suggest that not all implementations will get it right.

> If this functionality is encapsulated anywhere in TLS, then that
> complexity needs to incorporated somewhere, either already in compound
> NamedGroups or in configuration of the parallel key share mechanism.
>  As I mentioned above, we thought that combinatorial explosion of
> NamedGroups was not the TLS 1.3 way.  However, we are open to
> considering that if there's a clear preference for it.
>

I would rather leave the complexity in the NamedGroups registry.

-Ben

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 17 Apr 2017 16:30:50 -0400

I agree with David here. ISTM that if we discover that this is turning a
lot of problems,
we can presumably add an extension like the one proposed here at some later
point.

-Ekr

On Mon, Apr 17, 2017 at 4:14 PM, Benjamin Kaduk <[email-masked]> wrote:

> nicely into the existing arrangement. The AdditionalKeyShare proposal has
> more moving parts and combinatorial combinations to test and worry about.
>
>
> NamedGroups.  Given that TLS 1.3 has taken the approach of splitting off
> each component of a TLS 1.2 ciphersuite into its own negotiable component
> to avoid combinatorial explosion in standardized values, separately
> negotiating each parallel key share mechanism seemed to us to follow the
> TLS 1.3 design approach.
>
>
> the possible combinations wouldn't make much sense, and would not need to
> be defined.  TLS 1.3 also tries to limit the possible combinations in some
> aspects, presenting just a few good choices with clear trade-offs.
>
> NamedGroups from which one element can be selected.  If the client offers
> say P256 and X5519 in KeyShare and NewHope in its AdditionalKeyShare, your
> first problem cannot happen.  If the client offers NewHope in both pools,
> then the situation you propose could happen.  This does not negatively
> impact compatibility or security, although there is obviously no value in
> doing two NewHopes compared to a single NewHope.  I don't think we've put
> in a MUST NOT/SHOULD NOT here, but we could add that.
>
>
> NamedGroups or in configuration of the parallel key share mechanism.  As I
> mentioned above, we thought that combinatorial explosion of NamedGroups was
> not the TLS 1.3 way.  However, we are open to considering that if there's a
> clear preference for it.
>
>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Wed, 19 Apr 2017 18:42:58 +0000

> -----Original Message-----
> From: TLS [mailto:[email-masked]] On Behalf Of Douglas Stebila
> Sent: Monday, April 17, 2017 2:24 PM
> To: <[email-masked]>
> Subject: [TLS] AdditionalKeyShare Internet-Draft
> 
> Dear TLS mailing list,
> 
> (Google's experiment with New Hope in 2016 had such an arrangement.) Our
> draft replicates the functionality of the KeyShare extension in a new
> extension called AdditionalKeyShare. Like KeyShare, the client's
> AdditionalKeyShare contains a vector of KeyShareEntry structs. The server
> can respond with a single matching KeyShareEntry in the AdditionalKeyShare
> extension of its ServerHello. The resulting additional shared secret is included
> in the TLS key schedule after the ECDH shared secret.
> 
> post-quantum algorithms, our Internet-Draft does not specify any post-
> quantum algorithms.

We have a draft with similar goals; draft-whyte-qsh-tls13 .  It also tries to achieve Quantum-safeness through multiple key exchange mechanisms; however in terms of protocol, it works somewhat differently.  You have the 'normal' key exchange (as exists in the protocol), and a second one on the side.  We allows the client to define a hybrid group (which consists of several key exchanges done in parallel).  One of our goals was to stay within the existing TLS architecture as much as possible (and thus limiting the changes needed to the TLS state machine and parsing logic); things such as modifying the key derivation mechanism (such as you do) were considered to be too large.

It may be worth your while to go through our draft,,,

>   want to add that complexity unless there was desire for it.

Our draft allows for that naturally.

As for the need, well, I expect that some will want it.  We don't have any postquantum key exchanges that are both practical and really well trusted (at least, to the same extent that (EC)DH is); I would expect that some people will want to spread their risk and do (for example) x25519 + Frodo + SIDH.

---

From: William Whyte <[email-masked]>
Date: Thu, 20 Apr 2017 13:08:00 -0400

Link to that draft: https://tools.ietf.org/html/draft-whyte-qsh-tls13-02

Cheers,

William

On Wed, Apr 19, 2017 at 2:42 PM, Scott Fluhrer (sfluhrer) <
[email-masked]> wrote:

> We have a draft with similar goals; draft-whyte-qsh-tls13 .  It also tries
> to achieve Quantum-safeness through multiple key exchange mechanisms;
> however in terms of protocol, it works somewhat differently.  You have the
> 'normal' key exchange (as exists in the protocol), and a second one on the
> side.  We allows the client to define a hybrid group (which consists of
> several key exchanges done in parallel).  One of our goals was to stay
> within the existing TLS architecture as much as possible (and thus limiting
> the changes needed to the TLS state machine and parsing logic); things such
> as modifying the key derivation mechanism (such as you do) were considered
> to be too large.
>
> > - We only provide a mechanism for a single AdditionalKeyShare, thus
> leading
> > to
> As for the need, well, I expect that some will want it.  We don't have any
> postquantum key exchanges that are both practical and really well trusted
> (at least, to the same extent that (EC)DH is); I would expect that some
> people will want to spread their risk and do (for example) x25519 + Frodo +
> SIDH.
>
> >
> >   for instance, request that the PSK only be used in a PSK+(EC)DHE mode,
> so
> > as

---

From: William Whyte <[email-masked]>
Date: Thu, 20 Apr 2017 13:33:35 -0400

Sorry! Link to the most recent version... https://tools.ietf.org/html/
draft-whyte-qsh-tls13-04

William

On Thu, Apr 20, 2017 at 1:08 PM, William Whyte <[email-masked]>
wrote:

>> We have a draft with similar goals; draft-whyte-qsh-tls13 .  It also
>> tries to achieve Quantum-safeness through multiple key exchange mechanisms;
>> As for the need, well, I expect that some will want it.  We don't have
>> any postquantum key exchanges that are both practical and really well
>> trusted (at least, to the same extent that (EC)DH is); I would expect that
>> some people will want to spread their risk and do (for example) x25519 +
>> Frodo + SIDH.
>>
>> >
>> >   for instance, request that the PSK only be used in a PSK+(EC)DHE
>> mode, so
>> > as