Generating true random numbers using floating ADC input – myth or facts?

This article shows the feasibility of using ADC input of AVR chip as a source of True Random Number Generator (TRNG). I have prepared the testbed and recorded via UART (115200; 8N1) about 50’000’000 of 32bit random numbers. The tests took about 11 hours (including a time I spent to pray to UART for a zero-errorate). Next paragraphs describes how I made the tests. Well, just to feed the curiosity on a begining – all statistical tests failed. I was really disapointend because the generated numbers looks “fairy random”. But, the math is math.

The Testbed

When I started writing the tests I knew that the environment factors can be crucial. So, I have choose a stable, battery power supply (3x AAA, 4.5V) and adjusted the room temperature to 25°C. I also made a Farady’s box to place there a tested dev-board (with Atmega8). Only one wire (about 30cm) has been placed outside. The same wire has been connected to ADC input to emulate a floating pin with some kind of antenne to easly sniff an electronic smog. Summing up the part list – battery pack, a dev-board with ATmega8 inside secured box, a wire and stable USB-to-UART converter. That’s all.

Testing Tools

As a testing tool I choose a cool DieHarder software (random-number generator test front-end) designed by Robert G. Brown (Duke University, Physics Department). This tool is also available in Ubuntu repository.

sudo apt-get install dieharder

The DieHarder program can test generated (expectedly) random numbers using variuous test suite and also offers various pseudo random number generators. Bellow is an example of how to generate 10’000’000 random numbers using built-in PRNG and make a basic monobit test.

$ dieharder -g 0 -t 10000000 -o -f test.dat
$ dieharder -d 100 -g 202 -f test.dat 
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
     file_input|                        test.dat|  5.04e+06  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
# The file file_input was rewound 2 times
         sts_monobit|   1|    100000|     100|0.02678203|  PASSED  

A list of tests available

$ dieharder -l
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
Installed dieharder tests:
 Test Number	                     Test Name	              Test Reliability
===============================================================================
  -d 0  	                  Diehard Birthdays Test	      Good
  -d 1  	                     Diehard OPERM5 Test	      Good
  -d 2  	          Diehard 32x32 Binary Rank Test	      Good
  -d 3  	            Diehard 6x8 Binary Rank Test	      Good
  -d 4  	                  Diehard Bitstream Test	      Good
  -d 5  	                            Diehard OPSO	   Suspect
  -d 6  	                       Diehard OQSO Test	   Suspect
  -d 7  	                        Diehard DNA Test	   Suspect
  -d 8  	      Diehard Count the 1s (stream) Test	      Good
  -d 9  	        Diehard Count the 1s Test (byte)	      Good
  -d 10  	                Diehard Parking Lot Test	      Good
  -d 11  	Diehard Minimum Distance (2d Circle) Test	      Good
  -d 12  	Diehard 3d Sphere (Minimum Distance) Test	      Good
  -d 13  	                    Diehard Squeeze Test	      Good
  -d 14  	                       Diehard Sums Test	Do Not Use
  -d 15  	                       Diehard Runs Test	      Good
  -d 16  	                      Diehard Craps Test	      Good
  -d 17  	            Marsaglia and Tsang GCD Test	      Good
  -d 100  	                        STS Monobit Test	      Good
  -d 101  	                           STS Runs Test	      Good
  -d 102  	           STS Serial Test (Generalized)	      Good
  -d 200  	               RGB Bit Distribution Test	      Good
  -d 201  	   RGB Generalized Minimum Distance Test	      Good
  -d 202  	                   RGB Permutations Test	      Good
  -d 203  	                     RGB Lagged Sum Test	      Good
  -d 204  	        RGB Kolmogorov-Smirnov Test Test	      Good
  -d 205  	                       Byte Distribution	      Good
  -d 206  	                                 DAB DCT	      Good
  -d 207  	                      DAB Fill Tree Test	      Good
  -d 208  	                    DAB Fill Tree 2 Test	      Good
  -d 209  	                      DAB Monobit 2 Test	      Good

A list of generators (PRNG)

