3
$\begingroup$

I have a hardware RNG that sends me some random bits. Due to nature of that RNG, the source is biased. Then, the bitstream is processed in a following way to remove the bias:
two counters are used, which count amounts of 1's and 0's in the stream and when the difference is above the threshold, the next bit out ot the rng is forced to either 0 or 1.
I have concerns about this. This just means that we have directly introduced some dependency of future bits on past bits, which totally destroys randomness, right? Is this a valid concern? If yes, what are proper ways to deal with bias in RNG?

$\endgroup$
  • $\begingroup$ Perhaps you should ask whoever implemented this. I'm not sure what they wanted to achieve. $\endgroup$ – Yuval Filmus Dec 19 '17 at 11:28
  • $\begingroup$ Presumably the counters are rest after emitting a bit. Perhaps you can take a second look and describe the entire algorithm? $\endgroup$ – Yuval Filmus Dec 19 '17 at 11:29
  • $\begingroup$ unfortunately I can't aske the implementor. I've modified the description a little. The idea of this addition is to remove the bias of the rng source $\endgroup$ – artemonster Dec 19 '17 at 13:28
  • $\begingroup$ Have you checked whether the counters are reset after emitting a bit? $\endgroup$ – Yuval Filmus Dec 19 '17 at 14:06
  • 1
    $\begingroup$ @YuvalFilmus In what circumstance could this be an acceptable way of post-processing the output of a HRNG? Seen through the eyes of a cryptograph(y us)er, this process is anathema. $\endgroup$ – Gilles 'SO- stop being evil' Dec 19 '17 at 22:36
3
$\begingroup$

This just means that we have directly introduced some dependency of future bits on past bits, which totally destroys randomness, right?

Yes.

Let $T$ be the threshold of the process you describe. In a uniform (i.e. non-biased) distribution, the sequence $\mathtt{0}^{T+1}$ would have the probability $2^{-(T+1)}$, like any other sequence of length $T+1$. But the process you describe will flip the last bit, since the threshold of excess $\mathtt{0}$ bits was exceeded, and thus this sequence has the probability $0$. That's a bias. Note that this bias exists regardless of the distribution of the original generator, i.e. the process always makes the generator somewhat worse.

It's pretty apparent if you take this to an extreme. With $T=1$, the output of the process would be an alternating sequence, either $\mathtt{01010101\ldots}$ or $\mathtt{10101010\ldots}$, which is obviously hardly random at all.

This process looks like it was devised by someone who doesn't understand probability. They have a vague intuition that (9,9,9,9,9,9) doesn't look random and so they go out of their way to avoid too many repetitions. But (9,9,9,9,9,9) is not impossible, so any random generator will generate this sequence of length 6 one day, and again, and again… And it will generate (9,9,9,9,9,9,9) if you wait long enough, and (9,9,9,9,9,9,9,9), etc.

The proportion of $\mathtt{1}$ bits in the first $n$ bits should tend towards a bell curve as $n$ tends to infinity. A biased initial source deforms the curve towards one side. The process moves the summit towards the center, but cuts off the sides.

Is this a valid concern?

Yes. Bad random generators sink ships (or save them, as the case may be). One of the ways the Allies broke messages encrypted with the German Enigma during WWII was to rely on lack of randomness because the operators' intuition of randomness led them to introducing biases.

If yes, what are proper ways to deal with bias in RNG?

If you have a random source where each bit has a probability $p$ of being $\mathtt{0}$ and $1-p$ of being $\mathtt{1}$, then there's a rather well-known trick to turn it into a uniform source, which is due to Von Neumann. Read two bits; if they're different then output the first bit and discard the second one; if they're the same then discard both bits and try again. This works well enough with a biased coin because the bias is overwhelmingly due to the design of the coin which doesn't change between tosses. But it assumes that the bits are all independent from one another. This is not a safe assumption for a physical random generator. Even if the underlying physical process is “perfectly” random, imperfections in the construction of the apparatus often have more complex biases, e.g. due to resonance phenomena. The general name for this sort of process is whitening. Von Neumann whitening is typical good enough for physical simulations, but other usage such as cryptography needs more reliable methods.

In computer security, the practical way to construct a random generator is to use a hybrid design.

  1. A random source (ultimately derived from some physical process) provides entropy. It doesn't matter that this source is biased. All that matters is that it has some minimal level of unpredictability, i.e. there is some threshold $p \gt 0$ such that the probability of any given bit being $\mathtt{0}$ is between $p$ and $1-p$.
  2. The entropy is used as a seed to a cryptographically secure pseudorandom number generator (CSPRNG). A CSPRNG is deterministic, but it is infeasible for an adversary to guess any part of its output unless they know the seed. (“Infeasible” means that the adversary trying to guess an output bit gains a negligible advantage from any knowledge that doesn't imply knowledge of the key.)

The resulting distribution is not uniform (since the CSPRNG is deterministic, it can only output a finite subset of all possible sequences, limited by its state size), but it is indistinguishable from a uniform distribution by an adversary with finite processing power.

$\endgroup$

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.