idnits 2.17.1 draft-irtf-cfrg-randomness-improvements-02.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 97: '... SHOULD apply this technique when in...' RFC 2119 keyword, line 161: '...ess wrapper, and MUST NOT be used or e...' RFC 2119 keyword, line 162: '.... Moreover, Sig MUST be a determinist...' RFC 2119 keyword, line 170: '... Both tags SHOULD be generated such ...' RFC 2119 keyword, line 175: '...ons, tag strings SHOULD be constructed...' (2 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 15, 2018) is 2111 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC2104' is defined on line 277, 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: January 16, 2019 S. Smyshlyaev 6 CryptoPro 7 N. Sullivan 8 Cloudflare 9 C. Wood 10 Apple Inc. 11 July 15, 2018 13 Randomness Improvements for Security Protocols 14 draft-irtf-cfrg-randomness-improvements-02 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. This document 23 describes a way for security protocol participants to mix their long- 24 term private key into the entropy pool(s) from which random values 25 are derived. This augments and improves randomness from broken or 26 otherwise subverted CSPRNGs. 28 Status of This Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at https://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on January 16, 2019. 45 Copyright Notice 47 Copyright (c) 2018 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (https://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 Table of Contents 62 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 63 2. Randomness Wrapper . . . . . . . . . . . . . . . . . . . . . 3 64 3. Tag Generation . . . . . . . . . . . . . . . . . . . . . . . 4 65 4. Application to TLS . . . . . . . . . . . . . . . . . . . . . 4 66 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 5 67 6. Security Considerations . . . . . . . . . . . . . . . . . . . 5 68 7. Comparison to RFC 6979 . . . . . . . . . . . . . . . . . . . 6 69 8. Normative References . . . . . . . . . . . . . . . . . . . . 6 70 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 7 72 1. Introduction 74 Randomness is a crucial ingredient for TLS and related transport 75 security protocols. TLS in particular uses Random Number Generators 76 (RNGs) to generate several values: session IDs, ephemeral key shares, 77 and ClientHello and ServerHello random values. RNG failures such as 78 the Debian bug described in [DebianBug] can lead to insecure TLS 79 connections. RNGs may also be intentionally weakened to cause harm 80 [DualEC]. In such cases where RNGs are poorly implemented or 81 insecure, an adversary may be able to predict its output and recover 82 secret Diffie-Hellman key shares that protect the connection. 84 This document proposes an improvement to randomness generation in 85 security protocols inspired by the "NAXOS trick" [NAXOS]. 86 Specifically, instead of using raw entropy where needed, e.g., in 87 generating ephemeral key shares, a party's long-term private key is 88 mixed into the entropy pool. In the NAXOS key exchange protocol, raw 89 entropy output x is replaced by H(x, sk), where sk is the sender's 90 private key. Unfortunately, as private keys are often isolated in 91 HSMs, direct access to compute H(x, sk) is impossible. An alternate 92 yet functionally equivalent construction is needed. 94 The approach described herein replaces the NAXOS hash with a keyed 95 hash, or pseudorandom function (PRF), where the key is derived from 96 raw entropy output and a private key signature. Implementations 97 SHOULD apply this technique when indirect access to a private key is 98 available and CSPRNG randomness guarantees are dubious, or to provide 99 stronger guarantees about possible future issues with the randomness. 100 Roughly, the security properties provided by the proposed 101 construction are as follows: 103 1. If the CSPRNG works fine, that is, in a certain adversary model 104 the CSPRNG output is indistinguishable from a truly random 105 sequence, then the output of the proposed construction is also 106 indistinguishable from a truly random sequence in that adversary 107 model. 109 2. An adversary Adv with full control of a (potentially broken) 110 CSPRNG and able to observe all outputs of the proposed 111 construction, does not obtain any non-negligible advantage in 112 leaking the private key, modulo side channel attacks. 114 3. If the CSPRNG is broken or controlled by adversary Adv, the 115 output of the proposed construction remains indistinguishable 116 from random provided the private key remains unknown to Adv. 118 2. Randomness Wrapper 120 Let x be the raw entropy output of a CSPRNG. When properly 121 instantiated, x should be indistinguishable from a random string of 122 length |x|. However, as previously discussed, this is not always 123 true. To mitigate this problem, we propose an approach for wrapping 124 the CSPRNG output with a construction that artificially injects 125 randomness into a value that may be lacking entropy. 127 Let G(n) be an algorithm that generates n random bytes from raw 128 entropy, i.e., the output of a CSPRNG. Let Sig(sk, m) be a function 129 that computes a signature of message m given private key sk. Let H 130 be a cryptographic hash function that produces output of length M. 131 Let Extract be a randomness extraction function, e.g., HKDF-Extract 132 [RFC5869], which accepts a salt and input keying material (IKM) 133 parameter and produces a pseudorandom key of length L suitable for 134 cryptographic use. Let Expand(k, info, n) be a randomness extractor, 135 e.g., HKDF-Expand [RFC5869], that takes as input a pseudorandom key k 136 of length L, info string, and output length n, and produces output of 137 length n. Finally, let tag1 be a fixed, context-dependent string, 138 and let tag2 be a dynamically changing string. 140 The construction works as follows. Instead of using x = G(n) when 141 randomness is needed, use: 143 x = Expand(Extract(G(L), H(Sig(sk, tag1))), tag2, n) 145 Functionally, this expands n random bytes from a key derived from the 146 CSPRNG output and signature over a fixed string (tag1). See 147 Section 3 for details about how "tag1" and "tag2" should be generated 148 and used per invocation of the randomness wrapper. Expand() 149 generates a string that is computationally indistinguishable from a 150 truly random string of length n. Thus, the security of this 151 construction depends upon the secrecy of H(Sig(sk, tag1)) and G(n). 152 If the signature is leaked, then security reduces to the scenario 153 wherein randomness is expanded directly from G(n). 155 Also, in systems where signature computations are expensive, these 156 values may be precomputed in anticipation of future randomness 157 requests. This is possible since the construction depends solely 158 upon the CSPRNG output and private key. 160 Sig(sk, tag1) should only be computed once for the lifetime of the 161 randomness wrapper, and MUST NOT be used or exposed beyond its role 162 in this computation. Moreover, Sig MUST be a deterministic signature 163 function, e.g., deterministic ECDSA [RFC6979], or use an independent 164 (and completely reliable) entropy source, e.g., if Sig is implemented 165 in an HSM with its own internal trusted entropy source for signature 166 generation. 168 3. Tag Generation 170 Both tags SHOULD be generated such that they never collide with 171 another contender or owner of the private key. This can happen if, 172 for example, one HSM with a private key is used from several servers, 173 or if virtual machines are cloned. 175 To mitigate collisions, tag strings SHOULD be constructed as follows: 177 o tag1: Constant string bound to a specific device and protocol in 178 use. This allows caching of Sig(sk, tag1). Device specific 179 information may include, for example, a MAC address. See 180 Section 4 for example protocol information that can be used in the 181 context of TLS 1.3. 183 o tag2: Non-constant string that includes a timestamp or counter. 184 This ensures change over time even if randomness were to repeat. 186 4. Application to TLS 188 The PRF randomness wrapper can be applied to any protocol wherein a 189 party has a long-term private key and also generates randomness. 190 This is true of most TLS servers. Thus, to apply this construction 191 to TLS, one simply replaces the "private" PRNG, i.e., the PRNG that 192 generates private values, such as key shares, with: 194 HKDF-Expand(HKDF-Extract(G(L), H(Sig(sk, tag1))), tag2, n) 196 Moreover, we fix tag1 to protocol-specific information such as "TLS 197 1.3 Additional Entropy" for TLS 1.3. Older variants use similarly 198 constructed strings. 200 5. IANA Considerations 202 This document makes no request to IANA. 204 6. Security Considerations 206 A security analysis was performed by two authors of this document. 207 Generally speaking, security depends on keeping the private key 208 secret. If this secret is compromised, the scheme reduces to the 209 scenario wherein the PRF provides only an outer wrapper on usual 210 CSPRNG generation. 212 The main reason one might expect the signature to be exposed is via a 213 side-channel attack. It is therefore prudent when implementing this 214 construction to take into consideration the extra long-term key 215 operation if equipment is used in a hostile environment when such 216 considerations are necessary. 218 The signature in the construction as well as in the protocol itself 219 MUST NOT use randomness from entropy sources with dubious randomness 220 guarantees. Thus, the signature scheme MUST either use a reliable 221 entropy source (independent from the CSPRNG that is being improved 222 with the proposed construction) or be deterministic: if the 223 signatures are probabilistic and use weak entropy, our construction 224 does not help and the signatures are still vulnerable due to repeat 225 randomness attacks. In such an attack, the adversary might be able 226 to recover the long-term key used in the signature. 228 Under these conditions, applying this construction should never yield 229 worse security guarantees than not applying it assuming that applying 230 the PRF does not reduce entropy. We believe there is always merit in 231 analyzing protocols specifically. However, this construction is 232 generic so the analyses of many protocols will still hold even if 233 this proposed construction is incorporated. 235 7. Comparison to RFC 6979 237 The construction proposed herein has similarities with that of RFC 238 6979 [RFC6979]: both of them use private keys to seed a DRBG. 239 Section 3.3 of RFC 6979 recommends deterministically instantiating an 240 instance of the HMAC DRBG pseudorandom number generator, described in 241 [SP80090A] and Annex D of [X962], using the private key sk as the 242 entropy_input parameter and H(m) as the nonce. The construction 243 provided herein is similar, with such difference that a key derived 244 from G(x) and H(Sig(sk, tag1)) is used as the entropy input and tag2 245 is the nonce. 247 However, the semantics and the security properties obtained by using 248 these two constructions are different. The proposed construction 249 aims to improve CSPRNG usage such that certain trusted randomness 250 would remain even if the CSPRNG is completely broken. Using a 251 signature scheme which requires entropy sources according to RFC 6979 252 is intended for different purposes and does not assume possession of 253 any entropy source - even an unstable one. For example, if in a 254 certain system all private key operations are performed within an 255 HSM, then the differences will manifest as follows: the HMAC DRBG 256 construction of RFC 6979 may be implemented inside the HSM for the 257 sake of signature generation, while the proposed construction would 258 assume calling the signature implemented in the HSM. 260 8. Normative References 262 [DebianBug] 263 Yilek, Scott, et al, ., "When private keys are public - 264 Results from the 2008 Debian OpenSSL vulnerability", n.d., 265 . 268 [DualEC] Bernstein, Daniel et al, ., "Dual EC - A standardized back 269 door", n.d., . 272 [NAXOS] LaMacchia, Brian et al, ., "Stronger Security of 273 Authenticated Key Exchange", n.d., 274 . 277 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 278 Hashing for Message Authentication", RFC 2104, 279 DOI 10.17487/RFC2104, February 1997, 280 . 282 [RFC5869] Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand 283 Key Derivation Function (HKDF)", RFC 5869, 284 DOI 10.17487/RFC5869, May 2010, 285 . 287 [RFC6979] Pornin, T., "Deterministic Usage of the Digital Signature 288 Algorithm (DSA) and Elliptic Curve Digital Signature 289 Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August 290 2013, . 292 [SP80090A] 293 "Recommendation for Random Number Generation Using 294 Deterministic Random Bit Generators (Revised), NIST 295 Special Publication 800-90A, January 2012.", n.d., 296 . 298 [X9.62] American National Standards Institute, ., "Public Key 299 Cryptography for the Financial Services Industry -- The 300 Elliptic Curve Digital Signature Algorithm (ECDSA). ANSI 301 X9.62-2005, November 2005.", n.d.. 303 [X962] "Public Key Cryptography for the Financial Services 304 Industry -- The Elliptic Curve Digital Signature Algorithm 305 (ECDSA), ANSI X9.62-2005, November 2005.", n.d., . 308 Authors' Addresses 310 Cas Cremers 311 University of Oxford 312 Wolfson Building, Parks Road 313 Oxford 314 England 316 Email: cas.cremers@cs.ox.ac.uk 318 Luke Garratt 319 University of Oxford 320 Wolfson Building, Parks Road 321 Oxford 322 England 324 Email: luke.garratt@cs.ox.ac.uk 325 Stanislav Smyshlyaev 326 CryptoPro 327 18, Suschevsky val 328 Moscow 329 Russian Federation 331 Email: svs@cryptopro.ru 333 Nick Sullivan 334 Cloudflare 335 101 Townsend St 336 San Francisco 337 United States of America 339 Email: nick@cloudflare.com 341 Christopher A. Wood 342 Apple Inc. 343 One Apple Park Way 344 Cupertino, California 95014 345 United States of America 347 Email: cawood@apple.com