$ dieharder -g -l
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
#    Id Test Name           | Id Test Name           | Id Test Name           #
#=============================================================================#
|   000 borosh13            |001 cmrg                |002 coveyou             |
|   003 fishman18           |004 fishman20           |005 fishman2x           |
|   006 gfsr4               |007 knuthran            |008 knuthran2           |
|   009 knuthran2002        |010 lecuyer21           |011 minstd              |
|   012 mrg                 |013 mt19937             |014 mt19937_1999        |
|   015 mt19937_1998        |016 r250                |017 ran0                |
|   018 ran1                |019 ran2                |020 ran3                |
|   021 rand                |022 rand48              |023 random128-bsd       |
|   024 random128-glibc2    |025 random128-libc5     |026 random256-bsd       |
|   027 random256-glibc2    |028 random256-libc5     |029 random32-bsd        |
|   030 random32-glibc2     |031 random32-libc5      |032 random64-bsd        |
|   033 random64-glibc2     |034 random64-libc5      |035 random8-bsd         |
|   036 random8-glibc2      |037 random8-libc5       |038 random-bsd          |
|   039 random-glibc2       |040 random-libc5        |041 randu               |
|   042 ranf                |043 ranlux              |044 ranlux389           |
|   045 ranlxd1             |046 ranlxd2             |047 ranlxs0             |
|   048 ranlxs1             |049 ranlxs2             |050 ranmar              |
|   051 slatec              |052 taus                |053 taus2               |
|   054 taus113             |055 transputer          |056 tt800               |
|   057 uni                 |058 uni32               |059 vax                 |
|   060 waterman14          |061 zuf                 |                        |
#=============================================================================#
|   200 stdin_input_raw     |201 file_input_raw      |202 file_input          |
|   203 ca                  |204 uvag                |205 AES_OFB             |
|   206 Threefish_OFB       |207 XOR (supergenerator)|208 kiss                |
|   209 superkiss           |                        |                        |
#=============================================================================#
|   400 R_wichmann_hill     |401 R_marsaglia_multic. |402 R_super_duper       |
|   403 R_mersenne_twister  |404 R_knuth_taocp       |405 R_knuth_taocp2      |
#=============================================================================#
|   500 /dev/random         |501 /dev/urandom        |                        |
#=============================================================================#
#=============================================================================#

Software

Testing Software for ATmega8 (slow)

Bellow is a testing software for ATmega8 (@16MHz) which produces a specified amount of (expectedly) random numbers and sends via UART (as a text) using Die Harder format. It’s a very slow version to demonstrate only an idea how to make a test and allow to play with the resulting data. The data can be read with any serial tool – i.e. CuteCom.

The bit-stream algorithm uses a least significant bit of ADC value. Also tested with alogrithm using two least significant bits of ADC value.

#include <stdint.h>
#include <avr/io.h>
#include <avr/interrupt.h>

#define N (32UL) // number of bits
#define SAMPLES (1000UL)
#define BAUDRATE (115200UL)

static uint8_t data[N];
volatile uint8_t counter = 0;

static void ADCRNG_init(void);
static uint32_t ADCRNG_next(void);
static void UART_init(uint32_t baudrate);
static void UART_putc(char c);
static void UART_puts(const char *s);
static void UART_putu32(uint32_t v);

int
main(void) {
  uint32_t random, n;

  ADCRNG_init(); // initialize ADCRNG
  UART_init(BAUDRATE); // initialize UART
  sei(); // enable global interrupts

  UART_puts("type: d\n");
  UART_puts("count: "); UART_putu32(SAMPLES); UART_putc('\n');
  UART_puts("numbit: "); UART_putu32(N); UART_putc('\n');

  for (n = 0; n < SAMPLES; ++n) {
    random = ADCRNG_next(); // get the random number
    UART_putu32(random); // and send it via serial port
    UART_putc('\n');
  }

  while(1); // infinite loop
}

ISR(ADC_vect) {
  if (counter < N) {
    data[counter++] = ADCH; // store ADC value
    ADCSRA |= _BV(ADSC); // run next signal acquisition
  }
}

void ADCRNG_init(void) {
  ADMUX |= _BV(REFS0)|_BV(REFS0); // use internal 2.56V voltage reference
  ADMUX |= _BV(ADLAR); // set left adjustment of ADC result (8bit mode)
  ADCSRA = _BV(ADPS1)|_BV(ADPS0); // set division factor to 2
  ADCSRA |= _BV(ADEN)|_BV(ADIE); // enable ADC0 (interrupt)
}

