Prev Article — https://medium.com/@LargeCardinal/random-numbers-on-the-arduino-fc34944615b
Tl;Dr — It is possible to generate random numbers on an Arduino, but you have to work for them! Example code below.
Results — use the temperature method if you need something that has plenty of entropy. UPDATE — based on further work here, don’t use the baked in avr-libc LCG for your random numbers. Use something like Salsa20 or Gimli permutation generator.
Caveat — THIS CODE IS FOR EXPERIMENTAL PURPOSES ONLY!
So, having caused a little bit of a stir about random numbers, I considered how to fix them. In order to fix them, it is recommended to get a decent entropy pool for the random seed that is used by the PRNG in order to maintain the speed of generation you get from the software random() function, but with the randomness of a true source of entropy.
Building High-Entropy Functions
Entropy is the natural world attempting to explore the world around it. Just take a look at Boltzmann’s Equation for an overview — I’m not going to bore you with physics nor information theory, but it’s very interesting stuff!
So, what we want is a good and decent source of entropy — called the ‘entropy pool’ — that allows us to seed and later re-seed our PRNG function to improve our randomness.
How this will work
We will essentially want to do two things:
- seed the PRNG using our high-entropy random bytes into
randomSeed()— this will allow us to use therandom()function as normal. - re-seed the PRNG periodically to maintain randomness
Plan of Attack
We will demonstrate 3 methods for generating random bits:
- RC Tank to get ADC jitter
- WDT jitter
- Internal Thermistor
We will provide example code and links — data can also be made available, but there’s quite a bit of it.
Overall Framework
Aside from one example (the WDT jitter) we provide a ‘coin flip’ function into the following framework:
int coin_flip(void) {
int little_bit;
return little_bit = (GetMagic() & 1);
}int getFairBit(void) {
while(1)
{
int a = coin_flip();
if (a != coin_flip()){
return a;
}
}
}int get_rand_byte(void){
int n=0;
int bits = 7;
while (bits--) {
n<<=1;
n |= getFairBit();
}
return n;
}void setup()
{
// do the init stuff here...
Serial.println("init done!");
}void loop()
{
unsigned long rand_long;
for ( int i = 0; i < 10; i++) {
for (int k=4; k>0; k--) {
rand_byte1 = 0;
rand_byte1 = get_rand_byte();
rand_byte1 <<= ((k-1)*8);
rand_long |= rand_byte1;
}
// note, in the other examples we don't
// use rand_long like this... but you can do, for
// extra added entropy! :D
randomSeed(rand_long);
for(int j=0; j<10; j++){
Serial.println(random(), HEX);
}
rand_long = 0;
rand_byte1 = 0;
}
// this is just so I can see when it's done :P
delay(100000);
}
This is precisely what @dakami used in PoC||GTFO 0x01 — this is no accident. We will change the coin_flip() functions, but the rest will generally be the same. Example code will be given as we go along, too!
WDT Jitter
WDT Jitter has a library written for it for Arduino that can be found here: https://github.com/pmjdebruijn/Arduino-Entropy-Library
This was tested with the following code: (based off the code here)
#include <Entropy.h> void setup()
{
Serial.begin(9600);
Entropy.initialize();
}
void loop()
{
for (int i=0; i<10; i++){
randomSeed(Entropy.random(WDT_RETURN_BYTE));
for (int j=0; j<1000; j++) {
Serial.println(random());
}
}
}Overview of results:
This code works fine, and does indeed generate random numbers. However, the following issue was found…
This is two separate instances of the above code using WDT jitter — however, the first run was identical. They do eventually diverge, but this is less than ideal.
This is probably due to a clock phase lock on the initialisation of the timers going into the main(), at a bit of an educated guess. As such, it’s going to give the same seed to randomSeed() on startup, which is very much less than ideal until the entropy sneaks in.
As such, this is probably not a method I would recommend.
RC Circuit Entropy
This is probably the most interesting example, insofar as there is a lot written about the technique, but very few examples I could find of it actually being done.
Here is a tweet of my setup: https://twitter.com/LargeCardinal/status/918122393687687169
So, the 100Ohm resistor and 1nF capacitor are in parallel from pin A6 to GND, and there is a fly-wire from pin 2. This drives the pin high, and then we measure the ADC jitter caused by the thermal effect on the capacitor and resistor.
In practice, all that was needed was the resistor, and it did give some very good results which I will summarise below. Here is the code that was used in the test setup:
// RC Entropy source...
// experimental code - NOT FOR USE IN PRODUCTION!!
// --- not proven to be anywhere close to CSPRNG nor TruRNG ---
// by Mark C (@LargeCardinal)
//
// So, a 1.2 to 1nF ceramic cap and 100Ohm resistor are placed in
// parallel across the A6 and GND pins. A fly wire from Digital
// pin 2 then goes to the A6 rail, powering the cap of 1nF and 100Ohm res
//
// In practice, it seems we really don't need the capacitor... maybe
// we can rely on the capacitance/resistance in the ADC converter itself?!
int coin_flip(void) {
int little_bit;
digitalWrite(2,1);
delay(2);
return little_bit = (analogRead(A6) & 1);
}
int getFairBit(void) {
while(1)
{
int a = coin_flip();
if (a != coin_flip()){
return a;
}
}
}
int get_rand_byte(void){
int n=0;
int bits = 7;
while (bits--) {
n<<=1;
n |= getFairBit();
}
return n;
}
void setup()
{
// set driver pin to output:
pinMode(2, OUTPUT);
// start serial
Serial.begin(9600);
// warm up the capacitor! :P
digitalWrite(2, 1);
delay(200);
digitalWrite(2, 0);
Serial.println("init done!");
}
void loop()
{
unsigned int rand_word, rand_byte1, rand_byte2 = 0;
for ( int i = 0; i < 10; i++) {
randomSeed(get_rand_byte());
for (int j=0; j<1000; j++) {
Serial.println(random());
}
}
// this is just so I can see when it's done :P
delay(100000);
}The core idea is to get the LSB of the ADC register, and then use this as our entropy source. This code produced very promising results, but it should be noted that with this, and the code for the thermistor example, it was very slow to get enough entropy (this is due to the get_fair_bit() function avoiding strings on 0’s nad 1’s).
Overview of Results
This was highly effective — under various conditions (putting the setup in the fridge, warming it gently with various heat sources, etc.) it reliably generated randomness that could be used as a seed value.
NB — it was very slow, hence it is best used as a seed source, not a randomness source itself. This is, however, very common.
Thermistor Noise
Thermal noise (properly called Johnson-Nyquist noise) affects all electronic components to some degree. This is what gives the effect in the previous example, but also affects the thermistors included in the middle of most IC’s on the market.
These temperature sensors are designed to alert the MCU/CPU that it is overheating and should probably either ‘tone it down a bit’ or just plain turn off. We can, however, use it to get a random bit from the LSB as before… We do need to include a function to activate the (slightly hidden) ADC channel that you need to use to see the register…
// Adapted a function I took from:
// https://playground.arduino.cc/Main/InternalTemperatureSensor
// read from here...
int GetTemp(void)
{
unsigned int wADC;
ADMUX = (_BV(REFS1) | _BV(REFS0) | _BV(MUX3));
ADCSRA |= _BV(ADEN); // enable the ADC
delay(20); // wait for voltages to become stable.
ADCSRA |= _BV(ADSC); // Start the ADC
// Detect end-of-conversion
while (bit_is_set(ADCSRA,ADSC));
// Reading register "ADCW" takes care of
// how to read ADCL and ADCH.
wADC = ADCW;
return (wADC);
}int coin_flip(void) {
int little_bit;
return little_bit = (GetTemp() & 1);
}
int getFairBit(void) {
while(1)
{
int a = coin_flip();
if (a != coin_flip()){
return a;
}
}
}
int get_rand_byte(void){
int n=0;
int bits = 7;
while (bits--) {
n<<=1;
n |= getFairBit();
}
return n;
}
void setup()
{
Serial.println("init done!");
}
void loop()
{
unsigned int rand_word, rand_byte1, rand_byte2 = 0;
for ( int i = 0; i < 10; i++) {
randomSeed(get_rand_byte());
for (int j=0; j<1000; j++) {
Serial.println(random());
}
}
// this is just so I can see when it's done :P
delay(100000);
}
Overview of Results
As you can see, we need to do a little more work to get our coin flip, but it does indeed get us some nice random bits! Again, it was slow, but as a seed function, it was much better.
This is probably the method I would personally recommend to developers to use to seed their PRNG on an AVR if they had to!
Fun Aside — Adapt the code to just spit out random bytes from the get_random_byte(), and as you do, slow blow warm air (like you do for cleaning glasses) onto the chip, and as the temp rises, you’ll see more random numbers come out. Similarly, when you cool it, the numbers will speed up and then slow as the temperature changes.
Conclusions
In all, the conclusion is that there are indeed relatively decent (though not perfect) ways of generating random numbers on AVR’s, but none of them are implemented on the Arduino IDE SDK at time of writing.
If I were to recommend one method it would be the temperature sensor method. The entropy is slow to gather, but good quality, and varies a lot under my (not really) lab conditions.
My recommendation would be to adapt the code using the temperature for use on the AVR in general as a random seed, and then have this reseed regularly on a background timer. (Full disclosure — I’m not sure how to do this, but if any dev’s know, please do implement it!)
NB — This PRNG is probably not cryptographically secure, as we have not built the correct reseeding machinery to ensure we pass, say, Yao’s next-bit test. But, as a test harness, it is satisfactory and easy to implement quickly in order to test entropy pools.
I have only tested to see if the entropy mitigates the issue identified in the previous article. I have not applied any tests (still trying to get the NIST SP800 statistical tests to work) that would justify the AVR PRNG as being cryptographically secure.
AS SUCH, THIS CODE IS FOR EXPERIMENTAL PURPOSES ONLY!
