[Cryptography] New White Paper: GhostLine - Information-Theoretically Secure Multi-Party Chat

[Jon Callas]

A long time ago, I wrote an article that I titled, "The Seduction of the One-Time Pad" -- it might still exist, or it might have been lost to the mists of archival storage. I used the word "seduce" there intentionally in the same way Gandalf used it when he said that Sauron seduced Saruman, particularly with the technology of the palantirs. Information-theoretic security, particularly in the guise of a one-time pad is a glittering thing one almost can't take one's eyes off of. And yet, almost certainly, one should turn away from it, because it is almost never suitable for the task at hand and is at best a distraction from some perfectly fine other systems, most of which are a riff on the one-time pad system.

One-time pads are perfectly fine for low-bandwidth, high-latency, short-content systems. Numbers stations, physical letters written with invisible ink, and so on. The more that the use case doesn't meet those (and other) considerations, the less suitable it is. One issue with one-time pads is that they're malleable, by which we mean that if an adversary can modify the message in transit, whatever they modify is trivially reduced to garbage. Another is that when you run out of pad material, you have to stop talking until you get more pad material. This is suboptimal. It's especially suboptimal in environments like the Internet, and "suboptimal" here is just a euphemism for other characterizations that have lots of swearing.

Let's look at information-theoretic security. Another way to state is is that if you have at least as much uncertainty as data, then your encryption algorithm doesn't need to be any fancier than XOR (or addition; in our case they're isomorphic). I'm using the word "uncertainty" here rather than than "entropy." Like the word "quantum," the word "entropy" sucks people's brains out and we lose the ability to discuss the situation rationally. There's a story that Von Neumann told Shannon to use the word entropy because no one knows what it means. I usually use the alternate term "unguessability," but today I'm going to use "uncertainty" because it suits my mood.

A long time ago, back when there was quote-quote export cryptography, a colleague of mine worked on a project to encrypt credit card numbers. I heard this story over lunch, also long ago, but after the demise of export cryptography, so time and whisper-down-the-lane might have induced errors. My colleague realized that it's easy to pare a credit card number down to below forty bits. The first four digits are a bank number, which is either a constant or a public value. The last digit is a check digit, and can be preserved or ignored or elided. So the protocol encrypted a 40-bit quantity with RSA, and instead of using that bit string as a key in RC2 or DES or whatever they would have done, they just xored the damned thing onto the data. Poof, Bob's your uncle, and Alice is your auntie. You also have the fastest cipher around in the guise of xor. 

Going past that, even today, if want to encrypt something the size or less than the block size of a block cipher, you can just use xor. This is pretty counterintuitive, but that's what information theory really is. When the data is smaller than the available shared uncertainty, then your encryption can be as simple as xor or addition.

If one lives in a world that has high-bandwidth, low-latency networks, the biggest operational issue is that you have lots of data and not much uncertainty. The big issue is to share that pad of uncertainty with your communications partner securely. That pad is also at best the same size as the comms you want to share. You can't compress the pad, it's random. If an adversary reads the pad, they will later read the data. You have to get the pad to your partner without the adversary reading it, and what are you going to do, encrypt it with another pad? We quickly get to it being pads all the way down.

I once saw a student project, where the student made a one-time pad encryption system for SMS. It was pretty good, actually, all things considered. SMS is reasonably low bandwidth, high latency, and fits the use case pretty well. The problem is how you get the pads exchanged and then protected once they're exchanged. A computerized one-time pad has great comms security, yet it's extra-vulnerable to malware. In that project, they decided that they'd transmit the pad via PGP with a 4096-bit key. Well, okay, but that means the system is no more secure than that PGP message.

This is a paradox of information-theoretic security. When you get there, it *doesn't* mean your system perfectly secure, and *that* is the Sauron-like seduction. What it means is that the vulnerability in your system is somewhere else, which is a nice thing to know, but it's merely an externality. The glaring externality is transmitting the pad. This is why those old spy movies with someone carrying a briefcase handcuffed to their wrist are interesting -- that courier is carrying pad material. If an adversary reads the pad, perfect security goes to zero security instantly. In the case of handwritten notes, SMS, and stuff like that, personal delivery, courier delivery, or even the occasional encrypted message could conceivably be good enough. In a high-bandwidth, low-latency world, it's not because the operational considerations outweigh the data security ones.

At the very least, one-time pads double the transmission. Remember from the paragraph above that transmitting the pads reduce the security of the system to the security of pad transmission. Every tiny weakness there adds up. 

This brings us to the real, and to me crushing paradox. If you're going to use Mechanism X to transmit your pads, why not use that same mechanism to just transmit the message? Send it by courier. Send it by PGP. Send it by whatever you're using to send the pad! If you do that, then you cut your bandwidth in half. Information-theoretic security means that the most secure way to send a message is whatever you used to send the key.

There's a lot of room here to debate, and those debates would be fun. I'll prep the stage for such a debate by saying that the whole reason we have ciphers is a tradeoff between information security and operational security. If you don't have perfect operational security, then you don't have perfect information security. If you loosen your parameters on information security where you'd accept huge but not perfect security, then you can also get some slack in the operational security, and I believe that the total *system* security is better when you use a modern cipher -- and come on, these things are often around 2^256, which is a HUGE number; there are only 2^265 (I remember it because it's a digit transpose) atoms in the universe (or so they said when I memorized that). It's a really, really big number! I think it's a worthwhile tradeoff to ditch all the complexities of one-time pads and pad management for the simplicity block cipher. It's good enough.

	Jon