[TLS] SIKE vs SIDH (was Options for negotiating hybrid key exchanges for postquantum)

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

This is a side issue (we’re probably not going to talk about which postquantum primitives to use for another two years), but:


  *   What do you see as the advantage of SIDH?  The server can’t arbitrarily select the shared secret (at least, if we select the KEM version of SIKE); what specific advantage were you thinking of.
  *   The security proof of TLS 1.3 (at least, the ones I’ve seen) assume that the key exchange is CCA secure [1].  SIDH is not; I would prefer to stay with a key exchange that meets the assumptions of the proof, and barring an improved security proof that makes weaker assumptions, that means SIKE rather than SIDH.

[1] For people with real lives and who do not obsess over the minutiae of cryptography, CCA for a key exchange means that the private key is secure, even if the attacker is allowed to submit an arbitrary (possibly malformed) key share.  The conventional wisdom is that you don’t need to this level of protection for ephemeral key exchanges (where we generate a fresh private key for each exchange; we allow him to learn the shared secret for the exchange he is a party of, and learning the private key for this exchange tells him nothing about any other exchange); however the current proofs for TLS 1.3 make this assumption, even if you use a private key only once.

From: Blumenthal, Uri - 0553 - MITLL <[e-mail]>
Sent: Tuesday, July 30, 2019 3:41 PM
To: Panos Kampanakis (pkampana) <[e-mail]>; Scott Fluhrer (sfluhrer) <[e-mail]>; <[e-mail]> <[e-mail]>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

One more thing: I would expect to use SIDH rather than SIKE.

Because to emulate the security advantages of DH, you’d have to run two SIKE’s – one in each direction.


From: TLS <[e-mail]<mailto:[e-mail]>> on behalf of "Panos Kampanakis (pkampana)" <[e-mail]<mailto:[e-mail]>>
Date: Tuesday, July 30, 2019 at 3:37 PM
To: "Scott Fluhrer (sfluhrer)" <[e-mail]<mailto:[e-mail]>>, "<[e-mail]<mailto:[e-mail]>>" <[e-mail]<mailto:[e-mail]>>
Subject: Re: [TLS] Options for negotiating hybrid key exchanges for postquantum

+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 <[e-mail]<mailto:[e-mail]>> On Behalf Of Scott Fluhrer (sfluhrer)
Sent: Tuesday, July 30, 2019 11:21 AM
To: <[e-mail]<mailto:[e-mail]>> <[e-mail]<mailto:[e-mail]>>
Subject: [TLS] Options for negotiating hybrid key exchanges for postquantum

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.