[Cryptography] TRNG review: Arduino based TRNGs

Bill Cox waywardgeek at gmail.com
Mon Jan 11 20:10:37 EST 2016


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 TrueRandom
<https://code.google.com/p/tinkerit/wiki/TrueRandom>, and probably_random
<https://gist.github.com/endolith/2568571>.  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.

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:

[image: Inline image 1]

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.

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.

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:

[image: Inline image 2]

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:

[image: Inline image 3]

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.  Here is a program I hacked
together <https://github.com/waywardgeek/predict> to determine an upper
bound for entropy per byte in probably_random.  Here's its output when run
on about 120K samples:

./predict16 foo
There seems to be at most 1.029738 bits per byte in this sample
Based on 122368 total samples
num bins: 4795, average hits per bin: 25.52

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.

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:

void loop()
{
  if (sample_waiting) {
    sample_waiting = false;

    result = rotl(result, 1); // Spread randomness around
    result ^= sample; // XOR preserves randomness

    current_bit++;
    if (current_bit == 64)  // Was 8, but I want 8X more samples per output
    {
      current_bit = 0;
      Serial.write(result); // raw binary
    }
  }
}

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

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160111/21ac3ffa/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 109781 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160111/21ac3ffa/attachment-0003.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 108463 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160111/21ac3ffa/attachment-0004.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 66602 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160111/21ac3ffa/attachment-0005.png>


More information about the cryptography mailing list