Showing posts with label random numbers. Show all posts
Showing posts with label random numbers. Show all posts

Sunday, 31 January 2016

Random Numbers from Salt (Radiation)

I bought a cheap Geiger Counter Kit from China to generate some random numbers. I wired it up to an Arduino Uno and wrote a basic sketch (lots plagiarised, but I have references back to their sources in the code) that generates random numbers from radioactive decay events. This is something that should, by its very nature be totally chaotic and not be predictable using classical or even quantum physics.

The basic theory is to record the time of 4 consecutive detected decay events. The time interval between the first two events will be greater than the time interval between the second two events 50% of the time on average. Allocate a 1 bit if this occurs and allocate a 0 bit if the opposite occurs [first interval is less than the second interval].

Wiring

Arduino 5V <-> middle pin of the three on the left side of the detector (labelled 5V).
Arduino Ground <-> top  pin of the three on the left side of the detector (labelled GND).
Arduino Pin 2 <-> bottom pin of the three on the left side of the detector (labelled VIN)
I also removed jumper J1 on the detector  to stop it clicking. The jumper actually still on the board but only on one pin, instead of bridging the both pins as it would by default.

One nice thing about this setup is that the Arduino is powering up the Geiger Counter Kit (both together are using about 0.04A @ 5.00 V =0.2 Watts - measured by a "USB Charger Doctor").

Radiation sources

The Geiger Müller tube used is sensitive to Beta and Gamma radiation (M4011), so I did a quick search for sources of radiation that I would feel comfortable owning, or ordering online and having delivered (for some odd reason I can picture the postman freaking out carrying a package with a big yellow radiation warning sticker on it).

Bananas have so little Potassium-40 in them, to be nearly invisible from background radiation (which is very comforting if you like to eat Bananas) - 0.098 μSv. And since the human body strictly controls the percentage of Potassium at a constant level, you should not let this information distract you from eating bananas their goodness far out ways any negative.

