Subject: [TLS] Options for negotiating hybrid key exchanges for postquantum

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 30 Jul 2019 15:21:05 +0000

During the physical meeting in Montreal, we had a discussion about postquantum security, and in particular, on how one might want to negotiate several different 'groups' simultaneously (because there might not be one group that is entirely trusted, and I put 'groups' in scarequotes because postquantum key exchanges are typically not formed from a Diffie-Hellman group).

At the meeting, there were two options presented:

Option 1: as the supported group, we insert a 'hybrid marker' (and include an extension that map lists which combination the hybrid marker stands for)
                For example, the client might list in his supported groups hybrid_marker_0 and hybrid_marker_1, and there would be a separate extension that lists hybrid_marker_0 = X25519 + SIKEp434 and hybrid_marker_1 = X25519 + NTRUPR653.  The server would then look up the meanings of hybrid_marker_0 and 1 in the extension, and then compare that against his security policy.
In this option, we would ask IANA to allocate code points for the various individual postquantum key exchanges (in this example, SIKEp434 and NTRUPR653), as well a range of code points for the various hybrid_markers.

Option 2: we have code points for all the various combinations that we may want to support; hence IANA might allocate a code point X25519_SIKEp434 and another code point for X25519_NTRUPR653.  With this option, the client would list X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups.
                In this option, we would ask IANA to allocate code points for all the various combinations that we want allow to be negotiated.

I would like to make an argument in favor of option 1:

  *   It is likely that not everyone will be satisified with "X25519 plus one of a handful of specific postquantum algorithms"; some may prefer another elliptic curve (for example, x448), or perhaps even a MODP group; I have talked to people who do not trust ECC); in addition, other people might not trust a single postquantum algorithm, and may want to rely on both (for example) SIKE and NewHope (which are based on very different hard problems).  With option 2, we could try to anticipate all the common combintations (such as P384_SIKEp434_NEWHOPE512CCA), however that could very well end up as a lot of combinations.
  *   There are likely to be several NIST-approved postquantum key exchanges, and each of those key exchanges are likely to have a number of supported parameter sets (if we take the specific postquantum key exchange as analogous to th ECDH protocool, the "parameter set" could be thought of an analogous to the specific elliptuc curve, and it modifies the key share size, the performance and sometimes the security properties).  In fact, one of the NIST submissoins currently has 30 parameter sets defined.  Hence, even if NIST doesn't approve all the parameter sets (or some of them do not make sense for TLS in any scenario), we might end up with 20 or more different key exchange/parameter set combinations that do make sense for some scenario that uses tLS (be it in a tranditional PC client/server, a wireless client, two cloud devices communicating or an IOT device).
  *   In addition, we are likely to support additional primitives in the future; possibly National curves (e.g. Brainpool), or additional Postquantum algorithms (or additional parameter sets to existing ones).  Of course, once we add that code point, we'll need to add the additional code points for all the combinations that it'll make sense in (very much like we had to add a number of ciphersuites whenever we added a new encryption algorithm into TLS 1.2).

It seemds reasonable to me that the combination of these two factors are likely to cause us (should we select option 2) to define a very large number of code points to cover all the various options that people need.

Now, this is based on speculation (both of the NIST process, and additional primitives that will be added to the protocol), and one objection I've heard is "we don't know what's going to happen, and so why would we make decisions based on this speculation?"  I agree that we have lack of knowledge; however it seems to me that a lack of knowledge is an argument in favor of selecting the more flexible option (which, in my opinion, is option 1, as it allows the negotiation of combinations of key exchanges that the WG has not anticipated).

My plea: lets not repeat the TLS 1.2 ciphersuite mess; lets add an extension that keeps the number of code points we need to a reasonable bound.

