idnits 2.17.1 draft-stebila-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: ---------------------------------------------------------------------------- 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 (March 11, 2019) is 1845 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-07) exists of draft-ietf-tls-tls13-cert-with-extern-psk-00 == Outdated reference: A later version (-07) exists of draft-hoffman-c2pq-04 == Outdated reference: A later version (-04) exists of draft-tjhai-ipsecme-hybrid-qske-ikev2-03 == Outdated reference: A later version (-11) exists of draft-ietf-ipsecme-qr-ikev2-07 Summary: 0 errors (**), 0 flaws (~~), 5 warnings (==), 1 comment (--). 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. Gueron 5 Expires: September 12, 2019 U. Haifa, Amazon Web Services 6 March 11, 2019 8 Design issues for hybrid key exchange in TLS 1.3 9 draft-stebila-tls-hybrid-design-00 11 Abstract 13 Hybrid key exchange refers to using multiple key exchange algorithms 14 simultaneously and combining the result with the goal of providing 15 security even if all but one of the component algorithms is broken, 16 and is motivated by transition to post-quantum cryptography. This 17 document categorizes various design considerations for using hybrid 18 key exchange in the Transport Layer Security (TLS) protocol version 19 1.3. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at https://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on September 12, 2019. 38 Copyright Notice 40 Copyright (c) 2019 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents 45 (https://trustee.ietf.org/license-info) in effect on the date of 46 publication of this document. Please review these documents 47 carefully, as they describe your rights and restrictions with respect 48 to this document. Code Components extracted from this document must 49 include Simplified BSD License text as described in Section 4.e of 50 the Trust Legal Provisions and are provided without warranty as 51 described in the Simplified BSD License. 53 Table of Contents 55 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 56 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3 57 1.2. Motivation for use of hybrid key exchange . . . . . . . . 4 58 1.3. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . 4 59 1.4. Goals . . . . . . . . . . . . . . . . . . . . . . . . . . 5 60 1.5. Related work . . . . . . . . . . . . . . . . . . . . . . 6 61 2. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 7 62 3. Design options . . . . . . . . . . . . . . . . . . . . . . . 9 63 3.1. (Neg) How to negotiate hybridization and component 64 algorithms? . . . . . . . . . . . . . . . . . . . . . . . 9 65 3.1.1. Key exchange negotiation in TLS 1.3 . . . . . . . . . 9 66 3.1.2. (Neg-Ind) Negotiating component algorithms 67 individually . . . . . . . . . . . . . . . . . . . . 9 68 3.1.3. (Neg-Comb) Negotiating component algorithms as a 69 combination . . . . . . . . . . . . . . . . . . . . . 10 70 3.1.4. Benefits and drawbacks . . . . . . . . . . . . . . . 11 71 3.2. (Num) How many component algorithms to combine? . . . . . 12 72 3.2.1. (Num-2) Two . . . . . . . . . . . . . . . . . . . . . 12 73 3.2.2. (Num-2+) Two or more . . . . . . . . . . . . . . . . 12 74 3.2.3. Benefits and Drawbacks . . . . . . . . . . . . . . . 12 75 3.3. (Shares) How to convey key shares? . . . . . . . . . . . 12 76 3.3.1. (Shares-Concat) Concatenate key shares . . . . . . . 13 77 3.3.2. (Shares-Multiple) Send multiple key shares . . . . . 13 78 3.3.3. (Shares-Ext-Additional) Extension carrying additional 79 key shares . . . . . . . . . . . . . . . . . . . . . 13 80 3.3.4. Benefits and Drawbacks . . . . . . . . . . . . . . . 13 81 3.4. (Comb) How to use keys? . . . . . . . . . . . . . . . . . 14 82 3.4.1. (Comb-Concat) Concatenate keys then KDF . . . . . . . 14 83 3.4.2. (Comb-XOR) XOR keys then KDF . . . . . . . . . . . . 15 84 3.4.3. (Comb-Chain) Chain of KDF applications for each key . 15 85 3.4.4. (Comb-AltInput) Second shared secret in an alternate 86 KDF input . . . . . . . . . . . . . . . . . . . . . . 16 87 3.4.5. Benefits and Drawbacks . . . . . . . . . . . . . . . 17 88 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 89 5. Security Considerations . . . . . . . . . . . . . . . . . . . 18 90 5.1. Active security . . . . . . . . . . . . . . . . . . . . . 18 91 5.2. Resumption . . . . . . . . . . . . . . . . . . . . . . . 19 92 5.3. Failures . . . . . . . . . . . . . . . . . . . . . . . . 19 93 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 19 94 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 19 95 7.1. Normative References . . . . . . . . . . . . . . . . . . 19 96 7.2. Informative References . . . . . . . . . . . . . . . . . 19 98 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 22 100 1. Introduction 102 This document categorizes various design decisions one could make 103 when implementing hybrid key exchange in TLS 1.3, with the goal of 104 fostering discussion, providing options for short-term prototypes/ 105 experiments, and serving as a basis for eventual standardization. 106 This document does not propose specific post-quantum mechanisms; see 107 Section 1.3 for more on the scope of this document. 109 Comments are solicited and should be addressed to the TLS working 110 group mailing list at tls@ietf.org and/or the author(s). 112 1.1. Terminology 114 For the purposes of this document, it is helpful to be able to divide 115 cryptographic algorithms into two classes: 117 o "Traditional" algorithms: Algorithms which are widely deployed 118 today, but which may be deprecated in the future. In the context 119 of TLS 1.3 in 2019, examples of traditional key exchange 120 algorithms include elliptic curve Diffie-Hellman using secp256r1 121 or x25519, or finite-field Diffie-Hellman. 123 o "Next-generation" (or "next-gen") algorithms: Algorithms which are 124 not yet widely deployed, but which may eventually be widely 125 deployed. An additional facet of these algorithms may be that we 126 have less confidence in their security due to them being 127 relatively new or less studied. This includes "post-quantum" 128 algorithms. 130 "Hybrid" key exchange, in this context, means the use of two (or 131 more) key exchange mechanisms based on different cryptographic 132 assumptions (for example, one traditional algorithm and one next-gen 133 algorithm), with the purpose of the final session key being secure as 134 long as at least one of the component key exchange mechanisms remains 135 unbroken. We use the term "component" algorithms to refer to the 136 algorithms that are being combined in a hybrid key exchange. 138 The primary motivation of this document is preparing for post-quantum 139 algorithms. However, it is possible that public key cryptography 140 based on alternative mathematical constructions will be required 141 independent of the advent of a quantum computer, for example because 142 of a cryptanalytic breakthrough. As such we opt for the more generic 143 term "next-generation" algorithms rather than exclusively "post- 144 quantum" algorithms. 146 1.2. Motivation for use of hybrid key exchange 148 Ideally, one would not use hybrid key exchange: one would have 149 confidence in a single algorithm and parameterization that will stand 150 the test of time. However, this may not be the case in the face of 151 quantum computers and cryptanalytic advances more generally. 153 Many (but not all) of the post-quantum algorithms currently under 154 consideration are relatively new; they have not been subject to the 155 same depth of study as RSA and finite-field / elliptic curve Diffie- 156 Hellman, and thus we do not necessarily have as much confidence in 157 their fundamental security, or the concrete security level of 158 specific parameterizations. 160 Early adopters eager for post-quantum security may want to use hybrid 161 key exchange to have the potential of post-quantum security from a 162 less-well-studied algorithm while still retaining at least the 163 security currently offered by traditional algorithms. (They may even 164 need to retain traditional algorithms due to regulatory constraints, 165 for example FIPS compliance.) 167 Moreover, it is possible that even by the end of the NIST Post- 168 Quantum Cryptography Standardization Project, and for a period of 169 time thereafter, conservative users may not have full confidence in 170 some algorithms. 172 As such, there may be users for whom hybrid key exchange is an 173 appropriate step prior to an eventual transition to next-generation 174 algorithms. 176 1.3. Scope 178 This document focuses on hybrid ephemeral key exchange in TLS 1.3 179 [TLS13]. It intentionally does not address: 181 o Selecting which next-generation algorithms to use in TLS 1.3, nor 182 algorithm identifiers nor encoding mechanisms for next-generation 183 algorithms. (The outcomes of the NIST Post-Quantum Cryptography 184 Standardization Project [NIST] will inform this choice.) 186 o Authentication using next-generation algorithms. (If a 187 cryptographic assumption is broken due to the advent of a quantum 188 computer or some other cryptanalytic breakthrough, confidentiality 189 of information can be broken retroactively by any adversary who 190 has passively recorded handshakes and encrypted communications. 191 But session authentication cannot be retroactively broken.) 193 1.4. Goals 195 The primary goal of a hybrid key exchange mechanism is to facilitate 196 the establishment of a shared secret which remains secure as long as 197 as one of the component key exchange mechanisms remains unbroken. 199 In addition to the primary cryptographic goal, there may be several 200 additional goals in the context of TLS 1.3: 202 o *Backwards compatibility:* Clients and servers who are "hybrid- 203 aware", i.e., compliant with whatever hybrid key exchange standard 204 is developed for TLS, should remain compatible with endpoints and 205 middle-boxes that are not hybrid-aware. The three scenarios to 206 consider are: 208 1. Hybrid-aware client, hybrid-aware server: These parties should 209 establish a hybrid shared secret. 211 2. Hybrid-aware client, non-hybrid-aware server: These parties 212 should establish a traditional shared secret (assuming the 213 hybrid-aware client is willing to downgrade to traditional- 214 only). 216 3. Non-hybrid-aware client, hybrid-aware server: These parties 217 should establish a traditional shared secret (assuming the 218 hybrid-aware server is willing to downgrade to traditional- 219 only). 221 Ideally backwards compatibility should be achieved without extra 222 round trips and without sending duplicate information; see below. 224 o *High performance:* Use of hybrid key exchange should not be 225 prohibitively expensive in terms of computational performance. In 226 general this will depend on the performance characteristics of the 227 specific cryptographic algorithms used, and as such is outside the 228 scope of this document. See [BCNS15], [CECPQ1], [FRODO] for 229 preliminary results about performance characteristics. 231 o *Low latency:* Use of hybrid key exchange should not substantially 232 increase the latency experienced to establish a connection. 233 Factors affecting this may include the following. 235 * The computational performance characteristics of the specific 236 algorithms used. See above. 238 * The size of messages to be transmitted. Public key / 239 ciphertext sizes for post-quantum algorithms range from 240 hundreds of bytes to over one hundred kilobytes, so this impact 241 can be substantially. See [BCNS15], [FRODO] for preliminary 242 results in a laboratory setting, and [LANGLEY] for preliminary 243 results on more realistic networks. 245 * Additional round trips added to the protocol. See below. 247 o *No extra round trips:* Attempting to negotiate hybrid key 248 exchange should not lead to extra round trips in any of the three 249 hybrid-aware/non-hybrid-aware scenarios listed above. 251 o *No duplicate information:* Attempting to negotiate hybrid key 252 exchange should not mean having to send multiple public keys of 253 the same type. 255 1.5. Related work 257 Quantum computing and post-quantum cryptography in general are 258 outside the scope of this document. For a general introduction to 259 quantum computing, see a standard textbook such as [NIELSEN]. For an 260 overview of post-quantum cryptography as of 2009, see [BERNSTEIN]. 261 For the current status of the NIST Post-Quantum Cryptography 262 Standardization Project, see [NIST]. For additional perspectives on 263 the general transition from classical to post-quantum cryptography, 264 see for example [ETSI] and [HOFFMAN], among others. 266 There have been several Internet-Drafts describing mechanisms for 267 embedding post-quantum and/or hybrid key exchange in TLS: 269 o Internet-Drafts for TLS 1.2: [WHYTE12] 271 o Internet-Drafts for TLS 1.3: [KIEFER], [SCHANCK], [WHYTE13] 273 There have been several prototype implementations for post-quantum 274 and/or hybrid key exchange in TLS: 276 o Experimental implementations in TLS 1.2: [BCNS15], [CECPQ1], 277 [FRODO], [OQS-102] 279 o Experimental implementations in TLS 1.3: [CECPQ2], [OQS-111] 281 These experimental implementations have taken an ad hoc approach and 282 not attempted to implement one of the drafts listed above. 284 Unrelated to post-quantum but still related to the issue of combining 285 multiple types of keying material in TLS is the use of pre-shared 286 keys, especially the recent TLS working group document on including 287 an external pre-shared key [EXTERN-PSK]. 289 Considering other IETF standards, there is work on post-quantum 290 preshared keys in IKEv2 [IKE-PSK] and a framework for hybrid key 291 exchange in IKEv2 [IKE-HYBRID]. The XMSS hash-based signature scheme 292 has been published as an informational RFC by the IRTF [XMSS]. 294 In the academic literature, [EVEN] initiated the study of combining 295 multiple symmetric encryption schemes; [ZHANG], [DODIS], and [HARNIK] 296 examined combining multiple public key encryption schemes, and 297 [HARNIK] coined the term "robust combiner" to refer to a compiler 298 that constructs a hybrid scheme from individual schemes while 299 preserving security properties. [GIACON] and [BINDEL] examined 300 combining multiple key encapsulation mechanisms. 302 2. Overview 304 We identify four distinct axes along which one can make choices when 305 integrating hybrid key exchange into TLS 1.3: 307 1. How to negotiate the use of hybridization in general and 308 component algorithms specifically? 310 2. How many component algorithms can be combined? 312 3. How should multiple key shares (public keys / ciphertexts) be 313 conveyed? 315 4. How should multiple shared secrets be combined? 317 The remainder of this document outlines various options we have 318 identified for each of these choices. Immediately below we provide a 319 summary list. Options are labelled with a short code in parentheses 320 to provide easy cross-referencing. 322 1. (Neg) (Section 3.1) How to negotiate the use of hybridization in 323 general and component algorithms specifically? 325 * (Neg-Ind) (Section 3.1.2) Negotiating component algorithms 326 individually 328 + (Neg-Ind-1) (Section 3.1.2.1) Traditional algorithms in 329 "ClientHello" "supported_groups" extension, next-gen 330 algorithms in another extension 332 + (Neg-Ind-2) (Section 3.1.2.2) Both types of algorithms in 333 "supported_groups" with external mapping to tradition/next- 334 gen. 336 + (Neg-Ind-3) (Section 3.1.2.3) Both types of algorithms in 337 "supported_groups" separated by a delimiter. 339 * (Neg-Comb) (Section 3.1.3) Negotiating component algorithms as 340 a combination 342 + (Neg-Comb-1) (Section 3.1.3.1) Standardize "NamedGroup" 343 identifiers for each desired combination. 345 + (Neg-Comb-2) (Section 3.1.3.2) Use placeholder identifiers 346 in "supported_groups" with an extension defining the 347 combination corresponding to each placeholder. 349 + (Neg-Comb-3) (Section 3.1.3.3) List combinations by 350 inserting grouping delimiters into "supported_groups" list. 352 2. (Num) (Section 3.2) How many component algorithms can be 353 combined? 355 * (Num-2) (Section 3.2.1) Two. 357 * (Num-2+) (Section 3.2.2) Two or more. 359 3. (Shares) (Section 3.3) How should multiple key shares (public 360 keys / ciphertexts) be conveyed? 362 * (Shares-Concat) (Section 3.3.1) Concatenate each combination 363 of key shares. 365 * (Shares-Multiple) (Section 3.3.2) Send individual key shares 366 for each algorithm. 368 * (Shares-Ext-Additional) (Section 3.3.3) Use an extension to 369 convey key shares for component algorithms. 371 4. (Comb) (Section 3.4) How should multiple shared secrets be 372 combined? 374 * (Comb-Concat) (Section 3.4.1) Concatenate the shared secrets 375 then use directly in the TLS 1.3 key schedule. 377 * (Comb-XOR) (Section 3.4.2) XOR the shared secrets then use 378 directly in the TLS 1.3 key schedule. 380 * (Comb-Chain) (Section 3.4.3) Extend the TLS 1.3 key schedule 381 so that there is a stage of the key schedule for each shared 382 secret. 384 * (Comb-AltInput) (Section 3.4.4) Use the second shared secret 385 in an alternate (otherwise unused) input in the TLS 1.3 key 386 schedule. 388 3. Design options 390 3.1. (Neg) How to negotiate hybridization and component algorithms? 392 3.1.1. Key exchange negotiation in TLS 1.3 394 Recall that in TLS 1.3, the key exchange mechanism is negotiated via 395 the "supported_groups" extension. The "NamedGroup" enum is a list of 396 standardized groups for Diffie-Hellman key exchange, such as 397 "secp256r1", "x25519", and "ffdhe2048". 399 The client, in its "ClientHello" message, lists its supported 400 mechanisms in the "supported_groups" extension. The client also 401 optionally includes the public key of one or more of these groups in 402 the "key_share" extension as a guess of which mechanisms the server 403 might accept in hopes of reducing the number of round trips. 405 If the server is willing to use one of the client's requested 406 mechanisms, it responds with a "key_share" extension containing its 407 public key for the desired mechanism. 409 If the server is not willing to use any of the client's requested 410 mechanisms, the server responds with a "HelloRetryRequest" message 411 that includes an extension indicating its preferred mechanism. 413 3.1.2. (Neg-Ind) Negotiating component algorithms individually 415 In these three approaches, the parties negotiate which traditional 416 algorithm and which next-gen algorithm to use independently. The 417 "NamedGroup" enum is extended to include algorithm identifiers for 418 each next-gen algorithm. 420 3.1.2.1. (Neg-Ind-1) 422 The client advertises two lists to the server: one list containing 423 its supported traditional mechanisms (e.g. via the existing 424 "ClientHello" "supported_groups" extension), and a second list 425 containing its supported next-generation mechanisms (e.g., via an 426 additional "ClientHello" extension). A server could then select one 427 algorithm from the traditional list, and one algorithm from the next- 428 generation list. (This is the approach in [SCHANCK].) 430 3.1.2.2. (Neg-Ind-2) 432 The client advertises a single list to the server which contains both 433 its traditional and next-generation mechanisms (e.g., all in the 434 existing "ClientHello" "supported_groups" extension), but with some 435 external table provides a standardized mapping of those mechanisms as 436 either "traditional" or "next-generation". A server could then 437 select two algorithms from this list, one from each category. 439 3.1.2.3. (Neg-Ind-3) 441 The client advertises a single list to the server delimited into 442 sublists: one for its traditional mechanisms and one for its next- 443 generation mechanisms, all in the existing "ClientHello" 444 "supported_groups" extension, with a special code point serving as a 445 delimiter between the two lists. For example, "supported_groups = 446 secp256r1, x25519, delimiter, nextgen1, nextgen4". 448 3.1.3. (Neg-Comb) Negotiating component algorithms as a combination 450 In these three approaches, combinations of key exchange mechanisms 451 appear as a single monolithic block; the parties negotiate which of 452 several combinations they wish to use. 454 3.1.3.1. (Neg-Comb-1) 456 The "NamedGroup" enum is extended to include algorithm identifiers 457 for each *combination* of algorithms desired by the working group. 458 There is no "internal structure" to the algorithm identifiers for 459 each combination, they are simply new code points assigned 460 arbitrarily. The client includes any desired combinations in its 461 "ClientHello" "supported_groups" list, and the server picks one of 462 these. This is the approach in [KIEFER] and [OQS-111]. 464 3.1.3.2. (Neg-Comb-2) 466 The "NamedGroup" enum is extended to include algorithm identifiers 467 for each next-gen algorithm. Some additional field/extension is used 468 to convey which combinations the parties wish to use. For example, 469 in [WHYTE13], there are distinguished "NamedGroup" called 470 "hybrid_marker 0", "hybrid_marker 1", "hybrid_marker 2", etc. This 471 is complemented by a "HybridExtension" which contains mappings for 472 each numbered "hybrid_marker" to the set of component key exchange 473 algorithms (2 or more) for that proposed combination. 475 3.1.3.3. (Neg-Comb-3) 477 The client lists combinations in "supported_groups" list, using a 478 special delimiter to indicate combinations. For example, 479 "supported_groups = combo_delimiter, secp256r1, nextgen1, 480 combo_delimiter, secp256r1, nextgen4, standalone_delimiter, 481 secp256r1, x25519" would indicate that the client's highest 482 preference is the combination secp256r1+nextgen1, the next highest 483 preference is the combination secp2561+nextgen4, then the single 484 algorithm secp256r1, then the single algorithm x25519. A hybrid- 485 aware server would be able to parse these; a hybrid-unaware server 486 would see "unknown, secp256r1, unknown, unknown, secp256r1, unknown, 487 unknown, secp256r1, x25519", which it would be able to process, 488 although there is the potential that every "projection" of a hybrid 489 list that is tolerable to a client does not result in list that is 490 tolerable to the client. 492 3.1.4. Benefits and drawbacks 494 *Combinatorial explosion.* (Neg-Comb-1) (Section 3.1.3.1) requires 495 new identifiers to be defined for each desired combination. The 496 other 4 options in this section do not. 498 *Extensions.* (Neg-Ind-1) (Section 3.1.2.1) and (Neg-Comb-2) 499 (Section 3.1.3.2) require new extensions to be defined. The other 500 options in this section do not. 502 *New logic.* All options in this section except (Neg-Comb-1) 503 (Section 3.1.3.1) require new logic to process negotiation. 505 *Matching security levels.* (Neg-Ind-1) (Section 3.1.2.1), (Neg-Ind- 506 2) (Section 3.1.2.2), (Neg-Ind-3) (Section 3.1.2.3), and (Neg-Comb-2) 507 (Section 3.1.3.2) allow algorithms of different claimed security 508 level from their corresponding lists to be combined. For example, 509 this could result in combining ECDH secp256r1 (classical security 510 level 128) with NewHope-1024 (classical security level 256). 511 Implementations dissatisfied with a mismatched security levels must 512 either accept this mismatch or attempt to renegotiate. (Neg-Ind-1) 513 (Section 3.1.2.1), (Neg-Ind-2) (Section 3.1.2.2), and (Neg-Ind-3) 514 (Section 3.1.2.3) give control over the combination to the server; 515 (Neg-Comb-2) (Section 3.1.3.2) gives control over the combination to 516 the client. (Neg-Comb-1) (Section 3.1.3.1) only allows standardized 517 combinations, which could be set by TLS working group to have 518 matching security (provided security estimates do not evolve 519 separately). 521 *Backwards-compability.* TLS 1.3-compliant hybrid-unaware servers 522 should ignore unreocgnized elements in "supported_groups" (Neg-Ind-2) 523 (Section 3.1.2.2), (Neg-Ind-3) (Section 3.1.2.3), (Neg-Comb-1) 524 (Section 3.1.3.1), (Neg-Comb-2) (Section 3.1.3.2) and unrecognized 525 "ClientHello" extensions (Neg-Ind-1) (Section 3.1.2.1), (Neg-Comb-2) 526 (Section 3.1.3.2). In (Neg-Ind-3) (Section 3.1.2.3) and (Neg-Comb-3) 527 (Section 3.1.3.3), a server that is hybrid-unaware will ignore the 528 delimiters in "supported_groups", and thus might try to negotiate an 529 algorithm individually that is only meant to be used in combination; 530 depending on how such an implementation is coded, it may also 531 encounter bugs when the same element appears multiple times in the 532 list. 534 3.2. (Num) How many component algorithms to combine? 536 3.2.1. (Num-2) Two 538 Exactly two algorithms can be combined together in hybrid key 539 exchange. This is the approach taken in [KIEFER] and [SCHANCK]. 541 3.2.2. (Num-2+) Two or more 543 Two or more algorithms can be combined together in hybrid key 544 exchange. This is the approach taken in [WHYTE13]. 546 3.2.3. Benefits and Drawbacks 548 Restricting the number of component algorithms that can be hybridized 549 to two substantially reduces the generality required. On the other 550 hand, some adopters may want to further reduce risk by employing 551 multiple next-gen algorithms built on different cryptographic 552 assumptions. 554 3.3. (Shares) How to convey key shares? 556 In ECDH ephmeral key exchange, the client sends its ephmeral public 557 key in the "key_share" extension of the "ClientHello" message, and 558 the server sends its ephmeral public key in the "key_share" extension 559 of the "ServerHello" message. 561 For a general key encapsulation mechanism used for ephemeral key 562 exchange, we imagine that that client generates a fresh KEM public 563 key / secret pair for each connection, sends it to the client, and 564 the server responds with a KEM ciphertext. For simplicity and 565 consistency with TLS 1.3 terminology, we will refer to both of these 566 types of objects as "key shares". 568 In hybrid key exchange, we have to decide how to convey the client's 569 two (or more) key shares, and the server's two (or more) key shares. 571 3.3.1. (Shares-Concat) Concatenate key shares 573 The client concatenates the bytes representing its two key shares and 574 uses this directly as the "key_exchange" value in a "KeyShareEntry" 575 in its "key_share" extension. The server does the same thing. Note 576 that the "key_exchange" value can be an octet string of length at 577 most 2^16-1. This is the approach taken in [KIEFER], [OQS-111], and 578 [WHYTE13]. 580 3.3.2. (Shares-Multiple) Send multiple key shares 582 The client sends multiple key shares directly in the "client_shares" 583 vectors of the "ClientHello" "key_share" extension. The server does 584 the same. (Note that while the existing "KeyShareClientHello" struct 585 allows for multiple key share entries, the existing 586 "KeyShareServerHello" only permits a single key share entry, so some 587 modification would be required to use this approach for the server to 588 send multiple key shares.) 590 3.3.3. (Shares-Ext-Additional) Extension carrying additional key shares 592 The client sends the key share for its traditional algorithm in the 593 original "key_share" extension of the "ClientHello" message, and the 594 key share for its next-gen algorithm in some additional extension in 595 the "ClientHello" message. The server does the same thing. This is 596 the approach taken in [SCHANCK]. 598 3.3.4. Benefits and Drawbacks 600 *Backwards compatibility.* (Shares-Multiple) (Section 3.3.2) is fully 601 backwards compatible with non-hybrid-aware servers. (Shares-Ext- 602 Additional) (Section 3.3.3) is backwards compatible with non-hybrid- 603 aware servers provided they ignore unrecognized extensions. (Shares- 604 Concat) (Section 3.3.1) is backwards-compatible with non-hybrid aware 605 servers, but may result in duplication / additional round trips (see 606 below). 608 *Duplication versus additional round trips.* If a client wants to 609 offer multiple key shares for multiple combinations in order to avoid 610 retry requests, then the client may ended up sending a key share for 611 one algorithm multiple times when using (Shares-Ext-Additional) 612 (Section 3.3.3) and (Shares-Concat) (Section 3.3.1). (For example, 613 if the client wants to send an ECDH-secp256r1 + McEliece123 key 614 share, and an ECDH-secp256r1 + NewHope1024 key share, then the same 615 ECDH public key may be sent twice. If the client also wants to offer 616 a traditional ECDH-only key share for non-hybrid-aware 617 implementations and avoid retry requests, then that same ECDH public 618 key may be sent another time.) (Shares-Multiple) (Section 3.3.2) 619 does not result in duplicate key shares. 621 3.4. (Comb) How to use keys? 623 Each component key exchange algorithm establishes a shared secret. 624 These shared secrets must be combined in some way that achieves the 625 "hybrid" property: the resulting secret is secure as long as at least 626 one of the component key exchange algorithms is unbroken. 628 3.4.1. (Comb-Concat) Concatenate keys then KDF 630 Each party concatenates the shared secrets established by each 631 component algorithm in an agreed-upon order, then uses feeds that 632 through a key derivation function. In the context of TLS 1.3, this 633 would mean using the concatenated shared secret in place of the 634 (EC)DHE input to the second call to "HKDF-Extract" in the TLS 1.3 key 635 schedule: 637 0 638 | 639 v 640 PSK -> HKDF-Extract = Early Secret 641 | 642 +-----> Derive-Secret(...) 643 +-----> Derive-Secret(...) 644 +-----> Derive-Secret(...) 645 | 646 v 647 Derive-Secret(., "derived", "") 648 | 649 v 650 concatenated_shared_secret -> HKDF-Extract = Handshake Secret 651 ^^^^^^^^^^^^^^^^^^^^^^^^^^ | 652 +-----> Derive-Secret(...) 653 +-----> Derive-Secret(...) 654 | 655 v 656 Derive-Secret(., "derived", "") 657 | 658 v 659 0 -> HKDF-Extract = Master Secret 660 | 661 +-----> Derive-Secret(...) 662 +-----> Derive-Secret(...) 663 +-----> Derive-Secret(...) 664 +-----> Derive-Secret(...) 666 This is the approach used in [KIEFER], [OQS-111], and [WHYTE13]. 668 [GIACON] analyzes the security of applying a KDF to concatenated KEM 669 shared secrets, but their analysis does not exactly apply here since 670 the transcript of ciphertexts is included in the KDF application 671 (though it should follow relatively straightforwardly). 673 [BINDEL] analyzes the security of the (Comb-Concat) approach as 674 abstracted in their "dualPRF" combiner. They show that, if the 675 component KEMs are IND-CPA-secure (or IND-CCA-secure), then the 676 values output by "Derive-Secret" are IND-CPA-secure (respectively, 677 IND-CCA-secure). An important aspect of their analysis is that each 678 ciphertext is input to the final PRF calls; this holds for TLS 1.3 679 since the "Derive-Secret" calls that derive output keys (application 680 traffic secrets, and exporter and resumption master secrets) include 681 the transcript hash as input. 683 3.4.2. (Comb-XOR) XOR keys then KDF 685 Each party XORs the shared secrets established by each component 686 algorithm (possibly after padding secrets of different lengths), then 687 uses feeds that through a key derivation function. In the context of 688 TLS 1.3, this would mean using the XORed shared secret in place of 689 the (EC)DHE input to the second call to "HKDF-Extract" in the TLS 1.3 690 key schedule. 692 [GIACON] analyzes the security of applying a KDF to the XORed KEM 693 shared secrets, but their analysis does not quite apply here since 694 the transcript of ciphertexts is included in the KDF application 695 (though it should follow relatively straightforwardly). 697 3.4.3. (Comb-Chain) Chain of KDF applications for each key 699 Each party applies a chain of key derivation functions to the shared 700 secrets established by each component algorithm in an agreed-upon 701 order; roughly speaking: "F(k1 || F(k2))". In the context of TLS 702 1.3, this would mean extending the key schedule to have one round of 703 the key schedule applied for each component algorithm's shared 704 secret: 706 0 707 | 708 v 709 PSK -> HKDF-Extract = Early Secret 710 | 711 +-----> Derive-Secret(...) 712 +-----> Derive-Secret(...) 713 +-----> Derive-Secret(...) 714 | 715 v 716 Derive-Secret(., "derived", "") 717 | 718 v 719 traditional_shared_secret -> HKDF-Extract 720 ^^^^^^^^^^^^^^^^^^^^^^^^^ | 721 Derive-Secret(., "derived", "") 722 | 723 v 724 next_gen_shared_secret -> HKDF-Extract = Handshake Secret 725 ^^^^^^^^^^^^^^^^^^^^^^ | 726 +-----> Derive-Secret(...) 727 +-----> Derive-Secret(...) 728 | 729 v 730 Derive-Secret(., "derived", "") 731 | 732 v 733 0 -> HKDF-Extract = Master Secret 734 | 735 +-----> Derive-Secret(...) 736 +-----> Derive-Secret(...) 737 +-----> Derive-Secret(...) 738 +-----> Derive-Secret(...) 740 This is the approach used in [SCHANCK]. 742 [BINDEL] analyzes the security of this approach as abstracted in 743 their nested dual-PRF "N" combiner, showing a similar result as for 744 the dualPRF combiner that it preserves IND-CPA (or IND-CCA) security. 745 Again their analysis depends on each ciphertext being input to the 746 final PRF ("Derive-Secret") calls, which holds for TLS 1.3. 748 3.4.4. (Comb-AltInput) Second shared secret in an alternate KDF input 750 In the context of TLS 1.3, the next-generation shared secret is used 751 in place of a currently unused input in the TLS 1.3 key schedule, 752 namely replacing the "0" "IKM" input to the final "HKDF-Extract": 754 0 755 | 756 v 757 PSK -> HKDF-Extract = Early Secret 758 | 759 +-----> Derive-Secret(...) 760 +-----> Derive-Secret(...) 761 +-----> Derive-Secret(...) 762 | 763 v 764 Derive-Secret(., "derived", "") 765 | 766 v 767 traditional_shared_secret -> HKDF-Extract = Handshake Secret 768 ^^^^^^^^^^^^^^^^^^^^^^^^^ | 769 +-----> Derive-Secret(...) 770 +-----> Derive-Secret(...) 771 | 772 v 773 Derive-Secret(., "derived", "") 774 | 775 v 776 next_gen_shared_secret -> HKDF-Extract = Master Secret 777 ^^^^^^^^^^^^^^^^^^^^^^ | 778 +-----> Derive-Secret(...) 779 +-----> Derive-Secret(...) 780 +-----> Derive-Secret(...) 781 +-----> Derive-Secret(...) 783 This approach is not taken in any of the known post-quantum/hybrid 784 TLS drafts. However, it bears some similarities to the approach for 785 using external PSKs in [EXTERN-PSK]. 787 3.4.5. Benefits and Drawbacks 789 *New logic.* While (Comb-Concat) (Section 3.4.1) requires new logic 790 to compute the concatenated shared secret, this value can then be 791 used by the TLS 1.3 key schedule without changes to the key schedule 792 logic. In contrast, (Comb-Chain) (Section 3.4.3) requires the TLS 793 1.3 key schedule to be extended for each extra component algorithm. 795 *Philosophical.* The TLS 1.3 key schedule already applies a new stage 796 for different types of keying material (PSK versus (EC)DHE), so 797 (Comb-Chain) (Section 3.4.3) continues that approach. 799 *Efficiency.* (Comb-Chain) (Section 3.4.3) increases the number of 800 KDF applications for each component algorithm, whereas (Comb-Concat) 801 (Section 3.4.1) and (Comb-AltInput) (Section 3.4.4) keep the number 802 of KDF applications the same (though with potentially longer inputs). 804 *Extensibility.* (Comb-AltInput) (Section 3.4.4) changes the use of 805 an existing input, which might conflict with other future changes to 806 the use of the input. 808 *More than 2 component algorithms.* The techniques in (Comb-Concat) 809 (Section 3.4.1) and (Comb-Chain) (Section 3.4.3) can naturally 810 accommodate more than 2 component shared secrets since there is no 811 distinction to how each shared secret is treated. (Comb-AltInput) 812 (Section 3.4.4) would have to make some distinct, since the 2 813 component shared secrets are used in different ways; for example, the 814 first shared secret is used as the "IKM" input in the 2nd "HKDF- 815 Extract" call, and all subsequent shared secrets are concatenated to 816 be used as the "IKM" input in the 3rd "HKDF-Extract" call. 818 4. IANA Considerations 820 None. 822 5. Security Considerations 824 The majority of this document is about security considerations. As 825 noted especially in Section 3.4, the shared secrets computed in the 826 hybrid key exchange should be computed in a way that achieves the 827 "hybrid" property: the resulting secret is secure as long as at least 828 one of the component key exchange algorithms is unbroken. While many 829 natural approaches seem to achieve this, there can be subtleties (see 830 for example the introduction of [GIACON]). 832 The rest of this section highlights a few unresolved questions 833 related to security. 835 5.1. Active security 837 One security consideration that is not yet resolved is whether key 838 encapsulation mechanisms used in TLS 1.3 must be secure against 839 active attacks (IND-CCA), or whether security against passive attacks 840 (IND-CPA) suffices. Existing security proofs of TLS 1.3 (such as 841 [DFGS15], [DOWLING]) are formulated specifically around Diffie- 842 Hellman and use an "actively secure" Diffie-Hellman assumption (PRF 843 Oracle Diffie-Hellman (PRF-ODH)) rather than a "passively secure" DH 844 assumption (e.g. decisional Diffie-Hellman (DDH)), but do not claim 845 that the actively secure notion is required. In the context of TLS 846 1.2, [KPW13] show that, at least in one formalization, a passively 847 secure assumption like DDH is insufficient (even when signatures are 848 used for mutual authentication). Resolving this issue for TLS 1.3 is 849 an open question. 851 5.2. Resumption 853 TLS 1.3 allows for session resumption via a pre-shared key. When a 854 pre-shared key is used during session establishment, an ephemeral key 855 exchange can also be used to enhance forward secrecy. If the 856 original key exchange was hybrid, should an ephemeral key exchange in 857 a resumption of that original key exchange be required to use the 858 same hybrid algorithms? 860 5.3. Failures 862 Some post-quantum key exchange algorithms have non-trivial failure 863 rates: two honest parties may fail to agree on the same shared secret 864 with non-negligible probability. Does a non-negligible failure rate 865 affect the security of TLS? How should such a failure be treated 866 operationally? What is an acceptable failure rate? 868 6. Acknowledgements 870 These ideas have grown from discussions with many colleagues, 871 including Christopher Wood, Matt Campagna, and authors of the various 872 hybrid Internet-Drafts and implementations cited in this document. 873 The immediate impetus for this document came from discussions with 874 attendees at the Workshop on Post-Quantum Software in Mountain View, 875 California, in January 2019. 877 7. References 879 7.1. Normative References 881 [TLS13] Rescorla, E., "The Transport Layer Security (TLS) Protocol 882 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 883 . 885 7.2. Informative References 887 [BCNS15] Bos, J., Costello, C., Naehrig, M., and D. Stebila, "Post- 888 Quantum Key Exchange for the TLS Protocol from the Ring 889 Learning with Errors Problem", 2015 IEEE Symposium on 890 Security and Privacy, DOI 10.1109/sp.2015.40, May 2015. 892 [BERNSTEIN] 893 "Post-Quantum Cryptography", Springer Berlin 894 Heidelberg book, DOI 10.1007/978-3-540-88702-7, 2009. 896 [BINDEL] Bindel, N., Brendel, J., Fischlin, M., Goncalves, B., and 897 D. Stebila, "Hybrid Key Encapsulation Mechanisms and 898 Authenticated Key Exchange", Post-Quantum Cryptography 899 (PQCrypto) , 2019, . 901 [CECPQ1] Braithwaite, M., "Experimenting with Post-Quantum 902 Cryptography", July 2016, 903 . 906 [CECPQ2] Langley, A., "CECPQ2", December 2018, 907 . 909 [DFGS15] Dowling, B., Fischlin, M., Guenther, F., and D. Stebila, 910 "A Cryptographic Analysis of the TLS 1.3 Handshake 911 Protocol Candidates", Proceedings of the 22nd ACM SIGSAC 912 Conference on Computer and Communications Security - 913 CCS '15, DOI 10.1145/2810103.2813653, 2015. 915 [DODIS] Dodis, Y. and J. Katz, "Chosen-Ciphertext Security of 916 Multiple Encryption", Theory of Cryptography pp. 188-209, 917 DOI 10.1007/978-3-540-30576-7_11, 2005. 919 [DOWLING] Dowling, B., "Provable Security of Internet Protocols", 920 Queensland University of Technology dissertation, 921 DOI 10.5204/thesis.eprints.108960, n.d.. 923 [ETSI] Campagna, M., Ed. and . others, "Quantum safe cryptography 924 and security: An introduction, benefits, enablers and 925 challengers", ETSI White Paper No. 8 , June 2015, 926 . 929 [EVEN] Even, S. and O. Goldreich, "On the Power of Cascade 930 Ciphers", Advances in Cryptology pp. 43-50, 931 DOI 10.1007/978-1-4684-4730-9_4, 1984. 933 [EXTERN-PSK] 934 Housley, R., "TLS 1.3 Extension for Certificate-based 935 Authentication with an External Pre-Shared Key", draft- 936 ietf-tls-tls13-cert-with-extern-psk-00 (work in progress), 937 February 2019. 939 [FRODO] Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, 940 M., Nikolaenko, V., Raghunathan, A., and D. Stebila, 941 "Frodo", Proceedings of the 2016 ACM SIGSAC Conference on 942 Computer and Communications Security - CCS'16, 943 DOI 10.1145/2976749.2978425, 2016. 945 [GIACON] Giacon, F., Heuer, F., and B. Poettering, "KEM Combiners", 946 Public-Key Cryptography - PKC 2018 pp. 190-218, 947 DOI 10.1007/978-3-319-76578-5_7, 2018. 949 [HARNIK] Harnik, D., Kilian, J., Naor, M., Reingold, O., and A. 950 Rosen, "On Robust Combiners for Oblivious Transfer and 951 Other Primitives", Lecture Notes in Computer Science pp. 952 96-113, DOI 10.1007/11426639_6, 2005. 954 [HOFFMAN] Hoffman, P., "The Transition from Classical to Post- 955 Quantum Cryptography", draft-hoffman-c2pq-04 (work in 956 progress), August 2018. 958 [IKE-HYBRID] 959 Tjhai, C., Tomlinson, M., grbartle@cisco.com, g., Fluhrer, 960 S., Geest, D., Garcia-Morchon, O., and V. Smyslov, 961 "Framework to Integrate Post-quantum Key Exchanges into 962 Internet Key Exchange Protocol Version 2 (IKEv2)", draft- 963 tjhai-ipsecme-hybrid-qske-ikev2-03 (work in progress), 964 January 2019. 966 [IKE-PSK] Fluhrer, S., McGrew, D., Kampanakis, P., and V. Smyslov, 967 "Postquantum Preshared Keys for IKEv2", draft-ietf- 968 ipsecme-qr-ikev2-07 (work in progress), January 2019. 970 [KIEFER] Kiefer, F. and K. Kwiatkowski, "Hybrid ECDHE-SIDH Key 971 Exchange for TLS", draft-kiefer-tls-ecdhe-sidh-00 (work in 972 progress), November 2018. 974 [KPW13] Krawczyk, H., Paterson, K., and H. Wee, "On the Security 975 of the TLS Protocol: A Systematic Analysis", Advances in 976 Cryptology - CRYPTO 2013 pp. 429-448, 977 DOI 10.1007/978-3-642-40041-4_24, 2013. 979 [LANGLEY] Langley, A., "Post-quantum confidentiality for TLS", April 980 2018, . 983 [NIELSEN] Nielsen, M. and I. Chuang, "Quantum Computation and 984 Quantum Information", Cambridge University Press , 2000. 986 [NIST] National Institute of Standards and Technology (NIST), 987 "Post-Quantum Cryptography", n.d., 988 . 990 [OQS-102] Open Quantum Safe Project, "OQS-OpenSSL-1-0-2_stable", 991 November 2018, . 994 [OQS-111] Open Quantum Safe Project, "OQS-OpenSSL-1-1-1_stable", 995 November 2018, . 998 [SCHANCK] Schanck, J. and D. Stebila, "A Transport Layer Security 999 (TLS) Extension For Establishing An Additional Shared 1000 Secret", draft-schanck-tls-additional-keyshare-00 (work in 1001 progress), April 2017. 1003 [WHYTE12] Schanck, J., Whyte, W., and Z. Zhang, "Quantum-Safe Hybrid 1004 (QSH) Ciphersuite for Transport Layer Security (TLS) 1005 version 1.2", draft-whyte-qsh-tls12-02 (work in progress), 1006 July 2016. 1008 [WHYTE13] Whyte, W., Zhang, Z., Fluhrer, S., and O. Garcia-Morchon, 1009 "Quantum-Safe Hybrid (QSH) Key Exchange for Transport 1010 Layer Security (TLS) version 1.3", draft-whyte-qsh- 1011 tls13-06 (work in progress), October 2017. 1013 [XMSS] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. 1014 Mohaisen, "XMSS: eXtended Merkle Signature Scheme", 1015 RFC 8391, DOI 10.17487/RFC8391, May 2018, 1016 . 1018 [ZHANG] Zhang, R., Hanaoka, G., Shikata, J., and H. Imai, "On the 1019 Security of Multiple Encryption or CCA-security+CCA- 1020 security=CCA-security?", Public Key Cryptography - PKC 1021 2004 pp. 360-374, DOI 10.1007/978-3-540-24632-9_26, 2004. 1023 Authors' Addresses 1025 Douglas Steblia 1026 University of Waterloo 1028 Email: dstebila@uwaterloo.ca 1030 Shay Gueron 1031 University of Haifa and Amazon Web Services 1033 Email: shay.gueron@gmail.com