Opening an old fire alarm for its Americium-241 ionizing source would be useless since it is an alpha emitter [and low energy gamma rays of 60 keV]. (alpha can't get into my detector and most gamma pass right through my detector unnoticed) [An average smoke detector for domestic use contains about 0.29 micrograms of Am-241 (in the form of americium dioxide), so its activity is around 37,000 becquerel (or about 1 µCurie)]. But in terms of danger factor, versus happiness - I'll give it a very wide berth.

I could scour antique shops looking for old radioactive consumer products like Fiesta Ware or Vaseline/Uranium Glass but I do not feel the need to add radioactive items into my living environment.

You can call me crazy but I do not really feel comfortable with most radiation sources, so for my test I decided to use background radiation and some easily accessible Potassium-40 which should be around about 10x background levels.

I only used two sources for my radiation. One thing to keep in mind is that my Geiger Müller tube itself is slightly radioactive, just like everything, so I get about 0.2 pulses/second from the tube.

background radiation (where I live)
~ one decay event every 3 seconds
~18 counts per minute (CPM) [0.122 μSievert]
~0.29 counts per second (CPS)
~0.0725 bits/second
~0.009 bytes/second
~ 0.54 bytes/minute
~783 bytes/day

LO-SALT [66% Potassium Chloride] emits Beta particles from K-40
~ three decay events every one second
~161 counts per minute (CPM) [~1.06 μSievert]
~2.68 counts per second (CPS)
~0.67 bits/second
~0.084 bytes/second
~ 5.05 bytes/minute 
~7260 bytes/day
 




I could always check into using Caesium-137 or a Strontium-90 source at some later date. But in all honesty I think that I'll go in a different direction for generating random numbers. The sources I would feel comfortable using are not all that cheap as well.

Here is the sketch that I used to measure the CPM of the background and LO-SALT and print the result every 60 seconds:
// http://www.rhelectronics.net/store/radiation-detector-geiger-counter-diy-kit-second-edition.html
// https://github.com/revspace/geiger
// http://forum.arduino.cc/index.php?topic=336041.25;wap2
#define LOG_PERIOD 60000 //Logging period in milliseconds, recommended value 15000-60000.
#define MAX_PERIOD 60000 //Maximum logging period without modifying this sketch

unsigned long counts;     //variable for GM Tube events
unsigned long cpm;        //variable for CPM
unsigned int multiplier;  //variable for calculation CPM in this sketch
unsigned long previousMillis;  //variable for time measurement
float uSv;            // the measured microSiverts
float ratio = 151.5; // 151 CPM = 1uSv/h for M4011 GM Tube

void tube_impulse(){               //procedure for capturing events from Geiger Kit
  counts++;
}

void setup(){                                               //setup procedure
  counts = 0;
  cpm = 0;
  multiplier = MAX_PERIOD / LOG_PERIOD;  //calculating multiplier, depend on your log period
  Serial.begin(115200);                                    // start serial monitor
 // uncommennt if you have time-out problem to connect with Radiation Logger
 //  delay(2000);
 //  Serial.write('0'); // sending zero to avoid connection time out with radiation logger
 //  delay(2000);
 //  Serial.write('0'); // sending zero to avoid connection time out with radiation logger
  pinMode(2, INPUT);    // set pin INT0 input for capturing GM Tube events
  digitalWrite(2, LOW); // turn on internal pullup resistors, solder C-INT on the PCB
  attachInterrupt(0, tube_impulse, FALLING);  //define external interrupts
}

 

void loop(){                                               //main cycle
  unsigned long currentMillis = millis();
  if(currentMillis - previousMillis > LOG_PERIOD){
    previousMillis = currentMillis;
    cpm = counts * multiplier;    
    Serial.print(cpm);
    Serial.print(' CPM ');
    uSv = cpm / ratio ;
    Serial.print(uSv); 
    Serial.println(' uSv ');
    counts = 0;
  }
}


And, here is the sketch that I ran on my Arduino to generate the random numbers:

// This code generates random numbers based on nuclear decay events, 
// In my mind they would be the highest quality of random numbers.
// The only downside is that it is very very very very very slow. 
//
// Using only background radiation of about 18CPM it would take
// about 30 hours to generate 1k of random goodness.
// Using  low-sodium kitchen salt, you can get about 10x background radiation.
// Using LoSalt (66% potassium Chloride) 161CPM it would take about 
// 202 minutes to generate 1k of random goodness.
// Using some crazy lethal radiation source of 170,000CPM (60*1000000/350)
// (maximum with my GM tube recovery time of ~350uS) it would take about 
// 200 minutes to generate 1MiB of random numbers
//
// This is one of the reasons that I would not use a GM tube as my final solution 
// to generate high quality truly random numbers, but it is interesting to test.
//
// Using background where I am is about 18 CPM I can generate about 0.53 bytes/minute
// Using Lo-Salt (66% Potassium Chloride) 161 CPM I can generate about 5 bytes/minute
//
// 2016-01-31
// Remove all elegance and make it dumb, just bit bang pins until they change state.
// For optimal timing resolution sometimes doing things as basic as 
// possible is the most efficient technique.
//
// 2016-01-30
// This is a rewrite to gather 4 decays and generate one bit of randomness without
// using interrupts also we will use the rising edge instead of the falling edge as
// the trigger for a new decay This is so that code is running while the GM tube 
// is recovering from the previous decay event
//
// 2016-01-13
// some critical code from 
// https://www.fourmilab.ch/hotbits/source/hotbits-c3.html
// and some code is from 
// https://github.com/revspace/geiger
// and some useful info from
// http://tinkerman.eldiariblau.net/geiger-counter/
//
// The Geiger Counter is connected to pin 2 
// each pulse every time a decay is detected about ~350 microseconds in duration 
// I measured that with the following very basic code:
// unsigned long array[101];
// int counter=0;
//
// void setup(){ 
// Serial.begin(115200); 
// pinMode(2, INPUT); 
//}
//
//void loop(){ 
// array[counter++]=pulseIn(2,LOW);
// if(counter > 100)
//   for(;--counter;counter>1)
//     Serial.println(array[counter]); 
//}
// For my Geiger Counter Kit it's default is low, it pulses high for ~350uS 
// on a decay event and returns to low

const int GMpin = 2;
const int LEDpin = 13;
int LEDstate=HIGH;
unsigned long triggeredTime[4]; 
unsigned char bits;
unsigned long duration1, duration2;
int flipper = 0; // flip bit that gets toggled every time a new bit is generated. 
int shift = 0; // track how many bits have we shifted


void setup() {
 Serial.begin(115200);
 pinMode(GMpin, INPUT);
 digitalWrite(LEDpin,LEDstate); 
 pinMode(LEDpin, OUTPUT);
 digitalWrite(GMpin,LOW); // turn on internal pullup resistor
}


void loop() {
// 4 highs and 4 lows is one bit, or 4 independent decay events
// 0L-(unknown)->1H-(~350uS)->2L-(unknown)->3H-(~350uS)->4L
// 4L-(unknown)->5H-(~350uS)->6L-(unknown)-7H->(~350uS)->0L
//
// Wait 0L->1H
 while (digitalRead(GMpin) == LOW) {}; // wait here while the GM is low.
 triggeredTime[0] = micros(); // first decay has occurred
 digitalWrite(LEDpin,LEDstate); // toggle the LED once for each new bit
 LEDstate=!LEDstate;
// Wait 1H->2L (~350uS)
 while (digitalRead(GMpin) == HIGH) {}; // wait here while the GM is high ~350uS
// Wait 2L->3H
 while (digitalRead(GMpin) == LOW) {}; // wait here while the GM is low.
 triggeredTime[1] = micros(); // second decay has occurred
// Wait 3H->4L (~350uS)
 while (digitalRead(GMpin) == HIGH) {}; // wait here while the GM is high ~350uS
// Wait 4L->5H
 while (digitalRead(GMpin) == LOW) {}; // wait here while the GM is low.
 triggeredTime[2] = micros(); // third decay has occurred
 digitalWrite(LEDpin,LEDstate); // toggle the LED once for each new bit
 LEDstate=!LEDstate;
// Wait 5H->6L (~350uS)
 while (digitalRead(GMpin) == HIGH) {}; // wait here while the GM is high ~350uS
// Wait 6L->7H
 while (digitalRead(GMpin) == LOW) {}; // wait here while the GM is low.
 triggeredTime[3] = micros(); // fourth decay has occurred
 
 duration1=triggeredTime[1]-triggeredTime[0]; // first two decay events 3H-1H
 duration2=triggeredTime[3]-triggeredTime[2]; // second two decay events 7H-5H
 if (duration1 != duration2) {
          /* There remains the possibility of a very slight bias due
             to long-term effects such as ionisation of a Geiger tube,
             poisoning of a silicon detector, or (absurdly small for
             any practical source) decrease in radioactivity of the source
             over time.  To mitigate this, we invert the sense of the
             magnitude test between the first and second samples for
             alternate samples.  This pushes the effect of any long-term
             bias to a much higher order effect. */ 
   flipper ^= 1;
   bits = (bits << 1) | (flipper ^ (duration1 > duration2));
   shift++;
   if(shift>7) { // we have bits 0-7 collected, time to display the two nibbles.
     if((bits&0xF0) == 0x00) // is the first nibble zero
       Serial.print("0");    // if it is then print the leading zero.
     Serial.print(bits, HEX); // this command does not print out leading zeroes
     shift=0; // time to start collecting a new byte.
    } 
  }

// I could just assume that my code above will take longer than ~350uS 
// (5600 clock cycles @ 16MHz] which would be a bad assumption. So I added the 
// following line just to be safe. The worse case is that I miss one decay event.
// Wait 7H->0L (~350uS)
 while (digitalRead(GMpin) == HIGH) {}; // wait here while the GM is high ~350uS
}

The above code sends hex digits one byte at a time to the serial port. To capture the random numbers and store them to file I used the following commands on Linux "screen -L /dev/ttyACM0 115200" [^A D - to exit the screen session and return to the console] this creates a logfile called screenlog.0 which captures all data coming to the USB serial port from the Arduino. Or you could use "(stty -F /dev/ttyACM0 raw ispeed 115200 ; cat > random.txt) < /dev/ttyACM0"

And to convert them from ASCII into binary I used the following UNIX command:
$ cat  screenlog.0 | xxd -r -p - random.bin

And this binary file can be tested with rngtest if the filesize is at least 2500 bytes (20000 bits). Unfortunately since the randomness generation rate is low, it would take multiple centuries to generate the Gigabytes of data required for one run of the full dieharder randomness test suite, using a single Geiger Müller tube even with the most radioactive source possible. So as much as it was fun playing with a Geiger counter, for generating random numbers, I feel that it is a dead end, at least for me. The quality of the randomness it fantastic but the generation rate is far too low, at least for my needs.

Monday, 27 October 2014

Part One: Time for custom OTP generation hardware ?

I have been looking at how to generate good random numbers and also at the Raspberry Pi's maximum data throughputs rates using wifi (9.9MiB/s), ethernet (11.2MiB/s) and disk (22MiB/s). The Raspberry Pi is good at some things, but it is not very good at moving large amounts of data about really fast. If it was I'd probably look at some way of generating good random numbers and transferring in the data in via the GPIO pins. But even doing this, the GPIO pins have a limit of about 10MHz maybe, some testing would need to be done to see if this could work or if the data rate could be pushed higher (use more pins to transfer more bits in parallel).

I looked into using the BeagleBone Black, but it also only has 10/100 Ethernet (circa 11.2MiB/s). And if I made a custom board with the 324 BGA single core 720MHz-1GHz  Cortex-A8 CPU it probably would not have enough oomph to fully saturate the gigabit built into the TI AM3359 CPU. OK, even if it could generate OTP data at a gigabit per second rates, I could not easily push it to a disk at that rate, so maybe the chip is good enough. It does include a RNG Crypto Hardware Accelerator (/dev/hwrng), but I trust that about as much as I would trust the similar RNG in the Raspberry Pi. The AM3359 does have a 12-bit ADC 200KSPS inbuilt but that would be too slow to sample a noise source for random numbers to generate random numbers at any decent rate. And the chip are a little bit on the expensive side as well:
AM3359ZCZD72  1+ @ €31.47; 15+ @ €29.11; 50+ @ €27.14; 100+ @ €26.45 (April 2014).
AM3359BZCZA80 1+ @ €47.48; 10+ @ €45.20; 25+ @ €42.53; 50+ @ €40.11 (April 2014).
AM3358BZCZ672 1+ @ €39.60; 10+ @ €37.08; 25+ @ €34.98; 50+ @ €31.06 (April 2014).
AM3358BZCZ100 1+ @ €46.84; 10+ @ €44.61; 25+ @ €41.97; 50+ @ €39.59 (April 2014).
AM3357BZCZA80 1+ @ €41.97; 10+ @ €39.97; 25+ @ €37.60; 50+ @ €35.48 (April 2014).

Refer to "8.1.2 Device Nomenclature" in the AM335x datasheet for the exact meaning of the Suffix's.

The Airspy project is using a  LPC4370 ARM CPU which is slow at only 204MHz in comparison to a TI AM3359, but it does have one very nice feature a 12-bit 80MSPS ADC. It also has three ARM  cores a Cortex-M4 and two Cortex-M0's.There is a 100 BGA chip with 3 multiplexed ADC channels or a 256 BGA chip with 6 multiplexed ADC channels.
LPC4370FET100 1+ @ €10.77; 10+ @  €9.46; 25+ @ €8.43 ; 50+ @ €7.19 (April 2014)
LPC4370FET256 1+ @ €14.85; 10+ @ €12.97; 25+ @ €11.58; 50+ @ €9.86 (April 2014)

The airspy project was spawned into existence by the HackRF project which originally used a LPC4330,  well now a LPC4320 (no need to 10/100 Ethernet). This chip has the advantage of not being a BGA device, it is a 144 pin QFP, but the data, in the case of the HackRF One,  is transferred from a separate ADC to the ARM using SGPIO.

LPC4320FBD144,551 1+ @ €8.78; 10+ @ €7.55; 50+ @ €6.19; 100+ @ €4.20 (April 2014)
LPC4330FBD144,551 1+ @ €9.89; 10+ @ €8.50; 50+ @ €6.98; 100+ @ €4.43 (April 2014)


The complexity of using SGPIO and the cost of a separate high speed ADC using a LPC4320, makes the  LPC4370 with its inbuilt 80MSPS ADC look like the best overall cheapest solution for what I want to do.

The fact that the Airspy has a 80dB Spurious-free dynamic range that I could use this to amplify the noise signal from a reverse biased zanier diode or a npn transistor acting as a  germanium diode is nice. Because the noise signal needs about 40dB of gain to be usable. One problem with using the Airspy is that it is only sampling at 20MSPS and not 80MSPS. But as a open software test platform, that could be used to see if making a dedicated board with the LPC4370 BGA chip is feasible or not and it is a good easy first step. The Airspy will have two high speed ADC inputs (using a u.FL connector) for the two spare multiplexed ADC channels on the 100 BGA chip. After the initial tests these ADC ports could be used with a custom firmware to test sampling at 80MSPS, 40MSPS per channel from two shielded secure noise sources.

The main advantage of doing some testing using an Airspy would be not having to design and build a fully custom development board with this 100-256 BGA chip. Ok in the short term it may cost a bit more, but if it does not work I would still have a very useful SDR receiver. Unfortunately there is no way to push more then about 40MiB/sec through USB 2.0. So even though I could be sampling 80MSPS at 12bits (120MiB/sec), I would need to concentrate this entropy by a factor of three. And that is provisional on there being enough spare CPU headroom available to do so before transferring the sampled noise to a PC. The fact that the chip supports SIMD (ARM NEON) may make this just about possible with a good pinch of lateral thinking.


Tuesday, 21 October 2014

What is a OTP ?




A One Time Pad is a sequence of random bits. If used correctly, the one-time pad encryption is unbreakable.  The OTP or key must be random, as large as the plaintext, never reused in whole or part and kept secret.

Pros

  • unbreakable security.
  • Almost all methods for encryption today is based on the assumption that the universe will end long before the decryption can be brute forced using computing power and maths theory available now. This assumption may be wrong with the invention of quantum decryption computers, where all solutions are evaluated at once and the correct solution is resolved when the wave function is collapsed. Post publicly/privately available quantum decryption computers, OTP should still be secure if the source of the randomness is from nature.

Cons

  • High-quality random numbers are not easily generated. Even when generating the random numbers care must be taken to prevent them from being copied.
  • Distribution of OTP key basically requires a secure physical handover.
  • Access, securing and controlling who can use the OTP may not be easy.
  • Destruction of used keys may not be easy, most storages devices remove pointers to data for speed. Secure Digital cards and Solid-State drives will almost never overwrite old data, because this will  shorten the lifetime and performance of the storage device. And the written wear levelling algorithms which maintain the  3,000 to 5,000 block write cycle limit before failure of flash/SSD storage may remap blocks. And this means that even though you think that you are overwriting the same block you may actually be, and probably are, overwriting a totally different block.
  • Authentication, if the OTP was duplicated, there is no way to tell if fake messages were sent/received.
  • It is often described as unpractical, because it requires the same amount of key material as the data being transmitted.

Generation

The good

So what quantum sources are available for generating high quality random numbers.
  • Nuclear decay, when heavy atoms split into lighter elements they eject either alpha, beta or gamma radiation, or some combination. The half-life for each radioactive element is totally predictable but the actual timing of the decay events in between each half-life is totally random.
  • Shot noise, when electrons flow from one point to another in a circuit the number of electrons is not constant this is because of the discrete nature of electric charge. For instance 1 ampere of current consists of about 6.24×10^18 electrons per second; even though this number will randomly vary by several billion in any given second, such a fluctuation is minuscule compared to the current itself. The variation is temperature and frequency independent.
  • Photons, when large numbers of photons travel from one point in space to another the number of photons is not constant this is because of the discrete nature of photons. The variation is temperature and frequency independent.
  • Spontaneous parametric down-conversion  One photon enters a crystal, two photons leave, each with lower energy energy/frequency.
  • Band gap tunnelling electrons. You have a gap, you have electrons, every now and again random electrons jumps the gap.

Probably the most trusted source of  random numbers is from the timing of radioactive decay events. But even a highly radioactive isotope like Cæsium-137 can only generate about 100 bytes a second, using four counts to generate each bit. To fill a 3TB harddisk at that rate would take about 950 years using only one generator. With a two year warranty on most 3TB harddisks today, it would have failed when the disk was still nearly empty.

The not so bad (maybe)

Non-quantum sources are also available for generating random numbers.

  • Thermal noise from a resistor, amplified to provide a random voltage source.
  • Avalanche noise generated from an avalanche diode, or Zener breakdown noise from a reverse-biased Zener diode.
  • Atmospheric noise, echoes from the big bang and RF generated by lightening strikes

  And the ugly

Some commercial hardware for generating random numbers may, or may not, use a good high quality quantum source for their randomness. They then may either feed this into a hashing algorithm (SHA1, MD5, Whirlpool) to whiten/de-bias the randomness or feed it in as the seed to a deterministic random bit generator first before feeding it into a hashing algorithm to generate more random numbers per second. These modifications have the artificial effect of making the random numbers that are output pass FIPS 140-2 Annex C and Diehard tests for randomness.

Also with no access to the real random source it is impossible to detect if any external influence is biasing it's output to mostly all ones or all zeroes. Say Eve is modifying the electricity supply phase/voltage/waveform or changing the temperature/pressure of the environment of the device or zapping it with high energy electromagnetic waves, or even a beam of neutrons, anything to bias the output towards ones or zeroes.

Storage

Never on a SSD, unless the SSD is 99.99% full at all times. Spinning rust (AKA harddisk) still offers may advantages in securing a OTP over Solid State Drive technology. The biggest of which is the ability to fully destroy used pad.

Transfer

When a transfer happens it should be a two way exchange. The reason for a two way exchange is to avoid the same two people communicating with each other using the same communal pad. One pad means that if both parties independently decided to communicate at the same time a collision would occur, where the same pad is used twice. Where as if Alice has a pad (from Bob), that is only used in only sending messages to Bob, and Bob has a pad (from Alice) that is only used in sending messages to Alice, then the same pad can not be accidentally used twice. And in using two (or more) independent OTP's  this removes any requirement for an independent, secure,  communications channel is required to synchronise the usage of a single OTP.

Correct Use

Correct use of a OTP requires the following:
  • The OTP consists of real random numbers.
  • Only two copies of the OTP exist (sender and receiver).
  • Each OTP is used only once.
  • Each copy of a OTP is destroyed immediately after use.
Method
A previously prepared OTP key is combined one bit at a time with the plaintext message to produce the ciphertext. To decipher the ciphertext, the same key would be again combined character by character, producing the plaintext.
XOR Truth Table

pi@raspberrypi ~ $ echo -n 'Hello World!' | xxd -b
0000000: 01001000 01100101 01101100 01101100 01101111 00100000  Hello
0000006: 01010111 01101111 01110010 01101100 01100100 00100001  World!                                     .
 
pi@raspberrypi ~ $ dd if=/dev/random bs=1 count=12 2>/dev/null | xxd -b
0000000: 11010101 00001110 10111111 01110001 10001010 10010100  ...q..
0000006: 00100110 01010001 01100101 10110101 10101110 11010100  &Qe...
 
pi@raspberrypi ~ $

   SENDING
   -------
   message: 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 ...
   OTP:     1 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 ...
   XOR      -----------------------------------
   cipher:  1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 ...

   RECEIVING
   ---------
   cipher:  1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 ...
   OTP:     1 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 ...  
   XOR      -----------------------------------
   message: 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 ...
 
 
 

Friday, 21 March 2014

Part 2: Using the RPi Camera module to generate random numbers

Last post I was not very happy about getting 88 KiB/second of good random numbers output. 

I wondered what would happen if I threw away more data from the raw file generated after I XOR the 2 raw images together.

I could write a program to convert the image sensor data from its raw format, of 10 bits packed as BGGR data stored in 5 bytes, to separate zero padded 16 bit or 32 bit Blue, Green, Green, Red values and then throw away top bits. But I decided against it, maybe it is something I will look at in the future. 








|12345678|90123456|78901234|56789012|34567890| < 4 x 10 bit sensor data samples
|12345678|12345678|12345678|12345678|12345678| < 5 bytes raw data from file.


 I decided to print out all the 256 bit patterns in c.raw (the XOR of the two raw still images) and see what were the most, and least, common bit patterns being generated.

$ cat printbits.c
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
        FILE *filea;
        int count, a;

        filea=fopen(argv[1],"r");

        a=getc(filea);
        while (!feof(filea)) {
                for(count=0;count<8;count++) {
                        if (a&(128>>count))
                                printf("1");
                        else
                                printf("0");


                }
                printf("\n");
                a=getc(filea);
        }
        fclose(filea);
}