The costs of option 1?

  *   It does increase the complexity on the server a small amount (I'm not a TLS implementor, however it would seem to me to be only a fairly small amount)
  *   It may increase the size of the client hello a small amount (on the other hand, because it allows us to avoid sending duplicate key shares, it can also reduce the size of the client hello as well, depending on what's actually negotiated)
IMHO, the small increase in complexity is worth the lack of complexity in the code point table, and the additional flexibility it gives.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 30 Jul 2019 09:17:57 -0700

On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) <[email-masked]>
wrote:

> During the physical meeting in Montreal, we had a discussion about
> postquantum security, and in particular, on how one might want to negotiate
> several different ‘groups’ simultaneously (because there might not be one
> group that is entirely trusted, and I put ‘groups’ in scarequotes because
> postquantum key exchanges are typically not formed from a Diffie-Hellman
> group).
>
>
>
> Option 1: as the supported group, we insert a ‘hybrid marker’ (and include
> an extension that map lists which combination the hybrid marker stands for)
>
>                 For example, the client might list in his supported groups
> hybrid_marker_0 and hybrid_marker_1, and there would be a separate
> extension that lists hybrid_marker_0 = X25519 + SIKEp434 and
> hybrid_marker_1 = X25519 + NTRUPR653.  The server would then look up the
> meanings of hybrid_marker_0 and 1 in the extension, and then compare that
> against his security policy.
>
> In this option, we would ask IANA to allocate code points for the various
> individual postquantum key exchanges (in this example, SIKEp434 and
> NTRUPR653), as well a range of code points for the various hybrid_markers.
>

>
> Option 2: we have code points for all the various combinations that we may
> want to support; hence IANA might allocate a code point X25519_SIKEp434 and
> another code point for X25519_NTRUPR653.  With this option, the client
> would list X25519_SIKEp434 and X25519_NTRUPR653 in their supported groups.
>
>                 In this option, we would ask IANA to allocate code points
> for all the various combinations that we want allow to be negotiated.
>
>
>
>    - It is likely that not everyone will be satisified with “X25519 plus
>    one of a handful of specific postquantum algorithms”; some may prefer
>    another elliptic curve (for example, x448), or perhaps even a MODP group; I
>    have talked to people who do not trust ECC); in addition, other people
>    might not trust a single postquantum algorithm, and may want to rely on
>    both (for example) SIKE and NewHope (which are based on very different hard
>    problems).  With option 2, we could try to anticipate all the common
>    combintations (such as P384_SIKEp434_NEWHOPE512CCA), however that could
>    very well end up as a lot of combinations.
>    - There are likely to be several NIST-approved postquantum key
>    exchanges, and each of those key exchanges are likely to have a number of
>    supported parameter sets (if we take the specific postquantum key exchange
>    as analogous to th ECDH protocool, the “parameter set” could be thought of
>    an analogous to the specific elliptuc curve, and it modifies the key share
>    size, the performance and sometimes the security properties).  In fact, one
>    of the NIST submissoins currently has 30 parameter sets defined.  Hence,
>    even if NIST doesn’t approve all the parameter sets (or some of them do not
>    make sense for TLS in any scenario), we might end up with 20 or more
>    different key exchange/parameter set combinations that do make sense for
>    some scenario that uses tLS (be it in a tranditional PC client/server, a
>    wireless client, two cloud devices communicating or an IOT device).
>    - In addition, we are likely to support additional primitives in the
>    future; possibly National curves (e.g. Brainpool), or additional
>    Postquantum algorithms (or additional parameter sets to existing ones).  Of
>    course, once we add that code point, we’ll need to add the additional code
>    points for all the combinations that it’ll make sense in (very much like we
>    had to add a number of ciphersuites whenever we added a new encryption
>    algorithm into TLS 1.2).
>
>
>

Are people actually going to use hybrid encryption post NIST? The actual
deployments today  for experiment have all fit option 2 and hybrids are
unlikely in the future.

My objection to 1 is it gets very messy. Do we use only the hybrids we both
support? What if I throw a bunch of expensive things together? No reason we
need a hybrid scheme!

It seemds reasonable to me that the combination of these two factors are
> likely to cause us (should we select option 2) to define a very large
> number of code points to cover all the various options that people need.
>
>
>
> Now, this is based on speculation (both of the NIST process, and
> additional primitives that will be added to the protocol), and one
> objection I’ve heard is “we don’t know what’s going to happen, and so why
> would we make decisions based on this speculation?”  I agree that we have
> lack of knowledge; however it seems to me that a lack of knowledge is an
> argument in favor of selecting the more flexible option (which, in my
> opinion, is option 1, as it allows the negotiation of combinations of key
> exchanges that the WG has not anticipated).
>
>
>
> My plea: lets not repeat the TLS 1.2 ciphersuite mess; lets add an
> extension that keeps the number of code points we need to a reasonable
> bound.
>
>
>
> The costs of option 1?
>
>    - It does increase the complexity on the server a small amount (I’m
>    not a TLS implementor, however it would seem to me to be only a fairly
>    small amount)
>    - It may increase the size of the client hello a small amount (on the
>    other hand, because it allows us to avoid sending duplicate key shares, it
>    can also reduce the size of the client hello as well, depending on what’s
>    actually negotiated)
>
> IMHO, the small increase in complexity is worth the lack of complexity in
> the code point table, and the additional flexibility it gives.
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: David Benjamin <[email-masked]>
Date: Tue, 30 Jul 2019 14:23:43 -0400

I think this underestimates the complexity cost of option 1 to the protocol
and implementations. Option 1 means group negotiation includes entire
codepoints whose meaning cannot be determined without a parallel extension.
This compounds across everything which interacts with named groups,
impacting everything from APIs to config file formats to even UI surfaces.
Other uses of NamedGroups are impacted too. For instance, option 2 fits
into draft-ietf-tls-esni as-is. Option 1 requires
injecting hybrid_extension into ESNI somehow. Analysis must further check
every use, say, incorporates this parallel lookup table into
transcript-like measures.

The lesson from TLS 1.2 code points is not combined codepoints vs. split
ones. Rather, the lesson is to avoid interdependent decisions:

* Signature algorithms in TLS 1.2 were a mess because the ECDSA codepoints
required cross-referencing against the supported curves list. The verifier
could not express some preferences (signing SHA-512 with P-256 is silly,
and mixing hash+curve pairs in ECDSA is slightly off in general). As
analogy to option 1's ESNI problem, we even forgot to allow the server to
express curve preferences. TLS 1.3 combined signature algorithm
considerations into a single codepoint to address all this.

