[Cryptography] The ultimate random source

[Joseph Ashwood]

From: Phillip Hallam-Baker
Sent: Friday, February 07, 2014 8:14 AM
Subject: [Cryptography] The ultimate random source

> I have a solution to the random number generator problem that can be built 
> for about $50 and is completely verifiable.
> [shake a flask of candy, take a picture]

I'm not confident it will have as much entropy as you think. The design is a 
fairly basic modification of the lavarand design. Just as with lavarand the 
actual entropy comes form the entropy in the movement source (the heating 
coil in lavarand, the shaking in this design). So the total entropy in the 
random source at any given time will be a function largely of the 
variability of the arm motions, along with sensor noise (I'll get there). 
This will certainly have a fairly significant amount of entropy but I doubt 
the average person's vigorous arm movements will collect 256-bits quickly 
enough.

Of more interest to me is the sensor noise. With sensors of any kind as you 
push the limit of the sensor there is noise of various kinds. In the case of 
a webcam sensor on the flask the primary noise will be diode over-power 
noise from the shiny white areas. You'll also find some noise that will 
appear because the temperature of the sensor will change over time creating 
heat noise in the system. With proper sampling the heat noise and sensor 
overpower noise should be sufficient to provide reasonable amounts of 
entropy.

Maximizing this entropy requires the user of incandescent lights, and shiny 
candy. The incandescent lights have their own noise pattern which will be 
echoed in the shiny candy, and the flask, as well as the heat from the 
light, especially if the light is close to the webcam, will induce heat 
noise in the webcam.

Will these be sufficient? Honestly it depends on the webcam. Using the cheap 
webcam that is in your laptop, phone, tablet will almost certainly not be 
enough. You need to have enough precision to actually collect the noise, so 
you'll be looking for at least 10 stops (10 bits per color) in the camera. 
These are not that difficult to find, but are notably more expensive than 
the really, really cheap cameras generally used.

As an example of just how bad it can be, even with a camera that is vastly 
better than the one in your laptop/phone/tablet the GoPro Hero3 Black has a 
significant amount of apparent noise in the image. This noise is almost 
exclusively deterministic and can be virtually eliminated with simple 
post-processing. So the 1/2.3" sensor in the Hero3 Black is just not enough 
sensor. At the other extreme, fighting the sensor noise in the Red Scarlet 
Dragon can be a nightmare if you want the maximum sensitivity, same with the 
BlackMagic Pocket Cinema Camera, these both have large amounts of apparently 
non-deterministic components to their noise, but it is worth noting that the 
Dragon sensor has 20 stops (basically 16-bits per color) while the 
BlackMagic has 13 stops (slightly over 10-bits per color). In both of these 
cases though the noise is a tiny fraction of a bit per sensor site.

The next big problem you will find is that modern sensors use a Bayer 
pattern (some use a modified, but fundamentally the same here), this is a 
system where a given sensor node will have a red, green, or blue filter, but 
to count the resolution of the device you actually count all the sensor 
nodes. So for example a 2048x2048 sensor will likely have 1024 red and 1024 
green on a single row, the next row will have 1024 green and 1024 blue 
sensors, alternating in both cases. The debayering process is used to 
calculate the approximate color at each of these sensor nodes. The process 
itself is quite complex. The result though is that to acquire maximum 
entropy will require getting the pure RAW data. This actually eliminates all 
cheap cameras, they all have built in debayering. Moving to more powerful 
sensors it actually eliminates using the Red cameras as well, they 
exclusively use a lossy compression based on wavelets which works very well 
at reducing and virtually eliminating the noise, normally a good thing, but 
we want the noise. That pretty much leaves only the CinemaDNG cameras, at 
this point that is largely just the BlackMagic cameras. If you were to build 
your own camera there are a wide range of sensors available, and the RAW 
data could be easily fed completely uncompressed into the hash function.

I know you thought you found one that is simple, and assuming the color 
blocks are big enough and that the rearrangement of candy is good enough, 
yes it is, but I don't have any evidence that either is genuinely true. It 
will take a detailed analysis of the entropy sources, and the harvest engine 
to determine.
                Joe