RFC 8937

Randomness Improvements for Security Protocols

📅 published October 2020, from ietf

RFC 8937: Randomness Improvements for Security Protocols 🎀

okay bestie, this one is RFC 8937 and it's all about randomness 🎲✨ It was written by C. Cremers (CISPA), L. Garratt (Cisco Meraki), S. Smyshlyaev (CryptoPro), N. Sullivan (no affiliation listed in this header), and C. Wood (Cloudflare). It came out of the Internet Research Task Force (IRTF) in October 2020 and is marked Informational, so it's not a standards-track spec 🙈 The ISSN is 2070-1721. It doesn't obsolete or update any other RFC, since none are listed in the header.

Abstract 🌸

Okay so randomness is literally the secret sauce for TLS and other security protocols 🔐 If a "cryptographically secure" pseudorandom number generator (CSPRNG) is weak or predictable, bad actors can totally abuse it for sketchy stuff 💀 And the starting entropy source that seeds the CSPRNG can be weak or broken too, which can cause big systemic problems. This document shows how security protocol implementations can boost their CSPRNGs using long-term private keys. The result is better randomness, even when the CSPRNG is broken or has been tampered with 💅

This document is a product of the Crypto Forum Research Group (CFRG) in the IRTF.

Status of This Memo 📝

This document is not an Internet Standards Track specification. It's published for informational purposes, so no pressure 💖

It's a product of the Internet Research Task Force (IRTF), which shares results from Internet-related research and development. Those results might not be ready for deployment, so keep that in mind 👀 This RFC reflects the consensus of the Crypto Forum Research Group of the IRTF. Anything approved for publication by the IRSG is not a candidate for any level of Internet Standard. See Section 2 of RFC 7841 for the details.

For the current status, any errata, and how to send feedback, check https://www.rfc-editor.org/info/rfc8937.

Copyright (c) 2020 IETF Trust and the persons identified as the document authors. All rights reserved.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info), as they stood on the publication date. Please actually read those, because they spell out your rights and restrictions for this document 🙏

Table of Contents 📋

1.  Introduction
2.  Conventions Used in This Document
3.  Randomness Wrapper
4.  Tag Generation
5.  Application to TLS
6.  Implementation Guidance
7.  IANA Considerations
8.  Security Considerations
9.  Comparison to RFC 6979
10. References
  10.1.  Normative References
  10.2.  Informative References
Acknowledgements
Authors' Addresses

1. Introduction ✨

Okay, so secure, properly implemented random number generators (aka CSPRNGs) should give output that looks indistinguishable from a random string of the same length 🫶 CSPRNGs are the building blocks for TLS and related transport security protocols. TLS uses them to make a bunch of values, like ephemeral key shares and the ClientHello and ServerHello random values 🎀 When CSPRNGs fail, things get messy. The Debian bug in [DebianBug] is a perfect example, and it can lead to insecure TLS connections 😭 CSPRNGs can also be intentionally weakened to cause harm [DualEC]. If the initial entropy sources are weak or broken, every CSPRNG seeded from them is insecure too. When CSPRNGs are poorly built or insecure, an adversary, Adv, might be able to tell its output apart from a random string, or even predict it and recover the secret key material protecting the connection. Yikes 💀

This document suggests a way to improve randomness in security protocols, inspired by the "NAXOS trick" [NAXOS] 🦋 Instead of using raw randomness wherever it's needed (like when generating ephemeral key shares), you mix a function of the party's long-term private key into the entropy pool. In the NAXOS key exchange protocol, the raw random value x gets replaced by H(x, sk), where sk is the sender's private key. The catch is that private keys often live inside Hardware Security Modules (HSMs), so you can't directly compute H(x, sk) 🙃 Some HSM APIs also only let you sign messages with a private key and offer nothing else with that key. So we need an alternate construction that works the same way functionally 🔄

The approach here swaps the NAXOS hash for a keyed hash, or pseudorandom function (PRF), where the key comes from a raw random value and a private key signature 🔑 Implementations SHOULD use this technique a) when indirect access to a private key is available and CSPRNG randomness guarantees are dubious, or b) to get stronger guarantees about possible future randomness issues 💜 At a high level, the proposed construction has these security properties:

  1. If the CSPRNG works fine (meaning, in a certain adversary model, its output is indistinguishable from a truly random sequence), then the output of the proposed construction is also indistinguishable from a truly random sequence in that same adversary model 🌈
  2. Adv has full control of a (potentially broken) CSPRNG and can observe every output of the proposed construction, but still doesn't get any non-negligible advantage in leaking the private key (assuming there are no side channel attacks) 🕵️‍♀️
  3. If the CSPRNG is broken or controlled by Adv, the output of the proposed construction stays indistinguishable from random, as long as the private key stays unknown to Adv 🛡️