* Cipher suites in TLS 1.2 were a mess because they were half-combined and
half-split. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 said to use some ECDHE
key exchange, but you need to check if you have a NamedGroup in common
first. It said to use ECDSA, but you need to check signature algorithms
(which themselves cross-reference curves) first. Early drafts of TLS 1.3
had it even worse, where a TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 full
handshake morphed into TLS_ECDHE_PSK_WITH_AES_128_GCM_SHA256 on resumption.
Thus, TLS 1.3 cipher suites negotiate solely AEAD + PRF hash.

In fairness to TLS 1.2, some of this was a consequence of TLS 1.2's
evolution over time as incremental extensions over SSL 3.0. And sometimes
we do need to pay costs like these. But hybrid key exchanges fit into the
NamedGroup "API" just fine, so option 2 is the clear answer. Code points
are cheap. Protocol complexity is much more expensive.

It's true that standards are often underspecified. This means the IETF
should finish the job, not pass all variations through. RSA-PSS is a clear
example of what to avoid. It takes more bytes to merely utter "RSA-PSS with
SHA-256 and usual parameters" in X.509 than to encode an entire ECDSA
signature! We should not define more than a handful of options, regardless
of the encoding.

On Tue, Jul 30, 2019 at 12:18 PM Watson Ladd <[email-masked]> wrote:

>> Option 1: as the supported group, we insert a ‘hybrid marker’ (and
>> include an extension that map lists which combination the hybrid marker
>> stands for)
>>
>>                 For example, the client might list in his supported
>> groups hybrid_marker_0 and hybrid_marker_1, and there would be a separate
>> Option 2: we have code points for all the various combinations that we
>> may want to support; hence IANA might allocate a code point X25519_SIKEp434
>> and another code point for X25519_NTRUPR653.  With this option, the client
> My objection to 1 is it gets very messy. Do we use only the hybrids we
> both support? What if I throw a bunch of expensive things together? No
> reason we need a hybrid scheme!
>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 30 Jul 2019 18:41:39 +0000

From: Watson Ladd <[email-masked]> 

> On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) <mailto:[email-masked]> wrote:
>> During the physical meeting in Montreal, we had a discussion about postquantum security, and in particular, on how one might want to negotiate several different ‘groups’ simultaneously (because there might not be one group that is entirely trusted, and I put ‘groups’ in scarequotes because postquantum key exchanges are typically not formed from a Diffie-Hellman group).
>> 
 >> 
>> Option 1: as the supported group, we insert a ‘hybrid marker’ (and include an extension that map lists which combination the hybrid marker stands for)
 >>
> Are people actually going to use hybrid encryption post NIST? The actual deployments today  for experiment have all fit option 2 and hybrids are unlikely in the future. 

it sounds like you are questioning, not between option 1 or option 2, but instead whether we need either of them at all.  Those are both methods of negotiating multiple keygroups; it appears that you don’t see any need for such an option.

