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