$ ./printbits c.raw | sort | uniq -c | sort -n
   4188 10101010
   4193 10111001
   4229 10101000
   4230 10101001
   4240 10100110
   4267 11101010
   4271 10011001
   4279 10101110
   4295 10111011
   4306 10011010
   4313 10001010
   4321 10111010
   4333 10101011
   4346 01101010
   4361 01101001
   4374 10011110
   4376 10101101
   4384 11101011
   4389 11111010
   4404 10111110
   4411 10011111
   4415 01100110
   4416 10001011
   4419 10100111
   4420 10011011
   4420 10101111
   4450 11100110
   4460 10100101
   4462 10110110
   4466 11101110
   4468 01011010
   4491 11011010
   4492 01101000
   4499 11011001
   4515 10011101
   4516 01011011
   4516 10011000
   4518 11101001
   4523 10111000
   4529 10010111
   4533 01101110
   4535 01011001
   4537 01101011
   4547 10100010
   4553 11111001
   4568 10010101
   4575 10100100
   4575 11111011
   4578 11011011
   4586 10010110
   4587 10001001
   4599 11001010
   4602 10110111
   4619 10001110
   4624 10000110
   4624 10110101
   4627 10101100
   4629 10100011
   4638 10001000
   4646 01001010
   4649 10100001
   4659 11100010
   4664 00101010
   4667 01100101
   4668 10010010
   4680 10110010
   4680 11011000
   4684 00101001
   4693 11101101
   4696 01100010
   4698 01100111
   4703 00101011
   4707 11100111
   4709 10111101
   4722 11101000
   4723 01101101
   4725 11101111
   4728 10010100
   4728 10111111
   4729 01011110
   4736 01011000
   4739 01001011
   4756 11010110
   4757 01001001
   4759 01111001
   4763 01111010
   4765 10011100
   4774 11001011
   4775 01101111
   4776 01110110
   4776 10010001
   4779 01001110
   4779 11100101
   4788 11001001
   4790 11110110
   4804 11111110
   4807 10000111
   4807 10001111
   4807 11100100
   4808 10110100
   4808 11001110
   4809 11010101
   4810 01010110
   4812 10001101
   4817 00100110
   4828 10100000
   4833 10111100
   4835 01100100
   4840 01011111
   4846 00101110
   4847 01000110
   4864 10010011
   4869 11011111
   4874 10000010
   4875 11011110
   4888 11010111
   4892 01100001
   4894 11100001
   4901 01011101
   4902 10000101
   4905 11101100
   4908 11001000
   4909 11011101
   4917 00101000
   4917 01010010
   4920 11111000
   4924 10110001
   4926 11110111
   4929 11000110
   4930 01110101
   4934 01010101
   4934 10001100
   4943 11010010
   4950 10000100
   4957 01001000
   4966 00111010
   4970 11100011
   4985 01111011
   4986 01101100
   4988 00100010
   4988 00111001
   4990 00101111
   4993 01111000
   5002 11001111
   5010 01100011
   5022 11110101
   5029 01110111
   5031 01000111
   5032 00100101
   5033 01001101
   5038 10110011
   5042 11111101
   5043 00110110
   5065 11110001
   5067 01110010
   5071 10000001
   5073 00010110
   5073 01001111
   5073 11110010
   5080 00011010
   5084 00100111
   5085 11000111
   5090 11110100
   5091 10010000
   5100 11000101
   5106 11111111
   5107 10110000
   5108 01010111
   5118 11011100
   5119 11010100
   5137 00101101
   5137 01000010
   5142 10000011
   5166 01100000
   5169 01110100
   5181 00100100
   5183 11010001
   5184 01011100
   5189 00111000
   5197 11100000
   5207 01010100
   5215 00011001
   5215 11000010
   5224 01000101
   5224 11010000
   5229 00101100
   5237 01010011
   5238 11010011
   5246 11001101
   5247 00010111
   5247 01111110
   5249 11111100
   5264 01010001
   5281 00010101
   5285 00010010
   5301 11110011
   5305 01110001
   5327 00110101
   5327 11001100
   5347 01110011
   5354 01000100
   5364 00100001
   5366 00011000
   5368 00100011
   5376 00111011
   5387 00110010
   5400 00110111
   5422 11000100
   5429 00011011
   5432 01001100
   5464 01000001
   5468 01000011
   5479 00010100
   5485 01110000
   5490 01010000
   5498 11000001
   5501 01111101
   5503 00110100
   5534 00010011
   5552 10000000
   5571 11000011
   5576 00110001
   5585 11110000
   5632 00100000
   5641 01111111
   5653 00010001
   5819 01111100
   5848 00001001
   5890 00010000
   5890 11000000
   5911 01000000
   5939 00001010
   5947 00110011
   5950 00110000
   6019 00001000
   6339 00001011
   6601 00111101
   6601 00111110
   6622 00111100
   6904 00011100
   7242 00111111
   7429 00011101
   9739 00001100
   9853 00011110
  10758 00011111
  13148 00000100
  13597 00001101
  16610 00000101
  33285 00000110
  89879 00001110
 107426 00000010
 220503 00001111
 404119 00000111
 412692 00000011
 938225 00000001
