6
$\begingroup$

The BSI (Federal Office for Information Security in Germany) has published a paper detailing the requirements of cryptographic modules for certain applications in the energy sector: Key Lifecycle Requirements.

The paper describes the various requirements for hardware security modules but also includes software based cryptographic modules.

The requirement for the random number generator are these:

For random number generation, e.g. for key or signature generation, a random number generator of one of the classes NTG.1, DRG.4 or PTG.3 according to [AIS 20/31] MUST be used.

The AIS document can be found here.

My question is: Does the Windows CNG random number generator conform to either of these classes?

The documentation for BCryptGenRandom states:

The default random number provider implements an algorithm for generating random numbers that complies with the NIST SP800-90 standard, specifically the CTR_DRBG portion of that standard.

The AIS document referenced above mentions NIST SP800-90, but only the Hash_DRBG.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

Reference

Since the question is about conformance, it's critical to find to what.

The quoted requirement in [KLSR] Key Lifecycle Security Requirements Version 1.0.3 refers to

[AIS 20/31]   BSI: A proposal for: Functionality classes for random number generators, Version 2.0

which, without doubt, is the document referenced by AIS 31 (found there with links to it's references) as:

[KS2011]   W. Killmann, W. Schindler, „A proposal for: Functionality classes for random number generators“, Version 2.0, September 18, 2011

This is to be confused neither with

Even though [DRAFT] is not official, it's still useful

  • When the official [KS2011] is unclear. Note that [DRAFT] references [KS2011] as [AIS2031An_11], and has §3.3.1 (resp. §3.4.1, §3.5.1) listing “Main Differences from [AIS2031An_11]” for DRNG (resp. PTRNG, NPTRNG) which are a goldmine on what [KS2011] actually means.
  • When we want a secure RNG that actually works on the field despite† using [KS2011] as a guideline.

Now for an attempt at an actual answer, with the disclaimer that the only rubber stamps I ever used beard a company's name/logo or “payed”, not “certified”, and that I consider AIS 31, [AIS31V1], [KS2011], and [DRAFT] hideously complex.

What's Windows's BCryptGenRandom ?

A useful reference to Windows's RNGs is Niels Ferguson's [NF2019] The Windows 10 random number generation infrastructure, October 2019, despite that

it should not be interpreted to be a commitment on the part of Microsoft, and Microsoft cannot guarantee the accuracy of any information presented after the date of publication.

We are told (additions mine) that

(…) it's used a (NIST) SP800-90 AES_CTR_DRBG with 256-bit security strength using the df() function (meaning Derivation Function) for seeding and re-seeding. (…)
This PRNG has backtracking resistance; after it has produced an output, the updated PRNG state does not contain enough information to recover that output. The backtracking resistance property is maintained throughout the RNG system.
Buffered PRNG: The Basic PRNGs are not used directly, but rather through a wrapping layer that adds several features (among which:) A small buffer of random bytes to improve performance for small requests. (…)
The buffering is straightforward. There is a small buffer (currently 128 bytes). If a request for random bytes is 128 bytes or larger, it is generated directly from AES_CTR_DRGB. If it is smaller than 128 bytes it is taken from the buffer. (…)
BCryptGenRandom: The BCRYPT_RNG_ALGORITHM produces random data by calling the per-processor AES-CTR-DRBG PRNGs. This works both in kernel mode and user mode.

I think we can refer to NIST SP 800-90A Rev. 1 for AES_CTR_DRBG with Derivation Function as a reference for interpreting the above.

Using Windows's BCryptGenRandom for key generation vs [KLSR]

Windows is not running in a “Hardware Security Module”, much less in one “Common Criteria certified by the BSI according to one (listed) Protection Profile”, thus Window's BCryptGenRandom could be usable for key generation only at “Security Level 1” in the sense of [KLSR], and only if it's a tenable position that the thing running Windows is worth the “Cryptographic Module” name.

On purely technical (rather than conformance) grounds, this means that integrity of that Windows platform, hardware and software, is both of paramount importance, and hypothetical. Therefore, in my opinion, whatever risk there may be to use BCryptGenRandom for key generation is negligible compared to the risk of using a compromised platform.

OTOH, I see no requirement for formal certification of the “Cryptographic Module” at “Security Level 1”, thus I'll leave aside what that thing running Windows is, and the only question I'll try to answer is:

Is it a tenable position that Windows's BCryptGenRandom belongs to one of the classes NTG.1, DRG.4 or PTG.3 according to [KS2011]?

PTG.3: nope

I assert that BCryptGenRandom can't be construed as PTG.3. A most uncontroversial reason is that in [KS2011] §4.5.1 #305 PTG.3.6 it's required that “the output data rate of the post-processing algorithm shall not exceed its input data rate”, and I'm seeing the output data rate of BCryptGenRandom limited by processor performance à la /dev/urandom, not gathered entropy à la /dev/random of old-style unixes.

DRG.4 or NTG.1?

That leaves DRG.4 and NTG.1 as our only avenues for conformance. These are, respectively, for

  • “hybrid deterministic RNGs that primarily rely on the security imposed by computational-complexity, which is ‘enhanced’ by additional entropy from a physical true RNG” (part of informational §4.9 #356)
  • “non-physical true RNGs that rely on information-theoretical security (similar as physical RNGs) but use external input signals as entropy source. Additionally, a suitable cryptographic post-processing algorithm shall provide a second security anchor.” (part of informational §4.10 #366)

My reading is that both are True RNGs (despite the “Deterministic” in DRG.4), in the sense that in actual uses their output varies unpredictably thanks to some entropy source, and both use post-processing of that source to produce the output. BCryptGenRandom broadly fits that.

Palpable differences are that NTG.1 implies

  • “non-physical” (which I tentatively read as meaning the entropy sources are out of scope, meaning in the case of BCryptGenRandom that we'd not need to care for the hardware),
  • at least an aim at information-theoretical security (which I read as secure against adversaries with arbitrary computing power and/or based on entropy arguments).

So if we could, we'd like to assert that BCryptGenRandom is NTG.1 so that we need not consider the hardware it runs on. Unfortunately that would imply it is per §4.10.1 #367 NTG.1.1:

The RNG shall test the external input data provided by a non-physical entropy source in order to estimate the entropy and to detect non-tolerable statistical defects under the condition [assignment: requirements for NPTRNG operation].

But I do not see support for such test in [NF2019] or what we could state the requirements are. There's a similar issue for §4.10.1 #367 NTG.1.2. As a relatively minor aside (since no requirement of §4.10.1 #367 is actually broken), it's untenable that AES_CTR_DRBG with 128-byte output as in BCryptGenRandom provides information-theoretical security.

I conclude it's least objectionable to argue for DRG.4 than NTG.1, but we can keep the later as a backup option.

Enhanced backward secrecy (requirements DRG.4.3 and NTG.1.3)

Per [KS2011] §4.9.1 #358 DRG.4.3 and §4.10.1 #367 NTG.1.3, both require that “The RNG provides backward secrecy even if the current internal state is known”. My reading is that's the “enhanced backward secrecy” in #353:

While (DRG.2.2) and (DRG.2.3) require forward and backward secrecy (i.e., unknown output value cannot be determined from known output values), the security capabilities (DRG.3.2) and (DRG.3.3) additionally require enhanced backward secrecy. This means that previous output values cannot even be determined with knowledge of the current internal state and current and future output values. Enhanced backward secrecy might be relevant, for instance, for software implementations of a DRNG when the internal state has been compromised while all random numbers generated in the past shall remain secret (e.g., cryptographic keys).

My impression is that BCryptGenRandom aims at “enhanced backward secrecy”, that it calls “backtracking resistance”, despite the aforementioned buffering mechanism in the wrapping layer. That's sort of stated in Niels Ferguson's document:

The buffer maintains secrecy. After a call to generate bytes, the buffered RNG state no longer has the data to reconstruct the output it provided. Of course, at any time the RNG state has the information to predict all future outputs until the next reseed.

At least we can keep a straight face when we assert conformance to DRG.4.3 or NTG.1.3.

Forward and backward secrecy (DRG.4.2 and DRG.4.3)

Forward and backward secrecy are requirements for DRG.4 per [KS2011] §4.9.1 #358 DRG.4.2 and DRG.4.3. With correct implementation, proper seeding of the 256-byte key, and any manageable output size, these requirements are met by AES-CTR-DRBG, and that's justifiable. I see no reason to hesitate to tick these boxes.

Statistical properties (DRG.4.6 and DRG.4.7)

[KS2011] §4.9.1 #358 DRG.4.6 and DRG.4.7 prescribe statistical properties theoretical and experimental (for the later: despite ample theoretical and practical evidence that gives no meaningful assurance). It can be justified that AES-CTR-DRBG meet these. I see no reason to hesitate to tick these boxes.

Other DRG.4.x

The remaining functional security requirements for DRG.4 are DRG.4.1 and DRG.4.5 of §4.9.1 #358. I don't immediately see that they are not met, and will try to think about a plausible justification that they are. But don't hold your breath.

Conclusion

If the context makes [KLSR] “Security Level 1” acceptable, and possible to get away with a “Cryptographic Module” that's a machine running a standard OS like Windows, I find technically sound to use Windows's BCryptGenRandom for key generation, and tenable that based on [NF2019] and a self-evaluation, BCryptGenRandom meets the DRG.4 criteria of [KS2011].


Note: The question's observation about [DRAFT] also is valid for [KS2011]: they both

mention NIST SP800-90, but only the Hash_DRBG

That's not much of an issue, because NIST SP800-90's Hash_DRBG is only mentioned as an informative example, and in my understanding for the purpose of illustrating how to justify a claimed attack potential, which is a consideration only for a Common Criteria evaluation, that I don't see asked by [KLSR] at “Security Level 1”.

And it remains good news that Hash_DRBG is deemed worth being an example, because save for quantitative aspects and using a block cipher, AES_CTR_DRBG with derivation function arguably has design goals aligned to that of Hash_DRBG.


† [DRAFT] fixes issues with [KS2011]. One that bogged me for two months is that for the (rightly) prescribed “online test”, [KS2011] gives a reference example §5.5.1 #408 (essentially a Pearson test) that

  • fails annoyingly often when applied to actual unconditioned entropy sources due to inevitable and harmless bias, and is pointless when applied to conditioned sources;
  • uses 128 rather than 80 samples in [AIS31V1], yet does not update the stated failure rate under null hypothesis (which is decreased by the change, yet the failure rate for actual unconditioned entropy sources is increased from bad to worse)
  • states that it applies a chi-squared approximation that would be outside of the bounds where that's mathematically justified
  • refers for that approximation to a book with a serious error in the relevant table.
$\endgroup$
1
  • $\begingroup$ Thank you very much for the detailed analysis. $\endgroup$ Sep 28, 2023 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.