<?xml version='1.0' encoding='utf-8'?>
<!-- generated by https://github.com/cabo/kramdown-rfc2629 version 1.3.3 -->
<!DOCTYPE rfc SYSTEM "rfc2629-xhtml.ent">
<rfc xmlns:xi="http://www.w3.org/2001/XInclude" ipr="trust200902"
docName="draft-irtf-cfrg-randomness-improvements-14" number="8937"
obsoletes="" updates="" submissionType="IRTF" category="info"
consensus="true" xml:lang="en" tocInclude="true" sortRefs="true"
symRefs="true" version="3">
<!-- xml2rfc v2v3 conversion 2.42.0 -->
<front>
<title abbrev="Randomness Improvements">Randomness Improvements for Security Protocols</title>
<seriesInfo name="RFC" value="8937"/>
<author initials="C." surname="Cremers" fullname="Cas Cremers">
<organization>CISPA</organization>
<address>
<postal>
<street>Saarland Informatics Campus</street>
<city>Saarbruecken</city>
<country>Germany</country>
</postal>
<email>cremers@cispa.saarland</email>
</address>
</author>
<author initials="L." surname="Garratt" fullname="Luke Garratt">
<organization>Cisco Meraki</organization>
<address>
<postal>
<street>500 Terry A Francois Blvd</street>
<city>San Francisco</city>
<country>United States of America</country>
</postal>
<email>lgarratt@cisco.com</email>
</address>
</author>
<author initials="S." surname="Smyshlyaev" fullname="Stanislav Smyshlyaev">
<organization>CryptoPro</organization>
<address>
<postal>
<street>18, Suschevsky val</street>
<city>Moscow</city>
<country>Russian Federation</country>
</postal>
<email>svs@cryptopro.ru</email>
</address>
</author>
<author initials="N." surname="Sullivan" fullname="Nick Sullivan">
<organization>Cloudflare</organization>
<address>
<postal>
<street>101 Townsend St</street>
<city>San Francisco</city>
<country>United States of America</country>
</postal>
<email>nick@cloudflare.com</email>
</address>
</author>
<author initials="C." surname="Wood" fullname="Christopher A. Wood">
<organization>Cloudflare</organization>
<address>
<postal>
<street>101 Townsend St</street>
<city>San Francisco</city>
<country>United States of America</country>
</postal>
<email>caw@heapingbits.net</email>
</address>
</author>
<date month="October" year="2020" />
<workgroup>Crypto Forum</workgroup>
<keyword>Security</keyword>
<keyword>Cryptography</keyword>
<keyword>TLS</keyword>
<abstract>
<t>Randomness is a crucial ingredient for Transport Layer Security (TLS)
and related security protocols.
Weak or predictable
"cryptographically secure" pseudorandom number generators (CSPRNGs) can
be abused or exploited for malicious purposes. An initial entropy source
that seeds a CSPRNG might be weak or broken as well, which can also lead
to critical and systemic security problems. This document describes a
way for security protocol implementations to augment their CSPRNGs using
long-term private keys. This improves randomness from broken or
otherwise subverted CSPRNGs.</t>
<t>This document is a product of the Crypto Forum Research Group (CFRG) in the IRTF.</t>
</abstract>
</front>
<middle>
<section anchor="introduction" numbered="true" toc="default">
<name>Introduction</name>
<t>Secure and properly implemented random number generators, or
"cryptographically secure" pseudorandom number generators (CSPRNGs),
should produce output that is indistinguishable from a random string of
the same length. CSPRNGs are critical building blocks for TLS and
related transport security protocols. TLS in particular uses CSPRNGs to
generate several values, such as ephemeral key shares and ClientHello
and ServerHello random values. CSPRNG failures, such as the Debian bug
described in <xref target="DebianBug" format="default"/>, can lead to
insecure TLS connections. CSPRNGs may also be intentionally weakened to
cause harm <xref target="DualEC" format="default"/>. Initial entropy
sources can also be weak or broken, and that would lead to insecurity of
all CSPRNG instances seeded with them. In such cases where CSPRNGs are
poorly implemented or insecure, an adversary, Adv, may be able to
distinguish its output from a random string or predict its output and
recover secret key material used to protect the connection.</t>
<t>This document proposes an improvement to randomness generation in
security protocols inspired by the "NAXOS trick" <xref target="NAXOS"
format="default"/>. Specifically, instead of using raw randomness where
needed, e.g., in generating ephemeral key shares, a function of a
party's long-term private key is mixed into the entropy pool. In the
NAXOS key exchange protocol, raw random value x is replaced by H(x, sk),
where sk is the sender's private key. Unfortunately, as private keys are
often isolated in Hardware Security Modules (HSMs), direct access to
compute H(x, sk) is impossible. Moreover, some HSM APIs may only offer
the option to sign messages using a private key, yet offer no other
operations involving that key. An alternate, yet functionally equivalent
construction, is needed.</t>
<t>The approach described herein replaces the NAXOS hash with a keyed
hash, or pseudorandom function (PRF), where the key is derived from a
raw random value and a private key signature.
Implementations
<bcp14>SHOULD</bcp14> apply this technique a) when indirect access to a
private key is available and CSPRNG randomness guarantees are dubious
or b) to provide stronger guarantees about possible future issues with the
randomness. Roughly, the security properties provided by the proposed
construction are as follows:</t>
<ol spacing="normal" type="1">
<li>If the CSPRNG works fine (that is, in a certain adversary model,
the CSPRNG 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 adversary model.</li>
<li>Adv with full control of a (potentially broken) CSPRNG and ability
to observe all outputs of the proposed construction does not obtain
any non-negligible advantage in leaking the private key (in the
absence of side channel attacks).</li>
<li>If the CSPRNG is broken or controlled by Adv, the output of the
proposed construction remains indistinguishable from random, provided that
the private key remains unknown to Adv.</li>
</ol>
<t>This document represents the consensus of the Crypto Forum Research Group (CFRG).</t>
</section>
<section anchor="conventions-used-in-this-document" numbered="true" toc="default">
<name>Conventions Used in This Document</name>
<t>
The key words "<bcp14>MUST</bcp14>", "<bcp14>MUST NOT</bcp14>",
"<bcp14>REQUIRED</bcp14>", "<bcp14>SHALL</bcp14>", "<bcp14>SHALL
NOT</bcp14>", "<bcp14>SHOULD</bcp14>", "<bcp14>SHOULD NOT</bcp14>",
"<bcp14>RECOMMENDED</bcp14>", "<bcp14>NOT RECOMMENDED</bcp14>",
"<bcp14>MAY</bcp14>", and "<bcp14>OPTIONAL</bcp14>" in this document are to be interpreted as
described in BCP 14 <xref target="RFC2119"/> <xref target="RFC8174"/>
when, and only when, they appear in all capitals, as shown here.
</t>
</section>
<section anchor="wrapper" numbered="true" toc="default">
<name>Randomness Wrapper</name>
<t>The output of a properly instantiated CSPRNG should be
indistinguishable from a random string of the same length. However, as
previously discussed, this is not always true. To mitigate this problem,
we propose an approach for wrapping the CSPRNG output with a
construction that mixes secret data into a value that may be lacking
randomness.</t>
<t>Let G(n) be an algorithm that generates n random bytes, i.e., the
output of a CSPRNG. Define an augmented CSPRNG G' as follows. Let
Sig(sk, m) be a function that computes a signature of message m given
private key sk. Let H be a cryptographic hash function that produces
output of length M. Let Extract(salt, IKM) be a randomness extraction
function, e.g., HKDF-Extract <xref target="RFC5869" format="default"/>,
which accepts a salt and input keying material (IKM) parameter and
produces a pseudorandom key of L bytes suitable for cryptographic
use. It must be a secure PRF (for salt as a key of length M) and
preserve uniformness of IKM (for details, see <xref target="SecAnalysis"
format="default"/>). L <bcp14>SHOULD</bcp14> be a fixed length. Let
Expand(k, info, n) be a variable-length output PRF, e.g., HKDF-Expand
<xref target="RFC5869" format="default"/>, that takes as input a
pseudorandom key k of L bytes, info string, and output length n, and
produces output of n bytes. Finally, let tag1 be a fixed,
context-dependent string, and let tag2 be a dynamically changing string
(e.g., a counter) of L' bytes. We require that L >= n - L' for each
value of tag2.</t>
<t>The construction works as follows. Instead of using G(n) when
randomness is needed, use G'(n), where</t>
<artwork name="" type="" align="left" alt="">
G'(n) = Expand(Extract(H(Sig(sk, tag1)), G(L)), tag2, n)
</artwork>
<t>Functionally, this expands n random bytes from a key derived from the
CSPRNG output and signature over a fixed string (tag1). See <xref
target="tag-gen" format="default"/> for details about how "tag1" and
"tag2" should be generated and used per invocation of the randomness
wrapper. Expand() generates a string that is computationally
indistinguishable from a truly random string of n bytes. Thus, the
security of this construction depends upon the secrecy of H(Sig(sk,
tag1)) and G(L). If the signature is leaked, then security of G'(n)
reduces to the scenario wherein randomness is expanded directly from
G(L).</t>
<t>If a private key sk is stored and used inside an HSM, then the
signature calculation is implemented inside it, while all other
operations (including calculation of a hash function, Extract function, and Expand
function) can be implemented either inside or outside the HSM.</t>
<t>Sig(sk, tag1) need only be computed once for the lifetime of the
randomness wrapper and <bcp14>MUST NOT</bcp14> be used or exposed
beyond its role in this computation. Additional recommendations for tag1
are given in the following section.</t>
<t>Sig <bcp14>MUST</bcp14> be a deterministic signature function, e.g.,
deterministic Elliptic Curve Digital Signature Algorithm (ECDSA) <xref
target="RFC6979" format="default"/>, or use an
independent (and completely reliable) entropy source, e.g., if Sig is
implemented in an HSM with its own internal trusted entropy source for
signature generation.</t>
<t>Because Sig(sk, tag1) can be cached, the relative cost of using G'(n)
instead of G(n) tends to be negligible with respect to cryptographic
operations in protocols such as TLS (the relatively inexpensive
computational cost of HKDF-Extract and HKDF-Expand dominates when
comparing G' to G). A description of the performance experiments and
their results can be found in <xref target="SecAnalysis"
format="default"/>.</t>
<t>Moreover, the values of G'(n) may be precomputed and pooled. This is
possible since the construction depends solely upon the CSPRNG output
and private key.</t>
</section>
<section anchor="tag-gen" numbered="true" toc="default">
<name>Tag Generation</name>
<t>Both tags <bcp14>MUST</bcp14> be generated such that 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.</t>
<t>The <bcp14>RECOMMENDED</bcp14> tag construction procedure is as follows:</t>
<dl newline="false" spacing="normal" indent="7">
<dt>tag1:</dt>
<dd>Constant string bound to a specific device and protocol in
use. This allows caching of Sig(sk, tag1). Device-specific information
may include, for example, a Media Access Control (MAC) address. To
provide security in the
cases of usage of CSPRNGs in virtual environments, it is
<bcp14>RECOMMENDED</bcp14> to incorporate all available information
specific to the process that would ensure the uniqueness of each tag1
value among different instances of virtual machines (including ones
that were cloned or recovered from snapshots). This is needed to
address the problem of CSPRNG state cloning (see <xref target="RY2010"
format="default"/>). See <xref target="sec_tls13" format="default"/>
for example protocol information that can be used in the context of
TLS 1.3. If sk could be used for other purposes, then selecting a
value for tag1 that is different than the form allowed by those other
uses ensures that the signature is not exposed.</dd>
<dt>tag2:</dt>
<dd>A nonce, that is, a value that is unique for each use of the same
combination of G(L), tag1, and sk values. The tag2 value can be
implemented using a counter or a timer, provided that the timer is
guaranteed to be different for each invocation of G'(n).</dd>
</dl>
</section>
<section anchor="sec_tls13" numbered="true" toc="default">
<name>Application to TLS</name>
<t>The PRF randomness wrapper can be applied to any protocol wherein a
party has a long-term private key and also generates randomness. This is
true of most TLS servers. Thus, to apply this construction to TLS, one
simply replaces the "private" CSPRNG G(n), i.e., the CSPRNG that
generates private values, such as key shares, with</t>
<artwork name="" type="" align="left" alt="">
G'(n) = HKDF-Expand(HKDF-Extract(H(Sig(sk, tag1)), G(L)), tag2, n)
</artwork>
</section>
<section anchor="implementation-guidance" numbered="true" toc="default">
<name>Implementation Guidance</name>
<t>Recall that the wrapper defined in <xref target="wrapper"
format="default"/> requires L >= n - L', where L is the Extract
output length and n is the desired amount of randomness. Some
applications may require n to exceed this bound. Wrapper implementations
can support this use case by invoking G' multiple times and
concatenating the results.</t>
</section>
<section anchor="iana-considerations" numbered="true" toc="default">
<name>IANA Considerations</name>
<t>This document has no IANA actions.</t>
</section>
<section anchor="security-considerations" numbered="true" toc="default">
<name>Security Considerations</name>
<t>A security analysis was performed in <xref target="SecAnalysis"
format="default"/>. 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.</t>
<t>The main reason one might expect the signature to be exposed is via a
side-channel attack. It is therefore prudent when implementing this
construction to take into consideration the extra long-term key
operation if equipment is used in a hostile environment when such
considerations are necessary. Hence, it is recommended to generate a key
specifically for the purposes of the defined construction and not to use it another way.</t>
<t>The signature in the construction, as well as in the protocol itself,
<bcp14>MUST NOT</bcp14> use randomness from entropy sources with dubious
security guarantees. Thus, the signature scheme <bcp14>MUST</bcp14>
either use a reliable entropy source (independent from the CSPRNG that
is being improved with the proposed construction) or be deterministic;
if the signatures are probabilistic and use weak entropy, our
construction does not help, and the signatures are still vulnerable due
to repeat randomness attacks. In such an attack, Adv might be able to
recover the long-term key used in the signature.</t>
<t>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 is always merit in
analyzing protocols specifically. However, this construction is generic
so the analyses of many protocols will still hold even if this proposed
construction is incorporated.</t>
<t>The proposed construction cannot provide any guarantees of security
if the CSPRNG state is cloned due to the virtual machine snapshots or
process forking (see <xref target="MAFS2017" format="default"/>). It is
<bcp14>RECOMMENDED</bcp14> that tag1 incorporate all available
information about the environment, such as process attributes, virtual
machine user information, etc.</t>
</section>
<section anchor="comparison-to-rfc-6979" numbered="true" toc="default">
<name>Comparison to RFC 6979</name>
<t>The construction proposed herein has similarities with that of
<xref target="RFC6979" format="default"/>; both of them use private
keys to seed a deterministic random number generator. <xref
target="RFC6979" sectionFormat="of" section="3.3"/> recommends
deterministically instantiating an instance of the HMAC_DRBG
pseudorandom number generator, described in <xref target="SP80090A"
format="default"/> and Annex D of <xref target="X962"
format="default"/>, using the private key sk as the entropy_input
parameter and H(m) as the nonce. The construction G'(n) provided herein
is similar, with such difference that a key derived from G(n) and
H(Sig(sk, tag1)) is used as the entropy input and tag2 is the nonce.</t>
<t>However, the semantics and the security properties obtained by using
these two constructions are different. The proposed construction aims to
improve CSPRNG usage such that certain trusted randomness would remain
even if the CSPRNG is completely broken. Using a signature scheme that
requires entropy sources according to <xref target="RFC6979"
format="default"/> is intended for different purposes and does not
assume possession of any entropy source -- even an unstable one. For
example, if in a certain system all private key operations are performed
within an HSM, then the differences will manifest as follows: the
HMAC_DRBG construction described in <xref target="RFC6979" format="default"/> may
be implemented inside the HSM for the sake of signature generation,
while the proposed construction would assume calling the signature
implemented in the HSM.</t>
</section>
</middle>
<back>
<references>
<name>References</name>
<references>
<name>Normative References</name>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.2119.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.5869.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.6979.xml"/>
<xi:include href="https://xml2rfc.ietf.org/public/rfc/bibxml/reference.RFC.8174.xml"/>
</references>
<references>
<name>Informative References</name>
<reference anchor="DebianBug" target="https://pdfs.semanticscholar.org/fcf9/fe0946c20e936b507c023bbf89160cc995b9.pdf">
<front>
<title>When private keys are public: results from the 2008 Debian
OpenSSL vulnerability</title>
<author initials="S" surname="Yilek" fullname="Scott Yilek">
<organization/>
</author>
<author initials="E" surname="Rescorla" fullname="Eric Rescorla">
<organization/>
</author>
<author initials="H" surname="Shacham" fullname="Hovav Shacham">
<organization/>
</author>
<author initials="B" surname="Enright" fullname="Brandon Enright">
<organization/>
</author>
<author initials="S" surname="Savage" fullname="Stefan Savage">
<organization/>
</author>
<date month="November" year="2009"/>
</front>
<seriesInfo name="DOI" value="10.1145/1644893.1644896"/>
<refcontent>ICM '09</refcontent>
</reference>
<reference anchor="DualEC" target="https://projectbullrun.org/dual-ec/documents/dual-ec-20150731.pdf">
<front>
<title>Dual EC: A Standardized Back Door</title>
<author initials="D" surname="Bernstein" fullname="Daniel J. Bernstein">
<organization/>
</author>
<author initials="T" surname="Lange" fullname="Tanja Lange">
<organization/>
</author>
<author initials="R" surname="Niederhagen" fullname="Ruben Niederhagen">
<organization/>
</author>
<date month="March" year="2016"/>
</front>
<seriesInfo name="DOI" value="10.1007/978-3-662-49301-4_17"/>
</reference>
<reference anchor="MAFS2017" target="https://rwc.iacr.org/2017/Slides/david.mcgrew.pptx">
<front>
<title>PRNG Failures and TLS Vulnerabilities in the Wild</title>
<author initials="D" surname="McGrew" fullname="David McGrew">
<organization/>
</author>
<author initials="B" surname="Anderson" fullname="Blake Anderson">
<organization/>
</author>
<author initials="S" surname="Fluhrer" fullname="Scott Fluhrer">
<organization/>
</author>
<author initials="C" surname="Schenefiel" fullname="Chris Schenefiel">
<organization/>
</author>
<date month="January" year="2017"/>
</front>
</reference>
<reference anchor="NAXOS" target="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/strongake-submitted.pdf">
<front>
<title>Stronger Security of Authenticated Key Exchange</title>
<author initials="B" surname="LaMacchia" fullname="Brian LaMacchia">
<organization/>
</author>
<author initials="K" surname="Lauter" fullname="Kristin Lauter">
<organization/>
</author>
<author initials="A" surname="Mityagin" fullname="Anton Mityagin">
<organization/>
</author>
<date month="November" year="2007"/>
</front>
<seriesInfo name="DOI" value="10.1007/978-3-540-75670-5_1"/>
</reference>
<reference anchor="SecAnalysis">
<front>
<title>Limiting the impact of unreliable randomness in deployed security protocols</title>
<seriesInfo name="DOI" value="10.1109/CSF49147.2020.00027"/>
<seriesInfo name="IEEE 33rd Computer Security Foundations Symposium (CSF), Boston, MA, USA," value="pp. 385-393"/>
<author initials="L" surname="Akhmetzyanova" fullname="Liliya Akhmetzyanova">
<organization/>
</author>
<author initials="C" surname="Cremers" fullname="Cas Cremers">
<organization/>
</author>
<author initials="L" surname="Garratt" fullname="Luke Garratt">
<organization/>
</author>
<author initials="S" surname="Smyshlyaev" fullname="Stanislav V. Smyshlyaev">
<organization/>
</author>
<author initials="N" surname="Sullivan" fullname="Nick Sullivan">
<organization/>
</author>
<date year="2020"/>
</front>
</reference>
<reference anchor="RY2010" target="https://rist.tech.cornell.edu/papers/sslhedge.pdf">
<front>
<title>When Good Randomness Goes Bad: Virtual Machine Reset
Vulnerabilities and Hedging Deployed Cryptography</title>
<author initials="T" surname="Ristenpart" fullname="Thomas Ristenpart">
<organization/>
</author>
<author initials="S" surname="Yilek" fullname="Scott Yilek">
<organization/>
</author>
<date month="January" year="2010"/>
</front>
</reference>
<reference anchor="SP80090A" target="https://doi.org/10.6028/NIST.SP.800-90Ar1">
<front>
<title>Recommendation for Random Number Generation Using Deterministic Random Bit Generators, Special Publication 800-90A Revision 1</title>
<author>
<organization>National Institute of Standards and Technology</organization>
</author>
<date year="2015" month="June"/>
</front>
<seriesInfo name="DOI" value="10.6028/NIST.SP.800-90Ar1"/>
</reference>
<reference anchor="X962" target="https://www.techstreet.com/standards/x9-x9-62-2005?product_id=1327225">
<front>
<title>Public Key Cryptography for the Financial Services
Industry, The Elliptic Curve Digital Signature Algorithm (ECDSA)</title>
<author>
<organization>American National Standard for Financial Services (ANSI)</organization>
</author>
<date year="2005" month="November"/>
</front>
<refcontent>ANSI X9.62</refcontent>
</reference>
</references>
</references>
<section anchor="acknowledgements" numbered="false" toc="default">
<name>Acknowledgements</name>
<t>We thank <contact fullname="Liliya Akhmetzyanova"/> for her deep
involvement in the security assessment in <xref target="SecAnalysis"
format="default"/>. We thank <contact fullname="John Mattsson"/>,
<contact fullname="Martin Thomson"/>, and <contact fullname="Rich Salz"/>
for their careful readings and useful comments.</t>
</section>
</back>
</rfc>