idnits 2.17.1 draft-ietf-tls-hybrid-design-02.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: ---------------------------------------------------------------------------- == There is 1 instance of lines with non-ascii characters in the document. 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 368: '...in this document MUST explicitly be de...' RFC 2119 keyword, line 373: '... KEM public keys MUST ensure that the ...' RFC 2119 keyword, line 375: '...lyses. Implementations MUST NOT reuse...' RFC 2119 keyword, line 471: '... KeyShareEntry MUST be generated ind...' RFC 2119 keyword, line 476: '...s for each algorithm MUST be generated...' (2 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (14 April 2021) is 1106 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-campagna-tls-bike-sike-hybrid-06 == Outdated reference: A later version (-12) exists of draft-irtf-cfrg-hpke-08 Summary: 1 error (**), 0 flaws (~~), 4 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: 16 October 2021 Cisco Systems 6 S. Gueron 7 U. Haifa, Amazon Web Services 8 14 April 2021 10 Hybrid key exchange in TLS 1.3 11 draft-ietf-tls-hybrid-design-02 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-ietf-tls-hybrid-design. 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at https://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on 16 October 2021. 43 Copyright Notice 45 Copyright (c) 2021 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 50 license-info) in effect on the date of publication of this document. 51 Please review these documents carefully, as they describe your rights 52 and restrictions with respect to this document. Code Components 53 extracted from this document must include Simplified BSD License text 54 as described in Section 4.e of the Trust Legal Provisions and are 55 provided without warranty as described in the Simplified BSD License. 57 Table of Contents 59 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 60 1.1. Revision history . . . . . . . . . . . . . . . . . . . . 3 61 1.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 4 62 1.3. Motivation for use of hybrid key exchange . . . . . . . . 5 63 1.4. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 6 64 1.5. Goals . . . . . . . . . . . . . . . . . . . . . . . . . . 6 65 2. Key encapsulation mechanisms . . . . . . . . . . . . . . . . 7 66 3. Construction for hybrid key exchange . . . . . . . . . . . . 8 67 3.1. Negotiation . . . . . . . . . . . . . . . . . . . . . . . 9 68 3.2. Transmitting public keys and ciphertexts . . . . . . . . 10 69 3.3. Shared secret calculation . . . . . . . . . . . . . . . . 11 70 4. Open questions . . . . . . . . . . . . . . . . . . . . . . . 13 71 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 14 72 6. Security Considerations . . . . . . . . . . . . . . . . . . . 14 73 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 15 74 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 15 75 8.1. Normative References . . . . . . . . . . . . . . . . . . 15 76 8.2. Informative References . . . . . . . . . . . . . . . . . 15 77 Appendix A. Related work . . . . . . . . . . . . . . . . . . . . 20 78 Appendix B. Design Considerations . . . . . . . . . . . . . . . 21 79 B.1. (Neg) How to negotiate hybridization and component 80 algorithms? . . . . . . . . . . . . . . . . . . . . . . . 22 81 B.1.1. Key exchange negotiation in TLS 1.3 . . . . . . . . . 23 82 B.1.2. (Neg-Ind) Negotiating component algorithms 83 individually . . . . . . . . . . . . . . . . . . . . 23 84 B.1.3. (Neg-Comb) Negotiating component algorithms as a 85 combination . . . . . . . . . . . . . . . . . . . . . 24 86 B.1.4. Benefits and drawbacks . . . . . . . . . . . . . . . 25 87 B.2. (Num) How many component algorithms to combine? . . . . . 26 88 B.2.1. (Num-2) Two . . . . . . . . . . . . . . . . . . . . . 26 89 B.2.2. (Num-2+) Two or more . . . . . . . . . . . . . . . . 26 90 B.2.3. Benefits and Drawbacks . . . . . . . . . . . . . . . 26 91 B.3. (Shares) How to convey key shares? . . . . . . . . . . . 26 92 B.3.1. (Shares-Concat) Concatenate key shares . . . . . . . 26 93 B.3.2. (Shares-Multiple) Send multiple key shares . . . . . 27 94 B.3.3. (Shares-Ext-Additional) Extension carrying additional 95 key shares . . . . . . . . . . . . . . . . . . . . . 27 97 B.3.4. Benefits and Drawbacks . . . . . . . . . . . . . . . 27 98 B.4. (Comb) How to use keys? . . . . . . . . . . . . . . . . . 27 99 B.4.1. (Comb-Concat) Concatenate keys . . . . . . . . . . . 28 100 B.4.2. (Comb-KDF-1) KDF keys . . . . . . . . . . . . . . . . 29 101 B.4.3. (Comb-KDF-2) KDF keys . . . . . . . . . . . . . . . . 30 102 B.4.4. (Comb-XOR) XOR keys . . . . . . . . . . . . . . . . . 31 103 B.4.5. (Comb-Chain) Chain of KDF applications for each 104 key . . . . . . . . . . . . . . . . . . . . . . . . . 31 105 B.4.6. (Comb-AltInput) Second shared secret in an alternate 106 KDF input . . . . . . . . . . . . . . . . . . . . . . 32 107 B.4.7. Benefits and Drawbacks . . . . . . . . . . . . . . . 33 108 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 34 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 * draft-ietf-tls-hybrid-design-02: 133 - Bump to version -02 to avoid expiry 135 * draft-ietf-tls-hybrid-design-01: 137 - Forbid variable-length secret keys 139 - Use fixed-length KEM public keys/ciphertexts 141 * draft-ietf-tls-hybrid-design-00: 143 - Allow key_exchange values from the same algorithm to be reused 144 across multiple KeyShareEntry records in the same ClientHello. 146 * draft-stebila-tls-hybrid-design-03: 148 - Add requirement for KEMs to provide protection against key 149 reuse. 151 - Clarify FIPS-compliance of shared secret concatenation method. 153 * draft-stebila-tls-hybrid-design-02: 155 - Design considerations from draft-stebila-tls-hybrid-design-00 156 and draft-stebila-tls-hybrid-design-01 are moved to the 157 appendix. 159 - A single construction is given in the main body. 161 * draft-stebila-tls-hybrid-design-01: 163 - Add (Comb-KDF-1) (Appendix B.4.2) and (Comb-KDF-2) 164 (Appendix B.4.3) options. 166 - Add two candidate instantiations. 168 * draft-stebila-tls-hybrid-design-00: Initial version. 170 1.2. Terminology 172 For the purposes of this document, it is helpful to be able to divide 173 cryptographic algorithms into two classes: 175 * "Traditional" algorithms: Algorithms which are widely deployed 176 today, but which may be deprecated in the future. In the context 177 of TLS 1.3 in 2019, examples of traditional key exchange 178 algorithms include elliptic curve Diffie-Hellman using secp256r1 179 or x25519, or finite-field Diffie-Hellman. 181 * "Next-generation" (or "next-gen") algorithms: Algorithms which are 182 not yet widely deployed, but which may eventually be widely 183 deployed. An additional facet of these algorithms may be that we 184 have less confidence in their security due to them being 185 relatively new or less studied. This includes "post-quantum" 186 algorithms. 188 "Hybrid" key exchange, in this context, means the use of two (or 189 more) key exchange algorithms based on different cryptographic 190 assumptions, e.g., one traditional algorithm and one next-gen 191 algorithm, with the purpose of the final session key being secure as 192 long as at least one of the component key exchange algorithms remains 193 unbroken. We use the term "component" algorithms to refer to the 194 algorithms combined in a hybrid key exchange. 196 The primary motivation of this document is preparing for post-quantum 197 algorithms. However, it is possible that public key cryptography 198 based on alternative mathematical constructions will be required 199 independent of the advent of a quantum computer, for example because 200 of a cryptanalytic breakthrough. As such we opt for the more generic 201 term "next-generation" algorithms rather than exclusively "post- 202 quantum" algorithms. 204 Note that TLS 1.3 uses the phrase "groups" to refer to key exchange 205 algorithms - for example, the "supported_groups" extension - since 206 all key exchange algorithms in TLS 1.3 are Diffie-Hellman-based. As 207 a result, some parts of this document will refer to data structures 208 or messages with the term "group" in them despite using a key 209 exchange algorithm that is not Diffie-Hellman-based nor a group. 211 1.3. Motivation for use of hybrid key exchange 213 A hybrid key exchange algorithm allows early adopters eager for post- 214 quantum security to have the potential of post-quantum security 215 (possibly from a less-well-studied algorithm) while still retaining 216 at least the security currently offered by traditional algorithms. 217 They may even need to retain traditional algorithms due to regulatory 218 constraints, for example FIPS compliance. 220 Ideally, one would not use hybrid key exchange: one would have 221 confidence in a single algorithm and parameterization that will stand 222 the test of time. However, this may not be the case in the face of 223 quantum computers and cryptanalytic advances more generally. 225 Many (though not all) post-quantum algorithms currently under 226 consideration are relatively new; they have not been subject to the 227 same depth of study as RSA and finite-field or elliptic curve Diffie- 228 Hellman, and thus the security community does not necessarily have as 229 much confidence in their fundamental security, or the concrete 230 security level of specific parameterizations. 232 Moreover, it is possible that even by the end of the NIST Post- 233 Quantum Cryptography Standardization Project, and for a period of 234 time thereafter, conservative users may not have full confidence in 235 some algorithms. 237 As such, there may be users for whom hybrid key exchange is an 238 appropriate step prior to an eventual transition to next-generation 239 algorithms. 241 1.4. Scope 243 This document focuses on hybrid ephemeral key exchange in TLS 1.3 244 [TLS13]. It intentionally does not address: 246 * Selecting which next-generation algorithms to use in TLS 1.3, nor 247 algorithm identifiers nor encoding mechanisms for next-generation 248 algorithms. This selection will be based on the recommendations 249 by the Crypto Forum Research Group (CFRG), which is currently 250 waiting for the results of the NIST Post-Quantum Cryptography 251 Standardization Project [NIST]. 253 * Authentication using next-generation algorithms. If a 254 cryptographic assumption is broken due to the advent of a quantum 255 computer or some other cryptanalytic breakthrough, confidentiality 256 of information can be broken retroactively by any adversary who 257 has passively recorded handshakes and encrypted communications. 258 In contrast, session authentication cannot be retroactively 259 broken. 261 1.5. Goals 263 The primary goal of a hybrid key exchange mechanism is to facilitate 264 the establishment of a shared secret which remains secure as long as 265 as one of the component key exchange mechanisms remains unbroken. 267 In addition to the primary cryptographic goal, there may be several 268 additional goals in the context of TLS 1.3: 270 * *Backwards compatibility:* Clients and servers who are "hybrid- 271 aware", i.e., compliant with whatever hybrid key exchange standard 272 is developed for TLS, should remain compatible with endpoints and 273 middle-boxes that are not hybrid-aware. The three scenarios to 274 consider are: 276 1. Hybrid-aware client, hybrid-aware server: These parties should 277 establish a hybrid shared secret. 279 2. Hybrid-aware client, non-hybrid-aware server: These parties 280 should establish a traditional shared secret (assuming the 281 hybrid-aware client is willing to downgrade to traditional- 282 only). 284 3. Non-hybrid-aware client, hybrid-aware server: These parties 285 should establish a traditional shared secret (assuming the 286 hybrid-aware server is willing to downgrade to traditional- 287 only). 289 Ideally backwards compatibility should be achieved without extra 290 round trips and without sending duplicate information; see below. 292 * *High performance:* Use of hybrid key exchange should not be 293 prohibitively expensive in terms of computational performance. In 294 general this will depend on the performance characteristics of the 295 specific cryptographic algorithms used, and as such is outside the 296 scope of this document. See [BCNS15], [CECPQ1], [FRODO] for 297 preliminary results about performance characteristics. 299 * *Low latency:* Use of hybrid key exchange should not substantially 300 increase the latency experienced to establish a connection. 301 Factors affecting this may include the following. 303 - The computational performance characteristics of the specific 304 algorithms used. See above. 306 - The size of messages to be transmitted. Public key and 307 ciphertext sizes for post-quantum algorithms range from 308 hundreds of bytes to over one hundred kilobytes, so this impact 309 can be substantial. See [BCNS15], [FRODO] for preliminary 310 results in a laboratory setting, and [LANGLEY] for preliminary 311 results on more realistic networks. 313 - Additional round trips added to the protocol. See below. 315 * *No extra round trips:* Attempting to negotiate hybrid key 316 exchange should not lead to extra round trips in any of the three 317 hybrid-aware/non-hybrid-aware scenarios listed above. 319 * *Minimal duplicate information:* Attempting to negotiate hybrid 320 key exchange should not mean having to send multiple public keys 321 of the same type. 323 2. Key encapsulation mechanisms 325 In the context of the NIST Post-Quantum Cryptography Standardization 326 Project, key exchange algorithms are formulated as key encapsulation 327 mechanisms (KEMs), which consist of three algorithms: 329 * "KeyGen() -> (pk, sk)": A probabilistic key generation algorithm, 330 which generates a public key "pk" and a secret key "sk". 332 * "Encaps(pk) -> (ct, ss)": A probabilistic encapsulation algorithm, 333 which takes as input a public key "pk" and outputs a ciphertext 334 "ct" and shared secret "ss". 336 * "Decaps(sk, ct) -> ss": A decapsulation algorithm, which takes as 337 input a secret key "sk" and ciphertext "ct" and outputs a shared 338 secret "ss", or in some cases a distinguished error value. 340 The main security property for KEMs is indistinguishability under 341 adaptive chosen ciphertext attack (IND-CCA2), which means that shared 342 secret values should be indistinguishable from random strings even 343 given the ability to have arbitrary ciphertexts decapsulated. IND- 344 CCA2 corresponds to security against an active attacker, and the 345 public key / secret key pair can be treated as a long-term key or 346 reused. A common design pattern for obtaining security under key 347 reuse is to apply the Fujisaki-Okamoto (FO) transform [FO] or a 348 variant thereof [HHK]. 350 A weaker security notion is indistinguishability under chosen 351 plaintext attack (IND-CPA), which means that the shared secret values 352 should be indistinguishable from random strings given a copy of the 353 public key. IND-CPA roughly corresponds to security against a 354 passive attacker, and sometimes corresponds to one-time key exchange. 356 Key exchange in TLS 1.3 is phrased in terms of Diffie-Hellman key 357 exchange in a group. DH key exchange can be modeled as a KEM, with 358 "KeyGen" corresponding to selecting an exponent "x" as the secret key 359 and computing the public key "g^x"; encapsulation corresponding to 360 selecting an exponent "y", computing the ciphertext "g^y" and the 361 shared secret "g^(xy)", and decapsulation as computing the shared 362 secret "g^(xy)". See [I-D.irtf-cfrg-hpke] for more details of such 363 Diffie-Hellman-based key encapsulation mechanisms. 365 TLS 1.3 does not require that ephemeral public keys be used only in a 366 single key exchange session; some implementations may reuse them, at 367 the cost of limited forward secrecy. As a result, any KEM used in 368 the manner described in this document MUST explicitly be designed to 369 be secure in the event that the public key is re-used, such as 370 achieving IND-CCA2 security or having a transform like the Fujisaki- 371 Okamoto transform [FO] [HHK] applied. While it is recommended that 372 implementations avoid reuse of KEM public keys, implementations that 373 do reuse KEM public keys MUST ensure that the number of reuses of a 374 KEM public key abides by any bounds in the specification of the KEM 375 or subsequent security analyses. Implementations MUST NOT reuse 376 randomness in the generation of KEM ciphertexts. 378 3. Construction for hybrid key exchange 379 3.1. Negotiation 381 Each particular combination of algorithms in a hybrid key exchange 382 will be represented as a "NamedGroup" and sent in the 383 "supported_groups" extension. No internal structure or grammar is 384 implied or required in the value of the identifier; they are simply 385 opaque identifiers. 387 Each value representing a hybrid key exchange will correspond to an 388 ordered pair of two algorithms. For example, a future document could 389 specify that hybrid value 0x2000 corresponds to 390 secp256r1+ntruhrss701, and 0x2001 corresponds to x25519+ntruhrss701. 391 (We note that this is independent from future documents standardizing 392 solely post-quantum key exchange methods, which would have to be 393 assigned their own identifier.) 395 Specific values shall be standardized by IANA in the TLS Supported 396 Groups registry. We suggest that values 0x2000 through 0x2EFF are 397 suitable for hybrid key exchange methods (the leading "2" suggesting 398 that there are 2 algorithms), noting that 0x2A2A is reserved as a 399 GREASE value [GREASE]. This document requests that values 0x2F00 400 through 0x2FFF be reserved for Private Use for hybrid key exchange. 402 enum { 404 /* Elliptic Curve Groups (ECDHE) */ 405 secp256r1(0x0017), secp384r1(0x0018), secp521r1(0x0019), 406 x25519(0x001D), x448(0x001E), 408 /* Finite Field Groups (DHE) */ 409 ffdhe2048(0x0100), ffdhe3072(0x0101), ffdhe4096(0x0102), 410 ffdhe6144(0x0103), ffdhe8192(0x0104), 412 /* Hybrid Key Exchange Methods */ 413 TBD(0xTBD), ..., 415 /* Reserved Code Points */ 416 ffdhe_private_use(0x01FC..0x01FF), 417 hybrid_private_use(0x2F00..0x2FFF), 418 ecdhe_private_use(0xFE00..0xFEFF), 419 (0xFFFF) 420 } NamedGroup; 422 3.2. Transmitting public keys and ciphertexts 424 We take the relatively simple "concatenation approach": the messages 425 from the two algorithms being hybridized will be concatenated 426 together and transmitted as a single value, to avoid having to change 427 existing data structures. The values are directly concatenated, 428 without any additional encoding or length fields; this assumes that 429 the representation and length of elements is fixed once the algorithm 430 is fixed. 432 Recall that in TLS 1.3 a KEM public key or KEM ciphertext is 433 represented as a "KeyShareEntry": 435 struct { 436 NamedGroup group; 437 opaque key_exchange<1..2^16-1>; 438 } KeyShareEntry; 440 These are transmitted in the "extension_data" fields of 441 "KeyShareClientHello" and "KeyShareServerHello" extensions: 443 struct { 444 KeyShareEntry client_shares<0..2^16-1>; 445 } KeyShareClientHello; 447 struct { 448 KeyShareEntry server_share; 449 } KeyShareServerHello; 451 The client's shares are listed in descending order of client 452 preference; the server selects one algorithm and sends its 453 corresponding share. 455 For a hybrid key exchange, the "key_exchange" field of a 456 "KeyShareEntry" is the concatenation of the "key_exchange" field for 457 each of the constituent algorithms. The order of shares in the 458 concatenation is the same as the order of algorithms indicated in the 459 definition of the "NamedGroup". 461 For the client's share, the "key_exchange" are the "pk" outputs of 462 the corresponding KEMs' "KeyGen" algorithms, if that algorithm 463 corresponds to a KEM; or the (EC)DH ephemeral key share, if that 464 algorithm corresponds to an (EC)DH group. For the server's share, 465 the "key_exchange" values are the "ct" outputs of the corresponding 466 KEMs' "Encaps" algorithms, if that algorithm corresponds to a KEM; or 467 the (EC)DH ephemeral key share, if that algorithm corresponds to an 468 (EC)DH group. 470 [TLS13] requires that ``The key_exchange values for each 471 KeyShareEntry MUST be generated independently.'' In the context of 472 this document, since the same algorithm may appear in multiple named 473 groups, we relax the above requirement to allow the same key_exchange 474 value for the same algorithm to be reused in multiple KeyShareEntry 475 records sent in within the same "ClientHello". However, the 476 key_exchange values for each algorithm MUST be generated 477 independently. 479 3.3. Shared secret calculation 481 Here we also take a simple "concatenation approach": the two shared 482 secrets are concatenated together and used as the shared secret in 483 the existing TLS 1.3 key schedule. Again, we do not add any 484 additional structure (length fields) in the concatenation procedure: 485 among all Round 3 finalists and alternate candidates, once the 486 algorithm and variant are specified, the shared secret output length 487 is fixed. 489 In other words, the shared secret is calculated as 491 concatenated_shared_secret = shared_secret_1 || shared_secret_2 493 and inserted into the TLS 1.3 key schedule in place of the (EC)DHE 494 shared secret: 496 0 497 | 498 v 499 PSK -> HKDF-Extract = Early Secret 500 | 501 +-----> Derive-Secret(...) 502 +-----> Derive-Secret(...) 503 +-----> Derive-Secret(...) 504 | 505 v 506 Derive-Secret(., "derived", "") 507 | 508 v 509 concatenated_shared_secret -> HKDF-Extract = Handshake Secret 510 ^^^^^^^^^^^^^^^^^^^^^^^^^^ | 511 +-----> Derive-Secret(...) 512 +-----> Derive-Secret(...) 513 | 514 v 515 Derive-Secret(., "derived", "") 516 | 517 v 518 0 -> HKDF-Extract = Master Secret 519 | 520 +-----> Derive-Secret(...) 521 +-----> Derive-Secret(...) 522 +-----> Derive-Secret(...) 523 +-----> Derive-Secret(...) 525 *FIPS-compliance of shared secret concatenation.* [NIST-SP-800-56C] 526 or [NIST-SP-800-135] give NIST recommendations for key derivation 527 methods in key exchange protocols. Some hybrid combinations may 528 combine the shared secret from a NIST-approved algorithm (e.g., ECDH 529 using the nistp256/secp256r1 curve) with a shared secret from a non- 530 approved algorithm (e.g., post-quantum). [NIST-SP-800-56C] lists 531 simple concatenation as an approved method for generation of a hybrid 532 shared secret in which one of the constituent shared secret is from 533 an approved method. 535 4. Open questions 537 *Larger public keys and/or ciphertexts.* The "HybridKeyExchange" 538 struct in Section 3.2 limits public keys and ciphertexts to 2^16-1 539 bytes; this is bounded by the same (2^16-1)-byte limit on the 540 "key_exchange" field in the "KeyShareEntry" struct. Some post- 541 quantum KEMs have larger public keys and/or ciphertexts; for example, 542 Classic McEliece's smallest parameter set has public key size 261,120 543 bytes. Hence this draft can not accommodate all current NIST Round 2 544 candidates. 546 If it is desired to accommodate algorithms with public keys or 547 ciphertexts larger than 2^16-1 bytes, options include a) revising the 548 TLS 1.3 standard to allow longer "key_exchange" fields; b) creating 549 an alternative extension which is sufficiently large; or c) providing 550 a reference to an external public key, e.g. a URL at which to look up 551 the public key (along with a hash to verify). 553 *Duplication of key shares.* Concatenation of public keys in the 554 "HybridKeyExchange" struct as described in Section 3.2 can result in 555 sending duplicate key shares. For example, if a client wanted to 556 offer support for two combinations, say "secp256r1+sikep503" and 557 "x25519+sikep503", it would end up sending two sikep503 public keys, 558 since the "KeyShareEntry" for each combination contains its own copy 559 of a sikep503 key. This duplication may be more problematic for 560 post-quantum algorithms which have larger public keys. 562 If it is desired to avoid duplication of key shares, options include 563 a) disconnect the use of a combination for the algorithm identifier 564 from the use of concatenation of public keys by introducing new logic 565 and/or data structures (see Appendix B.3.2 or Appendix B.3.3); or b) 566 provide some back reference from a later key share entry to an 567 earlier one. 569 *Resumption.* TLS 1.3 allows for session resumption via a PSK. When 570 a PSK is used during session establishment, an ephemeral key exchange 571 can also be used to enhance forward secrecy. If the original key 572 exchange was hybrid, should an ephemeral key exchange in a resumption 573 of that original key exchange be required to use the same hybrid 574 algorithms? 576 *Failures.* Some post-quantum key exchange algorithms have non- 577 trivial failure rates: two honest parties may fail to agree on the 578 same shared secret with non-negligible probability. Does a non- 579 negligible failure rate affect the security of TLS? How should such 580 a failure be treated operationally? What is an acceptable failure 581 rate? 583 5. IANA Considerations 585 Identifiers for specific key exchange algorithm combinations will be 586 defined in later documents. This document requests IANA reserve 587 values 0x2F00..0x2FFF in the TLS Supported Groups registry for 588 private use for hybrid key exchange methods. 590 6. Security Considerations 592 The shared secrets computed in the hybrid key exchange should be 593 computed in a way that achieves the "hybrid" property: the resulting 594 secret is secure as long as at least one of the component key 595 exchange algorithms is unbroken. See [GIACON] and [BINDEL] for an 596 investigation of these issues. Under the assumption that shared 597 secrets are fixed length once the combination is fixed, the 598 construction from Section 3.3 corresponds to the dual-PRF combiner of 599 [BINDEL] which is shown to preserve security under the assumption 600 that the hash function is a dual-PRF. 602 As noted in Section 2, KEMs used in the manner described in this 603 document MUST explicitly be designed to be secure in the event that 604 the public key is re-used, such as achieving IND-CCA2 security or 605 having a transform like the Fujisaki-Okamoto transform applied. Some 606 IND-CPA-secure post-quantum KEMs (i.e., without countermeasures such 607 as the FO transform) are completely insecure under public key reuse; 608 for example, some lattice-based IND-CPA-secure KEMs are vulnerable to 609 attacks that recover the private key after just a few thousand 610 samples [FLUHRER]. 612 *Public keys, ciphertexts, and secrets should be constant length.* 613 This document assumes that the length of each public key, ciphertext, 614 and shared secret is fixed once the algorithm is fixed. This is the 615 case for all Round 3 finalists and alternate candidates. 617 Note that variable-length secrets are, generally speaking, dangerous. 618 In particular, when using key material of variable length and 619 processing it using hash functions, a timing side channel may arise. 620 In broad terms, when the secret is longer, the hash function may need 621 to process more blocks internally. In some unfortunate 622 circumstances, this has led to timing attacks, e.g. the Lucky 623 Thirteen [LUCKY13] and Raccoon [RACCOON] attacks. 625 Therefore, this specification MUST only be used with algorithms which 626 have fixed-length shared secrets (after the variant has been fixed by 627 the algorithm identifier in the "NamedGroup" negotiation in 628 Section 3.1). 630 7. Acknowledgements 632 These ideas have grown from discussions with many colleagues, 633 including Christopher Wood, Matt Campagna, Eric Crockett, authors of 634 the various hybrid Internet-Drafts and implementations cited in this 635 document, and members of the TLS working group. The immediate 636 impetus for this document came from discussions with attendees at the 637 Workshop on Post-Quantum Software in Mountain View, California, in 638 January 2019. Martin Thomson suggested the (Comb-KDF-1) 639 (Appendix B.4.2) approach. Daniel J. Bernstein and Tanja Lange 640 commented on the risks of reuse of ephemeral public keys. Matt 641 Campagna and the team at Amazon Web Services provided additional 642 suggestions. Nimrod Aviram proposed restricting to fixed-length 643 secrets. 645 8. References 647 8.1. Normative References 649 [TLS13] Rescorla, E., "The Transport Layer Security (TLS) Protocol 650 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 651 . 653 8.2. Informative References 655 [BCNS15] Bos, J., Costello, C., Naehrig, M., and D. Stebila, "Post- 656 Quantum Key Exchange for the TLS Protocol from the Ring 657 Learning with Errors Problem", 2015 IEEE Symposium on 658 Security and Privacy, DOI 10.1109/sp.2015.40, May 2015, 659 . 661 [BERNSTEIN] 662 "Post-Quantum Cryptography", Springer Berlin 663 Heidelberg book, DOI 10.1007/978-3-540-88702-7, 2009, 664 . 666 [BINDEL] Bindel, N., Brendel, J., Fischlin, M., Goncalves, B., and 667 D. Stebila, "Hybrid Key Encapsulation Mechanisms and 668 Authenticated Key Exchange", Post-Quantum Cryptography pp. 669 206-226, DOI 10.1007/978-3-030-25510-7_12, 2019, 670 . 672 [CAMPAGNA] Campagna, M. and E. Crockett, "Hybrid Post-Quantum Key 673 Encapsulation Methods (PQ KEM) for Transport Layer 674 Security 1.2 (TLS)", Work in Progress, Internet-Draft, 675 draft-campagna-tls-bike-sike-hybrid-06, 9 March 2021, 676 . 679 [CECPQ1] Braithwaite, M., "Experimenting with Post-Quantum 680 Cryptography", 7 July 2016, 681 . 684 [CECPQ2] Langley, A., "CECPQ2", 12 December 2018, 685 . 687 [DODIS] Dodis, Y. and J. Katz, "Chosen-Ciphertext Security of 688 Multiple Encryption", Theory of Cryptography pp. 188-209, 689 DOI 10.1007/978-3-540-30576-7_11, 2005, 690 . 692 [ETSI] Campagna, M., Ed. and . others, "Quantum safe cryptography 693 and security: An introduction, benefits, enablers and 694 challengers", ETSI White Paper No. 8 , June 2015, 695 . 698 [EVEN] Even, S. and O. Goldreich, "On the Power of Cascade 699 Ciphers", Advances in Cryptology pp. 43-50, 700 DOI 10.1007/978-1-4684-4730-9_4, 1984, 701 . 703 [EXTERN-PSK] 704 Housley, R., "TLS 1.3 Extension for Certificate-Based 705 Authentication with an External Pre-Shared Key", RFC 8773, 706 DOI 10.17487/RFC8773, March 2020, 707 . 709 [FLUHRER] Fluhrer, S., "Cryptanalysis of ring-LWE based key exchange 710 with key share reuse", Cryptology ePrint Archive, Report 711 2016/085 , January 2016, 712 . 714 [FO] Fujisaki, E. and T. Okamoto, "Secure Integration of 715 Asymmetric and Symmetric Encryption Schemes", Journal of 716 Cryptology Vol. 26, pp. 80-101, 717 DOI 10.1007/s00145-011-9114-1, December 2011, 718 . 720 [FRODO] Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, 721 M., Nikolaenko, V., Raghunathan, A., and D. Stebila, 722 "Frodo: Take off the Ring! Practical, Quantum-Secure Key 723 Exchange from LWE", Proceedings of the 2016 ACM SIGSAC 724 Conference on Computer and Communications Security, 725 DOI 10.1145/2976749.2978425, October 2016, 726 . 728 [GIACON] Giacon, F., Heuer, F., and B. Poettering, "KEM Combiners", 729 Public-Key Cryptography - PKC 2018 pp. 190-218, 730 DOI 10.1007/978-3-319-76578-5_7, 2018, 731 . 733 [GREASE] Benjamin, D., "Applying Generate Random Extensions And 734 Sustain Extensibility (GREASE) to TLS Extensibility", 735 RFC 8701, DOI 10.17487/RFC8701, January 2020, 736 . 738 [HARNIK] Harnik, D., Kilian, J., Naor, M., Reingold, O., and A. 739 Rosen, "On Robust Combiners for Oblivious Transfer and 740 Other Primitives", Lecture Notes in Computer Science pp. 741 96-113, DOI 10.1007/11426639_6, 2005, 742 . 744 [HHK] Hofheinz, D., Hövelmanns, K., and E. Kiltz, "A Modular 745 Analysis of the Fujisaki-Okamoto Transformation", Theory 746 of Cryptography pp. 341-371, 747 DOI 10.1007/978-3-319-70500-2_12, 2017, 748 . 750 [HOFFMAN] Hoffman, P., "The Transition from Classical to Post- 751 Quantum Cryptography", Work in Progress, Internet-Draft, 752 draft-hoffman-c2pq-07, 26 May 2020, 753 . 756 [I-D.irtf-cfrg-hpke] 757 Barnes, R. L., Bhargavan, K., Lipp, B., and C. A. Wood, 758 "Hybrid Public Key Encryption", Work in Progress, 759 Internet-Draft, draft-irtf-cfrg-hpke-08, 15 February 2021, 760 . 763 [IKE-HYBRID] 764 Tjhai, C., Tomlinson, M., Bartlett, G., Fluhrer, S., 765 Geest, D. V., Garcia-Morchon, O., and V. Smyslov, 766 "Framework to Integrate Post-quantum Key Exchanges into 767 Internet Key Exchange Protocol Version 2 (IKEv2)", Work in 768 Progress, Internet-Draft, draft-tjhai-ipsecme-hybrid-qske- 769 ikev2-04, 9 July 2019, . 772 [IKE-PSK] Fluhrer, S., Kampanakis, P., McGrew, D., and V. Smyslov, 773 "Mixing Preshared Keys in the Internet Key Exchange 774 Protocol Version 2 (IKEv2) for Post-quantum Security", 775 RFC 8784, DOI 10.17487/RFC8784, June 2020, 776 . 778 [KIEFER] Kiefer, F. and K. Kwiatkowski, "Hybrid ECDHE-SIDH Key 779 Exchange for TLS", Work in Progress, Internet-Draft, 780 draft-kiefer-tls-ecdhe-sidh-00, 5 November 2018, 781 . 784 [LANGLEY] Langley, A., "Post-quantum confidentiality for TLS", 11 785 April 2018, . 788 [LUCKY13] Al Fardan, N.J. and K.G. Paterson, "Lucky Thirteen: 789 Breaking the TLS and DTLS record protocols", n.d., 790 . 793 [NIELSEN] Nielsen, M.A. and I.L. Chuang, "Quantum Computation and 794 Quantum Information", Cambridge University Press , 2000. 796 [NIST] National Institute of Standards and Technology (NIST), 797 "Post-Quantum Cryptography", n.d., 798 . 800 [NIST-SP-800-135] 801 National Institute of Standards and Technology (NIST), 802 "Recommendation for Existing Application-Specific Key 803 Derivation Functions", December 2011, 804 . 806 [NIST-SP-800-56C] 807 National Institute of Standards and Technology (NIST), 808 "Recommendation for Key-Derivation Methods in Key- 809 Establishment Schemes", August 2020, 810 . 812 [OQS-102] Open Quantum Safe Project, "OQS-OpenSSL-1-0-2_stable", 813 November 2018, . 816 [OQS-111] Open Quantum Safe Project, "OQS-OpenSSL-1-1-1_stable", 817 November 2018, . 820 [RACCOON] Merget, R., Brinkmann, M., Aviram, N., Somorovsky, J., 821 Mittmann, J., and J. Schwenk, "Raccoon Attack: Finding and 822 Exploiting Most-Significant-Bit-Oracles in TLS-DH(E)", 823 September 2020, . 825 [S2N] Amazon Web Services, "Post-quantum TLS now supported in 826 AWS KMS", 4 November 2019, 827 . 830 [SCHANCK] Schanck, J. M. and D. Stebila, "A Transport Layer Security 831 (TLS) Extension For Establishing An Additional Shared 832 Secret", Work in Progress, Internet-Draft, draft-schanck- 833 tls-additional-keyshare-00, 17 April 2017, 834 . 837 [WHYTE12] Schanck, J. M., Whyte, W., and Z. Zhang, "Quantum-Safe 838 Hybrid (QSH) Ciphersuite for Transport Layer Security 839 (TLS) version 1.2", Work in Progress, Internet-Draft, 840 draft-whyte-qsh-tls12-02, 22 July 2016, 841 . 844 [WHYTE13] Whyte, W., Zhang, Z., Fluhrer, S., and O. Garcia-Morchon, 845 "Quantum-Safe Hybrid (QSH) Key Exchange for Transport 846 Layer Security (TLS) version 1.3", Work in Progress, 847 Internet-Draft, draft-whyte-qsh-tls13-06, 3 October 2017, 848 . 851 [XMSS] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. 852 Mohaisen, "XMSS: eXtended Merkle Signature Scheme", 853 RFC 8391, DOI 10.17487/RFC8391, May 2018, 854 . 856 [ZHANG] Zhang, R., Hanaoka, G., Shikata, J., and H. Imai, "On the 857 Security of Multiple Encryption or CCA-security+CCA- 858 security=CCA-security?", Public Key Cryptography - PKC 859 2004 pp. 360-374, DOI 10.1007/978-3-540-24632-9_26, 2004, 860 . 862 Appendix A. Related work 864 Quantum computing and post-quantum cryptography in general are 865 outside the scope of this document. For a general introduction to 866 quantum computing, see a standard textbook such as [NIELSEN]. For an 867 overview of post-quantum cryptography as of 2009, see [BERNSTEIN]. 868 For the current status of the NIST Post-Quantum Cryptography 869 Standardization Project, see [NIST]. For additional perspectives on 870 the general transition from classical to post-quantum cryptography, 871 see for example [ETSI] and [HOFFMAN], among others. 873 There have been several Internet-Drafts describing mechanisms for 874 embedding post-quantum and/or hybrid key exchange in TLS: 876 * Internet-Drafts for TLS 1.2: [WHYTE12], [CAMPAGNA] 878 * Internet-Drafts for TLS 1.3: [KIEFER], [SCHANCK], [WHYTE13] 880 There have been several prototype implementations for post-quantum 881 and/or hybrid key exchange in TLS: 883 * Experimental implementations in TLS 1.2: [BCNS15], [CECPQ1], 884 [FRODO], [OQS-102], [S2N] 886 * Experimental implementations in TLS 1.3: [CECPQ2], [OQS-111] 888 These experimental implementations have taken an ad hoc approach and 889 not attempted to implement one of the drafts listed above. 891 Unrelated to post-quantum but still related to the issue of combining 892 multiple types of keying material in TLS is the use of pre-shared 893 keys, especially the recent TLS working group document on including 894 an external pre-shared key [EXTERN-PSK]. 896 Considering other IETF standards, there is work on post-quantum 897 preshared keys in IKEv2 [IKE-PSK] and a framework for hybrid key 898 exchange in IKEv2 [IKE-HYBRID]. The XMSS hash-based signature scheme 899 has been published as an informational RFC by the IRTF [XMSS]. 901 In the academic literature, [EVEN] initiated the study of combining 902 multiple symmetric encryption schemes; [ZHANG], [DODIS], and [HARNIK] 903 examined combining multiple public key encryption schemes, and 904 [HARNIK] coined the term "robust combiner" to refer to a compiler 905 that constructs a hybrid scheme from individual schemes while 906 preserving security properties. [GIACON] and [BINDEL] examined 907 combining multiple key encapsulation mechanisms. 909 Appendix B. Design Considerations 911 This appendix discusses choices one could make along four distinct 912 axes when integrating hybrid key exchange into TLS 1.3: 914 1. How to negotiate the use of hybridization in general and 915 component algorithms specifically? 917 2. How many component algorithms can be combined? 919 3. How should multiple key shares (public keys / ciphertexts) be 920 conveyed? 922 4. How should multiple shared secrets be combined? 924 The construction in the main body illustrates one selection along 925 each of these axes. The remainder of this appendix outlines various 926 options we have identified for each of these choices. Immediately 927 below we provide a summary list. Options are labelled with a short 928 code in parentheses to provide easy cross-referencing. 930 1. (Neg) (Appendix B.1) How to negotiate the use of hybridization in 931 general and component algorithms specifically? 933 * (Neg-Ind) (Appendix B.1.2) Negotiating component algorithms 934 individually 936 - (Neg-Ind-1) (Appendix B.1.2.1) Traditional algorithms in 937 "ClientHello" "supported_groups" extension, next-gen 938 algorithms in another extension 940 - (Neg-Ind-2) (Appendix B.1.2.2) Both types of algorithms in 941 "supported_groups" with external mapping to tradition/next- 942 gen. 944 - (Neg-Ind-3) (Appendix B.1.2.3) Both types of algorithms in 945 "supported_groups" separated by a delimiter. 947 * (Neg-Comb) (Appendix B.1.3) Negotiating component algorithms 948 as a combination 950 - (Neg-Comb-1) (Appendix B.1.3.1) Standardize "NamedGroup" 951 identifiers for each desired combination. 953 - (Neg-Comb-2) (Appendix B.1.3.2) Use placeholder identifiers 954 in "supported_groups" with an extension defining the 955 combination corresponding to each placeholder. 957 - (Neg-Comb-3) (Appendix B.1.3.3) List combinations by 958 inserting grouping delimiters into "supported_groups" list. 960 2. (Num) (Appendix B.2) How many component algorithms can be 961 combined? 963 * (Num-2) (Appendix B.2.1) Two. 965 * (Num-2+) (Appendix B.2.2) Two or more. 967 3. (Shares) (Appendix B.3) How should multiple key shares (public 968 keys / ciphertexts) be conveyed? 970 * (Shares-Concat) (Appendix B.3.1) Concatenate each combination 971 of key shares. 973 * (Shares-Multiple) (Appendix B.3.2) Send individual key shares 974 for each algorithm. 976 * (Shares-Ext-Additional) (Appendix B.3.3) Use an extension to 977 convey key shares for component algorithms. 979 4. (Comb) (Appendix B.4) How should multiple shared secrets be 980 combined? 982 * (Comb-Concat) (Appendix B.4.1) Concatenate the shared secrets 983 then use directly in the TLS 1.3 key schedule. 985 * (Comb-KDF-1) (Appendix B.4.2) and (Comb-KDF-2) 986 (Appendix B.4.3) KDF the shared secrets together, then use the 987 output in the TLS 1.3 key schedule. 989 * (Comb-XOR) (Appendix B.4.4) XOR the shared secrets then use 990 directly in the TLS 1.3 key schedule. 992 * (Comb-Chain) (Appendix B.4.5) Extend the TLS 1.3 key schedule 993 so that there is a stage of the key schedule for each shared 994 secret. 996 * (Comb-AltInput) (Appendix B.4.6) Use the second shared secret 997 in an alternate (otherwise unused) input in the TLS 1.3 key 998 schedule. 1000 B.1. (Neg) How to negotiate hybridization and component algorithms? 1001 B.1.1. Key exchange negotiation in TLS 1.3 1003 Recall that in TLS 1.3, the key exchange mechanism is negotiated via 1004 the "supported_groups" extension. The "NamedGroup" enum is a list of 1005 standardized groups for Diffie-Hellman key exchange, such as 1006 "secp256r1", "x25519", and "ffdhe2048". 1008 The client, in its "ClientHello" message, lists its supported 1009 mechanisms in the "supported_groups" extension. The client also 1010 optionally includes the public key of one or more of these groups in 1011 the "key_share" extension as a guess of which mechanisms the server 1012 might accept in hopes of reducing the number of round trips. 1014 If the server is willing to use one of the client's requested 1015 mechanisms, it responds with a "key_share" extension containing its 1016 public key for the desired mechanism. 1018 If the server is not willing to use any of the client's requested 1019 mechanisms, the server responds with a "HelloRetryRequest" message 1020 that includes an extension indicating its preferred mechanism. 1022 B.1.2. (Neg-Ind) Negotiating component algorithms individually 1024 In these three approaches, the parties negotiate which traditional 1025 algorithm and which next-gen algorithm to use independently. The 1026 "NamedGroup" enum is extended to include algorithm identifiers for 1027 each next-gen algorithm. 1029 B.1.2.1. (Neg-Ind-1) 1031 The client advertises two lists to the server: one list containing 1032 its supported traditional mechanisms (e.g. via the existing 1033 "ClientHello" "supported_groups" extension), and a second list 1034 containing its supported next-generation mechanisms (e.g., via an 1035 additional "ClientHello" extension). A server could then select one 1036 algorithm from the traditional list, and one algorithm from the next- 1037 generation list. (This is the approach in [SCHANCK].) 1039 B.1.2.2. (Neg-Ind-2) 1041 The client advertises a single list to the server which contains both 1042 its traditional and next-generation mechanisms (e.g., all in the 1043 existing "ClientHello" "supported_groups" extension), but with some 1044 external table provides a standardized mapping of those mechanisms as 1045 either "traditional" or "next-generation". A server could then 1046 select two algorithms from this list, one from each category. 1048 B.1.2.3. (Neg-Ind-3) 1050 The client advertises a single list to the server delimited into 1051 sublists: one for its traditional mechanisms and one for its next- 1052 generation mechanisms, all in the existing "ClientHello" 1053 "supported_groups" extension, with a special code point serving as a 1054 delimiter between the two lists. For example, "supported_groups = 1055 secp256r1, x25519, delimiter, nextgen1, nextgen4". 1057 B.1.3. (Neg-Comb) Negotiating component algorithms as a combination 1059 In these three approaches, combinations of key exchange mechanisms 1060 appear as a single monolithic block; the parties negotiate which of 1061 several combinations they wish to use. 1063 B.1.3.1. (Neg-Comb-1) 1065 The "NamedGroup" enum is extended to include algorithm identifiers 1066 for each *combination* of algorithms desired by the working group. 1067 There is no "internal structure" to the algorithm identifiers for 1068 each combination, they are simply new code points assigned 1069 arbitrarily. The client includes any desired combinations in its 1070 "ClientHello" "supported_groups" list, and the server picks one of 1071 these. This is the approach in [KIEFER] and [OQS-111]. 1073 B.1.3.2. (Neg-Comb-2) 1075 The "NamedGroup" enum is extended to include algorithm identifiers 1076 for each next-gen algorithm. Some additional field/extension is used 1077 to convey which combinations the parties wish to use. For example, 1078 in [WHYTE13], there are distinguished "NamedGroup" called 1079 "hybrid_marker 0", "hybrid_marker 1", "hybrid_marker 2", etc. This 1080 is complemented by a "HybridExtension" which contains mappings for 1081 each numbered "hybrid_marker" to the set of component key exchange 1082 algorithms (2 or more) for that proposed combination. 1084 B.1.3.3. (Neg-Comb-3) 1086 The client lists combinations in "supported_groups" list, using a 1087 special delimiter to indicate combinations. For example, 1088 "supported_groups = combo_delimiter, secp256r1, nextgen1, 1089 combo_delimiter, secp256r1, nextgen4, standalone_delimiter, 1090 secp256r1, x25519" would indicate that the client's highest 1091 preference is the combination secp256r1+nextgen1, the next highest 1092 preference is the combination secp2561+nextgen4, then the single 1093 algorithm secp256r1, then the single algorithm x25519. A hybrid- 1094 aware server would be able to parse these; a hybrid-unaware server 1095 would see "unknown, secp256r1, unknown, unknown, secp256r1, unknown, 1096 unknown, secp256r1, x25519", which it would be able to process, 1097 although there is the potential that every "projection" of a hybrid 1098 list that is tolerable to a client does not result in list that is 1099 tolerable to the client. 1101 B.1.4. Benefits and drawbacks 1103 *Combinatorial explosion.* (Neg-Comb-1) (Appendix B.1.3.1) requires 1104 new identifiers to be defined for each desired combination. The 1105 other 4 options in this section do not. 1107 *Extensions.* (Neg-Ind-1) (Appendix B.1.2.1) and (Neg-Comb-2) 1108 (Appendix B.1.3.2) require new extensions to be defined. The other 1109 options in this section do not. 1111 *New logic.* All options in this section except (Neg-Comb-1) 1112 (Appendix B.1.3.1) require new logic to process negotiation. 1114 *Matching security levels.* (Neg-Ind-1) (Appendix B.1.2.1), 1115 (Neg-Ind-2) (Appendix B.1.2.2), (Neg-Ind-3) (Appendix B.1.2.3), and 1116 (Neg-Comb-2) (Appendix B.1.3.2) allow algorithms of different claimed 1117 security level from their corresponding lists to be combined. For 1118 example, this could result in combining ECDH secp256r1 (classical 1119 security level 128) with NewHope-1024 (classical security level 256). 1120 Implementations dissatisfied with a mismatched security levels must 1121 either accept this mismatch or attempt to renegotiate. (Neg-Ind-1) 1122 (Appendix B.1.2.1), (Neg-Ind-2) (Appendix B.1.2.2), and (Neg-Ind-3) 1123 (Appendix B.1.2.3) give control over the combination to the server; 1124 (Neg-Comb-2) (Appendix B.1.3.2) gives control over the combination to 1125 the client. (Neg-Comb-1) (Appendix B.1.3.1) only allows standardized 1126 combinations, which could be set by TLS working group to have 1127 matching security (provided security estimates do not evolve 1128 separately). 1130 *Backwards-compability.* TLS 1.3-compliant hybrid-unaware servers 1131 should ignore unreocgnized elements in "supported_groups" (Neg-Ind-2) 1132 (Appendix B.1.2.2), (Neg-Ind-3) (Appendix B.1.2.3), (Neg-Comb-1) 1133 (Appendix B.1.3.1), (Neg-Comb-2) (Appendix B.1.3.2) and unrecognized 1134 "ClientHello" extensions (Neg-Ind-1) (Appendix B.1.2.1), (Neg-Comb-2) 1135 (Appendix B.1.3.2). In (Neg-Ind-3) (Appendix B.1.2.3) and 1136 (Neg-Comb-3) (Appendix B.1.3.3), a server that is hybrid-unaware will 1137 ignore the delimiters in "supported_groups", and thus might try to 1138 negotiate an algorithm individually that is only meant to be used in 1139 combination; depending on how such an implementation is coded, it may 1140 also encounter bugs when the same element appears multiple times in 1141 the list. 1143 B.2. (Num) How many component algorithms to combine? 1145 B.2.1. (Num-2) Two 1147 Exactly two algorithms can be combined together in hybrid key 1148 exchange. This is the approach taken in [KIEFER] and [SCHANCK]. 1150 B.2.2. (Num-2+) Two or more 1152 Two or more algorithms can be combined together in hybrid key 1153 exchange. This is the approach taken in [WHYTE13]. 1155 B.2.3. Benefits and Drawbacks 1157 Restricting the number of component algorithms that can be hybridized 1158 to two substantially reduces the generality required. On the other 1159 hand, some adopters may want to further reduce risk by employing 1160 multiple next-gen algorithms built on different cryptographic 1161 assumptions. 1163 B.3. (Shares) How to convey key shares? 1165 In ECDH ephmeral key exchange, the client sends its ephmeral public 1166 key in the "key_share" extension of the "ClientHello" message, and 1167 the server sends its ephmeral public key in the "key_share" extension 1168 of the "ServerHello" message. 1170 For a general key encapsulation mechanism used for ephemeral key 1171 exchange, we imagine that that client generates a fresh KEM public 1172 key / secret pair for each connection, sends it to the client, and 1173 the server responds with a KEM ciphertext. For simplicity and 1174 consistency with TLS 1.3 terminology, we will refer to both of these 1175 types of objects as "key shares". 1177 In hybrid key exchange, we have to decide how to convey the client's 1178 two (or more) key shares, and the server's two (or more) key shares. 1180 B.3.1. (Shares-Concat) Concatenate key shares 1182 The client concatenates the bytes representing its two key shares and 1183 uses this directly as the "key_exchange" value in a "KeyShareEntry" 1184 in its "key_share" extension. The server does the same thing. Note 1185 that the "key_exchange" value can be an octet string of length at 1186 most 2^16-1. This is the approach taken in [KIEFER], [OQS-111], and 1187 [WHYTE13]. 1189 B.3.2. (Shares-Multiple) Send multiple key shares 1191 The client sends multiple key shares directly in the "client_shares" 1192 vectors of the "ClientHello" "key_share" extension. The server does 1193 the same. (Note that while the existing "KeyShareClientHello" struct 1194 allows for multiple key share entries, the existing 1195 "KeyShareServerHello" only permits a single key share entry, so some 1196 modification would be required to use this approach for the server to 1197 send multiple key shares.) 1199 B.3.3. (Shares-Ext-Additional) Extension carrying additional key shares 1201 The client sends the key share for its traditional algorithm in the 1202 original "key_share" extension of the "ClientHello" message, and the 1203 key share for its next-gen algorithm in some additional extension in 1204 the "ClientHello" message. The server does the same thing. This is 1205 the approach taken in [SCHANCK]. 1207 B.3.4. Benefits and Drawbacks 1209 *Backwards compatibility.* (Shares-Multiple) (Appendix B.3.2) is 1210 fully backwards compatible with non-hybrid-aware servers. 1211 (Shares-Ext-Additional) (Appendix B.3.3) is backwards compatible with 1212 non-hybrid-aware servers provided they ignore unrecognized 1213 extensions. (Shares-Concat) (Appendix B.3.1) is backwards-compatible 1214 with non-hybrid aware servers, but may result in duplication / 1215 additional round trips (see below). 1217 *Duplication versus additional round trips.* If a client wants to 1218 offer multiple key shares for multiple combinations in order to avoid 1219 retry requests, then the client may ended up sending a key share for 1220 one algorithm multiple times when using (Shares-Ext-Additional) 1221 (Appendix B.3.3) and (Shares-Concat) (Appendix B.3.1). (For example, 1222 if the client wants to send an ECDH-secp256r1 + McEliece123 key 1223 share, and an ECDH-secp256r1 + NewHope1024 key share, then the same 1224 ECDH public key may be sent twice. If the client also wants to offer 1225 a traditional ECDH-only key share for non-hybrid-aware 1226 implementations and avoid retry requests, then that same ECDH public 1227 key may be sent another time.) (Shares-Multiple) (Appendix B.3.2) 1228 does not result in duplicate key shares. 1230 B.4. (Comb) How to use keys? 1232 Each component key exchange algorithm establishes a shared secret. 1233 These shared secrets must be combined in some way that achieves the 1234 "hybrid" property: the resulting secret is secure as long as at least 1235 one of the component key exchange algorithms is unbroken. 1237 B.4.1. (Comb-Concat) Concatenate keys 1239 Each party concatenates the shared secrets established by each 1240 component algorithm in an agreed-upon order, then feeds that through 1241 the TLS key schedule. In the context of TLS 1.3, this would mean 1242 using the concatenated shared secret in place of the (EC)DHE input to 1243 the second call to "HKDF-Extract" in the TLS 1.3 key schedule: 1245 0 1246 | 1247 v 1248 PSK -> HKDF-Extract = Early Secret 1249 | 1250 +-----> Derive-Secret(...) 1251 +-----> Derive-Secret(...) 1252 +-----> Derive-Secret(...) 1253 | 1254 v 1255 Derive-Secret(., "derived", "") 1256 | 1257 v 1258 concatenated_shared_secret -> HKDF-Extract = Handshake Secret 1259 ^^^^^^^^^^^^^^^^^^^^^^^^^^ | 1260 +-----> Derive-Secret(...) 1261 +-----> Derive-Secret(...) 1262 | 1263 v 1264 Derive-Secret(., "derived", "") 1265 | 1266 v 1267 0 -> HKDF-Extract = Master Secret 1268 | 1269 +-----> Derive-Secret(...) 1270 +-----> Derive-Secret(...) 1271 +-----> Derive-Secret(...) 1272 +-----> Derive-Secret(...) 1274 This is the approach used in [KIEFER], [OQS-111], and [WHYTE13]. 1276 [GIACON] analyzes the security of applying a KDF to concatenated KEM 1277 shared secrets, but their analysis does not exactly apply here since 1278 the transcript of ciphertexts is included in the KDF application 1279 (though it should follow relatively straightforwardly). 1281 [BINDEL] analyzes the security of the (Comb-Concat) approach as 1282 abstracted in their "dualPRF" combiner. They show that, if the 1283 component KEMs are IND-CPA-secure (or IND-CCA-secure), then the 1284 values output by "Derive-Secret" are IND-CPA-secure (respectively, 1285 IND-CCA-secure). An important aspect of their analysis is that each 1286 ciphertext is input to the final PRF calls; this holds for TLS 1.3 1287 since the "Derive-Secret" calls that derive output keys (application 1288 traffic secrets, and exporter and resumption master secrets) include 1289 the transcript hash as input. 1291 B.4.2. (Comb-KDF-1) KDF keys 1293 Each party feeds the shared secrets established by each component 1294 algorithm in an agreed-upon order into a KDF, then feeds that through 1295 the TLS key schedule. In the context of TLS 1.3, this would mean 1296 first applying "HKDF-Extract" to the shared secrets, then using the 1297 output in place of the (EC)DHE input to the second call to "HKDF- 1298 Extract" in the TLS 1.3 key schedule: 1300 0 1301 | 1302 v 1303 PSK -> HKDF-Extract = Early Secret 1304 | 1305 +-----> Derive-Secret(...) 1306 +-----> Derive-Secret(...) 1307 +-----> Derive-Secret(...) 1308 Next-Gen | 1309 | v 1310 (EC)DHE -> HKDF-Extract Derive-Secret(., "derived", "") 1311 | | 1312 v v 1313 output -----> HKDF-Extract = Handshake Secret 1314 ^^^^^^ | 1315 +-----> Derive-Secret(...) 1316 +-----> Derive-Secret(...) 1317 | 1318 v 1319 Derive-Secret(., "derived", "") 1320 | 1321 v 1322 0 -> HKDF-Extract = Master Secret 1323 | 1324 +-----> Derive-Secret(...) 1325 +-----> Derive-Secret(...) 1326 +-----> Derive-Secret(...) 1327 +-----> Derive-Secret(...) 1329 B.4.3. (Comb-KDF-2) KDF keys 1331 Each party concatenates the shared secrets established by each 1332 component algorithm in an agreed-upon order then feeds that into a 1333 KDF, then feeds the result through the TLS key schedule. 1335 Compared with (Comb-KDF-1) (Appendix B.4.2), this method concatenates 1336 the (2 or more) shared secrets prior to input to the KDF, whereas 1337 (Comb-KDF-1) puts the (exactly 2) shared secrets in the two different 1338 input slots to the KDF. 1340 Compared with (Comb-Concat) (Appendix B.4.1), this method has an 1341 extract KDF application. While this adds computational overhead, 1342 this may provide a cleaner abstraction of the hybridization mechanism 1343 for the purposes of formal security analysis. 1345 0 1346 | 1347 v 1348 PSK -> HKDF-Extract = Early Secret 1349 | 1350 +-----> Derive-Secret(...) 1351 +-----> Derive-Secret(...) 1352 +-----> Derive-Secret(...) 1353 | 1354 v 1355 concatenated 0 1356 shared | 1357 secret -> HKDF-Extract Derive-Secret(., "derived", "") 1358 ^^^^^^ | | 1359 v v 1360 output -----> HKDF-Extract = Handshake Secret 1361 ^^^^^^ | 1362 +-----> Derive-Secret(...) 1363 +-----> Derive-Secret(...) 1364 | 1365 v 1366 Derive-Secret(., "derived", "") 1367 | 1368 v 1369 0 -> HKDF-Extract = Master Secret 1370 | 1371 +-----> Derive-Secret(...) 1372 +-----> Derive-Secret(...) 1373 +-----> Derive-Secret(...) 1374 +-----> Derive-Secret(...) 1376 B.4.4. (Comb-XOR) XOR keys 1378 Each party XORs the shared secrets established by each component 1379 algorithm (possibly after padding secrets of different lengths), then 1380 feeds that through the TLS key schedule. In the context of TLS 1.3, 1381 this would mean using the XORed shared secret in place of the (EC)DHE 1382 input to the second call to "HKDF-Extract" in the TLS 1.3 key 1383 schedule. 1385 [GIACON] analyzes the security of applying a KDF to the XORed KEM 1386 shared secrets, but their analysis does not quite apply here since 1387 the transcript of ciphertexts is included in the KDF application 1388 (though it should follow relatively straightforwardly). 1390 B.4.5. (Comb-Chain) Chain of KDF applications for each key 1392 Each party applies a chain of key derivation functions to the shared 1393 secrets established by each component algorithm in an agreed-upon 1394 order; roughly speaking: "F(k1 || F(k2))". In the context of TLS 1395 1.3, this would mean extending the key schedule to have one round of 1396 the key schedule applied for each component algorithm's shared 1397 secret: 1399 0 1400 | 1401 v 1402 PSK -> HKDF-Extract = Early Secret 1403 | 1404 +-----> Derive-Secret(...) 1405 +-----> Derive-Secret(...) 1406 +-----> Derive-Secret(...) 1407 | 1408 v 1409 Derive-Secret(., "derived", "") 1410 | 1411 v 1412 traditional_shared_secret -> HKDF-Extract 1413 ^^^^^^^^^^^^^^^^^^^^^^^^^ | 1414 Derive-Secret(., "derived", "") 1415 | 1416 v 1417 next_gen_shared_secret -> HKDF-Extract = Handshake Secret 1418 ^^^^^^^^^^^^^^^^^^^^^^ | 1419 +-----> Derive-Secret(...) 1420 +-----> Derive-Secret(...) 1421 | 1422 v 1423 Derive-Secret(., "derived", "") 1424 | 1425 v 1426 0 -> HKDF-Extract = Master Secret 1427 | 1428 +-----> Derive-Secret(...) 1429 +-----> Derive-Secret(...) 1430 +-----> Derive-Secret(...) 1431 +-----> Derive-Secret(...) 1433 This is the approach used in [SCHANCK]. 1435 [BINDEL] analyzes the security of this approach as abstracted in 1436 their nested dual-PRF "N" combiner, showing a similar result as for 1437 the dualPRF combiner that it preserves IND-CPA (or IND-CCA) security. 1438 Again their analysis depends on each ciphertext being input to the 1439 final PRF ("Derive-Secret") calls, which holds for TLS 1.3. 1441 B.4.6. (Comb-AltInput) Second shared secret in an alternate KDF input 1443 In the context of TLS 1.3, the next-generation shared secret is used 1444 in place of a currently unused input in the TLS 1.3 key schedule, 1445 namely replacing the "0" "IKM" input to the final "HKDF-Extract": 1447 0 1448 | 1449 v 1450 PSK -> HKDF-Extract = Early Secret 1451 | 1452 +-----> Derive-Secret(...) 1453 +-----> Derive-Secret(...) 1454 +-----> Derive-Secret(...) 1455 | 1456 v 1457 Derive-Secret(., "derived", "") 1458 | 1459 v 1460 traditional_shared_secret -> HKDF-Extract = Handshake Secret 1461 ^^^^^^^^^^^^^^^^^^^^^^^^^ | 1462 +-----> Derive-Secret(...) 1463 +-----> Derive-Secret(...) 1464 | 1465 v 1466 Derive-Secret(., "derived", "") 1467 | 1468 v 1469 next_gen_shared_secret -> HKDF-Extract = Master Secret 1470 ^^^^^^^^^^^^^^^^^^^^^^ | 1471 +-----> Derive-Secret(...) 1472 +-----> Derive-Secret(...) 1473 +-----> Derive-Secret(...) 1474 +-----> Derive-Secret(...) 1476 This approach is not taken in any of the known post-quantum/hybrid 1477 TLS drafts. However, it bears some similarities to the approach for 1478 using external PSKs in [EXTERN-PSK]. 1480 B.4.7. Benefits and Drawbacks 1482 *New logic.* While (Comb-Concat) (Appendix B.4.1), (Comb-KDF-1) 1483 (Appendix B.4.2), and (Comb-KDF-2) (Appendix B.4.3) require new logic 1484 to compute the concatenated shared secret, this value can then be 1485 used by the TLS 1.3 key schedule without changes to the key schedule 1486 logic. In contrast, (Comb-Chain) (Appendix B.4.5) requires the TLS 1487 1.3 key schedule to be extended for each extra component algorithm. 1489 *Philosophical.* The TLS 1.3 key schedule already applies a new stage 1490 for different types of keying material (PSK versus (EC)DHE), so 1491 (Comb-Chain) (Appendix B.4.5) continues that approach. 1493 *Efficiency.* (Comb-KDF-1) (Appendix B.4.2), (Comb-KDF-2) 1494 (Appendix B.4.3), and (Comb-Chain) (Appendix B.4.5) increase the 1495 number of KDF applications for each component algorithm, whereas 1496 (Comb-Concat) (Appendix B.4.1) and (Comb-AltInput) (Appendix B.4.6) 1497 keep the number of KDF applications the same (though with potentially 1498 longer inputs). 1500 *Extensibility.* (Comb-AltInput) (Appendix B.4.6) changes the use of 1501 an existing input, which might conflict with other future changes to 1502 the use of the input. 1504 *More than 2 component algorithms.* The techniques in (Comb-Concat) 1505 (Appendix B.4.1) and (Comb-Chain) (Appendix B.4.5) can naturally 1506 accommodate more than 2 component shared secrets since there is no 1507 distinction to how each shared secret is treated. (Comb-AltInput) 1508 (Appendix B.4.6) would have to make some distinct, since the 2 1509 component shared secrets are used in different ways; for example, the 1510 first shared secret is used as the "IKM" input in the 2nd "HKDF- 1511 Extract" call, and all subsequent shared secrets are concatenated to 1512 be used as the "IKM" input in the 3rd "HKDF-Extract" call. 1514 Authors' Addresses 1516 Douglas Stebila 1517 University of Waterloo 1519 Email: dstebila@uwaterloo.ca 1521 Scott Fluhrer 1522 Cisco Systems 1524 Email: sfluhrer@cisco.com 1526 Shay Gueron 1527 University of Haifa and Amazon Web Services 1529 Email: shay.gueron@gmail.com