2
$\begingroup$

Given a sample of random bytes, how to determine if Entropy Source (source of random bytes) includes a Conditioning Component or not, with respect to NIST SP 800-90 B)?

Thanks

$\endgroup$
  • $\begingroup$ @PaulUszak I am trying to run Validation Testing (as per NIST SP 800-90B) on a file containing random bytes generated by HRBG. I have estimated entropy, but I am confused how to conclude from results that conditional component was used within HRBG or not. $\endgroup$ – R. Sam Sep 28 '17 at 11:13
  • $\begingroup$ @PaulUszak as per NIST SP 800-90B, in section 3.1.5 "Entropy Estimation for Entropy Sources Using a Conditioning Component" is explained for the HRBG in which conditional component is present, in my case I want to test if Conditional Component is present in HRBG is not $\endgroup$ – R. Sam Sep 28 '17 at 11:20
  • $\begingroup$ Well, is it present or is it not? If you don't know, you can't really test the HRBG in any meaningful way. (For all you know, it might not generate any actual randomness at all, but just feed you deterministic pseudorandom output.) The testing methods described in SP 800-90B are not meant for "black box" testing of unknown randomness sources; you're supposed to know how the source works and have access to its internals for testing. (Also, try to keep your terminology straight: "conditioning" ≠ "conditional".) $\endgroup$ – Ilmari Karonen Jun 11 at 8:55
2
$\begingroup$

So this is what we're talking about:-

conditioning

It will be obvious at the drop of a hat whether a conditioning component has been used. This is why I was being pedantic with my queries. You are using the term entropy source in an ill defined and careless fashion (sorry). I'll cut you some slack when talking about PRNGs or CSPRNGs and call them entropy sources. However when dealing with a TRNG, an entropy source is a hardware thingie than produces non deterministic /random signals. It is the noise source in the above diagram. It might be a self interfering laser beam, a thermionic rectifier diode or a bank of funky lava lamps.

Simply running the common ent utility against your data will immediately confirm whether you have hin data or hout. Raw data from the noise source will fail all the ent tests. I find this the easiest litmus test for randomness. Non IID NIST section 6.2 applies to a raw noise source, but it's not worth the hassle. ent or simply viewing the hexed data will show pretty clearly if it's raw data. Raw data will be poorly distributed and might contain many common /repeat values and biases approaching 50%. You may only get ~0.2 bits /bit of entropy if the device is not particularly efficient. [I write 0.2 as an example, but it actually could be any value between 0 and 1.] If it looks weird, it's raw.

This is an example of raw entropy that might be your signal source:-

entropy

Strictly, this is illegal entropy under section 3.1.3 as NIST doesn't allow 10 bit quantization, but I'm a rebel dude and do and wear what I want. You can imagine that the digitisation of this trace would be highly biased as it's some form of inverted gamma /log normal distribution. I seem to remember that it's about 3.5 bits /sample of entropy.

Sometimes hardware designers try to build TRNGs that spit out naively uniformly distributed random data by reducing biases. Beam splitters are good at producing almost unbiased random noise data. This data may not be visually identifiable as raw, and you'll have to perform the section 6.2 tests.

If the data passes section 6.2 (or ent) and you get entropy of ~1 bit /bit, you have conditioned data. It may then have gone through something from Table 1, section 3.1.5.1.1.

$\endgroup$
6
$\begingroup$

The Ways Things Should Be is that when one tests data, one knows (independently of the data) from what this data came from, and therefore if the origin of the data is the output of a Conditioning Component (including, a source with Conditioning Component), or not (source with Raw data output).

There is no reliable way to determine that from the data. If any correct standard entropy test consistently fails (low p-value), then the data is not from the output of a properly functioning Conditioning Component. I do not see that anything else can be safely asserted (save contraposition).

In particular, if in the following model the Noise source detects particles from a radioactive source; Digitization outputs 1 for event and 0 for no event, sampling at fixed rate several times above the average disintegration period; and Post-processing computes delays between pairs of events (in periods of the sampling), with output 0, 1 or nothing based on comparing the delays (with nothing for equality); then it is practically impossible to distinguish presence or absence of a properly functioning Conditioning final stage.

Entropy source per NIST SP 800-90B 2nd draft:

Entropy source

$\endgroup$
  • $\begingroup$ @Paul Uszak: I believe that the setup I now describe before the drawing works; conforms to NIST SP 800-90B; and makes sense since there is a fair chance that Healt Tests detects a failure of any of Noise source, Digitization or Post-processing. $\endgroup$ – fgrieu Sep 28 '17 at 13:03
  • $\begingroup$ Not sure about final para. There are no commercial atomic TRNGs (Hotbits isn't commercial and it's unique anyway). A simple Vonn Neumann extractor wouldn't remove auto correlation from the detector or circuitry that would fail a Diehard test. In 99% of real world cases a raw noise signal will have "I'm a raw noise signal" written all over it. Isn't that why you have a separate YES /NO health test output? $\endgroup$ – Paul Uszak Sep 28 '17 at 13:34
  • $\begingroup$ @Paul Uszak: the YES /NO health test output is supposed to detect a failure in Noise source, Digitization, or Post-processing; and while it is hard to achieve that reliably AND have the normal output of Post-processing pass randomness tests, it can and has been done. The relatively simple structure that I propose does. RNGs in some modern commercial Smart Cards also, I'm told (but I and many others do not trust these too much; we prefer very little post processing with not-perfectly-random Raw data, which makes Health tests easier; and Conditioning). $\endgroup$ – fgrieu Sep 28 '17 at 13:41
0
$\begingroup$

Write down a probabilistic model for the hardware device based on physics. For example, maybe the device is a 52 μg sample of polonium-210, a Geiger–Müller tube, and a bit generator that counts ionizing events over the course of a second and generates a 1 bit if there are more than 4.4⨯10⁹ events—the activity of 26 μg of polonium-210 at 166 TBq/g, over the course of one second—and generates 0 bit if there are fewer. (Adjusting for the geometry and detection efficiency of the Geiger–Müller tube left as an exercise for the reader.) Polonium-210, of course, is quite safe to handle as it is primarily an alpha-emitter!Warning: This is a joke.

For any time interval $[t, t + 1\,\mathrm{sec}]$, the number of ionizing events should be Poisson-distributed with an average that is a function of the half-life of polonium-210, which is about 138 days[1], and of $t - t_0$, the duration since you loaded it up with a fresh sample of polonium.

From this you can derive a distribution on the bits it should generate over the course of time: initially, twice as many 1 bits as 0 bits on average because there's 52 μg rather than 26 μg of the stuff; then about ten fortnights into the use of the device, they should appear at about the same rate; then twenty fortnights into the use of the device there should be only half as many 1 bits as 0 bits; and so on.

Consider drawing 512 bits $b_t$ from this at some time $t$, and compare $b_t$ to $\hat b_t = \operatorname{SHA-512}(b_t)$, an example conditioner. Whatever the Hamming weight of $b_t$—which will be high on average when you load up fresh polonium, and low after it's gotten stale—the Hamming weight of $\hat b_t$ will be on average 256, because SHA-512 is a sleek conditioner with balanced volumizing effects comfortably fitting the stylish hat of $\hat b_t$.

Consider what happens instead if you mix up your grain of polonium with a grain of sugar, and the radioactively inert grain of sugar winds up in your device while the tastefully inert grain of polonium winds up in your colleague's tea, to their chagrin (paywall-free). Then the detector will report almost all zero bits from the very small counts of ionizing events from background radiation, though at this point you may be distracted by the news on the television of an international incident.

Filling in the quantitative details lets you write a statistical test—frequentist- or Bayesian-flavored according to taste—to distinguish these cases: fresh polonium, stale polonium, inert sugar, and conditioned. To be confident that you don't just have moderately stale polonium, which would have approximately the same distribution of bits as the conditioned output, you could wait ten fortnights for the half-life to kick in.

$\endgroup$
  • $\begingroup$ Why do people insist on using nuclear material as an example of a TRNG??? There aren't any. Polonium? Is this really helping with the question? If you have a crate load of Polonium sat on your desk with a Geiger tube up it, do you think that statistical bias should be your main concern? Would you be better off with a little diode or your shiny coin? $\endgroup$ – Paul Uszak Sep 28 '17 at 14:22
  • $\begingroup$ You're welcome to pick a different TRNG as long as you have a clear, concise model for how it should behave, in contrast to a uniform random string of bits. I picked polonium-210 for the sake of illustration because it admits just that, so that it is easy to imagine how to concoct a statistical test to empirically distinguish a conditioned RNG from a shampoo-only RNG. Shirley you don't think I was serious about detecting ionizing radiation events from a grain of sugar while a grain of polonium is poisoning your colleague's tea? $\endgroup$ – Squeamish Ossifrage Nov 3 '17 at 1:44
  • $\begingroup$ Would the downvoter care to explain what you disagree with in this post? $\endgroup$ – Squeamish Ossifrage Jun 11 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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