Subject: [TLS] Advancing draft-ietf-tls-hybrid-design

From: Douglas Stebila <[email-masked]>
Date: Tue, 6 Jul 2021 21:19:35 -0400

Dear TLS working group,

We wanted to see if there is any further feedback on our draft "Hybrid key exchange in TLS 1.3" (https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/) and what steps are required for it to advance further.  We have not received any new feedback from the working group since we posted our last non-trivial update in October 2020.

The draft as written does not actually specify any post-quantum algorithms nor give identifiers for specific algorithm combinations, only the formats for hybrid key exchange messages and key derivation.  We have received a suggestion that the draft be updated to include identifiers for hybrid key exchange combining elliptic curve groups and the KEMs currently in Round 3 of the NIST PQC standardization process, so that implementations can begin testing interoperability using numbers listed in the draft, rather than relying on ad hoc lists for such purposes.  Is that something the working group would like to see, or would you prefer to leave it as it currently stands, without any specific algorithm identifiers?

Douglas, Scott, and Shay

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 7 Jul 2021 01:47:01 +0000

I personally do not find the proposed approach appealing (or even useful).

There are three possibilities.

a. Quantum computers capable of breaking crypto (QC) become practical *and* NIST PQC winner(s) resist both quantum and classic attacks;
b. QC become practical, and NIST PQC candidates fail (doesn't matter whether they fall to classic or quantum attack!);
c. QC do *not* materialize, *and* PQC candidates fail to classic attacks.

The only possibility justifying the hybrid exchange is (c), which I personally find the least probable. In both (a) and (b) addition of ECC does not make the KE any more secure than without it.
--
Regards,
Uri
 
There are two ways to design a system. One is to make is so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
                                                                                                                                     -  C. A. R. Hoare

On 7/6/21, 21:19, "TLS on behalf of Douglas Stebila" <[email-masked] on behalf of [email-masked]> wrote:

    Dear TLS working group,

    Douglas, Scott, and Shay
    _______________________________________________
    TLS mailing list
    [email-masked]
    https://www.ietf.org/mailman/listinfo/tls

---

From: "Martin Thomson" <[email-masked]>
Date: Wed, 07 Jul 2021 11:53:25 +1000

I just took a look.  I didn't read the (large) appendices, though I appreciate that they have value.

The draft is largely in good shape.  I have a few minor concerns.

I don't think that you want to reserve the hybrid_private_use(0x2F00..0x2FFF) range of values.  There were specific reasons for an FFDHE range that I don't think apply if we constrain this design to TLS 1.3 and higher (as we should).  The same applies to the 0x02.. prefix you suggest for the use of hybrid codepoints.

I find the emphasis on the NIST process a little strong for what is a permanent artifact.  It is OK to note its existence as motivation for the work, but I would avoid over-emphasis.  For example:

OLD:
   Moreover, it is possible that even by the end of the NIST Post-
   Quantum Cryptography Standardization Project, and for a period of
   time thereafter, conservative users may not have full confidence in
   some algorithms.
NEW:
   Moreover, it is possible that after next-generation algorithms are defined, and for a period of
   time thereafter, conservative users may not have full confidence in those algorithms.

and 

OLD:
   In the context of the NIST Post-Quantum Cryptography Standardization
   Project, key exchange algorithms are formulated as key encapsulation
   mechanisms (KEMs), which consist of three algorithms:
NEW:
   This document models key agreement as key encapsulation
   mechanisms (KEMs), which consist of three algorithms:

Please avoid "defining" codepoints, even in examples:

OLD:
   For example, a future document could specify that hybrid value 0x2000 corresponds to
   secp256r1+ntruhrss701, and 0x2001 corresponds to x25519+ntruhrss701.
 NEW:
   For example, a future document could specify that one codepoint corresponds to
   secp256r1+ntruhrss701, and another corresponds to x25519+ntruhrss701.
  
Finally, the use of the word "hybrid" is awkward.  Maybe "composite" is a less-heavily overloaded term that accurately captures the intent; with an antonym of "unitary" or "discrete".

When you talk about concatenation, it might pay to cite the relevant appendix.  I would also note that the goal is that when the composed elements are not fixed-length, a length prefix might be used to ensure that both secrets contribute all of their entropy without being exposed to a weakness in the other.  (You might say that the composition is injective.)

Section 4 includes questions to which I think answers can be given now:

 *Larger public keys and/or ciphertexts.* => I think that the answer here has to be "too bad".  Just note that TLS cannot handle a KEM that includes values larger than 2^16 (minus a little bit).

*Duplication of key shares.* => Your existing text is sufficient to answer this one.

*Resumption.* => There isn't much existing language on this point, but I don't see it as needing anything special in this draft.  My view is that fresh entropy of any kind is an improvement, but generally we will see better than that because clients and servers will perform a fresh key exchange with an algorithm that they consider sufficient at the time.  That might result in a change in posture relative to the original session, but the result should still be as good as min(original, current), which is always better than just using the PSK.

*Failures.* => KEM failure is a problem, but I would do nothing more than note the potential and have the handshake fail.  I see that the finalists have low enough error rates that this doesn't seem likely to be an issue in practice.  Clients can always try again if they hit this specific problem.  Ours already retries in a bunch of different failure cases.  Some text on this point in the draft is probably sensible.

Nits:

OLD:
   However, the
   key_exchange values for each algorithm MUST be generated
   independently.
NEW:
   However, 
   key_exchange values for different algorithms MUST be generated
   independently.

On Wed, Jul 7, 2021, at 11:19, Douglas Stebila wrote:
> Dear TLS working group,
> 
> We wanted to see if there is any further feedback on our draft "Hybrid 
> key exchange in TLS 1.3" 
> (https://datatracker.ietf.org/doc/draft-ietf-tls-hybrid-design/) and 
> what steps are required for it to advance further.  We have not 
> received any new feedback from the working group since we posted our 
> last non-trivial update in October 2020.
> 
> The draft as written does not actually specify any post-quantum 
> algorithms nor give identifiers for specific algorithm combinations, 
> only the formats for hybrid key exchange messages and key derivation.  
> We have received a suggestion that the draft be updated to include 
> identifiers for hybrid key exchange combining elliptic curve groups and 
> the KEMs currently in Round 3 of the NIST PQC standardization process, 
> so that implementations can begin testing interoperability using 
> numbers listed in the draft, rather than relying on ad hoc lists for 
> such purposes.  Is that something the working group would like to see, 
> or would you prefer to leave it as it currently stands, without any 
> specific algorithm identifiers?
> 
> Douglas, Scott, and Shay

---

From: "Salz, Rich" <[email-masked]>
Date: Wed, 7 Jul 2021 13:26:53 +0000

PQ OID's came up in the LAMPS working group, which seems to want to defer to NIST.  You should maybe cross-post your note there.

---

From: Douglas Stebila <[email-masked]>
Date: Mon, 12 Jul 2021 13:56:14 -0400

Thanks Martin.  All makes sense, and I'll incorporate in a revision.  Though at this point changing the word "hybrid" to "composite" would be a rather big rewrite so I'll omit that unless there are very strong objections to the word hybrid.

Douglas

> On Jul 6, 2021, at 21:53, Martin Thomson <[email-masked]> wrote:
>

---

From: Douglas Stebila <[email-masked]>
Date: Mon, 12 Jul 2021 13:59:16 -0400

> PQ OID's came up in the LAMPS working group, which seems to want to defer to NIST.  You should maybe cross-post your note there.

Hi Rich,

Unless I'm mistaken, OIDs are relevant to TLS in the context of signatures, but not key exchange; TLS defines its own algorithm identifiers for "groups" in key exchange independently of the OID system.  So when to define group identifiers for hybrid key exchange would be a TLS working group choice.

Douglas

---

From: Dan Brown <[email-masked]>
Date: Tue, 13 Jul 2021 15:08:07 +0000

Hi Douglas,

Your general approach paves the way for improved forward security, as
insurance against new attacks, a non-negligible risk (*).  So, the TLS WG
should advance it soon.  Sorry, that I've not yet looked at the details, but
I trust that your I-D is good. 

Best regards,

Dan

PS

(*) The non-negligible risk of new (or secret) attacks does not discount the
existing protocols or past work of the TLS WG. The TLS WG priority has
rightly been to address much greater risks (TCP unprotected by
cryptography), etc., but can now build on that work to further improve
security.

A strawman counter-argument to "hybrid public-key": why not do the same
thing for symmetric-key, i.e. the TLS record layer?  Two reasons. One: the
quantum computer risk more greatly affects public-key, while many of the PQC
alternatives are not yet tested (as much as the symmetric-key options).
Two: internally, typical symmetric-key cryptography already applies rounds
of different types of operations, e.g. linear and non-linear, so
symmetric-key is "hybrid" already (to a limited degree).

About "hybrid" terminology

> -----Original Message-----
> From: TLS <[email-masked]> On Behalf Of Douglas Stebila
 
> ...  Though at
> this point changing the word "hybrid" to "composite" would be a rather big
> rewrite so I'll omit that unless there are very strong objections to the
word
> hybrid.

On the "hybrid" terminology (i.e. which paint for the bike-shed), other
names seem better, if less slick.  

There's "layered diverse cryptography", but that conflicts with the L in
TLS.  Also, "strongest-link" is quite clear.  There's several other
alternatives, but maybe not as good. 

PPS: off-topic rant (for TLS ): 

Consider that CFRG has a draft about "Hybrid PKE" (HPKE, *).  This raises a
question: what to call a hybrid of this hybrid (e.g. ECC+PQC) with that
hybrid (e.g. KEM+DEM)?  Hyper-hybrid?

Although HPKE is not destined for TLS, consistent terminology for
cryptography across WGs would be ideal.  It could be confusing if each WG
used different terminology for the same cryptographic methods, or in this
case, the same terminology for different cryptographic methods.  That said,
coordination of a large open organization like IETF is difficult, and so is
choosing clear terminology for complicated ideas of cryptography.

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.