Fun

Thoughts On One-Time Pads For Cell Phones

Best short description of one-time pads (OTPs) is from Jason Matthews, who is describing their use in the heyday of the cold war in the book Strangers on a Bridge by James B Donovan.

Before the advent of automatic enciphering technology, secure radio communications between an intelligence headquarters and its agents in the field were abetted by use of one-time pages (OTPs, sometimes referred to as “cut numbers”). These cipher pads were individual sheets of printed rows and columns of five-digit numerical groups. The pads were bound with rubberized adhesive on all fours sides, and normally printed small for concealment purposes.

A field agent would receive a shortwave radio broadcast from headquarters via one-way-voice link (OWVL.) These OWVL broadcasts consisted of a monotone female voice reading a series of recited numbers—an enciphered message. The agent would record the recited numbers in five-digit groups and subtract them on the correct OTP page. The resultant values would correspond to the 26 letters of the alphabet and reveal the message. Because each page of the OTP is randomly different and used only once, looking for patterns in cryptanalysis is futile. It is an unbreakable cipher…

Indeed it is unbreakable. Eat your heart of quantum cryptography! Because, in essence, every character in a OTP is separately encrypted, and each pad used only once, the code is impossible to break. I use impossible in its literal sense. No computer no matter how powerful running for any amount of time can decipher the message. That is to say, unless the “key” which generates the OTP can be discovered.

Since random means unknown, the “secret” to key generation is an unknown process. Here, of course, “quantum” events can be used, say, in the form of static of radios tuned to unused stations—as long as that static is atmospheric, or preferably extra-gallactic, in origin and thus unpredictable. Using any kind of “random number algorithm” produces, as all experts know, perfectly predictable, deterministic keys. (This, incidentally, is why in Uncertainty, I recommend against simulation methods.) Also, the device used to capture static must itself be as “noise-free” as possible, since known circuitry could generate predictable signals.

OTPs were used well after the advent of “automatic enciphering technology”. I recall in the early 80s listening on shortwave to “numbers broadcasts”, almost always in Spanish and male voices, in San Antonio. (Not only did I get my start in the Air Force in a cryptographic specialty, I was and am a “ham”; back then I was KA5YHN and am now K2JM.)

Shortwave broadcasts have the added benefit of disguising the intended receiver, which could be anybody with a radio and a length of wire. This is important to discourage “SIGINT“, or signals intelligence, which is the study of where, when, and how signals are sent. A surprising amount of information can be gathered about an encrypted message, even if the cipher is never broken, simply by paying attention to the transmission. SIGINT is called “meta data” with respect to your cell phone and computer messages, and that “secrets” about you can be discovered using it alone and ignoring the actual content of your phone calls and emails is why we don’t want the government, or other sources, evasedropping on our conversations.

Real OTPs must be destroyed immediately after use, or the cipher can be broken. They must be used only one time, or patterns will stick out like a Republican in an Anthropology department.

Now, with our hand-distractions, it is easy to store very large electronic OTPs (which can be used in encrypting text or digitized voice); it is even easy to generate keys, assuming the cautions about unpredictable generation are minded. The problem comes in swapping keys with recipients. You have a cell phone on which is the OTP App. How do you communicate this key to your friend? The key has to migrate from your device to his. It could do this via Bluetooth, but doing so exposes the key to the world. The device itself, unless it is well shielded against electronic emanations, can leak the key (this is called Tempest security). The key may be shifted to something like a thumb drive or SD chip, and then the chip inserted into your friend’s phone. The chip must then be destroyed, as in utterly, or otherwise rendered unreadable (perhaps by rewriting on it new unused keys many times).

This meeting between you and friend must take place. You can’t use an old key to transmit a new one, because with OTPs it’s digit-for-digit: compression of keys is impossible. Transmission of the key over the air or, say, internet exposes it. Anything short of a hand-to-hand swap exposes it. Since a meeting must take place, the usefulness of OTPs is limited. But very useful is absolute, unbreakable security is desired.

