5 Block Ciphers

Block ciphers are deterministic symmetric ciphers with fixed length in- and output. A deterministic cipher always produces the same ciphertext given the same message and key, even if you execute it multiple different times. Using block ciphers, encryption and decryption happen with the same key. This makes them symmetric ciphers. What gives block ciphers their name, is that encryption happens in blocks of fixed length. Both message and ciphertexts are of that length.

Symmetric cryptography schemes have the main disadvantage that anyone who can encrypt can also decrypt. These schemes are therefore used in settings where this is not critical, e.g. as part of a bigger protocol or in a local setting only.

Symmetric encryption, schematically

One example for block ciphers is the Advanced Encryption Standard (AES), with a block length of 128 bit.

Block ciphers are then used in a so-called mode of operation. These modes of operation determine how block ciphers are applied to longer messages (In Cipher block chaining for example, messages are XORed with the previous block’s ciphertext). Using block ciphers in such a mode results in another symmetric encryption scheme which allows encrypting longer messages and is more secure (like IND-CPA, IND-CCA, although more on these later).

We will ask the following questions in this lecture:

What security properties should block ciphers have?
What constructions of block ciphers are there?
What quantum attacks are there?

5.1 Security of block ciphers

We want block ciphers to be a so-called strong pseudorandom permutation. This means, intuitively, that the block cipher encryption looks like a random permutation, as long as the key is not known to us. (In this case permutation does not mean a reordering of bits, but a bijective function).

Now, how do we define two things looking the same? A common proof technique in cryptography is specifying a game. If the adversary playing the game is not able to win, our algorithm/idea are safe from attack. In the case of block ciphers we construct the game as follows: The adversary is given a black box that encrypts any plain text given to it. The adversary can encrypt things as often as it would like, but then has to decide whether the function was a random permutation or the encryption scheme. If it can guess no better than $50\%$, the scheme is considered secure. We can also give the adversary the additional power of decrypting any ciphertext it wants (in the diagram shown in red). If it still cannot decide reliably we call this strong PRP.

Definition 5.1 (Pseudorandom Permutation) $(E,D)$ is a $(t,\epsilon)-\color{red}\text{strong}\color{black}$ pseudorandom Permutation (PRP) iff:

for all keys $k$: $E(k, \cdot)$ is a permutation
for all $k$: $D(k, \cdot)$ is the inverse of $E(k, \cdot)$
for all $t$-time quantum adversaries $A$: $\lvert Pr[b = 1: k \xleftarrow{\$} \mathcal{K}, b \xleftarrow{\$} A^{E(k, \cdot),\color{red}D(k, \cdot)\color{black}}()] - Pr[b = 1: \pi \leftarrow Perm(\mathcal{M}\rightarrow \mathcal{M}),b \leftarrow A^{\pi, \color{red}\pi^{-1}\color{black}}()] \leq \epsilon$. Here $\mathcal{K}$ is key space, $\mathcal{M}$=$\mathcal{C}$ are message space and ciphertext space.

In this definition, we give access to the encryption function to the adversary. We denote this by writing $A^E$. This means it can query it as often as it wants. $K$ denotes the key space, and $M = C$ denotes the message/ciphertext space. Note that this is two definitions in one, depending on if you read the red part or not.

5.1.1 Getting a Strong Pseudorandom Permutation

Different PRPs choose different approaches. One you might have heard of is the Advanced Encryption Standard (AES). In AES, the message is fed through lots of very simple functions. These are called rounds, and each round depends on (some parts of) the key. Given the key, each round is easily inverted. The round itself might just shift some bits, or switch them out. In combination, these form a very secure algorithm.

5.1.2 Feistel networks

A different approach is called a Feistel network. Let us say our message space is $\mathcal{M}=\{0,1\}^{2n}$ and we have a function $F_k:\{0,1\}^n \rightarrow \{0,1\}^n$, which is random looking, but depends on the key. This function has more lax requirements than a permutation, because it does not need to come with a decryption, nor does it even need to be injective at all. Still, we will manage to build a permutation out of it. We simply split our message into two halves: $m_1$ and $m_2$. We then take these halves and pass them through functions $F_k$ (they need not all be the same), alternating between $m_1$ and $m_2$, like shown below. This is known as a Feistel network. If you repeat this long enough, this becomes a good block cipher. This is classically well understood, if $F$ is a pseudorandom function, and the Feistel network has $3/4$ rounds, you get a PRP/strong PRP. The same holds in the postquantum setting, but $\underline{\text{not}}$ when we allow superposition queries (see Section N/A).

5.1.3 Even-Mansour

