<div dir="ltr">Summary: We're not quite ready for generating random numbers for crypto on Arduinos, at least not without a TRNG shield.  Two libraries for generating true random numbers are <a href="https://code.google.com/p/tinkerit/wiki/TrueRandom">TrueRandom</a>, and <a href="https://gist.github.com/endolith/2568571">probably_random</a>.  If you _have_ to generate key material on an Arduino, it looks like you can do an OK job of it in about 1 minute.<div><br></div><div>The most popular technique for generating true random data is to do what TrueRandom does, and drive a voltage onto pin 0, and measure it with the 8-bit ADC.  While sometimes this generates unpredictable data, the scatter plots show scary correlations, and the one thing we know it is not measuring is thermal noise.  Here is a scatter plot built by the author of probably_random:</div><div><br></div><div><img src="cid:ii_152332c1196bacb8" alt="Inline image 1" width="472" height="258"><br></div><div><br></div><div>The 8-bit ADC in this application does not have enough resolution to reliably detect any thermal noise.  It is more likely measuring power supply noise, which could be under the control of the machine powering the Arduino.  This scatter plot has issues even though some whitening was applied, so reality is probably much worse.</div><div><br></div><div>I like the probably_random page.  The author says, "Disclaimer: I have no idea what I'm doing."  Honestly, he did a fairly decent job, and only went wrong when it came time to guess the level of entropy per sample.  This is fairly good work overall.  On the down side, he is generating only 64 bits per second, and as we'll see, that is a bit too fast, since there isn't quite enough entropy there to reliably extract 64 bits/s.</div><div><br></div><div>Probably_random 8 reads from the timer to produce one byte, rotating and XORing each 8-bit sample.  The README states that we assumes there is at least one bit of entropy per byte, and the scatter plots look unpredictable.  However, at least on my Arduino Uno, extracting 64 bits per second is most likely pushing faster than the timer can integrate jitter noise.  Here's a plot from his web site:</div><div><br></div><div><img src="cid:ii_15233338322eba9a" alt="Inline image 2" width="256" height="256"><br></div><div><br></div><div>That looks pretty good!  However, I prefer to see pre-whitened data to get a feel for how much real entropy is there from the start.  You can make the data look random, but you can't make it actually random.  The rotating and XORing simply hides too much.  Here's a plot using his tester.py code when I output every sample from the timer without mixing 8 together:</div><div><br></div><div><img src="cid:ii_15233369948c5c40" alt="Inline image 3" width="256" height="256"><br></div><div><br></div><div>This was generated from 65536 8-bit samples from the timer, which normally would be condensed to 65536 output bits.  Is it true that there is a least 1 bit of entropy per sample?  I could use ent, but ent is absolutely terrible for finding patterns like we see here.  Ent thinks this plot is very random.  So, I examined the data manually, and found that most of the time, given two sequential bytes, I could predict the next byte, by examining previous cases in the stream.  Clearly most bytes have less than one bit of entropy.  However, _some_ bytes buck the trend and have a value that rarely follows the prior two.  The entropy in those bytes is far higher, so the average can still be over 1.  <a href="https://github.com/waywardgeek/predict">Here is a program I hacked together</a> to determine an upper bound for entropy per byte in probably_random.  Here's its output when run on about 120K samples:</div><div><br></div><div><div>./predict16 foo</div><div>There seems to be at most 1.029738 bits per byte in this sample</div><div>Based on 122368 total samples</div><div>num bins: 4795, average hits per bin: 25.52</div></div><div><br></div><div>There is a more non-randomness that my program is not finding, which I suspect I could find if I put in a few days of effort.  For example, different 3-sample sequences appear more frequently near each other than far apart in the sample stream, likely due to whatever global parameters are drifting to cause the trends we see in the plot above.  So, to be safe, we need at least 2X margin, so we should back off to 32 bits/s when using probably_random.  However, this does not take into account variation in jitter from device to device, or over temperature, or what happens when running of a nice quiet battery, rather than a noisy laptop USB port.  To account for these variables, I would prefer to back off another factor of 4X: 2X for process variation, and 2X for the differing environments the Arduino runs in.</div><div><br></div><div>So, I recommend extracting only 8 bits of entropy per second, base on the limited data I saw today.  I prefer no whitener on the Arduino, and instead would feed the timer samples into a cryptographic sponge, like Keccak-1600, but you can use the current probably_random output as-is if you change one line:</div><div><br></div><div>void loop()<br></div><div><div>{</div><div>  if (sample_waiting) {</div><div>    sample_waiting = false;</div><div><br></div><div>    result = rotl(result, 1); // Spread randomness around</div><div>    result ^= sample; // XOR preserves randomness</div><div><br></div><div>    current_bit++;</div><div>    if (current_bit == 64)  // Was 8, but I want 8X more samples per output</div><div>    {</div><div>      current_bit = 0;</div><div>      Serial.write(result); // raw binary</div><div>    }</div><div>  }</div><div>}</div></div><div><br></div><div>If you just need numbers as a seed for a game or something, where there is no money on the line, feel free to use the original version.  As the author says, it is _probably_ random :)</div><div><br></div><div>Bill</div></div>