3
$\begingroup$

NIST 800-90C defines 3 classes of random bit generation (RBG) constructions: RBG1, RBG2 and RBG3. All constructions must include a DRBG from NIST SP 800-90A. The particular construction in question is RBG3, which is "designed to provide output with a security strength equal to the requested length of its output by producing outputs that have full entropy" and is based on a physical entropy source. This construction has 2 types, RBG(XOR) and RBG(RS).

I am going to guess that "full entropy" is defined as entropy per bit above some threshold like 1-2^32 or 1-2^64, not sure what the actual threshold is here so please correct me.

Why does this recommendation require a RBG3 construction based on some physical entropy source to use a DRBG that is XOR'd or re-seeded by the entropy source to produce full entropy?

$\endgroup$
2
  • 2
    $\begingroup$ Hiya, and welcome :-) I suggest that you're going to have to think outside of the 800-90x box, and consider why(n't) the NSA would want the people to (not)have access to true random numbers. You don't need 100's of pages of tech.spec. to build a TRNG. You can do it with a web page, a £0.017 diode and some wood & nails. $\endgroup$
    – Paul Uszak
    Jun 22 at 17:10
  • $\begingroup$ Thanks for the welcome and the reminder! RRR is a fascinating site, say less. $\endgroup$
    – randumb20
    Jun 23 at 3:57

2 Answers 2

1
$\begingroup$

Allegedly, it comes from this:-

When n bits of output are requested from an RBG3(XOR) construction, n bits of output from the DRBG are XORed with n full-entropy bits obtained either directly from the entropy source or from the entropy source after cryptographic processing by an external vetted conditioning function (see Section 3.3). When the entropy source is working properly, an n-bit output from the RBG3(XOR) construction is said to provide n bits of entropy or to support a security strength of n bits. The DRBG used in the RBG3(XOR) construction is always required to support a 256-bit security strength. If the entropy source fails without being detected and the DRBG has been successfully instantiated with at least 256 bits of entropy, the DRBG continues to produce output at a security strength of 256 bits.

So if the entropy source fails (they don't if designed properly), you still have 256 bits of security strength XORed over the top of rubbish. XOR preserves entropy. Although if the source did fail, reseeding wouldn't really help if the DRBG is being fed with all zeros.

If the entropy source has failed though (without being detected) it may have failed on day one. So you'd be left with a NIST approved PRNG masquerading as a TRNG. I'd ignore virtually all of 800-90x and roll your own TRNG.

There is more sense in BSI AIS 20/31.

$\endgroup$
7
  • $\begingroup$ Are you saying that the alleged point of adding a DRBG into the mix is to be able to continue providing random numbers in the case of entropy source failures? $\endgroup$
    – randumb20
    Jun 22 at 20:38
  • 1
    $\begingroup$ @randumb20 YES. That's point of that clause. $\endgroup$
    – Paul Uszak
    Jun 22 at 22:04
  • 5
    $\begingroup$ "So if the entropy source fails (they don't if designed properly)" - an entropy source is a hardware device - any hardware device will fail given sufficient manufacturing defects or environmental abuse. The difference between entropy sources and general digital electronics is that entropy sources can fail subtly... $\endgroup$
    – poncho
    Jun 22 at 22:24
  • 1
    $\begingroup$ Poncho's point is why I make an effort to be clear about the distinction between a TRNG (theoretical device similar to a Random Oracle that provides truly random bits when queried) and a HWRNG (real hardware device that attempts to be indistinguishable from a TRNG). HWRNGs are the real-world entropy sources we can work with, but it's often useful to pretend they're TRNGs to simplify security proofs. If they're correctly made and functioning properly there's no way to tell the difference, but that caveat is sometimes critical. $\endgroup$ Jun 23 at 16:36
  • $\begingroup$ @SAIPeregrinus Are you sure about HWRNGs? I have (maybe) six or seven TRNGs on my table, but Google only finds en.wikipedia.org/wiki/Hwarang... $\endgroup$
    – Paul Uszak
    Jun 25 at 6:37
5
$\begingroup$

Why does this recommendation require a RBG3 construction based on some physical entropy source to use a DRBG that is XOR'd or re-seeded by the entropy source to produce full entropy?

Remember that RGB3 is designed for the ultraparanoid types, who ask if 1,000,000 random bits, want each of the $2^{1000000}$ possible outputs to be approximately equiprobable [1]. It should be obvious that this goal would be unachievable for any rng with a fixed state much less than 1,000,000 bits.

Hence, to output an arbitrary number of 'truly random' bits, we need some additional entropy inputs as we go along. NIST has opted for two different options to provide this additional entropy input; xor'ing the raw entropy input with the DRBG output, and periodic reseeding. The first option obviously achieves this goal (xor'ing a truly random string with anything not correlated to it produces a truly random string); the second one would appear to (if we make some plausible but unproven assumptions on the DRBG).

[1]: My opinion: don't ask me what they want to do with those random bits - almost all the uses of random bits use them as inputs to some computational complexity crypto, which would void any security we would get from informational theoretical randomness.

$\endgroup$
9
  • $\begingroup$ With your experience, why are you championing the NSA's nudging $\endgroup$
    – Paul Uszak
    Jun 22 at 22:10
  • 3
    $\begingroup$ @PaulUszak: two things: 1) NIST != NSA; I know the crypto people at NIST; that make decisions independent of the NSA, and 2) I was explaining what RBG3 was (and why); I wasn't endorsing it... $\endgroup$
    – poncho
    Jun 23 at 1:23
  • $\begingroup$ I don't understand this response fully so bear with me as prod and try to get my head around it, I am just a rookie hardware entropy enthusiast. My understanding is that it is the conditioning (not the DRBG) that helps make the output approximately equiprobable. Are you saying that RBG3(XOR) and RBG3(RS) constructions allow one to get more entropy than they would if they just cut out the DRBG all together? $\endgroup$
    – randumb20
    Jun 23 at 3:38
  • 2
    $\begingroup$ @randumb20: no, obviously, inserting the DRBG can't add entropy (a deterministic process cannot); instead, I believe it is intended to be a belt-and-suspenders approach; that way, if the entropy had a subtle failure that isn't detected by its health tests, you're still at least computationally secure. $\endgroup$
    – poncho
    Jun 23 at 12:26
  • 2
    $\begingroup$ @randumb20: the plausible but unproven assumption would be that reseeding with N bits of entropy makes the next N bits of output equiprobable (that is, all $2^N$ output sequences occur with approximately the same probability). That certainly sounds reasonable (for the values of $N$ under discussion), however given the complexity of the DRBGs involved, completely unprovable (unlike the XOR construction, where we can generate a proof just assuming that the original entropy stream was uniformly random) $\endgroup$
    – poncho
    Jun 23 at 13:41

Your Answer

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

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