Perhaps we need to have such a debate.  Here is one opinion (mine, but I'm pretty sure it is shared by others): the various NIST candidates are based on hard problems that were only recently studied (e.g. supersingular isogenies, Quasicyclic codes), or have cryptanalytic methods that are quite difficult to fully assess (e.g. Lattices).  Even after NIST and CFRG have blessed one or more of them, it would seem reasonable to me that we wouldn't want to place all our security eggs in that one basket.  We currently place all our trust in DH or ECDH; however those have been studied for 30+ years - we are not there yet for most of the postquantum algorithms.

Hence, it seems reasonable to me that we give users the option of being able to rely on multiple methods.

>
> My objection to 1 is it gets very messy. Do we use only the hybrids we both support? What if I throw a bunch of expensive things together? No reason we need a hybrid scheme! 

Actually, I personally don't see the messiness; if the client wants to propose X25519 + NTRUPR653, he places hybrid_marker_1 in the supported groups list, and adds hybrid_marker_1 = X25519 + NTRUPR653 to his hybrid group extension.  If the server sees hybrid_marker_1 in the client's supported group list, he looks for the definition in the hybrid group extension, and processes the policy accordingly.  The logic in both direction would appear (at least to me) to be reasonably simple (and it doesn’t get more complex if we feel the need to negotiate three or more key exchanges).

As for the expense, that is for the user to judge.  If the user decides that he is willing to pay for a series of expensive key exchanges, that should be his decision to make.  Option 1 gives the user the ability to negotiate a series of expensive (but perhaps more trusted) algorithms, it doesn't mandate that the user do so.

And, as for a need for a hybrid scheme (either option 1, option 2 or something else), I do believe that there will be a demand for it, even after NIST and CFRG has given their blessing, as their will be users who will not fully trust a new scheme that was just endorsed (but they do want some protection against future quantum computers).

---

From: Andrei Popov <[email-masked]>
Date: Tue, 30 Jul 2019 18:48:09 +0000

Given these options, I also prefer option 2, for some of the same reasons.

For my understanding though, why not have the client advertise support for hybrid-key-exchange (e.g. via a “flag” extension) and then KeyShareServerHello can contain two KeyShareEntries (essentially, using the same format as KeyShareClientHello? This would solve the Cartesian product issue.

Cheers,

Andrei

From: TLS <[email-masked]> On Behalf Of David Benjamin
Sent: Tuesday, July 30, 2019 11:24 AM
To: Watson Ladd <[email-masked]>
Cc: TLS List <[email-masked]>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

I think this underestimates the complexity cost of option 1 to the protocol and implementations. Option 1 means group negotiation includes entire codepoints whose meaning cannot be determined without a parallel extension. This compounds across everything which interacts with named groups, impacting everything from APIs to config file formats to even UI surfaces. Other uses of NamedGroups are impacted too. For instance, option 2 fits into draft-ietf-tls-esni as-is. Option 1 requires injecting hybrid_extension into ESNI somehow. Analysis must further check every use, say, incorporates this parallel lookup table into transcript-like measures.

The lesson from TLS 1.2 code points is not combined codepoints vs. split ones. Rather, the lesson is to avoid interdependent decisions:

* Signature algorithms in TLS 1.2 were a mess because the ECDSA codepoints required cross-referencing against the supported curves list. The verifier could not express some preferences (signing SHA-512 with P-256 is silly, and mixing hash+curve pairs in ECDSA is slightly off in general). As analogy to option 1's ESNI problem, we even forgot to allow the server to express curve preferences. TLS 1.3 combined signature algorithm considerations into a single codepoint to address all this.

* Cipher suites in TLS 1.2 were a mess because they were half-combined and half-split. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 said to use some ECDHE key exchange, but you need to check if you have a NamedGroup in common first. It said to use ECDSA, but you need to check signature algorithms (which themselves cross-reference curves) first. Early drafts of TLS 1.3 had it even worse, where a TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 full handshake morphed into TLS_ECDHE_PSK_WITH_AES_128_GCM_SHA256 on resumption. Thus, TLS 1.3 cipher suites negotiate solely AEAD + PRF hash.

In fairness to TLS 1.2, some of this was a consequence of TLS 1.2's evolution over time as incremental extensions over SSL 3.0. And sometimes we do need to pay costs like these. But hybrid key exchanges fit into the NamedGroup "API" just fine, so option 2 is the clear answer. Code points are cheap. Protocol complexity is much more expensive.

It's true that standards are often underspecified. This means the IETF should finish the job, not pass all variations through. RSA-PSS is a clear example of what to avoid. It takes more bytes to merely utter "RSA-PSS with SHA-256 and usual parameters" in X.509 than to encode an entire ECDSA signature! We should not define more than a handful of options, regardless of the encoding..

On Tue, Jul 30, 2019 at 12:18 PM Watson Ladd <[email-masked]<mailto:[email-masked]>> wrote:

On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) <[email-masked]<mailto:[email-masked]>> wrote:
During the physical meeting in Montreal, we had a discussion about postquantum security, and in particular, on how one might want to negotiate several different ‘groups’ simultaneously (because there might not be one group that is entirely trusted, and I put ‘groups’ in scarequotes because postquantum key exchanges are typically not formed from a Diffie-Hellman group).

  *   It is likely that not everyone will be satisified with “X25519 plus one of a handful of specific postquantum algorithms”; some may prefer another elliptic curve (for example, x448), or perhaps even a MODP group; I have talked to people who do not trust ECC); in addition, other people might not trust a single postquantum algorithm, and may want to rely on both (for example) SIKE and NewHope (which are based on very different hard problems).  With option 2, we could try to anticipate all the common combintations (such as P384_SIKEp434_NEWHOPE512CCA), however that could very well end up as a lot of combinations.
  *   There are likely to be several NIST-approved postquantum key exchanges, and each of those key exchanges are likely to have a number of supported parameter sets (if we take the specific postquantum key exchange as analogous to th ECDH protocool, the “parameter set” could be thought of an analogous to the specific elliptuc curve, and it modifies the key share size, the performance and sometimes the security properties).  In fact, one of the NIST submissoins currently has 30 parameter sets defined.  Hence, even if NIST doesn’t approve all the parameter sets (or some of them do not make sense for TLS in any scenario), we might end up with 20 or more different key exchange/parameter set combinations that do make sense for some scenario that uses tLS (be it in a tranditional PC client/server, a wireless client, two cloud devices communicating or an IOT device).
  *   In addition, we are likely to support additional primitives in the future; possibly National curves (e.g. Brainpool), or additional Postquantum algorithms (or additional parameter sets to existing ones).  Of course, once we add that code point, we’ll need to add the additional code points for all the combinations that it’ll make sense in (very much like we had to add a number of ciphersuites whenever we added a new encryption algorithm into TLS 1.2).

Now, this is based on speculation (both of the NIST process, and additional primitives that will be added to the protocol), and one objection I’ve heard is “we don’t know what’s going to happen, and so why would we make decisions based on this speculation?”  I agree that we have lack of knowledge; however it seems to me that a lack of knowledge is an argument in favor of selecting the more flexible option (which, in my opinion, is option 1, as it allows the negotiation of combinations of key exchanges that the WG has not anticipated).

The costs of option 1?

  *   It does increase the complexity on the server a small amount (I’m not a TLS implementor, however it would seem to me to be only a fairly small amount)
  *   It may increase the size of the client hello a small amount (on the other hand, because it allows us to avoid sending duplicate key shares, it can also reduce the size of the client hello as well, depending on what’s actually negotiated)
