Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 3 down vote favorite

Say you have a picture with 1 megapixels taken at random and with $2^{24}$ possible colours per pixel (RGB-24). That image would be unique and the possible combinations $(2^{24})^{10^6}$ immense.

However when taking a picture in the real world, say of a clear sky, there will be a lot of repetition.

The question is: would such repetition present a security risk when used as a one-time pad, where the requirements of randomness is so high?

My hunch is that it is, as true randomness would require the possibility of all pixels being #FF0020 or whatever, but I would like to be proven right or wrong.

If I've been unclear at some point, please let me know and I will edit my post.

share|improve this question
1  
I am pretty sure that at 1MP it's "okay" if it's not truly random. Also, is it really "less random" or does it just have "less distribution"? – pst Sep 7 '12 at 22:18
Oops, wrong click... And now I voted for a wrong comment.. Sorry – Alex Cohn Sep 10 '12 at 7:51
You need full control of the acquisition process in order to avoid fake images (as demonstrated by John Deters). You usually have better sources of random bits than camera. – Alex Cohn Sep 10 '12 at 7:54

migrated from stackoverflow.com Sep 7 '12 at 22:19

5 Answers

up vote 11 down vote accepted

No. This is not safe. The one-time pad requires that the pad be generated by a true-random process, where each bit of the pad is chosen uniformly at random (0 or 1 with equal probability), independent of all other bits.

Any deviation from that, and what you haven't is no longer the one-time pad cryptosystem -- it is some kludgy thing. In particular, once you deviate from that requirement even a little bit (and you're talking about a huge deviation), you are skating on thin ice and there will probably be security problems with your scheme.

If you're gonna use the one-time pad, you gotta use it exactly as it is defined, with a truly-random pad. There are no shortcuts, no halfway stuff. Messing around with this sort of thing is exactly what enabled the US to cryptanalyze Soviet use of a "one-time pad" in the VENONA project.

But in practice, you probably don't want to use the one-time pad anyway. The key management issues are enough that it is rarely a good choice in practice.

