Symmetric Encryption: From One-Time Pad to AES and Block Ciphers

Symmetric Ciphers: The Fight for Confidentiality

Let's start with the simpler of the two families. As previously discussed, a symmetric cipher is a cipher in which the required encryption and decryption keys are the same.

The first constraint we will analyze is also the most popular and discussed when talking about cryptography: confidentiality.
To be able to correctly judge the level of confidentiality of our cipher, the first thing to do is to put ourselves inside a framework where we assume to be under some kind of attack. In particular, we'll consider the most basic model of an attack, called ciphertext-only attack. In a ciphertext-only attack, the attacker can simply intercept and read the ciphertext transmitted over the channel.

The Perfect Cipher

Let $ctx_{sent}$ be the ciphertext transmitted over the channel, and $ptx_{sent}$ the corresponding plaintext. A cipher is said to be perfect iff $\forall ptx\in P$ and $\forall ctx\in C$ we have $P(ptx_{sent}= ptx) = P(ptx_{sent} = ptx | ctx_{sent} = ctx)$ .

In other terms, after eavesdropping the communication, the attacker has not any additional information with respect to what he previously knew. But this definition is not constructive. If a perfect cipher actually exists, how we can build one? Let's first look at a characteristic feature of a perfect cipher:

If a cipher with ${|P|=|C|}$ is perfect, then ${|K|\geq|P|}$ .

Let me walk through the intuition behind this theorem.
We are considering the case where the number of plaintexts is the same as the number of ciphertexts: for instance, suppose $P=\lbrace ptx_1, ptx_2, ptx_3\rbrace$ and $C=\lbrace ctx_1, ctx_2, ctx_3\rbrace$ .
If the number of keys is enough, we can theoretically map every plaintext in each possible ciphertext, depending on the key used. If instead the number of keys is not enough, some ciphertexts will not be mapped by every possible plaintext. This means that every time one of these ciphertexts is transmitted, the attacker will get more information than he had before. To understand it better, let's continue with the same example, and suppose that the key space has only two keys: $K=\lbrace k_1, k_2\rbrace$ . We can define a possible encryption function as follow: $E(ptx_1, k_1)=ctx_1$ , $E(ptx_1, k_2)=ctx_2$ , $E(ptx_2, k_1)=ctx_2$ , $E(ptx_2, k_2)=ctx_3$ , $E(ptx_3, k_1)=ctx_2$ , $E(ptx_3, k_2)=ctx_3$ .

Remember that this mapping is known to the attacker: as we discussed earlier, the cryptosystem is fully known to him.
For the sake of simplicity, let's just focus on $ptx_1$ , but the same reasoning can be applied to each plaintext: before the transmission the attacker can state that $P(ptx_{sent}=ptx_1)=P(ptx_{sent}=ptx_2)=P(ptx_{sent}=ptx_3)=\frac{1}{3}$ , as he has no idea which message will be transmitted. Let's now suppose that $ctx_3$ is transmitted other the channel. At this point, since there is no key mapping $ptx_1$ to $ctx_3$ , the attacker knows that $ptx_{sent}\neq{ptx_1}$ . He can consequently tell that $P(ptx_{sent}=ptx_1|ctx_{sent}=ctx_3)=0\neq{P(ptx_{sent}=ptx_1)}$ . Therefore, we can state that the cipher is not perfect. Moreover, we can observe that the hypothesis of the theorem about $|P|=|C|$ is not so far-fetched: intuitively, in the encryption, to be sure that the same key does not map multiple plaintexts in the same ciphertext, we need at least as many ciphertexts as the number of plaintexts, i.e. $|P|\leq|C|$ . In the decryption we can apply the opposite reasoning: to be sure that the same decryption key does not map multiple ciphertexts in the same plaintext we need $|P|\geq|C|$ . So at the end we obtain $|P|=|C|$ . The only real example of secure cipher we have today is the Vernam cipher, also called one-time pad (OTP). In its most popular form, it considers $P=C=\lbrace 0,1\rbrace ^{l}, K=\lbrace 0,1\rbrace ^{\lambda}$ . The encryption function $E$ performs a bitwise XOR between the plaintext and the key to obtain the ciphertext. The decryption function $D$ is exactly the same function as $E$ : by performing a bitwise XOR between the ciphertext and the key, it returns the original plaintext. The key is called "pad". More formally:

1. The pad must have at least the same length $l$ as the plaintext;

2. The pad must be chosen randomly, i.e. it must be uniformly distributed in the set of all possible keys;

3. The pad must never be reused (hence the name one-time pad).

About point 3, the best way to understand the danger of key-reusing is by seeing it in action. Suppose we want to use the OTP cipher on images, and we encrypt the dog image with a certain key:

Let's now encrypt another image (the cat image) with the same key:

The two results, taken individually, appear pretty random. But when we XOR them together, we get the XOR of the two original plaintexts, and this is what it looks like:

It's therefore evident that the attacker can get information about every plaintext that has been encrypted with the same key.
To test it yourself: https://t.ly/7YJX.

If these three assumptions are met, there is no way an attacker can get information about the plaintext by observing the ciphertext. The only information he could infer is the length of the plaintext (since it is the same of the length of the ciphertext), but this is already a public information of the cryptosystem. We can therefore state:

OTP is not vulnerable to brute force attacks.

In fact, by brute forcing all the possible keys, an attacker would get all the possible plaintexts, but the plaintext space is an information he already had before. This cipher is still used in government scope, but, unfortunately, for our everyday purposes is impractical. The reasons why actually lie in the assumptions stated before:

1. The first problem is to communicate the key to the receiver in a secure way, and in the case of OTP this means to communicate a message at least as long as the plaintext. The advantage in communicating the key, instead of directly communicate the plaintext, is that in this way we can send a unique long bitstream that can be used to extract multiple keys, until the sum of the length of the messages to sent reaches the length of the bitstream. But this process makes the data to communicate even bigger. Nowadays, where OTP is used, the key is communicated in person, even if this is still a method sensitive to corruption or theft. But this is obviously not an option for our daily purposes;

2. Generating a key that is completely random is not an easy task at all. True-random generators exist, but they are harder to implement and slower than pseudorandom generators;

3. We need as many keys as the possible messages that can be sent from here on, theoretically forever. In practical applications, some key reuse problems have arisen.

Since building a OTP cipher is not practical, we have to leave the ambition of a perfectly secure cipher. The idea is to go towards something more feasible to implement, that, even if not perfect in theory, is unbreakable in practice. And honestly, that's good enough.

Computationally-Secure Cipher: Good Enough Is Good Enough

We have seen that, in a perfect cipher, the attacker cannot know the plaintext associated to a ciphertext without knowing the key. But what if the plaintext can be actually obtained, yet the process of doing this is extremely computationally difficult?

A secure cipher is a cipher that is computational hard to break.

The statement refers to NP problems and it is telling that, in order for a cipher to be secure, decrypting the message without knowing the key should be reduced to solving a NP problem.
Note that this concept is based on the non-proved assumption that $P\neq NP$ . If one day it will be proved that $P = NP$ , every concept described from now on will immediately collapse, and modern cryptography will have to be entirely thrown away. Let that sink in for a moment.
But how we can use this definition to our advantage?
We have seen that the problems with the implementation of a perfect cipher derive from the generation and distribution of long keys. We can therefore think to manage a communication as follows:
Basic Idea: Alice and Bob exchange a key that is shorter than the plaintext. At this point, both Alice and Bob use the same deterministic function to extend the length of key, in order to reach the length of the plaintext. With the same key, Alice and Bob can now communicate using a OTP protocol.
The function used to stretch the key goes under a particular name in the literature:

A Pseudorandom Number Generator (PRNG) is a deterministic function $PRNG:\lbrace 0,1\rbrace ^{\lambda}\rightarrow \lbrace 0,1\rbrace ^{\lambda+n}$ , where $n$ is called PRNG stretch.

The problem now is that, since the exchanged key is shorter than the plaintext, the cipher isn't perfect anymore. However, if the PRNG is hard to break, using Proposition 2 we can say that the cipher is by definition secure. In particular, still denoting with $\lambda$ the length of the original exchanged key, and assuming that the attacker can only do computations with polynomial complexity with respect to $\lambda$ :

A Cryptographically Safe Pseudorandom Number Generator (CSPRNG) is a PRNG whose output cannot be distinguished from an uniform random sampling of $\lbrace 0,1\rbrace ^{\lambda +n}$ in $O(poly(\lambda))$ .

Although possible, building and testing a CSPRNG from scratch is neither efficient nor practical. So the real question becomes: how do we practically implement it? Actually, a CSPRNG is built by means of a particular building block, called block cipher. Let's first define and analyze a block cipher, then we'll move to describing how it is used to build a CSPRNG.

A block cipher is an encryption algorithm that takes as input a key $k$ and a string $ptx$ of a fixed length $b$ (called block), and returns an output of the same length. Given $k$ , the encryption function $E(ptx,k)$ corresponds to one of the possible permutations over the set of the $2^b$ possible input blocks.

When dealing with cryptography through a theoretical lens, a block cipher usually goes under the name of Pseudorandom Permutation (PRP), but both terms mean exactly the same thing.

A block cipher that accepts keys of length $\lambda$ is said to be broken if, without knowing the key, the plaintext can be derived from the ciphertext with less than $2^\lambda$ operations.

This means that in an unbroken block cipher the only way to derive the plaintext is to brute force the key, which costs $T(\lambda)=O(2^\lambda)$ .
There are some examples of widespread block ciphers. In the 1970s the standard was the Data Encryption Algorithm (DEA, aka DES), but the keys were only long 56 bits, and nowadays it can be broken in a reasonable amount of time. A variant is Triple DES, that we can superficially see as the same algorithm but with a three-times recursive encryption. Triple DES can still be found in some legacy systems, but it's officially deprecated. The standard algorithm is now Advanced Encryption Standard (AES). In AES, the block has a length of 128 bits, and the key can be 128, 192 or 256 bits long.
Keep in mind that the time required to brute-force a cipher that uses a 256-bits key is not even astronomically quantifiable, and also a 128-bits length can be considered more than enough. Obviously, it's rare that the message we want to encrypt is exactly of the same length of the block. In particular, the case where $len(plaintext) < len(block)$ doesn't cause any problem, since it's sufficient to extend the plaintext with a sequence of fixed bits ("padding"), until we reach the length of the block.
But what most of the time happens is that $len(plaintext)>len(block)$ , and so the block cipher is always used in conjunction with some mechanism to overcome this problem, that comes under different names:

Electronic CodeBook (ECB)

It's the most intuitive method, and it's based on the principle of split-and-encrypt: we split the plaintext in multiple segments and we encrypt each segment with the same key.

It's fast, easy to implement and even suitable for parallelization. The decryption is straight forward as well. The problem arises when in the original message there are repetitions, and two or more blocks come out to be the same: in this case, even the corresponding outputs will coincide. Therefore, even if the attacker does not know the corresponding plaintext, he knows that such parts are repeated, and that's a huge and really dangerous information. This is usually shown with the "ECB penguin" example: the one on the left is the original image, while on the right its encrypted version computed in ECB mode. Due to lot of repeated sections in the original image, the result it's pretty bad in terms of confidentiality:

Counter (CTR) Mode

To overcome the drawback of the Electronic CodeBook, this time we use a counter, made of numbers of fixed length, sequentially increased. We encrypt each value of the counter and then we XOR it with each segment of the plaintext. This process will return an output that it's always different.The starting number of the counter is indifferent, and we can also decide to use an increment different than 1, but 1 is secure enough and results in a more efficient computation.

