idnits 2.17.1 draft-irtf-cfrg-randomness-improvements-06.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 : ---------------------------------------------------------------------------- ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 102: '...key signature. Implementations SHOULD...' RFC 2119 keyword, line 169: '...ess wrapper, and MUST NOT be used or e...' RFC 2119 keyword, line 174: '... Sig MUST be a deterministic signatu...' RFC 2119 keyword, line 191: '... Both tags SHOULD be generated such ...' RFC 2119 keyword, line 196: '...ons, tag strings SHOULD be constructed...' (5 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (July 08, 2019) is 1751 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC2104' is defined on line 327, but no explicit reference was found in the text Summary: 1 error (**), 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: January 9, 2020 University of Oxford 6 S. Smyshlyaev 7 CryptoPro 8 N. Sullivan 9 Cloudflare 10 C. Wood 11 Apple Inc. 12 July 08, 2019 14 Randomness Improvements for Security Protocols 15 draft-irtf-cfrg-randomness-improvements-06 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 January 9, 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. Randomness Wrapper . . . . . . . . . . . . . . . . . . . . . 3 66 3. Tag Generation . . . . . . . . . . . . . . . . . . . . . . . 5 67 4. Application to TLS . . . . . . . . . . . . . . . . . . . . . 5 68 5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 5 69 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 6 70 7. Security Considerations . . . . . . . . . . . . . . . . . . . 6 71 8. Comparison to RFC 6979 . . . . . . . . . . . . . . . . . . . 7 72 9. Normative References . . . . . . . . . . . . . . . . . . . . 7 73 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8 75 1. Introduction 77 Randomness is a crucial ingredient for TLS and related transport 78 security protocols. TLS in particular uses random number generators 79 (generally speaking, CSPRNGs) to generate several values: session 80 IDs, ephemeral key shares, and ClientHello and ServerHello random 81 values. CSPRNG failures such as the Debian bug described in 82 [DebianBug] can lead to insecure TLS connections. CSPRNGs may also 83 be intentionally weakened to cause harm [DualEC]. Initial entropy 84 sources can also be weak or broken, and that would lead to insecurity 85 of all CSPRNG instances seeded with them. In such cases where 86 CSPRNGs are poorly implemented or insecure, an adversary may be able 87 to predict its output and recover secret Diffie-Hellman key shares 88 that protect the connection. 90 This document proposes an improvement to randomness generation in 91 security protocols inspired by the "NAXOS trick" [NAXOS]. 92 Specifically, instead of using raw randomness where needed, e.g., in 93 generating ephemeral key shares, a party's long-term private key is 94 mixed into the entropy pool. In the NAXOS key exchange protocol, raw 95 random value x is replaced by H(x, sk), where sk is the sender's 96 private key. Unfortunately, as private keys are often isolated in 97 HSMs, direct access to compute H(x, sk) is impossible. An alternate 98 yet functionally equivalent construction is needed. 100 The approach described herein replaces the NAXOS hash with a keyed 101 hash, or pseudorandom function (PRF), where the key is derived from a 102 raw random value and a private key signature. Implementations SHOULD 103 apply this technique when indirect access to a private key is 104 available and CSPRNG randomness guarantees are dubious, or to provide 105 stronger guarantees about possible future issues with the randomness. 106 Roughly, the security properties provided by the proposed 107 construction are as follows: 109 1. If the CSPRNG works fine, that is, in a certain adversary model 110 the CSPRNG output is indistinguishable from a truly random 111 sequence, then the output of the proposed construction is also 112 indistinguishable from a truly random sequence in that adversary 113 model. 115 2. An adversary Adv with full control of a (potentially broken) 116 CSPRNG and able to observe all outputs of the proposed 117 construction, does not obtain any non-negligible advantage in 118 leaking the private key, modulo side channel attacks. 120 3. If the CSPRNG is broken or controlled by adversary Adv, the 121 output of the proposed construction remains indistinguishable 122 from random provided the private key remains unknown to Adv. 124 2. Randomness Wrapper 126 The output of a properly instantiated CSPRNG should be 127 indistinguishable from a random string of the same length. However, 128 as previously discussed, this is not always true. To mitigate this 129 problem, we propose an approach for wrapping the CSPRNG output with a 130 construction that mixes secret data into a value that may be lacking 131 randomness. 133 Let G(n) be an algorithm that generates n random bytes, i.e., the 134 output of a CSPRNG. Define an augmented CSPRNG G' as follows. Let 135 Sig(sk, m) be a function that computes a signature of message m given 136 private key sk. Let H be a cryptographic hash function that produces 137 output of length M. Let Extract(salt, IKM) be a randomness 138 extraction function, e.g., HKDF-Extract [RFC5869], which accepts a 139 salt and input keying material (IKM) parameter and produces a 140 pseudorandom key of length L suitable for cryptographic use. Let 141 Expand(k, info, n) be a variable-length output PRF, e.g., HKDF-Expand 142 [RFC5869], that takes as input a pseudorandom key k of length L, info 143 string, and output length n, and produces output of n bytes. 144 Finally, let tag1 be a fixed, context-dependent string, and let tag2 145 be a dynamically changing string. 147 The construction works as follows. Instead of using G(n) when 148 randomness is needed, use G'(n), where 150 G'(n) = Expand(Extract(H(Sig(sk, tag1)), G(L)), tag2, n) 152 Functionally, this expands n random bytes from a key derived from the 153 CSPRNG output and signature over a fixed string (tag1). See 154 Section 3 for details about how "tag1" and "tag2" should be generated 155 and used per invocation of the randomness wrapper. Expand() 156 generates a string that is computationally indistinguishable from a 157 truly random string of n bytes. Thus, the security of this 158 construction depends upon the secrecy of H(Sig(sk, tag1)) and G(L). 159 If the signature is leaked, then security of G'(n) reduces to the 160 scenario wherein randomness is expanded directly from G(L). 162 If a private key sk is stored and used inside an HSM, then the 163 signature calculation is implemented inside it, while all other 164 operations (including calculation of a hash function, Extract and 165 Expand functions) can be implemented either inside or outside the 166 HSM. 168 Sig(sk, tag1) need only be computed once for the lifetime of the 169 randomness wrapper, and MUST NOT be used or exposed beyond its role 170 in this computation. To achieve this, tag1 may have the format that 171 is not supported (or explicitly forbidden) by other applications 172 using sk. 174 Sig MUST be a deterministic signature function, e.g., deterministic 175 ECDSA [RFC6979], or use an independent (and completely reliable) 176 entropy source, e.g., if Sig is implemented in an HSM with its own 177 internal trusted entropy source for signature generation. 179 Because Sig(sk, tag1) can be cached, the relative cost of using G'(n) 180 instead of G(n) tends to be negligible with respect to cryptographic 181 operations in protocols such as TLS. A description of the 182 performance experiments and their results can be found in the 183 appendix of [SecAnalysis]. 185 Moreover, the values of G'(n) may be precomputed and pooled. This is 186 possible since the construction depends solely upon the CSPRNG output 187 and private key. 189 3. Tag Generation 191 Both tags SHOULD be generated such that they never collide with 192 another contender or owner of the private key. This can happen if, 193 for example, one HSM with a private key is used from several servers, 194 or if virtual machines are cloned. 196 To mitigate collisions, tag strings SHOULD be constructed as follows: 198 o tag1: Constant string bound to a specific device and protocol in 199 use. This allows caching of Sig(sk, tag1). Device specific 200 information may include, for example, a MAC address. To provide 201 security in the cases of usage of CSPRNGs in virtual environments, 202 it is RECOMMENDED to incorporate all available information 203 specific to the process that would ensure the uniqueness of each 204 tag1 value among different instances of virtual machines 205 (including ones that were cloned or recovered from snapshots). 206 This is needed to address the problem of CSPRNG state cloning (see 207 [RY2010]). See Section 4 for example protocol information that 208 can be used in the context of TLS 1.3. 210 o tag2: Non-constant string that includes a timestamp or counter. 211 This ensures change over time even if outputs of G(L) were to 212 repeat. It MUST be implemented such that its values never repeat. 213 This means, in particular, that timestamp is guaranteed to change 214 between two requests to CSPRNG (otherwise counters should be 215 used). 217 4. Application to TLS 219 The PRF randomness wrapper can be applied to any protocol wherein a 220 party has a long-term private key and also generates randomness. 221 This is true of most TLS servers. Thus, to apply this construction 222 to TLS, one simply replaces the "private" CSPRNG G(n), i.e., the 223 CSPRNG that generates private values, such as key shares, with: 225 G'(n) = HKDF-Expand(HKDF-Extract(H(Sig(sk, tag1)), G(L)), tag2, n) 227 Moreover, we fix tag1 to protocol-specific information such as "TLS 228 1.3 Additional Entropy" for TLS 1.3. Older variants use similarly 229 constructed strings. 231 5. Acknowledgements 233 We thank Liliya Akhmetzyanova for her deep involvement in the 234 security assessment in [SecAnalysis]. 236 6. IANA Considerations 238 This document makes no request to IANA. 240 7. Security Considerations 242 A security analysis was performed in [SecAnalysis]. Generally 243 speaking, the following security theorem has been proven: if the 244 adversary learns only one of the signature or the usual randomness 245 generated on one particular instance, then under the security 246 assumptions on our primitives, the wrapper construction should output 247 randomness that is indistinguishable from a random string. 249 The main reason one might expect the signature to be exposed is via a 250 side-channel attack. It is therefore prudent when implementing this 251 construction to take into consideration the extra long-term key 252 operation if equipment is used in a hostile environment when such 253 considerations are necessary. Hence, it is recommended to generate a 254 key specifically for the purposes of the defined construction and not 255 to use it another way. 257 The signature in the construction as well as in the protocol itself 258 MUST NOT use randomness from entropy sources with dubious security 259 guarantees. Thus, the signature scheme MUST either use a reliable 260 entropy source (independent from the CSPRNG that is being improved 261 with the proposed construction) or be deterministic: if the 262 signatures are probabilistic and use weak entropy, our construction 263 does not help and the signatures are still vulnerable due to repeat 264 randomness attacks. In such an attack, the adversary might be able 265 to recover the long-term key used in the signature. 267 Under these conditions, applying this construction should never yield 268 worse security guarantees than not applying it assuming that applying 269 the PRF does not reduce entropy. We believe there is always merit in 270 analyzing protocols specifically. However, this construction is 271 generic so the analyses of many protocols will still hold even if 272 this proposed construction is incorporated. 274 The proposed construction cannot provide any guarantees of security 275 if the CSPRNG state is cloned due to the virtual machine snapshots or 276 process forking (see [MAFS2017]). Thus tag1 SHOULD incorporate all 277 available information about the environment, such as process 278 attributes, virtual machine user information, etc. 280 8. Comparison to RFC 6979 282 The construction proposed herein has similarities with that of RFC 283 6979 [RFC6979]: both of them use private keys to seed a DRBG. 284 Section 3.3 of RFC 6979 recommends deterministically instantiating an 285 instance of the HMAC DRBG pseudorandom number generator, described in 286 [SP80090A] and Annex D of [X962], using the private key sk as the 287 entropy_input parameter and H(m) as the nonce. The construction 288 G'(n) provided herein is similar, with such difference that a key 289 derived from G(n) and H(Sig(sk, tag1)) is used as the entropy input 290 and tag2 is the nonce. 292 However, the semantics and the security properties obtained by using 293 these two constructions are different. The proposed construction 294 aims to improve CSPRNG usage such that certain trusted randomness 295 would remain even if the CSPRNG is completely broken. Using a 296 signature scheme which requires entropy sources according to RFC 6979 297 is intended for different purposes and does not assume possession of 298 any entropy source - even an unstable one. For example, if in a 299 certain system all private key operations are performed within an 300 HSM, then the differences will manifest as follows: the HMAC DRBG 301 construction of RFC 6979 may be implemented inside the HSM for the 302 sake of signature generation, while the proposed construction would 303 assume calling the signature implemented in the HSM. 305 9. Normative References 307 [DebianBug] 308 Yilek, Scott, et al, ., "When private keys are public - 309 Results from the 2008 Debian OpenSSL vulnerability", n.d., 310 . 313 [DualEC] Bernstein, Daniel et al, ., "Dual EC - A standardized back 314 door", n.d., . 317 [MAFS2017] 318 McGrew, Anderson, Fluhrer, Shenefeil, ., "PRNG Failures 319 and TLS Vulnerabilities in the Wild", n.d., 320 . 322 [NAXOS] LaMacchia, Brian et al, ., "Stronger Security of 323 Authenticated Key Exchange", n.d., 324 . 327 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 328 Hashing for Message Authentication", RFC 2104, 329 DOI 10.17487/RFC2104, February 1997, 330 . 332 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 333 Key Derivation Function (HKDF)", RFC 5869, 334 DOI 10.17487/RFC5869, May 2010, 335 . 337 [RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature 338 Algorithm (DSA) and Elliptic Curve Digital Signature 339 Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August 340 2013, . 342 [RY2010] Ristenpart, Yilek, ., "When Good Randomness Goes Bad|:| 343 Virtual Machine Reset Vulnerabilities and Hedging Deployed 344 Cryptography", n.d., 345 . 347 [SecAnalysis] 348 Akhmetzyanova, Cremers, Garratt, Smyshlyaev, ., "Security 349 Analysis for Randomness Improvements for Security 350 Protocols", n.d., . 352 [SP80090A] 353 "Recommendation for Random Number Generation Using 354 Deterministic Random Bit Generators (Revised), NIST 355 Special Publication 800-90A, January 2012.", n.d., 356 . 358 [X9.62] American National Standards Institute, ., "Public Key 359 Cryptography for the Financial Services Industry -- The 360 Elliptic Curve Digital Signature Algorithm (ECDSA). ANSI 361 X9.62-2005, November 2005.", n.d.. 363 [X962] "Public Key Cryptography for the Financial Services 364 Industry -- The Elliptic Curve Digital Signature Algorithm 365 (ECDSA), ANSI X9.62-2005, November 2005.", n.d., . 368 Authors' Addresses 369 Cas Cremers 370 CISPA Helmholtz Center for Information Security 371 Saarland Informatics Campus 372 Saarbruecken 373 Germany 375 Email: cremers@cispa.saarland 377 Luke Garratt 378 University of Oxford 379 Wolfson Building, Parks Road 380 Oxford 381 England 383 Email: luke.garratt@cs.ox.ac.uk 385 Stanislav Smyshlyaev 386 CryptoPro 387 18, Suschevsky val 388 Moscow 389 Russian Federation 391 Email: svs@cryptopro.ru 393 Nick Sullivan 394 Cloudflare 395 101 Townsend St 396 San Francisco 397 United States of America 399 Email: nick@cloudflare.com 401 Christopher A. Wood 402 Apple Inc. 403 One Apple Park Way 404 Cupertino, California 95014 405 United States of America 407 Email: cawood@apple.com