Pages: 1 [2] 3   Go Down
Author Topic: Beta testers needed for a new library that generates true random numbers  (Read 8194 times)
0 Members and 1 Guest are viewing this topic.
Dubuque, Iowa, USA
Offline Offline
Edison Member
*
Karma: 44
Posts: 2463
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Q&D perl script to capture the data:

Code:
#!/usr/bin/perl
$|++;

use Device::SerialPort;

$PortObj = new Device::SerialPort ("/dev/ttyUSB2")
  || die "Can't open: $^E / $!\n";

$PortObj->user_msg(ON);
$PortObj->databits(8);
$PortObj->baudrate(115200);
$PortObj->parity("none");
$PortObj->stopbits(1);
$PortObj->handshake("rts");
$PortObj->read_const_time(100);

do {
  ($count_in, $string_in) = $PortObj->read(100);
} until ($string_in =~ /\n/);

while(($count_in, $string_in) = $PortObj->read(100)) {
  if ($count_in > 0) {
    print $string_in;
  }
}

Just direct STDOUT to a file, e.g. "perl script.pl > logfile.txt".
« Last Edit: June 07, 2012, 09:20:50 am by Chagrin » Logged

Dallas, Texas
Offline Offline
God Member
*****
Karma: 30
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

One more test result added for the library.  While only a small number of devices have been test so far, none have failed the basic tests.

IDDeviceTypeSample SizeEntropyChi squareP-value
1Arduino Uno R3DIP1,000,0007.999797281.390.1231
3Arduino Uno R3DIP1,000,0007.999819251.380.5524
3Arduino UnoSMD1,000,0007.999809265.270.3163
4Arduino Mega R3SMD1,000,0007.999813258.510.4268
5Adafruit ATmega32u4 breakout boardSMD1,000,0007.999811261.870.3703

While these tests have a lot of data (1,000,000 bytes), tests of only 100,000 bytes (25,000 samples) would be useful as well.  Please spend a couple of hours running the test script and send me your results.  In order to be confident that the library, and the methodology, are producing truly uniform random numbers we need a lot more samples from a lot more devices.  In particular, we need more samples from the same type of chips as already sampled.

Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

North Queensland, Australia
Offline Offline
Edison Member
*
Karma: 64
Posts: 2101
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Do you have a link to the stuff you are using to calculate the entropy value?
If it is producing true random numbers, can it be made faster by masking blocks of random numbers together; seeing as each block is truly random?

EDIT:
I have attached my capture, it is still a binary file. I have to still convert it to strings for you but you can grab this if you wanted now.
I set up my mega to gather 7kb blocks at a time before sending to the PC.

* SerialIn.data (791 KB - downloaded 36 times.)
« Last Edit: June 08, 2012, 07:18:29 am by pYro_65 » Logged


Dallas, Texas
Offline Offline
God Member
*****
Karma: 30
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Do you have a link to the stuff you are using to calculate the entropy value?
If it is producing true random numbers, can it be made faster by masking blocks of random numbers together; seeing as each block is truly random?

