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 -lq220324/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.

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.