A One Time Pad (OTP) sounds perfectly secure if we are to believe Wikipedia. But on the surface it also sounds ridiculously impractical - how does one securely distribute the OTP?

Idea: why not have someone distribute it for you in plain sight of everyone?

Presuming I can keep the details secret (as I would with an encryption key), if I wanted to communicate securely, why wouldn't I harvest the images from some source of abundant images (Facebook, news site, dating site, porn site, etc), and make use of the noise in their lower bits to create a one-time-pad?

Even assuming someone hacks my PC and can narrow down the image(s) I may have used, an image is not in itself an OTP - you need to extract the OTP bits from the image pixels. That can be done in an enormous number of ways. The secrets to doing it are more or less equivalent to conventional encryption keys.

E.g. I could shuffle the pixels in the chosen image before using them in one of N! possible shuffles for N pixels, which is enormous after even 50 pixels. I could also extract the OTP bits from the image pixels starting from any pixel and in a bunch of scanning directions/modes. And which bits do I use, and in which order? Plenty more permutations there to be guessed at by anyone wanting to crack my code.

Which raises a different possibility: why don't I distribute the algorithm for permuting the pixels and extracting the bits to create the OTP from a single image?

I'm suggesting this because I noticed a while ago that the original image posted on Wikipedia of the Mona Lisa happened to have prime numbers for its width and height. That sounds like a useful property to someone wanting to generate an OTP. You don't suppose someone is already using it for that, or some other cryptographic purpose, do you? After all, this image size is the only one that Wikipedia has repeated, which seems... improbable as a coincidence.

Yet all of this completely contravenes the advice of "don't roll your own". Does that advice still apply to an OTP that is truly only ever used once, even if its random bits are pseudo-randomly selected each time in one of extraordinarily many ways from a single source of truly random bits?


marked as duplicate by e-sushi Jun 11 '18 at 0:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ The question you are trying to ask is this: Since one-time pads can offer a provably secure means of encryption, why don't we use them? That question has already been answered on this site several times. By the way, Wikipedia articles are often full of errors because anyone can write them, edit them, vandalize them. Those articles are not authoritative. One more point you should consider is that generating prime numbers has nothing to do with creating truly random keys. $\endgroup$ – Patriot Jun 9 '18 at 11:02
  • 2
    $\begingroup$ If a key is not truly random, it can not be an OTP. And simply calling something OTP does not provide its security. BTW: the adversary knows everything except the key, including any method your algorithm uses to extract information of other data and any public data of course. Making things complicated does not automatically provide a single bit of extra security. $\endgroup$ – tylo Jun 9 '18 at 16:10

Using public sources for key material is a well known concept. Book ciphers go way back.

But it is a mistake to think youre key is a largr OTP of random bits extracted from public source. The real key is the choice of images.

You and your partner will have to agree on a set of publicly available images to the basis for extracting bits. That is your key which you need to share somehow.

The possible number of images on the internet is significant and yet much less than two to the power of the number of random bits you plan on extracting. Furthermore you will probably not be able to select randomly from all images but rather be selecting from some image pool smaller than "the internet".

Adding an extra fixed permutation will add little extra security.

  • $\begingroup$ Adding extra FIXED permutation? No: read that last paragraph - it advocates making a one-time permutation (never re-used) to a bunch of bits that are already (more or less) random. Cryptographically random? Maybe not. But if they are "sufficiently random" for a single-time use, does permuting them in one N different ways extend their usefulness? If N is roughly 10 or even 10^6, then it's complete fool's gold. But if N is more like 2^128, one what grounds is what is advocated different from a conventional 128-bit encryption process? $\endgroup$ – omatai Jun 10 '18 at 2:14
  • 1
    $\begingroup$ Indeed, yet it doesn't seem to specify when it is selected/how it is coordinated. A minor point in the question regardless. $\endgroup$ – Meir Maor Jun 10 '18 at 3:46
  • $\begingroup$ @omatai, how do you plan to distribute your choice of one-time never-to-be-reused permutation? How can you trust that distribution channel? And if you can trust that distribution channel, why not just use it to distribute an actually random one-time pad? Your scheme has zero advantages over actual OTP and a great many more weaknesses. $\endgroup$ – Wildcard Oct 17 '18 at 2:09

The general idea in crypto is that the system is protected by the secrecy of the key, not the algoithn. Your proposed system requires that the algorithm for generating the key be kept secret.

There are simpler ways to do that, for example, given a seed value you could XOR the output of some selected DRBGs as the OTP. What’s secret then is the DRBGs used.

  • $\begingroup$ You realise that this won't be a OTP though if it's deterministic? $\endgroup$ – Paul Uszak Jun 9 '18 at 15:18
  • $\begingroup$ Just as much an OTP as a non-deterministic one. You can just never use the same seed twice - it’s a nonce. $\endgroup$ – Swashbuckler Jun 10 '18 at 1:08
  • $\begingroup$ A Twitter message encrypted with a OTP might use a key with an entropy of 1280 bits. You'd need a choice of $ 10^{385} $ DRBGs for an equivalence. That's probably not practical. $\endgroup$ – Paul Uszak Jun 10 '18 at 2:46

But on the surface it also sounds ridiculously impractical - how does one securely distribute the OTP?

This notion comes up frequently on this forum. Distribution is absolutely not ridiculously impractical. Key distribution is harder than other forms of cryptography, yes. But it's not insurmountable as the Wikipedia entry, history and your very existence post the Cuban Missile Crisis proves. The military do it with couriers and hardware fill devices full of key materials, diplomats do it with diplomatic pouches and spies did by just hiding a book full of key material on their person. Now they and you can simply transport a flash drive with enough material for billions of characters. A few years ago you could even listen to OPT messages being broadcast via public radio across the world.

Then there are more exotic key exchange mechanisms. Can a key exchange protocol exchange a one time pad instead of a key? suggests that it may be possible to simply generate/transmit the key between two parties using public key cryptography. I'm not convinced and the question remains open. And of course quantum key distribution networks do this as their raison d'être.

Authentication is also not an impediment to adoption. I don't know why people think that it is. Simply apply standard HMAC techniques to the message. You won't have perfect authentication security comparable to perfect secrecy of the OTP, but it will be at the same level as any other current HMAC technique. It will be a mathematically impossible to break message with currently impossible to break authentication.

And finally to the Mona Lisa. (I've never liked it). You may be able to eek out a few bits of entropy from various images here and there, but hardware random number generators are easy to buy and fairly simple to build. You can even use a webcam or camera phone and hash low light images. You can see the efficacy of this technique here. Or sit down in front of a Linux box and type:-

dd if=/dev/random bs=1 | xxd

Then do whatever you do with computers for the remainder of the day whilst watching true random numbers scroll down the terminal window. It's important you do things this way around as your interactions create the entropy that /dev/random then extracts. Redirect it as appropriate.

  • 2
    $\begingroup$ I'm not sure what question you thought you were answering, but it doesn't feel like my one. $\endgroup$ – omatai Jun 10 '18 at 2:20
  • $\begingroup$ @omatai Your title, 2nd paragraph and my quote? It's clearly not ridiculously impractical. $\endgroup$ – Paul Uszak Jun 10 '18 at 2:38

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