5
$\begingroup$

This question concerns the conditioning and output of true random number generators. It refers to NIST Special Publication 800-90C, Recommendation for Random Bit Generator (RBG) Constructions. It defines an $ n $ length bit string as having full entropy (ideally random) as:-

...if that bit string is estimated to contain at least $ (1-\epsilon) n $ bits of entropy, where $ 0 \leq \epsilon \leq 2^{-64} $.

Now to obtain a bit string containing full entropy, the document recommends a conditioning operation listed in Appendix C. The smallest internal block width of any of these functions is 64 bits for treble DES.

And the document also says that if you follow this recommendation, you'll get a full entropy $ t $ length bit string from the conditioner's output:-

If $ t \leq \frac{n}{2} $, then the output string has full entropy output .

This is the common rule of thumb for outputting half of the hashed input entropy in a TRNG. My question therefore is what is the relationship between $ \frac{n}{2} $ and $ 2^{-64} $? More specifically, what would the maximum of $ \epsilon $ be for $ \frac{n}{4} $?

$\endgroup$

2 Answers 2

5
$\begingroup$

The notation is a little confusing because it uses the same letter $n$ for two purposes, so let's change it to be a bit clearer:

  1. An entropy source output string containing $2t$ bits of entropy can be conditioned into a string of $t$ bits that contains full entropy output using an approved conditioning function, where $t$ is the length of the output block of the approved derivation function (see SP 800-90B).

(Replaced $n$ by $t$.)

In other words, if we have a physical device that produces a string $\sigma$ with $2t$ bits of entropy, which is necessarily at least $2t$ bits long, and we can pick a conditioning function $C\colon \{0,1\}^* \to \{0,1\}^t$, then the string $C(\sigma)$ is $t$ bits long and has nearly $t$ bits of entropy—in particular, $(1 - \varepsilon) t$, where $\varepsilon < 2^{-64}$.

This is a statement of an assumption (in §4.2 ‘Assumptions’) about the entropy source, having at least $2t$ bits of entropy where $t$ is the length of the output block.

  1. The derivation functions in SP 800-90A distribute the entropy provided by the input string is $n$ bits (so that the length of the input string is $r$ bits for some $r \geq n$), and the length of the output string is $t$ bits, then the following is true:

    • If $t \leq n/2$, then the output string has full entropy output (i.e., the output string has $(1 - \varepsilon) t$ bits of entropy, for some $\varepsilon \leq 2^{-64}$).

($t$ is the same as above now.)

In other words, if we have a string $\sigma$ with $n$ bits of entropy, which is necessarily at least $n$ bits long ($r \geq n$), then for any choice of derivation function $C\colon \{0,1\}^* \to \{0,1\}^t$ in SP 800-90A with $t \leq n/2$, the $t$-bit string $C(\sigma)$ has nearly $t$ bits of entropy—in particular, $(1 - \varepsilon) t$, where $\varepsilon < 2^{-64}$.

This is a statement of an assumption about the derivation function, like Hash_df, used as a conditioning function. An example of a function that would fail to satisfy this property is one that, say, just gives the first $t$ bits of the input string.

Why should these relations hold? See an earlier answer for some details. The quick summary is that a rough approximation for expected entropy of the output $F(\sigma)$ of a uniform random function $F\colon \{0,1\}^* \to \{0,1\}^t$ on a string $\sigma$ with $t + k$ bits of entropy is $\lg 2^t (1 - e^{-2^k}) = t + \lg (1 - e^{-2^k}) \approx t - e^{-2^k}/\log 2$, so as long as $k$ is reasonably large we easily attain ‘full entropy’ in this model with $\varepsilon \approx e^{-2^k}/(t\log 2)$.

Picking $k \geq 64$ is plenty—and we are required to do that because the block size of every approved derivation function is at least 64. We don't have a uniform random function in the real world, but the derivation functions of SP 800-90A don't seem to have any interesting properties that let us distinguish them from one, so it's a pretty good model.

What if you chose a string $\sigma$ with $n = 256$ bits of entropy, and a 3DES-based derivation function with an output block of $t = 64 = n/4$ bits? Then $k = 192$, so $\varepsilon$ is really quite tiny, and we get ‘full entropy’ in a 64-bit string—although that's only just under 64 bits of entropy.

What if you chose a string $\sigma$ with $n = 130$ bits of entropy, and an AES-based derivation function with an output block of $t = 128$ bits? The margin is smaller in this case: since $k = 2$, the approximation above (a) is not a very good approximation and (b) gives an $\varepsilon$ nowhere near $2^{-64}$. Maybe we get more than 64 bits of entropy in the end, but that's not ‘full entropy’ for a 128-bit string.

