As we talked about in [A walk down the low-cost MCU-road], we landed on trying to make a random number generator with the rather low cost Padauk – PFS154.
How can we create “true” randomness?
Before we dive more into the implementation we can look more into how true randomness can be achieved.
As stated earlier, we want to make:
A device that spits out true random numbers through a serial communication link
How we can achieve that is the most tricky part. As we talked more about in [Randomness: What is it? Why do we need it? How do we create it?], pseudo-randomness is rather easy to create, but true randomness requires more. The key here is to fetch entropy from something physical.
There exists several ways (and places) to fetch this entropy.
Maybe the most used, is to make a system that fetches noise from hardware-things such as zener diode breakdowns, an ADC, human keyboard timings, mouse movements, air turbulence etc.
Creating a TRNG
But we want to make this thing with as little (hopefully none) external requirements, and the PFS154 does not have an ADC-module, so randomness from or through an ADC is not possible.
Several people have implemented random number generator that uses 2 system clocks running at different speeds and when the slowest of them ticks, data is taken out from a counter connected to the other clock.
By doing so we can catch the clock noise and the jitter (that probably is close to 100% random).
The PFS154 has two clock systems that we think is completely independent of each other. Namely the IHRC and the ILRC, where the IHRC is the “fast one” running at typically 16 MHz, while the “slow one” / the ILRC runs at ~54 kHz.
We can pipe the two different clocks into separate timers, and take out some of the bits from the fast counter each time the “slow interrupt” triggers.
Implementation and some data
The T16 interrupt happens only at ~1.6 Hz to give the two clocks time to behave differently (the IHRC 8-bit counter wraps around ~39 000 times for every T16 interrupt).
But this means that we only get a full byte with data every 5 second! Resulting in a not so fast number generator…
First we tried fetching out 2 bits at each interrupt, giving us a whopping 1,25 bps, but the resulting data was clearly not random (see “round 1” results further down). So we reduced the speed by only fetching 1 bit of data from the counter every interrupt (data from this is called “round 2”).
All the data generated by this system in these two rounds are possible to download here and here.
After starting the different timers (including the bitbanged UART), the main thing left is the interrupt handler.
And the “number generator” looked like this:
if ( INTRQ & INTRQ_T16 )
{
if ( random_number_index == 0 )
{
random_number = 0;
}
// take out one bit each time
random_number |= ( ( (TM3CT & 0b00000010) >> 1) << random_number_index );
if ( random_number_index >= 7 )
{
random_number_index = 0;
new_number = 1;
}
else
{
random_number_index++;
}
// mark T16 interrupt request processed
INTRQ &= ~INTRQ_T16;
}
For easy of use was the easypdk modified to dump incoming data to a binary-file:
// Changes added to easypdkprog.c line 714+:
FILE *fptr;
if ( dbgd>0 && !first_byte )
{
dbgmsg[dbgd]=0;
printf("%s", dbgmsg);
fptr = fopen("serialdump.bin","ab");
fwrite(&dbgmsg[0], 1, 1, fptr);
fclose(fptr);
}
if ( first_byte )
{
first_byte = false;
}
Is it random?
No.
If we start by looking at the distribution from the 2 different rounds:
You can quickly see that this is not uniformly distributed. And if we look at the development of this distribution we can also state that this lack several layers of “randomness”:
So by just looking quickly at the numbers we can state that this is not random.
Yes, the dataset is rather small (round 2 consist of only 9 189 912 bits), but still we can see that this is not going the “correct” way 🙂
For fun we ran this dataset through several statistical tests in dieharder. And the results did not surprise:
$ dieharder -g 201 -f serialdump_round2.bin -a
#=============================================================================#
# dieharder version 3.31.1 Copyright 2003 Robert G. Brown #
#=============================================================================#
rng_name | filename |rands/second|
file_input_raw| serialdump_round2.bin| 4.98e+06 |
#=============================================================================#
test_name |ntup| tsamples |psamples| p-value |Assessment
#=============================================================================#
# The file file_input_raw was rewound 48 times
diehard_birthdays| 0| 100| 100|0.00000000| FAILED
# The file file_input_raw was rewound 396 times
diehard_operm5| 0| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 842 times
diehard_rank_32x32| 0| 40000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 1051 times
diehard_rank_6x8| 0| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 1142 times
diehard_bitstream| 0| 2097152| 100|0.00000000| FAILED
# The file file_input_raw was rewound 1872 times
diehard_opso| 0| 2097152| 100|0.00000000| FAILED
# The file file_input_raw was rewound 2359 times
diehard_oqso| 0| 2097152| 100|0.00000000| FAILED
# The file file_input_raw was rewound 2587 times
diehard_dna| 0| 2097152| 100|0.00000000| FAILED
# The file file_input_raw was rewound 2609 times
diehard_count_1s_str| 0| 256000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 3055 times
diehard_count_1s_byt| 0| 256000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 3063 times
diehard_parking_lot| 0| 12000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 3069 times
diehard_2dsphere| 2| 8000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 3073 times
diehard_3dsphere| 3| 4000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 4199 times
diehard_squeeze| 0| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 4199 times
diehard_sums| 0| 100| 100|0.00000000| FAILED
# The file file_input_raw was rewound 4234 times
diehard_runs| 0| 100000| 100|0.83092807| PASSED
diehard_runs| 0| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 4712 times
diehard_craps| 0| 200000| 100|0.00000000| FAILED
diehard_craps| 0| 200000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 11677 times
marsaglia_tsang_gcd| 0| 10000000| 100|0.00000000| FAILED
marsaglia_tsang_gcd| 0| 10000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 11711 times
sts_monobit| 1| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 11746 times
sts_runs| 2| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 11781 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_raw was rewound 11851 times
rgb_bitdist| 1| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 11990 times
rgb_bitdist| 2| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 12199 times
rgb_bitdist| 3| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 12478 times
rgb_bitdist| 4| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 12826 times
rgb_bitdist| 5| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 13244 times
rgb_bitdist| 6| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 13731 times
rgb_bitdist| 7| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 14288 times
rgb_bitdist| 8| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 14915 times
rgb_bitdist| 9| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 15611 times
rgb_bitdist| 10| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 16377 times
rgb_bitdist| 11| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 17213 times
rgb_bitdist| 12| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 17283 times
rgb_minimum_distance| 2| 10000| 1000|0.00000000| FAILED
# The file file_input_raw was rewound 17387 times
rgb_minimum_distance| 3| 10000| 1000|0.00000000| FAILED
# The file file_input_raw was rewound 17527 times
rgb_minimum_distance| 4| 10000| 1000|0.00000000| FAILED
# The file file_input_raw was rewound 17701 times
rgb_minimum_distance| 5| 10000| 1000|0.00000000| FAILED
# The file file_input_raw was rewound 17770 times
rgb_permutations| 2| 100000| 100|0.00008615| WEAK
# The file file_input_raw was rewound 17875 times
rgb_permutations| 3| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 18014 times
rgb_permutations| 4| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 18188 times
rgb_permutations| 5| 100000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 18536 times
rgb_lagged_sum| 0| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 19233 times
rgb_lagged_sum| 1| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 20277 times
rgb_lagged_sum| 2| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 21670 times
rgb_lagged_sum| 3| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 23411 times
rgb_lagged_sum| 4| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 25501 times
rgb_lagged_sum| 5| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 27938 times
rgb_lagged_sum| 6| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 30724 times
rgb_lagged_sum| 7| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 33858 times
rgb_lagged_sum| 8| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 37340 times
rgb_lagged_sum| 9| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 41170 times
rgb_lagged_sum| 10| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 45348 times
rgb_lagged_sum| 11| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 49875 times
rgb_lagged_sum| 12| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 54750 times
rgb_lagged_sum| 13| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 59973 times
rgb_lagged_sum| 14| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 65545 times
rgb_lagged_sum| 15| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 71464 times
rgb_lagged_sum| 16| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 77732 times
rgb_lagged_sum| 17| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 84348 times
rgb_lagged_sum| 18| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 91312 times
rgb_lagged_sum| 19| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 98624 times
rgb_lagged_sum| 20| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 106285 times
rgb_lagged_sum| 21| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 114294 times
rgb_lagged_sum| 22| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 122651 times
rgb_lagged_sum| 23| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 131356 times
rgb_lagged_sum| 24| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 140409 times
rgb_lagged_sum| 25| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 149811 times
rgb_lagged_sum| 26| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 159561 times
rgb_lagged_sum| 27| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 169659 times
rgb_lagged_sum| 28| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 180105 times
rgb_lagged_sum| 29| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 190900 times
rgb_lagged_sum| 30| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 202042 times
rgb_lagged_sum| 31| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 213533 times
rgb_lagged_sum| 32| 1000000| 100|0.00000000| FAILED
# The file file_input_raw was rewound 213568 times
rgb_kstest_test| 0| 10000| 1000|0.00000000| FAILED
# The file file_input_raw was rewound 214103 times
dab_bytedistrib| 0| 51200000| 1|0.00000000| FAILED
# The file file_input_raw was rewound 214148 times
dab_dct| 256| 50000| 1|0.00000000| FAILED
Preparing to run test 207. ntuple = 0
# The file file_input_raw was rewound 214541 times
dab_filltree| 32| 15000000| 1|0.00000000| FAILED
dab_filltree| 32| 15000000| 1|0.00000000| FAILED
Preparing to run test 208. ntuple = 0
# The file file_input_raw was rewound 214626 times
The dieharder-tests probably reports several false negatives, because of the times it had to rewound the input data file. So if you actually are going to use a statistical test battery such as the dieharder tests, you need many GB of raw-data (compared to the ~1 MB here!)
Why is this not random?
We can clearly see that this data is not “random“.
But two independent hardware clocks should contain enough randomness and jitter which we can extract!?
Maybe they are not so independent as we thought?
Because when we calibrated one of the clocks the other clock started behaving differently, meaning that some sort of interaction happens. And maybe Padauk occasionally calibrates the ILRC with the the IHRC?
This is not a bad thing, but note that this behavior is not documented in the datasheet and makes it difficult to make a TRNG in this way on a PFS154.