IMHO, the small increase in complexity is worth the lack of complexity in the code point table, and the additional flexibility it gives.
_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=02%7C01%7CAndrei.Popov%40microsoft.com%7C8b45740f081f44820a4c08d7151b30e3%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637001079003849042&sdata=swB52kH%2Fx7DvLNaX9EAyHcNf7VuiXRRUsx%2Ftdn0e1S4%3D&reserved=0>
_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=02%7C01%7CAndrei.Popov%40microsoft.com%7C8b45740f081f44820a4c08d7151b30e3%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637001079003859035&sdata=OHEwC6itmwbrqT1TpByKoytOuhKOIghix7SzMkPdXvQ%3D&reserved=0>

---

From: David Benjamin <[email-masked]>
Date: Tue, 30 Jul 2019 14:59:21 -0400

The nuisance with just a flag is the client can't express [what I think
are] reasonable preferences. It should be able to say things like:

* Don't do X25519 + P-256. This is just silly.
* Don't do PQ1 on its own. I really want the PQ scheme paired with
something more established.
* Don't do PQ1 + PQ2. I said something more established, please.
* PQ1 + X25519 is cool. I like that combo.
* Don't do PQ1 + X25519 + P-256. Why are you doing three of these?
* Don't do PQ1 + PQ2 + PQ3 + PQ4 + X25519 + P-256 + P-384 + FFDHE2048 +
FFDHE3072, oww my head.

We can make things implicit by categorizing named groups and building all
this into the protocol itself, but I think that's an unnecessary moving
part.

On Tue, Jul 30, 2019 at 2:48 PM Andrei Popov <[email-masked]>
wrote:

> For my understanding though, why not have the client advertise support for
> hybrid-key-exchange (e.g. via a “flag” extension) and then
> KeyShareServerHello can contain two KeyShareEntries (essentially, using the
> same format as KeyShareClientHello? This would solve the Cartesian product
> issue.
>
>
>
> Cheers,
>
>
>
> Andrei
>
>
>
> *From:* TLS <[email-masked]> *On Behalf Of * David Benjamin
> *Sent:* Tuesday, July 30, 2019 11:24 AM
> *To:* Watson Ladd <[email-masked]>
> *Cc:* TLS List <[email-masked]>
> *Subject:* Re: [TLS] Options for negotiating hybrid key exchanges for
> postquantum
>
>
>
> I think this underestimates the complexity cost of option 1 to the
> protocol and implementations. Option 1 means group negotiation includes
> entire codepoints whose meaning cannot be determined without a parallel
> extension. This compounds across everything which interacts with named
> groups, impacting everything from APIs to config file formats to even UI
> surfaces. Other uses of NamedGroups are impacted too. For instance, option
> 2 fits into draft-ietf-tls-esni as-is. Option 1 requires
> of the encoding..
> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=02%7C01%7CAndrei.Popov%40microsoft.com%7C8b45740f081f44820a4c08d7151b30e3%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637001079003849042&sdata=swB52kH%2Fx7DvLNaX9EAyHcNf7VuiXRRUsx%2Ftdn0e1S4%3D&reserved=0>
>
> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=02%7C01%7CAndrei.Popov%40microsoft.com%7C8b45740f081f44820a4c08d7151b30e3%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637001079003859035&sdata=OHEwC6itmwbrqT1TpByKoytOuhKOIghix7SzMkPdXvQ%3D&reserved=0>
>
>

---

From: Andrei Popov <[email-masked]>
Date: Tue, 30 Jul 2019 19:09:39 +0000

Yes, I see your point WRT clients expressing preferences.

Regardless of the protocol option we choose, I anticipate some difficulty in agreeing on what’s “reasonable”.
E.g. I’ve had several customers ask about the possibility of combining a couple of traditional algorithms (e.g. national vanity + NIST).
Some of them ended up doing TLS-in-TLS, which of course only works between their particular clients and servers.

From: David Benjamin <[email-masked]>
Sent: Tuesday, July 30, 2019 11:59 AM
To: Andrei Popov <[email-masked]>
Cc: Watson Ladd <[email-masked]>; TLS List <[email-masked]>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

The nuisance with just a flag is the client can't express [what I think are] reasonable preferences. It should be able to say things like:

* Don't do X25519 + P-256. This is just silly.
* Don't do PQ1 on its own. I really want the PQ scheme paired with something more established.
* Don't do PQ1 + PQ2. I said something more established, please.
* PQ1 + X25519 is cool. I like that combo.
* Don't do PQ1 + X25519 + P-256. Why are you doing three of these?
* Don't do PQ1 + PQ2 + PQ3 + PQ4 + X25519 + P-256 + P-384 + FFDHE2048 + FFDHE3072, oww my head.

We can make things implicit by categorizing named groups and building all this into the protocol itself, but I think that's an unnecessary moving part.

On Tue, Jul 30, 2019 at 2:48 PM Andrei Popov <[email-masked]<mailto:[email-masked]>> wrote:
Given these options, I also prefer option 2, for some of the same reasons.

Cheers,

Andrei

From: TLS <[email-masked]<mailto:[email-masked]>> On Behalf Of David Benjamin
Sent: Tuesday, July 30, 2019 11:24 AM
To: Watson Ladd <[email-masked]<mailto:[email-masked]>>
Cc: TLS List <[email-masked]<mailto:[email-masked]>>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

The costs of option 1?

  *   It does increase the complexity on the server a small amount (I’m not a TLS implementor, however it would seem to me to be only a fairly small amount)
  *   It may increase the size of the client hello a small amount (on the other hand, because it allows us to avoid sending duplicate key shares, it can also reduce the size of the client hello as well, depending on what’s actually negotiated)
IMHO, the small increase in complexity is worth the lack of complexity in the code point table, and the additional flexibility it gives.
_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=02%7C01%7CAndrei.Popov%40microsoft.com%7C6d168181e330430452f108d715201216%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637001099808056548&sdata=0Irv6k3NLggUZHMmxupaFmWiBpeECXQ2nDZNPmG1L78%3D&reserved=0>
_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=02%7C01%7CAndrei.Popov%40microsoft.com%7C6d168181e330430452f108d715201216%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637001099808066546&sdata=EXrNFZJ7fvjkfIxjIUrMSZ2jsoRPDMwNAQm85bJusnQ%3D&reserved=0>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Tue, 30 Jul 2019 19:12:15 +0000

Offhand, I don’t see at all why the client should be able to say any of these “don’t”s:

This is the only thing that IMHO the client should be able to say:

 

On Tue, Jul 30, 2019 at 2:48 PM Andrei Popov <[email-masked]> wrote:

Cheers,

Andrei

On Tue, Jul 30, 2019, 8:21 AM Scott Fluhrer (sfluhrer) <[email-masked]> wrote:

·         It is likely that not everyone will be satisified with “X25519 plus one of a handful of specific postquantum algorithms”; some may prefer another elliptic curve (for example, x448), or perhaps even a MODP group; I have talked to people who do not trust ECC); in addition, other people might not trust a single postquantum algorithm, and may want to rely on both (for example) SIKE and NewHope (which are based on very different hard problems).  With option 2, we could try to anticipate all the common combintations (such as P384_SIKEp434_NEWHOPE512CCA), however that could very well end up as a lot of combinations.

