LCE: Don't play dice with random numbers [LWN.net]

LCE: Don't play dice with random numbers

Posted Nov 22, 2012 20:15 UTC (Thu) by kleptog (subscriber, #1183)
Parent article: LCE: Don't play dice with random numbers

You don't need a lava lamp to produce random-looking numbers from a camera, just cover the lens with opaque tape. The camera will then produce a 640*480*3 colours x 10 fps = about 10Mbit/s of noise, assuming you just take the last bit of each pixel value.

Not sure how you prove its really random though, but at least every image is uncorrelated with every other image.

LCE: Don't play dice with random numbers

Posted Nov 25, 2012 6:10 UTC (Sun) by rgmoore (✭ supporter ✭, #75) [Link] (2 responses)

That's a good idea, but some of the implementation details are wrong in a way that might cause real world problems. For one thing, digital cameras sensors* measure the value for only one color at each physical pixel location. The three color final picture is the result of a complex color interpolation routine, which should result in correlation between the values in adjacent pixels. So in practice, you'll want to get the raw, uninterpolated sensor data rather than the final three colors per pixel interpolated data. Also, many real-world sensors have some kind of correlation between nearby pixels that isn't the result of the interpolation routines; it shows up as "pattern noise" in low-light pictures and is a major limit on many cameras' ability to take pictures in low light.

And as long as you're looking only at the least significant digits at each pixel, you shouldn't actually need to cover the lens. The least significant value is subject to shot noise as long as the pixel isn't anywhere close to saturation. Testing to make sure that it isn't saturated should be pretty easy, so you could probably get some useful randomness by appropriate use of a webcam without needing any modification.

*With the exception of those using Foveon's x3 technology, which is limited to a few expensive models you probably aren't going to be using for these applications.

LCE: Don't play dice with random numbers

Posted Nov 25, 2012 7:38 UTC (Sun) by kleptog (subscriber, #1183) [Link] (1 responses)

You clearly know more about digital cameras than I. The idea is not new, see for example http://www.lavarnd.org/what/process.html . I've never seriously proposed it because I figured there was more too it. That site for example also doesn't consider the issues you raised, it just asserts that by throwing enough SHA-1 hashes and bit-swapping at the problem the result is random. I think he misses the point that the problem is not getting random data, but knowing how random your data is.

For example, if you have 50kB of data that you know has 50% entropy you can "distill" it. The trick is knowing the 50%.

You're right you don't need to cover the lens, I left that out for simplicity. I tried this out on a camera being used for another purpose. It had some light and some dark, and the "randomness" was clearly dependant on the light level at that point. But like you say the camera has internal processing (to handle e.g. varying light conditions) and it's hard to know what effect that is having on the output.

Raw output would be best, but I don't know if cheap webcams offer that :)

LCE: Don't play dice with random numbers

Posted Nov 26, 2012 4:23 UTC (Mon) by rgmoore (✭ supporter ✭, #75) [Link]

Raw output would be best, but I don't know if cheap webcams offer that :)

I think that raw output is going to be pretty much mandatory if you hope to get anything like the theoretical entropy out of the sensor. But thinking about it, the biggest loss won't be from interpolation, it will be from using lossy compression. An essential trick to the lossy compression algorithms used to send images and video is that they keep only the most significant information in the picture. Since you're hoping to use the least significant information as a source of entropy, that's a killer.