Skip to content

Instantly share code, notes, and snippets.

@endolith
Last active January 14, 2024 07:37
Show Gist options
  • Save endolith/2568571 to your computer and use it in GitHub Desktop.
Save endolith/2568571 to your computer and use it in GitHub Desktop.
Arduino hardware true random number generator

My attempt at a hardware random number generator in Arduino with no external components.

Only produces ~64 bit/s because of the minimum length of the watchdog timer. :(

Tested only on a Duemilanove. May not work on other hardware. Post a comment if you try it on other hardware or if you find a scenario where it doesn't work.

It uses the watchdog timer to sample (and reset) Timer 1. Since the watchdog timer runs on its own RC oscillator, and Timer 1 is on the crystal oscillator, there is random variation in the value read. Then the randomness is spread around to all 8 bits by reading 8 times and bit-shifting and XORing, to produce a random byte.

The assumption is that at least one bit in each sample is truly random. Though in reality, probably multiple bits have varying amounts of entropy? The raw read from the timer sampling is estimated at 4.4 bits of entropy per byte.

It seems to work. I think the main flaw would be if the two oscillators become correlated to each other in certain hardware configurations or at certain points in time, which I haven't noticed, despite running it continuously for days.

Disclaimer: I have no idea what I'm doing.

But it measures better than TrueRandom. "TrueRandom" is not truly random:

Entropy = 7.544390 bits per byte.

Optimum compression would reduce the size
of this 92810048 byte file by 5 percent.

Chi square distribution for 92810048 samples is 131287892.21, and randomly
would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 93.7178 (127.5 = random).
Monte Carlo value for Pi is 3.682216212 (error 17.21 percent).
Serial correlation coefficient is -0.008583 (totally uncorrelated = 0.0).

For comparison, with probably_random_with_TimerOne.ino, ent says:

Entropy = 7.996943 bits per byte.

Optimum compression would reduce the size
of this 65536 byte file by 0 percent.

Chi square distribution for 65536 samples is 277.59, and randomly
would exceed this value 15.83 percent of the times.

Arithmetic mean value of data bytes is 127.8158 (127.5 = random).
Monte Carlo value for Pi is 3.126899835 (error 0.47 percent).
Serial correlation coefficient is -0.007752 (totally uncorrelated = 0.0).

Generating the 13 GB required by dieharder would take about 48 years. :D

Output as an image:

noise

Output scatter plotted (plot(a, 'bo', alpha=0.1)):

plot

Histogram of output:

histogram

Gallery of tests of both TrueRandom and ProbablyRandom

I've also tested without the TimerOne library (probably_random.ino), just sampling the Arduino's constantly-cycling PWM timers instead of configuring and resetting Timer 1, and it doesn't seem to hurt the randomness:

Entropy = 7.999969 bits per byte.

Optimum compression would reduce the size
of this 5489591 byte file by 0 percent.

Chi square distribution for 5489591 samples is 233.95, and randomly
would exceed this value 75.00 percent of the times.

Arithmetic mean value of data bytes is 127.4536 (127.5 = random).
Monte Carlo value for Pi is 3.145767276 (error 0.13 percent).
Serial correlation coefficient is -0.001267 (totally uncorrelated = 0.0).

So you should be able to use all the inputs and outputs normally, and still generate random numbers. The LSBs will still be noisy even if the MSBs are periodic, and XORing the two will preserve only the randomness of the LSBs.

Obviously if your program turns off Timer 1 completely, this will no longer produce random numbers. (But it doesn't use any obfuscation or whitening other than the XOR shifting, so if you feed it nothing but 0s, it will output nothing but 0s and it will be obvious.)

Using Clear Timer on Compare mode should be ok, as long as the compare isn't correlated with the watchdog. If you use the watchdog timer to reset Timer 1 before reading it, for instance, you won't get random numbers. :)

Not sure about switching Timer 1 to other prescalers. Is it possible to run Timer 1 so slowly that it doesn't change between samples? That would be bad.

MIT License
Copyright (c) 2012 endolith
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
#include <stdint.h>
#include <avr/interrupt.h>
#include <avr/wdt.h>
byte sample = 0;
boolean sample_waiting = false;
byte current_bit = 0;
byte result = 0;
void setup() {
Serial.begin(115200);
wdtSetup();
}
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 > 7)
{
current_bit = 0;
Serial.write(result); // raw binary
}
}
}
// Rotate bits to the left
// https://en.wikipedia.org/wiki/Circular_shift#Implementing_circular_shifts
byte rotl(const byte value, int shift) {
if ((shift &= sizeof(value)*8 - 1) == 0)
return value;
return (value << shift) | (value >> (sizeof(value)*8 - shift));
}
// Setup of the watchdog timer.
void wdtSetup() {
cli();
MCUSR = 0;
/* Start timed sequence */
WDTCSR |= _BV(WDCE) | _BV(WDE);
/* Put WDT into interrupt mode */
/* Set shortest prescaler(time-out) value = 2048 cycles (~16 ms) */
WDTCSR = _BV(WDIE);
sei();
}
// Watchdog Timer Interrupt Service Routine
ISR(WDT_vect)
{
sample = TCNT1L; // Ignore higher bits
sample_waiting = true;
}
#include <stdint.h>
#include <avr/interrupt.h>
#include <avr/wdt.h>
#include <TimerOne.h>
byte sample = 0;
boolean sample_waiting = false;
byte current_bit = 0;
byte result = 0;
void setup() {
Serial.begin(115200);
wdtSetup();
Timer1.initialize(30000); // set a timer of length somewhat longer than watchdog length
}
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 > 7)
{
current_bit = 0;
Serial.write(result); // raw binary
//Serial.println(result, DEC); // decimal text
//binprint(result); // bits
}
}
}
// Rotate bits to the left
// https://en.wikipedia.org/wiki/Circular_shift#Implementing_circular_shifts
byte rotl(const byte value, int shift) {
if ((shift &= sizeof(value)*8 - 1) == 0)
return value;
return (value << shift) | (value >> (sizeof(value)*8 - shift));
}
// Setup of the watchdog timer.
void wdtSetup() {
cli();
MCUSR = 0;
/* Start timed sequence */
WDTCSR |= _BV(WDCE) | _BV(WDE);
/* Put WDT into interrupt mode */
/* Set shortest prescaler(time-out) value = 2048 cycles (~16 ms) */
WDTCSR = _BV(WDIE);
sei();
}
// Watchdog Timer Interrupt
ISR(WDT_vect)
{
sample = TCNT1L; // Ignore higher bits
TCNT1 = 0; // Clear Timer 1
sample_waiting = true;
}
// Print binary numbers
// http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1193507343/5#5
void binprint(int input) {
for (unsigned int mask = 0x80; mask; mask >>= 1) {
Serial.print(mask&input?'1':'0');
}
Serial.println();
}
# -*- coding: utf-8 -*-
from __future__ import division
import serial
from pylab import *
from time import time
import Image
size = 2**16
with serial.Serial('COM6', 115200) as port:
start_time = time()
data += port.read(size)
elapsed_time = time() - start_time
print 'Read ' + str(size) + ' bytes in ' + str(int(round(elapsed_time))) + ' s'
print 'Data rate: %.1f bit/s' % (size*8 / elapsed_time)
# Binary dump
with open(str(int(time())) + 'out.bin','wb') as f:
f.write(data)
a = numpy.fromstring(data, dtype = 'uint8')
# Plot
figure()
plot(a, 'bo', alpha=0.1) # Transparent to show stackups
# Histogram
figure()
hist(a, bins=64, range=[0,255])
# Image
repeat = int(sqrt(size))
b = reshape(a[:len(a) - len(a)%repeat], (-1, repeat))
im = Image.fromarray(b)
im.save(str(int(time())) + 'out.png')
@derickdressel
Copy link