I am using a python script I wrote to perform the calculations used by the ent program (http://www.fourmilab.ch/hotbits/statistical_testing/stattest.html) by John Walker.  My script (attached) performs the same tests, except for the pi calculation, and combines several of the option along with producing a couple of charts of the data.  I am not sure where you would obtain blocks of random numbers to mask with those produced by this algorithm, so I can't comment if it would be faster.  If you need, non cryptographically secure, random numbers, that still have useful properties, at faster speeds, the best method is to use this library to re-seed the avr-libc random function whenever it has a value available.  Here is a sample sketch to illustrate what I mean:

Code:
#include <Entropy.h>

void setup()
{
  Entropy.Initialize();
  randomSeed(Entropy.random());
}

void loop()
{
  if (Entropy.Available > 0)
      randomSeed(Entropy.random());
  // Use normal random function for getting random numbers
  // ie. some_value = random();   
}


I have attached my capture, it is still a binary file. I have to still convert it to strings for you but you can grab this if you wanted now.
I set up my mega to gather 7kb blocks at a time before sending to the PC.

I am attaching the results of the tests for your data.  This is the first sample that shows some concern, the p-value for the chi-square test is only 0.0189.  Can you send me the full text on the smd chip you used for this--the label on the chip?  If the mechanism is producing truly random number we should get samples that exceed the normal acceptible p-values as George Marginalia says himself in his diehard series of tests:

#
NOTE: Most of the tests in DIEHARD return a p-value, which
       should be uniform on [0,1) if the input file contains truly
       independent random bits.   Those p-values are obtained by
       p=F(X), where F is the assumed distribution of the sample
       random variable X---often normal. But that assumed F is just
       an asymptotic approximation, for which the fit will be worst
       in the tails. Thus you should not be surprised with
       occasional p-values near 0 or 1, such as .0012 or .9983.
       When a bit stream really FAILS BIG, you will get p's of 0 or
       1 to six or more places.  By all means, do not, as a
       Statistician might, think that a p < .025 or p> .975 means
       that the RNG has "failed the test at the .05 level".  Such
       p's happen among the hundreds that DIEHARD produces, even
       with good RNG's.  So keep in mind that " p happens".
#


* SerialIn.data.png (446.87 KB, 800x1000 - viewed 42 times.)
* SerialIn.data.stats.txt (15.88 KB - downloaded 12 times.)
* analyze.py (8.7 KB - downloaded 13 times.)
« Last Edit: June 08, 2012, 07:49:40 am by wanderson » Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

North Queensland, Australia
Offline Offline
Edison Member
*
Karma: 64
Posts: 2101
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
I am not sure where you would obtain blocks of random numbers

I was thinking along the lines of using your algorithm to create two sets of random numbers. And masking them together to make a third set of random numbers. Would provide more numbers per minute for something like a random number provider.

Its just a thought, but I would assume ( with little analysis mind you ) that two truly random numbers combined to make a third should be no less random than generating the third value from scratch? maybe...
Logged


Dallas, Texas
Offline Offline
God Member
*****
Karma: 30
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
I am not sure where you would obtain blocks of random numbers

I was thinking along the lines of using your algorithm to create two sets of random numbers. And masking them together to make a third set of random numbers. Would provide more numbers per minute for something like a random number provider.

Its just a thought, but I would assume ( with little analysis mind you ) that two truly random numbers combined to make a third should be no less random than generating the third value from scratch? maybe...

Yes two uncorrelated random streams do produce a random stream; however, the internal avr-libc random function while useful is not really random.  It is good for all but the most demanding applications.


Oh, and here is the new table with your results added:

IDDeviceDate CodeTypeSample SizeEntropyChi squareP-value
1Arduino Uno R31153DIP1,000,0007.999797281.390.1231
3Arduino Uno R31107DIP1,000,0007.999819251.380.5524
3Arduino Uno1103SMD1,000,0007.999809265.270.3163
4Arduino Mega R31131SMD1,000,0007.999813258.510.4268
5Adafruit ATmega32u4 breakout board1038SMD1,000,0007.999811261.870.3703
6Clone mega1110SMD809,9847.999729304.090.0189
Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

North Queensland, Australia
Offline Offline
Edison Member
*
Karma: 64
Posts: 2101
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

I will do a check on the serial output to see if the binary is equivalent to the ascii version and re-run the test. The values seem skewed a little compared to the other samples.
Logged


Global Moderator
Dallas
Online Online
Shannon Member
*****
Karma: 197
Posts: 12744
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
It is good for all but the most demanding applications.

You're being generous.
Logged

North Queensland, Australia
Offline Offline
Edison Member
*
Karma: 64
Posts: 2101
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
however, the internal avr-libc random function while useful is not really random.  It is good for all but the most demanding applications.

I'm more concerned about your algorithm, it has been known for quite some time that random() is a pseudo generator. Is that not the motivation behind this project?

My previous question applies to your algorithm not random(), If it is to be useful it would have to be significantly faster to cope with demand for things like an Internet enabled device that could be polled continuously.
Logged


Dallas, Texas
Offline Offline
God Member
*****
Karma: 30
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
however, the internal avr-libc random function while useful is not really random.  It is good for all but the most demanding applications.

I'm more concerned about your algorithm, it has been known for quite some time that random() is a pseudo generator. Is that not the motivation behind this project?

My previous question applies to your algorithm not random(), If it is to be useful it would have to be significantly faster to cope with demand for things like an Internet enabled device that could be polled continuously.


Why would my comments about the internal random() function cause concern about the Entropy library?  The library doesn't make use of the avr-libc random function, nor any other pseudo random number generator.  

The purpose of the library is to provide a means of real random numbers on the Arduino without resorting to external hardware.  Uses include seeding the internal PRNG so that it provides different sequences everytime, generating secure passwords, etc...  The speed is very useable for some purposes, and unusable for others, indeed, it isn't much different speed wise than the internal linux mechanism for /dev/random

If greater speeds are needed than  external hardware based solutions are needed.  Geiger counter solutions are out, since a single device that doesn't use too hazardous a radiation source will produce at a lower rate than this source.  For instance my Geiger counter generator is only producing about 50,000 bytes per day with a piece of uranium ore as its source, while this one produces more than ten times that.  A hardware generator I built around avalanche noise source produces about 40,000,000 bytes per day (or more than 50 times what this one will).  Even that isn't enough for one of my needs--simulation.  So I am continuing to work on the hardware to increase its generation speed.

When deciding on what TRNG to use, first you need to establish the speed you desire, then determine the degree of randomness desired--and select from there.  One can increase speed at the expense of the uniform distribution.  All of the TRNG's I have worked with can produce at much higher bit rates, but the cost is a less uniform distribution.  Depending upon the use the numbers will be put to, that lack of uniformity may not matter much.  For instance, this library could be modified to get rid of the hashing algorithm and simply use the raw generated numbers.  The raw bytes have a uniform distribution for values 1 to 254; however, values 0 and 255 have approximately half of the probability as the other 253 values...  If you can accept that you can increase the generation speed 8 fold.

In order to include more numbers (in a given time frame) using this algorithm requires using multiple AVR chips to generate those numbers.  That added hardware complexity is not useful, since other mechanism could be used that are much faster and would require only a few extra components.  Again, the purpose of this library is to not requre ANY external components.  If no external components are used, and cryptographic levels of security along with high speeds, the only possibility is to use this library in conjunction with one of the better cryptograhic level pseudo-random number generator algorithms such as the AES_OFB or the Blowfish_OFB.

Ultimately, this library is designed to be a better replacement to the TrueRandom library in a similar set of situations.
« Last Edit: June 08, 2012, 06:13:13 pm by wanderson » Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Dallas, Texas
Offline Offline
God Member
*****
Karma: 30
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

I have completed a couple of more tests on two new devices, including a ATtiny85 (thanks Coding Badly).  Here are the updated test results.  Again I would really appreciate assistance in testing this library on more devices.  Even if you can only run the test for a couple of hours (25,000 samples or 100,000 bytes) that would be very helpful.

IDTesterDeviceChipDate CodeTypeSample SizeEntropyChi squareP-valueMeanS.C.C.Comments
1wandrsonArduino Uno R3ATMEGA328p-PU1153DIP1,000,0007.999797281.390.1231127.58030.000811
2wandrsonArduino Uno R3ATMEGA328p-PU1107DIP1,000,0007.999819251.380.5524127.44030.000379
3wandrsonArduino UnoATMEGA328p-MU1103SMD1,000,0007.999809265.270.3163127.48230.001646
4wandrsonArduino Mega R3ATMEGA2560-16AU1131SMD1,000,0007.999813258.510.4268127.55480.000069
5wandrsonAdafruit ATmega32u4 breakout boardMEGA32U4-AU1038SMD1,000,0007.999811261.870.3703127.46970.001247
6pYro_65Clone megaATMEGA2560-16AU1110SMD809,9847.999729304.090.0189127.5027-0.000090
7wandrsonSparkfun AVR/StickTINY85-20SU1023SMD1,000,0007.999826240.630.7321127.59750.000831
8wandrsonArduino NG/Rev C (168)ATMEGA168-20PU0701DIP1,000,0007.999808265.590.3114127.32460.000910
« Last Edit: June 09, 2012, 08:55:02 am by wanderson » Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Dubuque, Iowa, USA
Offline Offline
Edison Member
*
Karma: 44
Posts: 2463
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Here's a couple. Let me know if that's sufficient.


* Seeeduino_ATMega328PAU-1040.txt.gz (1733.37 KB - downloaded 35 times.)
* Seeeduino_Mega_V1.23_ATMega128016AU-0846.txt.gz (1677.33 KB - downloaded 33 times.)
Logged

Dallas, Texas
Offline Offline
God Member
*****
Karma: 30
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Here's a couple. Let me know if that's sufficient.



Thank you!  The data is much appreciated!

Here is the updated table!

IDTesterDeviceChipDate CodeTypeSample SizeEntropyChi squareP-valueMeanS.C.C.Comments
1wandrsonArduino Uno R3ATMEGA328p-PU1153DIP1,000,0007.999797281.390.1231127.58030.000811
2wandrsonArduino Uno R3ATMEGA328p-PU1107DIP1,000,0007.999819251.380.5524127.44030.000379
3wandrsonArduino UnoATMEGA328p-MU1103SMD1,000,0007.999809265.270.3163127.48230.001646
4wandrsonArduino Mega R3ATMEGA2560-16AU1131SMD1,000,0007.999813258.510.4268127.55480.000069
5wandrsonAdafruit ATmega32u4 breakout boardMEGA32U4-AU1038SMD1,000,0007.999811261.870.3703127.46970.001247
6pYro_65Clone megaATMEGA2560-16AU1110SMD809,9847.999729304.090.0189127.5027-0.000090
7wandrsonSparkfun AVR/StickTINY85-20SU1023SMD1,000,0007.999826240.630.7321127.59750.000831
8wandrsonArduino NG/Rev CATMEGA168-20PU0701DIP1,000,0007.999808265.590.3114127.32460.000910
9ChagrinSeeeduinoATMEGA328P-AU1040SMD1,336,3607.999865250.350.5704127.65950.000431
10ChagrinSeeeduino Mega v1.23ATMEGA1280-16AU0846SMD1,293,5007.999861248.240.6074127.5377-0.000420
« Last Edit: June 09, 2012, 09:52:36 am by wanderson » Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Dallas, Texas
Offline Offline
God Member
*****
Karma: 30
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Well, I spent most of the weekend testing a variety of new chips with the library.  I had one spectacular failure, 018, on a dip version of the ATtiny85; however, when I retested the same chip it performed well, so that highly unlikely sequence produced by the first test, while improbable is possible...  More testing needed to see how often such failures occur, which could be a problem.  Anyway, here are the test results so far.  Most of the later tests are shorter, which I have done to illustrate that these don't need to tie up your boards for very long, please download the latest version of the library and run the test on your chips and send me the results.  A library like this really needs hundreds (if not thousands) of different chips tested.  Here is the test sketch (and the library is linked in my signature block)

Code:
#include <Entropy.h>

void setup()
{
  Serial.begin(115200);
  Entropy.Initialize();
}

void loop()
{
  Serial.println(Entropy.random());
}

And here are the latest test results:

IDTesterDeviceChipDate CodeTypeSample SizeEntropyChi squareP-valueMeanS.C.C.Comments
1wandrsonArduino Uno R3ATMEGA328p-PU1153DIP1,000,0007.999797281.390.1231127.58030.000811
2wandrsonArduino Uno R3ATMEGA328p-PU1107DIP1,000,0007.999819251.380.5524127.44030.000379
3wandrsonArduino UnoATMEGA328p-MU1103SMD1,000,0007.999809265.270.3163127.48230.001646
4wandrsonArduino Mega R3ATMEGA2560-16AU1131SMD1,000,0007.999813258.510.4268127.55480.000069
5wandrsonAdafruit ATmega32u4 breakout boardMEGA32U4-AU1038SMD1,000,0007.999811261.870.3703127.46970.001247
6pYro_65Clone megaATMEGA2560-16AU1110SMD809,9847.999729304.090.0189127.5027-0.000090
7wandrsonSparkfun AVR/StickTINY85-20SU1023SMD1,000,0007.999826240.630.7321127.59750.000831
8wandrsonArduino NG/Rev CATMEGA168-20PU0701DIP1,000,0007.999808265.590.3114127.32460.000910
9ChagrinSeeeduinoATMEGA328P-AU1040SMD1,336,3607.999865250.350.5704127.65950.000431
10ChagrinSeeeduino Mega v1.23ATMEGA1280-16AU0846SMD1,293,5007.999861248.240.6074127.5377-0.000420
11wandrsonArduino NG/Rev CATMEGA168-20PU0701DIP1,000,0007.999815256.570.4606127.47650.0000042
12wandrsonArduino Mega R3ATMEGA2560-16AU1126SMD1,000,0007.999843217.740.9562127.53590.000320
13wandrsonArduino LeonardoATMEGA168-20PU1039SMD1,000,0007.999788293.570.0487127.43570.000022
14wandrsonbreadboard tinyATTINY85-20PU1211DIP106,7447.998190267.920.2768127.37960.009237
15wandrsonbreadboard tinyATTINY85-20PU1211DIP102,6407.998103270.080.2468127.6913-0.001888
16wandrsonbreadboard tinyATTINY85-20PU1211DIP100,0007.998026274.120.1960127.49610.007423
17wandrsonbreadboard tinyATTINY85-20PU1211DIP277,3887.999275277.330.1610127.26890.003250
18wandrsonbreadboard tinyATTINY85-20PU1211DIP100,8647.9861593084.670.0000127.79450.032045
19wandrsonbreadboard tinyATTINY85-20PU1211DIP111,0767.998312259.450.4108127.76970.000617
20wandrsonbreadboard tinyATTINY85-20PU1211DIP101,4647.997946288.950.0707127.51820.006300
21wandrsonbreadboard tinyATTINY85-20PU1211DIP287,8087.999319271.780.2246127.30420.002162
22wandrsonbreadboard tinyATTINY85-20PU1211DIP262,3127.999314249.990.5767127.78280.001686Retested same chip from 018
23wandrsonArduino NG/RevATMEGA168-20PU0624DIP539,7487.999642267.920.2769127.67160.000370
24wandrsonArduino Pro Mini 3v3ATMEGA328P-AU1208SMD1,004,3527.999785298.990.0304127.58720.001192
25wandrsonBreadboard tinyATMEGA328P-AU1211DIP111,5047.998213275.620.1791127.2366-0.003130
26wandrsonBreadboard tinyATMEGA328P-AU1211DIP115,7287.998499240.810.7292127.4722-0.001927
27wandrsonATmega1284p on STK500ATMEGA1284P-PU1209DIP100,9767.998129262.240.3642127.3669-0.001081
28P. StoffregenTeensy++ 2.0, 3V 8MHzAT90USB12871039SMD254,2807.999227272.240.2188127.13360.001923
29P. StoffregenTeensy++ 1.0, 5V 16MHzAT90USB6460849SMD343,0327.999508233.230.8322127.6864-0.001012
30P. StoffregenTeensy++ 2.0, 5V 16MHzAT90USB12860932SMD280,0687.999329260.120.3996127.64410.002521


All of the above tests were performed on different chips. No repeated tests on the same chip, unless otherwise noted. Since test number 018 failed so spectacularly, I retested that same chip in test number 022. Tests 014 - 022, and 25-26  were performed using arduino-tiny-0100-0013.zip from http://code.google.com/p/arduino-tiny/ with the ATtiny85@16MHz (internal PLL; 4.3V BOD) bootloader Test 27 was performed using Mighty 1284P core files with the original bootloader.
« Last Edit: June 14, 2012, 08:43:02 am by wanderson » Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Dallas, Texas
Offline Offline
God Member
*****
Karma: 30
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Just a reminder, that while so far the test results have been good, this library really needs a lot more testing on a lot more chips--even chip types that have already been tested.  Please consider, running an arduino overnight running this test code and capturing the output.  Then email me the output or attach it to a reply to this thread along with information on the type of arduino you ran it on and the text on the arduino chip.

Any assistance on this would be greatly appreciated!

Code:
#include <Entropy.h>

void setup()
{
  Serial.begin(115200);
  Entropy.Initialize();
}

void loop()
{
  Serial.println(Entropy.random());
}
Logged

New true random number library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Pages: 1 [2] 3   Go Up
Jump to: