[Cryptography] Whitening Algorithm

[Ben Laurie]

On Thu, 23 Jul 2015 at 04:57 Rob Seward <robseward at gmail.com> 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. Also, I had used the Von Neumann algorithm
> <https://en.wikipedia.org/wiki/Hardware_random_number_generator#Software_whitening>,
> but this slows output significantly.)
>
> The algorithm mixes new bytes derived from the noise source with previous
> ones in an overlapping manner. Below is the source code, and a link to an
> illustration of the process.
>
> I’ve done some testing, and it appears to transform data that shows as
> much as 5% bias to ~0% while passing ent chi-square. Some less rigorous
> testing with NIST also had positive results.
>
> 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;
> }
>

The repeated XORs make this mildly fishy. For example, if we assume
everything is initialised to 0, then the first byte output is B0, and all
the state bytes are also set to B0.

The second byte out, therefore, is B0 ^ B1, and pmb1 = pmb3 = B0 ^ B1, pmb2
= pmb4 = B1.

Third byte out is B2 ^ B1 and pmb1 = B1 ^ B2, pmb2 = B2 ^ B0, pmb3 = B2 ^
B1 ^ B0, pmb4 = B2.

In other words, I don't think this is doing what you think its doing.

Addition (with carry bit recycled?) might be a better choice.


> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150723/5e666733/attachment.html>