·         There are likely to be several NIST-approved postquantum key exchanges, and each of those key exchanges are likely to have a number of supported parameter sets (if we take the specific postquantum key exchange as analogous to th ECDH protocool, the “parameter set” could be thought of an analogous to the specific elliptuc curve, and it modifies the key share size, the performance and sometimes the security properties).  In fact, one of the NIST submissoins currently has 30 parameter sets defined.  Hence, even if NIST doesn’t approve all the parameter sets (or some of them do not make sense for TLS in any scenario), we might end up with 20 or more different key exchange/parameter set combinations that do make sense for some scenario that uses tLS (be it in a tranditional PC client/server, a wireless client, two cloud devices communicating or an IOT device).

·         In addition, we are likely to support additional primitives in the future; possibly National curves (e.g. Brainpool), or additional Postquantum algorithms (or additional parameter sets to existing ones).  Of course, once we add that code point, we’ll need to add the additional code points for all the combinations that it’ll make sense in (very much like we had to add a number of ciphersuites whenever we added a new encryption algorithm into TLS 1.2).

The costs of option 1?

·         It does increase the complexity on the server a small amount (I’m not a TLS implementor, however it would seem to me to be only a fairly small amount)

·         It may increase the size of the client hello a small amount (on the other hand, because it allows us to avoid sending duplicate key shares, it can also reduce the size of the client hello as well, depending on what’s actually negotiated)

---

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Tue, 30 Jul 2019 19:36:23 +0000

+1 for option 2. The combinatoric explosion and complexity of 1 is unnecessary. I expect that just a few, conservative, acceptably efficient, classical+PQ combinations need to be standardized and used. Combining a classical algo with more than one postquantum algorithms in a key exchange does not seem practical based on the PQ candidates key sizes and performance.

Panos

From: TLS <[email-masked]> On Behalf Of Scott Fluhrer (sfluhrer)
Sent: Tuesday, July 30, 2019 11:21 AM
To: <[email-masked]> <[email-masked]>
Subject: [TLS] Options for negotiating hybrid key exchanges for postquantum

The costs of option 1?

---

From: Andrei Popov <[email-masked]>
Date: Tue, 30 Jul 2019 19:41:49 +0000

Sure, hybrid-key-exchange “flag” extension is too generic. We could have the client advertise something like one-traditional-and-one-PQ, and still avoid the Cartesian product.
From: TLS <[email-masked]> On Behalf Of Blumenthal, Uri - 0553 - MITLL
Sent: Tuesday, July 30, 2019 12:12 PM
To: David Benjamin <[email-masked]>
Cc: TLS List <[email-masked]>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

Cheers,

Andrei

It's true that standards are often underspecified. This means the IETF should finish the job, not pass all variations through. RSA-PSS is a clear example of what to avoid. It takes more bytes to merely utter "RSA-PSS with SHA-256 and usual parameters" in X.509 than to encode an entire ECDSA signature! We should not define more than a handful of options, regardless of the encoding...

The costs of option 1?

https://www.ietf.org/mailman/listinfo/tls<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=02%7C01%7CAndrei.Popov%40microsoft.com%7C46fca7fab91c4d875c3c08d71521f413%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637001107919064706&sdata=CnZ1NqUcQSIE8RqnpPF8jY0oNp%2FF%2BgbI7jWB7RaLsrA%3D&reserved=0>
https://www.ietf.org/mailman/listinfo/tls<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=02%7C01%7CAndrei.Popov%40microsoft.com%7C46fca7fab91c4d875c3c08d71521f413%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637001107919064706&sdata=CnZ1NqUcQSIE8RqnpPF8jY0oNp%2FF%2BgbI7jWB7RaLsrA%3D&reserved=0>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 30 Jul 2019 19:44:13 +0000

