Note: phiên bản Tiếng Việt của bài này ở link dưới.

https://duongnt.com/one-time-pad-vie

One time pad, the perfect encryption

One time pad (OTP) is a very simple encryption. Its algorithm is like this.

• Convert the data you want to encrypt into binary (we call this the plaintext).
• Generate a true random binary array with the same length as your plaintext (we call this the pad).
• Perform bitwise XOR between the plaintext and the pad, the result is our cipher.
• To retrieve the plaintext from the cipher, we just need to XOR the cipher with the pad.

OTP is the only encryption that has been proven to be perfectly secure. If used properly, the cipher doesn’t reveal any additional information that we didn’t already know about the plaintext. For our example above, from the cipher 0011 1010 1101 1101 we know that the plaintext is at most 2 bytes long. However, for any 2 bytes long data between 0000 0000 0000 0000 and 1111 1111 1111 1111, there is a pad that when XOR with the cipher will give us that exact data. And because our pad is truly random, without it, the best solution for an adversary to crack the cipher is random guessing.

One time pad, the not very useful encryption

If OTP is so simple yet perfectly secure then why do we still need AES, RSA or any other encryption? The answer is because to be perfectly secure, OTP needs to be used in a very specific way. It has to satisfy the following requirements.

• The pad must be truly random and is at least as long as the plaintext.
• Both the sender and the receiver must have the pad and keep it secret.
• The pad must not be reused.

Let’s go through each point above one by one.

The pad must be truly random and is at least as long as the plaintext

Generating truly random data is not as simple as it sounds, especially when we need the pad to be as long as the data we are trying to protect. In most cases, a computer can only generate pseudorandom data. It actually uses an algorithm to derive seemingly random data from a seed. That seed might be chosen by the user, or taken from some information that is hard to guess, like the exact current time.

Some pseudorandom number generators like CryptGenRandom, Yarrow or Fortuna are even called cryptographically-secure. This means the values they provide are almost indistinguishable from true random and thus suitable to be used in cryptography.

Does that mean we can use a cryptographically-secure pseudorandom number generator to generate our pad? Unfortunately no, because a chain is only as strong as its weakest link. Our encryption would also be cryptographically-secure only, pretty good but nowhere near perfect.

That doesn’t mean we can’t have truly random data. There are ways to measure atmospheric noise, thermal noise or some quantum phenomena and convert them into random data. But this method is complicated and slow. We need to harvest enough randomness from an outside source before we can generate random data. And it’s also necessary to compensate for any bias in our measurement process.

Both the sender and the receiver must have the pad and keep it secret

This condition sounds simple at first, but let’s think about it. If we have a secure channel to transport a pad which is as long as the plaintext then why bother with OTP? Just use that channel to share the plain text directly. This is actually the biggest drawback of OTP and severely limits its application.

Some of you might wonder why we don’t just use a key exchange algorithm? It’s true that exchanging secret information on a non-secure channel is not a new problem, public-key cryptography has solved it quite well with algorithms like Diffie–Hellman or ECDH just to name a few. But when trying to apply them to OTP, we face two major roadblocks. The first one is traditional key exchange algorithms were designed for short keys and are not efficient with big pad (remember that the pad needs to be at least as long as the plaintext). And the second reason is again the chain and weak link story. After all, no key exchange algorithm is perfect.

The pad must not be reused

We will perform a small experience to see why it is a bad idea to reuse a pad. Let’s say I have this image.

I XOR it with a pad and get this, which looks random enough.

Now I have another image here.

I XOR it with the same pad above and get another random image.

Everything seems okay right? Well, guess what is the result when we XOR the two ciphers above.

Suddenly, we have a pretty good idea of what the two plaintexts look like. You can try it out yourself with the script I’ve uploaded here. Since I used urandom to generate the pad this is technically not OTP, but it is good enough for a demo.

https://gist.github.com/duongntbk/12b5bca15b7b297dbba4f9502ad46ebe

Is there any use for OTP?

It’s such a shame that a simple yet secure encryption like OTP is not very useful in practice. Is there any case where it is suitable? Actually it is. OTP allows us to have a secure meeting in advance. Let’s say you meet a friend in person and exchange a USB drive full of truly random data. Now you and your friend can safely exchange information with each other at a later time. It’s clear that such situations most often happen in espionage.

The most famous application of OTP I can think of is the Moscow–Washington hotline. To quote Crypto Museum.

Rather than using American or Russian cipher machines for the encryption of the messages, the ETCRRM machines were built in Norway by STK 1, who was considered neutral and impartial.

As the ETCRRM is a One-Time Tape machine (OTT), it uses the principle of the One-Time Pad (OTP). When used in combination with truely random key tapes, an OTT machine is absolutely safe and unbreakable. As the Russians insisted on producing their own keys, it was decided that each side would create their own key tapes.

These key tapes were then delivered by special couriers to the embassy at the other end, who then delivered it at the other party’s terminal [9]. So, the American Embassy in Moscow delivered their key tapes at the Moscow hotline terminal.

Conclusion

Nowadays, storage has become so cheap that storing terabytes of data is not a problem. And while not trivial, generating truly random data is not too hard, especially if we have a long time to prepare. All this means that as long as they understand how to use it properly, anyone can take advantage of OTP. What about you? Do you ever want to have a secure meeting in advance?