2
$\begingroup$

Let's suppose I want to do One-Time-Pad but I only have a biased true random number generator (TRNG).

I XOR to the ciphertext block with another with random data got from the TRNG, e repeat the process two or more times with different random blocks.

Will this scheme make the One-Time-Pad more secure? Will this provide the same security as if was done with a non-biased TRNG?

$\endgroup$
2
  • 2
    $\begingroup$ Given that XORing the block to be encrypted $n$ times with different random blocks is equivalent to XORing it once with the XOR of all the $n$ random blocks, a more fruitful way of rephrasing this question might be "(how much) does XORing $n$ blocks of biased random bits together reduce the bias?" Also, FWIW, this process (and other similar techniques for improving TRNG quality) is commonly known as "whitening". $\endgroup$ May 11 at 10:47
  • $\begingroup$ More efficient approach and perfectly unbiased assuming independence of coin flips: flip twice for each bit and set the bit to 0 iff the flips are the same. $\endgroup$ May 12 at 1:22

3 Answers 3

10
$\begingroup$

Better than using it once, but not as good as an unbiased TRNG.

To see this, suppose our TRNG is very biased, producing a zero 10% of the time and an one 90% of the time.

If we use the TRNG twice, for each bit we have four possibilities:

  • Both times we get a 0 from the TRNG. This will occur 10% * 10% = 1% of the time.
  • The first time we get a 0 and the second time we get a 1: This will occur 10% * 90% = 9% of the time
  • The first time we get a 1 and the second time we get a 0: This will occur 90% * 10% = 9% of the time
  • Both times we get a 1 from the TRNG. This will occur 90% * 90% = 81% of the time.

So after the XOR, the first and last cases produce a 0, and the second and third cases produce a 1. So 82% of the the time we get a 0 and 18% of the time we get a 1. So the result is still a biased TRNG, but not as bad as the original TRNG. If you repeat this enough times, you could get close enough to 50/50 that it wouldn't matter in practice. A less biased TRNG would get there quicker, but the same principles would apply.

$\endgroup$
0
8
$\begingroup$

The convergence of your suggested process towards unbiased bits is guided by the Piling Up Lemma. It will be slow. It is more efficient to use unbiasing procedures such as von Neumann unbiasing. See for example this question

But this is of course simpler due to direct XOR.

For $n$ independent identically distributed $\{0,1\}$ valued random variables, $X_1, X_2, \ldots X_n$:

$$ Pr(X_1 \oplus \ldots \oplus X_n = 0) = \frac{1}{2} + 2^{n-1} \prod_{i=1}^n \epsilon_i $$ where $\epsilon_i$ is the bias of $X_i.$ This gives the final bias as

$$ \epsilon_{1,2, \ldots, n} = 2^{n-1} \prod_{i=1}^n \epsilon_i $$

For each bit of your combined blocks, and taking the example of bias $\epsilon_i = 0.4$ for $i=1,\ldots, n$ (corresponding to the 90% in the other answer) we get biases as below

\begin{array}{c|c|c} \textrm{Number of } & \textrm{Resulting Bias} & \textrm{Probability of 1} \\ \textrm{combined blocks ($n$)} & & \\ 2 & 0.32000 & 82.0\% \\ 4 & 0.20480 & 70.4\% \\ 8 & 0.083886 & 58.4\% \\ 16 & 0.014074 & 51.4\% \end{array}

FYI, this slow convergence due to the $2^{n-1}$ factor is the reason linear cryptanalysis works.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer, but I had to choose the other answer as "best answer" because I'm very newbie into cryptography and I didn't understand your formulas very well. $\endgroup$ May 10 at 22:47
  • 2
    $\begingroup$ No problem at all. The formulas show what happens in the general case $\endgroup$
    – kodlu
    May 10 at 23:33
3
$\begingroup$

Pretty much yes.

Many TRNG designs are based entirely on digital circuitry, and do not involve any analogue components [see note]. It makes them simpler to incorporate on silicon. But unfortunately digital circuitry tends to perform digitally and is therefore quite poor at generating entropy. So rather than giving you a theoretical example, here's a real TRNG with very very poor bias:-

This is from a paper building an FPGA TRNG.

pll

Notice the Decimator. It's role is to successively XOR $K_D$ samples together in order to increase the entropy per output sample. In this case, $K_D=7$, effectively XORing seven OTPs together from your perspective. Later in that paper, $K_D$ reaches 185 for another design. That's 185 biased TRNG samples XORed together using the Piling up lemma. I can't find the reference for you, but I've seen a decimation ratio of 512 in a ring oscillator TRNG.

So you'll find that successive multiple XORing is common in all digital TRNGs in the form of decimation. It avoids more complex entropy extraction techniques such as hashing which require more silicon real estate.


Note. I'm positing that in this case purely digital circuitry exists, whilst realising that all circuitry is basically analogue at the micro scale.

$\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.