I believe that one important property (of either of the options I listed) is a nice fallback if an enhanced client talks to an older server.  In both cases, the server will see a series of named groups that it doesn’t know (which it will ignore), and possibility an extension it doesn’t know (which it will ignore); the server will accept either a named group that it does understand (if the client did propose a traditional group as a fall back), or it will come to the correct conclusion that the two sides have no mutually acceptable security policy.

It is not clear if the proposal you outlined share this property; do you duplicate a payload that an unenhanced server would assume only occurs once?

From: TLS <[email-masked]> On Behalf Of Andrei Popov
Sent: Tuesday, July 30, 2019 2:48 PM
To: David Benjamin <[email-masked]>; Watson Ladd <[email-masked]>
Cc: TLS List <[email-masked]>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

Cheers,

Andrei

The costs of option 1?

---

From: Andrei Popov <[email-masked]>
Date: Tue, 30 Jul 2019 19:51:13 +0000

> It is not clear if the proposal you outlined share this property; do you duplicate a payload that an unenhanced server would assume only occurs once?
I think this property is preserved: only a server that knows the hybrid-key-exchange extension (or perhaps, a more specific one-traditional-and-one-PQ extension) will send KeyShareServerHello with two KeyShareEntries.
An “unenhanced” server will send only one KeyShareEntry. We’d need to think about how the “enhanced” client can distinguish the two KeyShareServerHello formats, but there are easy solutions to this, I think.

From: Scott Fluhrer (sfluhrer) <[email-masked]>
Sent: Tuesday, July 30, 2019 12:44 PM
To: Andrei Popov <[email-masked]>; David Benjamin <[email-masked]>; Watson Ladd <[email-masked]>
Cc: TLS List <[email-masked]>
Subject: RE: [TLS] Options for negotiating hybrid key exchanges for postquantum

From: TLS <[email-masked]<mailto:[email-masked]>> On Behalf Of Andrei Popov
Sent: Tuesday, July 30, 2019 2:48 PM
To: David Benjamin <[email-masked]<mailto:[email-masked]>>; Watson Ladd <[email-masked]<mailto:[email-masked]>>
Cc: TLS List <[email-masked]<mailto:[email-masked]>>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

Cheers,

Andrei

The costs of option 1?

  *   It does increase the complexity on the server a small amount (I’m not a TLS implementor, however it would seem to me to be only a fairly small amount)
  *   It may increase the size of the client hello a small amount (on the other hand, because it allows us to avoid sending duplicate key shares, it can also reduce the size of the client hello as well, depending on what’s actually negotiated)
IMHO, the small increase in complexity is worth the lack of complexity in the code point table, and the additional flexibility it gives.
_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=02%7C01%7CAndrei.Popov%40microsoft.com%7C341e473b6a4b474a3aba08d715265328%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637001126663608127&sdata=jJdB9kWPfARYg6B7iiHNZk3cu3Oeg5m9iIYKZrKeOpA%3D&reserved=0>
_______________________________________________
TLS mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/tls<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.ietf.org%2Fmailman%2Flistinfo%2Ftls&data=02%7C01%7CAndrei.Popov%40microsoft.com%7C341e473b6a4b474a3aba08d715265328%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637001126663618124&sdata=EpI7O%2BKzbwpOMrhxDq6VPm0ruyq5K4u7dw4fs%2FSuoSQ%3D&reserved=0>

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 30 Jul 2019 20:52:56 +0100

I'm neutral as to how we represent this stuff for the moment
as I think it's too early to tell until we get closer to the
end of the algorithms competition.

That said, I do want to second this...

On 30/07/2019 19:41, Scott Fluhrer (sfluhrer) wrote:
> Here is one opinion (mine, but I'm pretty sure it is shared by
> others): the various NIST candidates are based on hard problems that
> were only recently studied (e.g. supersingular isogenies, Quasicyclic
> codes), or have cryptanalytic methods that are quite difficult to
> fully assess (e.g. Lattices).  Even after NIST and CFRG have blessed
> one or more of them, it would seem reasonable to me that we wouldn't
> want to place all our security eggs in that one basket.  We currently
> place all our trust in DH or ECDH; however those have been studied
> for 30+ years - we are not there yet for most of the postquantum
> algorithms.
> 
The only person with whom I've spoken who said he'd plan to
deploy some of this soon is a VPN operator who explicitly
wanted to start early and use >1 PQ scheme (3-4 is what he
said) plus a current scheme. His expectation was that that'd
settle down to one PQ scheme, or one PQ and a current one,
in time, but that time may be a decade after he'd like to
start.

So, to the extent it matters, count me as a +1 for supporting
that.

Cheers,
S.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 30 Jul 2019 13:03:09 -0700

> end of the algorithms competition.

Part of the input being provided is deployability experiments happening now
in TLS.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 30 Jul 2019 20:19:59 +0000

> -----Original Message-----
> From: Stephen Farrell <[email-masked]>
> Sent: Tuesday, July 30, 2019 3:53 PM
> To: Scott Fluhrer (sfluhrer) <[email-masked]>; Watson Ladd
> <[email-masked]>
> I'm neutral as to how we represent this stuff for the moment as I think it's
> too early to tell until we get closer to the end of the algorithms competition.

