Prerequisites
In order to understand this article, you must understand what a XOR cipher is. I won’t go into too much details about it here as this is not the subject of this article, but because this is not a tough subject and I assume that only smart people are reading this article, I will give a short summary about it.
XOR stands for exclusive-OR. It is a bitwise operation that takes as input two bits and will apply the operation that you can see in figure 1 on it.
Now that you understand what the XOR operation is, the XOR cipher will be easy. Instead of one bit, you will take all your plaintext and you will XOR it with what is called a keystream that can be generated by different means, but we will come back on it later. When you will XOR those two strings of bits, you will in fact XOR the first bit of the plaintext with the first bit of the keystream, then the second, and so on.
We can define a XOR cipher as follow:
Ci := Pi ⊕ Ki ; Where C means “Ciphertext”, P means “Plaintext” and K means “Key” or “Keystream”. The i corresponds the the ith bit of each of those bit strings. If the key, or keystream is not at least as long as the plaintext, then you will not use Ki, but K(i%key_length).
History
The One-Time Pad is a concept that has barely more than a century. Gilbert Vernam, the creator of the Vernam cipher (which is another name for the One-Time Pad) created it in 1917. In fact, this version was missing one of the requirement that we will see further on: the randomness of the key. This requirement has been added a bit later by Joseph Mauborgne. In 1949, Claude Shannon demonstrated the security of the Vernam cipher.
Definition
Now that everyone has the basics and has seen a bit of history, we will start with the real topic: the One-Time Pad.
First thing first, the One-Time Pad in itself is not a cipher; it is more of a concept. This concept can be applied to several ciphers, for example the XOR cipher, which we have discussed earlier and which we will take as an example during this entire article. The One-Time Pad can also be applied on the Vigenère cipher for example. Most of the modern stream ciphers are based on this idea, while not reaching its goal.
It becomes interesting from now on: The One-Time Pad is unbreakable. But not unbreakable like “RSA 2048 bits key cannot be cracked because it would take more than a lifetime etc.”, because this assumption doesn’t consider the facts that:
[list]
[]RSA may be broken in the future (even if it’s really not likely to happen, but who knows?);
[]An attacker with a huge computational power can break a 2048 bits key;
[*]With the rise of quantum computers, RSA will be down quite soon.
[/list]
When I mean unbreakable, I mean that it is mathematically unbreakable and even if we consider that an attacker has an infinite computational power and quantum computers, he will not be able to retrieve the plaintext (I simplify here, we will see this point in much details later). This is what I will try to demonstrate in the next sections.
First, we need to give a definition of what is “unbreakability”. The unbreakability of a cipher can also be referred as the perfect secrecy that this cipher will provide. This is the ability that given an encryption scheme and a ciphertext, an attacker will not be able to retrieve the corresponding plaintext, even with an infinite computational power. Claude Shannon has given a definition of perfect secrecy, which is that:
[list=1]
[]The key must be chosen with equal probability among the set of all possible keys;
[]For a given plaintext p and a given ciphertext c, there is only one key k that will map p to c.
[/list]
We will not demonstrate this theorem here (please take a look at the last section for further readings), but we will show in the following sections that the One-Time Pad respects those requirements.
Application requirements
It is possible that reading the last section, you’ve asked yourself “If it’s unbreakable, why don’t we use it?”, and this is a good question. The answer is that One-Time Pad has several requirements that are difficult to achieve. In general, we consider that there are three requirements, but we often include a fourth one. We will discuss about the three first requirements in the three following sections, then we will discuss the fourth one in the last section.
The list of the requirements is the following:
[list=1]
[] The key must be used only once;
[] The key must be generated randomly;
[*] The key must be as long as the plaintext.
[/list]
What is often considered as the fourth requirement, but can be seen more as a problematic, is the transmission of the key. In fact, the One-Time Pad (even if it’s way older than modern cryptography and modern concepts, as seen in the History section), can be considered as symmetric cryptography, because the same key is used to encrypt the plaintext and to decrypt the ciphertext. Moreover, as this cipher works bit per bit, it is a stream cipher. So you might know that symmetric cryptography suffers from an impossibility to transfer securely its keys (this is why hybrid cryptography has been created, but it is another topic). This will be the topic of the last section.
Unicity of the key
Definition
Even if the title of this section is very clear, I will explicit that a little bit more.
The unicity of the key means that each time you will send a message, you will need to use a new key. At first sight, it might not seem that hard to achieve, but in practice, this is a major concern (even more when you combine that with the two other requirements).
How tough is it to achieve?
In practice, how does it work? For the big picture, nowadays, when you start a secure communication (over TLS for example), you will send the symmetric key encrypted using a key exchange algorithm, that has been setup between you and the receiver (this is what is called hybrid cryptography). Then the receiver will be able to decrypt the symmetric key and you will be able to send messages securely by encrypting them with the symmetric key. It has two main advantages:
[list]
[]you don’t have to setup the key at each message;
[]symmetric encryption is really fast, unlike asymmetric encryption
[/list]
The problem here with the One-Time Pad is that you need a new key for each message, which means that you lose your first advantage, because you will need to send before each message a new key. But after all, I’m sure that you’ll be OK to give up a bit of bandwidth against perfect secrecy. But let’s see if you’re still OK as we advance towards the other requirements ;) .
Possible cryptanalysis if not respected
You might wonder why the key should be used only once. In fact, this is because the One-Time Pad security is based not on the algorithm, but on its key. To give a counter example, the most famous modern block cipher, AES, has a security based on its algorithm (of course the key still needs to be secret). It means that if I give you a plaintext and the corresponding ciphertext, you will not be able to retrieve the key, unless you break the cipher itself. In more technical words, AES is resistant to KPA and CPA (Known-Plaintext Attack and Chosen Plaintext Attack). Please note that I do not consider KPA and CPA as the same attack in contrary to what some articles or books tends to make believe. But in this specific section, the fact that the plaintext was chosen by the attacker doesn’t change the parameters on the attack as in the case of AES, it is resistant to both and in the case of the One-Time Pad, only the knowledge of the plaintext is important.
We will make an easy scenario of CPA.
The scenario uses a CPA, it means that the attacker will be able to choose which plaintext will be encrypted. Then you will also have access to the ciphertext. The most common way to do a CPA is an oracle access. You can see the oracle access as a black box interface that takes as input a plaintext and that generates as output the ciphertext. It is a notion that is widely used when speaking of CPA. So, the attacker will have in his possession the plaintext and the ciphertext.
Just as a reminder, the One-Time Pad is done by XORing the plaintext and the key to generate the ciphertext: P ⊕ K = C.
A bit of math here:
- P ⊕ K = C
- i.e. P ⊕ K ⊕ C = 0
- i.e. P ⊕ C = K
By looking at the last equation, we clearly see that if we have the plaintext and the ciphertext, we can retrieve the key.
All that to say that if you use a key multiple times, if someone steals one of the plaintext and the corresponding ciphertext (KPA) (we always assume that the ciphertext is public); or if he can generate a ciphertext from one of his plaintext (CPA), then he will be able to retrieve the key. Once he has the key, he will be able to decrypt all the previous messages that have been encrypted with it and all the future messages encrypted with it, hence the necessity of using the key only once.
Generation of the key
Definition
The key of the One-Time Pad must be generated randomly.
First, we need to understand clearly the difference between random data and pseudo-random data.
We cannot analyze a single number as random or pseudo-random or not random at all. If I give you 75, you cannot tell from where it comes. What we can analyze is a stream of numbers, and because we work on computers, it is a stream of bits. The common point that will have random data and pseudo-random data is the fact that they are undistinguishable. It means that giving a random stream of bits and a pseudo-random stream of bits, no one will be able to tell which is which. A Cryptographically Secure Pseudo Random Number Generator (CSPRNG) will give a stream where each bit has a 0.5 probability to be either 0 or 1.
So what is the difference between random data and pseudo-random data?
A random data is not based on any algorithm; it might be based on radioactive decay for example. The concept of a random data is that it cannot be predicted.
In contrary, a pseudo-random stream of bits is generated by a PRNG (or a CSPRNG, for cryptographic usage, here we will talk about CSPRNG) that will have two important properties: its seed (it can be seen as an IV in some ciphers/modes of operation or as a salt for hashing), and its internal state.
The algorithm (the CSPRNG) will first takes as input a value (the seed). Depending on this value it will deterministically generates data with a very high period (if the period is finished before the seed is renewed, the same stream of bits will be issued by the CSPRNG, but in practice, good CSPRNGs have a so high period that it never happens).
The internal state of a CSPRNG is basically “where it is” in its pseudo-random data generation. If an attacker knows both the seed and the internal state of a CSPRNG, he can generate the pseudo-random stream of bits that will be next issued by the CSPRNG.
The first requirement of the Shannon’s Theorem is respected here, because as we generate a truly random key, there is an equal probability that each key from the key space will be generated.
How tough is it to achieve?
We have seen that we do not want to use pseudo random keys, because it implies the usage of a CSPRNG, and we have seen the vulnerabilities associated with that. Hence, we want to use truly random data. The problem of truly random data is that it is slow to generate or expensive to generate. States can afford having several modules that will analyze the radioactive decay of radioactive materials with a low half-life period, but I am not sure that as an individual you will be able to have such modules. So once again, if you have the money, it’s fine, you will be able to generate a lot of random data, sufficiently to produce One-Time Pad compliant keys.
Possible cryptanalysis if not respected
Here the possible cryptanalysis is obvious based on the explanation between random data and pseudo-random data. If you use a CSPRNG and that the attacker discovers the seed and the internal state of it, you have a pseudo-random key that is predictable by the attacker. Telling that, it is not an easy-to-perform attack (at all), because the attacker will need to gather the seed used, which usually comes from a random source, and the internal state, which is not easy either. However, you need to remind that your goal is to achieve a perfect secrecy. It is not perfect secrecy anymore if you say, “it’s perfectly secret if my CSPRNG is not broken”. Moreover, if you need perfect secrecy, it means that the data that you protect are critical assets, and it means that an attacker will be able to spend a lot of money to corrupt the confidentiality of this asset. I will not even go any further and say, “if you use a password/passphrase as a key, it is not secure, etc.”, because I assume that if someone wants to achieve perfect secrecy, he will not rely on a password.
Length of the key
Definition
The length of the key is also really important when talking about the One-Time Pad. The key must be at least as long as the plaintext (note that the key being longer than the plaintext is useless for cryptographic means). This requirement might seem quite obvious nowadays, as we know that the keystream of stream ciphers is as long as the plaintext. We must note a thing here, it is that a key and a keystream are very different. A keystream can be seen as the result of a key-scheduling algorithm (KSA) of the key. It means that a keystream cannot be random (this is our previous requirement); at most it can be pseudo-random if the KSA is cryptographically secure. Take a look at how is constructed RC4 if you want to go into much more details about that.
We will demonstrate on this point that the One-Time Pad respect the second requirement of the Shannon’s Theorem.
“For a given plaintext p and a given ciphertext c, there is only one key k that will map p to c.”
Here, our key is as long as the message. It means that we have as much keys as plaintext. As the XOR operation is a one to one operation, given a specific plaintext p and a specific ciphertext c, there is only one key that map p and c together as P ⊕ C = K.
How tough is it to achieve?
As I said before, perfect secrecy has a cost. Imagine that you download a movie from a website that uses HTTPS, you will use a public key (let’s say a 2048 bit public key) and a symmetric key (let’s say a 128 bit symmetric key). You will need to transmit that one time, and then you are done. However, imagine with the One-Time Pad, you need to share a key as long as the file you want to download (potentially several GB of data), it means that you double the bandwidth to use for every communication. You also double the storage, as you will need to store the key. If you have a nice implementation, you will not have to store the entire key in the RAM at the same time and you will use a stream from a file, but then you lose a lot of the interest of stream ciphers: the speed.
Possible cryptanalysis if not respected
What will happen if the key is not as long as the plaintext?
Some older ciphers have the same principle as the One-Time Pad (it directly combines the key with the plaintext to give as result the ciphertext); this is the case of the Vigenère cipher. In the Vigenère cipher, if the key is smaller than the plaintext, the key is simply repeated. For example if your plaintext is “Attack at dawn”, and the key is “abcd”, you will repeat the key 3 times as there are twelve characters in the plaintext and four in the key (we do not encrypt spaces in the Vigenère cipher). Your key (maybe here keystream is more appropriate, even if the KSA is really poor) is now “abcdabcdabcd”. This leads to serious problems, such as statistical analysis; because your key is repeated. Another possible scenario is the following: an attacker succeeds a P-KPA (Partial-KPA), which means that he knows a part of the plaintext, he will then be able to retrieve a part of the keystream. The problem when someone has a part of the keystream and that the keystream is just repeated keys is that the attacker can reconstitute the whole keystream, hence decrypting the entire ciphertext. This scenario is highly probable, because most of the plaintext contains standard stuff. That could be headers for example, or simply someone beginning each message by “Hi Bob”.
This is the reason why it is absolutely needed to have a key as long as the plaintext.
Practical application of the concept of the One-Time Pad
A bit of history
Really just a little bit of history. It is not exhaustive at all, but it’s a good example of the usage of the One-Time Pad. During the Cold War, the red phone (a direct phone line between the President of the USA and the President of the USSR) was using a One-Time Pad to encrypt the communications going through this line. The key was not transmitted through a digital canal, but through the diplomatic bag, written on nitrocellulose sheets (to be easily burn once used). The advantage of this technique is that, the key being used only once, it means that if it’s stolen, the attacker will not be able to decrypt any previous communication and the key will never be used (as it has been stolen). Moreover, because the key is random, the attacker cannot predict the previous or the following key based on the key he stole.
What about now?
Even if it has never been practical to transmit a key physically (as in the little story above), it is completely impossible to do that if you want to use the One-Time Pad as an everyday cryptographic mechanism, as we would today use AES in the TLS protocol. Therefore, we need to transmit the key through a digital canal. Do you remember about the hybrid cryptography?
For this part, let’s assume that we have in our possession an asymmetric cipher, which is able to encrypt an infinity of data (we assume that the plaintext has an infinite length, hence the key too). Let’s also assume that we will have the computational power to perform such encryption. Now the problem is that if we encrypt our symmetric key using RSA for example, then we only have a finite level of security (112 effective bits of security for a 2048 bit key). Then an attacker will be able to break the RSA encryption to read the key. The cryptosystem is not perfectly secure anymore. Therefore, we would need an unbreakable way to exchange keys, which do not exist in modern cryptography. So sadly, in modern cryptography, the One-Time Pad is just a perfect theory that’s not possibly applicable in real world.
And what’s next?
Some of you may have heard of quantum key exchange. That might be a way to achieve the goal of the One-Time Pad and answer the problematic of the key exchange. However, I won’t enter much in details as the subject of quantum key exchange would fill a whole article.
References:
Because I’ve not written this article from nothing, here are some books that you can read and that I highly recommend if you want to start in crypto:
[list]
[]The Code Book of Simon SINGH
[]Cryptography Engineering of Bruce SCHNEIER, Niels FERGUSON and Tadayoshi KOHNO
[]Introduction to Modern Cryptography* of Jonathan KATZ and Yehuda LINDELL
[/list]
Those are listed by order of complexity, so if you want to read them, I recommend respecting this order.
I hope that you’ve liked this article, and feel free to PM me if you want to talk about that (or about something else) :)
