[1]https://www.rfc-editor.org/rfc/rfc8937.html
RFC 8937
Randomness Improvements for Security Protocols
[2]Abstract
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.
This document is a product of the Crypto Forum Research Group (CFRG) in
the IRTF.
[3]Status of This Memo
This document is not an Internet Standards Track specification; it is
published for informational purposes.
This document is a product of the Internet Research Task Force (IRTF).
The IRTF publishes the results of Internet-related research and
development activities. These results might not be suitable for
deployment. This RFC represents the consensus of the Crypto Forum
Research Group of the Internet Research Task Force (IRTF). Documents
approved for publication by the IRSG are not a candidate for any level
of Internet Standard; see Section 2 of RFC 7841.
Information about the current status of this document, any errata, and
how to provide feedback on it may be obtained
at [4]https://www.rfc-editor.org/info/rfc8937.
[5]Copyright Notice
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
([6]https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents carefully,
as they describe your rights and restrictions with respect to this
document.
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 [[7]DebianBug], can lead to insecure TLS connections.
CSPRNGs may also be intentionally weakened to cause harm [[8]DualEC].
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.
This document proposes an improvement to randomness generation in
security protocols inspired by the "NAXOS trick" [[9]NAXOS].
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.
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 SHOULD 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:
1. 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.
2. 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).
3. 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.
This document represents the consensus of the Crypto Forum Research
Group (CFRG).
[10]2. [11]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 [[12]RFC2119] [[13]RFC8174] when, and only when, they appear in
all capitals, as shown here.
[14]3. [15]Randomness Wrapper
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.
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 [[16]RFC5869], 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 [[17]SecAnalysis]). L SHOULD be a fixed length. Let
Expand(k, info, n) be a variable-length output PRF, e.g.,
HKDF-Expand [[18]RFC5869], 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.
The construction works as follows. Instead of using G(n) when
randomness is needed, use G'(n), where
G'(n) = Expand(Extract(H(Sig(sk, tag1)), G(L)), tag2, n)
Functionally, this expands n random bytes from a key derived from the
CSPRNG output and signature over a fixed string (tag1). See [19]Section
4 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).
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.
Sig(sk, tag1) need only be computed once for the lifetime of the
randomness wrapper and MUST NOT be used or exposed beyond its role in
this computation. Additional recommendations for tag1 are given in the
following section.
Sig MUST be a deterministic signature function, e.g., deterministic
Elliptic Curve Digital Signature Algorithm (ECDSA) [[20]RFC6979], 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.
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 [[21]SecAnalysis].
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.
[22]4. [23]Tag Generation
Both tags MUST 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.
The RECOMMENDED tag construction procedure is as follows:
tag1:
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 RECOMMENDED 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 [[24]RY2010]).
See [25]Section 5 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.
tag2:
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).
[26]5. [27]Application to TLS
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
G'(n) = HKDF-Expand(HKDF-Extract(H(Sig(sk, tag1)), G(L)), tag2, n)
[28]6. [29]Implementation Guidance
Recall that the wrapper defined in [30]Section 3 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.
[31]7. [32]IANA Considerations
This document has no IANA actions.
[33]8. [34]Security Considerations
A security analysis was performed in [[35]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 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.
The signature in the construction, as well as in the protocol
itself, MUST NOT use randomness from entropy sources with dubious
security guarantees. Thus, the signature scheme MUST 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.
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.
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 [[36]MAFS2017]). It is RECOMMENDED that tag1
incorporate all available information about the environment, such as
process attributes, virtual machine user information, etc.
[37]9. [38]Comparison to RFC 6979
The construction proposed herein has similarities with that
of [[39]RFC6979]; both of them use private keys to seed a deterministic
random number generator. [40]Section 3.3 of [[41]RFC6979] recommends
deterministically instantiating an instance of the HMAC_DRBG
pseudorandom number generator, described in [[42]SP80090A] and Annex D
of [[43]X962], 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.
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 [[44]RFC6979] 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 [[45]RFC6979] 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.
[46]10. [47]References
[48]10.1. [49]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, <[50]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, <[51]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, <[52]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, <[53]https://www.rfc-editor.org/info/rfc8174>.
[54]10.2. [55]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, <[56]https://pdfs.semanticscholar.org/fcf9/fe0946c20e936b5
07c023bbf89160cc995b9.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, <[57]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, <[58]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, <[59]https://www.microsoft.com/en-us/research/wp-content/u
ploads/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, <[60]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, <[61]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, <[62]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, <[63]https://www.techstreet.com/standards/x9-x9-62-2005?pr
oduct_id=1327225>.
[64]Acknowledgements
We thank Liliya Akhmetzyanova for her deep involvement in the security
assessment in [[65]SecAnalysis]. We thank John Mattsson, Martin
Thomson, and Rich Salz for their careful readings and useful comments.
References
1. https://www.rfc-editor.org/rfc/rfc8937.html
2. https://www.rfc-editor.org/rfc/rfc8937.html#abstract
3. https://www.rfc-editor.org/rfc/rfc8937.html#name-status-of-this-memo
4. https://www.rfc-editor.org/info/rfc8937
5. https://www.rfc-editor.org/rfc/rfc8937.html#name-copyright-notice
6. https://trustee.ietf.org/license-info
7. https://www.rfc-editor.org/rfc/rfc8937.html#DebianBug
8. https://www.rfc-editor.org/rfc/rfc8937.html#DualEC
9. https://www.rfc-editor.org/rfc/rfc8937.html#NAXOS
10. https://www.rfc-editor.org/rfc/rfc8937.html#section-2
11. https://www.rfc-editor.org/rfc/rfc8937.html#name-conventions-used-in-this-do
12. https://www.rfc-editor.org/rfc/rfc8937.html#RFC2119
13. https://www.rfc-editor.org/rfc/rfc8937.html#RFC8174
14. https://www.rfc-editor.org/rfc/rfc8937.html#section-3
15. https://www.rfc-editor.org/rfc/rfc8937.html#name-randomness-wrapper
16. https://www.rfc-editor.org/rfc/rfc8937.html#RFC5869
17. https://www.rfc-editor.org/rfc/rfc8937.html#SecAnalysis
18. https://www.rfc-editor.org/rfc/rfc8937.html#RFC5869
19. https://www.rfc-editor.org/rfc/rfc8937.html#tag-gen
20. https://www.rfc-editor.org/rfc/rfc8937.html#RFC6979
21. https://www.rfc-editor.org/rfc/rfc8937.html#SecAnalysis
22. https://www.rfc-editor.org/rfc/rfc8937.html#section-4
23. https://www.rfc-editor.org/rfc/rfc8937.html#name-tag-generation
24. https://www.rfc-editor.org/rfc/rfc8937.html#RY2010
25. https://www.rfc-editor.org/rfc/rfc8937.html#sec_tls13
26. https://www.rfc-editor.org/rfc/rfc8937.html#section-5
27. https://www.rfc-editor.org/rfc/rfc8937.html#name-application-to-tls
28. https://www.rfc-editor.org/rfc/rfc8937.html#section-6
29. https://www.rfc-editor.org/rfc/rfc8937.html#name-implementation-guidance
30. https://www.rfc-editor.org/rfc/rfc8937.html#wrapper
31. https://www.rfc-editor.org/rfc/rfc8937.html#section-7
32. https://www.rfc-editor.org/rfc/rfc8937.html#name-iana-considerations
33. https://www.rfc-editor.org/rfc/rfc8937.html#section-8
34. https://www.rfc-editor.org/rfc/rfc8937.html#name-security-considerations
35. https://www.rfc-editor.org/rfc/rfc8937.html#SecAnalysis
36. https://www.rfc-editor.org/rfc/rfc8937.html#MAFS2017
37. https://www.rfc-editor.org/rfc/rfc8937.html#section-9
38. https://www.rfc-editor.org/rfc/rfc8937.html#name-comparison-to-rfc-6979
39. https://www.rfc-editor.org/rfc/rfc8937.html#RFC6979
40. https://www.rfc-editor.org/rfc/rfc6979#section-3.3
41. https://www.rfc-editor.org/rfc/rfc8937.html#RFC6979
42. https://www.rfc-editor.org/rfc/rfc8937.html#SP80090A
43. https://www.rfc-editor.org/rfc/rfc8937.html#X962
44. https://www.rfc-editor.org/rfc/rfc8937.html#RFC6979
45. https://www.rfc-editor.org/rfc/rfc8937.html#RFC6979
46. https://www.rfc-editor.org/rfc/rfc8937.html#section-10
47. https://www.rfc-editor.org/rfc/rfc8937.html#name-references
48. https://www.rfc-editor.org/rfc/rfc8937.html#section-10.1
49. https://www.rfc-editor.org/rfc/rfc8937.html#name-normative-references
50. https://www.rfc-editor.org/info/rfc2119
51. https://www.rfc-editor.org/info/rfc5869
52. https://www.rfc-editor.org/info/rfc6979
53. https://www.rfc-editor.org/info/rfc8174
54. https://www.rfc-editor.org/rfc/rfc8937.html#section-10.2
55. https://www.rfc-editor.org/rfc/rfc8937.html#name-informative-references
56. https://pdfs.semanticscholar.org/fcf9/fe0946c20e936b507c023bbf89160cc995b9.pdf
57. https://projectbullrun.org/dual-ec/documents/dual-ec-20150731.pdf
58. https://rwc.iacr.org/2017/Slides/david.mcgrew.pptx
59. https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/strongake-submitted.pdf
60. https://rist.tech.cornell.edu/papers/sslhedge.pdf
61. https://doi.org/10.1109/CSF49147.2020.00027
62. https://doi.org/10.6028/NIST.SP.800-90Ar1
63. https://www.techstreet.com/standards/x9-x9-62-2005?product_id=1327225
64. https://www.rfc-editor.org/rfc/rfc8937.html#name-acknowledgements
65. https://www.rfc-editor.org/rfc/rfc8937.html#SecAnalysis