The AVR series microcontrollers are a collection of cheap and versatile chips that are used in many applications ranging from hobbist projects to commercial infrastructure. One major problem for some hobbists is the lack of secure random number generation on the Arduino platform. The included pseudo-random number generator (PRNG) is very easy to defeat and is useless for any crypto-related uses. One recommendation from the Arduino Reference Manual is to use atmospheric noise from the chip's analog sensor pins as seed data[6].
Unfortunately this method is extremely weak and should not be used to emulate a true random number generator (TRNG). Existing methods such as using the internal timer drift or using a dedicated generator are either too slow, requires extensive external hardware or modifications to the microcontroller's internal mechanisms[1][3], which can make some other features unavailable to the user. In this article we will explore two better methods to generate true random numbers from the Arduino that are both fast, less predictable and less prone to external attack.
Randomness is present everywhere, from the flow of water out of a sink to a dice roll. To succesfully model physical phenomenon or secure data using cryptography, a good source of true random numbers is necessary. Due to the deterministic nature of processors, it is almost impossible to generate true random numbers using only processor instructions.
In the early days, true random numbers were generated by recording noise in the physical world and was saved in a table for later use by a computer. But even to this day, true random number generation hardware is slow when processors are now running in the gigahertz, not to mention that they are very costly, usually beyond what a hobbist is willing to pay. PRNGs are very fast, but as they are deterministic, they can be predictable and are not suitable for sensitive applications.
As more people are interested in the fields of stochastic simulation and cryptography, and seek cheap platforms to tinker around as a hobby, the Arduino platform should be able to at least be able to close the gap between affordability and quality.
The Arduino Reference Manual suggests using an "random" value from the analog pin when initialising the seed for its PRNG, but since the resolution of the chip's ADC is only 10-bit, there are only 210 different seeds. 1024 is a small number and is cannot whistand a brute force attack. In the works of B. Kristinsson, it is determined that the output from analogRead() is not statistically random and cannot be used as-is without modification[2].
We will outline two simple and fast methods of extracting entropy from the arduino analog pin and using a commonly available sensor, the MPU6050 Accelerometer.
Fig 1.1 True RNG vs Bad RNG
Source: https://www.random.org/analysis/
Unless otherwise specified, all experimental data is collected using an Arduino Mega2560 development board
It is common knowledge that the level of entropy from using the analogRead() method on floating pins is very low, as they are only 210 possible values and their overall amplitude changes very slowly. One can try extracting randomness directly from the analog pins by taking the least significant bit of analogRead(), but this naive method is flawed. A quick visual check reveals the periodicity of its output.
Pseudocode
while (have less than 8 bits stored)
store the least significant bit of analogRead()
wait for an arbitrary amount of time
Fig 1.2 Sampling intervals of 4, 16, 128, 256, 1024 microseconds
However, one region of interest might around 256us, where the data seems to be less periodic.
Fig 1.3 Sampling intervals of 192, 256, 320 microseconds
See Appendix for more sampling intervals
We will not delve deeper into this phenomenon in this article as the factors causing this are very complex. We suspect a mix of ambient interference, internal clocks and changes in power usage caused by processor instructions. If it is indeed caused by internal factors, direct sampling as-is is definitively not suitable for random number generation as it is vunerable to side channel attacks and timing attacks.
Nonetheless, we can improve upon such a straightforward method.
We define a Von Neumann extractor as a transformation that maps a non-uniform bitstream into a uniform bitstream by presuming that rising edges (01) are as probable as falling edges (10) and that there is no correlation between successive bits. Such a transformation can help us get rid of the low frequency periodic components of the previous method. We sample two bits at a time, and store the first bit if and only if the two bits are not equal.
while (have less than 8 bits stored)
bit1 := LSB of analogRead()
wait for an arbitrary amount of time
bit2 := LSB of analogRead()
if bit1 != bit2
store bit1
wait for an arbitrary amount of time
Fig 1.4 Sampling intervals of 64, 128, 256 microseconds
This method is very slow, as we sample the ADC twice for a single bit and we might ignore a large number of bits. As we decrease the sample rate below 16 microseconds, we drop too many bits, wasting processor cycles and when we increase it beyond 256us, we wait too much. Even so, this might be appropriate as a straightfoward way of generating true random numbers on the Arduino platform.
A big drawback of the previous method is its speed. We would like a faster method to generate random numbers without constantly sampling the analog pins, ideally at least 1 bit per analogRead(). We could implement an recursive AMLS version, but it is not cost effective concerning its speed for our purposes. To achieve a better method we will need to take advantage of two properties concerning the previous methods.
- Direct sampling is a good source of local randomness, since its least significant bits changes very quickly. However, it exhibits periodic behaviour in low frequencies, which is undesirable for generating long sequences.
- The Von Neumann extractor is a good source of reliable and uniform random bits. Since it is very slow and requires occasionally many samples to output a single bit, we will only consider it as a good source of global randomness. It is unsuitable for quick generation of short random sequences.
We will take advantage of both the local randomness of the direct sampling method and the global randomness of the Von Neumann extractor method combined with a quick method to extract the most entropy possible from the higher bits of the analogRead() function.
Let us define a function rotate() pushes bits n times inside a ring buffer.
function rotate(byte b, byte n)
return (b << n) OR (b >> (8-n))
A small example of the output of this function:
Input: b = 01001011
| n | output |
|---|---|
| 0 | 01001011 |
| 1 | 10010110 |
| 2 | 00101101 |
| 3 | 01011010 |
| 4 | 10110100 |
| 5 | 01101001 |
| 6 | 11010010 |
| 7 | 10100101 |
| 8 | 01001011 |
The first bit of the input is highlighted
The first step of our method consists of sampling the analog pin 8 times, rotate each sample's 8 least significant bits by an incrementing counter and XORing them together at the end, essentially "shuffling" the bits around. This will resolve the problem of the upper bits not changing as quickly as the lower bits and remove any temporal bias from analogRead(). We will call this as XOR-Rotation for the remainder of the article.
bits := 0
for i=0 until 8 (exclusive)
sample := 8 least significant bits from analogRead()
bits := bits XOR rotate(sample, i)
wait for an arbitrary amount of time
Note: An interesting property of this method is the ability for the user to choose the sample rate. A slower sample rate will yield a better random result (due to internal interference having less impact on the randomness of analogRead()) while a faster sample rate guarantees a quick response. This will generate 8 random bits within a reasonable amount of time.
We will also improve the statistical properties of the XOR-Rotation algorithm by combining it with a quick 8-bit XORShift[7] PRNG. In this case the small period cycle of a 8-bit PRNG does not matter since we will be re-seeding it at each step.
lastBits := last 8 bits obtained from XOR-Rotate, initially set at 0x00
function xorRotateRandom()
bits := 0
for i=0 until 8 (exclusive)
sample := 8 least significant bits from analogRead()
bits := bits XOR rotate(sample, i)
wait for an arbitrary amount of time
lastBits := lastBits XOR (lastBits >> 3) XOR (lastBits << 5) XOR (lastBits >> 4); //One round of XORShift PRNG algorithm for statistical stability
lastBits := lastBits XOR bits //Reseed the PRNG with TRNG values
return lastBits
However, we still have the problem that directly sampling from analogRead() has a low frequency periodic component which causes value bias in the bits generated by XOR-Rotation. Since the Von Neumann extractor exhibits good Global randomness, we will integrate it in our method as a slow changing source of randomness. The main idea behind our method is instead of waiting for the Von Neumann extractor to output bits as a constant source, we use it as a "seed" for our XOR-Rotate method.
lBuf := buffer of 8 bits, initialised with 0x00
rBuf := buffer of 8 bits, initialised with 0x00
lastBits := last 8 bits obtained from this XOR-Rotate, initially set at 0x00
function trueRotateRandom()
bits := 0
lastBuf := lBuf XOR rBuf;
for i=0 until 4 (exclusive)
wait for an arbitrary amount of time
leftSample := 8 least significant bits from analogRead()
wait for an arbitrary amount of time
rightSample := 8 least significant bits from analogRead()
bits := bits XOR rotate(leftSample, i)
bits := bits XOR rotate(rightSample, 7 - i) //Rotate backwards to prevent LSB bias
for j=0 until 8 (exclusive)
leftBit := j-th bit leftSample
rightBit := j-th bit rightSample
if leftBit != rightBit
if lastBuf is even //Insert the bits randomly from either start or end to prevent LSB bias
(insert leftBit in the lBuf buffer from the start)
else
(insert leftBit in the rBuf buffer from the end)
lastBits := lastBits XOR (lastBits >> 3) XOR (lastBits << 5) XOR (lastBits >> 4); //One round of XORShift PRNG algorithm for statistical stability
lastBits := lastBits XOR bits //Reseed the PRNG with TRNG values
return lastBits XOR lBuf XOR rBuf //Further seed the TRNG with Von Neumann extractor values for global randomness stability
This improved method generates random numbers that are uniform, and is robust to external interference (such as an electrically charged object passing by the pins) and is very quick.
C++ code, experimental data and Diehard test logs can be found in the Appendix.
The MPU6050 is a multipurpose Accelerometer and Gyroscope sensor module for the Arduino, it can read raw acceleration from 3 axis and raw turn rate from 3 orientations. To our surprise, its acceleration sensor's noise level far surpasses its resolution, with at least 4 bits of recorded entropy.
A naive approach to generate a random byte would to directly take the 4 least significant bits of the x and y axis, XORed with the z axis LSBs.
//X, Y, Z are 4-bit values from each axis
randomByte := ((Y ^ Z) << 4) | (X ^ Z))
Unfortunately this method is flawed as the distribution and bias of the noise is different and unpredictable between axes, not to mention other sensors of the same model. A simple fix would be to discard some bits and only use 2 bits from each axis, but that would yield only 6 bits of noise per reading, making it impossible to generate a 8-bit number with only one data sample of the accelerometer.
However with clever transposition, we can achieve 8 bits of randomness using 4 bits that are not necessarily the same magnitude from each axis. We are supposing that the upper 2 bits are not always reliable, so we will XOR each axis' higher 2 bits with another axis' lower 2 bits, and vice-versa. An important property to note is the "piling-up lemma"[4], which states that XORing a good random source with a bad one is not harmful. Since we have 3 axis, each having 4 bits, we will obtain 8 bits at the end. This operation is similar to Convolution.
randomByte := ((X & 0x3) << 6) ^ (Z << 4) ^ (Y << 2) ^ X ^ (Z >> 2)
Output:
Fig 3.1 Final output
This final method achieves state of the art performance for True Random Number Generation on the Arduino, with our tests providing us around 8000 random bits per second on an Arduino Uno.
Diehard test:
| Arduino random() | Method 1 | |
|---|---|---|
| BIRTHDAY SPACINGS | PASSED | PASSED |
| OPERM5 | PASSED | PASSED |
| BINARY RANK 31x31 | PASSED | PASSED |
| BINARY RANK 32x32 | PASSED | PASSED |
| BINARY RANK 6x8 | PASSED | PASSED |
| BITSTREAM | PASSED | PASSED |
| OPSO | PASSED | PASSED |
| OQSO | PASSED | PASSED |
| DNA | PASSED | PASSED |
| COUNT-THE-1 | PASSED | PASSED |
| COUNT-THE-1 SPECIFIC | PASSED | PASSED |
| PARKING LOT | PASSED | PASSED |
| MINIMUM DISTANCE | PASSED | PASSED |
| 3DSPHERES | PASSED | PASSED |
| SQUEEZE | PASSED | PASSED |
| OVERLAPPING SUMS | PASSED | PASSED |
| RUNS | PASSED | PASSED |
| CRAPS | PASSED | PASSED |
Experimental data and Diehard test logs can be found in the Appendix.
In this article we provided the reader two possible methods of achieving fast true random number generation on the Arduino. With some clever modifications, even the analogRead() is usable as a source of entropy. Still, it is preferable to use the method that uses a cheaply available Accelerometer as a faster source of randomness. We highly encourage the reader to try improving the methods outlined in this article themselves as an exercise.
The C++ code will be released shortly.
The second method requires the Arduino-MPU6050 library[5]
Method 1 Diehard test log
Method 2 Diehard test log
Arduino random() Diehard test log
Method 1 Collected data (10MB Download)
Method 2 Collected data (10MB Download)
Arduino random() Collected data (10MB Download)
Naive sampling at intervals of 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 microseconds
Naive sampling at intervals of 192, 256, 320, 384 microseconds
Von Neumann extractor sampling at intervals of 16, 32, 64, 128, 256 microseconds
(1) Josef Hlavac et al., True Random Number Generation on an AtmelAVR Microcontroller
(2) Benedikt Kristinsson, Ardrand: The Arduino as a Hardware Random-Number Generator
(3) endolit, Arduino hardware true random number generator
(4) Matsui, Mitsuru, Linear Cryptanalysis Method for DES Cipher
(5) jarzebski, MPU6050 Triple Axis Gyroscope & Accelerometer Arduino Library
(6) Arduino Online Reference > Random
(7) George Marsaglia, Xorshift RNGs
Just what I was looking for!