2860652 00000000


$ sudo apt-get install bc
$ bc -lq
2592*1944
5038848
2860652*8/10
2288521.60000000000000000000
(2288521.6/5038848)*100
45.417555758776609256
938225*8/10
750580.00000000000000000000
(750580/5038848)*100
14.895865086622974140
quit
$

All zeros was the most common as expected (little change between two consecutive images),
2860652 bytes would correspond to about 45% of the pixels in the image. And 00000001 would correspond to about 15% of the pixels. Quickly eye-balling the most common raw data would suggest that if we discarded the top 20 most common pixels byte patterns we should get better random numbers out.

Anyhow lets give that a try and see what happens.

$ cat purify.c#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
        FILE *filea, *filec;
        int a, c=0, bits=0;

        filea=fopen(argv[1],"r");
        filec=fopen(argv[2],"w");

        a=getc(filea);
        while (!feof(filea)) {
                switch (a) {

                        case 0: break;
                        case 1: break;
                        case 3: break;
                        case 7: break;
                        case 15: break;
                        case 2: break;
                        case 14: break;
                        case 6: break;
                        case 5: break;
                        case 13: break;
                        case 4: break;
                        case 31: break;
                        case 30: break;
                        case 12: break;
                        case 29: break;
                        case 63: break;
                        case 28: break;
                        case 60: break;
                        case 62: break;
                        case 61: break;
                        default: c=a; bits=8; break;
                }
                if(bits==8) {
                    bits=0;
                        putc(c,filec);
                        c=0;
                }
                a=getc(filea);
        }
        fclose(filea);
        fclose(filec);
}