uint32_t ADCRNG_next(void) {
  uint8_t i;
  uint32_t result = 0;
  counter = 0; // reset counter
  ADCSRA |= _BV(ADSC); // start signal acquisition
  while (counter != N); // wait for data
  for (i = 0; i < N; ++i, result <<= 1) {
    result |= (data[i] & 1); // use least significant bit
  }
  return result;
}

void UART_init(uint32_t baudrate) {
  uint16_t baudrate_calc = (F_CPU / 4 / baudrate - 1) / 2;
  DDRD |= _BV(PD1); // set PD1 (TXD) as output
  UBRRH = baudrate_calc >> 8; // set calculated baudrate, high
  UBRRL = baudrate_calc; // and low register
  UCSRA = _BV(U2X); // double the transmition speed
  UCSRB = _BV(TXEN); // enable transmission
  UCSRC = _BV(URSEL)|(1<<UCSZ1)|(1<<UCSZ0); // set format 8N1
}

void UART_putc(char c) {
  while (!(UCSRA & _BV(UDRE))); // wait for empty buffer
  UDR = c; // put data into buffer
}

void UART_puts(const char *s) {
  while (*s) UART_putc(*(s++));
}

void UART_putu32(uint32_t v) {
  char buff[11];
  char *p = buff + 10; // switch to end of buffer
  *p = 0; // set string null-termination
  do {*(--p) = (v % 10L) + '0'; v /= 10L;} while (v); // convert
  UART_puts((const char *)p);
}

Testing Software for ATmega8 (fast)

Bellow is another testing software for ATmega8 (@16MHz) which produces a specified amount of random numbers and sends it via UART (as a binary). It’s a very similar (different only inside main function) but fast version which does not use Die Harder format. It simply sends number of samples (as a text) and then random numbers as binary data. The data can be read with the attached python script. The script reads the data from serial port and converts the bit stream to text version of Die Harder format.

int
main(void) {
  uint32_t random, n;
  char *p;

  ADCRNG_init(); // initialize ADCRNG
  UART_init(BAUDRATE); // initialize UART
  sei(); // enable global interrupts

  UART_putu32(SAMPLES); UART_putc('\n'); // print number of samples
 
  for (n = 0; n < SAMPLES; ++n) {
    random = ADCRNG_next(); // get the random number
    p = (char *)&random;
    UART_putc(p[0]); // send the 4byte integer via UART
    UART_putc(p[1]);
    UART_putc(p[2]);
    UART_putc(p[3]);
 }

 while(1); // infinite loop
}

Python script to read binary data

A python (>=2.7) script to read a data from serial port and convert the bit-stream to Die Harder text format.

#!/bin/env python

import serial
import struct

with serial.Serial('/dev/ttyUSB0', 115200, timeout=100) as s:
    line = s.readline()
    n = int(line)
    print("type: d")
    print("count: {}".format(n))
    print("numbit: 32")
    while n > 0:
        data = s.read(4);
        sample = struct.unpack("<I", data)[0]
        print("%10d" % sample)
        n -= 1

Testing Procedure

  1. Record 4’000’000 samples,
  2. run DieHarder tests,
  3. repeat (10 times).

Example Test Results

Histogram describing uniformity of distribution of tested random numbers (test4m1.log, ~44MB). As you can see the distribution of the numbers is not regular.

DieHarder output.

$ dieharder -a -g 202 -f test4m1.log 
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
     file_input|                     test4m1.log|  4.90e+06  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
# The file file_input was rewound 3 times
   diehard_birthdays|   0|       100|     100|0.00000000|  FAILED  
# The file file_input was rewound 28 times
      diehard_operm5|   0|   1000000|     100|0.00000000|  FAILED  
# The file file_input was rewound 60 times
  diehard_rank_32x32|   0|     40000|     100|0.00000000|  FAILED  
# The file file_input was rewound 75 times
    diehard_rank_6x8|   0|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 82 times
   diehard_bitstream|   0|   2097152|     100|0.00000000|  FAILED  
# The file file_input was rewound 134 times
        diehard_opso|   0|   2097152|     100|0.00000000|  FAILED  
# The file file_input was rewound 169 times
        diehard_oqso|   0|   2097152|     100|0.00000000|  FAILED  
# The file file_input was rewound 185 times
         diehard_dna|   0|   2097152|     100|0.00000000|  FAILED  