This document represents the consensus of the Crypto Forum Research Group (CFRG) 🤝

2. Conventions Used in This Document 📖

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 📚

3. Randomness Wrapper 🎁

A properly set up CSPRNG should give output that's indistinguishable from a random string of the same length 🙂 But as we already talked about, that isn't always the case. To work around this, we propose wrapping the CSPRNG output in a construction that mixes secret data into a value that might be missing randomness 🌸

Let G(n) be an algorithm that makes n random bytes, which is basically the output of a CSPRNG. Then we define an augmented CSPRNG, G', like this. Let Sig(sk, m) be a function that computes a signature over message m with private key sk. Let H be a cryptographic hash function whose output is M bytes long. Let Extract(salt, IKM) be a randomness extraction function, such as HKDF-Extract [RFC5869]. It takes a salt and input keying material (IKM) and produces a pseudorandom key of L bytes that's ready for cryptographic use. It has to be a secure PRF (with the salt acting as a key of length M) and it has to preserve the uniformity of the IKM. For the details, see [SecAnalysis]. L SHOULD be a fixed length. Let Expand(k, info, n) be a variable-length output PRF, such as HKDF-Expand [RFC5869]. It takes a pseudorandom key k of L bytes, an info string, and an output length n, and produces n bytes of output 🧁 Last, let tag1 be a fixed, context-dependent string, and let tag2 be a dynamically changing string (like a counter) of L' bytes. We require that L >= n - L' for each value of tag2 ✨

Here's how the construction goes. Instead of using G(n) whenever randomness is needed, use G'(n), where:

G'(n) = Expand(Extract(H(Sig(sk, tag1)), G(L)), tag2, n)

In plain terms, this stretches n random bytes out of a key that's derived from the CSPRNG output plus a signature over a fixed string (tag1) 🪄 See Section 4 for details on how tag1 and tag2 should be generated and used for each invocation of the randomness wrapper. Expand() gives a string that's computationally indistinguishable from a truly random string of n bytes. So the security of this construction depends on keeping H(Sig(sk, tag1)) and G(L) secret. If the signature leaks, then the security of G'(n) drops down to the case where randomness is expanded straight from G(L) 😬

If the private key sk is stored and used inside an HSM, the signature calculation happens inside the HSM too. Everything else (the hash function, the Extract function, and the Expand function) can run either inside or outside the HSM 🏠

Sig(sk, tag1) only needs to be computed once for the lifetime of the randomness wrapper. It MUST NOT be used or exposed beyond its role in this computation 🔒 More guidance on tag1 comes in the next section. Sig MUST be a deterministic signature function, such as deterministic Elliptic Curve Digital Signature Algorithm (ECDSA) [RFC6979]. Or it can use an independent, completely reliable entropy source, for example if Sig runs in an HSM that has its own trusted entropy source for generating signatures 🔐

Since Sig(sk, tag1) can be cached, using G'(n) instead of G(n) usually costs next to nothing compared to the crypto operations in protocols like TLS. The relatively cheap HKDF-Extract and HKDF-Expand calls are what dominate when you compare G' to G 💸 A description of the performance experiments and their results can be found in [SecAnalysis].

And the values of G'(n) can be precomputed and pooled too 🧺 That works because the construction depends only on the CSPRNG output and the private key 💖

4. Tag Generation ✨

Okay bestie, both tags MUST be generated so they never collide with another contender or owner of the private key 🔐. This can happen if, for example, one HSM with a private key is used from several servers 🖥️ or if virtual machines are cloned 👯. Yikes 😭

The RECOMMENDED tag construction procedure goes like this 💅:

tag1: This is a constant string bound to a specific device and the protocol in use 🎀. It lets you cache Sig(sk, tag1). Device-specific info can include stuff like a Media Access Control (MAC) address 🌐. To keep things secure when CSPRNGs run in virtual environments, it is RECOMMENDED to pack in all the available info that's specific to the process, so every tag1 value is unique across different VM instances. That includes VMs that got cloned or restored from snapshots 📸. This matters because of CSPRNG state cloning, which is a real problem (see [RY2010]) 😬. Section 5 has example protocol info you can use with TLS 1.3 🦋. And if sk could be used for other purposes, picking a tag1 that's different from the forms those other uses allow means the signature doesn't get exposed 🔒.

tag2: This is a nonce, meaning a value that's unique for every use of the same combination of G(L), tag1, and sk values 🌸. You can implement tag2 with a counter or a timer 🕰️, as long as the timer is guaranteed to be different for each invocation of G'(n) ⭐.

5. Application to TLS 🔐

The PRF randomness wrapper works with any protocol where a party has a long-term private key and also generates randomness 🧚. That describes most TLS servers, so to apply this construction to TLS, you just swap out the "private" CSPRNG G(n) (the one that generates private values like key shares 🔑) with:

G'(n) = HKDF-Expand(HKDF-Extract(H(Sig(sk, tag1)), G(L)), tag2, n)

6. Implementation Guidance 💡

Quick reminder: the wrapper from Section 3 requires L >= n - L', where L is the Extract output length and n is the amount of randomness you want 🍓. Some applications may require n to go past this bound 🙈. No worries though, because wrapper implementations can handle that by calling G' multiple times and concatenating the results 🧩.

7. IANA Considerations 🎉

This document has no IANA actions. Easy peasy 💖

8. Security Considerations 💀

Okay, this section is serious, so listen up 👀. A security analysis was done in [SecAnalysis]. Generally speaking, the following security theorem has been proven: if Adv learns only one of the signature or the usual randomness generated on one particular instance, then, under the security assumptions on our primitives, the wrapper construction should output randomness that is indistinguishable from a random string 🤯✨.

The main reason you'd expect the signature to get exposed is a side-channel attack 😱. So when you implement this construction, it's prudent to think about the extra long-term key operation, especially if your equipment is in a hostile environment where those considerations are necessary 🚨. That's why it's recommended to generate a key specifically for this construction and not use it any other way 🗝️.

The signature in the construction, as well as in the protocol itself, MUST NOT use randomness from entropy sources with dubious security guarantees 🙅‍♀️. So the signature scheme MUST either use a reliable entropy source (independent from the CSPRNG that's being improved with this construction) or be deterministic 🫠. If the signatures are probabilistic and use weak entropy, this construction doesn't help, and the signatures are still vulnerable to repeat randomness attacks 💔. In that kind of attack, Adv might be able to recover the long-term key used in the signature 😭.

Under these conditions, applying this construction should never yield worse security guarantees than not applying it, assuming that applying the PRF does not reduce entropy 👑. We believe there's always merit in analyzing protocols specifically 🔍. However, this construction is generic, so the analyses of many protocols will still hold even if this construction gets incorporated 🫶.

Now the big warning 🚨: the proposed construction cannot provide any security guarantees if the CSPRNG state gets cloned due to virtual machine snapshots or process forking (see [MAFS2017]) 🙀. It is RECOMMENDED that tag1 incorporate all available information about the environment, such as process attributes, virtual machine user information, and so on 🧾.

9. Comparison to RFC 6979 🆚

This construction has similarities with the one in [RFC6979] 👯‍♀️. Both of them use private keys to seed a deterministic random number generator 🎲. Section 3.3 of [RFC6979] recommends deterministically instantiating an instance of the HMAC_DRBG pseudorandom number generator, which is described in [SP80090A] and Annex D of [X962], using the private key sk as the entropy_input parameter and H(m) as the nonce 🔁. The construction G'(n) given here is similar, with one difference: a key derived from G(n) and H(Sig(sk, tag1)) is used as the entropy input, and tag2 is the nonce 🌈.

That said, the semantics and security properties you get from these two constructions are different 💅. The proposed construction aims to improve CSPRNG usage so that certain trusted randomness stays safe even if the CSPRNG is completely broken 🛡️. Using a signature scheme that requires entropy sources according to [RFC6979] is meant for different purposes, and it doesn't assume you have any entropy source, not even an unstable one 🌪️. For example, if all private key operations in a system happen inside an HSM, the differences look like this 🔐: the HMAC_DRBG construction described in [RFC6979] may be implemented inside the HSM for signature generation, while the proposed construction would assume calling the signature implemented in the HSM 📞.

10. References 📚

10.1. Normative References

[RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
           Requirement Levels", BCP 14, RFC 2119,
           DOI 10.17487/RFC2119, March 1997,
           <https://www.rfc-editor.org/info/rfc2119>.

[RFC5869]  Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand
           Key Derivation Function (HKDF)", RFC 5869,
           DOI 10.17487/RFC5869, May 2010,
           <https://www.rfc-editor.org/info/rfc5869>.

[RFC6979]  Pornin, T., "Deterministic Usage of the Digital Signature
           Algorithm (DSA) and Elliptic Curve Digital Signature
           Algorithm (ECDSA)", RFC 6979, DOI 10.17487/RFC6979, August
           2013, <https://www.rfc-editor.org/info/rfc6979>.

[RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
           2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
           May 2017, <https://www.rfc-editor.org/info/rfc8174>.

10.2. Informative References

[DebianBug]
           Yilek, S., Rescorla, E., Shacham, H., Enright, B., and S.
           Savage, "When private keys are public: results from the
           2008 Debian OpenSSL vulnerability", ICM '09,
           DOI 10.1145/1644893.1644896, November 2009,
           <https://pdfs.semanticscholar.org/fcf9/fe0946c20e936b507c023bbf89160cc995b9.pdf>.

[DualEC]   Bernstein, D., Lange, T., and R. Niederhagen, "Dual EC: A
           Standardized Back Door", DOI 10.1007/978-3-662-49301-4_17,
           March 2016, <https://projectbullrun.org/dual-ec/documents/dual-ec-20150731.pdf>.

[MAFS2017] McGrew, D., Anderson, B., Fluhrer, S., and C. Schenefiel,
           "PRNG Failures and TLS Vulnerabilities in the Wild",
           January 2017,
           <https://rwc.iacr.org/2017/Slides/david.mcgrew.pptx>.

[NAXOS]    LaMacchia, B., Lauter, K., and A. Mityagin, "Stronger
           Security of Authenticated Key Exchange",
           DOI 10.1007/978-3-540-75670-5_1, November 2007,
           <https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/strongake-submitted.pdf>.

[RY2010]   Ristenpart, T. and S. Yilek, "When Good Randomness Goes
           Bad: Virtual Machine Reset Vulnerabilities and Hedging
           Deployed Cryptography", January 2010,
           <https://rist.tech.cornell.edu/papers/sslhedge.pdf>.

[SecAnalysis]
           Akhmetzyanova, L., Cremers, C., Garratt, L., Smyshlyaev,
           S., and N. Sullivan, "Limiting the impact of unreliable
           randomness in deployed security protocols",
           DOI 10.1109/CSF49147.2020.00027, IEEE 33rd Computer
           Security Foundations Symposium (CSF), Boston, MA, USA, pp.
           385-393, 2020,
           <https://doi.org/10.1109/CSF49147.2020.00027>.

[SP80090A] National Institute of Standards and Technology,
           "Recommendation for Random Number Generation Using
           Deterministic Random Bit Generators, Special Publication
           800-90A Revision 1", DOI 10.6028/NIST.SP.800-90Ar1, June
           2015, <https://doi.org/10.6028/NIST.SP.800-90Ar1>.

[X962]     American National Standard for Financial Services (ANSI),
           "Public Key Cryptography for the Financial Services
           Industry, The Elliptic Curve Digital Signature Algorithm
           (ECDSA)", ANSI X9.62, November 2005,
           <https://www.techstreet.com/standards/x9-x9-62-2005?product_id=1327225>.

Acknowledgements 🫶

We thank Liliya Akhmetzyanova for her deep involvement in the security assessment in [SecAnalysis] 👏. We also thank John Mattsson, Martin Thomson, and Rich Salz for their careful readings and useful comments 💜.

Authors' Addresses 💌

Cas Cremers
CISPA
Saarland Informatics Campus
Saarbruecken
Germany

Email: cremers@cispa.saarland


Luke Garratt
Cisco Meraki
500 Terry A Francois Blvd
San Francisco,
United States of America

Email: lgarratt@cisco.com


Stanislav Smyshlyaev
CryptoPro
18, Suschevsky val
Moscow
Russian Federation

Email: svs@cryptopro.ru


Nick Sullivan
Cloudflare
101 Townsend St
San Francisco,
United States of America

Email: nick@cloudflare.com


Christopher A. Wood
Cloudflare
101 Townsend St
San Francisco,
United States of America

Email: caw@heapingbits.net
📦 where this page comes from