$ gcc purify.c -o purify

$ ./purify c.raw d8.raw
$ cat d8.raw | rngtest
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 9306648
rngtest: FIPS 140-2 successes: 132
rngtest: FIPS 140-2 failures: 333

rngtest: FIPS 140-2(2001-10-10) Monobit: 8
rngtest: FIPS 140-2(2001-10-10) Poker: 301
rngtest: FIPS 140-2(2001-10-10) Runs: 157
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=9.721; avg=262.790; max=1733.953)Mibits/s
rngtest: FIPS tests speed: (min=3.696; avg=7.334; max=8.458)Mibits/s
rngtest: Program run time: 1253786 microseconds
 

$ ./von-Neumann d8.raw e8.raw
$ cat e8.raw | rngtest
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 1762592
rngtest: FIPS 140-2 successes: 88
rngtest: FIPS 140-2 failures: 0

rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=8.646; avg=234.685; max=1271.566)Mibits/s
rngtest: FIPS tests speed: (min=4.628; avg=6.070; max=6.252)Mibits/s
rngtest: Program run time: 293258 microseconds
 

$ ls -lart ?8.raw
-rw-r--r-- 1 pi pi 1163331 Mar 20 16:32 d8.raw
-rw-r--r-- 1 pi pi  220324 Mar 20 16:32 e8.raw
$ bc -lq
220324/1024
215.16015625000000000000
quit
$


