idnits 2.17.1 draft-stebila-tls-hybrid-design-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** There are 2 instances of too long lines in the document, the longest one being 1 character in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 08, 2019) is 1754 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-07) exists of draft-ietf-tls-tls13-cert-with-extern-psk-02 == Outdated reference: A later version (-07) exists of draft-hoffman-c2pq-05 == Outdated reference: A later version (-04) exists of draft-tjhai-ipsecme-hybrid-qske-ikev2-03 == Outdated reference: A later version (-11) exists of draft-ietf-ipsecme-qr-ikev2-08 Summary: 1 error (**), 0 flaws (~~), 5 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group D. Stebila 3 Internet-Draft University of Waterloo 4 Intended status: Informational S. Fluhrer 5 Expires: January 9, 2020 Cisco Systems 6 S. Gueron 7 U. Haifa, Amazon Web Services 8 July 08, 2019 10 Design issues for hybrid key exchange in TLS 1.3 11 draft-stebila-tls-hybrid-design-01 13 Abstract 15 Hybrid key exchange refers to using multiple key exchange algorithms 16 simultaneously and combining the result with the goal of providing 17 security even if all but one of the component algorithms is broken, 18 and is motivated by transition to post-quantum cryptography. This 19 document categorizes various design considerations for using hybrid 20 key exchange in the Transport Layer Security (TLS) protocol version 21 1.3 and outlines two concrete instantiations for consideration. 23 Status of This Memo 25 This Internet-Draft is submitted in full conformance with the 26 provisions of BCP 78 and BCP 79. 28 Internet-Drafts are working documents of the Internet Engineering 29 Task Force (IETF). Note that other groups may also distribute 30 working documents as Internet-Drafts. The list of current Internet- 31 Drafts is at https://datatracker.ietf.org/drafts/current/. 33 Internet-Drafts are draft documents valid for a maximum of six months 34 and may be updated, replaced, or obsoleted by other documents at any 35 time. It is inappropriate to use Internet-Drafts as reference 36 material or to cite them other than as "work in progress." 38 This Internet-Draft will expire on January 9, 2020. 40 Copyright Notice 42 Copyright (c) 2019 IETF Trust and the persons identified as the 43 document authors. All rights reserved. 45 This document is subject to BCP 78 and the IETF Trust's Legal 46 Provisions Relating to IETF Documents 47 (https://trustee.ietf.org/license-info) in effect on the date of 48 publication of this document. Please review these documents 49 carefully, as they describe your rights and restrictions with respect 50 to this document. Code Components extracted from this document must 51 include Simplified BSD License text as described in Section 4.e of 52 the Trust Legal Provisions and are provided without warranty as 53 described in the Simplified BSD License. 55 Table of Contents 57 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 58 1.1. Revision history . . . . . . . . . . . . . . . . . . . . 3 59 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 60 1.3. Motivation for use of hybrid key exchange . . . . . . . . 4 61 1.4. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 5 62 1.5. Goals . . . . . . . . . . . . . . . . . . . . . . . . . . 5 63 1.6. Related work . . . . . . . . . . . . . . . . . . . . . . 7 64 2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 8 65 3. Design options . . . . . . . . . . . . . . . . . . . . . . . 10 66 3.1. (Neg) How to negotiate hybridization and component 67 algorithms? . . . . . . . . . . . . . . . . . . . . . . . 10 68 3.1.1. Key exchange negotiation in TLS 1.3 . . . . . . . . . 10 69 3.1.2. (Neg-Ind) Negotiating component algorithms 70 individually . . . . . . . . . . . . . . . . . . . . 10 71 3.1.3. (Neg-Comb) Negotiating component algorithms as a 72 combination . . . . . . . . . . . . . . . . . . . . . 11 73 3.1.4. Benefits and drawbacks . . . . . . . . . . . . . . . 12 74 3.2. (Num) How many component algorithms to combine? . . . . . 13 75 3.2.1. (Num-2) Two . . . . . . . . . . . . . . . . . . . . . 13 76 3.2.2. (Num-2+) Two or more . . . . . . . . . . . . . . . . 13 77 3.2.3. Benefits and Drawbacks . . . . . . . . . . . . . . . 13 78 3.3. (Shares) How to convey key shares? . . . . . . . . . . . 13 79 3.3.1. (Shares-Concat) Concatenate key shares . . . . . . . 13 80 3.3.2. (Shares-Multiple) Send multiple key shares . . . . . 14 81 3.3.3. (Shares-Ext-Additional) Extension carrying additional 82 key shares . . . . . . . . . . . . . . . . . . . . . 14 83 3.3.4. Benefits and Drawbacks . . . . . . . . . . . . . . . 14 84 3.4. (Comb) How to use keys? . . . . . . . . . . . . . . . . . 14 85 3.4.1. (Comb-Concat) Concatenate keys . . . . . . . . . . . 15 86 3.4.2. (Comb-KDF-1) KDF keys . . . . . . . . . . . . . . . . 16 87 3.4.3. (Comb-KDF-2) KDF keys . . . . . . . . . . . . . . . . 17 88 3.4.4. (Comb-XOR) XOR keys . . . . . . . . . . . . . . . . . 18 89 3.4.5. (Comb-Chain) Chain of KDF applications for each key . 18 90 3.4.6. (Comb-AltInput) Second shared secret in an alternate 91 KDF input . . . . . . . . . . . . . . . . . . . . . . 19 92 3.4.7. Benefits and Drawbacks . . . . . . . . . . . . . . . 20 93 3.4.8. Open questions . . . . . . . . . . . . . . . . . . . 21 94 4. Candidate instantiations . . . . . . . . . . . . . . . . . . 21 95 4.1. Candidate Instantiation 1 . . . . . . . . . . . . . . . . 21 96 4.1.1. ClientHello extension supported_groups . . . . . . . 22 97 4.1.2. ClientHello extension hybrid_extension . . . . . . . 22 98 4.1.3. ClientHello extension key_share . . . . . . . . . . . 23 99 4.1.4. ServerHello extension KeyShareServerHello . . . . . . 23 100 4.1.5. Key schedule . . . . . . . . . . . . . . . . . . . . 24 101 4.2. Candidate Instantiation 2 . . . . . . . . . . . . . . . . 25 102 4.2.1. ClientHello extension supported_groups . . . . . . . 26 103 4.2.2. ClientHello extension KeyShareClientHello . . . . . . 26 104 4.2.3. ServerHello extension KeyShareServerHello . . . . . . 27 105 4.2.4. Key schedule . . . . . . . . . . . . . . . . . . . . 27 106 4.3. Comparing Candidate Instantiation 1 and 2 . . . . . . . . 27 107 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 27 108 6. Security Considerations . . . . . . . . . . . . . . . . . . . 27 109 6.1. Active security . . . . . . . . . . . . . . . . . . . . . 28 110 6.2. Resumption . . . . . . . . . . . . . . . . . . . . . . . 28 111 6.3. Failures . . . . . . . . . . . . . . . . . . . . . . . . 28 112 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 28 113 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 29 114 8.1. Normative References . . . . . . . . . . . . . . . . . . 29 115 8.2. Informative References . . . . . . . . . . . . . . . . . 29 116 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 32 118 1. Introduction 120 This document categorizes various design decisions one could make 121 when implementing hybrid key exchange in TLS 1.3, with the goal of 122 fostering discussion, providing options for short-term prototypes/ 123 experiments, and serving as a basis for eventual standardization. 124 This document also includes two concrete instantiations for 125 consideration, following two different approaches; it is not our 126 intention that both be standardized. 128 This document does not propose specific post-quantum mechanisms; see 129 Section 1.4 for more on the scope of this document. 131 Comments are solicited and should be addressed to the TLS working 132 group mailing list at tls@ietf.org and/or the author(s). 134 1.1. Revision history 136 o draft-00: Initial version. 138 o draft-01: 140 * Add (Comb-KDF-1) (Section 3.4.2) and (Comb-KDF-2) 141 (Section 3.4.3) options. 143 * Add Candidate Instantiation 1 (Section 4.1). 145 * Add Candidate Instantiation 2 (Section 4.2). 147 1.2. Terminology 149 For the purposes of this document, it is helpful to be able to divide 150 cryptographic algorithms into two classes: 152 o "Traditional" algorithms: Algorithms which are widely deployed 153 today, but which may be deprecated in the future. In the context 154 of TLS 1.3 in 2019, examples of traditional key exchange 155 algorithms include elliptic curve Diffie-Hellman using secp256r1 156 or x25519, or finite-field Diffie-Hellman. 158 o "Next-generation" (or "next-gen") algorithms: Algorithms which are 159 not yet widely deployed, but which may eventually be widely 160 deployed. An additional facet of these algorithms may be that we 161 have less confidence in their security due to them being 162 relatively new or less studied. This includes "post-quantum" 163 algorithms. 165 "Hybrid" key exchange, in this context, means the use of two (or 166 more) key exchange mechanisms based on different cryptographic 167 assumptions (for example, one traditional algorithm and one next-gen 168 algorithm), with the purpose of the final session key being secure as 169 long as at least one of the component key exchange mechanisms remains 170 unbroken. We use the term "component" algorithms to refer to the 171 algorithms that are being combined in a hybrid key exchange. 173 The primary motivation of this document is preparing for post-quantum 174 algorithms. However, it is possible that public key cryptography 175 based on alternative mathematical constructions will be required 176 independent of the advent of a quantum computer, for example because 177 of a cryptanalytic breakthrough. As such we opt for the more generic 178 term "next-generation" algorithms rather than exclusively "post- 179 quantum" algorithms. 181 1.3. Motivation for use of hybrid key exchange 183 Ideally, one would not use hybrid key exchange: one would have 184 confidence in a single algorithm and parameterization that will stand 185 the test of time. However, this may not be the case in the face of 186 quantum computers and cryptanalytic advances more generally. 188 Many (but not all) of the post-quantum algorithms currently under 189 consideration are relatively new; they have not been subject to the 190 same depth of study as RSA and finite-field / elliptic curve Diffie- 191 Hellman, and thus we do not necessarily have as much confidence in 192 their fundamental security, or the concrete security level of 193 specific parameterizations. 195 Early adopters eager for post-quantum security may want to use hybrid 196 key exchange to have the potential of post-quantum security from a 197 less-well-studied algorithm while still retaining at least the 198 security currently offered by traditional algorithms. (They may even 199 need to retain traditional algorithms due to regulatory constraints, 200 for example FIPS compliance.) 202 Moreover, it is possible that even by the end of the NIST Post- 203 Quantum Cryptography Standardization Project, and for a period of 204 time thereafter, conservative users may not have full confidence in 205 some algorithms. 207 As such, there may be users for whom hybrid key exchange is an 208 appropriate step prior to an eventual transition to next-generation 209 algorithms. 211 1.4. Scope 213 This document focuses on hybrid ephemeral key exchange in TLS 1.3 214 [TLS13]. It intentionally does not address: 216 o Selecting which next-generation algorithms to use in TLS 1.3, nor 217 algorithm identifiers nor encoding mechanisms for next-generation 218 algorithms. (The outcomes of the NIST Post-Quantum Cryptography 219 Standardization Project [NIST] will inform this choice.) 221 o Authentication using next-generation algorithms. (If a 222 cryptographic assumption is broken due to the advent of a quantum 223 computer or some other cryptanalytic breakthrough, confidentiality 224 of information can be broken retroactively by any adversary who 225 has passively recorded handshakes and encrypted communications. 226 But session authentication cannot be retroactively broken.) 228 1.5. Goals 230 The primary goal of a hybrid key exchange mechanism is to facilitate 231 the establishment of a shared secret which remains secure as long as 232 as one of the component key exchange mechanisms remains unbroken. 234 In addition to the primary cryptographic goal, there may be several 235 additional goals in the context of TLS 1.3: 237 o *Backwards compatibility:* Clients and servers who are "hybrid- 238 aware", i.e., compliant with whatever hybrid key exchange standard 239 is developed for TLS, should remain compatible with endpoints and 240 middle-boxes that are not hybrid-aware. The three scenarios to 241 consider are: 243 1. Hybrid-aware client, hybrid-aware server: These parties should 244 establish a hybrid shared secret. 246 2. Hybrid-aware client, non-hybrid-aware server: These parties 247 should establish a traditional shared secret (assuming the 248 hybrid-aware client is willing to downgrade to traditional- 249 only). 251 3. Non-hybrid-aware client, hybrid-aware server: These parties 252 should establish a traditional shared secret (assuming the 253 hybrid-aware server is willing to downgrade to traditional- 254 only). 256 Ideally backwards compatibility should be achieved without extra 257 round trips and without sending duplicate information; see below. 259 o *High performance:* Use of hybrid key exchange should not be 260 prohibitively expensive in terms of computational performance. In 261 general this will depend on the performance characteristics of the 262 specific cryptographic algorithms used, and as such is outside the 263 scope of this document. See [BCNS15], [CECPQ1], [FRODO] for 264 preliminary results about performance characteristics. 266 o *Low latency:* Use of hybrid key exchange should not substantially 267 increase the latency experienced to establish a connection. 268 Factors affecting this may include the following. 270 * The computational performance characteristics of the specific 271 algorithms used. See above. 273 * The size of messages to be transmitted. Public key / 274 ciphertext sizes for post-quantum algorithms range from 275 hundreds of bytes to over one hundred kilobytes, so this impact 276 can be substantially. See [BCNS15], [FRODO] for preliminary 277 results in a laboratory setting, and [LANGLEY] for preliminary 278 results on more realistic networks. 280 * Additional round trips added to the protocol. See below. 282 o *No extra round trips:* Attempting to negotiate hybrid key 283 exchange should not lead to extra round trips in any of the three 284 hybrid-aware/non-hybrid-aware scenarios listed above. 286 o *No duplicate information:* Attempting to negotiate hybrid key 287 exchange should not mean having to send multiple public keys of 288 the same type. 290 1.6. Related work 292 Quantum computing and post-quantum cryptography in general are 293 outside the scope of this document. For a general introduction to 294 quantum computing, see a standard textbook such as [NIELSEN]. For an 295 overview of post-quantum cryptography as of 2009, see [BERNSTEIN]. 296 For the current status of the NIST Post-Quantum Cryptography 297 Standardization Project, see [NIST]. For additional perspectives on 298 the general transition from classical to post-quantum cryptography, 299 see for example [ETSI] and [HOFFMAN], among others. 301 There have been several Internet-Drafts describing mechanisms for 302 embedding post-quantum and/or hybrid key exchange in TLS: 304 o Internet-Drafts for TLS 1.2: [WHYTE12] 306 o Internet-Drafts for TLS 1.3: [KIEFER], [SCHANCK], [WHYTE13] 308 There have been several prototype implementations for post-quantum 309 and/or hybrid key exchange in TLS: 311 o Experimental implementations in TLS 1.2: [BCNS15], [CECPQ1], 312 [FRODO], [OQS-102] 314 o Experimental implementations in TLS 1.3: [CECPQ2], [OQS-111] 316 These experimental implementations have taken an ad hoc approach and 317 not attempted to implement one of the drafts listed above. 319 Unrelated to post-quantum but still related to the issue of combining 320 multiple types of keying material in TLS is the use of pre-shared 321 keys, especially the recent TLS working group document on including 322 an external pre-shared key [EXTERN-PSK]. 324 Considering other IETF standards, there is work on post-quantum 325 preshared keys in IKEv2 [IKE-PSK] and a framework for hybrid key 326 exchange in IKEv2 [IKE-HYBRID]. The XMSS hash-based signature scheme 327 has been published as an informational RFC by the IRTF [XMSS]. 329 In the academic literature, [EVEN] initiated the study of combining 330 multiple symmetric encryption schemes; [ZHANG], [DODIS], and [HARNIK] 331 examined combining multiple public key encryption schemes, and 332 [HARNIK] coined the term "robust combiner" to refer to a compiler 333 that constructs a hybrid scheme from individual schemes while 334 preserving security properties. [GIACON] and [BINDEL] examined 335 combining multiple key encapsulation mechanisms. 337 2. Overview 339 We identify four distinct axes along which one can make choices when 340 integrating hybrid key exchange into TLS 1.3: 342 1. How to negotiate the use of hybridization in general and 343 component algorithms specifically? 345 2. How many component algorithms can be combined? 347 3. How should multiple key shares (public keys / ciphertexts) be 348 conveyed? 350 4. How should multiple shared secrets be combined? 352 The remainder of this document outlines various options we have 353 identified for each of these choices. Immediately below we provide a 354 summary list. Options are labelled with a short code in parentheses 355 to provide easy cross-referencing. 357 1. (Neg) (Section 3.1) How to negotiate the use of hybridization in 358 general and component algorithms specifically? 360 * (Neg-Ind) (Section 3.1.2) Negotiating component algorithms 361 individually 363 + (Neg-Ind-1) (Section 3.1.2.1) Traditional algorithms in 364 "ClientHello" "supported_groups" extension, next-gen 365 algorithms in another extension 367 + (Neg-Ind-2) (Section 3.1.2.2) Both types of algorithms in 368 "supported_groups" with external mapping to tradition/next- 369 gen. 371 + (Neg-Ind-3) (Section 3.1.2.3) Both types of algorithms in 372 "supported_groups" separated by a delimiter. 374 * (Neg-Comb) (Section 3.1.3) Negotiating component algorithms as 375 a combination 377 + (Neg-Comb-1) (Section 3.1.3.1) Standardize "NamedGroup" 378 identifiers for each desired combination. 380 + (Neg-Comb-2) (Section 3.1.3.2) Use placeholder identifiers 381 in "supported_groups" with an extension defining the 382 combination corresponding to each placeholder. 384 + (Neg-Comb-3) (Section 3.1.3.3) List combinations by 385 inserting grouping delimiters into "supported_groups" list. 387 2. (Num) (Section 3.2) How many component algorithms can be 388 combined? 390 * (Num-2) (Section 3.2.1) Two. 392 * (Num-2+) (Section 3.2.2) Two or more. 394 3. (Shares) (Section 3.3) How should multiple key shares (public 395 keys / ciphertexts) be conveyed? 397 * (Shares-Concat) (Section 3.3.1) Concatenate each combination 398 of key shares. 400 * (Shares-Multiple) (Section 3.3.2) Send individual key shares 401 for each algorithm. 403 * (Shares-Ext-Additional) (Section 3.3.3) Use an extension to 404 convey key shares for component algorithms. 406 4. (Comb) (Section 3.4) How should multiple shared secrets be 407 combined? 409 * (Comb-Concat) (Section 3.4.1) Concatenate the shared secrets 410 then use directly in the TLS 1.3 key schedule. 412 * (Comb-KDF-1) (Section 3.4.2) and (Comb-KDF-2) (Section 3.4.3) 413 KDF the shared secrets together, then use the output in the 414 TLS 1.3 key schedule. 416 * (Comb-XOR) (Section 3.4.4) XOR the shared secrets then use 417 directly in the TLS 1.3 key schedule. 419 * (Comb-Chain) (Section 3.4.5) Extend the TLS 1.3 key schedule 420 so that there is a stage of the key schedule for each shared 421 secret. 423 * (Comb-AltInput) (Section 3.4.6) Use the second shared secret 424 in an alternate (otherwise unused) input in the TLS 1.3 key 425 schedule. 427 3. Design options 429 3.1. (Neg) How to negotiate hybridization and component algorithms? 431 3.1.1. Key exchange negotiation in TLS 1.3 433 Recall that in TLS 1.3, the key exchange mechanism is negotiated via 434 the "supported_groups" extension. The "NamedGroup" enum is a list of 435 standardized groups for Diffie-Hellman key exchange, such as 436 "secp256r1", "x25519", and "ffdhe2048". 438 The client, in its "ClientHello" message, lists its supported 439 mechanisms in the "supported_groups" extension. The client also 440 optionally includes the public key of one or more of these groups in 441 the "key_share" extension as a guess of which mechanisms the server 442 might accept in hopes of reducing the number of round trips. 444 If the server is willing to use one of the client's requested 445 mechanisms, it responds with a "key_share" extension containing its 446 public key for the desired mechanism. 448 If the server is not willing to use any of the client's requested 449 mechanisms, the server responds with a "HelloRetryRequest" message 450 that includes an extension indicating its preferred mechanism. 452 3.1.2. (Neg-Ind) Negotiating component algorithms individually 454 In these three approaches, the parties negotiate which traditional 455 algorithm and which next-gen algorithm to use independently. The 456 "NamedGroup" enum is extended to include algorithm identifiers for 457 each next-gen algorithm. 459 3.1.2.1. (Neg-Ind-1) 461 The client advertises two lists to the server: one list containing 462 its supported traditional mechanisms (e.g. via the existing 463 "ClientHello" "supported_groups" extension), and a second list 464 containing its supported next-generation mechanisms (e.g., via an 465 additional "ClientHello" extension). A server could then select one 466 algorithm from the traditional list, and one algorithm from the next- 467 generation list. (This is the approach in [SCHANCK].) 469 3.1.2.2. (Neg-Ind-2) 471 The client advertises a single list to the server which contains both 472 its traditional and next-generation mechanisms (e.g., all in the 473 existing "ClientHello" "supported_groups" extension), but with some 474 external table provides a standardized mapping of those mechanisms as 475 either "traditional" or "next-generation". A server could then 476 select two algorithms from this list, one from each category. 478 3.1.2.3. (Neg-Ind-3) 480 The client advertises a single list to the server delimited into 481 sublists: one for its traditional mechanisms and one for its next- 482 generation mechanisms, all in the existing "ClientHello" 483 "supported_groups" extension, with a special code point serving as a 484 delimiter between the two lists. For example, "supported_groups = 485 secp256r1, x25519, delimiter, nextgen1, nextgen4". 487 3.1.3. (Neg-Comb) Negotiating component algorithms as a combination 489 In these three approaches, combinations of key exchange mechanisms 490 appear as a single monolithic block; the parties negotiate which of 491 several combinations they wish to use. 493 3.1.3.1. (Neg-Comb-1) 495 The "NamedGroup" enum is extended to include algorithm identifiers 496 for each *combination* of algorithms desired by the working group. 497 There is no "internal structure" to the algorithm identifiers for 498 each combination, they are simply new code points assigned 499 arbitrarily. The client includes any desired combinations in its 500 "ClientHello" "supported_groups" list, and the server picks one of 501 these. This is the approach in [KIEFER] and [OQS-111]. 503 3.1.3.2. (Neg-Comb-2) 505 The "NamedGroup" enum is extended to include algorithm identifiers 506 for each next-gen algorithm. Some additional field/extension is used 507 to convey which combinations the parties wish to use. For example, 508 in [WHYTE13], there are distinguished "NamedGroup" called 509 "hybrid_marker 0", "hybrid_marker 1", "hybrid_marker 2", etc. This 510 is complemented by a "HybridExtension" which contains mappings for 511 each numbered "hybrid_marker" to the set of component key exchange 512 algorithms (2 or more) for that proposed combination. 514 3.1.3.3. (Neg-Comb-3) 516 The client lists combinations in "supported_groups" list, using a 517 special delimiter to indicate combinations. For example, 518 "supported_groups = combo_delimiter, secp256r1, nextgen1, 519 combo_delimiter, secp256r1, nextgen4, standalone_delimiter, 520 secp256r1, x25519" would indicate that the client's highest 521 preference is the combination secp256r1+nextgen1, the next highest 522 preference is the combination secp2561+nextgen4, then the single 523 algorithm secp256r1, then the single algorithm x25519. A hybrid- 524 aware server would be able to parse these; a hybrid-unaware server 525 would see "unknown, secp256r1, unknown, unknown, secp256r1, unknown, 526 unknown, secp256r1, x25519", which it would be able to process, 527 although there is the potential that every "projection" of a hybrid 528 list that is tolerable to a client does not result in list that is 529 tolerable to the client. 531 3.1.4. Benefits and drawbacks 533 *Combinatorial explosion.* (Neg-Comb-1) (Section 3.1.3.1) requires 534 new identifiers to be defined for each desired combination. The 535 other 4 options in this section do not. 537 *Extensions.* (Neg-Ind-1) (Section 3.1.2.1) and (Neg-Comb-2) 538 (Section 3.1.3.2) require new extensions to be defined. The other 539 options in this section do not. 541 *New logic.* All options in this section except (Neg-Comb-1) 542 (Section 3.1.3.1) require new logic to process negotiation. 544 *Matching security levels.* (Neg-Ind-1) (Section 3.1.2.1), (Neg-Ind- 545 2) (Section 3.1.2.2), (Neg-Ind-3) (Section 3.1.2.3), and (Neg-Comb-2) 546 (Section 3.1.3.2) allow algorithms of different claimed security 547 level from their corresponding lists to be combined. For example, 548 this could result in combining ECDH secp256r1 (classical security 549 level 128) with NewHope-1024 (classical security level 256). 550 Implementations dissatisfied with a mismatched security levels must 551 either accept this mismatch or attempt to renegotiate. (Neg-Ind-1) 552 (Section 3.1.2.1), (Neg-Ind-2) (Section 3.1.2.2), and (Neg-Ind-3) 553 (Section 3.1.2.3) give control over the combination to the server; 554 (Neg-Comb-2) (Section 3.1.3.2) gives control over the combination to 555 the client. (Neg-Comb-1) (Section 3.1.3.1) only allows standardized 556 combinations, which could be set by TLS working group to have 557 matching security (provided security estimates do not evolve 558 separately). 560 *Backwards-compability.* TLS 1.3-compliant hybrid-unaware servers 561 should ignore unreocgnized elements in "supported_groups" (Neg-Ind-2) 562 (Section 3.1.2.2), (Neg-Ind-3) (Section 3.1.2.3), (Neg-Comb-1) 563 (Section 3.1.3.1), (Neg-Comb-2) (Section 3.1.3.2) and unrecognized 564 "ClientHello" extensions (Neg-Ind-1) (Section 3.1.2.1), (Neg-Comb-2) 565 (Section 3.1.3.2). In (Neg-Ind-3) (Section 3.1.2.3) and (Neg-Comb-3) 566 (Section 3.1.3.3), a server that is hybrid-unaware will ignore the 567 delimiters in "supported_groups", and thus might try to negotiate an 568 algorithm individually that is only meant to be used in combination; 569 depending on how such an implementation is coded, it may also 570 encounter bugs when the same element appears multiple times in the 571 list. 573 3.2. (Num) How many component algorithms to combine? 575 3.2.1. (Num-2) Two 577 Exactly two algorithms can be combined together in hybrid key 578 exchange. This is the approach taken in [KIEFER] and [SCHANCK]. 580 3.2.2. (Num-2+) Two or more 582 Two or more algorithms can be combined together in hybrid key 583 exchange. This is the approach taken in [WHYTE13]. 585 3.2.3. Benefits and Drawbacks 587 Restricting the number of component algorithms that can be hybridized 588 to two substantially reduces the generality required. On the other 589 hand, some adopters may want to further reduce risk by employing 590 multiple next-gen algorithms built on different cryptographic 591 assumptions. 593 3.3. (Shares) How to convey key shares? 595 In ECDH ephmeral key exchange, the client sends its ephmeral public 596 key in the "key_share" extension of the "ClientHello" message, and 597 the server sends its ephmeral public key in the "key_share" extension 598 of the "ServerHello" message. 600 For a general key encapsulation mechanism used for ephemeral key 601 exchange, we imagine that that client generates a fresh KEM public 602 key / secret pair for each connection, sends it to the client, and 603 the server responds with a KEM ciphertext. For simplicity and 604 consistency with TLS 1.3 terminology, we will refer to both of these 605 types of objects as "key shares". 607 In hybrid key exchange, we have to decide how to convey the client's 608 two (or more) key shares, and the server's two (or more) key shares. 610 3.3.1. (Shares-Concat) Concatenate key shares 612 The client concatenates the bytes representing its two key shares and 613 uses this directly as the "key_exchange" value in a "KeyShareEntry" 614 in its "key_share" extension. The server does the same thing. Note 615 that the "key_exchange" value can be an octet string of length at 616 most 2^16-1. This is the approach taken in [KIEFER], [OQS-111], and 617 [WHYTE13]. 619 3.3.2. (Shares-Multiple) Send multiple key shares 621 The client sends multiple key shares directly in the "client_shares" 622 vectors of the "ClientHello" "key_share" extension. The server does 623 the same. (Note that while the existing "KeyShareClientHello" struct 624 allows for multiple key share entries, the existing 625 "KeyShareServerHello" only permits a single key share entry, so some 626 modification would be required to use this approach for the server to 627 send multiple key shares.) 629 3.3.3. (Shares-Ext-Additional) Extension carrying additional key shares 631 The client sends the key share for its traditional algorithm in the 632 original "key_share" extension of the "ClientHello" message, and the 633 key share for its next-gen algorithm in some additional extension in 634 the "ClientHello" message. The server does the same thing. This is 635 the approach taken in [SCHANCK]. 637 3.3.4. Benefits and Drawbacks 639 *Backwards compatibility.* (Shares-Multiple) (Section 3.3.2) is fully 640 backwards compatible with non-hybrid-aware servers. (Shares-Ext- 641 Additional) (Section 3.3.3) is backwards compatible with non-hybrid- 642 aware servers provided they ignore unrecognized extensions. (Shares- 643 Concat) (Section 3.3.1) is backwards-compatible with non-hybrid aware 644 servers, but may result in duplication / additional round trips (see 645 below). 647 *Duplication versus additional round trips.* If a client wants to 648 offer multiple key shares for multiple combinations in order to avoid 649 retry requests, then the client may ended up sending a key share for 650 one algorithm multiple times when using (Shares-Ext-Additional) 651 (Section 3.3.3) and (Shares-Concat) (Section 3.3.1). (For example, 652 if the client wants to send an ECDH-secp256r1 + McEliece123 key 653 share, and an ECDH-secp256r1 + NewHope1024 key share, then the same 654 ECDH public key may be sent twice. If the client also wants to offer 655 a traditional ECDH-only key share for non-hybrid-aware 656 implementations and avoid retry requests, then that same ECDH public 657 key may be sent another time.) (Shares-Multiple) (Section 3.3.2) 658 does not result in duplicate key shares. 660 3.4. (Comb) How to use keys? 662 Each component key exchange algorithm establishes a shared secret. 663 These shared secrets must be combined in some way that achieves the 664 "hybrid" property: the resulting secret is secure as long as at least 665 one of the component key exchange algorithms is unbroken. 667 3.4.1. (Comb-Concat) Concatenate keys 669 Each party concatenates the shared secrets established by each 670 component algorithm in an agreed-upon order, then feeds that through 671 the TLS key schedule. In the context of TLS 1.3, this would mean 672 using the concatenated shared secret in place of the (EC)DHE input to 673 the second call to "HKDF-Extract" in the TLS 1.3 key schedule: 675 0 676 | 677 v 678 PSK -> HKDF-Extract = Early Secret 679 | 680 +-----> Derive-Secret(...) 681 +-----> Derive-Secret(...) 682 +-----> Derive-Secret(...) 683 | 684 v 685 Derive-Secret(., "derived", "") 686 | 687 v 688 concatenated_shared_secret -> HKDF-Extract = Handshake Secret 689 ^^^^^^^^^^^^^^^^^^^^^^^^^^ | 690 +-----> Derive-Secret(...) 691 +-----> Derive-Secret(...) 692 | 693 v 694 Derive-Secret(., "derived", "") 695 | 696 v 697 0 -> HKDF-Extract = Master Secret 698 | 699 +-----> Derive-Secret(...) 700 +-----> Derive-Secret(...) 701 +-----> Derive-Secret(...) 702 +-----> Derive-Secret(...) 704 This is the approach used in [KIEFER], [OQS-111], and [WHYTE13]. 706 [GIACON] analyzes the security of applying a KDF to concatenated KEM 707 shared secrets, but their analysis does not exactly apply here since 708 the transcript of ciphertexts is included in the KDF application 709 (though it should follow relatively straightforwardly). 711 [BINDEL] analyzes the security of the (Comb-Concat) approach as 712 abstracted in their "dualPRF" combiner. They show that, if the 713 component KEMs are IND-CPA-secure (or IND-CCA-secure), then the 714 values output by "Derive-Secret" are IND-CPA-secure (respectively, 715 IND-CCA-secure). An important aspect of their analysis is that each 716 ciphertext is input to the final PRF calls; this holds for TLS 1.3 717 since the "Derive-Secret" calls that derive output keys (application 718 traffic secrets, and exporter and resumption master secrets) include 719 the transcript hash as input. 721 3.4.2. (Comb-KDF-1) KDF keys 723 Each party feeds the shared secrets established by each component 724 algorithm in an agreed-upon order into a KDF, then feeds that through 725 the TLS key schedule. In the context of TLS 1.3, this would mean 726 first applying "HKDF-Extract" to the shared secrets, then using the 727 output in place of the (EC)DHE input to the second call to "HKDF- 728 Extract" in the TLS 1.3 key schedule: 730 0 731 | 732 v 733 PSK -> HKDF-Extract = Early Secret 734 | 735 +-----> Derive-Secret(...) 736 +-----> Derive-Secret(...) 737 +-----> Derive-Secret(...) 738 Next-Gen | 739 | v 740 (EC)DHE -> HKDF-Extract Derive-Secret(., "derived", "") 741 | | 742 v v 743 output -----> HKDF-Extract = Handshake Secret 744 ^^^^^^ | 745 +-----> Derive-Secret(...) 746 +-----> Derive-Secret(...) 747 | 748 v 749 Derive-Secret(., "derived", "") 750 | 751 v 752 0 -> HKDF-Extract = Master Secret 753 | 754 +-----> Derive-Secret(...) 755 +-----> Derive-Secret(...) 756 +-----> Derive-Secret(...) 757 +-----> Derive-Secret(...) 759 3.4.3. (Comb-KDF-2) KDF keys 761 Each party concatenates the shared secrets established by each 762 component algorithm in an agreed-upon order then feeds that into a 763 KDF, then feeds the result through the TLS key schedule. 765 Compared with (Comb-KDF-1) (Section 3.4.2), this method concatenates 766 the (2 or more) shared secrets prior to input to the KDF, whereas 767 (Comb-KDF-1) puts the (exactly 2) shared secrets in the two different 768 input slots to the KDF. 770 Compared with (Comb-Concat) (Section 3.4.1), this method has an 771 extract KDF application. While this adds computational overhead, 772 this may provide a cleaner abstraction of the hybridization mechanism 773 for the purposes of formal security analysis. 775 0 776 | 777 v 778 PSK -> HKDF-Extract = Early Secret 779 | 780 +-----> Derive-Secret(...) 781 +-----> Derive-Secret(...) 782 +-----> Derive-Secret(...) 783 | 784 v 785 concatenated 0 786 shared | 787 secret -> HKDF-Extract Derive-Secret(., "derived", "") 788 ^^^^^^ | | 789 v v 790 output -----> HKDF-Extract = Handshake Secret 791 ^^^^^^ | 792 +-----> Derive-Secret(...) 793 +-----> Derive-Secret(...) 794 | 795 v 796 Derive-Secret(., "derived", "") 797 | 798 v 799 0 -> HKDF-Extract = Master Secret 800 | 801 +-----> Derive-Secret(...) 802 +-----> Derive-Secret(...) 803 +-----> Derive-Secret(...) 804 +-----> Derive-Secret(...) 806 3.4.4. (Comb-XOR) XOR keys 808 Each party XORs the shared secrets established by each component 809 algorithm (possibly after padding secrets of different lengths), then 810 feeds that through the TLS key schedule. In the context of TLS 1.3, 811 this would mean using the XORed shared secret in place of the (EC)DHE 812 input to the second call to "HKDF-Extract" in the TLS 1.3 key 813 schedule. 815 [GIACON] analyzes the security of applying a KDF to the XORed KEM 816 shared secrets, but their analysis does not quite apply here since 817 the transcript of ciphertexts is included in the KDF application 818 (though it should follow relatively straightforwardly). 820 3.4.5. (Comb-Chain) Chain of KDF applications for each key 822 Each party applies a chain of key derivation functions to the shared 823 secrets established by each component algorithm in an agreed-upon 824 order; roughly speaking: "F(k1 || F(k2))". In the context of TLS 825 1.3, this would mean extending the key schedule to have one round of 826 the key schedule applied for each component algorithm's shared 827 secret: 829 0 830 | 831 v 832 PSK -> HKDF-Extract = Early Secret 833 | 834 +-----> Derive-Secret(...) 835 +-----> Derive-Secret(...) 836 +-----> Derive-Secret(...) 837 | 838 v 839 Derive-Secret(., "derived", "") 840 | 841 v 842 traditional_shared_secret -> HKDF-Extract 843 ^^^^^^^^^^^^^^^^^^^^^^^^^ | 844 Derive-Secret(., "derived", "") 845 | 846 v 847 next_gen_shared_secret -> HKDF-Extract = Handshake Secret 848 ^^^^^^^^^^^^^^^^^^^^^^ | 849 +-----> Derive-Secret(...) 850 +-----> Derive-Secret(...) 851 | 852 v 853 Derive-Secret(., "derived", "") 854 | 855 v 856 0 -> HKDF-Extract = Master Secret 857 | 858 +-----> Derive-Secret(...) 859 +-----> Derive-Secret(...) 860 +-----> Derive-Secret(...) 861 +-----> Derive-Secret(...) 863 This is the approach used in [SCHANCK]. 865 [BINDEL] analyzes the security of this approach as abstracted in 866 their nested dual-PRF "N" combiner, showing a similar result as for 867 the dualPRF combiner that it preserves IND-CPA (or IND-CCA) security. 868 Again their analysis depends on each ciphertext being input to the 869 final PRF ("Derive-Secret") calls, which holds for TLS 1.3. 871 3.4.6. (Comb-AltInput) Second shared secret in an alternate KDF input 873 In the context of TLS 1.3, the next-generation shared secret is used 874 in place of a currently unused input in the TLS 1.3 key schedule, 875 namely replacing the "0" "IKM" input to the final "HKDF-Extract": 877 0 878 | 879 v 880 PSK -> HKDF-Extract = Early Secret 881 | 882 +-----> Derive-Secret(...) 883 +-----> Derive-Secret(...) 884 +-----> Derive-Secret(...) 885 | 886 v 887 Derive-Secret(., "derived", "") 888 | 889 v 890 traditional_shared_secret -> HKDF-Extract = Handshake Secret 891 ^^^^^^^^^^^^^^^^^^^^^^^^^ | 892 +-----> Derive-Secret(...) 893 +-----> Derive-Secret(...) 894 | 895 v 896 Derive-Secret(., "derived", "") 897 | 898 v 899 next_gen_shared_secret -> HKDF-Extract = Master Secret 900 ^^^^^^^^^^^^^^^^^^^^^^ | 901 +-----> Derive-Secret(...) 902 +-----> Derive-Secret(...) 903 +-----> Derive-Secret(...) 904 +-----> Derive-Secret(...) 906 This approach is not taken in any of the known post-quantum/hybrid 907 TLS drafts. However, it bears some similarities to the approach for 908 using external PSKs in [EXTERN-PSK]. 910 3.4.7. Benefits and Drawbacks 912 *New logic.* While (Comb-Concat) (Section 3.4.1), (Comb-KDF-1) 913 (Section 3.4.2), and (Comb-KDF-2) (Section 3.4.3) require new logic 914 to compute the concatenated shared secret, this value can then be 915 used by the TLS 1.3 key schedule without changes to the key schedule 916 logic. In contrast, (Comb-Chain) (Section 3.4.5) requires the TLS 917 1.3 key schedule to be extended for each extra component algorithm. 919 *Philosophical.* The TLS 1.3 key schedule already applies a new stage 920 for different types of keying material (PSK versus (EC)DHE), so 921 (Comb-Chain) (Section 3.4.5) continues that approach. 923 *Efficiency.* (Comb-KDF-1) (Section 3.4.2), (Comb-KDF-2) 924 (Section 3.4.3), and (Comb-Chain) (Section 3.4.5) increase the number 925 of KDF applications for each component algorithm, whereas (Comb- 926 Concat) (Section 3.4.1) and (Comb-AltInput) (Section 3.4.6) keep the 927 number of KDF applications the same (though with potentially longer 928 inputs). 930 *Extensibility.* (Comb-AltInput) (Section 3.4.6) changes the use of 931 an existing input, which might conflict with other future changes to 932 the use of the input. 934 *More than 2 component algorithms.* The techniques in (Comb-Concat) 935 (Section 3.4.1) and (Comb-Chain) (Section 3.4.5) can naturally 936 accommodate more than 2 component shared secrets since there is no 937 distinction to how each shared secret is treated. (Comb-AltInput) 938 (Section 3.4.6) would have to make some distinct, since the 2 939 component shared secrets are used in different ways; for example, the 940 first shared secret is used as the "IKM" input in the 2nd "HKDF- 941 Extract" call, and all subsequent shared secrets are concatenated to 942 be used as the "IKM" input in the 3rd "HKDF-Extract" call. 944 3.4.8. Open questions 946 At this point, it is unclear which, if any, of the above methods 947 preserve FIPS compliance: i.e., if one shared secret is from a FIPS- 948 compliant method (e.g., ECDH), and another shared secret is from a 949 non-approved method (e.g., post-quantum), is the result still 950 considered FIPS compliant? Guidance from NIST on this question would 951 be helpful. Specifically, are any of these approaches acceptable 952 under either [NIST-SP-800-56C] or [NIST-SP-800-135]? 954 4. Candidate instantiations 956 In this section, we describe two candidate instantiations of hybrid 957 key exchange in TLS 1.3, based on the design considerations framework 958 above. It is not our intention that both of these instantations be 959 standardized; we are providing two for discussion and for comparing 960 and contrasting the two approaches. 962 4.1. Candidate Instantiation 1 964 Candidate Instantiation 1 allows for two or more component algorithms 965 to be combined (Num-2+) (Section 3.2.2), and negotiates the 966 combination using markers in the "NamedGroup" list as pointers to an 967 extension listing the algorithms comprising each possible combination 968 (Neg-Comb-2) (Section 3.1.3.2) following the approach of [WHYTE13]. 969 The client conveys its multiple key shares individually in the 970 "client_shares" vector of the "ClientHello" "key_share" extension 971 (Shares-Multiple) (Section 3.3.2). The server conveys its multiple 972 key shares concatenated together in its "KeyShareServerHello" struct 973 (Shares-Concat) (Section 3.3.1). The shared secrets are combined by 974 concatenating them then feeding them through a KDF, then feeding the 975 result into the TLS 1.3 key schedule (Comb-KDF-2) (Section 3.4.3). 977 4.1.1. ClientHello extension supported_groups 979 Following [WHYTE13] section 3.1, the "NamedGroup" enum used by the 980 client to populate the "supported_groups" extension is extended to 981 include new code points representing markers for hybrid combinations: 983 enum { 984 /* existing named groups */ 985 secp256r1 (23), 986 ..., 988 /* new code points eventually defined for post-quantum algorithms */ 989 ..., 991 /* new code points reserved for hybrid markers */ 992 hybrid_marker00 (0xFD00), 993 hybrid_marker01 (0xFD01), 994 ... 995 hybrid_markerFF (0xFDFF), 997 /* existing reserved code points */ 998 ffdhe_private_use (0x01FC..0x01FF), 999 ecdhe_private_use (0xFE00..0xFEFF), 1000 (0xFFFF) 1001 } NamedGroup; 1003 "hybrid_marker" code points do not a priori represent any fixed 1004 combination. Instead, during each session establishment, the client 1005 defines what it wants each "hybrid_marker" code point to represent 1006 using the following extension. 1008 4.1.2. ClientHello extension hybrid_extension 1010 Following [WHYTE13] section 3.2.4, a new "ClientHello" 1011 "hybrid_extension" extension is defined. It is defined as follows: 1013 struct { 1014 NamedGroup hybrid_marker; 1015 NamedGroup components<2..10>; 1016 } HybridMapping; 1018 struct { 1019 HybridMapping map<0..255>; 1020 } HybridExtension; 1021 The "HybridExtension" contains 0 or more "HybridMapping"s. Each 1022 "HybridMapping" corresponds to one of the "hybrid_marker" included in 1023 the "supported_groups" extension, and lists the component algorithms 1024 that are meant to comprise the this hybrid combination, which can be 1025 any of the existing named groups (elliptic curve or finite field), 1026 new code points eventually defined for post-quantum algorithms, or 1027 reserved code points for private use. 1029 4.1.3. ClientHello extension key_share 1031 No syntactical modifications are made to the "KeyShareEntry" or 1032 "KeyShareClientHello" data structures. 1034 Semantically, the client does not send a "KeyShareEntry" 1035 corresponding to any of the "hybrid_marker" code points. Instead, 1036 the client sends "KeyShareEntry" for each of the component algorithms 1037 listed in the "HybridMapping"s. 1039 For example, if the list of "supported_groups" is "secp256r1", 1040 "x25519", "hybrid_marker00", and "hybrid_marker01", where 1041 "hybrid_marker00" comprises "secp256r1" with a fictional post-quantum 1042 algorithm "PQ1", and "hybrid_marker01" comprises "x25519" with "PQ1", 1043 then the client could send three "KeyShareEntry" components: one for 1044 "secp256r1", one for "x25519", and one for "PQ1". 1046 4.1.4. ServerHello extension KeyShareServerHello 1048 The server responds with a "KeyShareServerHello" struct containing a 1049 single "KeyShareEntry", which contains a single "NamedGroup" value 1050 and an opaque "key_exchange" string. 1052 To complete the negotiation of a hybrid algorithm, the server 1053 responds with the "NamedGroup" value being the "hybrid_marker" code 1054 point correspond to the combination that the server was willing to 1055 agree to. 1057 The "key_exchange" string is the octet representation of the 1058 following struct: 1060 struct { 1061 KeyShareEntry key_share<2..10>; 1062 } HybridKeyShare; 1064 where there is one "key_share" entry for each of the components of 1065 this hybrid combination. 1067 Note that the "key_exchange" string has a maximum length of 2^16-1 1068 octets, which may be insufficient for some post-quantum algorithms or 1069 for some hybridizations of multiple post-quantum algorithms. It 1070 remains an open question as to whether this length can be increased 1071 without breaking existing TLS 1.3 implementations. 1073 4.1.5. Key schedule 1075 The component algorithm shared secrets are combined by concatenating 1076 them, then applying a key derivation function, the output of which is 1077 then used in the TLS 1.3 key schedule in place of the (EC)DHE shared 1078 secret. The component shared secrets are concatenated in the order 1079 that they appear in the "components" vector of the "HybridMapping" 1080 extension above. 1082 We provide two options for concatenating the shared secrets, and 1083 would like feedback from the working group in which to proceed with. 1085 Each component algorithm's "shared_secret" is defined by the 1086 algorithm itself, for example the DHE or ECDHE shared secrets as 1087 defined in Section 7.4 of [TLS13], or as defined by post-quantum 1088 methods once standardized in their own documents. 1090 *Option 1: Using data structures.* Option 1 uses a full-fledged TLS 1091 1.3 data structure to represent the list of component shared secrets. 1092 As a result, lengths of each shared secret are unambiguously encoded. 1094 struct SharedSecret { 1095 opaque shared_secret<0..2^16-1>; 1096 } 1098 struct { 1099 SharedSecret component<2..10>; 1100 } HybridSharedSecret; 1102 The "concatenated_shared_secret" is then the octet representation of 1103 the "HybridSharedSecret " struct. 1105 *Option 2: Direct concatenation.* Option 2 directly concatenates the 1106 shared secrets. Option 2 should only be considered if the shared 1107 secret for each algorithm is guarantees to be of a fixed length, 1108 which would imply that, once the component algorithms are fixed, 1109 concatenation is bijective. 1111 concatenated_shared_secret = shared_secret0 | shared_secret1 | ... 1113 In either option, the "concatenated_shared_secret" octet string is 1114 used as the IKM argument of HKDF-Extract, with the zero-length string 1115 as the salt argument. THe output of HKDF-Extract is used as the IKM 1116 argument for HKDF-Extract's calculation of the handshake secret, as 1117 shown below. 1119 0 1120 | 1121 v 1122 PSK -> HKDF-Extract = Early Secret 1123 | 1124 +-----> Derive-Secret(...) 1125 +-----> Derive-Secret(...) 1126 +-----> Derive-Secret(...) 1127 | 1128 v 1129 concatenated 0 1130 shared | 1131 secret -> HKDF-Extract Derive-Secret(., "derived", "") 1132 ^^^^^^ | | 1133 v v 1134 output -----> HKDF-Extract = Handshake Secret 1135 ^^^^^^ | 1136 +-----> Derive-Secret(...) 1137 +-----> Derive-Secret(...) 1138 | 1139 v 1140 Derive-Secret(., "derived", "") 1141 | 1142 v 1143 0 -> HKDF-Extract = Master Secret 1144 | 1145 +-----> Derive-Secret(...) 1146 +-----> Derive-Secret(...) 1147 +-----> Derive-Secret(...) 1148 +-----> Derive-Secret(...) 1150 4.2. Candidate Instantiation 2 1152 Candidate Instantiation 2 allows for exactly two component algorithms 1153 to be combined (Num-2) (Section 3.2.1), and uses code points 1154 standardized for each permissible combination. The client 1155 concatenates its multiple key shares together as a distinct entry in 1156 the "client_shares" vector of the "ClientHello" "key_share" extension 1157 (Shares-Concat) (Section 3.3.1). The server does the same. The 1158 shared secrets are combined by concatenating them then feeding them 1159 through a KDF, then feeding the result into the TLS 1.3 key schedule 1160 (Comb-KDF-2) (Section 3.4.3). 1162 4.2.1. ClientHello extension supported_groups 1164 The "NamedGroup" enum used by the client to populate the 1165 "supported_groups" extension is extended to include new code points 1166 representing each desired combination. 1168 For example, 1170 enum { 1171 /* existing named groups */ 1172 secp256r1 (23), 1173 x25519 (0x001D), 1174 ..., 1176 /* new code points eventually defined for post-quantum algorithms */ 1177 PQ1 (0x????), 1178 PQ2 (0x????), 1179 ..., 1181 /* new code points defined for hybrid combinations */ 1182 secp256r1_PQ1 (0x????), 1183 secp256r1_PQ2 (0x????), 1184 x25519_PQ1 (0x????), 1185 x25519_PQ2 (0x????), 1187 /* existing reserved code points */ 1188 ffdhe_private_use (0x01FC..0x01FF), 1189 ecdhe_private_use (0xFE00..0xFEFF), 1190 (0xFFFF) 1191 } NamedGroup; 1193 4.2.2. ClientHello extension KeyShareClientHello 1195 The client sends a "KeyShareClientHello" struct containing multiple 1196 "KeyShareEntry" values, some of which may correspond to some of the 1197 hybrid combination code points it listed in the "supported_groups" 1198 extension above. 1200 The "KeyShareEntry" for a hybrid combination code point contains an 1201 opaque "key_exchange" string which is the octet representation of the 1202 following struct: 1204 struct { 1205 KeyShareEntry key_share<2..10>; 1206 } HybridKeyShare; 1208 where there is one "key_share" entry for each of the components of 1209 this hybrid combination. 1211 Note that this approach may result in duplication of key shares being 1212 sent; for example, a client wanting to support either the combination 1213 "secp256r1_PQ1" or "x25519_PQ1" would send two "PQ1" key shares. 1215 4.2.3. ServerHello extension KeyShareServerHello 1217 The server responds with a "KeyShareServerHello" struct containing a 1218 single "KeyShareEntry", which contains a single "NamedGroup" value 1219 and an opaque "key_exchange" string. The "key_exchange" string is 1220 the octet representation of the "HybridKeyShare" struct defined 1221 above. 1223 4.2.4. Key schedule 1225 The key schedule is computed as in Candidate Instantiation 1 above. 1227 4.3. Comparing Candidate Instantiation 1 and 2 1229 CI2 requires much less change to negotiation routines - each hybrid 1230 combination is just a new key exchange method, and the concatenation 1231 of key shares and shared secrets can be handled internally to that 1232 method. This comes at the cost, however, of combinatorial explosion 1233 of code points: one code point needs to be standardized for each 1234 desired combination. We have also limited the number of hybrid 1235 algorithms to 2 in CI2 to somewhat limit the explosion of code points 1236 needing to be defined. Concatenating client key shares also risks 1237 sending duplicate key shares, increasing communication sizes. 1239 CI1 requires more change to negotiation routines, since it introduces 1240 new data structures and has an indirect mapping between hybrid 1241 combinations and key shares. Benefits from this approach include 1242 avoiding sending duplicate key shares and not needing to standardize 1243 every possible supported combination. Implementers, however, must do 1244 the work of deciding which combinations of algorithms are meaningful 1245 / tolerable / desirable from a security perspective, potentially 1246 complicating interoperability. 1248 5. IANA Considerations 1250 If Candidate Instantiation 1 is selected, the TLS Supported Groups 1251 registry will have to be updated to include code points for hybrid 1252 markers. 1254 6. Security Considerations 1256 The majority of this document is about security considerations. As 1257 noted especially in Section 3.4, the shared secrets computed in the 1258 hybrid key exchange should be computed in a way that achieves the 1259 "hybrid" property: the resulting secret is secure as long as at least 1260 one of the component key exchange algorithms is unbroken. While many 1261 natural approaches seem to achieve this, there can be subtleties (see 1262 for example the introduction of [GIACON]). 1264 The rest of this section highlights a few unresolved questions 1265 related to security. 1267 6.1. Active security 1269 One security consideration that is not yet resolved is whether key 1270 encapsulation mechanisms used in TLS 1.3 must be secure against 1271 active attacks (IND-CCA), or whether security against passive attacks 1272 (IND-CPA) suffices. Existing security proofs of TLS 1.3 (such as 1273 [DFGS15], [DOWLING]) are formulated specifically around Diffie- 1274 Hellman and use an "actively secure" Diffie-Hellman assumption (PRF 1275 Oracle Diffie-Hellman (PRF-ODH)) rather than a "passively secure" DH 1276 assumption (e.g. decisional Diffie-Hellman (DDH)), but do not claim 1277 that the actively secure notion is required. In the context of TLS 1278 1.2, [KPW13] show that, at least in one formalization, a passively 1279 secure assumption like DDH is insufficient (even when signatures are 1280 used for mutual authentication). Resolving this issue for TLS 1.3 is 1281 an open question. 1283 6.2. Resumption 1285 TLS 1.3 allows for session resumption via a pre-shared key. When a 1286 pre-shared key is used during session establishment, an ephemeral key 1287 exchange can also be used to enhance forward secrecy. If the 1288 original key exchange was hybrid, should an ephemeral key exchange in 1289 a resumption of that original key exchange be required to use the 1290 same hybrid algorithms? 1292 6.3. Failures 1294 Some post-quantum key exchange algorithms have non-trivial failure 1295 rates: two honest parties may fail to agree on the same shared secret 1296 with non-negligible probability. Does a non-negligible failure rate 1297 affect the security of TLS? How should such a failure be treated 1298 operationally? What is an acceptable failure rate? 1300 7. Acknowledgements 1302 These ideas have grown from discussions with many colleagues, 1303 including Christopher Wood, Matt Campagna, and authors of the various 1304 hybrid Internet-Drafts and implementations cited in this document. 1305 The immediate impetus for this document came from discussions with 1306 attendees at the Workshop on Post-Quantum Software in Mountain View, 1307 California, in January 2019. 1309 Martin Thomson suggested the (Comb-KDF-1) (Section 3.4.2) approach. 1311 8. References 1313 8.1. Normative References 1315 [TLS13] Rescorla, E., "The Transport Layer Security (TLS) Protocol 1316 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 1317 . 1319 8.2. Informative References 1321 [BCNS15] Bos, J., Costello, C., Naehrig, M., and D. Stebila, "Post- 1322 Quantum Key Exchange for the TLS Protocol from the Ring 1323 Learning with Errors Problem", 2015 IEEE Symposium on 1324 Security and Privacy, DOI 10.1109/sp.2015.40, May 2015. 1326 [BERNSTEIN] 1327 "Post-Quantum Cryptography", Springer Berlin 1328 Heidelberg book, DOI 10.1007/978-3-540-88702-7, 2009. 1330 [BINDEL] Bindel, N., Brendel, J., Fischlin, M., Goncalves, B., and 1331 D. Stebila, "Hybrid Key Encapsulation Mechanisms and 1332 Authenticated Key Exchange", Post-Quantum Cryptography 1333 (PQCrypto) , 2019, . 1335 [CECPQ1] Braithwaite, M., "Experimenting with Post-Quantum 1336 Cryptography", July 2016, 1337 . 1340 [CECPQ2] Langley, A., "CECPQ2", December 2018, 1341 . 1343 [DFGS15] Dowling, B., Fischlin, M., Guenther, F., and D. Stebila, 1344 "A Cryptographic Analysis of the TLS 1.3 Handshake 1345 Protocol Candidates", Proceedings of the 22nd ACM SIGSAC 1346 Conference on Computer and Communications Security - 1347 CCS '15, DOI 10.1145/2810103.2813653, 2015. 1349 [DODIS] Dodis, Y. and J. Katz, "Chosen-Ciphertext Security of 1350 Multiple Encryption", Theory of Cryptography pp. 188-209, 1351 DOI 10.1007/978-3-540-30576-7_11, 2005. 1353 [DOWLING] Dowling, B., "Provable Security of Internet Protocols", 1354 Queensland University of Technology dissertation, 1355 DOI 10.5204/thesis.eprints.108960, n.d.. 1357 [ETSI] Campagna, M., Ed. and . others, "Quantum safe cryptography 1358 and security: An introduction, benefits, enablers and 1359 challengers", ETSI White Paper No. 8 , June 2015, 1360 . 1363 [EVEN] Even, S. and O. Goldreich, "On the Power of Cascade 1364 Ciphers", Advances in Cryptology pp. 43-50, 1365 DOI 10.1007/978-1-4684-4730-9_4, 1984. 1367 [EXTERN-PSK] 1368 Housley, R., "TLS 1.3 Extension for Certificate-based 1369 Authentication with an External Pre-Shared Key", draft- 1370 ietf-tls-tls13-cert-with-extern-psk-02 (work in progress), 1371 May 2019. 1373 [FRODO] Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, 1374 M., Nikolaenko, V., Raghunathan, A., and D. Stebila, 1375 "Frodo", Proceedings of the 2016 ACM SIGSAC Conference on 1376 Computer and Communications Security - CCS'16, 1377 DOI 10.1145/2976749.2978425, 2016. 1379 [GIACON] Giacon, F., Heuer, F., and B. Poettering, "KEM Combiners", 1380 Public-Key Cryptography - PKC 2018 pp. 190-218, 1381 DOI 10.1007/978-3-319-76578-5_7, 2018. 1383 [HARNIK] Harnik, D., Kilian, J., Naor, M., Reingold, O., and A. 1384 Rosen, "On Robust Combiners for Oblivious Transfer and 1385 Other Primitives", Lecture Notes in Computer Science pp. 1386 96-113, DOI 10.1007/11426639_6, 2005. 1388 [HOFFMAN] Hoffman, P., "The Transition from Classical to Post- 1389 Quantum Cryptography", draft-hoffman-c2pq-05 (work in 1390 progress), May 2019. 1392 [IKE-HYBRID] 1393 Tjhai, C., Tomlinson, M., grbartle@cisco.com, g., Fluhrer, 1394 S., Geest, D., Garcia-Morchon, O., and V. Smyslov, 1395 "Framework to Integrate Post-quantum Key Exchanges into 1396 Internet Key Exchange Protocol Version 2 (IKEv2)", draft- 1397 tjhai-ipsecme-hybrid-qske-ikev2-03 (work in progress), 1398 January 2019. 1400 [IKE-PSK] Fluhrer, S., McGrew, D., Kampanakis, P., and V. Smyslov, 1401 "Postquantum Preshared Keys for IKEv2", draft-ietf- 1402 ipsecme-qr-ikev2-08 (work in progress), March 2019. 1404 [KIEFER] Kiefer, F. and K. Kwiatkowski, "Hybrid ECDHE-SIDH Key 1405 Exchange for TLS", draft-kiefer-tls-ecdhe-sidh-00 (work in 1406 progress), November 2018. 1408 [KPW13] Krawczyk, H., Paterson, K., and H. Wee, "On the Security 1409 of the TLS Protocol: A Systematic Analysis", Advances in 1410 Cryptology - CRYPTO 2013 pp. 429-448, 1411 DOI 10.1007/978-3-642-40041-4_24, 2013. 1413 [LANGLEY] Langley, A., "Post-quantum confidentiality for TLS", April 1414 2018, . 1417 [NIELSEN] Nielsen, M. and I. Chuang, "Quantum Computation and 1418 Quantum Information", Cambridge University Press , 2000. 1420 [NIST] National Institute of Standards and Technology (NIST), 1421 "Post-Quantum Cryptography", n.d., 1422 . 1424 [NIST-SP-800-135] 1425 National Institute of Standards and Technology (NIST), 1426 "Recommendation for Existing Application-Specific Key 1427 Derivation Functions", December 2011, 1428 . 1430 [NIST-SP-800-56C] 1431 National Institute of Standards and Technology (NIST), 1432 "Recommendation for Key-Derivation Methods in Key- 1433 Establishment Schemes", April 2018, 1434 . 1436 [OQS-102] Open Quantum Safe Project, "OQS-OpenSSL-1-0-2_stable", 1437 November 2018, . 1440 [OQS-111] Open Quantum Safe Project, "OQS-OpenSSL-1-1-1_stable", 1441 November 2018, . 1444 [SCHANCK] Schanck, J. and D. Stebila, "A Transport Layer Security 1445 (TLS) Extension For Establishing An Additional Shared 1446 Secret", draft-schanck-tls-additional-keyshare-00 (work in 1447 progress), April 2017. 1449 [WHYTE12] Schanck, J., Whyte, W., and Z. Zhang, "Quantum-Safe Hybrid 1450 (QSH) Ciphersuite for Transport Layer Security (TLS) 1451 version 1.2", draft-whyte-qsh-tls12-02 (work in progress), 1452 July 2016. 1454 [WHYTE13] Whyte, W., Zhang, Z., Fluhrer, S., and O. Garcia-Morchon, 1455 "Quantum-Safe Hybrid (QSH) Key Exchange for Transport 1456 Layer Security (TLS) version 1.3", draft-whyte-qsh- 1457 tls13-06 (work in progress), October 2017. 1459 [XMSS] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. 1460 Mohaisen, "XMSS: eXtended Merkle Signature Scheme", 1461 RFC 8391, DOI 10.17487/RFC8391, May 2018, 1462 . 1464 [ZHANG] Zhang, R., Hanaoka, G., Shikata, J., and H. Imai, "On the 1465 Security of Multiple Encryption or CCA-security+CCA- 1466 security=CCA-security?", Public Key Cryptography - PKC 1467 2004 pp. 360-374, DOI 10.1007/978-3-540-24632-9_26, 2004. 1469 Authors' Addresses 1471 Douglas Stebila 1472 University of Waterloo 1474 Email: dstebila@uwaterloo.ca 1476 Scott Fluhrer 1477 Cisco Systems 1479 Email: sfluhrer@cisco.com 1481 Shay Gueron 1482 University of Haifa and Amazon Web Services 1484 Email: shay.gueron@gmail.com