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 [RFC 5869
], 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 [SecAnalysis
]). L SHOULD
be a fixed length. Let Expand(k, info, n) be a variable-length output PRF, e.g., HKDF-Expand [RFC 5869
], 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 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.
be a deterministic signature function, e.g., deterministic Elliptic Curve Digital Signature Algorithm (ECDSA) [RFC 6979
], 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 [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.