So in theory at 1 raw frame a second we could get slightly more than double previous the random number generation rate, up to 215 KiB/second. So instead of 384 days to fill a 3TB hard disk with random numbers it would now take 158 days. Better but still not good enough for me..

This is still a tiny bit better than using /dev/hwrng which has a sustained throughput of 125 KiB/sec. But even with a custom RAW to RAM dumping application this way would never achieve a data rate of 40MB/sec(38.1MiB/sec), and even if somehow it could (filming a train/car journey or a candle flame) the Raspberry Pi would be unable to push this data to any external device at that rate because of the shared USB hub for 10/100 NIC and two USB ports intrinsic to its design. But I am going to do some USB throughput tests to see how fast it can push data about, maybe it can, if only one device is in use at a time.

Thursday, 20 March 2014

Using the RPi Camera module to generate random numbers


I do know about /dev/hwrng (sudo modprobe bcm2708-rng) on the Raspberry Pi, but it has a maximum output of 125KiB/second. So just for fun I thought I'd see how much cryptographically secure random numbers could be generated by the quantization errors on the camera module. Anyhow I also do not fully trust broadcoms random number generator because it is not public knowledge how the random numbers are being generated. And yes I do see some irony in using a blob infested RPi to generate high quality true random numbers. But with binary blobs everywhere, even in hard disks, it is hard to stay away from them. No matter how much you personally feel that they are bad, for any kind of good security/privacy.