We can also repeat the experiment of the encryption of the penguin image, using now the CTR mode. The difference in the result is pretty evident:

The CTR mode is actually the definitive implementation of our original idea about the construction of a computationally-secure cipher. In fact, in its schema we can actually spot a PRNG (highlighted in the figure below), that stretches the key received as input. If the block ciphers are not broken, the PRNG is also a CSPRNG. The concatenation of the outputs of each block cipher is the output string of the CSPRNG, which is then XORed with the plaintext in order to obtain the ciphertext, as in the OTP cipher.

How Block Ciphers Are Actually Built

I won't cover the algorithms behind the commonly used block ciphers here, but it is important to discuss the process that leads to their creation.
As we have seen, to prove that a PRNG is a CSPRNG we should prove that the block cipher employed is not broken, i.e. that deriving the plaintext or the key has at least a cost $T(\lambda)=O(2^\lambda)$ . However, unfortunately, we are not (yet) able to do this. In fact, proving the exponential lower bound complexity of an algorithm would imply proving that $P\neq{NP}$ . The only thing we can do is to prove that a PRNG is not a CSPRNG, in case we are able to derive the plaintext with less than $2^\lambda$ operations.
For this reason, the commonly used block ciphers are the result of public contests, where cryptographers propose their algorithms and other cryptographers try to break them.
At the beginning, introducing cryptography, we said that a public cryptosystem must not compromise security. We see now that a public cryptosystem actually improves security, since it means more revision, more testing and so more guarantees of robustness. This is something I find really elegant about the field.

What If the Attacker Already Knows Part of the Message?

So far we have analyzed confidentiality under the hypothesis of a ciphertext-only attack. But a ciphertext-only attack is not the only kind of attack that can compromise the constraint of confidentiality. Another possible threat is the so-called known-plaintext attack. In a known-plaintext attack, the attacker knows at least a sample of couples $(ptx,ctx)$ , where $ctx$ is the encryption of $ptx$ . A famous example of this kind of attacker was Alan Turing when, in the early 40s, he discovered repetitive messages in the Enigma code corresponding to the greeting to Adolf Hitler.
A limit case of a known-plaintext attack is the chosen-plaintext attack: in this case the attacker actually chooses the plaintext, and can consequently see the corresponding ciphertext. It's a rarer condition.
We can anyway just focus on general known-plaintext attacks, as chosen-plaintext attacks are just a proper subset.

To analyze the situation, we consider the extreme case, where $P=\lbrace ptx_1,ptx_2\rbrace$ . At this point, if the encryption function is deterministic (as the ones seen so far), the cipher is not secure. In fact, even if the attacker knows only a pair $(ptx_1,ctx_1)$ , he will be able to understand every message exchanged: if he reads $ctx_1$ , he knows that the original message is $ptx_1$ , vice versa $ptx_2$ .
This means that, in order for the cipher to be secure, the encryption function must be non-deterministic. Actually, there exists different paths we can follow to reach this goal:
A first, simple way is to manipulate the key every time it is used. Another common method is to choose each time a different number, called nonce, as starting point of the counter. But the most popular way to do it is probably the technique of rekeying, employed through what goes under the name of symmetric ratcheting. This method consists in producing a different key for every message through the use of a PRNG, that takes an input string of length $\lambda$ and stretches it into an output of length $2\lambda$ : the first half of the output is used as a key, while the second half is used as input to the same function to produce another key, and so on. The initial input used to generate all the keys from there on is called seed.

The terms "ratcheting" derives from the fact that, as a ratchet can only turn on one side but cannot turn back, this mechanism ensures that, even finding a key, there's no way to know the previous ones.

What's Next?

We've locked down confidentiality, but what happens when the attacker can tamper with the ciphertext? Next up: integrity and hash functions.