share|improve this answer
I see, so despite the ridiculous number of combinations the pixels in a photo provide, the fact that there is a limit at all, makes it insecure? I appologize if I seem a bit thick, but it's hard to understand how the scattering of light such as that picked up by a camera does not fill the above criteria. The thought was to reduce key generation time but now I'm all confused (that's a good thing though :) – youjustreadthis Sep 8 '12 at 1:10
Yes, it is insecure. The "number of configurations" is not the parameter that is relevant to security. The security of the one-time pad relies upon the requirement that the pad be truly random, with no patterns whatsoever. Violate that requirement, and it's not a one-time pad any longer. Anyway, the one-time pad is not really suitable for practical use in any case, so this is pretty much moot in practice anyway. Use modern crypto; its key generation time is negligible. – D.W. Sep 8 '12 at 1:13
I see, thanks for the help. I know that key distribution issues and practicality makes it outdated, but the concept of "perfect security" (at least the cryptological part) is intriguing. – youjustreadthis Sep 8 '12 at 1:31
up vote 4 down vote

You should not use the raw data of any image as a one time pad. This is even worse with an image of a sky, because of the large amount of blue pixels. For all images, adjacent pixels tend to be the same colour - which means there is a large amount of repetition.

If you want to use some of the data of the image as a one time pad, you will need to condition the data (concentrating the entropy present in the image).

A simple example of concentration of entropy is to take 2 not-so-random integers, a and b, and perform an operation, such as (a*b+a+b), then extracting the lower order bits (probably half). This scheme would eliminate bias present in the original integers. Of course, a more complex scheme is probably required.

A simple scheme you could use, which would be quite random, is to use a digest on the data. If for example, you believe that a third of the bits in the image contain useful entropy, then from every 64 pixels, containing 64*24 = 1536 bits, feed it into a SHA512 hash function, which will output a 512 bit digest (that is 64 bytes). You can then use that output for your one-time pad.

An IEEE article on Bull Mountain, Intel's Random Number Generator, includes some discussion on "concentration" of randomness, when the input data is not random enough.

share|improve this answer
Thanks for the thorough and useful answer. I do understand your point about repetition, however I'm not sure I managed to follow you on the useful entropy bit. Wouldn't the unpredictable nature of a large picture result in sufficient entropy for every bit involved, be it after a thorough shuffling or for example hashing pixel nr 1 with nr 10, 2 with 11 and so on? – youjustreadthis Sep 8 '12 at 0:01
2  
I agree with the first paragraph, but the remaining paragraphs are problematic. Any scheme that begins with "take something not-so-random, then process it a bunch, and use it as a pad with the one-time pad" is deeply dubious, and probably violates all of the security benefits of a one-time pad. The main benefit of the one-time pad is it is "provably secure", but this only holds if the pad is truly random (all bits iid uniform random). If the pad is generated by taking something sorta-random and then processing them, the security proof no longer applies, and you're on sketchy ground. – D.W. Sep 8 '12 at 0:35
1  
Fully random means having enough entropy for the number of bits. For example, if you have 10 bits of random data, it should have entropy equivalent to 10 bits. If you have instead 20 bits of data with entropy equivalent to 10 bits, it is not completely random. However, if you are able to shrink the data to 10 bits, so that it is 10 bits with 10 bits of entropy, it becomes fully random. – ronalchn Sep 8 '12 at 4:42
It means that even though the image might be 1MB, you do not have 1MB of fully random data, by concentrating the entropy down to say 100KB, you might then have random data. – ronalchn Sep 8 '12 at 4:43
4  
This will only work if you have a good randomness extractor, which is not as trivial as you seem to think. – Paŭlo Ebermann♦ Sep 8 '12 at 14:34
show 1 more comment
up vote 3 down vote

The reason repetition is so dangerous is imagine trying to attack a worst case scenario: a BMP picture file that contains all black. The contents of the image file will be #000000 #000000 #000000 #000000 ... Now consider how a one-time pad works: it XORs the cleartext with the bit stream. So if your plaintext was "ATTACK ON 10 SEPT", and you XORed it with an image that started with some repeating black pixels, the resulting "cipher text" would be "ATTACK ON 10 SEPT". I wouldn't be surprised if your enemy is not surprised.

Any swath of repeating bytes in the key file will do the same. The attacker just has to try 255 guesses to look for stretches of intelligible ASCII text.

Long ago a friend of mine wrote a proxy that used XOR "encryption" like this. My first attempt to discover his key was to download a black .GIF file, and his "secret key" printed itself in front of my eyes.

share|improve this answer
   
... although if the process involves controlled capture with an attached camera, the #000000 problem can be excluded. – Alex Cohn Sep 10 '12 at 7:50
1  
@AlexCohn, certainly, a controlled environment can be different. That was the basis for LavaRand. But taking pictures of a stochastic system is different than taking random pictures, which is what the question was about. Regardless, you wouldn't use the photos of LavaRand directly anyway, as there was a lot of repeat in the background. LavaRand used the images as input to a hash, and derived relatively few bytes per frame from the pictures. – John Deters Sep 11 '12 at 3:54
methinks that taking random pictures should be OK. No way as a 1M*3/2*8 random bits, but (wild guess) 256K random bits, provided the lighting conditions are in natural range. – Alex Cohn Sep 11 '12 at 6:15
up vote 3 down vote

The amount of randomness in common pictures has actually been studied thoroughly, just not for applications to encryption, but rather for stenography. An artifact of images is that the least significant bit (it is what changes between slightly different shades of blue) has the highest entropy.

A simple stego-system is to overwrite the least significant bits of a picture with, say, a ciphertext or key (both of which are random—either pseudo or truly random respectively), a compressed plaintext (high entropy) or a raw plaintext (which is of low entropy). In either case, it is generally practical to distinguish between the true distribution of LSBs of an image and either things of higher/lower entropy.

A consequence of this is that an image does not make a good one-time pad, as even the most random aspect of the image is not random enough.

share|improve this answer
up vote 2 down vote

Great question. I had actually been thinking about the same thing some time ago, but I realized that using an image as a one-time pad isn't a good idea. Try to take some random pictures and then open the pictures with a hex editor (like XVI32). I did that and noticed that the bytes were not all that random, for example many picture files have a lot of 0x00 bytes. Even though this is only for a part of the picture, it would still give someone a head start on trying to decrypt.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.