The raspistill command has a --raw argument which appends at the end of a jpeg image file the raw uncompressed monochrome data from the image sensor before it is processed to add colour via the BGGR Bayer filter. In fact it is before quite a lot of processing: lens shading, black level correction, debayering, denoise, sharpening, defective pixel correction, colour correction.

Taking two raw images of the same subject should generate some least significant bit differences as the 10-bit ADC within the image sensor converted the voltages at each pixel into digital values. At the simplest level this could be due to random changes in light levels between images (number of photons hitting each sensor element) or thermal variations within the system between images or vibration of the image sensor or at a macro level a bird flying by the image sensor (if it was pointing at the sky).

Anyhow the idea is simple enough.
  • take two images using rpistill --raw, 
  • extract and XOR the raw images together to remove everything unchanged between the images so that only the differences remain.
  • There will be randomness here, but it will be low grade (mostly zero bits), so it needs to be concentrated or distilled somehow.  Or it is biased towards zero, so it needs to be unbiased. One solution is to pass the data through a Von Neumann's bias correcting algorithm. Which at its simplest is to throw away bits. i.e. 00-> /dev/null, 01->0, 10->1, 11->/dev/null. If the data was random then on average 8 bits input would become at most 2 bits output.
  • To help reduce any systemic biases every other output generated will be flipped.

Prerequisites:

sudo apt-get install rng-tools

Hardware:

Raspberry Pi model B
  • 512MiB RAM, 128MB of RAM allocated to GPU, no overclocking
  • Inbuilt 10/100 NIC is not connected.
  • Top USB port is empty
  • Bottom  USB port is empty
Raspberry Pi camera board

Code:

$ cat makeraw.sh

#!/bin/sh -- 
bytes=6404096
header=32768
sensordata=6345216
footer=26112
trunk1=`expr $bytes - $header`
#trunk1=`expr $sensordata + $footer`
# 6404096 bytes of RAW data is appended after a jpeg files data
# RAW image is always the maximum size x=2592 and y=1944
# 32768 byte header block before bit packed sensor data
# 10 bits, 10 bits, 10 bits, 10 bits = first 5 bytes of sensor data
# each line of image has 24 extra bytes at the end (unknown)
# ((2592*10/8)+24)=3264 bytes per horizontal line
# 1944 vertical lines of 3264 bytes each (3264x1944=6345216 bytes of sensor data)
# 26112 byte footer block after sensor data
raspistill --raw -q 1 -w 200 -h 200 --verbose --timeout 30 --thumb none --exif none --nopreview -o - | tail -c $trunk1 | head -c $sensordata > a.raw
raspistill --raw -q 1 -w 200 -h 200 --verbose --timeout 30 --thumb none --exif none --nopreview -o - | tail -c $trunk1 | head -c $sensordata > b.raw


if [ ! -r xor.c ]; then
cat << EOF > xor.c
#include <stdio.h>
#include <stdlib.h>

