idnits 2.17.1 draft-stebila-tls-hybrid-design-03.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 : ---------------------------------------------------------------------------- ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 352: '... this document MUST explicitly be de...' RFC 2119 keyword, line 356: '...ons that do reuse KEM public keys MUST...' RFC 2119 keyword, line 359: '... Implementations MUST NOT reuse random...' RFC 2119 keyword, line 610: '...ed in this document MUST explicitly be...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 12, 2020) is 1532 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 ---------------------------------------------------------------------------- == Unused Reference: 'DFGS15' is defined on line 663, but no explicit reference was found in the text == Unused Reference: 'DOWLING' is defined on line 673, but no explicit reference was found in the text == Unused Reference: 'KPW13' is defined on line 752, but no explicit reference was found in the text == Outdated reference: A later version (-07) exists of draft-hoffman-c2pq-06 == Outdated reference: A later version (-12) exists of draft-irtf-cfrg-hpke-02 Summary: 1 error (**), 0 flaws (~~), 6 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: August 15, 2020 Cisco Systems 6 S. Gueron 7 U. Haifa, Amazon Web Services 8 February 12, 2020 10 Hybrid key exchange in TLS 1.3 11 draft-stebila-tls-hybrid-design-03 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 It is motivated by transition to post-quantum cryptography. This 19 document provides a construction for hybrid key exchange in the 20 Transport Layer Security (TLS) protocol version 1.3. 22 Discussion of this work is encouraged to happen on the TLS IETF 23 mailing list tls@ietf.org or on the GitHub repository which contains 24 the draft: https://github.com/dstebila/draft-stebila-tls-hybrid- 25 design. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at https://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on August 15, 2020. 44 Copyright Notice 46 Copyright (c) 2020 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (https://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the Simplified BSD License. 59 Table of Contents 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 62 1.1. Revision history . . . . . . . . . . . . . . . . . . . . 3 63 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 64 1.3. Motivation for use of hybrid key exchange . . . . . . . . 5 65 1.4. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 5 66 1.5. Goals . . . . . . . . . . . . . . . . . . . . . . . . . . 6 67 2. Key encapsulation mechanisms . . . . . . . . . . . . . . . . 7 68 3. Construction for hybrid key exchange . . . . . . . . . . . . 8 69 3.1. Negotiation . . . . . . . . . . . . . . . . . . . . . . . 8 70 3.2. Transmitting public keys and ciphertexts . . . . . . . . 9 71 3.3. Shared secret calculation . . . . . . . . . . . . . . . . 10 72 4. Open questions . . . . . . . . . . . . . . . . . . . . . . . 12 73 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 74 6. Security Considerations . . . . . . . . . . . . . . . . . . . 13 75 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 14 76 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 14 77 8.1. Normative References . . . . . . . . . . . . . . . . . . 14 78 8.2. Informative References . . . . . . . . . . . . . . . . . 14 79 Appendix A. Related work . . . . . . . . . . . . . . . . . . . . 18 80 Appendix B. Design Considerations . . . . . . . . . . . . . . . 19 81 B.1. (Neg) How to negotiate hybridization and component 82 algorithms? . . . . . . . . . . . . . . . . . . . . . . . 21 83 B.1.1. Key exchange negotiation in TLS 1.3 . . . . . . . . . 21 84 B.1.2. (Neg-Ind) Negotiating component algorithms 85 individually . . . . . . . . . . . . . . . . . . . . 21 86 B.1.3. (Neg-Comb) Negotiating component algorithms as a 87 combination . . . . . . . . . . . . . . . . . . . . . 22 88 B.1.4. Benefits and drawbacks . . . . . . . . . . . . . . . 23 89 B.2. (Num) How many component algorithms to combine? . . . . . 24 90 B.2.1. (Num-2) Two . . . . . . . . . . . . . . . . . . . . . 24 91 B.2.2. (Num-2+) Two or more . . . . . . . . . . . . . . . . 24 92 B.2.3. Benefits and Drawbacks . . . . . . . . . . . . . . . 24 93 B.3. (Shares) How to convey key shares? . . . . . . . . . . . 24 94 B.3.1. (Shares-Concat) Concatenate key shares . . . . . . . 25 95 B.3.2. (Shares-Multiple) Send multiple key shares . . . . . 25 96 B.3.3. (Shares-Ext-Additional) Extension carrying additional 97 key shares . . . . . . . . . . . . . . . . . . . . . 25 98 B.3.4. Benefits and Drawbacks . . . . . . . . . . . . . . . 25 99 B.4. (Comb) How to use keys? . . . . . . . . . . . . . . . . . 26 100 B.4.1. (Comb-Concat) Concatenate keys . . . . . . . . . . . 26 101 B.4.2. (Comb-KDF-1) KDF keys . . . . . . . . . . . . . . . . 27 102 B.4.3. (Comb-KDF-2) KDF keys . . . . . . . . . . . . . . . . 28 103 B.4.4. (Comb-XOR) XOR keys . . . . . . . . . . . . . . . . . 29 104 B.4.5. (Comb-Chain) Chain of KDF applications for each key . 30 105 B.4.6. (Comb-AltInput) Second shared secret in an alternate 106 KDF input . . . . . . . . . . . . . . . . . . . . . . 31 107 B.4.7. Benefits and Drawbacks . . . . . . . . . . . . . . . 31 108 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 32 110 1. Introduction 112 This document gives a construction for hybrid key exchange in TLS 113 1.3. The overall design approach is a simple, "concatenation"-based 114 approach: each hybrid key exchange combination should be viewed as a 115 single new key exchange method, negotiated and transmitted using the 116 existing TLS 1.3 mechanisms. 118 This document does not propose specific post-quantum mechanisms; see 119 Section 1.4 for more on the scope of this document. 121 1.1. Revision history 123 *RFC Editor's Note:* Please remove this section prior to 124 publication of a final version of this document. 126 Earlier versions of this document categorized various design 127 decisions one could make when implementing hybrid key exchange in TLS 128 1.3. These have been moved to the appendix of the current draft, and 129 will be eventually be removed. 131 o draft-03: 133 * Add requirement for KEMs to provide protection against key 134 reuse. 136 * Clarify FIPS-compliance of shared secret concatenation method. 138 o draft-02: 140 * Design considerations from draft-00 and draft-01 are moved to 141 the appendix. 143 * A single construction is given in the main body. 145 o draft-01: 147 * Add (Comb-KDF-1) (Appendix B.4.2) and (Comb-KDF-2) 148 (Appendix B.4.3) options. 150 * Add two candidate instantiations. 152 o draft-00: Initial version. 154 1.2. Terminology 156 For the purposes of this document, it is helpful to be able to divide 157 cryptographic algorithms into two classes: 159 o "Traditional" algorithms: Algorithms which are widely deployed 160 today, but which may be deprecated in the future. In the context 161 of TLS 1.3 in 2019, examples of traditional key exchange 162 algorithms include elliptic curve Diffie-Hellman using secp256r1 163 or x25519, or finite-field Diffie-Hellman. 165 o "Next-generation" (or "next-gen") algorithms: Algorithms which are 166 not yet widely deployed, but which may eventually be widely 167 deployed. An additional facet of these algorithms may be that we 168 have less confidence in their security due to them being 169 relatively new or less studied. This includes "post-quantum" 170 algorithms. 172 "Hybrid" key exchange, in this context, means the use of two (or 173 more) key exchange algorithms based on different cryptographic 174 assumptions, e.g., one traditional algorithm and one next-gen 175 algorithm, with the purpose of the final session key being secure as 176 long as at least one of the component key exchange algorithms remains 177 unbroken. We use the term "component" algorithms to refer to the 178 algorithms combined in a hybrid key exchange. 180 The primary motivation of this document is preparing for post-quantum 181 algorithms. However, it is possible that public key cryptography 182 based on alternative mathematical constructions will be required 183 independent of the advent of a quantum computer, for example because 184 of a cryptanalytic breakthrough. As such we opt for the more generic 185 term "next-generation" algorithms rather than exclusively "post- 186 quantum" algorithms. 188 Note that TLS 1.3 uses the phrase "groups" to refer to key exchange 189 algorithms - for example, the "supported_groups" extension - since 190 all key exchange algorithms in TLS 1.3 are Diffie-Hellman-based. As 191 a result, some parts of this document will refer to data structures 192 or messages with the term "group" in them despite using a key 193 exchange algorithm that is not Diffie-Hellman-based nor a group. 195 1.3. Motivation for use of hybrid key exchange 197 A hybrid key exchange algorithm allows early adopters eager for post- 198 quantum security to have the potential of post-quantum security 199 (possibly from a less-well-studied algorithm) while still retaining 200 at least the security currently offered by traditional algorithms. 201 They may even need to retain traditional algorithms due to regulatory 202 constraints, for example FIPS compliance. 204 Ideally, one would not use hybrid key exchange: one would have 205 confidence in a single algorithm and parameterization that will stand 206 the test of time. However, this may not be the case in the face of 207 quantum computers and cryptanalytic advances more generally. 209 Many (though not all) post-quantum algorithms currently under 210 consideration are relatively new; they have not been subject to the 211 same depth of study as RSA and finite-field or elliptic curve Diffie- 212 Hellman, and thus the security community does not necessarily have as 213 much confidence in their fundamental security, or the concrete 214 security level of specific parameterizations. 216 Moreover, it is possible that even by the end of the NIST Post- 217 Quantum Cryptography Standardization Project, and for a period of 218 time thereafter, conservative users may not have full confidence in 219 some algorithms. 221 As such, there may be users for whom hybrid key exchange is an 222 appropriate step prior to an eventual transition to next-generation 223 algorithms. 225 1.4. Scope 227 This document focuses on hybrid ephemeral key exchange in TLS 1.3 228 [TLS13]. It intentionally does not address: 230 o Selecting which next-generation algorithms to use in TLS 1.3, nor 231 algorithm identifiers nor encoding mechanisms for next-generation 232 algorithms. This selection will be based on the recommendations 233 by the Crypto Forum Research Group (CFRG), which is currently 234 waiting for the results of the NIST Post-Quantum Cryptography 235 Standardization Project [NIST]. 237 o Authentication using next-generation algorithms. If a 238 cryptographic assumption is broken due to the advent of a quantum 239 computer or some other cryptanalytic breakthrough, confidentiality 240 of information can be broken retroactively by any adversary who 241 has passively recorded handshakes and encrypted communications. 242 In contrast, session authentication cannot be retroactively 243 broken. 245 1.5. Goals 247 The primary goal of a hybrid key exchange mechanism is to facilitate 248 the establishment of a shared secret which remains secure as long as 249 as one of the component key exchange mechanisms remains unbroken. 251 In addition to the primary cryptographic goal, there may be several 252 additional goals in the context of TLS 1.3: 254 o *Backwards compatibility:* Clients and servers who are "hybrid- 255 aware", i.e., compliant with whatever hybrid key exchange standard 256 is developed for TLS, should remain compatible with endpoints and 257 middle-boxes that are not hybrid-aware. The three scenarios to 258 consider are: 260 1. Hybrid-aware client, hybrid-aware server: These parties should 261 establish a hybrid shared secret. 263 2. Hybrid-aware client, non-hybrid-aware server: These parties 264 should establish a traditional shared secret (assuming the 265 hybrid-aware client is willing to downgrade to traditional- 266 only). 268 3. Non-hybrid-aware client, hybrid-aware server: These parties 269 should establish a traditional shared secret (assuming the 270 hybrid-aware server is willing to downgrade to traditional- 271 only). 273 Ideally backwards compatibility should be achieved without extra 274 round trips and without sending duplicate information; see below. 276 o *High performance:* Use of hybrid key exchange should not be 277 prohibitively expensive in terms of computational performance. In 278 general this will depend on the performance characteristics of the 279 specific cryptographic algorithms used, and as such is outside the 280 scope of this document. See [BCNS15], [CECPQ1], [FRODO] for 281 preliminary results about performance characteristics. 283 o *Low latency:* Use of hybrid key exchange should not substantially 284 increase the latency experienced to establish a connection. 285 Factors affecting this may include the following. 287 * The computational performance characteristics of the specific 288 algorithms used. See above. 290 * The size of messages to be transmitted. Public key and 291 ciphertext sizes for post-quantum algorithms range from 292 hundreds of bytes to over one hundred kilobytes, so this impact 293 can be substantially. See [BCNS15], [FRODO] for preliminary 294 results in a laboratory setting, and [LANGLEY] for preliminary 295 results on more realistic networks. 297 * Additional round trips added to the protocol. See below. 299 o *No extra round trips:* Attempting to negotiate hybrid key 300 exchange should not lead to extra round trips in any of the three 301 hybrid-aware/non-hybrid-aware scenarios listed above. 303 o *Minimal duplicate information:* Attempting to negotiate hybrid 304 key exchange should not mean having to send multiple public keys 305 of the same type. 307 2. Key encapsulation mechanisms 309 In the context of the NIST Post-Quantum Cryptography Standardization 310 Project, key exchange algorithms are formulated as key encapsulation 311 mechanisms (KEMs), which consist of three algorithms: 313 o "KeyGen() -> (pk, sk)": A probabilistic key generation algorithm, 314 which generates a public key "pk" and a secret key "sk". 316 o "Encaps(pk) -> (ct, ss)": A probabilistic encapsulation algorithm, 317 which takes as input a public key "pk" and outputs a ciphertext 318 "ct" and shared secret "ss". 320 o "Decaps(sk, ct) -> ss": A decapsulation algorithm, which takes as 321 input a secret key "sk" and ciphertext "ct" and outputs a shared 322 secret "ss", or in some cases a distinguished error value. 324 The main security property for KEMs is indistinguishability under 325 adaptive chosen ciphertext attack (IND-CCA2), which means that shared 326 secret values should be indistinguishable from random strings even 327 given the ability to have arbitrary ciphertexts decapsulated. IND- 328 CCA2 corresponds to security against an active attacker, and the 329 public key / secret key pair can be treated as a long-term key or 330 reused. A common design pattern for obtaining security under key 331 reuse is to apply the Fujisaki-Okamoto (FO) transform [FO] or a 332 variant thereof [HHK]. 334 A weaker security notion is indistinguishability under chosen 335 plaintext attack (IND-CPA), which means that the shared secret values 336 should be indistinguishable from random strings given a copy of the 337 public key. IND-CPA roughly corresponds to security against a 338 passive attacker, and sometimes corresponds to one-time key exchange. 340 Key exchange in TLS 1.3 is phrased in terms of Diffie-Hellman key 341 exchange in a group. DH key exchange can be modeled as a KEM, with 342 "KeyGen" corresponding to selecting an exponent "x" as the secret key 343 and computing the public key "g^x"; encapsulation corresponding to 344 selecting an exponent "y", computing the ciphertext "g^y" and the 345 shared secret "g^(xy)", and decapsulation as computing the shared 346 secret "g^(xy)". See [I-D.irtf-cfrg-hpke] for more details of such 347 Diffie-Hellman-based key encapsulation mechanisms. 349 TLS 1.3 does not require that ephemeral public keys be used only in a 350 single key exchange session; some implementations may reuse them, at 351 the cost of limited forward secrecy. As a result, any KEM used in 352 this document MUST explicitly be designed to be secure in the event 353 that the public key is re-used, such as achieving IND-CCA2 security 354 or having a transform like the Fujisaki-Okamoto transform [FO] [HHK] 355 applied. While it is recommended that implementations avoid reuse of 356 KEM public keys, implementations that do reuse KEM public keys MUST 357 ensure that the number of reuses of a KEM public key abides by any 358 bounds in the specification of the KEM or subsequent security 359 analyses. Implementations MUST NOT reuse randomness in the 360 generation of KEM ciphertexts. 362 3. Construction for hybrid key exchange 364 3.1. Negotiation 366 Each particular combination of algorithms in a hybrid key exchange 367 will be represented as a "NamedGroup" and sent in the 368 "supported_groups" extension. No internal structure or grammar is 369 implied or required in the value of the identifier; they are simply 370 opaque identifiers. 372 Each value representing a hybrid key exchange will correspond to an 373 ordered pair of two algorithms. For example, a future document could 374 specify that hybrid value 0x2000 corresponds to 375 secp256r1+ntruhrss701, and 0x2001 corresponds to x25519+ntruhrss701. 376 (We note that this is independent from future documents standardizing 377 solely post-quantum key exchange methods, which would have to be 378 assigned their own identifier.) 380 Specific values shall be standardized by IANA in the TLS Supported 381 Groups registry. We suggest that values 0x2000 through 0x2EFF are 382 suitable for hybrid key exchange methods (the leading "2" suggesting 383 that there are 2 algorithms), noting that 0x2A2A is reserved as a 384 GREASE value [GREASE]. This document requests that values 0x2F00 385 through 0x2FFF be reserved for Private Use for hybrid key exchange. 387 enum { 389 /* Elliptic Curve Groups (ECDHE) */ 390 secp256r1(0x0017), secp384r1(0x0018), secp521r1(0x0019), 391 x25519(0x001D), x448(0x001E), 393 /* Finite Field Groups (DHE) */ 394 ffdhe2048(0x0100), ffdhe3072(0x0101), ffdhe4096(0x0102), 395 ffdhe6144(0x0103), ffdhe8192(0x0104), 397 /* Hybrid Key Exchange Methods */ 398 TBD(0xTBD), ..., 400 /* Reserved Code Points */ 401 ffdhe_private_use(0x01FC..0x01FF), 402 hybrid_private_use(0x2F00..0x2FFF), 403 ecdhe_private_use(0xFE00..0xFEFF), 404 (0xFFFF) 405 } NamedGroup; 407 3.2. Transmitting public keys and ciphertexts 409 We take the relatively simple "concatenation approach": the messages 410 from the two algorithms being hybridized will be concatenated 411 together and transmitted as a single value, to avoid having to change 412 existing data structures. However we do add structure in the 413 concatenation procedure, specifically including length fields, so 414 that the concatenation operation is unambiguous. Note that among the 415 Round 2 candidates in the NIST Post-Quantum Cryptography 416 Standardization Project, not all algorithms have fixed public key 417 sizes; for example, the SIKE key encapsulation mechanism permits 418 compressed or uncompressed public keys at each security level, and 419 the compressed and uncompressed formats are interoperable. 421 Recall that in TLS 1.3 a KEM public key or KEM ciphertext is 422 represented as a "KeyShareEntry": 424 struct { 425 NamedGroup group; 426 opaque key_exchange<1..2^16-1>; 427 } KeyShareEntry; 429 These are transmitted in the "extension_data" fields of 430 "KeyShareClientHello" and "KeyShareServerHello" extensions: 432 struct { 433 KeyShareEntry client_shares<0..2^16-1>; 434 } KeyShareClientHello; 436 struct { 437 KeyShareEntry server_share; 438 } KeyShareServerHello; 440 The client's shares are listed in descending order of client 441 preference; the server selects one algorithm and sends its 442 corresponding share. 444 For a hybrid key exchange, the "key_exchange" field of a 445 "KeyShareEntry" is the following data structure: 447 struct { 448 opaque key_exchange_1<1..2^16-1>; 449 opaque key_exchange_2<1..2^16-1>; 450 } HybridKeyExchange 452 The order of shares in the "HybridKeyExchange" struct is the same as 453 the order of algorithms indicated in the definition of the 454 "NamedGroup". 456 For the client's share, the "key_exchange_1" and "key_exchange_2" 457 values are the "pk" outputs of the corresponding KEMs' "KeyGen" 458 algorithms, if that algorithm corresponds to a KEM; or the (EC)DH 459 ephemeral key share, if that algorithm corresponds to an (EC)DH 460 group. For the server's share, the "key_exchange_1" and 461 "key_exchange_2" values are the "ct" outputs of the corresponding 462 KEMs' "Encaps" algorithms, if that algorithm corresponds to a KEM; or 463 the (EC)DH ephemeral key share, if that algorithm corresponds to an 464 (EC)DH group. 466 3.3. Shared secret calculation 468 Here we also take a simple "concatenation approach": the two shared 469 secrets are concatenated together and used as the shared secret in 470 the existing TLS 1.3 key schedule. In this case, we do not add any 471 additional structure (length fields) in the concatenation procedure: 472 among all Round 2 candidates, once the algorithm and variant are 473 specified, the shared secret output length is fixed. 475 In other words, the shared secret is calculated as 476 concatenated_shared_secret = shared_secret_1 || shared_secret_2 478 and inserted into the TLS 1.3 key schedule in place of the (EC)DHE 479 shared secret: 481 0 482 | 483 v 484 PSK -> HKDF-Extract = Early Secret 485 | 486 +-----> Derive-Secret(...) 487 +-----> Derive-Secret(...) 488 +-----> Derive-Secret(...) 489 | 490 v 491 Derive-Secret(., "derived", "") 492 | 493 v 494 concatenated_shared_secret -> HKDF-Extract = Handshake Secret 495 ^^^^^^^^^^^^^^^^^^^^^^^^^^ | 496 +-----> Derive-Secret(...) 497 +-----> Derive-Secret(...) 498 | 499 v 500 Derive-Secret(., "derived", "") 501 | 502 v 503 0 -> HKDF-Extract = Master Secret 504 | 505 +-----> Derive-Secret(...) 506 +-----> Derive-Secret(...) 507 +-----> Derive-Secret(...) 508 +-----> Derive-Secret(...) 510 *FIPS-compliance of shared secret concatenation.* [NIST-SP-800-56C] 511 or [NIST-SP-800-135] give NIST recommendations for key derivation 512 methods in key exchange protocols. Some hybrid combinations may 513 combine the shared secret from a NIST-approved algorithm (e.g., ECDH 514 using the nistp256/secp256r1 curve) with a shared secret from a non- 515 approved algorithm (e.g., post-quantum). Although the simple 516 concatenation approach above is not currently an approved method in 517 [NIST-SP-800-56C] or [NIST-SP-800-135], NIST indicated in January 518 2020 that a forthcoming revision of [NIST-SP-800-56C] will list 519 simple concatenation as an approved method [NIST-FAQ]. 521 4. Open questions 523 *Larger public keys and/or ciphertexts.* The "HybridKeyExchange" 524 struct in Section 3.2 limits public keys and ciphertexts to 2^16-1 525 bytes; this is bounded by the same (2^16-1)-byte limit on the 526 "key_exchange" field in the "KeyShareEntry" struct. Some post- 527 quantum KEMs have larger public keys and/or ciphertexts; for example, 528 Classic McEliece's smallest parameter set has public key size 261,120 529 bytes. Hence this draft can not accommodate all current NIST Round 2 530 candidates. 532 If it is desired to accommodate algorithms with public keys or 533 ciphertexts larger than 2^16-1 bytes, options include a) revising the 534 TLS 1.3 standard to allow longer "key_exchange" fields; b) creating 535 an alternative extension which is sufficiently large; or c) providing 536 a reference to an external public key, e.g. a URL at which to look up 537 the public key (along with a hash to verify). 539 *Duplication of key shares.* Concatenation of public keys in the 540 "HybridKeyExchange" struct as described in Section 3.2 can result in 541 sending duplicate key shares. For example, if a client wanted to 542 offer support for two combinations, say "secp256r1+sikep503" and 543 "x25519+sikep503", it would end up sending two sikep503 public keys, 544 since the "KeyShareEntry" for each combination contains its own copy 545 of a sikep503 key. This duplication may be more problematic for 546 post-quantum algorithms which have larger public keys. 548 If it is desired to avoid duplication of key shares, options include 549 a) disconnect the use of a combination for the algorithm identifier 550 from the use of concatenation of public keys by introducing new logic 551 and/or data structures (see Appendix B.3.2 or Appendix B.3.3); or b) 552 provide some back reference from a later key share entry to an 553 earlier one. 555 *Variable-length shared secrets.* The shared secret calculation in 556 Section 3.3 directly concatenates the shared secret values of each 557 scheme, rather than encoding them with length fields. This 558 implicitly assumes that the length of each shared secret is fixed 559 once the algorithm is fixed. This is the case for all Round 2 560 candidates. 562 However, if it is envisioned that this specification be used with 563 algorithms which do not have fixed-length shared secrets (after the 564 variant has been fixed by the algorithm identifier in the 565 "NamedGroup" negotiation in Section 3.1), then Section 3.3 should be 566 revised to use an unambiguous concatenation method such as the 567 following: 569 struct { 570 opaque shared_secret_1<1..2^16-1>; 571 opaque shared_secret_2<1..2^16-1>; 572 } HybridSharedSecret 574 Guidance from the working group is particularly requested on this 575 point. 577 *Resumption.* TLS 1.3 allows for session resumption via a PSK. When 578 a PSK is used during session establishment, an ephemeral key exchange 579 can also be used to enhance forward secrecy. If the original key 580 exchange was hybrid, should an ephemeral key exchange in a resumption 581 of that original key exchange be required to use the same hybrid 582 algorithms? 584 *Failures.* Some post-quantum key exchange algorithms have non- 585 trivial failure rates: two honest parties may fail to agree on the 586 same shared secret with non-negligible probability. Does a non- 587 negligible failure rate affect the security of TLS? How should such 588 a failure be treated operationally? What is an acceptable failure 589 rate? 591 5. IANA Considerations 593 Identifiers for specific key exchange algorithm combinations will be 594 defined in later documents. This document requests IANA reserve 595 values 0x2F00..0x2FFF in the TLS Supported Groups registry for 596 private use for hybrid key exchange methods. 598 6. Security Considerations 600 The shared secrets computed in the hybrid key exchange should be 601 computed in a way that achieves the "hybrid" property: the resulting 602 secret is secure as long as at least one of the component key 603 exchange algorithms is unbroken. See [GIACON] and [BINDEL] for an 604 investigation of these issues. Under the assumption that shared 605 secrets are fixed length once the combination is fixed, the 606 construction from Section 3.3 corresponds to the dual-PRF combiner of 607 [BINDEL] which is shown to preserve security under the assumption 608 that the hash function is a dual-PRF. 610 As noted in Section 2, KEMs used in this document MUST explicitly be 611 designed to be secure in the event that the public key is re-used, 612 such as achieving IND-CCA2 security or having a transform like the 613 Fujisaki-Okamoto transform applied. Some IND-CPA-secure post-quantum 614 KEMs (i.e., without countermeasures such as the FO transform) are 615 completely insecure under public key reuse; for example, some 616 lattice-based IND-CPA-secure KEMs are vulnerable to attacks that 617 recover the private key after just a few thousand samples [FLUHRER]. 619 7. Acknowledgements 621 These ideas have grown from discussions with many colleagues, 622 including Christopher Wood, Matt Campagna, Eric Crockett, authors of 623 the various hybrid Internet-Drafts and implementations cited in this 624 document, and members of the TLS working group. The immediate 625 impetus for this document came from discussions with attendees at the 626 Workshop on Post-Quantum Software in Mountain View, California, in 627 January 2019. Martin Thomson suggested the (Comb-KDF-1) 628 (Appendix B.4.2) approach. Daniel J. Bernstein and Tanja Lange 629 commented on the risks of reuse of ephemeral public keys. 631 8. References 633 8.1. Normative References 635 [TLS13] Rescorla, E., "The Transport Layer Security (TLS) Protocol 636 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 637 . 639 8.2. Informative References 641 [BCNS15] Bos, J., Costello, C., Naehrig, M., and D. Stebila, "Post- 642 Quantum Key Exchange for the TLS Protocol from the Ring 643 Learning with Errors Problem", 2015 IEEE Symposium on 644 Security and Privacy, DOI 10.1109/sp.2015.40, May 2015. 646 [BERNSTEIN] 647 "Post-Quantum Cryptography", Springer Berlin 648 Heidelberg book, DOI 10.1007/978-3-540-88702-7, 2009. 650 [BINDEL] Bindel, N., Brendel, J., Fischlin, M., Goncalves, B., and 651 D. Stebila, "Hybrid Key Encapsulation Mechanisms and 652 Authenticated Key Exchange", Post-Quantum Cryptography pp. 653 206-226, DOI 10.1007/978-3-030-25510-7_12, 2019. 655 [CECPQ1] Braithwaite, M., "Experimenting with Post-Quantum 656 Cryptography", July 2016, 657 . 660 [CECPQ2] Langley, A., "CECPQ2", December 2018, 661 . 663 [DFGS15] Dowling, B., Fischlin, M., Guenther, F., and D. Stebila, 664 "A Cryptographic Analysis of the TLS 1.3 Handshake 665 Protocol Candidates", Proceedings of the 22nd ACM SIGSAC 666 Conference on Computer and Communications Security - 667 CCS '15, DOI 10.1145/2810103.2813653, 2015. 669 [DODIS] Dodis, Y. and J. Katz, "Chosen-Ciphertext Security of 670 Multiple Encryption", Theory of Cryptography pp. 188-209, 671 DOI 10.1007/978-3-540-30576-7_11, 2005. 673 [DOWLING] Dowling, B., "Provable Security of Internet Protocols", 674 Queensland University of Technology dissertation, 675 DOI 10.5204/thesis.eprints.108960, n.d.. 677 [ETSI] Campagna, M., Ed. and . others, "Quantum safe cryptography 678 and security: An introduction, benefits, enablers and 679 challengers", ETSI White Paper No. 8 , June 2015, 680 . 683 [EVEN] Even, S. and O. Goldreich, "On the Power of Cascade 684 Ciphers", Advances in Cryptology pp. 43-50, 685 DOI 10.1007/978-1-4684-4730-9_4, 1984. 687 [EXTERN-PSK] 688 Housley, R., "TLS 1.3 Extension for Certificate-based 689 Authentication with an External Pre-Shared Key", draft- 690 ietf-tls-tls13-cert-with-extern-psk-07 (work in progress), 691 December 2019. 693 [FLUHRER] Fluhrer, S., "Cryptanalysis of ring-LWE based key exchange 694 with key share reuse", Cryptology ePrint Archive, Report 695 2016/085 , January 2016, 696 . 698 [FO] Fujisaki, E. and T. Okamoto, "Secure Integration of 699 Asymmetric and Symmetric Encryption Schemes", Journal of 700 Cryptology Vol. 26, pp. 80-101, 701 DOI 10.1007/s00145-011-9114-1, December 2011. 703 [FRODO] Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, 704 M., Nikolaenko, V., Raghunathan, A., and D. Stebila, 705 "Frodo", Proceedings of the 2016 ACM SIGSAC Conference on 706 Computer and Communications Security - CCS'16, 707 DOI 10.1145/2976749.2978425, 2016. 709 [GIACON] Giacon, F., Heuer, F., and B. Poettering, "KEM Combiners", 710 Public-Key Cryptography - PKC 2018 pp. 190-218, 711 DOI 10.1007/978-3-319-76578-5_7, 2018. 713 [GREASE] Benjamin, D., "Applying GREASE to TLS Extensibility", 714 draft-ietf-tls-grease-04 (work in progress), August 2019. 716 [HARNIK] Harnik, D., Kilian, J., Naor, M., Reingold, O., and A. 717 Rosen, "On Robust Combiners for Oblivious Transfer and 718 Other Primitives", Lecture Notes in Computer Science pp. 719 96-113, DOI 10.1007/11426639_6, 2005. 721 [HHK] Hofheinz, D., Hoevelmanns, K., and E. Kiltz, "A Modular 722 Analysis of the Fujisaki-Okamoto Transformation", Theory 723 of Cryptography pp. 341-371, 724 DOI 10.1007/978-3-319-70500-2_12, 2017. 726 [HOFFMAN] Hoffman, P., "The Transition from Classical to Post- 727 Quantum Cryptography", draft-hoffman-c2pq-06 (work in 728 progress), November 2019. 730 [I-D.irtf-cfrg-hpke] 731 Barnes, R. and K. Bhargavan, "Hybrid Public Key 732 Encryption", draft-irtf-cfrg-hpke-02 (work in progress), 733 November 2019. 735 [IKE-HYBRID] 736 Tjhai, C., Tomlinson, M., grbartle@cisco.com, g., Fluhrer, 737 S., Geest, D., Garcia-Morchon, O., and V. Smyslov, 738 "Framework to Integrate Post-quantum Key Exchanges into 739 Internet Key Exchange Protocol Version 2 (IKEv2)", draft- 740 tjhai-ipsecme-hybrid-qske-ikev2-04 (work in progress), 741 July 2019. 743 [IKE-PSK] Fluhrer, S., Kampanakis, P., McGrew, D., and V. Smyslov, 744 "Mixing Preshared Keys in IKEv2 for Post-quantum 745 Security", draft-ietf-ipsecme-qr-ikev2-11 (work in 746 progress), January 2020. 748 [KIEFER] Kiefer, F. and K. Kwiatkowski, "Hybrid ECDHE-SIDH Key 749 Exchange for TLS", draft-kiefer-tls-ecdhe-sidh-00 (work in 750 progress), November 2018. 752 [KPW13] Krawczyk, H., Paterson, K., and H. Wee, "On the Security 753 of the TLS Protocol: A Systematic Analysis", Advances in 754 Cryptology - CRYPTO 2013 pp. 429-448, 755 DOI 10.1007/978-3-642-40041-4_24, 2013. 757 [LANGLEY] Langley, A., "Post-quantum confidentiality for TLS", April 758 2018, . 761 [NIELSEN] Nielsen, M. and I. Chuang, "Quantum Computation and 762 Quantum Information", Cambridge University Press , 2000. 764 [NIST] National Institute of Standards and Technology (NIST), 765 "Post-Quantum Cryptography", n.d., 766 . 768 [NIST-FAQ] 769 National Institute of Standards and Technology (NIST), 770 "Post-Quantum Cryptography - FAQs", January 2020, 771 . 774 [NIST-SP-800-135] 775 National Institute of Standards and Technology (NIST), 776 "Recommendation for Existing Application-Specific Key 777 Derivation Functions", December 2011, 778 . 780 [NIST-SP-800-56C] 781 National Institute of Standards and Technology (NIST), 782 "Recommendation for Key-Derivation Methods in Key- 783 Establishment Schemes", April 2018, 784 . 786 [OQS-102] Open Quantum Safe Project, "OQS-OpenSSL-1-0-2_stable", 787 November 2018, . 790 [OQS-111] Open Quantum Safe Project, "OQS-OpenSSL-1-1-1_stable", 791 November 2018, . 794 [SCHANCK] Schanck, J. and D. Stebila, "A Transport Layer Security 795 (TLS) Extension For Establishing An Additional Shared 796 Secret", draft-schanck-tls-additional-keyshare-00 (work in 797 progress), April 2017. 799 [WHYTE12] Schanck, J., Whyte, W., and Z. Zhang, "Quantum-Safe Hybrid 800 (QSH) Ciphersuite for Transport Layer Security (TLS) 801 version 1.2", draft-whyte-qsh-tls12-02 (work in progress), 802 July 2016. 804 [WHYTE13] Whyte, W., Zhang, Z., Fluhrer, S., and O. Garcia-Morchon, 805 "Quantum-Safe Hybrid (QSH) Key Exchange for Transport 806 Layer Security (TLS) version 1.3", draft-whyte-qsh- 807 tls13-06 (work in progress), October 2017. 809 [XMSS] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. 810 Mohaisen, "XMSS: eXtended Merkle Signature Scheme", 811 RFC 8391, DOI 10.17487/RFC8391, May 2018, 812 . 814 [ZHANG] Zhang, R., Hanaoka, G., Shikata, J., and H. Imai, "On the 815 Security of Multiple Encryption or CCA-security+CCA- 816 security=CCA-security?", Public Key Cryptography - PKC 817 2004 pp. 360-374, DOI 10.1007/978-3-540-24632-9_26, 2004. 819 Appendix A. Related work 821 Quantum computing and post-quantum cryptography in general are 822 outside the scope of this document. For a general introduction to 823 quantum computing, see a standard textbook such as [NIELSEN]. For an 824 overview of post-quantum cryptography as of 2009, see [BERNSTEIN]. 825 For the current status of the NIST Post-Quantum Cryptography 826 Standardization Project, see [NIST]. For additional perspectives on 827 the general transition from classical to post-quantum cryptography, 828 see for example [ETSI] and [HOFFMAN], among others. 830 There have been several Internet-Drafts describing mechanisms for 831 embedding post-quantum and/or hybrid key exchange in TLS: 833 o Internet-Drafts for TLS 1.2: [WHYTE12] 835 o Internet-Drafts for TLS 1.3: [KIEFER], [SCHANCK], [WHYTE13] 837 There have been several prototype implementations for post-quantum 838 and/or hybrid key exchange in TLS: 840 o Experimental implementations in TLS 1.2: [BCNS15], [CECPQ1], 841 [FRODO], [OQS-102] 843 o Experimental implementations in TLS 1.3: [CECPQ2], [OQS-111] 845 These experimental implementations have taken an ad hoc approach and 846 not attempted to implement one of the drafts listed above. 848 Unrelated to post-quantum but still related to the issue of combining 849 multiple types of keying material in TLS is the use of pre-shared 850 keys, especially the recent TLS working group document on including 851 an external pre-shared key [EXTERN-PSK]. 853 Considering other IETF standards, there is work on post-quantum 854 preshared keys in IKEv2 [IKE-PSK] and a framework for hybrid key 855 exchange in IKEv2 [IKE-HYBRID]. The XMSS hash-based signature scheme 856 has been published as an informational RFC by the IRTF [XMSS]. 858 In the academic literature, [EVEN] initiated the study of combining 859 multiple symmetric encryption schemes; [ZHANG], [DODIS], and [HARNIK] 860 examined combining multiple public key encryption schemes, and 861 [HARNIK] coined the term "robust combiner" to refer to a compiler 862 that constructs a hybrid scheme from individual schemes while 863 preserving security properties. [GIACON] and [BINDEL] examined 864 combining multiple key encapsulation mechanisms. 866 Appendix B. Design Considerations 868 This appendix discusses choices one could make along four distinct 869 axes when integrating hybrid key exchange into TLS 1.3: 871 1. How to negotiate the use of hybridization in general and 872 component algorithms specifically? 874 2. How many component algorithms can be combined? 876 3. How should multiple key shares (public keys / ciphertexts) be 877 conveyed? 879 4. How should multiple shared secrets be combined? 881 The construction in the main body illustrates one selection along 882 each of these axes. The remainder of this appendix outlines various 883 options we have identified for each of these choices. Immediately 884 below we provide a summary list. Options are labelled with a short 885 code in parentheses to provide easy cross-referencing. 887 1. (Neg) (Appendix B.1) How to negotiate the use of hybridization in 888 general and component algorithms specifically? 890 * (Neg-Ind) (Appendix B.1.2) Negotiating component algorithms 891 individually 893 + (Neg-Ind-1) (Appendix B.1.2.1) Traditional algorithms in 894 "ClientHello" "supported_groups" extension, next-gen 895 algorithms in another extension 897 + (Neg-Ind-2) (Appendix B.1.2.2) Both types of algorithms in 898 "supported_groups" with external mapping to tradition/next- 899 gen. 901 + (Neg-Ind-3) (Appendix B.1.2.3) Both types of algorithms in 902 "supported_groups" separated by a delimiter. 904 * (Neg-Comb) (Appendix B.1.3) Negotiating component algorithms 905 as a combination 907 + (Neg-Comb-1) (Appendix B.1.3.1) Standardize "NamedGroup" 908 identifiers for each desired combination. 910 + (Neg-Comb-2) (Appendix B.1.3.2) Use placeholder identifiers 911 in "supported_groups" with an extension defining the 912 combination corresponding to each placeholder. 914 + (Neg-Comb-3) (Appendix B.1.3.3) List combinations by 915 inserting grouping delimiters into "supported_groups" list. 917 2. (Num) (Appendix B.2) How many component algorithms can be 918 combined? 920 * (Num-2) (Appendix B.2.1) Two. 922 * (Num-2+) (Appendix B.2.2) Two or more. 924 3. (Shares) (Appendix B.3) How should multiple key shares (public 925 keys / ciphertexts) be conveyed? 927 * (Shares-Concat) (Appendix B.3.1) Concatenate each combination 928 of key shares. 930 * (Shares-Multiple) (Appendix B.3.2) Send individual key shares 931 for each algorithm. 933 * (Shares-Ext-Additional) (Appendix B.3.3) Use an extension to 934 convey key shares for component algorithms. 936 4. (Comb) (Appendix B.4) How should multiple shared secrets be 937 combined? 939 * (Comb-Concat) (Appendix B.4.1) Concatenate the shared secrets 940 then use directly in the TLS 1.3 key schedule. 942 * (Comb-KDF-1) (Appendix B.4.2) and (Comb-KDF-2) 943 (Appendix B.4.3) KDF the shared secrets together, then use the 944 output in the TLS 1.3 key schedule. 946 * (Comb-XOR) (Appendix B.4.4) XOR the shared secrets then use 947 directly in the TLS 1.3 key schedule. 949 * (Comb-Chain) (Appendix B.4.5) Extend the TLS 1.3 key schedule 950 so that there is a stage of the key schedule for each shared 951 secret. 953 * (Comb-AltInput) (Appendix B.4.6) Use the second shared secret 954 in an alternate (otherwise unused) input in the TLS 1.3 key 955 schedule. 957 B.1. (Neg) How to negotiate hybridization and component algorithms? 959 B.1.1. Key exchange negotiation in TLS 1.3 961 Recall that in TLS 1.3, the key exchange mechanism is negotiated via 962 the "supported_groups" extension. The "NamedGroup" enum is a list of 963 standardized groups for Diffie-Hellman key exchange, such as 964 "secp256r1", "x25519", and "ffdhe2048". 966 The client, in its "ClientHello" message, lists its supported 967 mechanisms in the "supported_groups" extension. The client also 968 optionally includes the public key of one or more of these groups in 969 the "key_share" extension as a guess of which mechanisms the server 970 might accept in hopes of reducing the number of round trips. 972 If the server is willing to use one of the client's requested 973 mechanisms, it responds with a "key_share" extension containing its 974 public key for the desired mechanism. 976 If the server is not willing to use any of the client's requested 977 mechanisms, the server responds with a "HelloRetryRequest" message 978 that includes an extension indicating its preferred mechanism. 980 B.1.2. (Neg-Ind) Negotiating component algorithms individually 982 In these three approaches, the parties negotiate which traditional 983 algorithm and which next-gen algorithm to use independently. The 984 "NamedGroup" enum is extended to include algorithm identifiers for 985 each next-gen algorithm. 987 B.1.2.1. (Neg-Ind-1) 989 The client advertises two lists to the server: one list containing 990 its supported traditional mechanisms (e.g. via the existing 991 "ClientHello" "supported_groups" extension), and a second list 992 containing its supported next-generation mechanisms (e.g., via an 993 additional "ClientHello" extension). A server could then select one 994 algorithm from the traditional list, and one algorithm from the next- 995 generation list. (This is the approach in [SCHANCK].) 997 B.1.2.2. (Neg-Ind-2) 999 The client advertises a single list to the server which contains both 1000 its traditional and next-generation mechanisms (e.g., all in the 1001 existing "ClientHello" "supported_groups" extension), but with some 1002 external table provides a standardized mapping of those mechanisms as 1003 either "traditional" or "next-generation". A server could then 1004 select two algorithms from this list, one from each category. 1006 B.1.2.3. (Neg-Ind-3) 1008 The client advertises a single list to the server delimited into 1009 sublists: one for its traditional mechanisms and one for its next- 1010 generation mechanisms, all in the existing "ClientHello" 1011 "supported_groups" extension, with a special code point serving as a 1012 delimiter between the two lists. For example, "supported_groups = 1013 secp256r1, x25519, delimiter, nextgen1, nextgen4". 1015 B.1.3. (Neg-Comb) Negotiating component algorithms as a combination 1017 In these three approaches, combinations of key exchange mechanisms 1018 appear as a single monolithic block; the parties negotiate which of 1019 several combinations they wish to use. 1021 B.1.3.1. (Neg-Comb-1) 1023 The "NamedGroup" enum is extended to include algorithm identifiers 1024 for each *combination* of algorithms desired by the working group. 1025 There is no "internal structure" to the algorithm identifiers for 1026 each combination, they are simply new code points assigned 1027 arbitrarily. The client includes any desired combinations in its 1028 "ClientHello" "supported_groups" list, and the server picks one of 1029 these. This is the approach in [KIEFER] and [OQS-111]. 1031 B.1.3.2. (Neg-Comb-2) 1033 The "NamedGroup" enum is extended to include algorithm identifiers 1034 for each next-gen algorithm. Some additional field/extension is used 1035 to convey which combinations the parties wish to use. For example, 1036 in [WHYTE13], there are distinguished "NamedGroup" called 1037 "hybrid_marker 0", "hybrid_marker 1", "hybrid_marker 2", etc. This 1038 is complemented by a "HybridExtension" which contains mappings for 1039 each numbered "hybrid_marker" to the set of component key exchange 1040 algorithms (2 or more) for that proposed combination. 1042 B.1.3.3. (Neg-Comb-3) 1044 The client lists combinations in "supported_groups" list, using a 1045 special delimiter to indicate combinations. For example, 1046 "supported_groups = combo_delimiter, secp256r1, nextgen1, 1047 combo_delimiter, secp256r1, nextgen4, standalone_delimiter, 1048 secp256r1, x25519" would indicate that the client's highest 1049 preference is the combination secp256r1+nextgen1, the next highest 1050 preference is the combination secp2561+nextgen4, then the single 1051 algorithm secp256r1, then the single algorithm x25519. A hybrid- 1052 aware server would be able to parse these; a hybrid-unaware server 1053 would see "unknown, secp256r1, unknown, unknown, secp256r1, unknown, 1054 unknown, secp256r1, x25519", which it would be able to process, 1055 although there is the potential that every "projection" of a hybrid 1056 list that is tolerable to a client does not result in list that is 1057 tolerable to the client. 1059 B.1.4. Benefits and drawbacks 1061 *Combinatorial explosion.* (Neg-Comb-1) (Appendix B.1.3.1) requires 1062 new identifiers to be defined for each desired combination. The 1063 other 4 options in this section do not. 1065 *Extensions.* (Neg-Ind-1) (Appendix B.1.2.1) and (Neg-Comb-2) 1066 (Appendix B.1.3.2) require new extensions to be defined. The other 1067 options in this section do not. 1069 *New logic.* All options in this section except (Neg-Comb-1) 1070 (Appendix B.1.3.1) require new logic to process negotiation. 1072 *Matching security levels.* (Neg-Ind-1) (Appendix B.1.2.1), (Neg-Ind- 1073 2) (Appendix B.1.2.2), (Neg-Ind-3) (Appendix B.1.2.3), and (Neg-Comb- 1074 2) (Appendix B.1.3.2) allow algorithms of different claimed security 1075 level from their corresponding lists to be combined. For example, 1076 this could result in combining ECDH secp256r1 (classical security 1077 level 128) with NewHope-1024 (classical security level 256). 1078 Implementations dissatisfied with a mismatched security levels must 1079 either accept this mismatch or attempt to renegotiate. (Neg-Ind-1) 1080 (Appendix B.1.2.1), (Neg-Ind-2) (Appendix B.1.2.2), and (Neg-Ind-3) 1081 (Appendix B.1.2.3) give control over the combination to the server; 1082 (Neg-Comb-2) (Appendix B.1.3.2) gives control over the combination to 1083 the client. (Neg-Comb-1) (Appendix B.1.3.1) only allows standardized 1084 combinations, which could be set by TLS working group to have 1085 matching security (provided security estimates do not evolve 1086 separately). 1088 *Backwards-compability.* TLS 1.3-compliant hybrid-unaware servers 1089 should ignore unreocgnized elements in "supported_groups" (Neg-Ind-2) 1090 (Appendix B.1.2.2), (Neg-Ind-3) (Appendix B.1.2.3), (Neg-Comb-1) 1091 (Appendix B.1.3.1), (Neg-Comb-2) (Appendix B.1.3.2) and unrecognized 1092 "ClientHello" extensions (Neg-Ind-1) (Appendix B.1.2.1), (Neg-Comb-2) 1093 (Appendix B.1.3.2). In (Neg-Ind-3) (Appendix B.1.2.3) and (Neg-Comb- 1094 3) (Appendix B.1.3.3), a server that is hybrid-unaware will ignore 1095 the delimiters in "supported_groups", and thus might try to negotiate 1096 an algorithm individually that is only meant to be used in 1097 combination; depending on how such an implementation is coded, it may 1098 also encounter bugs when the same element appears multiple times in 1099 the list. 1101 B.2. (Num) How many component algorithms to combine? 1103 B.2.1. (Num-2) Two 1105 Exactly two algorithms can be combined together in hybrid key 1106 exchange. This is the approach taken in [KIEFER] and [SCHANCK]. 1108 B.2.2. (Num-2+) Two or more 1110 Two or more algorithms can be combined together in hybrid key 1111 exchange. This is the approach taken in [WHYTE13]. 1113 B.2.3. Benefits and Drawbacks 1115 Restricting the number of component algorithms that can be hybridized 1116 to two substantially reduces the generality required. On the other 1117 hand, some adopters may want to further reduce risk by employing 1118 multiple next-gen algorithms built on different cryptographic 1119 assumptions. 1121 B.3. (Shares) How to convey key shares? 1123 In ECDH ephmeral key exchange, the client sends its ephmeral public 1124 key in the "key_share" extension of the "ClientHello" message, and 1125 the server sends its ephmeral public key in the "key_share" extension 1126 of the "ServerHello" message. 1128 For a general key encapsulation mechanism used for ephemeral key 1129 exchange, we imagine that that client generates a fresh KEM public 1130 key / secret pair for each connection, sends it to the client, and 1131 the server responds with a KEM ciphertext. For simplicity and 1132 consistency with TLS 1.3 terminology, we will refer to both of these 1133 types of objects as "key shares". 1135 In hybrid key exchange, we have to decide how to convey the client's 1136 two (or more) key shares, and the server's two (or more) key shares. 1138 B.3.1. (Shares-Concat) Concatenate key shares 1140 The client concatenates the bytes representing its two key shares and 1141 uses this directly as the "key_exchange" value in a "KeyShareEntry" 1142 in its "key_share" extension. The server does the same thing. Note 1143 that the "key_exchange" value can be an octet string of length at 1144 most 2^16-1. This is the approach taken in [KIEFER], [OQS-111], and 1145 [WHYTE13]. 1147 B.3.2. (Shares-Multiple) Send multiple key shares 1149 The client sends multiple key shares directly in the "client_shares" 1150 vectors of the "ClientHello" "key_share" extension. The server does 1151 the same. (Note that while the existing "KeyShareClientHello" struct 1152 allows for multiple key share entries, the existing 1153 "KeyShareServerHello" only permits a single key share entry, so some 1154 modification would be required to use this approach for the server to 1155 send multiple key shares.) 1157 B.3.3. (Shares-Ext-Additional) Extension carrying additional key shares 1159 The client sends the key share for its traditional algorithm in the 1160 original "key_share" extension of the "ClientHello" message, and the 1161 key share for its next-gen algorithm in some additional extension in 1162 the "ClientHello" message. The server does the same thing. This is 1163 the approach taken in [SCHANCK]. 1165 B.3.4. Benefits and Drawbacks 1167 *Backwards compatibility.* (Shares-Multiple) (Appendix B.3.2) is 1168 fully backwards compatible with non-hybrid-aware servers. (Shares- 1169 Ext-Additional) (Appendix B.3.3) is backwards compatible with non- 1170 hybrid-aware servers provided they ignore unrecognized extensions. 1171 (Shares-Concat) (Appendix B.3.1) is backwards-compatible with non- 1172 hybrid aware servers, but may result in duplication / additional 1173 round trips (see below). 1175 *Duplication versus additional round trips.* If a client wants to 1176 offer multiple key shares for multiple combinations in order to avoid 1177 retry requests, then the client may ended up sending a key share for 1178 one algorithm multiple times when using (Shares-Ext-Additional) 1179 (Appendix B.3.3) and (Shares-Concat) (Appendix B.3.1). (For example, 1180 if the client wants to send an ECDH-secp256r1 + McEliece123 key 1181 share, and an ECDH-secp256r1 + NewHope1024 key share, then the same 1182 ECDH public key may be sent twice. If the client also wants to offer 1183 a traditional ECDH-only key share for non-hybrid-aware 1184 implementations and avoid retry requests, then that same ECDH public 1185 key may be sent another time.) (Shares-Multiple) (Appendix B.3.2) 1186 does not result in duplicate key shares. 1188 B.4. (Comb) How to use keys? 1190 Each component key exchange algorithm establishes a shared secret. 1191 These shared secrets must be combined in some way that achieves the 1192 "hybrid" property: the resulting secret is secure as long as at least 1193 one of the component key exchange algorithms is unbroken. 1195 B.4.1. (Comb-Concat) Concatenate keys 1197 Each party concatenates the shared secrets established by each 1198 component algorithm in an agreed-upon order, then feeds that through 1199 the TLS key schedule. In the context of TLS 1.3, this would mean 1200 using the concatenated shared secret in place of the (EC)DHE input to 1201 the second call to "HKDF-Extract" in the TLS 1.3 key schedule: 1203 0 1204 | 1205 v 1206 PSK -> HKDF-Extract = Early Secret 1207 | 1208 +-----> Derive-Secret(...) 1209 +-----> Derive-Secret(...) 1210 +-----> Derive-Secret(...) 1211 | 1212 v 1213 Derive-Secret(., "derived", "") 1214 | 1215 v 1216 concatenated_shared_secret -> HKDF-Extract = Handshake Secret 1217 ^^^^^^^^^^^^^^^^^^^^^^^^^^ | 1218 +-----> Derive-Secret(...) 1219 +-----> Derive-Secret(...) 1220 | 1221 v 1222 Derive-Secret(., "derived", "") 1223 | 1224 v 1225 0 -> HKDF-Extract = Master Secret 1226 | 1227 +-----> Derive-Secret(...) 1228 +-----> Derive-Secret(...) 1229 +-----> Derive-Secret(...) 1230 +-----> Derive-Secret(...) 1232 This is the approach used in [KIEFER], [OQS-111], and [WHYTE13]. 1234 [GIACON] analyzes the security of applying a KDF to concatenated KEM 1235 shared secrets, but their analysis does not exactly apply here since 1236 the transcript of ciphertexts is included in the KDF application 1237 (though it should follow relatively straightforwardly). 1239 [BINDEL] analyzes the security of the (Comb-Concat) approach as 1240 abstracted in their "dualPRF" combiner. They show that, if the 1241 component KEMs are IND-CPA-secure (or IND-CCA-secure), then the 1242 values output by "Derive-Secret" are IND-CPA-secure (respectively, 1243 IND-CCA-secure). An important aspect of their analysis is that each 1244 ciphertext is input to the final PRF calls; this holds for TLS 1.3 1245 since the "Derive-Secret" calls that derive output keys (application 1246 traffic secrets, and exporter and resumption master secrets) include 1247 the transcript hash as input. 1249 B.4.2. (Comb-KDF-1) KDF keys 1251 Each party feeds the shared secrets established by each component 1252 algorithm in an agreed-upon order into a KDF, then feeds that through 1253 the TLS key schedule. In the context of TLS 1.3, this would mean 1254 first applying "HKDF-Extract" to the shared secrets, then using the 1255 output in place of the (EC)DHE input to the second call to "HKDF- 1256 Extract" in the TLS 1.3 key schedule: 1258 0 1259 | 1260 v 1261 PSK -> HKDF-Extract = Early Secret 1262 | 1263 +-----> Derive-Secret(...) 1264 +-----> Derive-Secret(...) 1265 +-----> Derive-Secret(...) 1266 Next-Gen | 1267 | v 1268 (EC)DHE -> HKDF-Extract Derive-Secret(., "derived", "") 1269 | | 1270 v v 1271 output -----> HKDF-Extract = Handshake Secret 1272 ^^^^^^ | 1273 +-----> Derive-Secret(...) 1274 +-----> Derive-Secret(...) 1275 | 1276 v 1277 Derive-Secret(., "derived", "") 1278 | 1279 v 1280 0 -> HKDF-Extract = Master Secret 1281 | 1282 +-----> Derive-Secret(...) 1283 +-----> Derive-Secret(...) 1284 +-----> Derive-Secret(...) 1285 +-----> Derive-Secret(...) 1287 B.4.3. (Comb-KDF-2) KDF keys 1289 Each party concatenates the shared secrets established by each 1290 component algorithm in an agreed-upon order then feeds that into a 1291 KDF, then feeds the result through the TLS key schedule. 1293 Compared with (Comb-KDF-1) (Appendix B.4.2), this method concatenates 1294 the (2 or more) shared secrets prior to input to the KDF, whereas 1295 (Comb-KDF-1) puts the (exactly 2) shared secrets in the two different 1296 input slots to the KDF. 1298 Compared with (Comb-Concat) (Appendix B.4.1), this method has an 1299 extract KDF application. While this adds computational overhead, 1300 this may provide a cleaner abstraction of the hybridization mechanism 1301 for the purposes of formal security analysis. 1303 0 1304 | 1305 v 1306 PSK -> HKDF-Extract = Early Secret 1307 | 1308 +-----> Derive-Secret(...) 1309 +-----> Derive-Secret(...) 1310 +-----> Derive-Secret(...) 1311 | 1312 v 1313 concatenated 0 1314 shared | 1315 secret -> HKDF-Extract Derive-Secret(., "derived", "") 1316 ^^^^^^ | | 1317 v v 1318 output -----> HKDF-Extract = Handshake Secret 1319 ^^^^^^ | 1320 +-----> Derive-Secret(...) 1321 +-----> Derive-Secret(...) 1322 | 1323 v 1324 Derive-Secret(., "derived", "") 1325 | 1326 v 1327 0 -> HKDF-Extract = Master Secret 1328 | 1329 +-----> Derive-Secret(...) 1330 +-----> Derive-Secret(...) 1331 +-----> Derive-Secret(...) 1332 +-----> Derive-Secret(...) 1334 B.4.4. (Comb-XOR) XOR keys 1336 Each party XORs the shared secrets established by each component 1337 algorithm (possibly after padding secrets of different lengths), then 1338 feeds that through the TLS key schedule. In the context of TLS 1.3, 1339 this would mean using the XORed shared secret in place of the (EC)DHE 1340 input to the second call to "HKDF-Extract" in the TLS 1.3 key 1341 schedule. 1343 [GIACON] analyzes the security of applying a KDF to the XORed KEM 1344 shared secrets, but their analysis does not quite apply here since 1345 the transcript of ciphertexts is included in the KDF application 1346 (though it should follow relatively straightforwardly). 1348 B.4.5. (Comb-Chain) Chain of KDF applications for each key 1350 Each party applies a chain of key derivation functions to the shared 1351 secrets established by each component algorithm in an agreed-upon 1352 order; roughly speaking: "F(k1 || F(k2))". In the context of TLS 1353 1.3, this would mean extending the key schedule to have one round of 1354 the key schedule applied for each component algorithm's shared 1355 secret: 1357 0 1358 | 1359 v 1360 PSK -> HKDF-Extract = Early Secret 1361 | 1362 +-----> Derive-Secret(...) 1363 +-----> Derive-Secret(...) 1364 +-----> Derive-Secret(...) 1365 | 1366 v 1367 Derive-Secret(., "derived", "") 1368 | 1369 v 1370 traditional_shared_secret -> HKDF-Extract 1371 ^^^^^^^^^^^^^^^^^^^^^^^^^ | 1372 Derive-Secret(., "derived", "") 1373 | 1374 v 1375 next_gen_shared_secret -> HKDF-Extract = Handshake Secret 1376 ^^^^^^^^^^^^^^^^^^^^^^ | 1377 +-----> Derive-Secret(...) 1378 +-----> Derive-Secret(...) 1379 | 1380 v 1381 Derive-Secret(., "derived", "") 1382 | 1383 v 1384 0 -> HKDF-Extract = Master Secret 1385 | 1386 +-----> Derive-Secret(...) 1387 +-----> Derive-Secret(...) 1388 +-----> Derive-Secret(...) 1389 +-----> Derive-Secret(...) 1391 This is the approach used in [SCHANCK]. 1393 [BINDEL] analyzes the security of this approach as abstracted in 1394 their nested dual-PRF "N" combiner, showing a similar result as for 1395 the dualPRF combiner that it preserves IND-CPA (or IND-CCA) security. 1397 Again their analysis depends on each ciphertext being input to the 1398 final PRF ("Derive-Secret") calls, which holds for TLS 1.3. 1400 B.4.6. (Comb-AltInput) Second shared secret in an alternate KDF input 1402 In the context of TLS 1.3, the next-generation shared secret is used 1403 in place of a currently unused input in the TLS 1.3 key schedule, 1404 namely replacing the "0" "IKM" input to the final "HKDF-Extract": 1406 0 1407 | 1408 v 1409 PSK -> HKDF-Extract = Early Secret 1410 | 1411 +-----> Derive-Secret(...) 1412 +-----> Derive-Secret(...) 1413 +-----> Derive-Secret(...) 1414 | 1415 v 1416 Derive-Secret(., "derived", "") 1417 | 1418 v 1419 traditional_shared_secret -> HKDF-Extract = Handshake Secret 1420 ^^^^^^^^^^^^^^^^^^^^^^^^^ | 1421 +-----> Derive-Secret(...) 1422 +-----> Derive-Secret(...) 1423 | 1424 v 1425 Derive-Secret(., "derived", "") 1426 | 1427 v 1428 next_gen_shared_secret -> HKDF-Extract = Master Secret 1429 ^^^^^^^^^^^^^^^^^^^^^^ | 1430 +-----> Derive-Secret(...) 1431 +-----> Derive-Secret(...) 1432 +-----> Derive-Secret(...) 1433 +-----> Derive-Secret(...) 1435 This approach is not taken in any of the known post-quantum/hybrid 1436 TLS drafts. However, it bears some similarities to the approach for 1437 using external PSKs in [EXTERN-PSK]. 1439 B.4.7. Benefits and Drawbacks 1441 *New logic.* While (Comb-Concat) (Appendix B.4.1), (Comb-KDF-1) 1442 (Appendix B.4.2), and (Comb-KDF-2) (Appendix B.4.3) require new logic 1443 to compute the concatenated shared secret, this value can then be 1444 used by the TLS 1.3 key schedule without changes to the key schedule 1445 logic. In contrast, (Comb-Chain) (Appendix B.4.5) requires the TLS 1446 1.3 key schedule to be extended for each extra component algorithm. 1448 *Philosophical.* The TLS 1.3 key schedule already applies a new stage 1449 for different types of keying material (PSK versus (EC)DHE), so 1450 (Comb-Chain) (Appendix B.4.5) continues that approach. 1452 *Efficiency.* (Comb-KDF-1) (Appendix B.4.2), (Comb-KDF-2) 1453 (Appendix B.4.3), and (Comb-Chain) (Appendix B.4.5) increase the 1454 number of KDF applications for each component algorithm, whereas 1455 (Comb-Concat) (Appendix B.4.1) and (Comb-AltInput) (Appendix B.4.6) 1456 keep the number of KDF applications the same (though with potentially 1457 longer inputs). 1459 *Extensibility.* (Comb-AltInput) (Appendix B.4.6) changes the use of 1460 an existing input, which might conflict with other future changes to 1461 the use of the input. 1463 *More than 2 component algorithms.* The techniques in (Comb-Concat) 1464 (Appendix B.4.1) and (Comb-Chain) (Appendix B.4.5) can naturally 1465 accommodate more than 2 component shared secrets since there is no 1466 distinction to how each shared secret is treated. (Comb-AltInput) 1467 (Appendix B.4.6) would have to make some distinct, since the 2 1468 component shared secrets are used in different ways; for example, the 1469 first shared secret is used as the "IKM" input in the 2nd "HKDF- 1470 Extract" call, and all subsequent shared secrets are concatenated to 1471 be used as the "IKM" input in the 3rd "HKDF-Extract" call. 1473 Authors' Addresses 1475 Douglas Stebila 1476 University of Waterloo 1478 Email: dstebila@uwaterloo.ca 1480 Scott Fluhrer 1481 Cisco Systems 1483 Email: sfluhrer@cisco.com 1485 Shay Gueron 1486 University of Haifa and Amazon Web Services 1488 Email: shay.gueron@gmail.com