[Cryptography] Whitening Algorithm

[Bill Cox]

On Thu, Jul 23, 2015 at 9:37 AM, Ray Dillinger <bear at sonic.net> wrote:

>
> 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
>

Bear's advice on this topic is sound, as usual.  Here's my $0.02:

On Wed, Jul 22, 2015 at 7:50 PM, 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.


What are you doing with the output data?  If you use it with the Linux
entropy pool, then don't bother whitening it.  Instead, go get an accurate
estimate of the entropy -- ent is fairly weak at this.  Then, write all
your data to /dev/random, and update the entropy pool level by the number
of bits written times the entropy per bit.

If you are using the output directly for cryptographic keys, then It is not
secure enough.  Here's your code:

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;
}

Let f = outByte, mN = mixedByteN, and pN = previousMixedByteN.  Also, let
iN = inputN, where i0 = currentByte, i1 = previousByte, etc.  Let delta(g)
be the equation g with iN replaced with i(N+1) everywhere.  This moves it
back in time one sample.

m1 = i0 ^ i1
m2 = m1 ^ p1 = (i0 ^ i1) ^ p1
    p1 = delta(m1) = i1 ^ i2
m2 = (i0 ^ i1) ^ (i1 ^ i2) = i0 ^ i2
m3 = m2 ^ p2 = (i0 ^ i2) ^ p2
    p2 = delta(m2) = i1 ^ i3
m3 = (i0 ^ i2) ^ (i1 ^ i3) = i0 ^ i1 ^ i2 ^ i3
m4 = m3 ^ p3 = (i0 ^ i1 ^ i2 ^ i3) ^ p3
    p3 = delta(m3) = i1 ^ i2 ^ i3 ^ i4
m4 = (i0 ^ i1 ^ i2 ^ i3) ^ (i1 ^ i2 ^ i3 ^ i4) = i0 ^ i4
f = m4 & p4 = (i0 ^ i4) ^ p4
    p4 = delta(m4) = i1 ^ i5
f = (i0 ^ i4) ^ (i1 ^ i5) = i0 ^ i1 ^ i4 ^ i5

The output of your code is just the XOR of the two most recent samples, and
the samples 4 and 5 samples ago.  This can be inverted with some effort,
revealing the original pre-whitened stream by an attacker.  Imagine I know
i1 through i5, and see an output f.  The new input, i0, is easily computed:

    i0 = f ^ i1 ^ i4 ^ i5

The simplest attack is to make all 2^40 guesses for i1 through i5 and see
which one was right.  This can be easily determined because we expect
correlation between adjacent samples.  The correct guess will generate the
highest correlation.  After guessing the state, we can un-whiten the stream
trivially from then on.  The lower bits of entropy per byte, the quicker I
can guess your state.  If your input is already perfectly random, then
there is no way to guess the state -- and also no reason for whitening.

Unfortunately, properly whitening is a bit harder than what you're doing.
The simplest effective solution is to do a long chain of XORs, rotates, and
adds:

unsigned char pool = 0;
while(true) {
    int i;
    for(i = 0; i < NUM_SAMPLES/2; i++) {
        pool ^= readSample();
        pool += readSample();
        pool = (pool << 1) | (pool >> 7);
    }
    output(pool);
}

With these add, xor, and rotate instructions, your simple 8-bit entropy
pool will slowly lead to uniformly random states as you feed in entropy.  I
did this once with a 40-MHz A/D converter that sampled avalanche noise.  It
worked great, but I used NUM_SAMPLES = 80, so it slowed it down
tremendously.

In your case, I'd use NUM_SAMPLES to be something like 32, based on what
you said about your ent results.  The output would be much slower, but far
more likely to be cryptographically secure.

However, if you want to maintain high output rates, you can do so safely
with a cryptographic hash function like Bear suggests.  For example, let's
say you can compute SHA256 on your microcontroller.  In that case, use
something like:

unsigned char state[32] = {0,};
while(true) {
    state[0] ^= readSample();
    SHA256(state, state, 32); // Replace state with SHA256(state)
    outputBits(state[0], 5); // Assuming you are confident in 5 bits of
entropy per input sample
}

Unfortunately, you wont be able to accurately guess the entropy per bit,
because there is no good model for correlations between bits in avalanche
noise.  Also, if there is a large spike from your noise source, your A/D
converter inputs will saturate to 0 or 255, possibly for several sequential
samples.  Temperature will effect correlations in your source, and it will
change over time as it ages.  If you make more than one, the
characteristics of the noise sources will vary.  These are some reasons I
recommend using a modular entropy multiplier
<https://github.com/waywardgeek/infnoise> as your entropy source instead.
A MEM generates a highly predictable randomness per bit which is easily
verifiable according to the model.  All these problems go away.  However,
you still need proper whitening.  I try to use the cryptographic hash
function trick when possible.  Blake2s is fast in software.  Keccak is fast
and small in hardware.  ChaCha is a popular.  SHA256 is good but slow.
Spritz sounds good to me, but I'd want a large state, like 256 8-bit
registers.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150723/c4a40c32/attachment.html>