40

Forgive my ignorance on the subject, but I wish to know more and asking (stupid) questions are one way. I was reading http://www.random.org/randomness/ and this idea popped into my head (before the bit about lava-lamps)

Considering the following:

  • Things like atmospheric properties and "real" life in general are supposedly random in the truest sense, they count as TRNGs.
  • Computers' pseudo random number generators are not as random (hence the pseudo) and, judging by all the NSA/GHCQ revelations lately, not to be trusted.
  • Smartphones have increasingly sensitive cameras.
  • Smartphone photos are usually taken by hand.

Would taking a photo using a smartphone and using the RAW file's bytes count as a good way to get a large random number quickly? The sensitivity and the naturally differing position would make even several photos of the same thing quite different, and photos are of the real world, making them as random as the things they point at (prior to loss introduced by the camera).

If it is a good way to get a large random number, I could see that it would be an accessible, easy way for average Joe to generate a key. An added benefit would be that it could be used as a key, or a random number for a key, that the holder could recognise by sight, and yet could also deny was a key, as it's just a photo.

Finally, since market forces and increasing technology mean more sensitive cameras will become more widespread, would this be one way to protect against intentional flaws being introduced? I imagine that poor camera quality would quickly be noticed and can easily be tested for (the linked article gave an example of how humans are good at testing things visually) - and it'd be news that would harm uptake of a model (happened to Apple at least once, not sure if it put people off though). Hence, market forces could work against the introduction of flaws.

If this is stupid, please say why and point me to a resource to further my knowledge. If it's not, I'm going to write an app to do this.

schroeder
  • 123,438
  • 55
  • 284
  • 319
