Score:3

Why does NIST SP 800-90C RBG3 construction require XOR or reseeding a DRBG with a physical entropy source to produce full entropy?

lr flag

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?

Paul Uszak avatar
cn flag
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](http://www.reallyreallyrandom.com/zener/breadboard/), a £0.017 diode and some wood & nails.
randumb20 avatar
lr flag
Thanks for the welcome and the reminder! RRR is a fascinating site, say less.
Score:5
my flag

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.

Paul Uszak avatar
cn flag
With your experience, why are you championing the NSA's [nudging](https://en.wikipedia.org/wiki/Nudge_theory)
poncho avatar
my flag
@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...
randumb20 avatar
lr flag
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?
poncho avatar
my flag
@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.
randumb20 avatar
lr flag
Can you elaborate on your statement _the second one would appear to (if we make some plausible but unproven assumptions on the DRBG)_? Edit: Curious what the plausible but unproven assumption on the DRBG are.
Paul Uszak avatar
cn flag
So, can I draw your friends' attention to where (line 49 of 800-90c, Authority) they wrote about their responsibilities under [44 U.S.C. § 3551](https://uscode.house.gov/view.xhtml?req=granuleid:USC-prelim-title44-section3551&num=0&edition=prelim)? NIST = f(NSA, Director of National Intelligence, Secretary of Defence) in US law regarding security systems. I keep repeating it because nobody wants to believe it. Please read the link and count the number of times "NSA" appears...
poncho avatar
my flag
@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)
randumb20 avatar
lr flag
@poncho In regards to [1], isn't this exactly what an RBG3(RS) construction does? Void our information-theoretic security?
randumb20 avatar
lr flag
Also for those interested, I believe an example of the XOR proof mentioned by @poncho can be found [here](https://crypto.stackexchange.com/questions/17658/mixing-entropy-sources-by-xor).
Score:1
cn flag

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.

randumb20 avatar
lr flag
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?
Paul Uszak avatar
cn flag
@randumb20 YES. That's point of that clause.
poncho avatar
my flag
"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...
SAI Peregrinus avatar
si flag
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.
Paul Uszak avatar
cn flag
@SAIPeregrinus Are you sure about HWRNGs? I have (maybe) six or seven TRNGs on my table, but Google only finds https://en.wikipedia.org/wiki/Hwarang...
Paul Uszak avatar
cn flag
And, what's a TRNG security proof?
randumb20 avatar
lr flag
Accepting this as the answer because it provides concrete reason by referencing NIST documentation.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.