Brilliant!

@wandrson
Copy link

Your post to the Arduino forum on this topic prompted me to continue researching the subject and eventually I developed a library to implement the functionality. If your interested it is available at http://code.google.com/p/avr-hardware-random-number-generation/wiki/WikiAVRentropy

@endolith
Copy link
Author

@wandrson: Cool! I actually saw the Entropy library on the Arduino site and thought "that sounds familiar" before I realized that it was inspired by this. :)

@jbellows
Copy link

Thanks for putting this together. It seems that the pseudo-random number generator used by avr-libc is pretty good, if you can get a truly random seed. Seems that you might be able to get good random numbers (7.994 bits/byte entropy) with the pseudo generator but setting the seed based on this method. That way you can get faster bit generation, but still maintain better randomness for an Arduino then standard methods.

@NoggetGump
Copy link

Do anyone here knows of such method in a library with a function like random(MIN,MAX)?
(p.s:noob here)

@arduinoenigma
Copy link

Hi,

Great work!

I am using a lightly modified version of this library to collect random numbers in the background and place them in a circular buffer.

https://gitlab.com/arduinoenigma/ciphersaber/blob/master/CipherSaber.ino#L95

Collection starts before the user starts typing the password and by the time the numbers are needed, the buffer is full, otherwise, we wait until it is.

https://gitlab.com/arduinoenigma/ciphersaber/blob/master/CipherSaber.ino#L510

https://gitlab.com/arduinoenigma/ciphersaber/blob/master/CipherSaber.ino#L698

The generated numbers look great for their purpose, to have a unique Initialization Vector for each message sent. The numbers are not secret, they are actually sent with the encrypted message so they can be used after the passphrase to setup the S array for decoding.

https://hackaday.io/project/168713/gallery#fcb64ce26a9c697b13530ebbc603d746

Thanks!

@endolith
Copy link
Author

endolith commented Dec 5, 2019

@jbellows: Yes, using this as the seed for a PRNG is a good method. Depends on your application.

@NoggetGump: The Entropy library is based on this method https://sites.google.com/site/astudyofentropy/project-definition/timer-jitter-entropy-sources/entropy-library https://github.com/pmjdebruijn/Arduino-Entropy-Library

@arduinoenigma: Cool!

@FelixWeichselgartner
Copy link

Does this code have some licensing? Under which conditions am I allowed to use your code (if I am at all)?

@endolith
Copy link
Author

@FelixWeichselgartner Added a license file

@FelixWeichselgartner
Copy link

@endolith TY very much :).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment