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
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communityGiven 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
So this is what we're talking about:-
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:-
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.
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:
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.