idnits 2.17.1 draft-irtf-cfrg-randomness-improvements-10.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 seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords -- however, there's a paragraph with a matching beginning. Boilerplate error? (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document date (February 17, 2020) is 1531 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group C. Cremers 3 Internet-Draft CISPA Helmholtz Center for Information Security 4 Intended status: Informational L. Garratt 5 Expires: August 20, 2020 Cisco Meraki 6 S. Smyshlyaev 7 CryptoPro 8 N. Sullivan 9 Cloudflare 10 C. Wood 11 Apple Inc. 12 February 17, 2020 14 Randomness Improvements for Security Protocols 15 draft-irtf-cfrg-randomness-improvements-10 17 Abstract 19 Randomness is a crucial ingredient for TLS and related security 20 protocols. Weak or predictable "cryptographically-strong" 21 pseudorandom number generators (CSPRNGs) can be abused or exploited 22 for malicious purposes. The Dual EC random number backdoor and 23 Debian bugs are relevant examples of this problem. An initial 24 entropy source that seeds a CSPRNG might be weak or broken as well, 25 which can also lead to critical and systemic security problems. 27 This document describes a way for security protocol participants to 28 augment their CSPRNGs using long-term private keys. This improves 29 randomness from broken or otherwise subverted CSPRNGs. This document 30 is a product of the Crypto Forum Research Group (CFRG). 32 Status of This Memo 34 This Internet-Draft is submitted in full conformance with the 35 provisions of BCP 78 and BCP 79. 37 Internet-Drafts are working documents of the Internet Engineering 38 Task Force (IETF). Note that other groups may also distribute 39 working documents as Internet-Drafts. The list of current Internet- 40 Drafts is at https://datatracker.ietf.org/drafts/current/. 42 Internet-Drafts are draft documents valid for a maximum of six months 43 and may be updated, replaced, or obsoleted by other documents at any 44 time. It is inappropriate to use Internet-Drafts as reference 45 material or to cite them other than as "work in progress." 47 This Internet-Draft will expire on August 20, 2020. 49 Copyright Notice 51 Copyright (c) 2020 IETF Trust and the persons identified as the 52 document authors. All rights reserved. 54 This document is subject to BCP 78 and the IETF Trust's Legal 55 Provisions Relating to IETF Documents 56 (https://trustee.ietf.org/license-info) in effect on the date of 57 publication of this document. Please review these documents 58 carefully, as they describe your rights and restrictions with respect 59 to this document. Code Components extracted from this document must 60 include Simplified BSD License text as described in Section 4.e of 61 the Trust Legal Provisions and are provided without warranty as 62 described in the Simplified BSD License. 64 Table of Contents 66 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 67 2. Conventions Used in This Document . . . . . . . . . . . . . . 3 68 3. Randomness Wrapper . . . . . . . . . . . . . . . . . . . . . 3 69 4. Tag Generation . . . . . . . . . . . . . . . . . . . . . . . 5 70 5. Application to TLS . . . . . . . . . . . . . . . . . . . . . 5 71 6. Implementation Guidance . . . . . . . . . . . . . . . . . . . 6 72 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 6 73 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 74 9. Security Considerations . . . . . . . . . . . . . . . . . . . 6 75 10. Comparison to RFC 6979 . . . . . . . . . . . . . . . . . . . 7 76 11. Normative References . . . . . . . . . . . . . . . . . . . . 7 77 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 79 1. Introduction 81 Randomness is a crucial ingredient for TLS and related transport 82 security protocols. TLS in particular uses random number generators 83 (generally speaking, CSPRNGs) to generate several values: session 84 IDs, ephemeral key shares, and ClientHello and ServerHello random 85 values. CSPRNG failures such as the Debian bug described in 86 [DebianBug] can lead to insecure TLS connections. CSPRNGs may also 87 be intentionally weakened to cause harm [DualEC]. Initial entropy 88 sources can also be weak or broken, and that would lead to insecurity 89 of all CSPRNG instances seeded with them. In such cases where 90 CSPRNGs are poorly implemented or insecure, an adversary may be able 91 to predict its output and recover secret key material used to protect 92 the connection. 94 This document proposes an improvement to randomness generation in 95 security protocols inspired by the "NAXOS trick" [NAXOS]. 96 Specifically, instead of using raw randomness where needed, e.g., in 97 generating ephemeral key shares, a party's long-term private key is 98 mixed into the entropy pool. In the NAXOS key exchange protocol, raw 99 random value x is replaced by H(x, sk), where sk is the sender's 100 private key. Unfortunately, as private keys are often isolated in 101 HSMs, direct access to compute H(x, sk) is impossible. Moreover, 102 some HSM APIs may only offer the option to sign messages using a 103 private key, yet offer no other operations involving that key. An 104 alternate yet functionally equivalent construction is needed. 106 The approach described herein replaces the NAXOS hash with a keyed 107 hash, or pseudorandom function (PRF), where the key is derived from a 108 raw random value and a private key signature. Implementations SHOULD 109 apply this technique when indirect access to a private key is 110 available and CSPRNG randomness guarantees are dubious, or to provide 111 stronger guarantees about possible future issues with the randomness. 112 Roughly, the security properties provided by the proposed 113 construction are as follows: 115 1. If the CSPRNG works fine, that is, in a certain adversary model 116 the CSPRNG output is indistinguishable from a truly random 117 sequence, then the output of the proposed construction is also 118 indistinguishable from a truly random sequence in that adversary 119 model. 121 2. An adversary Adv with full control of a (potentially broken) 122 CSPRNG and able to observe all outputs of the proposed 123 construction, does not obtain any non-negligible advantage in 124 leaking the private key, modulo side channel attacks. 126 3. If the CSPRNG is broken or controlled by adversary Adv, the 127 output of the proposed construction remains indistinguishable 128 from random provided the private key remains unknown to Adv. 130 2. Conventions Used in This Document 132 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 133 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 134 "OPTIONAL" in this document are to be interpreted as described in BCP 135 14 [RFC2119], [RFC8174] when, and only when, they appear in all 136 capitals, as shown here. 138 3. Randomness Wrapper 140 The output of a properly instantiated CSPRNG should be 141 indistinguishable from a random string of the same length. However, 142 as previously discussed, this is not always true. To mitigate this 143 problem, we propose an approach for wrapping the CSPRNG output with a 144 construction that mixes secret data into a value that may be lacking 145 randomness. 147 Let G(n) be an algorithm that generates n random bytes, i.e., the 148 output of a CSPRNG. Define an augmented CSPRNG G' as follows. Let 149 Sig(sk, m) be a function that computes a signature of message m given 150 private key sk. Let H be a cryptographic hash function that produces 151 output of length M. Let Extract(salt, IKM) be a randomness 152 extraction function, e.g., HKDF-Extract [RFC5869], which accepts a 153 salt and input keying material (IKM) parameter and produces a 154 pseudorandom key of L bytes suitable for cryptographic use. It must 155 be a secure PRF (for salt as a key) and preserve uniformness of IKM 156 (for details see [SecAnalysis]). L SHOULD be a fixed length. Let 157 Expand(k, info, n) be a variable-length output PRF, e.g., HKDF-Expand 158 [RFC5869], that takes as input a pseudorandom key k of L bytes, info 159 string, and output length n, and produces output of n bytes. 160 Finally, let tag1 be a fixed, context-dependent string, and let tag2 161 be a dynamically changing string (e.g., a counter) of L' bytes. We 162 require that L >= n - L' for each value of tag2. 164 The construction works as follows. Instead of using G(n) when 165 randomness is needed, use G'(n), where 167 G'(n) = Expand(Extract(H(Sig(sk, tag1)), G(L)), tag2, n) 169 Functionally, this expands n random bytes from a key derived from the 170 CSPRNG output and signature over a fixed string (tag1). See 171 Section 4 for details about how "tag1" and "tag2" should be generated 172 and used per invocation of the randomness wrapper. Expand() 173 generates a string that is computationally indistinguishable from a 174 truly random string of n bytes. Thus, the security of this 175 construction depends upon the secrecy of H(Sig(sk, tag1)) and G(L). 176 If the signature is leaked, then security of G'(n) reduces to the 177 scenario wherein randomness is expanded directly from G(L). 179 If a private key sk is stored and used inside an HSM, then the 180 signature calculation is implemented inside it, while all other 181 operations (including calculation of a hash function, Extract and 182 Expand functions) can be implemented either inside or outside the 183 HSM. 185 Sig(sk, tag1) need only be computed once for the lifetime of the 186 randomness wrapper, and MUST NOT be used or exposed beyond its role 187 in this computation. Additional recommendations for tag1 are given 188 in the following section. 190 Sig MUST be a deterministic signature function, e.g., deterministic 191 ECDSA [RFC6979], or use an independent (and completely reliable) 192 entropy source, e.g., if Sig is implemented in an HSM with its own 193 internal trusted entropy source for signature generation. 195 Because Sig(sk, tag1) can be cached, the relative cost of using G'(n) 196 instead of G(n) tends to be negligible with respect to cryptographic 197 operations in protocols such as TLS (the relatively inexpensive 198 computational cost of HKDF dominates when comparing G' to G). A 199 description of the performance experiments and their results can be 200 found in the appendix of [SecAnalysis]. 202 Moreover, the values of G'(n) may be precomputed and pooled. This is 203 possible since the construction depends solely upon the CSPRNG output 204 and private key. 206 4. Tag Generation 208 Both tags SHOULD be generated such that they never collide with 209 another contender or owner of the private key. This can happen if, 210 for example, one HSM with a private key is used from several servers, 211 or if virtual machines are cloned. 213 Tag strings SHOULD be constructed as follows: 215 o tag1: Constant string bound to a specific device and protocol in 216 use. This allows caching of Sig(sk, tag1). Device specific 217 information may include, for example, a MAC address. To provide 218 security in the cases of usage of CSPRNGs in virtual environments, 219 it is RECOMMENDED to incorporate all available information 220 specific to the process that would ensure the uniqueness of each 221 tag1 value among different instances of virtual machines 222 (including ones that were cloned or recovered from snapshots). 223 This is needed to address the problem of CSPRNG state cloning (see 224 [RY2010]). See Section 5 for example protocol information that 225 can be used in the context of TLS 1.3. If sk could be used for 226 other purposes, then selecting a value for tag1 that is different 227 than the form allowed by those other uses ensures that the 228 signature is not exposed. 230 o tag2: A nonce. That is, a value that is unique for each use of 231 the same combination of G(L), tag1, and sk values. The tag2 value 232 can be implemented using a counter, or a timer, provided that the 233 timer is guaranteed to be different for each invocation of G'(n). 235 5. Application to TLS 237 The PRF randomness wrapper can be applied to any protocol wherein a 238 party has a long-term private key and also generates randomness. 239 This is true of most TLS servers. Thus, to apply this construction 240 to TLS, one simply replaces the "private" CSPRNG G(n), i.e., the 241 CSPRNG that generates private values, such as key shares, with: 243 G'(n) = HKDF-Expand(HKDF-Extract(H(Sig(sk, tag1)), G(L)), tag2, n) 245 6. Implementation Guidance 247 Recall that the wrapper defined in Section 3 requires L >= n - L', 248 where L is the Extract output length and n is the desired amount of 249 randomness. Some applications may require n to exceed this bound. 250 Wrapper implementations SHOULD support this use case by invoking G' 251 multiple times and concatenating the results. 253 7. Acknowledgements 255 We thank Liliya Akhmetzyanova for her deep involvement in the 256 security assessment in [SecAnalysis]. We thank John Mattsson, Martin 257 Thomson, Rich Salz for their careful readings and useful comments. 259 8. IANA Considerations 261 This document makes no request to IANA. 263 9. Security Considerations 265 A security analysis was performed in [SecAnalysis]. Generally 266 speaking, the following security theorem has been proven: if the 267 adversary learns only one of the signature or the usual randomness 268 generated on one particular instance, then under the security 269 assumptions on our primitives, the wrapper construction should output 270 randomness that is indistinguishable from a random string. 272 The main reason one might expect the signature to be exposed is via a 273 side-channel attack. It is therefore prudent when implementing this 274 construction to take into consideration the extra long-term key 275 operation if equipment is used in a hostile environment when such 276 considerations are necessary. Hence, it is recommended to generate a 277 key specifically for the purposes of the defined construction and not 278 to use it another way. 280 The signature in the construction as well as in the protocol itself 281 MUST NOT use randomness from entropy sources with dubious security 282 guarantees. Thus, the signature scheme MUST either use a reliable 283 entropy source (independent from the CSPRNG that is being improved 284 with the proposed construction) or be deterministic: if the 285 signatures are probabilistic and use weak entropy, our construction 286 does not help and the signatures are still vulnerable due to repeat 287 randomness attacks. In such an attack, the adversary might be able 288 to recover the long-term key used in the signature. 290 Under these conditions, applying this construction should never yield 291 worse security guarantees than not applying it assuming that applying 292 the PRF does not reduce entropy. We believe there is always merit in 293 analyzing protocols specifically. However, this construction is 294 generic so the analyses of many protocols will still hold even if 295 this proposed construction is incorporated. 297 The proposed construction cannot provide any guarantees of security 298 if the CSPRNG state is cloned due to the virtual machine snapshots or 299 process forking (see [MAFS2017]). Thus tag1 SHOULD incorporate all 300 available information about the environment, such as process 301 attributes, virtual machine user information, etc. 303 10. Comparison to RFC 6979 305 The construction proposed herein has similarities with that of RFC 306 6979 [RFC6979]: both of them use private keys to seed a DRBG. 307 Section 3.3 of RFC 6979 recommends deterministically instantiating an 308 instance of the HMAC DRBG pseudorandom number generator, described in 309 [SP80090A] and Annex D of [X962], using the private key sk as the 310 entropy_input parameter and H(m) as the nonce. The construction 311 G'(n) provided herein is similar, with such difference that a key 312 derived from G(n) and H(Sig(sk, tag1)) is used as the entropy input 313 and tag2 is the nonce. 315 However, the semantics and the security properties obtained by using 316 these two constructions are different. The proposed construction 317 aims to improve CSPRNG usage such that certain trusted randomness 318 would remain even if the CSPRNG is completely broken. Using a 319 signature scheme which requires entropy sources according to RFC 6979 320 is intended for different purposes and does not assume possession of 321 any entropy source - even an unstable one. For example, if in a 322 certain system all private key operations are performed within an 323 HSM, then the differences will manifest as follows: the HMAC DRBG 324 construction of RFC 6979 may be implemented inside the HSM for the 325 sake of signature generation, while the proposed construction would 326 assume calling the signature implemented in the HSM. 328 11. Normative References 330 [DebianBug] 331 Yilek, Scott, et al, ., "When private keys are public - 332 Results from the 2008 Debian OpenSSL vulnerability", 2009, 333 . 336 [DualEC] Bernstein, Daniel et al, ., "Dual EC - A standardized back 337 door", 2016, . 340 [MAFS2017] 341 McGrew, Anderson, Fluhrer, Shenefeil, ., "PRNG Failures 342 and TLS Vulnerabilities in the Wild", 2017, 343 . 345 [NAXOS] LaMacchia, Brian et al, ., "Stronger Security of 346 Authenticated Key Exchange", 2007, 347 . 350 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 351 Requirement Levels", BCP 14, RFC 2119, 352 DOI 10.17487/RFC2119, March 1997, 353 . 355 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 356 Key Derivation Function (HKDF)", RFC 5869, 357 DOI 10.17487/RFC5869, May 2010, 358 . 360 [RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature 361 Algorithm (DSA) and Elliptic Curve Digital Signature 362 Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August 363 2013, . 365 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 366 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 367 May 2017, . 369 [RY2010] Ristenpart, Yilek, ., "When Good Randomness Goes Bad|:| 370 Virtual Machine Reset Vulnerabilities and Hedging Deployed 371 Cryptography", 2010, 372 . 374 [SecAnalysis] 375 Akhmetzyanova, Cremers, Garratt, Smyshlyaev, Sullivan, ., 376 "Limiting the impact of unreliable randomness in deployed 377 security protocols", 2019, 378 . 380 [SP80090A] 381 "Recommendation for Random Number Generation Using 382 Deterministic Random Bit Generators (Revised), NIST 383 Special Publication 800-90A.", January 2012, . 386 [X9.62] American National Standards Institute, ., "Public Key 387 Cryptography for the Financial Services Industry -- The 388 Elliptic Curve Digital Signature Algorithm (ECDSA). ANSI 389 X9.62-2005", November 2005. 391 [X962] "Public Key Cryptography for the Financial Services 392 Industry -- The Elliptic Curve Digital Signature Algorithm 393 (ECDSA), ANSI X9.62-2005", November 2005, . 396 Authors' Addresses 398 Cas Cremers 399 CISPA Helmholtz Center for Information Security 400 Saarland Informatics Campus 401 Saarbruecken 402 Germany 404 Email: cremers@cispa.saarland 406 Luke Garratt 407 Cisco Meraki 408 500 Terry A Francois Blvd 409 San Francisco 410 United States of America 412 Email: lgarratt@cisco.com 414 Stanislav Smyshlyaev 415 CryptoPro 416 18, Suschevsky val 417 Moscow 418 Russian Federation 420 Email: svs@cryptopro.ru 421 Nick Sullivan 422 Cloudflare 423 101 Townsend St 424 San Francisco 425 United States of America 427 Email: nick@cloudflare.com 429 Christopher A. Wood 430 Apple Inc. 431 One Apple Park Way 432 Cupertino, California 95014 433 United States of America 435 Email: cawood@apple.com