# The file file_input was rewound 187 times
diehard_count_1s_str|   0|    256000|     100|0.00000000|  FAILED  
# The file file_input was rewound 219 times
diehard_count_1s_byt|   0|    256000|     100|0.00000000|  FAILED  
# The file file_input was rewound 219 times
 diehard_parking_lot|   0|     12000|     100|0.00000000|  FAILED  
# The file file_input was rewound 220 times
    diehard_2dsphere|   2|      8000|     100|0.00000000|  FAILED  
# The file file_input was rewound 220 times
    diehard_3dsphere|   3|      4000|     100|0.00000000|  FAILED  
# The file file_input was rewound 261 times
     diehard_squeeze|   0|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 261 times
        diehard_sums|   0|       100|     100|0.00000000|  FAILED  
# The file file_input was rewound 264 times
        diehard_runs|   0|    100000|     100|0.00000000|  FAILED  
        diehard_runs|   0|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 294 times
       diehard_craps|   0|    200000|     100|0.00000000|  FAILED  
       diehard_craps|   0|    200000|     100|0.00000000|  FAILED  
# The file file_input was rewound 794 times
 marsaglia_tsang_gcd|   0|  10000000|     100|0.00000000|  FAILED  
 marsaglia_tsang_gcd|   0|  10000000|     100|0.00000000|  FAILED  
# The file file_input was rewound 797 times
         sts_monobit|   1|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 799 times
            sts_runs|   2|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 802 times
          sts_serial|   1|    100000|     100|0.00000000|  FAILED  
          sts_serial|   2|    100000|     100|0.00000000|  FAILED  
          sts_serial|   3|    100000|     100|0.00000000|  FAILED  
          sts_serial|   3|    100000|     100|0.00000000|  FAILED  
          sts_serial|   4|    100000|     100|0.00000000|  FAILED  
          sts_serial|   4|    100000|     100|0.00000000|  FAILED  
          sts_serial|   5|    100000|     100|0.00000000|  FAILED  
          sts_serial|   5|    100000|     100|0.00000000|  FAILED  
          sts_serial|   6|    100000|     100|0.00000000|  FAILED  
          sts_serial|   6|    100000|     100|0.00000000|  FAILED  
          sts_serial|   7|    100000|     100|0.00000000|  FAILED  
          sts_serial|   7|    100000|     100|0.00000000|  FAILED  
          sts_serial|   8|    100000|     100|0.00000000|  FAILED  
          sts_serial|   8|    100000|     100|0.00000000|  FAILED  
          sts_serial|   9|    100000|     100|0.00000000|  FAILED  
          sts_serial|   9|    100000|     100|0.00000000|  FAILED  
          sts_serial|  10|    100000|     100|0.00000000|  FAILED  
          sts_serial|  10|    100000|     100|0.00000000|  FAILED  
          sts_serial|  11|    100000|     100|0.00000000|  FAILED  
          sts_serial|  11|    100000|     100|0.00000000|  FAILED  
          sts_serial|  12|    100000|     100|0.00000000|  FAILED  
          sts_serial|  12|    100000|     100|0.00000000|  FAILED  
          sts_serial|  13|    100000|     100|0.00000000|  FAILED  
          sts_serial|  13|    100000|     100|0.00000000|  FAILED  
          sts_serial|  14|    100000|     100|0.00000000|  FAILED  
          sts_serial|  14|    100000|     100|0.00000000|  FAILED  
          sts_serial|  15|    100000|     100|0.00000000|  FAILED  
          sts_serial|  15|    100000|     100|0.00000000|  FAILED  
          sts_serial|  16|    100000|     100|0.00000000|  FAILED  
          sts_serial|  16|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 807 times
         rgb_bitdist|   1|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 817 times
         rgb_bitdist|   2|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 832 times
         rgb_bitdist|   3|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 852 times
         rgb_bitdist|   4|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 877 times
         rgb_bitdist|   5|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 907 times
         rgb_bitdist|   6|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 942 times
         rgb_bitdist|   7|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 982 times
         rgb_bitdist|   8|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1027 times
         rgb_bitdist|   9|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1077 times
         rgb_bitdist|  10|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1132 times
         rgb_bitdist|  11|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1192 times
         rgb_bitdist|  12|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1197 times