At what $k$ do we draw the line? To give a comfortable margin without having to think hard about it, we just say that you should use twice as much the entropy in the input as the ${\geq}64$-bit output is long, in order to reliably get ‘full entropy’ in the output.

$\endgroup$
3
  • $\begingroup$ Having a problem with $ \varepsilon \approx e^{-2^k}/(t\log 2) $ where t=64 and k=192. From SpeedCrunch (which handles 4 digit exponents), exp(-2^192)/(64*log(2)) = NaN. I don't think that you can raise e to such a huge -ve number. I build TRNGs for my sins so it would be nice if this stuff worked for background & marketing:-) $\endgroup$
    – Paul Uszak
    Apr 9, 2018 at 3:21
  • 2
    $\begingroup$ Since $t = 64 > 1/\log 2$, we have $\varepsilon \approx e^{-2^k} / (t \log 2) < e^{-2^k} < 2^{-2^k} = 2^{-2^{192}}$, which in technical jargon is usually classified as ‘very small’. Note that the smallest IEEE 754 binary64 floating-point number is $2^{-1074}$, and $2^{-2^{192}}$ is much, much smaller than that. Either you typed something in wrong, or SpeedCrunch is broken if it gave NaN for that; standard IEEE 754 arithmetic rounds the result to zero. $\endgroup$ Apr 9, 2018 at 3:52
  • $\begingroup$ @PaulUszak The requirement that the entropy of a $t$-bit string be at least $(1 - \varepsilon) t$ for $\varepsilon < 2^{-64}$ before it is considered to have ‘full entropy’ is very conservative. If we can show $\varepsilon \lll 2^{-64}$ it's even more conservative. But remember that these are all estimates of the Shannon entropy, which is an upper bound on the min-entropy. Precise estimates of min-entropy a pain to compute. So these are all extremely conservative choices, like requiring $\varepsilon < 2^{-64}$ and suggesting $t < n/2$, that make it unlikely we have to think harder. $\endgroup$ Apr 9, 2018 at 16:25
-2
$\begingroup$

Found it.

The relationship of input & output entropies to the bias is simply bounded by:-

$$ \epsilon = 2^{-(sn-k)/2} $$

where $s$ = input entropy rate, $n$ = number of input bits and $k$ = internal block width. If you take AESy like conditioning components of a 128 bit width, $\epsilon = 2^{-64}$. This exactly tallies with NIST. Note then that $t \leq \frac{n}{2}$ only holds for a $k$ of 128. The NIST recommendation does not hold for a DES /TDEA conditioner which would produce a larger bias of $2^{-32}$. Such would not have full entropy as defined by NIST using their stated criteria for $t$. Curious.

And so finally to my questionanswer. If n = 4 and I use AES, $\epsilon = 2^{-192}$.


References:-

ID Quantique, Technical Paper on Randomness Extractor. Version 1.0 September 2012

Bruno Sanguinetti, Anthony Martin, Hugo Zbinden, and Nicolas Gisin, Quantum random number generation on a mobile phone. Group of Applied Physics, University of Geneva, Switzerland.

$\endgroup$
3
  • 1
    $\begingroup$ The $\epsilon$ formula you quoted appears to be a bound on the total variation distance of the output of a specific randomness extractor, namely $x \mapsto M\cdot x$ for a uniform random linear map $M$ of $n$-bit strings to $k$-bit strings. (I don't know whether it actually gives this bound, but it's plausible.) Total variation distance is a metric on probability distributions, and while it's the usual one in the randomness extractor literature, there's nothing magic about it; KL divergence, Hellinger distance, etc., are other metrics that are sometimes relevant to applications. $\endgroup$ Feb 18, 2019 at 15:17
  • $\begingroup$ The total variation distance of two distributions $P$ and $Q$ is $(1/2) \sum_x |P(x) - Q(x)|$. It is a way in the randomness extractor literature to quantify nonuniformity. Another way is KL divergence; when taken relative to a uniform distribution, it coincides with Shannon entropy. The term ‘bias’ doesn't generally mean TVD; I took your question to be about entropy, and in another question fgrieu took it to mean expected ratio of one bits to zero bits. See en.wikipedia.org/wiki/Bias_(statistics) for other things it may mean. $\endgroup$ Feb 18, 2019 at 15:27
  • $\begingroup$ This $\epsilon$ formula is about the distribution of the output from applying a random function with a specific known probability distribution ($x \mapsto M\cdot x$ for a uniform random matrix $M$) to a random input with an unknown distribution characterized only by a bound on its (probably min-)entropy. AES is not one of these: there is no matrix $M$ such that $M\cdot x = \operatorname{AES}_k(x)$. We can estimate bounds by computing the expected {entropy, TVD, ...}, modelling AES as a uniform random permutation, like I did above, but neither the paper nor the brochure you cited does this. $\endgroup$ Feb 18, 2019 at 15:34

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.