I'm of the opposite opinion; I think it is important to get this settled before (or at the time) the algorithm competition ends.  I really wouldn't want to see us wait for NIST to settle on (say) SIKE and NewHope, and then have us spend another year or two debating on how to integrate them into our protocols.  Instead, I would rather spend the year or two now (when we're not on the critical path).

Now, there are certainly things we don't know yet about the results of the competition (how many algorithms, what types of parameter sets, what sizes of key shares do they have); however (based on the current round 2 submissions) we can certainly have some informed suspicions...

> > place all our trust in DH or ECDH; however those have been studied for
> > 30+ years - we are not there yet for most of the postquantum
> > algorithms.
> >
> The only person with whom I've spoken who said he'd plan to deploy some
> of this soon is a VPN operator who explicitly wanted to start early and use >1
> PQ scheme (3-4 is what he
> said) plus a current scheme. His expectation was that that'd settle down to
> one PQ scheme, or one PQ and a current one, in time, but that time may be a
> decade after he'd like to start.
> 
> So, to the extent it matters, count me as a +1 for supporting that.
> 
> Cheers,
> S.

---

From: Benjamin Kaduk <[email-masked]>
Date: Tue, 30 Jul 2019 15:20:24 -0500

> It is not clear if the proposal you outlined share this property; do you duplicate a payload that an unenhanced server would assume only occurs once?

It's clear that anything we do needs to preserve compat with all four
possibilities in the interop matrix for (old, enhanced) (client,
server).  Your closing note about duplicating payloads is something of a
different creature, though, and perhaps should be considered more
explicitly.

Trying to uplevel a bit, option 1 is essentially introducing another
layer of indirection, with the need to carry the additional lookup table
on the side.  This has the disadvantages of both needing the extra layer
of indirection and also can have unfortunate impact from needing the
extra table on the side in more places than is immediately obvious
(i.e., the ESNI case that David mentioned).  The perceived benefit is
that we allocate fewer codepoints, avoid duplicating some KeyShare
information, and maybe get increased flexibility about how we combine
schemes.  In contrast, option 2 is more smoothly integrated into the
existing negotiation mechanism, but has the potential costs of allocating
more codepoints and duplicating some KeyShare information.

But, what are the KeyShare bits that will get duplicated?  If we're just
doing "X25519 plus one post-quantum", only the X25519 share gets
duplicated, even if we want to do several different post-quantum options
in "X25519 plus one post-quantum" form.  And X25519 shares are pretty
small, all things considered!  I'd find the concern about duplicated
KeyShares more compelling if we think we're going to end up needing to
negotiate between (X25519 plus PQ1 plus PQ2) and (X25519 plus PQ2 plus
PQ3) and (X25519 plus PQ1 plus PQ2 plus PQ3), where the PS shares add up
fast.  It's not clear that the ecosystem will end up in a place where we
need to do the latter.

-Ben

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 31 Jul 2019 10:31:47 +1000

> different creature, though, and perhaps should be considered more

Adam directly addressed that concern at the meeting; and others agreed.  25519 shares are small enough that worrying about duplication isn't necessary.  The delta is tiny when considering the need to additionally signal combinatorics in the scheme imagined by Option 1.

So I'd like to add my voice to those in support of buttoning down a single scheme (i.e., Option 2).  The cost of the added indirection is significant.  I'll take the addition of a few bytes to the ClientHello over that any time.

The other arguments all assume that we'll fail to narrow the parameter set or number of options.  My view is that deciding on a single parameter set is not just desirable, but necessary.  My experience suggests that clients won't want to expend the resources necessary to create and send two PQ shares.  No PQ scheme that I've seen are close enough in terms of efficiency - bytes or CPU - to allow for multiple shares to be offered.

Option 2 also allows us to defer the combination method.  While I imagine that concatenation will be injective for most schemes, which might be sufficient, we might want to change the combination method as we learn more.  Option 2 allows us to include a definition for how secrets produced by each scheme are merged into the key schedule for each combination.

---

From: Hubert Kario <[email-masked]>
Date: Wed, 31 Jul 2019 11:38:22 +0200

On Tuesday, 30 July 2019 17:21:05 CEST Scott Fluhrer (sfluhrer) wrote:
> several different 'groups' simultaneously (because there might not be one
> group that is entirely trusted, and I put 'groups' in scarequotes because
> Option 1: as the supported group, we insert a 'hybrid marker' (and include
> For example, the client might list in his supported groups hybrid_marker_0
> and hybrid_marker_1, and there would be a separate extension that lists
> hybrid_marker_0 = X25519 + SIKEp434 and hybrid_marker_1 = X25519 +
> NTRUPR653.  The server would then look up the meanings of hybrid_marker_0
> and 1 in the extension, and then compare that against his security policy.
> In this option, we would ask IANA to allocate code points for all the
> various combinations that we want allow to be negotiated.

yes, option 1 sounds like a safer bet given the number of unknowns we have to 
work with
(though the exact proposed mechanism is a bit clunky)

both leave open the question how the secrets should be combined – some kind of 
concatenation scheme or another round of Derive-Secret → HKDF-Extract

-- 
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 115, 612 00  Brno, Czech Republic