<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Jul 23, 2015 at 9:37 AM, Ray Dillinger <span dir="ltr"><<a href="mailto:bear@sonic.net" target="_blank">bear@sonic.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=""><br></span>As a lightweight CSPRNG suitable for devices of modest<br>
compute power, I recommend the 'Spritz' algorithm developed<br>
by Rivest & Schuldt. Although it's fairly new, it seems<br>
quite good.<br>
<br>
Bear<br></blockquote><br>Bear's advice on this topic is sound, as usual. Here's my $0.02:<br><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">On Wed, Jul 22, 2015 at 7:50 PM, Rob Seward <<a href="mailto:robseward@gmail.com">robseward@gmail.com</a>> wrote:<br>Hi,<br>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. </blockquote><br>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.<br><br>If you are using the output directly for cryptographic keys, then It is not secure enough. Here's your code:<br><br>void loop(){<br> currentByte = readByteFromSource()<br><br> mixedByte1 = currentByte ^ previousByte;<br> mixedByte2 = mixedByte1 ^ previousMixedByte1;<br> mixedByte3 = mixedByte2 ^ previousMixedByte2;<br> mixedByte4 = mixedByte3 ^ previousMixedByte3;<br> outByte = mixedByte4 ^ previousMixedByte4;<br><br> Serial.write(outByte);<br> <br> previousByte = currentByte;<br> previousMixedByte1 = mixedByte1;<br> previousMixedByte2 = mixedByte2;<br> previousMixedByte3 = mixedByte3;<br> previousMixedByte4 = mixedByte4; <br>}<br><br>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.<br><br>m1 = i0 ^ i1<br>m2 = m1 ^ p1 = (i0 ^ i1) ^ p1<br> p1 = delta(m1) = i1 ^ i2<br>m2 = (i0 ^ i1) ^ (i1 ^ i2) = i0 ^ i2<br>m3 = m2 ^ p2 = (i0 ^ i2) ^ p2<br> p2 = delta(m2) = i1 ^ i3<br>m3 = (i0 ^ i2) ^ (i1 ^ i3) = i0 ^ i1 ^ i2 ^ i3<br>m4 = m3 ^ p3 = (i0 ^ i1 ^ i2 ^ i3) ^ p3<br> p3 = delta(m3) = i1 ^ i2 ^ i3 ^ i4<br>m4 = (i0 ^ i1 ^ i2 ^ i3) ^ (i1 ^ i2 ^ i3 ^ i4) = i0 ^ i4<br>f = m4 & p4 = (i0 ^ i4) ^ p4<br> p4 = delta(m4) = i1 ^ i5<br>f = (i0 ^ i4) ^ (i1 ^ i5) = i0 ^ i1 ^ i4 ^ i5<br><br>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:<br><br> i0 = f ^ i1 ^ i4 ^ i5<br><br>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.<br><br>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:<br><br>unsigned char pool = 0;<br>while(true) {<br> int i;<br> for(i = 0; i < NUM_SAMPLES/2; i++) {<br> pool ^= readSample();<br> pool += readSample();<br> pool = (pool << 1) | (pool >> 7);<br> }<br> output(pool);<br>}<br><br>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.<br><br>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.<br><br>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:<br><br>unsigned char state[32] = {0,};<br>while(true) {<br> state[0] ^= readSample();<br> SHA256(state, state, 32); // Replace state with SHA256(state)<br> outputBits(state[0], 5); // Assuming you are confident in 5 bits of entropy per input sample<br>}<br><br>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 <a href="https://github.com/waywardgeek/infnoise">modular entropy multiplier</a> 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.<br><br>Bill</div></div></div>