[Cryptography] Whitening Algorithm

Ray Dillinger bear at sonic.net
Thu Jul 23 12:37:27 EDT 2015



On 07/22/2015 07:50 PM, Rob Seward wrote:
>   Hi,
> I’m trying to whiten a random noise source (a reverse biased transistor)
> with a low-powered microprocessor. I figured out a technique that seems to
> work well, and I want to know if there is anything insecure or subpar about
> it.

> (Earlier, I had heard that XORing a random stream with alternating 0s and
> 1s could remove bias. However, this strikes me as very insecure, because an
> attacker could reverse the mask by XORing the mixed stream with the same 01
> mask. 

You are absolutely right.  Thanks for not having to explain that one.

Also, I had used the Von Neumann algorithm
> <https://en.wikipedia.org/wiki/Hardware_random_number_generator#Software_whitening>,
> but this slows output significantly.)

If you whiten input from a biased source, you're always going
to get less output than you had input.  So yes, whitening
inherently must slow output significantly.

> Here’s an illustration of what the algorithm is doing:
> http://imgur.com/itLWNyf
> 
> void loop(){
>   currentByte = readByteFromSource()
> 
>     mixedByte1 = currentByte ^ previousByte;
>   mixedByte2 = mixedByte1 ^ previousMixedByte1;
>   mixedByte3 = mixedByte2 ^ previousMixedByte2;
>   mixedByte4 = mixedByte3 ^ previousMixedByte3;
>   outByte = mixedByte4 ^ previousMixedByte4;
> 
>   Serial.write(outByte);
> 
>   previousByte = currentByte;
>   previousMixedByte1 = mixedByte1;
>   previousMixedByte2 = mixedByte2;
>   previousMixedByte3 = mixedByte3;
>   previousMixedByte4 = mixedByte4;
> }

Eventually transistors burn out.  When that happens
they start producing all 1's.  Or all 0's.  And they
won't announce it ahead of  time.

So consider how it breaks down when your input is biased in
particular ways.  For example, if it's all zeros or all ones.
In the all-zeros case especially, you quickly run into what
most hardware either responds to with NaN or traps as an
error (zero to the zeroth power equals?)  In the all-ones
case, your loop goes on quietly producing highly predictable
output, which is exactly what you don't want it to do.

When a whitening algorithm is run on a repeating string of
zeros (or a repeating string of ones) the "correct" result is
no output, because there is no unpredictability in the input.
If you're getting any other response, you're doing something
besides whitening the input, at least in a cryptographic
sense.

If you need a high ratio of output to somewhat-biased
input, on modest compute requirements, use your somewhat
biased input to seed a cryptographically secure pseudorandom
number generator.  But be sure to use enough of it so
that it actually has at least the same number of
unpredictable bit transitions that the state of the PRNG
has bits.  In practical terms, if you want to seed the
PRNG all in one go, use the output of the Von Neumann
whitener as a seed.

Once you've seeded a CSPRNG, you can run it and use its
output directly. Although it won't really be random, these
algorithms exist because it's very hard to tell they aren't.
Or you can use its output to XOR-mask your biased input:
this still won't be "whitening" your input in the cryptographic
sense, but it'll be indistinguishable from random for
practical purposes.

As a lightweight CSPRNG suitable for devices of modest
compute power, I recommend the 'Spritz' algorithm developed
by Rivest & Schuldt.  Although it's fairly new, it seems
quite good.

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150723/7f7eb2ae/attachment.sig>


More information about the cryptography mailing list