idnits 2.17.1 draft-irtf-cfrg-randomness-improvements-03.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 100: '...key signature. Implementations SHOULD...' RFC 2119 keyword, line 168: '...ess wrapper, and MUST NOT be used or e...' RFC 2119 keyword, line 173: '... Sig MUST be a deterministic signatu...' RFC 2119 keyword, line 184: '... Both tags SHOULD be generated such ...' RFC 2119 keyword, line 189: '...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 (October 21, 2018) is 2014 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RY2010' is defined on line 322, 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 L. Garratt 4 Intended status: Informational University of Oxford 5 Expires: April 24, 2019 S. Smyshlyaev 6 CryptoPro 7 N. Sullivan 8 Cloudflare 9 C. Wood 10 Apple Inc. 11 October 21, 2018 13 Randomness Improvements for Security Protocols 14 draft-irtf-cfrg-randomness-improvements-03 16 Abstract 18 Randomness is a crucial ingredient for TLS and related security 19 protocols. Weak or predictable "cryptographically-strong" 20 pseudorandom number generators (CSPRNGs) can be abused or exploited 21 for malicious purposes. The Dual EC random number backdoor and 22 Debian bugs are relevant examples of this problem. An initial 23 entropy source that seeds a CSPRNG might be weak or broken as well, 24 which can also lead to critical and systemic security problems. This 25 document describes a way for security protocol participants to 26 augment their CSPRNGs using long-term private keys. This improves 27 randomness from broken or otherwise subverted CSPRNGs. 29 Status of This Memo 31 This Internet-Draft is submitted in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF). Note that other groups may also distribute 36 working documents as Internet-Drafts. The list of current Internet- 37 Drafts is at https://datatracker.ietf.org/drafts/current/. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 This Internet-Draft will expire on April 24, 2019. 46 Copyright Notice 48 Copyright (c) 2018 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (https://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 64 2. Randomness Wrapper . . . . . . . . . . . . . . . . . . . . . 3 65 3. Tag Generation . . . . . . . . . . . . . . . . . . . . . . . 4 66 4. Application to TLS . . . . . . . . . . . . . . . . . . . . . 5 67 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5 68 6. Security Considerations . . . . . . . . . . . . . . . . . . . 5 69 7. Comparison to RFC 6979 . . . . . . . . . . . . . . . . . . . 6 70 8. Normative References . . . . . . . . . . . . . . . . . . . . 7 71 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8 73 1. Introduction 75 Randomness is a crucial ingredient for TLS and related transport 76 security protocols. TLS in particular uses random number generators 77 (generally speaking, CSPRNGs) to generate several values: session 78 IDs, ephemeral key shares, and ClientHello and ServerHello random 79 values. CSPRNG failures such as the Debian bug described in 80 [DebianBug] can lead to insecure TLS connections. CSPRNGs may also 81 be intentionally weakened to cause harm [DualEC]. Initial entropy 82 sources can also be weak or broken, and that would lead to insecurity 83 of all CSPRNG instances seeded with them. In such cases where 84 CSPRNGs are poorly implemented or insecure, an adversary may be able 85 to predict its output and recover secret Diffie-Hellman key shares 86 that protect the connection. 88 This document proposes an improvement to randomness generation in 89 security protocols inspired by the "NAXOS trick" [NAXOS]. 90 Specifically, instead of using raw randomness where needed, e.g., in 91 generating ephemeral key shares, a party's long-term private key is 92 mixed into the entropy pool. In the NAXOS key exchange protocol, raw 93 random value x is replaced by H(x, sk), where sk is the sender's 94 private key. Unfortunately, as private keys are often isolated in 95 HSMs, direct access to compute H(x, sk) is impossible. An alternate 96 yet functionally equivalent construction is needed. 98 The approach described herein replaces the NAXOS hash with a keyed 99 hash, or pseudorandom function (PRF), where the key is derived from a 100 raw random value and a private key signature. Implementations SHOULD 101 apply this technique when indirect access to a private key is 102 available and CSPRNG randomness guarantees are dubious, or to provide 103 stronger guarantees about possible future issues with the randomness. 104 Roughly, the security properties provided by the proposed 105 construction are as follows: 107 1. If the CSPRNG works fine, that is, in a certain adversary model 108 the CSPRNG output is indistinguishable from a truly random 109 sequence, then the output of the proposed construction is also 110 indistinguishable from a truly random sequence in that adversary 111 model. 113 2. An adversary Adv with full control of a (potentially broken) 114 CSPRNG and able to observe all outputs of the proposed 115 construction, does not obtain any non-negligible advantage in 116 leaking the private key, modulo side channel attacks. 118 3. If the CSPRNG is broken or controlled by adversary Adv, the 119 output of the proposed construction remains indistinguishable 120 from random provided the private key remains unknown to Adv. 122 2. Randomness Wrapper 124 Let x be the output of a CSPRNG. When properly instantiated, x 125 should be indistinguishable from a random string of x bytes. 126 However, as previously discussed, this is not always true. To 127 mitigate this problem, we propose an approach for wrapping the CSPRNG 128 output with a construction that mixes secret data into a value that 129 may be lacking randomness. 131 Let G(n) be an algorithm that generates n random bytes, i.e., the 132 output of a CSPRNG. Define an augmented CSPRNG G' as follows. Let 133 Sig(sk, m) be a function that computes a signature of message m given 134 private key sk. Let H be a cryptographic hash function that produces 135 output of length M. Let Extract(salt, IKM) be a randomness 136 extraction function, e.g., HKDF-Extract [RFC5869], which accepts a 137 salt and input keying material (IKM) parameter and produces a 138 pseudorandom key of length L suitable for cryptographic use. Let 139 Expand(k, info, n) be a randomness extractor, e.g., HKDF-Expand 140 [RFC5869], that takes as input a pseudorandom key k of length L, info 141 string, and output length n, and produces output of n bytes. 143 Finally, let tag1 be a fixed, context-dependent string, and let tag2 144 be a dynamically changing string. 146 The construction works as follows. Instead of using G(n) when 147 randomness is needed, use G'(n), where 149 G'(n) = Expand(Extract(G(L), H(Sig(sk, tag1))), tag2, n) 151 Functionally, this expands n random bytes from a key derived from the 152 CSPRNG output and signature over a fixed string (tag1). See 153 Section 3 for details about how "tag1" and "tag2" should be generated 154 and used per invocation of the randomness wrapper. Expand() 155 generates a string that is computationally indistinguishable from a 156 truly random string of n bytes. Thus, the security of this 157 construction depends upon the secrecy of H(Sig(sk, tag1)) and G(n). 158 If the signature is leaked, then security of G'(n) reduces to the 159 scenario wherein randomness is expanded directly from G(n). 161 If a private key sk is stored and used inside an HSM, then the 162 signature calculation is implemented inside it, while all other 163 operations (including calculation of a hash function, Extract and 164 Expand functions) can be implemented either inside or outside the 165 HSM. 167 Sig(sk, tag1) should only be computed once for the lifetime of the 168 randomness wrapper, and MUST NOT be used or exposed beyond its role 169 in this computation. To achieve this, tag1 may have the format that 170 is not supported (or explicitly forbidden) by other applications 171 using sk. 173 Sig MUST be a deterministic signature function, e.g., deterministic 174 ECDSA [RFC6979], or use an independent (and completely reliable) 175 entropy source, e.g., if Sig is implemented in an HSM with its own 176 internal trusted entropy source for signature generation. 178 In systems where signature computations are expensive, G'(n) may be 179 precomputed and pooled. This is possible since the construction 180 depends solely upon the CSPRNG output and private key. 182 3. Tag Generation 184 Both tags SHOULD be generated such that they never collide with 185 another contender or owner of the private key. This can happen if, 186 for example, one HSM with a private key is used from several servers, 187 or if virtual machines are cloned. 189 To mitigate collisions, tag strings SHOULD be constructed as follows: 191 o tag1: Constant string bound to a specific device and protocol in 192 use. This allows caching of Sig(sk, tag1). Device specific 193 information may include, for example, a MAC address. To provide 194 security in the cases of usage of CSPRNGs in virtual environments, 195 it is RECOMMENDED to incorporate all available information 196 specific to the process that would ensure the uniqueness of each 197 tag1 value among different instances of virtual machines 198 (including ones that were cloned or recovered from snapshots). It 199 is needed to address the problem of CSPRNG state cloning (see 200 [RY2010]}. See Section 4 for example protocol information that 201 can be used in the context of TLS 1.3. 203 o tag2: Non-constant string that includes a timestamp or counter. 204 This ensures change over time even if outputs of G(L) were to 205 repeat. It MUST be implemented such that its values never repeat. 206 This means, in particular, that timestamp is guaranteed to change 207 between two requests to CSPRNG (otherwise counters should be 208 used). 210 4. Application to TLS 212 The PRF randomness wrapper can be applied to any protocol wherein a 213 party has a long-term private key and also generates randomness. 214 This is true of most TLS servers. Thus, to apply this construction 215 to TLS, one simply replaces the "private" CSPRNG G(n), i.e., the 216 CSPRNG that generates private values, such as key shares, with: 218 G'(n) = HKDF-Expand(HKDF-Extract(G(L), H(Sig(sk, tag1))), tag2, n) 220 Moreover, we fix tag1 to protocol-specific information such as "TLS 221 1.3 Additional Entropy" for TLS 1.3. Older variants use similarly 222 constructed strings. 224 5. IANA Considerations 226 This document makes no request to IANA. 228 6. Security Considerations 230 A security analysis was performed by two authors of this document. 231 Generally speaking, security depends on keeping the private key 232 secret. If this secret is compromised, the scheme reduces to the 233 scenario wherein the PRF provides only an outer wrapper on usual 234 CSPRNG generation. 236 The main reason one might expect the signature to be exposed is via a 237 side-channel attack. It is therefore prudent when implementing this 238 construction to take into consideration the extra long-term key 239 operation if equipment is used in a hostile environment when such 240 considerations are necessary. 242 The signature in the construction as well as in the protocol itself 243 MUST NOT use randomness from entropy sources with dubious security 244 guarantees. Thus, the signature scheme MUST either use a reliable 245 entropy source (independent from the CSPRNG that is being improved 246 with the proposed construction) or be deterministic: if the 247 signatures are probabilistic and use weak entropy, our construction 248 does not help and the signatures are still vulnerable due to repeat 249 randomness attacks. In such an attack, the adversary might be able 250 to recover the long-term key used in the signature. 252 Under these conditions, applying this construction should never yield 253 worse security guarantees than not applying it assuming that applying 254 the PRF does not reduce entropy. We believe there is always merit in 255 analyzing protocols specifically. However, this construction is 256 generic so the analyses of many protocols will still hold even if 257 this proposed construction is incorporated. 259 The proposed construction cannot provide any guarantees of security 260 if the CSPRNG state is cloned due to the virtual machine snapshots or 261 process forking (see [MAFS2017]). Thus tag1 SHOULD incorporate all 262 available information about the environment, such as process 263 attributes, virtual machine user information, etc. 265 7. Comparison to RFC 6979 267 The construction proposed herein has similarities with that of RFC 268 6979 [RFC6979]: both of them use private keys to seed a DRBG. 269 Section 3.3 of RFC 6979 recommends deterministically instantiating an 270 instance of the HMAC DRBG pseudorandom number generator, described in 271 [SP80090A] and Annex D of [X9.62], using the private key sk as the 272 entropy_input parameter and H(m) as the nonce. The construction 273 G'(n) provided herein is similar, with such difference that a key 274 derived from G(n) and H(Sig(sk, tag1)) is used as the entropy input 275 and tag2 is the nonce. 277 However, the semantics and the security properties obtained by using 278 these two constructions are different. The proposed construction 279 aims to improve CSPRNG usage such that certain trusted randomness 280 would remain even if the CSPRNG is completely broken. Using a 281 signature scheme which requires entropy sources according to RFC 6979 282 is intended for different purposes and does not assume possession of 283 any entropy source - even an unstable one. For example, if in a 284 certain system all private key operations are performed within an 285 HSM, then the differences will manifest as follows: the HMAC DRBG 286 construction of RFC 6979 may be implemented inside the HSM for the 287 sake of signature generation, while the proposed construction would 288 assume calling the signature implemented in the HSM. 290 8. Normative References 292 [DebianBug] 293 Yilek, Scott, et al, "When private keys are public - 294 Results from the 2008 Debian OpenSSL vulnerability", 295 https://pdfs.semanticscholar.org/fcf9/ 296 fe0946c20e936b507c023bbf89160cc995b9.pdf. 298 [DualEC] Bernstein, Daniel et al, "Dual EC - A standardized 299 backdoor", https://projectbullrun.org/dual- 300 ec/documents/dual-ec-20150731.pdf. 302 [MAFS2017] 303 McGrew, Anderson, Fluhrer, Shenefeil, "PRNG Failures and 304 TLS Vulnerabilities in the Wild", 305 https://rwc.iacr.org/2017/Slides/david.mcgrew.pptx. 307 [NAXOS] LaMacchia, Brian et al, "Stronger Security of 308 Authenticated Key Exchange", 309 https://www.microsoft.com/en-us/research/wp- 310 content/uploads/2016/02/strongake-submitted.pdf. 312 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 313 Key Derivation Function (HKDF)", RFC 5869, 314 DOI 10.17487/RFC5869, May 2010, 315 . 317 [RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature 318 Algorithm (DSA) and Elliptic Curve Digital Signature 319 Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August 320 2013, . 322 [RY2010] Ristenpart, Yilek, "When Good Randomness Goes Bad: Virtual 323 Machine Reset Vulnerabilities and Hedging Deployed 324 Cryptography", 325 https://rist.tech.cornell.edu/papers/sslhedge.pdf. 327 [SP80090A] 328 National Institute of Standards and Technology, 329 "Recommendation for Random Number Generation Using 330 Deterministic Random Bit Generators (Revised), NIST 331 Special Publication 800-90A", January 2012. 333 [X9.62] American National Standards Institute, "Public Key 334 Cryptography for the Financial Services Industry - The 335 Elliptic Curve Digital Signature Algorithm (ECDSA), ANSI 336 X9.62-2005", November 2005. 338 Authors' Addresses 340 Cas Cremers 341 University of Oxford 342 Wolfson Building, Parks Road 343 Oxford 344 England 346 Email: cas.cremers@cs.ox.ac.uk 348 Luke Garratt 349 University of Oxford 350 Wolfson Building, Parks Road 351 Oxford 352 England 354 Email: luke.garratt@cs.ox.ac.uk 356 Stanislav Smyshlyaev 357 CryptoPro 358 18, Suschevsky val 359 Moscow 360 Russian Federation 362 Email: svs@cryptopro.ru 364 Nick Sullivan 365 Cloudflare 366 101 Townsend St 367 San Francisco 368 United States of America 370 Email: nick@cloudflare.com 371 Christopher A. Wood 372 Apple Inc. 373 One Apple Park Way 374 Cupertino, California 95014 375 United States of America 377 Email: cawood@apple.com