idnits 2.17.1 draft-ietf-tls-hybrid-design-00.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 358: '...in this document MUST explicitly be de...' RFC 2119 keyword, line 363: '... KEM public keys MUST ensure that the ...' RFC 2119 keyword, line 365: '...lyses. Implementations MUST NOT reuse...' RFC 2119 keyword, line 473: '... KeyShareEntry MUST be generated ind...' RFC 2119 keyword, line 478: '...s for each algorithm MUST be generated...' (1 more instance...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (15 April 2020) is 1465 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-03 == 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 (~~), 5 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group D. Stebila 3 Internet-Draft University of Waterloo 4 Intended status: Informational S. Fluhrer 5 Expires: 17 October 2020 Cisco Systems 6 S. Gueron 7 U. Haifa, Amazon Web Services 8 15 April 2020 10 Hybrid key exchange in TLS 1.3 11 draft-ietf-tls-hybrid-design-00 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 17 October 2020. 43 Copyright Notice 45 Copyright (c) 2020 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 . . . . . . . . . . . . . . . . . . . . . . . . . . 5 64 1.5. Goals . . . . . . . . . . . . . . . . . . . . . . . . . . 6 65 2. Key encapsulation mechanisms . . . . . . . . . . . . . . . . 7 66 3. Construction for hybrid key exchange . . . . . . . . . . . . 8 67 3.1. Negotiation . . . . . . . . . . . . . . . . . . . . . . . 8 68 3.2. Transmitting public keys and ciphertexts . . . . . . . . 9 69 3.3. Shared secret calculation . . . . . . . . . . . . . . . . 11 70 4. Open questions . . . . . . . . . . . . . . . . . . . . . . . 12 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? . . . . . . . . . . . . . . . . . . . . . . . 23 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-00: 133 - Allow key_exchange values from the same algorithm to be reused 134 across multiple KeyShareEntry records in the same ClientHello. 136 * draft-stebila-tls-hybrid-design-03: 138 - Add requirement for KEMs to provide protection against key 139 reuse. 141 - Clarify FIPS-compliance of shared secret concatenation method. 143 * draft-stebila-tls-hybrid-design-02: 145 - Design considerations from draft-stebila-tls-hybrid-design-00 146 and draft-stebila-tls-hybrid-design-01 are moved to the 147 appendix. 149 - A single construction is given in the main body. 151 * draft-stebila-tls-hybrid-design-01: 153 - Add (Comb-KDF-1) (Appendix B.4.2) and (Comb-KDF-2) 154 (Appendix B.4.3) options. 156 - Add two candidate instantiations. 158 * draft-stebila-tls-hybrid-design-00: Initial version. 160 1.2. Terminology 162 For the purposes of this document, it is helpful to be able to divide 163 cryptographic algorithms into two classes: 165 * "Traditional" algorithms: Algorithms which are widely deployed 166 today, but which may be deprecated in the future. In the context 167 of TLS 1.3 in 2019, examples of traditional key exchange 168 algorithms include elliptic curve Diffie-Hellman using secp256r1 169 or x25519, or finite-field Diffie-Hellman. 171 * "Next-generation" (or "next-gen") algorithms: Algorithms which are 172 not yet widely deployed, but which may eventually be widely 173 deployed. An additional facet of these algorithms may be that we 174 have less confidence in their security due to them being 175 relatively new or less studied. This includes "post-quantum" 176 algorithms. 178 "Hybrid" key exchange, in this context, means the use of two (or 179 more) key exchange algorithms based on different cryptographic 180 assumptions, e.g., one traditional algorithm and one next-gen 181 algorithm, with the purpose of the final session key being secure as 182 long as at least one of the component key exchange algorithms remains 183 unbroken. We use the term "component" algorithms to refer to the 184 algorithms combined in a hybrid key exchange. 186 The primary motivation of this document is preparing for post-quantum 187 algorithms. However, it is possible that public key cryptography 188 based on alternative mathematical constructions will be required 189 independent of the advent of a quantum computer, for example because 190 of a cryptanalytic breakthrough. As such we opt for the more generic 191 term "next-generation" algorithms rather than exclusively "post- 192 quantum" algorithms. 194 Note that TLS 1.3 uses the phrase "groups" to refer to key exchange 195 algorithms - for example, the "supported_groups" extension - since 196 all key exchange algorithms in TLS 1.3 are Diffie-Hellman-based. As 197 a result, some parts of this document will refer to data structures 198 or messages with the term "group" in them despite using a key 199 exchange algorithm that is not Diffie-Hellman-based nor a group. 201 1.3. Motivation for use of hybrid key exchange 203 A hybrid key exchange algorithm allows early adopters eager for post- 204 quantum security to have the potential of post-quantum security 205 (possibly from a less-well-studied algorithm) while still retaining 206 at least the security currently offered by traditional algorithms. 207 They may even need to retain traditional algorithms due to regulatory 208 constraints, for example FIPS compliance. 210 Ideally, one would not use hybrid key exchange: one would have 211 confidence in a single algorithm and parameterization that will stand 212 the test of time. However, this may not be the case in the face of 213 quantum computers and cryptanalytic advances more generally. 215 Many (though not all) post-quantum algorithms currently under 216 consideration are relatively new; they have not been subject to the 217 same depth of study as RSA and finite-field or elliptic curve Diffie- 218 Hellman, and thus the security community does not necessarily have as 219 much confidence in their fundamental security, or the concrete 220 security level of specific parameterizations. 222 Moreover, it is possible that even by the end of the NIST Post- 223 Quantum Cryptography Standardization Project, and for a period of 224 time thereafter, conservative users may not have full confidence in 225 some algorithms. 227 As such, there may be users for whom hybrid key exchange is an 228 appropriate step prior to an eventual transition to next-generation 229 algorithms. 231 1.4. Scope 233 This document focuses on hybrid ephemeral key exchange in TLS 1.3 234 [TLS13]. It intentionally does not address: 236 * Selecting which next-generation algorithms to use in TLS 1.3, nor 237 algorithm identifiers nor encoding mechanisms for next-generation 238 algorithms. This selection will be based on the recommendations 239 by the Crypto Forum Research Group (CFRG), which is currently 240 waiting for the results of the NIST Post-Quantum Cryptography 241 Standardization Project [NIST]. 243 * Authentication using next-generation algorithms. If a 244 cryptographic assumption is broken due to the advent of a quantum 245 computer or some other cryptanalytic breakthrough, confidentiality 246 of information can be broken retroactively by any adversary who 247 has passively recorded handshakes and encrypted communications. 248 In contrast, session authentication cannot be retroactively 249 broken. 251 1.5. Goals 253 The primary goal of a hybrid key exchange mechanism is to facilitate 254 the establishment of a shared secret which remains secure as long as 255 as one of the component key exchange mechanisms remains unbroken. 257 In addition to the primary cryptographic goal, there may be several 258 additional goals in the context of TLS 1.3: 260 * *Backwards compatibility:* Clients and servers who are "hybrid- 261 aware", i.e., compliant with whatever hybrid key exchange standard 262 is developed for TLS, should remain compatible with endpoints and 263 middle-boxes that are not hybrid-aware. The three scenarios to 264 consider are: 266 1. Hybrid-aware client, hybrid-aware server: These parties should 267 establish a hybrid shared secret. 269 2. Hybrid-aware client, non-hybrid-aware server: These parties 270 should establish a traditional shared secret (assuming the 271 hybrid-aware client is willing to downgrade to traditional- 272 only). 274 3. Non-hybrid-aware client, hybrid-aware server: These parties 275 should establish a traditional shared secret (assuming the 276 hybrid-aware server is willing to downgrade to traditional- 277 only). 279 Ideally backwards compatibility should be achieved without extra 280 round trips and without sending duplicate information; see below. 282 * *High performance:* Use of hybrid key exchange should not be 283 prohibitively expensive in terms of computational performance. In 284 general this will depend on the performance characteristics of the 285 specific cryptographic algorithms used, and as such is outside the 286 scope of this document. See [BCNS15], [CECPQ1], [FRODO] for 287 preliminary results about performance characteristics. 289 * *Low latency:* Use of hybrid key exchange should not substantially 290 increase the latency experienced to establish a connection. 291 Factors affecting this may include the following. 293 - The computational performance characteristics of the specific 294 algorithms used. See above. 296 - The size of messages to be transmitted. Public key and 297 ciphertext sizes for post-quantum algorithms range from 298 hundreds of bytes to over one hundred kilobytes, so this impact 299 can be substantially. See [BCNS15], [FRODO] for preliminary 300 results in a laboratory setting, and [LANGLEY] for preliminary 301 results on more realistic networks. 303 - Additional round trips added to the protocol. See below. 305 * *No extra round trips:* Attempting to negotiate hybrid key 306 exchange should not lead to extra round trips in any of the three 307 hybrid-aware/non-hybrid-aware scenarios listed above. 309 * *Minimal duplicate information:* Attempting to negotiate hybrid 310 key exchange should not mean having to send multiple public keys 311 of the same type. 313 2. Key encapsulation mechanisms 315 In the context of the NIST Post-Quantum Cryptography Standardization 316 Project, key exchange algorithms are formulated as key encapsulation 317 mechanisms (KEMs), which consist of three algorithms: 319 * "KeyGen() -> (pk, sk)": A probabilistic key generation algorithm, 320 which generates a public key "pk" and a secret key "sk". 322 * "Encaps(pk) -> (ct, ss)": A probabilistic encapsulation algorithm, 323 which takes as input a public key "pk" and outputs a ciphertext 324 "ct" and shared secret "ss". 326 * "Decaps(sk, ct) -> ss": A decapsulation algorithm, which takes as 327 input a secret key "sk" and ciphertext "ct" and outputs a shared 328 secret "ss", or in some cases a distinguished error value. 330 The main security property for KEMs is indistinguishability under 331 adaptive chosen ciphertext attack (IND-CCA2), which means that shared 332 secret values should be indistinguishable from random strings even 333 given the ability to have arbitrary ciphertexts decapsulated. IND- 334 CCA2 corresponds to security against an active attacker, and the 335 public key / secret key pair can be treated as a long-term key or 336 reused. A common design pattern for obtaining security under key 337 reuse is to apply the Fujisaki-Okamoto (FO) transform [FO] or a 338 variant thereof [HHK]. 340 A weaker security notion is indistinguishability under chosen 341 plaintext attack (IND-CPA), which means that the shared secret values 342 should be indistinguishable from random strings given a copy of the 343 public key. IND-CPA roughly corresponds to security against a 344 passive attacker, and sometimes corresponds to one-time key exchange. 346 Key exchange in TLS 1.3 is phrased in terms of Diffie-Hellman key 347 exchange in a group. DH key exchange can be modeled as a KEM, with 348 "KeyGen" corresponding to selecting an exponent "x" as the secret key 349 and computing the public key "g^x"; encapsulation corresponding to 350 selecting an exponent "y", computing the ciphertext "g^y" and the 351 shared secret "g^(xy)", and decapsulation as computing the shared 352 secret "g^(xy)". See [I-D.irtf-cfrg-hpke] for more details of such 353 Diffie-Hellman-based key encapsulation mechanisms. 355 TLS 1.3 does not require that ephemeral public keys be used only in a 356 single key exchange session; some implementations may reuse them, at 357 the cost of limited forward secrecy. As a result, any KEM used in 358 the manner described in this document MUST explicitly be designed to 359 be secure in the event that the public key is re-used, such as 360 achieving IND-CCA2 security or having a transform like the Fujisaki- 361 Okamoto transform [FO] [HHK] applied. While it is recommended that 362 implementations avoid reuse of KEM public keys, implementations that 363 do reuse KEM public keys MUST ensure that the number of reuses of a 364 KEM public key abides by any bounds in the specification of the KEM 365 or subsequent security analyses. Implementations MUST NOT reuse 366 randomness in the generation of KEM ciphertexts. 368 3. Construction for hybrid key exchange 370 3.1. Negotiation 372 Each particular combination of algorithms in a hybrid key exchange 373 will be represented as a "NamedGroup" and sent in the 374 "supported_groups" extension. No internal structure or grammar is 375 implied or required in the value of the identifier; they are simply 376 opaque identifiers. 378 Each value representing a hybrid key exchange will correspond to an 379 ordered pair of two algorithms. For example, a future document could 380 specify that hybrid value 0x2000 corresponds to 381 secp256r1+ntruhrss701, and 0x2001 corresponds to x25519+ntruhrss701. 382 (We note that this is independent from future documents standardizing 383 solely post-quantum key exchange methods, which would have to be 384 assigned their own identifier.) 386 Specific values shall be standardized by IANA in the TLS Supported 387 Groups registry. We suggest that values 0x2000 through 0x2EFF are 388 suitable for hybrid key exchange methods (the leading "2" suggesting 389 that there are 2 algorithms), noting that 0x2A2A is reserved as a 390 GREASE value [GREASE]. This document requests that values 0x2F00 391 through 0x2FFF be reserved for Private Use for hybrid key exchange. 393 enum { 395 /* Elliptic Curve Groups (ECDHE) */ 396 secp256r1(0x0017), secp384r1(0x0018), secp521r1(0x0019), 397 x25519(0x001D), x448(0x001E), 399 /* Finite Field Groups (DHE) */ 400 ffdhe2048(0x0100), ffdhe3072(0x0101), ffdhe4096(0x0102), 401 ffdhe6144(0x0103), ffdhe8192(0x0104), 403 /* Hybrid Key Exchange Methods */ 404 TBD(0xTBD), ..., 406 /* Reserved Code Points */ 407 ffdhe_private_use(0x01FC..0x01FF), 408 hybrid_private_use(0x2F00..0x2FFF), 409 ecdhe_private_use(0xFE00..0xFEFF), 410 (0xFFFF) 411 } NamedGroup; 413 3.2. Transmitting public keys and ciphertexts 415 We take the relatively simple "concatenation approach": the messages 416 from the two algorithms being hybridized will be concatenated 417 together and transmitted as a single value, to avoid having to change 418 existing data structures. However we do add structure in the 419 concatenation procedure, specifically including length fields, so 420 that the concatenation operation is unambiguous. Note that among the 421 Round 2 candidates in the NIST Post-Quantum Cryptography 422 Standardization Project, not all algorithms have fixed public key 423 sizes; for example, the SIKE key encapsulation mechanism permits 424 compressed or uncompressed public keys at each security level, and 425 the compressed and uncompressed formats are interoperable. 427 Recall that in TLS 1.3 a KEM public key or KEM ciphertext is 428 represented as a "KeyShareEntry": 430 struct { 431 NamedGroup group; 432 opaque key_exchange<1..2^16-1>; 433 } KeyShareEntry; 435 These are transmitted in the "extension_data" fields of 436 "KeyShareClientHello" and "KeyShareServerHello" extensions: 438 struct { 439 KeyShareEntry client_shares<0..2^16-1>; 440 } KeyShareClientHello; 442 struct { 443 KeyShareEntry server_share; 444 } KeyShareServerHello; 446 The client's shares are listed in descending order of client 447 preference; the server selects one algorithm and sends its 448 corresponding share. 450 For a hybrid key exchange, the "key_exchange" field of a 451 "KeyShareEntry" is the following data structure: 453 struct { 454 opaque key_exchange_1<1..2^16-1>; 455 opaque key_exchange_2<1..2^16-1>; 456 } HybridKeyExchange 458 The order of shares in the "HybridKeyExchange" struct is the same as 459 the order of algorithms indicated in the definition of the 460 "NamedGroup". 462 For the client's share, the "key_exchange_1" and "key_exchange_2" 463 values are the "pk" outputs of the corresponding KEMs' "KeyGen" 464 algorithms, if that algorithm corresponds to a KEM; or the (EC)DH 465 ephemeral key share, if that algorithm corresponds to an (EC)DH 466 group. For the server's share, the "key_exchange_1" and 467 "key_exchange_2" values are the "ct" outputs of the corresponding 468 KEMs' "Encaps" algorithms, if that algorithm corresponds to a KEM; or 469 the (EC)DH ephemeral key share, if that algorithm corresponds to an 470 (EC)DH group. 472 [TLS13] requires that ``The key_exchange values for each 473 KeyShareEntry MUST be generated independently.'' In the context of 474 this document, since the same algorithm may appear in multiple named 475 groups, we relax the above requirement to allow the same key_exchange 476 value for the same algorithm to be reused in multiple KeyShareEntry 477 records sent in within the same "ClientHello". However, the 478 key_exchange values for each algorithm MUST be generated 479 independently. 481 3.3. Shared secret calculation 483 Here we also take a simple "concatenation approach": the two shared 484 secrets are concatenated together and used as the shared secret in 485 the existing TLS 1.3 key schedule. In this case, we do not add any 486 additional structure (length fields) in the concatenation procedure: 487 among all Round 2 candidates, once the algorithm and variant are 488 specified, the shared secret output length is fixed. 490 In other words, the shared secret is calculated as 492 concatenated_shared_secret = shared_secret_1 || shared_secret_2 494 and inserted into the TLS 1.3 key schedule in place of the (EC)DHE 495 shared secret: 497 0 498 | 499 v 500 PSK -> HKDF-Extract = Early Secret 501 | 502 +-----> Derive-Secret(...) 503 +-----> Derive-Secret(...) 504 +-----> Derive-Secret(...) 505 | 506 v 507 Derive-Secret(., "derived", "") 508 | 509 v 510 concatenated_shared_secret -> HKDF-Extract = Handshake Secret 511 ^^^^^^^^^^^^^^^^^^^^^^^^^^ | 512 +-----> Derive-Secret(...) 513 +-----> Derive-Secret(...) 514 | 515 v 516 Derive-Secret(., "derived", "") 517 | 518 v 519 0 -> HKDF-Extract = Master Secret 520 | 521 +-----> Derive-Secret(...) 522 +-----> Derive-Secret(...) 523 +-----> Derive-Secret(...) 524 +-----> Derive-Secret(...) 526 *FIPS-compliance of shared secret concatenation.* [NIST-SP-800-56C] 527 or [NIST-SP-800-135] give NIST recommendations for key derivation 528 methods in key exchange protocols. Some hybrid combinations may 529 combine the shared secret from a NIST-approved algorithm (e.g., ECDH 530 using the nistp256/secp256r1 curve) with a shared secret from a non- 531 approved algorithm (e.g., post-quantum). Although the simple 532 concatenation approach above is not currently an approved method in 533 [NIST-SP-800-56C] or [NIST-SP-800-135], NIST indicated in January 534 2020 that a forthcoming revision of [NIST-SP-800-56C] will list 535 simple concatenation as an approved method [NIST-FAQ]. 537 4. Open questions 539 *Larger public keys and/or ciphertexts.* The "HybridKeyExchange" 540 struct in Section 3.2 limits public keys and ciphertexts to 2^16-1 541 bytes; this is bounded by the same (2^16-1)-byte limit on the 542 "key_exchange" field in the "KeyShareEntry" struct. Some post- 543 quantum KEMs have larger public keys and/or ciphertexts; for example, 544 Classic McEliece's smallest parameter set has public key size 261,120 545 bytes. Hence this draft can not accommodate all current NIST Round 2 546 candidates. 548 If it is desired to accommodate algorithms with public keys or 549 ciphertexts larger than 2^16-1 bytes, options include a) revising the 550 TLS 1.3 standard to allow longer "key_exchange" fields; b) creating 551 an alternative extension which is sufficiently large; or c) providing 552 a reference to an external public key, e.g. a URL at which to look up 553 the public key (along with a hash to verify). 555 *Duplication of key shares.* Concatenation of public keys in the 556 "HybridKeyExchange" struct as described in Section 3.2 can result in 557 sending duplicate key shares. For example, if a client wanted to 558 offer support for two combinations, say "secp256r1+sikep503" and 559 "x25519+sikep503", it would end up sending two sikep503 public keys, 560 since the "KeyShareEntry" for each combination contains its own copy 561 of a sikep503 key. This duplication may be more problematic for 562 post-quantum algorithms which have larger public keys. 564 If it is desired to avoid duplication of key shares, options include 565 a) disconnect the use of a combination for the algorithm identifier 566 from the use of concatenation of public keys by introducing new logic 567 and/or data structures (see Appendix B.3.2 or Appendix B.3.3); or b) 568 provide some back reference from a later key share entry to an 569 earlier one. 571 *Variable-length shared secrets.* The shared secret calculation in 572 Section 3.3 directly concatenates the shared secret values of each 573 scheme, rather than encoding them with length fields. This 574 implicitly assumes that the length of each shared secret is fixed 575 once the algorithm is fixed. This is the case for all Round 2 576 candidates. 578 However, if it is envisioned that this specification be used with 579 algorithms which do not have fixed-length shared secrets (after the 580 variant has been fixed by the algorithm identifier in the 581 "NamedGroup" negotiation in Section 3.1), then Section 3.3 should be 582 revised to use an unambiguous concatenation method such as the 583 following: 585 struct { 586 opaque shared_secret_1<1..2^16-1>; 587 opaque shared_secret_2<1..2^16-1>; 588 } HybridSharedSecret 590 Guidance from the working group is particularly requested on this 591 point. 593 *Resumption.* TLS 1.3 allows for session resumption via a PSK. When 594 a PSK is used during session establishment, an ephemeral key exchange 595 can also be used to enhance forward secrecy. If the original key 596 exchange was hybrid, should an ephemeral key exchange in a resumption 597 of that original key exchange be required to use the same hybrid 598 algorithms? 600 *Failures.* Some post-quantum key exchange algorithms have non- 601 trivial failure rates: two honest parties may fail to agree on the 602 same shared secret with non-negligible probability. Does a non- 603 negligible failure rate affect the security of TLS? How should such 604 a failure be treated operationally? What is an acceptable failure 605 rate? 607 5. IANA Considerations 609 Identifiers for specific key exchange algorithm combinations will be 610 defined in later documents. This document requests IANA reserve 611 values 0x2F00..0x2FFF in the TLS Supported Groups registry for 612 private use for hybrid key exchange methods. 614 6. Security Considerations 616 The shared secrets computed in the hybrid key exchange should be 617 computed in a way that achieves the "hybrid" property: the resulting 618 secret is secure as long as at least one of the component key 619 exchange algorithms is unbroken. See [GIACON] and [BINDEL] for an 620 investigation of these issues. Under the assumption that shared 621 secrets are fixed length once the combination is fixed, the 622 construction from Section 3.3 corresponds to the dual-PRF combiner of 623 [BINDEL] which is shown to preserve security under the assumption 624 that the hash function is a dual-PRF. 626 As noted in Section 2, KEMs used in the manner described in this 627 document MUST explicitly be designed to be secure in the event that 628 the public key is re-used, such as achieving IND-CCA2 security or 629 having a transform like the Fujisaki-Okamoto transform applied. Some 630 IND-CPA-secure post-quantum KEMs (i.e., without countermeasures such 631 as the FO transform) are completely insecure under public key reuse; 632 for example, some lattice-based IND-CPA-secure KEMs are vulnerable to 633 attacks that recover the private key after just a few thousand 634 samples [FLUHRER]. 636 7. Acknowledgements 638 These ideas have grown from discussions with many colleagues, 639 including Christopher Wood, Matt Campagna, Eric Crockett, authors of 640 the various hybrid Internet-Drafts and implementations cited in this 641 document, and members of the TLS working group. The immediate 642 impetus for this document came from discussions with attendees at the 643 Workshop on Post-Quantum Software in Mountain View, California, in 644 January 2019. Martin Thomson suggested the (Comb-KDF-1) 645 (Appendix B.4.2) approach. Daniel J. Bernstein and Tanja Lange 646 commented on the risks of reuse of ephemeral public keys. Matt 647 Campagna and the team at Amazon Web Services provided additional 648 suggestions. 650 8. References 652 8.1. Normative References 654 [TLS13] Rescorla, E., "The Transport Layer Security (TLS) Protocol 655 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 656 . 658 8.2. Informative References 660 [BCNS15] Bos, J., Costello, C., Naehrig, M., and D. Stebila, "Post- 661 Quantum Key Exchange for the TLS Protocol from the Ring 662 Learning with Errors Problem", DOI 10.1109/sp.2015.40, 663 2015 IEEE Symposium on Security and Privacy, May 2015, 664 . 666 [BERNSTEIN] 667 "Post-Quantum Cryptography", 668 DOI 10.1007/978-3-540-88702-7, Springer Berlin 669 Heidelberg book, 2009, 670 . 672 [BINDEL] Bindel, N., Brendel, J., Fischlin, M., Goncalves, B., and 673 D. Stebila, "Hybrid Key Encapsulation Mechanisms and 674 Authenticated Key Exchange", 675 DOI 10.1007/978-3-030-25510-7_12, Post-Quantum 676 Cryptography pp. 206-226, 2019, 677 . 679 [CAMPAGNA] Campagna, M. and E. Crockett, "Hybrid Post-Quantum Key 680 Encapsulation Methods (PQ KEM) for Transport Layer 681 Security 1.2 (TLS)", Work in Progress, Internet-Draft, 682 draft-campagna-tls-bike-sike-hybrid-03, 6 March 2020, 683 . 686 [CECPQ1] Braithwaite, M., "Experimenting with Post-Quantum 687 Cryptography", 7 July 2016, 688 . 691 [CECPQ2] Langley, A., "CECPQ2", 12 December 2018, 692 . 694 [DODIS] Dodis, Y. and J. Katz, "Chosen-Ciphertext Security of 695 Multiple Encryption", DOI 10.1007/978-3-540-30576-7_11, 696 Theory of Cryptography pp. 188-209, 2005, 697 . 699 [ETSI] Campagna, M., Ed. and . others, "Quantum safe cryptography 700 and security: An introduction, benefits, enablers and 701 challengers", ETSI White Paper No. 8 , June 2015, 702 . 705 [EVEN] Even, S. and O. Goldreich, "On the Power of Cascade 706 Ciphers", DOI 10.1007/978-1-4684-4730-9_4, Advances in 707 Cryptology pp. 43-50, 1984, 708 . 710 [EXTERN-PSK] 711 Housley, R., "TLS 1.3 Extension for Certificate-based 712 Authentication with an External Pre-Shared Key", Work in 713 Progress, Internet-Draft, draft-ietf-tls-tls13-cert-with- 714 extern-psk-07, 23 December 2019, . 718 [FLUHRER] Fluhrer, S., "Cryptanalysis of ring-LWE based key exchange 719 with key share reuse", Cryptology ePrint Archive, Report 720 2016/085 , January 2016, 721 . 723 [FO] Fujisaki, E. and T. Okamoto, "Secure Integration of 724 Asymmetric and Symmetric Encryption Schemes", 725 DOI 10.1007/s00145-011-9114-1, Journal of Cryptology Vol. 726 26, pp. 80-101, December 2011, 727 . 729 [FRODO] Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, 730 M., Nikolaenko, V., Raghunathan, A., and D. Stebila, 731 "Frodo", DOI 10.1145/2976749.2978425, Proceedings of the 732 2016 ACM SIGSAC Conference on Computer and Communications 733 Security - CCS'16, 2016, 734 . 736 [GIACON] Giacon, F., Heuer, F., and B. Poettering, "KEM Combiners", 737 DOI 10.1007/978-3-319-76578-5_7, Public-Key Cryptography - 738 PKC 2018 pp. 190-218, 2018, 739 . 741 [GREASE] Benjamin, D., "Applying GREASE to TLS Extensibility", Work 742 in Progress, Internet-Draft, draft-ietf-tls-grease-04, 22 743 August 2019, . 746 [HARNIK] Harnik, D., Kilian, J., Naor, M., Reingold, O., and A. 747 Rosen, "On Robust Combiners for Oblivious Transfer and 748 Other Primitives", DOI 10.1007/11426639_6, Lecture Notes 749 in Computer Science pp. 96-113, 2005, 750 . 752 [HHK] Hofheinz, D., Hövelmanns, K., and E. Kiltz, "A Modular 753 Analysis of the Fujisaki-Okamoto Transformation", 754 DOI 10.1007/978-3-319-70500-2_12, Theory of 755 Cryptography pp. 341-371, 2017, 756 . 758 [HOFFMAN] Hoffman, P., "The Transition from Classical to Post- 759 Quantum Cryptography", Work in Progress, Internet-Draft, 760 draft-hoffman-c2pq-06, 25 November 2019, 761 . 764 [I-D.irtf-cfrg-hpke] 765 Barnes, R. and K. Bhargavan, "Hybrid Public Key 766 Encryption", Work in Progress, Internet-Draft, draft-irtf- 767 cfrg-hpke-02, 4 November 2019, . 770 [IKE-HYBRID] 771 Tjhai, C., Tomlinson, M., grbartle@cisco.com, g., Fluhrer, 772 S., Geest, D., Garcia-Morchon, O., and V. Smyslov, 773 "Framework to Integrate Post-quantum Key Exchanges into 774 Internet Key Exchange Protocol Version 2 (IKEv2)", Work in 775 Progress, Internet-Draft, draft-tjhai-ipsecme-hybrid-qske- 776 ikev2-04, 9 July 2019, . 779 [IKE-PSK] Fluhrer, S., Kampanakis, P., McGrew, D., and V. Smyslov, 780 "Mixing Preshared Keys in IKEv2 for Post-quantum 781 Security", Work in Progress, Internet-Draft, draft-ietf- 782 ipsecme-qr-ikev2-11, 14 January 2020, 783 . 786 [KIEFER] Kiefer, F. and K. Kwiatkowski, "Hybrid ECDHE-SIDH Key 787 Exchange for TLS", Work in Progress, Internet-Draft, 788 draft-kiefer-tls-ecdhe-sidh-00, 5 November 2018, 789 . 792 [LANGLEY] Langley, A., "Post-quantum confidentiality for TLS", 11 793 April 2018, . 796 [NIELSEN] Nielsen, M.A. and I.L. Chuang, "Quantum Computation and 797 Quantum Information", Cambridge University Press , 2000. 799 [NIST] National Institute of Standards and Technology (NIST), 800 "Post-Quantum Cryptography", n.d., 801 . 803 [NIST-FAQ] National Institute of Standards and Technology (NIST), 804 "Post-Quantum Cryptography - FAQs", 28 January 2020, 805 . 808 [NIST-SP-800-135] 809 National Institute of Standards and Technology (NIST), 810 "Recommendation for Existing Application-Specific Key 811 Derivation Functions", December 2011, 812 . 814 [NIST-SP-800-56C] 815 National Institute of Standards and Technology (NIST), 816 "Recommendation for Key-Derivation Methods in Key- 817 Establishment Schemes", April 2018, 818 . 820 [OQS-102] Open Quantum Safe Project, "OQS-OpenSSL-1-0-2_stable", 821 November 2018, . 824 [OQS-111] Open Quantum Safe Project, "OQS-OpenSSL-1-1-1_stable", 825 November 2018, . 828 [S2N] Amazon Web Services, "Post-quantum TLS now supported in 829 AWS KMS", 4 November 2019, 830 . 833 [SCHANCK] Schanck, J. and D. Stebila, "A Transport Layer Security 834 (TLS) Extension For Establishing An Additional Shared 835 Secret", Work in Progress, Internet-Draft, draft-schanck- 836 tls-additional-keyshare-00, 17 April 2017, 837 . 840 [WHYTE12] Schanck, J., Whyte, W., and Z. Zhang, "Quantum-Safe Hybrid 841 (QSH) Ciphersuite for Transport Layer Security (TLS) 842 version 1.2", Work in Progress, Internet-Draft, draft- 843 whyte-qsh-tls12-02, 22 July 2016, . 846 [WHYTE13] Whyte, W., Zhang, Z., Fluhrer, S., and O. Garcia-Morchon, 847 "Quantum-Safe Hybrid (QSH) Key Exchange for Transport 848 Layer Security (TLS) version 1.3", Work in Progress, 849 Internet-Draft, draft-whyte-qsh-tls13-06, 3 October 2017, 850 . 853 [XMSS] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. 854 Mohaisen, "XMSS: eXtended Merkle Signature Scheme", 855 RFC 8391, DOI 10.17487/RFC8391, May 2018, 856 . 858 [ZHANG] Zhang, R., Hanaoka, G., Shikata, J., and H. Imai, "On the 859 Security of Multiple Encryption or CCA-security+CCA- 860 security=CCA-security?", DOI 10.1007/978-3-540-24632-9_26, 861 Public Key Cryptography - PKC 2004 pp. 360-374, 2004, 862 . 864 Appendix A. Related work 866 Quantum computing and post-quantum cryptography in general are 867 outside the scope of this document. For a general introduction to 868 quantum computing, see a standard textbook such as [NIELSEN]. For an 869 overview of post-quantum cryptography as of 2009, see [BERNSTEIN]. 870 For the current status of the NIST Post-Quantum Cryptography 871 Standardization Project, see [NIST]. For additional perspectives on 872 the general transition from classical to post-quantum cryptography, 873 see for example [ETSI] and [HOFFMAN], among others. 875 There have been several Internet-Drafts describing mechanisms for 876 embedding post-quantum and/or hybrid key exchange in TLS: 878 * Internet-Drafts for TLS 1.2: [WHYTE12], [CAMPAGNA] 880 * Internet-Drafts for TLS 1.3: [KIEFER], [SCHANCK], [WHYTE13] 882 There have been several prototype implementations for post-quantum 883 and/or hybrid key exchange in TLS: 885 * Experimental implementations in TLS 1.2: [BCNS15], [CECPQ1], 886 [FRODO], [OQS-102], [S2N] 888 * Experimental implementations in TLS 1.3: [CECPQ2], [OQS-111] 890 These experimental implementations have taken an ad hoc approach and 891 not attempted to implement one of the drafts listed above. 893 Unrelated to post-quantum but still related to the issue of combining 894 multiple types of keying material in TLS is the use of pre-shared 895 keys, especially the recent TLS working group document on including 896 an external pre-shared key [EXTERN-PSK]. 898 Considering other IETF standards, there is work on post-quantum 899 preshared keys in IKEv2 [IKE-PSK] and a framework for hybrid key 900 exchange in IKEv2 [IKE-HYBRID]. The XMSS hash-based signature scheme 901 has been published as an informational RFC by the IRTF [XMSS]. 903 In the academic literature, [EVEN] initiated the study of combining 904 multiple symmetric encryption schemes; [ZHANG], [DODIS], and [HARNIK] 905 examined combining multiple public key encryption schemes, and 907 [HARNIK] coined the term "robust combiner" to refer to a compiler 908 that constructs a hybrid scheme from individual schemes while 909 preserving security properties. [GIACON] and [BINDEL] examined 910 combining multiple key encapsulation mechanisms. 912 Appendix B. Design Considerations 914 This appendix discusses choices one could make along four distinct 915 axes when integrating hybrid key exchange into TLS 1.3: 917 1. How to negotiate the use of hybridization in general and 918 component algorithms specifically? 920 2. How many component algorithms can be combined? 922 3. How should multiple key shares (public keys / ciphertexts) be 923 conveyed? 925 4. How should multiple shared secrets be combined? 927 The construction in the main body illustrates one selection along 928 each of these axes. The remainder of this appendix outlines various 929 options we have identified for each of these choices. Immediately 930 below we provide a summary list. Options are labelled with a short 931 code in parentheses to provide easy cross-referencing. 933 1. (Neg) (Appendix B.1) How to negotiate the use of hybridization in 934 general and component algorithms specifically? 936 * (Neg-Ind) (Appendix B.1.2) Negotiating component algorithms 937 individually 939 - (Neg-Ind-1) (Appendix B.1.2.1) Traditional algorithms in 940 "ClientHello" "supported_groups" extension, next-gen 941 algorithms in another extension 943 - (Neg-Ind-2) (Appendix B.1.2.2) Both types of algorithms in 944 "supported_groups" with external mapping to tradition/next- 945 gen. 947 - (Neg-Ind-3) (Appendix B.1.2.3) Both types of algorithms in 948 "supported_groups" separated by a delimiter. 950 * (Neg-Comb) (Appendix B.1.3) Negotiating component algorithms 951 as a combination 953 - (Neg-Comb-1) (Appendix B.1.3.1) Standardize "NamedGroup" 954 identifiers for each desired combination. 956 - (Neg-Comb-2) (Appendix B.1.3.2) Use placeholder identifiers 957 in "supported_groups" with an extension defining the 958 combination corresponding to each placeholder. 960 - (Neg-Comb-3) (Appendix B.1.3.3) List combinations by 961 inserting grouping delimiters into "supported_groups" list. 963 2. (Num) (Appendix B.2) How many component algorithms can be 964 combined? 966 * (Num-2) (Appendix B.2.1) Two. 968 * (Num-2+) (Appendix B.2.2) Two or more. 970 3. (Shares) (Appendix B.3) How should multiple key shares (public 971 keys / ciphertexts) be conveyed? 973 * (Shares-Concat) (Appendix B.3.1) Concatenate each combination 974 of key shares. 976 * (Shares-Multiple) (Appendix B.3.2) Send individual key shares 977 for each algorithm. 979 * (Shares-Ext-Additional) (Appendix B.3.3) Use an extension to 980 convey key shares for component algorithms. 982 4. (Comb) (Appendix B.4) How should multiple shared secrets be 983 combined? 985 * (Comb-Concat) (Appendix B.4.1) Concatenate the shared secrets 986 then use directly in the TLS 1.3 key schedule. 988 * (Comb-KDF-1) (Appendix B.4.2) and (Comb-KDF-2) 989 (Appendix B.4.3) KDF the shared secrets together, then use the 990 output in the TLS 1.3 key schedule. 992 * (Comb-XOR) (Appendix B.4.4) XOR the shared secrets then use 993 directly in the TLS 1.3 key schedule. 995 * (Comb-Chain) (Appendix B.4.5) Extend the TLS 1.3 key schedule 996 so that there is a stage of the key schedule for each shared 997 secret. 999 * (Comb-AltInput) (Appendix B.4.6) Use the second shared secret 1000 in an alternate (otherwise unused) input in the TLS 1.3 key 1001 schedule. 1003 B.1. (Neg) How to negotiate hybridization and component algorithms? 1005 B.1.1. Key exchange negotiation in TLS 1.3 1007 Recall that in TLS 1.3, the key exchange mechanism is negotiated via 1008 the "supported_groups" extension. The "NamedGroup" enum is a list of 1009 standardized groups for Diffie-Hellman key exchange, such as 1010 "secp256r1", "x25519", and "ffdhe2048". 1012 The client, in its "ClientHello" message, lists its supported 1013 mechanisms in the "supported_groups" extension. The client also 1014 optionally includes the public key of one or more of these groups in 1015 the "key_share" extension as a guess of which mechanisms the server 1016 might accept in hopes of reducing the number of round trips. 1018 If the server is willing to use one of the client's requested 1019 mechanisms, it responds with a "key_share" extension containing its 1020 public key for the desired mechanism. 1022 If the server is not willing to use any of the client's requested 1023 mechanisms, the server responds with a "HelloRetryRequest" message 1024 that includes an extension indicating its preferred mechanism. 1026 B.1.2. (Neg-Ind) Negotiating component algorithms individually 1028 In these three approaches, the parties negotiate which traditional 1029 algorithm and which next-gen algorithm to use independently. The 1030 "NamedGroup" enum is extended to include algorithm identifiers for 1031 each next-gen algorithm. 1033 B.1.2.1. (Neg-Ind-1) 1035 The client advertises two lists to the server: one list containing 1036 its supported traditional mechanisms (e.g. via the existing 1037 "ClientHello" "supported_groups" extension), and a second list 1038 containing its supported next-generation mechanisms (e.g., via an 1039 additional "ClientHello" extension). A server could then select one 1040 algorithm from the traditional list, and one algorithm from the next- 1041 generation list. (This is the approach in [SCHANCK].) 1043 B.1.2.2. (Neg-Ind-2) 1045 The client advertises a single list to the server which contains both 1046 its traditional and next-generation mechanisms (e.g., all in the 1047 existing "ClientHello" "supported_groups" extension), but with some 1048 external table provides a standardized mapping of those mechanisms as 1049 either "traditional" or "next-generation". A server could then 1050 select two algorithms from this list, one from each category. 1052 B.1.2.3. (Neg-Ind-3) 1054 The client advertises a single list to the server delimited into 1055 sublists: one for its traditional mechanisms and one for its next- 1056 generation mechanisms, all in the existing "ClientHello" 1057 "supported_groups" extension, with a special code point serving as a 1058 delimiter between the two lists. For example, "supported_groups = 1059 secp256r1, x25519, delimiter, nextgen1, nextgen4". 1061 B.1.3. (Neg-Comb) Negotiating component algorithms as a combination 1063 In these three approaches, combinations of key exchange mechanisms 1064 appear as a single monolithic block; the parties negotiate which of 1065 several combinations they wish to use. 1067 B.1.3.1. (Neg-Comb-1) 1069 The "NamedGroup" enum is extended to include algorithm identifiers 1070 for each *combination* of algorithms desired by the working group. 1071 There is no "internal structure" to the algorithm identifiers for 1072 each combination, they are simply new code points assigned 1073 arbitrarily. The client includes any desired combinations in its 1074 "ClientHello" "supported_groups" list, and the server picks one of 1075 these. This is the approach in [KIEFER] and [OQS-111]. 1077 B.1.3.2. (Neg-Comb-2) 1079 The "NamedGroup" enum is extended to include algorithm identifiers 1080 for each next-gen algorithm. Some additional field/extension is used 1081 to convey which combinations the parties wish to use. For example, 1082 in [WHYTE13], there are distinguished "NamedGroup" called 1083 "hybrid_marker 0", "hybrid_marker 1", "hybrid_marker 2", etc. This 1084 is complemented by a "HybridExtension" which contains mappings for 1085 each numbered "hybrid_marker" to the set of component key exchange 1086 algorithms (2 or more) for that proposed combination. 1088 B.1.3.3. (Neg-Comb-3) 1090 The client lists combinations in "supported_groups" list, using a 1091 special delimiter to indicate combinations. For example, 1092 "supported_groups = combo_delimiter, secp256r1, nextgen1, 1093 combo_delimiter, secp256r1, nextgen4, standalone_delimiter, 1094 secp256r1, x25519" would indicate that the client's highest 1095 preference is the combination secp256r1+nextgen1, the next highest 1096 preference is the combination secp2561+nextgen4, then the single 1097 algorithm secp256r1, then the single algorithm x25519. A hybrid- 1098 aware server would be able to parse these; a hybrid-unaware server 1099 would see "unknown, secp256r1, unknown, unknown, secp256r1, unknown, 1100 unknown, secp256r1, x25519", which it would be able to process, 1101 although there is the potential that every "projection" of a hybrid 1102 list that is tolerable to a client does not result in list that is 1103 tolerable to the client. 1105 B.1.4. Benefits and drawbacks 1107 *Combinatorial explosion.* (Neg-Comb-1) (Appendix B.1.3.1) requires 1108 new identifiers to be defined for each desired combination. The 1109 other 4 options in this section do not. 1111 *Extensions.* (Neg-Ind-1) (Appendix B.1.2.1) and (Neg-Comb-2) 1112 (Appendix B.1.3.2) require new extensions to be defined. The other 1113 options in this section do not. 1115 *New logic.* All options in this section except (Neg-Comb-1) 1116 (Appendix B.1.3.1) require new logic to process negotiation. 1118 *Matching security levels.* (Neg-Ind-1) (Appendix B.1.2.1), 1119 (Neg-Ind-2) (Appendix B.1.2.2), (Neg-Ind-3) (Appendix B.1.2.3), and 1120 (Neg-Comb-2) (Appendix B.1.3.2) allow algorithms of different claimed 1121 security level from their corresponding lists to be combined. For 1122 example, this could result in combining ECDH secp256r1 (classical 1123 security level 128) with NewHope-1024 (classical security level 256). 1124 Implementations dissatisfied with a mismatched security levels must 1125 either accept this mismatch or attempt to renegotiate. (Neg-Ind-1) 1126 (Appendix B.1.2.1), (Neg-Ind-2) (Appendix B.1.2.2), and (Neg-Ind-3) 1127 (Appendix B.1.2.3) give control over the combination to the server; 1128 (Neg-Comb-2) (Appendix B.1.3.2) gives control over the combination to 1129 the client. (Neg-Comb-1) (Appendix B.1.3.1) only allows standardized 1130 combinations, which could be set by TLS working group to have 1131 matching security (provided security estimates do not evolve 1132 separately). 1134 *Backwards-compability.* TLS 1.3-compliant hybrid-unaware servers 1135 should ignore unreocgnized elements in "supported_groups" (Neg-Ind-2) 1136 (Appendix B.1.2.2), (Neg-Ind-3) (Appendix B.1.2.3), (Neg-Comb-1) 1137 (Appendix B.1.3.1), (Neg-Comb-2) (Appendix B.1.3.2) and unrecognized 1138 "ClientHello" extensions (Neg-Ind-1) (Appendix B.1.2.1), (Neg-Comb-2) 1139 (Appendix B.1.3.2). In (Neg-Ind-3) (Appendix B.1.2.3) and 1140 (Neg-Comb-3) (Appendix B.1.3.3), a server that is hybrid-unaware will 1141 ignore the delimiters in "supported_groups", and thus might try to 1142 negotiate an algorithm individually that is only meant to be used in 1143 combination; depending on how such an implementation is coded, it may 1144 also encounter bugs when the same element appears multiple times in 1145 the list. 1147 B.2. (Num) How many component algorithms to combine? 1149 B.2.1. (Num-2) Two 1151 Exactly two algorithms can be combined together in hybrid key 1152 exchange. This is the approach taken in [KIEFER] and [SCHANCK]. 1154 B.2.2. (Num-2+) Two or more 1156 Two or more algorithms can be combined together in hybrid key 1157 exchange. This is the approach taken in [WHYTE13]. 1159 B.2.3. Benefits and Drawbacks 1161 Restricting the number of component algorithms that can be hybridized 1162 to two substantially reduces the generality required. On the other 1163 hand, some adopters may want to further reduce risk by employing 1164 multiple next-gen algorithms built on different cryptographic 1165 assumptions. 1167 B.3. (Shares) How to convey key shares? 1169 In ECDH ephmeral key exchange, the client sends its ephmeral public 1170 key in the "key_share" extension of the "ClientHello" message, and 1171 the server sends its ephmeral public key in the "key_share" extension 1172 of the "ServerHello" message. 1174 For a general key encapsulation mechanism used for ephemeral key 1175 exchange, we imagine that that client generates a fresh KEM public 1176 key / secret pair for each connection, sends it to the client, and 1177 the server responds with a KEM ciphertext. For simplicity and 1178 consistency with TLS 1.3 terminology, we will refer to both of these 1179 types of objects as "key shares". 1181 In hybrid key exchange, we have to decide how to convey the client's 1182 two (or more) key shares, and the server's two (or more) key shares. 1184 B.3.1. (Shares-Concat) Concatenate key shares 1186 The client concatenates the bytes representing its two key shares and 1187 uses this directly as the "key_exchange" value in a "KeyShareEntry" 1188 in its "key_share" extension. The server does the same thing. Note 1189 that the "key_exchange" value can be an octet string of length at 1190 most 2^16-1. This is the approach taken in [KIEFER], [OQS-111], and 1191 [WHYTE13]. 1193 B.3.2. (Shares-Multiple) Send multiple key shares 1195 The client sends multiple key shares directly in the "client_shares" 1196 vectors of the "ClientHello" "key_share" extension. The server does 1197 the same. (Note that while the existing "KeyShareClientHello" struct 1198 allows for multiple key share entries, the existing 1199 "KeyShareServerHello" only permits a single key share entry, so some 1200 modification would be required to use this approach for the server to 1201 send multiple key shares.) 1203 B.3.3. (Shares-Ext-Additional) Extension carrying additional key shares 1205 The client sends the key share for its traditional algorithm in the 1206 original "key_share" extension of the "ClientHello" message, and the 1207 key share for its next-gen algorithm in some additional extension in 1208 the "ClientHello" message. The server does the same thing. This is 1209 the approach taken in [SCHANCK]. 1211 B.3.4. Benefits and Drawbacks 1213 *Backwards compatibility.* (Shares-Multiple) (Appendix B.3.2) is 1214 fully backwards compatible with non-hybrid-aware servers. 1215 (Shares-Ext-Additional) (Appendix B.3.3) is backwards compatible with 1216 non-hybrid-aware servers provided they ignore unrecognized 1217 extensions. (Shares-Concat) (Appendix B.3.1) is backwards-compatible 1218 with non-hybrid aware servers, but may result in duplication / 1219 additional round trips (see below). 1221 *Duplication versus additional round trips.* If a client wants to 1222 offer multiple key shares for multiple combinations in order to avoid 1223 retry requests, then the client may ended up sending a key share for 1224 one algorithm multiple times when using (Shares-Ext-Additional) 1225 (Appendix B.3.3) and (Shares-Concat) (Appendix B.3.1). (For example, 1226 if the client wants to send an ECDH-secp256r1 + McEliece123 key 1227 share, and an ECDH-secp256r1 + NewHope1024 key share, then the same 1228 ECDH public key may be sent twice. If the client also wants to offer 1229 a traditional ECDH-only key share for non-hybrid-aware 1230 implementations and avoid retry requests, then that same ECDH public 1231 key may be sent another time.) (Shares-Multiple) (Appendix B.3.2) 1232 does not result in duplicate key shares. 1234 B.4. (Comb) How to use keys? 1236 Each component key exchange algorithm establishes a shared secret. 1237 These shared secrets must be combined in some way that achieves the 1238 "hybrid" property: the resulting secret is secure as long as at least 1239 one of the component key exchange algorithms is unbroken. 1241 B.4.1. (Comb-Concat) Concatenate keys 1243 Each party concatenates the shared secrets established by each 1244 component algorithm in an agreed-upon order, then feeds that through 1245 the TLS key schedule. In the context of TLS 1.3, this would mean 1246 using the concatenated shared secret in place of the (EC)DHE input to 1247 the second call to "HKDF-Extract" in the TLS 1.3 key schedule: 1249 0 1250 | 1251 v 1252 PSK -> HKDF-Extract = Early Secret 1253 | 1254 +-----> Derive-Secret(...) 1255 +-----> Derive-Secret(...) 1256 +-----> Derive-Secret(...) 1257 | 1258 v 1259 Derive-Secret(., "derived", "") 1260 | 1261 v 1262 concatenated_shared_secret -> HKDF-Extract = Handshake Secret 1263 ^^^^^^^^^^^^^^^^^^^^^^^^^^ | 1264 +-----> Derive-Secret(...) 1265 +-----> Derive-Secret(...) 1266 | 1267 v 1268 Derive-Secret(., "derived", "") 1269 | 1270 v 1271 0 -> HKDF-Extract = Master Secret 1272 | 1273 +-----> Derive-Secret(...) 1274 +-----> Derive-Secret(...) 1275 +-----> Derive-Secret(...) 1276 +-----> Derive-Secret(...) 1278 This is the approach used in [KIEFER], [OQS-111], and [WHYTE13]. 1280 [GIACON] analyzes the security of applying a KDF to concatenated KEM 1281 shared secrets, but their analysis does not exactly apply here since 1282 the transcript of ciphertexts is included in the KDF application 1283 (though it should follow relatively straightforwardly). 1285 [BINDEL] analyzes the security of the (Comb-Concat) approach as 1286 abstracted in their "dualPRF" combiner. They show that, if the 1287 component KEMs are IND-CPA-secure (or IND-CCA-secure), then the 1288 values output by "Derive-Secret" are IND-CPA-secure (respectively, 1289 IND-CCA-secure). An important aspect of their analysis is that each 1290 ciphertext is input to the final PRF calls; this holds for TLS 1.3 1291 since the "Derive-Secret" calls that derive output keys (application 1292 traffic secrets, and exporter and resumption master secrets) include 1293 the transcript hash as input. 1295 B.4.2. (Comb-KDF-1) KDF keys 1297 Each party feeds the shared secrets established by each component 1298 algorithm in an agreed-upon order into a KDF, then feeds that through 1299 the TLS key schedule. In the context of TLS 1.3, this would mean 1300 first applying "HKDF-Extract" to the shared secrets, then using the 1301 output in place of the (EC)DHE input to the second call to "HKDF- 1302 Extract" in the TLS 1.3 key schedule: 1304 0 1305 | 1306 v 1307 PSK -> HKDF-Extract = Early Secret 1308 | 1309 +-----> Derive-Secret(...) 1310 +-----> Derive-Secret(...) 1311 +-----> Derive-Secret(...) 1312 Next-Gen | 1313 | v 1314 (EC)DHE -> HKDF-Extract Derive-Secret(., "derived", "") 1315 | | 1316 v v 1317 output -----> HKDF-Extract = Handshake Secret 1318 ^^^^^^ | 1319 +-----> Derive-Secret(...) 1320 +-----> Derive-Secret(...) 1321 | 1322 v 1323 Derive-Secret(., "derived", "") 1324 | 1325 v 1326 0 -> HKDF-Extract = Master Secret 1327 | 1328 +-----> Derive-Secret(...) 1329 +-----> Derive-Secret(...) 1330 +-----> Derive-Secret(...) 1331 +-----> Derive-Secret(...) 1333 B.4.3. (Comb-KDF-2) KDF keys 1335 Each party concatenates the shared secrets established by each 1336 component algorithm in an agreed-upon order then feeds that into a 1337 KDF, then feeds the result through the TLS key schedule. 1339 Compared with (Comb-KDF-1) (Appendix B.4.2), this method concatenates 1340 the (2 or more) shared secrets prior to input to the KDF, whereas 1341 (Comb-KDF-1) puts the (exactly 2) shared secrets in the two different 1342 input slots to the KDF. 1344 Compared with (Comb-Concat) (Appendix B.4.1), this method has an 1345 extract KDF application. While this adds computational overhead, 1346 this may provide a cleaner abstraction of the hybridization mechanism 1347 for the purposes of formal security analysis. 1349 0 1350 | 1351 v 1352 PSK -> HKDF-Extract = Early Secret 1353 | 1354 +-----> Derive-Secret(...) 1355 +-----> Derive-Secret(...) 1356 +-----> Derive-Secret(...) 1357 | 1358 v 1359 concatenated 0 1360 shared | 1361 secret -> HKDF-Extract Derive-Secret(., "derived", "") 1362 ^^^^^^ | | 1363 v v 1364 output -----> HKDF-Extract = Handshake Secret 1365 ^^^^^^ | 1366 +-----> Derive-Secret(...) 1367 +-----> Derive-Secret(...) 1368 | 1369 v 1370 Derive-Secret(., "derived", "") 1371 | 1372 v 1373 0 -> HKDF-Extract = Master Secret 1374 | 1375 +-----> Derive-Secret(...) 1376 +-----> Derive-Secret(...) 1377 +-----> Derive-Secret(...) 1378 +-----> Derive-Secret(...) 1380 B.4.4. (Comb-XOR) XOR keys 1382 Each party XORs the shared secrets established by each component 1383 algorithm (possibly after padding secrets of different lengths), then 1384 feeds that through the TLS key schedule. In the context of TLS 1.3, 1385 this would mean using the XORed shared secret in place of the (EC)DHE 1386 input to the second call to "HKDF-Extract" in the TLS 1.3 key 1387 schedule. 1389 [GIACON] analyzes the security of applying a KDF to the XORed KEM 1390 shared secrets, but their analysis does not quite apply here since 1391 the transcript of ciphertexts is included in the KDF application 1392 (though it should follow relatively straightforwardly). 1394 B.4.5. (Comb-Chain) Chain of KDF applications for each key 1396 Each party applies a chain of key derivation functions to the shared 1397 secrets established by each component algorithm in an agreed-upon 1398 order; roughly speaking: "F(k1 || F(k2))". In the context of TLS 1399 1.3, this would mean extending the key schedule to have one round of 1400 the key schedule applied for each component algorithm's shared 1401 secret: 1403 0 1404 | 1405 v 1406 PSK -> HKDF-Extract = Early Secret 1407 | 1408 +-----> Derive-Secret(...) 1409 +-----> Derive-Secret(...) 1410 +-----> Derive-Secret(...) 1411 | 1412 v 1413 Derive-Secret(., "derived", "") 1414 | 1415 v 1416 traditional_shared_secret -> HKDF-Extract 1417 ^^^^^^^^^^^^^^^^^^^^^^^^^ | 1418 Derive-Secret(., "derived", "") 1419 | 1420 v 1421 next_gen_shared_secret -> HKDF-Extract = Handshake Secret 1422 ^^^^^^^^^^^^^^^^^^^^^^ | 1423 +-----> Derive-Secret(...) 1424 +-----> Derive-Secret(...) 1425 | 1426 v 1427 Derive-Secret(., "derived", "") 1428 | 1429 v 1430 0 -> HKDF-Extract = Master Secret 1431 | 1432 +-----> Derive-Secret(...) 1433 +-----> Derive-Secret(...) 1434 +-----> Derive-Secret(...) 1435 +-----> Derive-Secret(...) 1437 This is the approach used in [SCHANCK]. 1439 [BINDEL] analyzes the security of this approach as abstracted in 1440 their nested dual-PRF "N" combiner, showing a similar result as for 1441 the dualPRF combiner that it preserves IND-CPA (or IND-CCA) security. 1442 Again their analysis depends on each ciphertext being input to the 1443 final PRF ("Derive-Secret") calls, which holds for TLS 1.3. 1445 B.4.6. (Comb-AltInput) Second shared secret in an alternate KDF input 1447 In the context of TLS 1.3, the next-generation shared secret is used 1448 in place of a currently unused input in the TLS 1.3 key schedule, 1449 namely replacing the "0" "IKM" input to the final "HKDF-Extract": 1451 0 1452 | 1453 v 1454 PSK -> HKDF-Extract = Early Secret 1455 | 1456 +-----> Derive-Secret(...) 1457 +-----> Derive-Secret(...) 1458 +-----> Derive-Secret(...) 1459 | 1460 v 1461 Derive-Secret(., "derived", "") 1462 | 1463 v 1464 traditional_shared_secret -> HKDF-Extract = Handshake Secret 1465 ^^^^^^^^^^^^^^^^^^^^^^^^^ | 1466 +-----> Derive-Secret(...) 1467 +-----> Derive-Secret(...) 1468 | 1469 v 1470 Derive-Secret(., "derived", "") 1471 | 1472 v 1473 next_gen_shared_secret -> HKDF-Extract = Master Secret 1474 ^^^^^^^^^^^^^^^^^^^^^^ | 1475 +-----> Derive-Secret(...) 1476 +-----> Derive-Secret(...) 1477 +-----> Derive-Secret(...) 1478 +-----> Derive-Secret(...) 1480 This approach is not taken in any of the known post-quantum/hybrid 1481 TLS drafts. However, it bears some similarities to the approach for 1482 using external PSKs in [EXTERN-PSK]. 1484 B.4.7. Benefits and Drawbacks 1486 *New logic.* While (Comb-Concat) (Appendix B.4.1), (Comb-KDF-1) 1487 (Appendix B.4.2), and (Comb-KDF-2) (Appendix B.4.3) require new logic 1488 to compute the concatenated shared secret, this value can then be 1489 used by the TLS 1.3 key schedule without changes to the key schedule 1490 logic. In contrast, (Comb-Chain) (Appendix B.4.5) requires the TLS 1491 1.3 key schedule to be extended for each extra component algorithm. 1493 *Philosophical.* The TLS 1.3 key schedule already applies a new stage 1494 for different types of keying material (PSK versus (EC)DHE), so 1495 (Comb-Chain) (Appendix B.4.5) continues that approach. 1497 *Efficiency.* (Comb-KDF-1) (Appendix B.4.2), (Comb-KDF-2) 1498 (Appendix B.4.3), and (Comb-Chain) (Appendix B.4.5) increase the 1499 number of KDF applications for each component algorithm, whereas 1500 (Comb-Concat) (Appendix B.4.1) and (Comb-AltInput) (Appendix B.4.6) 1501 keep the number of KDF applications the same (though with potentially 1502 longer inputs). 1504 *Extensibility.* (Comb-AltInput) (Appendix B.4.6) changes the use of 1505 an existing input, which might conflict with other future changes to 1506 the use of the input. 1508 *More than 2 component algorithms.* The techniques in (Comb-Concat) 1509 (Appendix B.4.1) and (Comb-Chain) (Appendix B.4.5) can naturally 1510 accommodate more than 2 component shared secrets since there is no 1511 distinction to how each shared secret is treated. (Comb-AltInput) 1512 (Appendix B.4.6) would have to make some distinct, since the 2 1513 component shared secrets are used in different ways; for example, the 1514 first shared secret is used as the "IKM" input in the 2nd "HKDF- 1515 Extract" call, and all subsequent shared secrets are concatenated to 1516 be used as the "IKM" input in the 3rd "HKDF-Extract" call. 1518 Authors' Addresses 1520 Douglas Stebila 1521 University of Waterloo 1523 Email: dstebila@uwaterloo.ca 1525 Scott Fluhrer 1526 Cisco Systems 1528 Email: sfluhrer@cisco.com 1530 Shay Gueron 1531 University of Haifa and Amazon Web Services 1533 Email: shay.gueron@gmail.com