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