1
$\begingroup$

Assume that I have a hardware entropy source. Not a TRNG, but the source that might feed a TRNG's extraction algorithm. This source produces independent bits with a not unreasonable bias of $60/40$. So that's $p(1) = 0.6$ and $p(0) = 0.4$ and min. entropy would therefore be 0.737 bits/bit.

I then use a cryptographic hash function to extract entropy. Let's say I take groups of 320 bits from my entropy source and hash them with SHA1. What is the resulting bias in the long run output? Or how might this be calculated?

I'm hoping for a numeric answer or calculation rather than verbiage.

$\endgroup$
  • 1
    $\begingroup$ I'll only comment since you are interested in a quantitative answer, but it seems like there wouldn't be any bias in the output. Assuming that you simply fed an incrementing counter into sha1, which is clearly a highly biased input, it seems that the output still wouldn't display any statistical bias. $\endgroup$ – Ella Rose Feb 15 '18 at 1:42
  • $\begingroup$ @EllaRose Well that's the thing. A counter isn't biased in the long run is it? Counting 0 to (2^80-1) is exactly 2^79 evens and 2^79 odds passing through the state. $\endgroup$ – Paul Uszak Feb 15 '18 at 14:05
2
$\begingroup$

On the conditioned generator's bias

Mathematically (and if $60/40$ is the bias of the question's unconditioned source), "the bias in the long run output" can be defined as $$E(|H(m)|)\;/\;(160-E(|H(m)|))$$ where $E(|H(m)|)$ is the expected value of the Hamming weight of the SHA-1 hash $H(m)$ when $m$ is a 320-bit bitstring made from independent random bits that are 1 with probability $p$, taken to be $p=0.6$ in the question.

A particular $m$ has a probability $p^{|m|}\;(1-p)^{320-|m|}$ . These probabilities sum to $1$, independent of $p$ . We derive $$E(|H(m)|)\ =\sum_{m\in\{0,1\}^{320}}p^{|m|}\;(1-p)^{320-|m|}\;|H(m)|$$

That is a precisely defined real number (a rational when $p$ is rational), which depends only on the definition of SHA-1, and on $p$.

For $p=0$, $E(|H(m)|=|H(0^{320})|=|_{^{\mathtt{B80DE5D138758541C5F05265AD144AB9FA86D1DB}_h}}|=78$, bias $78/82$;
For $p=1$, $E(|H(m)|=|H(1^{320})|=|_{^{\mathtt{F443319695979917A03B717049235423874D2716}_h}}|=73$, bias $73/87$.

We know no practical way to exactly compute that sum for any other value of $p$ , because there are $2^{320}$ terms all with non-zero $p^{|m|}\;(1-p)^{320-|m|}$, and as far as we know each requires computation of a SHA-1 to get $|H(m)|$ . Except for values of $p$ exceedingly close to $0$ or $1$, we can't even tell if that sum is below or above $80$ (equivalently: if the conditioned output is biased towards 0 or 1); nothing that we know about SHA-1 allows that.

For all practical purposes, the question's conditioned generator is unbiased.

Note: the generator that alternatively outputs $0$ and $1$ also is unbiased. This illustrates that unbiasedness (bias close to 1 per the question's definition) is not a sufficient condition for a generator to be secure. The question's generator is secure and practically indistinguishable from a source of random bits (baring a new break of SHA-1), but the reasoning to conclude that has nothing to do with bias; see below.


On the conditioned generator's security

To conclude that the generator is secure (taken as: not distinguishable from true unbiased independent random bits), we observe that probability for an adversary to guess a 320-bit input are at best $\max(p,1-p)^{320}<2^{-235}$. As an example consequence, there's probability $<2^{-45}$ than any of $2^{100}$ values of $m$ occurs has hash input in $2^{90}$ conditioned hash outputs; and a distinguisher exploiting that remote possibility would need to have computed the $2^{100}$ hashes, or exploit yet unknown weakness of SHA-1 (allowing to deduce something about the input from the output better than by hashing a conjectured input and comparing to the output).

If the hash is unbroken, and fed with blocks of $b$ random secret independent bits each with probability $p$, our security level against any distinguishing attack of the output is, conservatively, at least $$-\log_2(\max(p,1-p))\cdot b/2 \text{ bit}$$ $-\log_2(\max(p,1-p))$ is the question's min. entropy. Here, for $b=320$ and $p=0.6$, we get about 118-bit security (discounting unknown weakness in SHA-1).

Note: That works for any unbroken hash (or CSPRNG) used to condition a TRNG, including if there is more bits in the output than entropy in the input, as would be the case if we replaced SHA-1 with SHA-512, still hashing 320 biased bits to get 512 conditioned bits. This illustrates the so-called "full entropy" condition is not necessary for security; it's not sufficient either.

Note: If we had $p=0.9$, the question's generator would be practically distinguishable from random: we pre-compute the 160-bit SHA-1 hash of the $2^{20}$ most likely 320-bit inputs, and watch for occurrence of any of these bitstrings in the conditioned generator's output. There's good chance that happens in $2^{40}$ bits, and we'll practically never falsely incriminate a true uniform random source. That's a break of the conditioned generator, with possibly practical consequences. Yet, the bias as per the first part of the answer is still entirely undetectable. This further illustrates unbiasedness is not sufficient for security.

$\endgroup$
2
$\begingroup$

Let's call the output of your TNRG $X$—this is a random variable taking the values 0 and 1, with $\Pr[X = 0] = 0.4$ and $\Pr[X = 1] = 0.6$, so that $H_\infty[X] = -\log_2 0.6 \approx 0.737$ bits. This induces the random variable $Y = \operatorname{SHA-256}(X)$, which has

\begin{align*} \Pr[Y = \operatorname{SHA-256}(0)] &= 0.4, \\ \Pr[Y = \operatorname{SHA-256}(1)] &= 0.6. \end{align*}

Since $\operatorname{SHA-256}(0) \ne \operatorname{SHA-256}(1)$, we clearly have $H_\infty[Y] = H_\infty[X]$.

What if we have a set of observations $\{X_i\}_i$, which are independent and identically distributed? Then, e.g.,

\begin{align*} \Pr[X_0 = 0, X_1 = 0] &= 0.4^2 &&= 0.16, \\ \Pr[X_0 = 0, X_1 = 1] &= 0.4 \times 0.6 &&= 0.24, \\ \Pr[X_0 = 1, X_1 = 0] &= 0.6 \times 0.4 &&= 0.24, \\ \Pr[X_0 = 1, X_1 = 1] &= 0.6^2 &&= 0.36. \end{align*}

I leave computing the entropy of the tuple $(X_0, X_1)$ as an exercise for the reader. What about $\operatorname{SHA-256}(X_0 \mathbin\Vert X_1)$? Since SHA-256 has no collisions on $00$, $01$, $10$, $11$, once again the entropy is preserved.

In fact, the entropy is not preserved only if there is a collision in the possible inputs. Obviously the entropy is at most 256 bits for the output of SHA-256 on a single input. How many distinct outputs are there? Nobody knows for SHA-256, but for a uniform random function $F\colon \{0,1\}^{256} \to \{0,1\}^{256}$, the expected fraction of distinct outputs is about half the total output space—specifically, $1 - e^{-1}$. So you might estimate a maximum min-entropy of about 255 bits, in the best case of a perfectly uniform input.

However, you're not limited to feeding in 256 bits; you could feed in 512. If you feed in $256 + k$ bits to a uniform random function 256-bit function, the expected fraction of distinct outputs is about $1 - e^{-2^k}$ which very rapidly approaches 1 as $k$ grows. The min-entropy of $(X_0, X_1, \dots, X_{511})$ is obviously $-\log_2 0.6^{512} \approx 377 \gg 256$ bits. While passing 512 bits through SHA-256 may not necessarily cover the entire 256-bit output space and may not attain the full possible entropy of 256 bits, it's probably a pretty safe bet that the entropy is close enough to 256 bits that the difference doesn't matter to you. This is plenty to use as a key for a PRNG for cryptographic work.

$\endgroup$
  • $\begingroup$ Sorry, I'm struggling to see the answer here. So what's the output bias? $\endgroup$ – Paul Uszak Mar 4 '18 at 22:14
  • $\begingroup$ Absent publication-worthy analysis of SHA-256, the best we can say is what the expectation value of the entropy of $F(X)$ is, integrated over all possible 256-bit functions $F$ with equal weight; then we can use this as a guess for what the entropy of $\operatorname{SHA-256}(X)$ is. If the entropy of $X$ is significantly larger than 256, e.g. if you use 512 independent 60/40 coin flips so that the entropy of $X$ is about 377 bits, then the expectation value of the entropy of $F(X)$ is probably negligibly less than 256. $\endgroup$ – Squeamish Ossifrage Mar 4 '18 at 23:30
  • $\begingroup$ Ah right. I'm looking at exactly how much less than 377 in numerical form. Perhaps I didn't make the question clear. Can you quantify "negligibly" please so I can compare my TRNGs to others? $\endgroup$ – Paul Uszak Mar 5 '18 at 14:05
  • $\begingroup$ @PaulUszak How about ‘between 255 and 256 bits’? $\endgroup$ – Squeamish Ossifrage Mar 6 '18 at 3:16

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.