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