// exclusive or two files together and produce a third file of the difference
int main(int argc, char **argv)
{
 FILE *filea, *fileb, *filec;
 int a, b;

 filea=fopen(argv[1],"r");
 fileb=fopen(argv[2],"r");
 filec=fopen(argv[3],"w");

 a=getc(filea);
 b=getc(fileb);
 while (!feof(filea) && !feof(fileb)) {
        putc(a ^ b, filec);
        a=getc(filea);
        b=getc(fileb);
 }
        fclose(filea);
 fclose(fileb);
 fclose(filec);
}
EOF
fi

if [ ! -r xor ]; then
gcc -o xor xor.c
fi

./xor a.raw b.raw c.raw

if [ ! -r von-Neumann.c ]; then
cat << EOF > von-Neumann.c
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
        FILE *filea, *filec;
        int count, a, c=0, bits=0, flipbit=0;

        filea=fopen(argv[1],"r");
        filec=fopen(argv[2],"w");

        a=getc(filea);
        while (!feof(filea)) {
// 00-> /dev/null
// 01-> 0
// 10-> 1
// 11-> /dev/null
// on average 8 bits are reduced to 2, but if there is no entropy it will shrink smaller
// to remove any systemic bias, flip every other bit on the output
                for (count=0;count<3;count++) {
                        switch (a&3) {
                                case 0: break;
                                case 1: c=(c<<1)|(0^flipbit); bits++; break;
                                case 2: c=(c<<1)|(1^flipbit); bits++ ; break;
                                case 3: break;
                                default: break; //should never reach here
                        }
                        a=(a>>2);
                        flipbit^=1;
                        if(bits==8) {
                                bits=0;
                                putc(c,filec);
                                c=0;
                        }
                }
                a=getc(filea);
        }
        fclose(filea);
        fclose(filec);
}
EOF
fi


if [ ! -r von-Neumann ]; then
gcc -o von-Neumann von-Neumann.c
fi

./von-Neumann c.raw d.raw
./von-Neumann d.raw e.raw
./von-Neumann e.raw f.raw
./von-Neumann f.raw g.raw


Quick tests:

$ ./makeraw.sh
$ cat c.raw | rngtest
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 50761728
rngtest: FIPS 140-2 successes: 0
rngtest: FIPS 140-2 failures: 2538
rngtest: FIPS 140-2(2001-10-10) Monobit: 2538
rngtest: FIPS 140-2(2001-10-10) Poker: 2538
rngtest: FIPS 140-2(2001-10-10) Runs: 2538
rngtest: FIPS 140-2(2001-10-10) Long run: 2538
rngtest: FIPS 140-2(2001-10-10) Continuous run: 2069
rngtest: input channel speed: (min=8.826; avg=282.277; max=1733.953)Mibits/s
rngtest: FIPS tests speed: (min=2.334; avg=9.600; max=10.260)Mibits/s
rngtest: Program run time: 5239237 microseconds


This result was to be expected, so lets look at more distilled randomness:

$ cat d.raw | rngtest
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 3771400
rngtest: FIPS 140-2 successes: 139
rngtest: FIPS 140-2 failures: 49
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 14
rngtest: FIPS 140-2(2001-10-10) Runs: 47
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=10.590; avg=250.494; max=1733.953)Mibits/s
rngtest: FIPS tests speed: (min=4.299; avg=6.761; max=8.473)Mibits/s
rngtest: Program run time: 559268 microseconds



Better but still not great, so lets look at even more distilled randomness:

$ cat e.raw | rngtest
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 723504
rngtest: FIPS 140-2 successes: 36
rngtest: FIPS 140-2 failures: 0

rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=9.201; avg=209.407; max=1362.392)Mibits/s
rngtest: FIPS tests speed: (min=5.208; avg=6.055; max=6.223)Mibits/s
rngtest: Program run time: 126666 microseconds


This looks good but as you can see there is a lot less random numbers, but they are getting cryptographically more secure.

$ ls -l
-rw-r--r-- 1 pi pi 6345216
Mar 20 13:16 a.raw
-rw-r--r-- 1 pi pi 6345216
Mar 20 13:16 b.raw
-rw-r--r-- 1 pi pi 6345216 Mar 20 13:16 c.raw
-rw-r--r-- 1 pi pi 471425  Mar 20 13:16 d.raw
-rw-r--r-- 1 pi pi 90438   Mar 20 13:16 e.raw
-rw-r--r-- 1 pi pi 17204   Mar 20 13:16 f.raw
-rwxr-xr-x 1 pi pi 2603    Mar 20 13:16 makeraw.sh
-rwxr-xr-x 1 pi pi 5930    Mar 20 13:16 von-Neumann
-rw-r--r-- 1 pi pi 1259    Mar 20 13:16 von-Neumann.c
-rwxr-xr-x 1 pi pi 5766    Mar 20 13:16 xor
-rw-r--r-- 1 pi pi 482     Mar 20 13:16 xor.c


Conclusion

So for 2 still images at resolution (2592×1944) we have generated about 90438 bytes of cryptographically secure randomness. In theory the sensor could capture 15 frames a second at this resolution, but unfortunately this does not include the 6MiB of raw sensor data. So we can only capture about 1 frame a second which includes the RAW sensor data. So approximately 88 KiB/second. To fill a 3TB hard disk with random numbers would take about 384 days. If the random number generation rate was higher I would probably implement everything in software (no SD writes, most of the calculations done in RAM) but it is way too low a random number generation rate for me to even think about doing that.

P.S. In case you did not notice all the code is quick and dirty with no error checking at all. In all quick tests done by me, error checking is always skipped - makes the code more readable and it is a lot quicker to write. And also efficiency was was minimised to maximise readability.