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