There are more problems, besides Tempest leakage. Suppose you are receiving the encrypted message from your friend, and decrypting on your device (ignoring electronic leakage, which is no small consideration). The device will still have the key and the plain-text message! Of course, this is no different a situation than the spy who sits in his room and has on hand the OTP and decrypted message. But a small piece of paper, or two, is easier to destroy and conceal than a cell phone.

This means the key must be self-destroying. As it is used, the places on the storage device must be re-written dynamically, and in such a way that no fine probing will ever reveal what was originally written. No easy task. And the same must happen to the message itself, after it is made use of. For voice communications, this is easy, because they’re (forgive me) in one ear and out the device. But texts (or emails, etc.) must be guarded more zealously.

OTPs are in use still on the internet, with otherwise innocuous web pages and images containing updated version of the five-number groups. Decrypting short messages can, and surely are, still processed by hand using paper OTPs. But long messages or other formats is not different than the two cell-phone case. Key swapping must still take place—as it did with paper OTPs, of course.

SIGINT for cell phones, and even web sites, is still a problem. Even thought the OTP App works as desired, your enemy will still know when you sent the message, where you were when it was sent, where your friend was when he received it, and how long that message was. That last item is perhaps the most revealing. So lucrative, if I can use this word, is this that stations have taken to swapping continuous messages so that outsiders never know when the real one starts and ends and how large the message was.

One last point about spoofing. A concern is that an enemy agent can inject numbers into the “code stream” which might mistakenly be taken to be real by the recipient. But unless the spoofer knows the key, and therefore hasn’t much need of spoofing, injection is immediately detectable. Which is also a boast of quantum-key cryptography. In that, incidentally, key swapping must still take place, though it is of a different form.

Conclusion? For cell phones, anyway, the whole thing is possible, and not even so difficult. The problems are signal leakage, lost phones, SIGINT and of course the key swapping. Just as with paper OTPs, we aren’t limited to only two phones, but an indefinite number in a network.

I always wanted to try this, but I am not a coder (though I code). The ideas are so obvious they must already be in use somewhere, but I’m too lazy to look them up.

Categories: Fun, Statistics

12 replies »

  1. Briggs, you’ve given it away. The typos aren’t attacks of your enemies or even plain mistakes; they’re encrypted messages. Very sly. But this reveals the weakest link in all this spy stuff — human error and/or the inability to keep a secret. Btw, if saw two misspellings in this post. I wonder what they mean and to whom…

  2. Many years ago I had the idea of, working with a friend, sending random text back a forth between us, to see if anything would happen and how long it would take if something did. I decided not to do it for fear the NSA algorithms would construct a threat from the messages and a black suited SWAT team would kick in my door.

  3. Ken Follett’s “The Key to Rebecca” comes to mind

    Instead of having the “key” on your phone and exchanging the key with your counterpart, just access the HTML for the on-line book and download a plethora of titles. In Follett’s story, there were just so many books you could keep on your person along with whatever else you needed to carry [one].

  4. I’m not a cryptographer, so I am not an expert on the math, but I work as a professional network security programmer. My understanding is that in terms of theoretical security, modern public-key cryptography is just as effective as one-time pads. You do need a secure source of entropy and you do need to keep key material secret, but you don’t have to share secrets with the parties you wish to communicate with. From everything I’ve read, including the latest CIA Wikileaks information, all of the significant breaches of communications security in recent years have been by exploiting bad implementations of security software, not breaking the crypto protocols themselves — problems that would be faced when using OTP as well. (I am quite skeptical of claims that quantum computers will be a credible threat to communication security in my lifetime, but “post-quantum cryptography” seems to be a topic on which the math guys are making progress.)

  5. Interesting. Yet it is HUMINT that in the end gets the things that SIGINT need. Thus, practically, every useful code can and will be broken, eventually.

    Corollary, if you’re broadcasting, there is no privacy; just as there isn’t any privacy sending a post card.

  6. ashv: The underpinning of private/public key pair cryptography is very large prime numbers that take a long time to generate. Brute force is effective against SHA1 and successors (never mind the little defect in SHA1 that reduces the complexity to merely galactic) *because* the generator code is available to everyone and all you need is the “seed”. So you take a message and start cracking. Once you have the seed and the sequence, you can then easily decrypt the rest of the message.

    With a one-time-pad, or ANY key that is longer than the message, it cannot really be brute forced. As you go through all conceivable possibilities you are actually going to generate many false positives; entire messages that simply are not what was written.

    Back in the day in the Navy, we kept the radio transmitters going constantly. Most of it was fake. But at designated (and random) times of the hour we would send something legitimate. This prevented traffic analysis. If something urgent came along, well, it’s going to have to wait.

    I’m now an extra class ham radio operator so “old school” radio is still interesting to me. __… …__ … _._

  7. A couple of comments…

    @ashv – nothing is as theoretically secure as a one time pad. It may be practically as secure, but proving it is hard.

    Briggs… are you aware of the Venona Project, where the NSA and FBI partially broke the Soviet “one time code” and thus proved (when it was finally released in 1995) that all the accused spies were actually, yep, Soviet spies?

    The problem is that the Soviet code was supposed to be one time. But given the Stalinist 5 year plans, with requirement for ever increased production, and Stalin style penalties for failure, there was a little oops.

    https://www.nsa.gov/news-features/declassified-documents/venona/

  8. “With a one-time-pad, . . . As you go through all conceivable possibilities you are actually going to generate many false positives . . . ”

    Actually, it’s far more hopeless than that. If you were to brute-force all possible OTP encryption sequences, you would generate all possible plaintext messages, all equally likely candidates to be the true message.

    One interesting case would be a OTP that decodes, say, a news story (or a comment on a blog) into a secret message.

  9. Milton Hathaway writes: “One interesting case would be a OTP that decodes, say, a news story (or a comment on a blog) into a secret message.”

    Easily done with XOR (exclusive OR). The key or OTP becomes the XOR of the news story with the secret. It is the XOR itself that sent to the other person; he or she can download the same news story from a source and it won’t be known what is that source. Then apply the XOR again and recover the secret.

  10. The technique offered is a variant of techniques that have been around a long time. For example, the actress Hedy Lamar patented a syste, during World War II where the key was a musical piece instead of a news story. The musical piece was used to vary the carrier frequency of a radio that was transmitting the secret – the first use of spread spectrum techniques.

    The technique offered is security by obscurity, not one time pad. The news story is out there – in theory someone could try every news story out there, which is a very, very small number compared to the possible number of one time pads of the same length. Also, the secret and the news story most likely have low information entropy, making this vulnerable to standard cryptographic attacks.

    A basic rule of cryptography is that unless you are an expert (and they are few and I am not one, but I listen to them), don’t try to come up with a scheme, use one that is believed by the experts to be strong. Even then, there are no guarantees.

    If you want to use a one time pad, all you have to do is get a source of truly random numbers (I can see Biggs wincing). Put another way, a source of numbers that is from a source that nobody can duplicate exactly and that passes a lot of well known tests for randomness – such as diode noise or other effectively random process. Even there, unless you are an expert, the chances are that it isn’t as “random” as you would expect, and might be attackable by the pros out there.

    The Venona Decrypts were much harder to do than an attack on this news story system, BTW.

  11. Having similar working experience (in the Navy, crypto and Morse radio operation, etc) I learned that privacy and security are both violated as soon as code (like OTP) is shared between 2 parties. To parties we must count persons and devices. Further to that, bare communication cannot be made in secret (it’s always like everybody else can listen to whatever is exchanged).

    Perhaps the bitcoin protocol (nonce, hash, etc) is a solution, by exchanging character codes instead of monetary value codes (technically they are same).

Leave a Reply

Your email address will not be published. Required fields are marked *