rgb_minimum_distance|   2|     10000|    1000|0.00000000|  FAILED  
# The file file_input was rewound 1204 times
rgb_minimum_distance|   3|     10000|    1000|0.00000000|  FAILED  
# The file file_input was rewound 1214 times
rgb_minimum_distance|   4|     10000|    1000|0.00000000|  FAILED  
# The file file_input was rewound 1227 times
rgb_minimum_distance|   5|     10000|    1000|0.00000000|  FAILED  
# The file file_input was rewound 1232 times
    rgb_permutations|   2|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1239 times
    rgb_permutations|   3|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1249 times
    rgb_permutations|   4|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1262 times
    rgb_permutations|   5|    100000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1287 times
      rgb_lagged_sum|   0|   1000000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1337 times
      rgb_lagged_sum|   1|   1000000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1412 times
      rgb_lagged_sum|   2|   1000000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1512 times
      rgb_lagged_sum|   3|   1000000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1637 times
      rgb_lagged_sum|   4|   1000000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1787 times
      rgb_lagged_sum|   5|   1000000|     100|0.00000000|  FAILED  
# The file file_input was rewound 1962 times
      rgb_lagged_sum|   6|   1000000|     100|0.00000000|  FAILED  
# The file file_input was rewound 2162 times
      rgb_lagged_sum|   7|   1000000|     100|0.00000000|  FAILED

Final Words

According to the tests have been made the myth has been refuted! ADC of AVR chips has not enough entropy to build TRNG (True Random Number Generator). However, it has enough randomness to generate seed numbers for PRNG (Pseudo Random Number Generator).

References

4 thoughts on “Generating true random numbers using floating ADC input – myth or facts?

  1. I recently made an RNG using an STM32 which does not come with an hardware RNG(some do).
    I used the internal temperature sensor as a source for entropy (WDT is a possible candidate too).

    The key is not to use your entropy source directly but to feed it through a randomness extractor. A randomness extractor should produce a random number if you feed enough bits to it with enough entropy even if there is some correlation. What you did is treat 1 adc bit as 1 random bit. But the adc-bits are not random. They are correlated since the ratio of 1’s and 0’s is not 1:1 and the spectrum may not be flat. I would be cautious to use a floating input as a source since you are depended on what radiowaves are present and without a nyquist filter you are guaranteed to get frequency folding. Some people use diodes as a source of noise.

    I noticed my ADC values only varied about 7*lsb values most of the time and there were a lot of 2-lsb jumps in my data. So I decided not to use only 1 bit but the lowest 4 bits since I did not want to throw out any entropy.
    I used fourier to check the spectrum. I used a histogram to check values. The spectrum looked ok, no strong peaks (with the exception of an obvious dc offset). The histogram followed a nice bell curve, not a flat distribution, but that is fine!

    I packed 2 4-bit samples in one byte. I fed 128 samples (64 bytes) to a crc32 function which should have plenty of randomness for 32-bit values, even if the entropy is only 1/4 bit per sample.

    I generated 10M values and it passed most dieharder tests. Using numbers generated by dieharder itself produced the same result.

    To save execution time I only use it as a seed value in my code.

    If I had more time I would reduce the number of samples fed into the crc-function until the tests start failing. This way I would know now much entropy it generates.

    • Hi Chris,

      thanks for leaving this valuable note. I was delighted reading your experience of making a RNG on STM32. I hope to find more time for this experiment to try to get a better distribution result with diode as source of the noise.

      Take Care
      /LP

  2. I appreciate the effort to this study. -I’d like a true random number generator for a project I’m working on. Looking the documentation over, I end up with theories and questions:
    1. Geometry of “pick-up”.. -Was a different length tried? Was the test done indoors/outdoors? Was the “antenna” vertical or, horizontal?
    2. Any amplification? Truly small signals may get swamped by adjacent circuitry on the processor (which might account for the four “lobes” in the graph).
    3. If “Thermal Background Noise” is random enough, I think I’d just connect the ADC pin to a diode biased at it’s “knee”. (My simplest suggestion..)

    • Hi Matthew, thanks for asking this questions.

      1. The wire length was the same for all test runs. Also, the a wire was laying down on the kitchens (wooden) table top.
      2. No amplification. My intention was to check ADC without extra components. Probably will give better result.
      3. Yes, diode connected in series with an “antenna” wire have a better result (much much better). I run some extra tests with a diode as well. Entropy is higher but distribution is still poor. Anyway, it also failed all statistical tests. It’s an experience I forgot to share. But thanks to you I will leave it here, in a comment.

      If you would like a file with samples from test with diode I still have it and I can share it via email.

      /L

Leave a Comment