====== Generating Entropy From Radioactive Decay With PiGI ======

Continuing on the final aspect of JamesT's very nice [[https://apollo.open-resource.org/mission:log:2014:02:08:playing-with-my-pigi-jamest42|exploration of PiGI]], we want to further examine the possibilities to create randomness from the output of a Geiger-counter. Of course we are using a [[lab:pigi|PiGI]] as testbed for our experiments.

True randomness, in the sense of "provably unpredictable" is not easily available on a computer. Good arguments can be made that the available sources of entropy like clock jitter, floating analog inputs, network traffic etc, combined with the algorithmic magic of /dev/random and /dev/urandom are more than adequate for all non-cryptographic purposes, and probably unpredictable enough to safely use them in cryptography without worrying to much.

But paranoia and cryptography run hand in hand and using radioactive decay as source of entropy is an interesting application of physics to provide access to the elusive "true" randomness on a computer.

While the half-life gives the duration after which a particle has decayed with a probability of 50%, the exact moment of decay can not be predicted in any way. So a sample of radioactive material creates a stream of events in a Geiger-counter, which, due to the enormous amounts of atoms even in the tiniest sample, averages to a steady rate, but the specific event times (or delays between events) are unpredictable. 

In the most fundamental form, our task is to produce a stream of equally probable 0's and 1's. To do this, we compare the last two delays between measured events. If one is longer than the other, the next bit is a 0 and if it is shorter it is a 1.

===== =====

===== Related Work =====
Radioactivity-based random number generators (RNGs) are not a new idea. The [[https://www.fourmilab.ch/hotbits/|Hotbits]] project is active since 1996 and provides a [[https://www.fourmilab.ch/hotbits/how3.html|nice explanation]] of the theory and setup.

Ionizing smoke detectors are a common source of the required radioactive sample, as they contain a small sample of Americium 241. [[http://etoan.com/random-number-generation/index.html| Dan Veeneman]] shows how to disassemble such a smoke detector, and [[http://www.inventgeek.com/Projects/AlphaRad/OverView.aspx| Jared Bouck]] explores how to visualize the alpha radiation with a webcam, similar to a [[https://en.wikipedia.org/wiki/Scintillator|Scintillator]] (and also uses the resulting data to generate randomness).

Random.org provides some excellent [[http://www.random.org/randomness/|general introduction]] to randomness and explains the difference between true random number generators (TRNG) and pseudo random number generators (PRNG). A deeper coverage of the subject is provided by a project report by Markus Rohe: [[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.110.9725&rep=rep1&type=pdf|RANDy - A True-Random Generator Based On Radioactive Decay]]


===== Implementation =====

==== Hardware ====

We use a Raspberry Pi running [[http://www.raspbian.org/|Raspbian]] with a prototype [[lab:pigi|PiGI-module]] and a LN712 Geiger-Müller-tube as hardware for our experiment. 

An Americium 241 sample from an ionizing smoke detector is used as source of radioactivity. It has a stated activity of 1 Microcurie which equates about 37000 decays per second (Bequerel).

==== Geigercounter Interface ====

We start with a minimal counter implementation in python. Every event in in the tube results in a falling edge on a certain GPIO input on the Pi. The class ''GeigerCounter'' sets up the GPIO if it is available or starts a thread which simulates the ticks if not. It also defines a function ''tick'' which is called for every event, simulted or real. For now it increments the ''tick_counter'' and prints the current value.

=== geiger.py ===

<sxh python; toolbar:false>


#!/usr/bin/env python
#minimal geigercounter

import time
import threading
import random

try:
    import RPi.GPIO as GPIO
    geiger_simulate = False
except ImportError:
    print "Simulating"
    geiger_simulate = True
        
GPIO_PIGI = 4
SIM_PER_SEC = 100

class GeigerCounter():
    def __init__(self):
        self.tick_counter = 0
            
        if geiger_simulate:
            self.simulator = threading.Thread(target=self.simulate_ticking)
            self.simulator.daemon = True
            self.simulator.start()
        else:
            GPIO.setmode(GPIO.BCM)
            GPIO.setup(GPIO_PIGI,GPIO.IN)
            GPIO.add_event_detect(GPIO_PIGI,GPIO.FALLING)
            GPIO.add_event_callback(GPIO_PIGI,self.tick)
        
    def simulate_ticking(self):
        while True:
            time.sleep(random.random()/(2*SIM_PER_SEC))
            self.tick()
    
    def tick (self,pin=0):
        self.tick_counter += 1
        print "Ticks: %d"%self.tick_counter

if __name__ == "__main__":
    gc = GeigerCounter()
    while True:
        time.sleep(1)
</sxh>

Running this program, we register a background radiation event every few seconds with the sample removed from the tube and a torrent of events when we bring it closer, peaking at about 2500 ticks per second.

Although this is less then 10% of the expected 37000 Bequerel of the sample, this value seems plausible because the sample radiates in all directions and the tube only detects events in one direction. Imagining the window of the tube as one wall of a cube around the sample, we see that we can detect at most 1/6 of all decays.

==== Entropy Generation ====


In order to generate randomness, we import the basic ''GeigerCounter'' class from geiger.py and extend it to a new class ''EntropyGeigerCounter''. 
Every even and odd tick, we set a marker, and every even tick we use these markers to compare the length of the last two delays between ticks. The result of this comparison is toggled every time to compensate potential bias. So we get one bit of randomness for every two ticks. These bits are appended to a bit-string which is periodically consumed into bytes which are written to file.


=== entropygeiger.py ===

<sxh python; toolbar:false>
#!/usr/bin/env python
#entropy generating geigercounter

import geiger
import time
import datetime

OUT_FILE = "entropy.bin"

class EntropyGeigerCounter(geiger.GeigerCounter):
    def __init__(self):
        #setup vars for randomness production
        self.toggle = False
        self.t0 = self.t1 = self.t2 = datetime.datetime.now()
        self.bitstring = ""

        #call __init__ of superclass
        geiger.GeigerCounter.__init__(self)


    def tick (self,pin=0):
        # This works like this:
        # time:   |------------|-------------|-----------|-----------|
        # tick 0: t0
        # tick 1: t0           t1
        # tick 2: t2           t1            t0
        #                d0            d1
        # tick 3: t2                         t0          t1
        # tick 4:                            t2          t1          t0
        #                                          dO          d1

        self.tick_counter += 1
        if (self.tick_counter % 2) == 0:
            self.t2 = self.t0
            self.t0 = datetime.datetime.now()
            d0 = self.t1 - self.t2
            d1 = self.t0 - self.t1

            if d0 > d1:
                self.bitstring += "1" if self.toggle else "0"
            elif d0 < d1:
                self.bitstring += "0" if self.toggle else "1"
            else: #d0 = d1
                print "Collision"

            self.toggle = not self.toggle

        else:
            self.t1 = datetime.datetime.now()

    def handle_bitstring(self):
        with open(OUT_FILE,"ab") as f:
            while len(self.bitstring)>=8:
                byte_bin = self.bitstring[:8]
                self.bitstring = self.bitstring[8:]
                byte_int = int(byte_bin,2)
                byte_hex = hex(byte_int)
                byte_chr = chr(byte_int)
                print "%s  %3d %4s %s"%(byte_bin,byte_int,
                                        byte_hex,byte_chr)
                f.write(byte_chr)

if __name__ == "__main__":
    egc = EntropyGeigerCounter()
    while True:
        egc.handle_bitstring()
        time.sleep(0.1)
</sxh>


As we need two ticks to generate one random bit, we produce entropy at half the tick rate. The 2500 events per second result in 1250 random bits per second, or about half a megabyte per hour.

===== Testing =====

We can test the "quality" of the decay-generated entropy with some readily available tools, right on the Pi, namely "rngtest" which is part of the "rng-tools" suite and implements [[http://www.fdk.com/cyber-e/pdf/HM-RAE103.pdf|FIPS 140-2]] tests and the [[http://www.phy.duke.edu/~rgb/General/dieharder.php|dieharder]] testsuite by Robert Brown which contains even more statistical tests.

It should be noted that all these tests can only detect certain patterns in the data. They can pass for non-random data and fail for true randomness. They should only be considered sanity checks and not definitive.

To install the tests, we run:

    apt-get install rng-tools dieharder 


To test our data with rngtest:

    cat entropy.bin | rngtest

Which - after running entropygeiger.py for about 15 minutes - produces the following report:

<sxh ; toolbar:false>
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: 1002488
rngtest: FIPS 140-2 successes: 49
rngtest: FIPS 140-2 failures: 1
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 1
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=24.205; avg=324.159; max=1362.392)Mibits/s
rngtest: FIPS tests speed: (min=4.671; avg=6.018; max=6.258)Mibits/s
rngtest: Program run time: 169693 microseconds
</sxh>

The tests run in blocks of 20000 bit each, and 49 of the 50 blocks passed the test. The single failure is most probably a false positive.

To test with dieharder:

    dieharder -a -f entropy.bin

It takes a lot more time than rngtest and outputs:

<sxh ; toolbar:false>
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
        mt19937|                     entropy.bin|  8.06e+06  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.60524248|  PASSED  
      diehard_operm5|   0|   1000000|     100|0.28329704|  PASSED  
  diehard_rank_32x32|   0|     40000|     100|0.14680003|  PASSED  
    diehard_rank_6x8|   0|    100000|     100|0.66775801|  PASSED  
   diehard_bitstream|   0|   2097152|     100|0.03547969|  PASSED  
        diehard_opso|   0|   2097152|     100|0.63643134|  PASSED  
        diehard_oqso|   0|   2097152|     100|0.58521817|  PASSED  
         diehard_dna|   0|   2097152|     100|0.49017156|  PASSED  
diehard_count_1s_str|   0|    256000|     100|0.90672404|  PASSED  
diehard_count_1s_byt|   0|    256000|     100|0.13019764|  PASSED  
 diehard_parking_lot|   0|     12000|     100|0.72516127|  PASSED  
    diehard_2dsphere|   2|      8000|     100|0.52175415|  PASSED  
[...]
</sxh>

===== Result =====

We were able to produce random data from radioactive decay at a steady rate of over 1200 bit per second, using only commonly available hardware and open-source software. The device is conceptually a true random number generator and the output passes statistical tests for randomness.

The inherent unpredictability of the generating process and the rather high output rate make it well suited for key-generation and other applications in cryptography.
{{tag>pigi raspberry pi software random rng radioactive geiger}}

{{keywords>Apollo-NG apollo next generation hackerspace hacker space research development makerspace fablab diy community open-resource open resource mobile hackbus pigi raspberry pi software random rng radioactive geiger}}


~~DISCUSSION~~