ian
  • 1,302
  • 11
  • 21
  • 1
    Only one random generate was found to be potentially backdoored by the NSA. Furthermore most attacks were done on the devices themselves by replacing or manipulating one of the endpoints. So regardless what random generator you use it would still be prone to these attacks. Most of the pseudorandom generators are still secure, so please don't roll your own. – Lucas Kauffman Sep 14 '13 at 10:53
  • 4
    @LucasKauffman That doesn't answer my question, and I don't see why you or anyone else should tell me what to do with my time, frankly. – ian Sep 14 '13 at 10:55
  • 1
    because of sucky implementations and people who decide we have had security breaches before. Unless you are a cryptographer you shouldn't be rolling your own and you should definitely not publish it before a vast review by several independent parties. Also it was posted as a comment not an answer ;). – Lucas Kauffman Sep 14 '13 at 11:46
  • 9
    The camera would be a useful entropy source for seeding a CSPRNG after hashing the image (e.g. with SHA-512). But using it as raw bitstream would be a bad idea in most situations. – CodesInChaos Sep 14 '13 at 11:46
  • 1
    Also I don't mind this if it's just for learning purposes – Lucas Kauffman Sep 14 '13 at 11:53
  • 3
    @LucasKauffman I'm not "rolling my own" - if an input source is truly random then what have I rolled? That I wrote some code to access a camera or a microphone? Do I need to be a cryptographer to write a program that reads from an input source? Strangely, no, I don't think so. When I release my successor to AES, then your point will have some merit. – ian Sep 14 '13 at 12:10
  • @Iain You'll need to use crypto properly to whiten the image data, since by itself it's trivially distinguishable from perfectly random data. – CodesInChaos Sep 14 '13 at 12:12
  • @Iain if you are building the one thing where the whole crypto supports on (random number generation) then you are rolling your own. Crypto supports on random generation, if your random generation is in fact weak (limited amount of possibilities) or predictable then your crypto is useless. – Lucas Kauffman Sep 14 '13 at 12:37
  • @LucasKauffman "if your random generation is in fact weak (limited amount of possibilities) or predictable then your crypto is useless". Right, hence the question. Producing keys doesn't have to be (and probably shouldn't be) tied to any particular cryptographic app, and I've no plans to build a cryptographic app, no "rolling my own" in sight. What I'd like, is a way to generate keys that is easy and secure and accessible. Everyone knows how to take a picture, whether with the camera or through an app. – ian Sep 14 '13 at 18:04
  • 2
    BTW: There are already projects that use a webcam as random source for PCs. There was a good article a few years ago in the German [magazine c't](https://www.heise.de/artikel-archiv/ct/2009/02/172_Faites-vos-jeux) and the [code](https://github.com/ola-ct/random-tools) is still available ([archive of the website too](http://web.archive.org/web/20131121093646/http://von-und-fuer-lau.de/randcam.html)). For Linux, there is [video_entropyd](http://www.vanheusden.com/ved/) – Josef Aug 14 '15 at 08:26

4 Answers4

41

Using a camera as random source is a good idea (not a new one, but still a good one). However, you should do it correctly: take the photo, then hash it with a cryptographic hash function, e.g. SHA-256. Then use the output as a seed for a cryptograhically secure PRNG to generate as many random bytes as you need.

Using the file size will yield only very few bits of entropy from your picture: if a typical picture compresses to a size around, say, 2 MB, plus or minus 128 kB on average, then you will get at most 18 bits of entropy from the size. With a hash function, you harvest all the entropy that there is in the photo itself, up to the internal limit of the hash function (about 255 bits for a 256-bit output), which is way beyond that which is necessary for all realistic purposes.

A single photo ought to contain a lot of entropy, unless the camera output is covered in some way and the picture is uniformly black. A word of warning, though: if the hash of the photo is used as a secret (and that's the case if you want to use it as seed for a PRNG to produce keys), then that photo must remain confidential: hash it, but never let it be written as a file in the Flash memory of the phone. The photo should be obtained in RAM only, hashed, and then discarded. I don't know what API for photo capture applications have in a typical phone; it seems probable that you can obtain the photo without hitting the Flash in any way, but I invite you to check.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • In iOS/Android you can take photos without flash and I am near positive you can store all of the bytes from the photo in RAM. – KDEx Sep 14 '13 at 14:58
  • 4
    @KDEx: He's not talking about the illuminating "flash" LED but Flash memory. – Tim Pietzcker Sep 14 '13 at 16:03
  • What would be the impact of XORing the picture with the PRNG result instead of using it as seed? – luiscubal Sep 14 '13 at 18:53
  • 3
    @luiscubal: in what I describe, there is no PRNG until you have a seed, so your question does not make not a lot of sense. Except if you consider that you already have an existing PRNG and you want to "enhance" its randomness; in that case, XORing the PRNG output with the image "as is" does not "enhance" the initial PRNG much, because a normal picture will have large biased, non-random areas. For proper randomness, you really need to harvest and concentrate all the entropy (the initial hash) and then expand it back (with a PRNG). – Thomas Pornin Sep 14 '13 at 20:07
  • @thomas-pornin: Hashing the signal works well if there is at least as much entropy as the size of hash collision space. For this purpose the hash function only needs to be [uniform not secure](http://programmers.stackexchange.com/q/49550); cryptographic hashing would cloud exactly where the true entropy is coming from. Running the hash result through a PRNG converts the net output from a TRNG/OTP to a PRNG which may or may not be acceptable. Determining the actual level of source entropy is hard, so we cheat and use functions (SHA2, AES-CTR, etc) that create "entropy" deterministically. :-) – LateralFractal Sep 14 '13 at 23:30
  • Thanks for taking the time to answer, very informative, and a lot for me to think about. – ian Sep 15 '13 at 13:15
  • "A single photo ought to contain a lot of entropy, unless the camera output is covered in some way and the picture is uniformly black. " Actually, camera sensors are noisy, and a dark picture may actually work better. – Luis Casillas Dec 06 '16 at 19:28
  • 255 bits for a 256 bit output? Where does this come from? I was always under the impression that feeding input with 256 bits of entropy to a (properly designed) 256 bit hash function would result in a digest with the same amount of entropy. – forest Dec 30 '17 at 10:44
  • 1
    @forest: a hash function with a 256-bit output is not (usually) a _permutation_ over all 256-bit possible inputs. For a random _function_ with an output space of size _N_, you expect that applying it on _N_ distinct inputs will yield about 0.63 times _N_ distinct outputs. – Thomas Pornin Jan 03 '18 at 14:48
  • I'm not really sure I agree that encouraging people to roll their own entropy sources is such a great idea. How is this not similar to encouraging people to roll their own crypto? It seems like there's a lot of ways to screw this up. i.e. it's completely dark and everything is black. it's too bright, and everything is white. There's something physically wrong with the camera, but it still gives output. – Steve Sether Jul 23 '18 at 14:42
9

Would taking a photo using a smartphone and using the RAW file's bytes count as a good way to get a large random number quickly?

In and of itself, no. Digital cameras are designed to capture signal rather than noise, so both the dynamic range and palette compression are designed to fit optimal human vision; not uniform noise distribution. While a RAW file image is a good idea, it will need to bypass the camera's firmware as the firmware "helps" by doing a lot of this image optimisation on the chip - the data fed into the operating system might have already been optimised and cleansed according to various criteria.

But if you can directly use the CCD sensor and tune it for maximum noise (and minimum signal) within a lightless container - a decent noise source can be created.

Holder could recognise by sight, and yet could also deny was a key?

Sadly no, unless the key isn't the whole image but instead a steganographic data stream embedded within the image - as a random image will look, well, random. Which would raise questions in itself for a suspicious attacker.

More sensitive cameras ... would this be one way to protect against intentional flaws being introduced?

There are three different things to consider with "more sensitive" cameras and market forces:

  1. For customers this means more megapixels; which is an improvement in the bandwidth of the sensor but says nothing about its inherent entropy (or signal-to-noise ratio).
  2. For customers "more sensitive" can mean more responsive to varying light conditions. This means more image processing with the intent of reducing sensor noise and artefacts.
  3. People and hence market forces tend not to be aware of how good humans are at matching patterns and how bad humans are at detecting random noise.
    • I could manipulate the values of pixel integers in a way that would almost completely subvert their use as a cryptographic random number source without it being apparent to the user's eye. For example, consider a greyscale image of 10x10 pixels with range of 256 values. I could halve or worse (I don't recall the exact maths) the level of entropy by simply rounding each pixel value to the nearest even value. The human eye wouldn't be able to detect such minute differences.

Further thoughts

The public could certainly benefit from a TRNG application for a mobile phone. Mobile phones have a wide variety of useful peripherals for noise collection. The limitation is whether these sources are accessible at a low level of abstraction.

Proving that a analog source is random is rather difficult; an analog source processed by an inherently digital mechanism even more so. Each camera chip might be subtly different (even on a iPhone monoculture), so a TRNG application would have to have these complex statistical metrics built-in so it can "tune" for each phone.

There is an understandable antagonism toward "rolling your own crypto" and creating a RNG is similar; but if no published well-vetted solution exists for the specific problem domain, then one open-source application is as good as another for starting the peer review process.

LateralFractal
  • 5,143
  • 18
  • 41
  • Thanks for the detailed answer, I was unaware of the firmware issue, I'd already noticed a wide array of RAW formats though :/ On the subject of "Holder could recognise by sight, and yet could also deny was a key?" wouldn't any photo be, essentially, random? Time, subject, environment, camera, and angle would essentially make it a unique object (disregarding processing). Like this Dilbert comic http://search.dilbert.com/comic/Random%20Number%20Generator. – ian Sep 14 '13 at 12:02
  • Well, this is the difference between unique and random. Random is maths shorthand for unpredictable. Unique on the other hand can still be predictable. If you show me 99 photos of the Eiffel Tower at night, I can reasonably predict the 100th photo will be the Eiffel Tower. The byte content of each photo will naturally differ but majority of bits would be predictable both within the image and between images. Hence the need for a light-less capture or at least a completely unchanging image source - so the most obvious patterns can be avoided or stripped out. – LateralFractal Sep 14 '13 at 12:30
5

It is true random, but obviously a little overkill. As launching camera and taking a picture is somewhat slow operation, and the user would be amazed if she found the camera is constantly turning on and off.

Smartphones have a lot of other sensors you can utilize, like the accelerometer, ambient light sensor, I believe these are much more efficient and hopefully more energy efficient. I think I have read somewhere that CPU uses its thermistor to acquire true random data, this is a great idea.

zerox
  • 51
  • 2
2

Besides the camera and microphone, we have one more source of enthropy: the user or, more specific, the timestaps of the user's actions.

So I suggest to combine the image itself, the date when it was taken, and the time since system start (which is available on most systems).

Kirill Gamazkov
  • 165
  • 7