We start off with a permutation $P$, as follows. $P: \{0,1\}^n \rightarrow \{0,1\}^n = \mathcal{M}$. This permutation is publicly known, as is its inverse. We also assume that it behaves like a random permutation (whatever that means formally). Constructing a block cipher from it is the next step. The block cipger has key space $\{0,1\}^{2n}$; each key consists of two halves $k_1,k_2\in\{0,1\}^n$. Encrypting works by first XORing the message with $k_1$, permuting it, and then XORing it with $k_2$ ($k_1, k_2\in\{0,1\}^n$). Similarly, we decrypt by XORing with $k_2$, using the permutation’s inverse, and then XORing with $k_1$. More formally: $E(k=k_1\parallel k_2, m) = P(m\oplus k_1)\oplus k_2$ and $D(k=k_1\parallel k_2, c) = P^{-1}(c\oplus k_2)\oplus k_1$.

Classically, Even-Mansour is a strong PRP for an adversary making less than $2^{n/2}$ queries. There exist attacks that break it in around that many queries. These are key recovery attacks, making it a relatively strong attack.

5.1.4 Attacking EM with quantum computers

This will work similarly to our attack on hash functions. We start of by picking $2^{n/3}$ values $m_i$. We also construct our set $\mathbb{D}=\{\underline{d_i}\}$, and to go along with it, our function $\mathcal{L}_{\mathbb{D}}(z)=[P(z) \oplus P(\bar{z}) \in \mathbb{D}]$. In this scenario our key is $kl$, and $d_i = E_{kl}(m_i) \oplus E_{kl}(\bar{m_i})$. Here $\bar{m_i}$ is the bitwise negation of $m_i$. Note that since we can compute $E_{kl}$ only by invoking the encryption oracle, we cannot evalate functions involving $E_{kl}$ in superposition, and thus cannot run Grover with such functions. (E.g. we cannot use Grover to search for some $m$ with $E_{kl}(m)=0.) However, $P$ is a public permutation, i.e. completely known to the adversary, thus we can apply Grover to functions involving $P$.

For any random $z$, our probability for ${L}_{\mathbb{D}}(z)$ to evaluate to 1 is very low. Both $P(z)$ and $P(\bar{z})$ are essentially random. Thus, we once again have a chance of success of $\frac{\lvert\mathbb{D}\rvert}{2^n} =\frac{2^{\frac{n}{3}}}{2^n}=2^{-\frac{2}{3}n}$. We then find the $z$ with Grover. This takes us $\sqrt{\frac{1}{2^{-\frac{2}{3}n}}}=\sqrt{2^{\frac{2}{3}n}}=2^{\frac{n}{3}}$ evaluations of ${L}_{\mathbb{D}}$. Luckily, we do not have to balance the two parts of the algorithm, because they already are.

We now have a $z$ with $P(z) \oplus P(\bar{z}) \in \mathbb{D}$. We want to find (using a table), an $m_i$, such that $E_{kl}(m_i) \oplus E_{kl}(\bar{m_i}) = d_z$. This necessarily exists, because of $P(z) \oplus P(\bar{z})$ being in $\mathbb{D}$. If we now use the definition of EM, we see that $P(z) \oplus P(\bar{z}) = P(m_i \oplus k)\oplus l \oplus P(\bar{m_i}\oplus k) \oplus l$. We can get rid of the $l$s, and then $z$ could have the following values: Either $z = m_i \oplus k$, or $z = \bar{m_i} \oplus k$. For random P, these are the only cases, up to a small probability. (Proof ommitted.) Turning the equations around, our key is $k = m_i \oplus z$, or $k = \bar{m_i} \oplus z$. Getting $l$ is now also possible: we evaluate (classically) $E_{kl}(0) \oplus P(k) = P(0\oplus k)\oplus l \oplus P(k) = l$. All that is left is to check whether $kl$ is correct, by letting the oracle encrypt something random for us, and then encrypting it ourselves to compare.

In summary, we used $O(2^{n/3})$ queries to recover the key. Some, like the $E_{kl}$-queries were classical, and the $P$-queries we used were quantum.

Ito, Gembu, Akinori Hosoyamada, Ryutaroh Matsumoto, Yu Sasaki, and Tetsu Iwata. 2019. “Quantum Chosen-Ciphertext Attacks Against Feistel Ciphers.” In Topics in Cryptology–CT-RSA 2019: The Cryptographers’ Track at the RSA Conference 2019, San Francisco, CA, USA, March 4–8, 2019, Proceedings, 391–411. Springer.

Kuwakado, Hidenori, and Masakatu Morii. 2010. “Quantum Distinguisher Between the 3-Round Feistel Cipher and the Random Permutation.” In 2010 IEEE International Symposium on Information Theory, 2682–85. IEEE.

Luby, Michael, and Charles Rackoff. 1988. “How to Construct Pseudorandom Permutations from Pseudorandom Functions.” SIAM Journal on Computing 17 (2): 373–86.