1
$\begingroup$

This is really a follow up question to a comment made regarding How to roll a HWRNG

In the situation of whitening a hardware generated random bit stream, "XORing the two bitstreams should be fine for mixing, by the piling-up lemma" was said. The other bit stream was suggested to be one from a PRNG.

In signal sampling, it is rare to use the full range of ADC bits. This is to avoid clipping the signal or saturating downstream amplification stages. Amplifier internal noise is typically related linearly to the input signal level, so more signal, more stray noise of the unintended variety. So for example in extremis, the hardware may only be sampling with a 1 bit width.

The PRNG will in all likelihood be outputting standard octets.

So the question arises, is

(1 bit HW signal) XOR (8 bits PRNG output)

sufficient to whiten a hardware random number generator, simultaneously ensuring that it's still a hardware generator rather than just a pseudo generator?

Side question: would the PRNG have to be cryptographically secure or not? Consider that the system's numbers could still not be predicted with a simple RND() type generator due to the unpredictability of the hardware signal.

$\endgroup$
  • 1
    $\begingroup$ How do you define "(1 bit) XOR (8 bits)"? For example, what is 1 XOR 01001110? Is it 01001111, 10110001, 1, or something else? $\endgroup$ – Ilmari Karonen Dec 18 '15 at 1:05
  • 1
    $\begingroup$ @IlmariKaronen Standard 8 bit boolean algebra. 1 XOR 01001110 = 1001111. You've hit the nail on the head. My formula only affects the least significant bit. $\endgroup$ – Paul Uszak Dec 18 '15 at 1:33
3
$\begingroup$

No, this is not a good way to whiten an HWRNG, and it definitely won't give you anything like true randomness.

It is true that the XOR of two independent bitstreams will, indeed, be at least as random as either of the original bitstreams. However by XORing only one bit of hardware randomness into each byte of output, you're effectively padding each bit in the hardware RNG stream with 7 zero bits, making it very non-random even if the original unpadded hardware RNG was perfectly random. You're also not doing anything to fix any possible biases in the hardware randomness except for XORing it with the pseudorandom bits.

In particular, this means that, if an attacker manages to discover the internal state of your PRNG (e.g. via statistical observation of the output, seven eighths of which is completely unaffected by the XOR), then they can trivially predict all but the lowest bit of each byte in the XORed output — and may even be able to guess the last bit with better-than-even probability, if the HWRNG output has less than 100% entropy.

(That last part would still apply even if you fixed your scheme to XOR each bit of the PRNG output with a separate HWRNG bit. To actually achieve proper whitening, you really need to mix multiple HWRNG bits into each single output bit (preferably non-linearly), or at least feed them through a properly designed entropy pool.)

$\endgroup$
  • $\begingroup$ So in a nutshell, you'd need a full 8 bits of entropy signal to XOR with an 8 bit PRNG? $\endgroup$ – Paul Uszak Dec 19 '15 at 0:50
  • $\begingroup$ @PaulUszak: Yes, at a minimum. Even then, while the randomness of the XORed output won't be less than the randomness of the stronger input, if both inputs are weak (e.g. the HWRNG is biased/correlated and the PRNG is not cryptographically secure) then the output might still be weak too. $\endgroup$ – Ilmari Karonen Dec 19 '15 at 1:13

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.