Meet-in-the-middle attacks on block ciphers

Wildon's Weblog 2019-08-20

A mathematical model for a block cipher is a collection $\mathcal{E}$ of invertible functions $e_k : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ indexed by keys $k \in \mathbb{F}_2^\ell$ . We say that the block cipher $\mathcal{E}$ has block size $n$ and key length $\ell$ . For example, DES has $n=64$ and $\ell = 56$ , while its successor AES has $n=128$ and $\ell = 128$ (or $192$ or $256$ for the super-paranoid).

Let $\mathcal{E}$ and $\mathcal{E}'$ be block ciphers of block size $n$ and key lengths $\ell$ and $\ell'$ , respectively. An easy way to boost the key length to $\ell + \ell'$ , while keeping essentially the same cryptologics, is to compose the encryption functions from the two ciphers. Thus for $(k,k') \in \mathbb{F}_2^\ell \times \mathbb{F}_2^{\ell'}$ we define

$e_{(k,k')}(x) = e'_{k'}\bigl(e_k(x)\bigr).$

Perhaps surprisingly, when $\ell, \ell' \le n$ , this cryptoscheme offers only $\mathrm{max}(\ell,\ell')+1$ bits of security, rather than the expected $\ell + \ell'$ . The purpose of this post is to give a fairly precise costing of the meet-in-the-middle attack behind this.

As a notational convention, $\star$ denotes quantities unknown to the cryptanalyst and $\dagger$ quantities chosen or observed by the cryptanalyst. We cost by the number of encryption/decryption operations, or cryptops, justifying this assumption in the course of the argument.

Let $(k_\star,k'_\star)$ be the (unknown) key. Let $x_\dagger$ be a chosen plaintext and let $z_\dagger = e_{(k',k)}(x_\dagger)$ be its observed encryption. (We write $e_{(k'_\star,k_\star)}(x_\dagger)$ rather than $e'_{k'_\star}\bigl(e_{k_\star}(x_\dagger)\bigr)$ to emphasise that in the chosen plaintext model, we can perform two-stage encryption using the unknown key pair $(k_\star,k'_\star)$ , but not each stage separately.) We denote by $d'_{k'}$ the inverse of the encryption function $e'_{k'}$ . Let

$\begin{aligned} E &= \{ \bigl(k, e_k(x_\dagger)\bigr) : k \in \mathbb{F}_2^\ell \} \\ D & = \{ \bigl(k', d'_{k'}(z_\dagger) \bigr) : k' \in \mathbb{F}_2^\ell \} \end{aligned}$

Thus $|E| = 2^\ell$ , $|D| = 2^{\ell'}$ and $2^\ell + 2^{\ell'}$ cryptops are required to get this far.

Using any reasonable algorithm, sorting $E$ by the second entry in each pair takes at most $2^\ell \ell s$ primitive operations for some smallish $s$ . Similarly $D$ is sorted using $2^{\ell'} \ell' s$ primitive operations. Working through the sorted lists we pair up the $(k,y) \in E$ with the $(k',y) \in D$ , for each $y \in \mathbb{F}_2^n$ . In one possible implementation this makes a list of pointers to the relevant members of $D$ and $E$ for each $y \in \mathbb{F}_2^n$ , so the cost in primitive operations is

$(|E|+|D|)b = (2^\ell + 2^{\ell'}) b$

for some small $b$ . Since each cryptop for $\mathcal{E}$ must produce $n$ bits, and similarly for $\mathcal{E}'$ , and typically $n \ge \ell$ , it seems reasonable to assume that the cost of $2^\ell + 2^{\ell'}$ cryptops is significantly more than the cost of this sorting and pairing up.

We now have the sets

$\begin{aligned} \mathcal{K}_y &= \{ k \in \mathbb{F}_2^\ell : e_{k}(x_\dagger) = y \} \\ \mathcal{K}'_y &= \{ k' \in \mathbb{F}_2^\ell : d'_{k'}(z_\dagger) = y \} \end{aligned}$

for each $y \in \mathbb{F}_2^n$ . Observe that $\mathcal{K}_y \times \mathcal{K}'_y$ is those key pairs (for the composed cryptosystem) that meet-in-the-middle at $y$ . Fix $p$ distinct plaintexts

$X_\dagger^{(1)}, \ldots, X_\dagger^{(p)} \in \mathbb{F}_2^n \backslash \{x_\dagger\}.$

For each $y \in \mathbb{F}_2^n$ we encrypt $X_\dagger^{(1)}, \ldots, X_\dagger^{(p)}$ using the guessed key pair $(k,k') \in \mathcal{K}_y \times \mathcal{K}'_{y}$ , and check if

$e'_{k'}\bigl(e_{k}(X_\dagger^{(i)})\bigr) = (e_{k'_\star} \circ e_{k_\star})(X^{(i)}_\dagger)$

for each $i$ . If all $p$ encryptions agree, we assume that $(k_\star,k'_\star) = (k,k')$ . (But for simplicity, let’s say we carry on checking all the other keys.) The number of pairs to be checked in the final step is

$M = \sum_{y \in \mathbb{F}_2^n} |\mathcal{K}_y| |\mathcal{K}'_y|$

and each pair requires two encryptions, making the cost of the final step $2Mp$ cryptops. The total cost in cryptops is therefore $2^{\ell+\ell'} + 2Mp$ .

We now estimate $2^{\ell+\ell'} + 2Mp$ for the random cipher, and use this as an approximation to DES and to AES.

Random cipher

Suppose that each $e_k : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ and $e'_{k'} : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ is chosen uniformly and independently at random from the $(2^n)!$ permutations of $\mathbb{F}_2^n$ . We know that $e_{k_\star}(x_\dagger) = y_\dagger$ and for each other key $k$ , the probability is $\frac{1}{2^n}$ that $e_k(x_\dagger) = y_\dagger$ . Dually, we know that $d'_{k'_\star}(z_\dagger) = y_\dagger$ , and for each other key $k'$ , the probability is $\frac{1}{2^n}$ that $d'_{k'}(z_\dagger) = y_\dagger$ . Therefore $|\mathcal{K}_{y_\dagger}|$ and $|\mathcal{K'}_{y_\dagger}|$ are independently distributed as the shifted binomial distribution

$1 + \mathrm{Bin}(2^\ell-1, \frac{1}{2^n}).$

Similarly, if $y \not= y_\dagger$ then $|\mathcal{K}|_y$ and $|\mathcal{K}|_y$ are independently distributed as $\mathrm{Bin}(2^\ell-1, \frac{1}{2^n})$ . (It is worth noting that $\mathcal{K}_{y}$ and $\mathcal{K}_{y'}$ are not independent: for example we have $\cup_{y \in \mathbb{F}_2^n} \mathcal{K}_y = \mathbb{F}_2^\ell$ where the union is disjoint, therefore $\sum_{y \in \mathbb{F}_2^n} |\mathcal{K}_y| = 2^\ell$ .) It follows by linearity of expectation that

$\begin{aligned} \mathbb{E}[M] &= \mathbb{E}\bigl[\sum_{y \in \mathbb{F}_2^\ell} |\mathcal{K}_y| |\mathcal{K}'_y|\bigr] \\ &= \bigl( 1 + \frac{2^\ell-1}{2^n} \bigr)\bigl( 1 + \frac{2^{\ell'}-1}{2^n} \bigr) + (2^n-1) \bigl( \frac{2^\ell-1}{2^n} \bigr)\bigl( \frac{2^{\ell'}-1}{2^n} \bigr) \\ &= \frac{2^{\ell+\ell'}}{2^n} + 1 - \frac{1}{2^{n}} \end{aligned}$

This is very well approximated by $\frac{2^{\ell + \ell'}}{2^n} + 1$ . Hence the total cost is estimated as

$2^{\ell} + 2^{\ell'} + 2p \bigl( \frac{2^{\ell + \ell'}}{2^n} + 1\bigr).$

It remains to choose a suitable value for $p$ . By our randomness assumption, $e'_{k'_\star} \circ e_{k_\star}$ and $e'_{k'} \circ e_k$ are each permutations of $\mathbb{F}_2^n$ chosen uniformly at random subject to the constraint $f(x_\dagger) = z_\dagger$ . Thus for each chosen plaintext $X_\dagger \not= x_\dagger$ , the ciphertexts $(e'_{k'_\star} \circ e_{k_\star})(X_\dagger)$ and $(e'_{k'} \circ e_k)(X_\dagger)$ are uniformly distributed on $\mathbb{F}_2^n \backslash \{z_\dagger\}$ . The probability they agree is therefore $1/(2^n-1)$ . More generally, the probability that $e'_{k'}\bigl(e_{k}(X_\dagger^{(i)})\bigr) = (e'_{k'_\star} \circ e_{k_\star})(X^{(i)}_\dagger)$ for all of the $p$ chosen $X_\dagger^{(i)}$ is

$\displaystyle \frac{1}{2^n-1} \times \ldots \times \frac{1}{2^n-p} \approx \frac{1}{2^{np}}.$

We have to check $M$ key pairs, so the expected number of ‘false’ keys is very nearly $\mathbb{E}\bigl[\frac{M}{2^{np}}\bigr]$ ; by the good approximation for $M$ above, this is very nearly

$\displaystyle \frac{2^{\ell+\ell'}}{2^{(1+p)n}} + \frac{1}{2^{np}}.$

Suppose for simplicity that $\ell = \ell'$ . Setting $n = \nu \ell$ , our estimate for the total work is then

$2^{\ell}+2^{\ell'} + 2p\bigl( 2^{(2-\nu)\ell} + 1 \bigr)$

cryptops, where $p$ should be chosen so that $\nu(1+p)$ is large compared to $2$ . In particular, if $\nu$ is very large then, as one would expect, then one can take $p=0$ : no checking cryptops are needed.

DES as a random cipher

For DES, $\ell = 56$ , $n = 64$ , so $\nu = \frac{8}{7}$ , $(2-\nu)\ell = \frac{6}{7} \times 56 = 48$ and we need $\frac{8}{7}(1+p)$ large compared to $2$ . Taking $p = 2$ , the total work is $2^{57} + 2^{50}$ . Clearly for any reasonable choice of $p$ , the cost of the attack is dominated by the first phase, and is about $2^{57}$ cryptops. Even in 2009, using a special purpose device, this took at most $2$ days.

AES as a random cipher

For AES with the shortest key length, $\ell = n = 128$ , so $\nu = 1$ and we need $2p$ large compared to $2$ . Again taking $p=2$ , the total work is $2^{129} + 2^{130}$ , roughly balanced between the first and second phases. For AES with the longest key length, $\ell = 256$ and $n=128$ , so $\nu = \frac{1}{2}$ and we need $(1+p)/2$ large compared to $2$ . Taking $p=5$ , the total work is $2^{257} + 10 \times 2^{378}$ . The second phase dominates. Of course neither attack is practical.

A cipher chosen to have many collisions in the middle

Let $\mathcal{K} = \mathcal{K}' = \mathbb{F}_{2^\ell} \times \mathbb{F}_2^m$ and define $e_{(a,b)} : \mathbb{F}_{2^\ell} \rightarrow \mathbb{F}_{2^\ell}$ by $e_{(a,b)}(x) = ax$ . (This is multiplication in the finite field: we will ignore that the encryption functions $e_{(0,b)}$ are not injective.) Define $e'_{(a',b')} : \mathbb{F}_2^{\ell} \rightarrow \mathbb{F}_{2^\ell}$ by $e'_{(a',b')}(x) = x+a'$ . The set $\mathcal{K}_y \times \mathcal{K}'_{y}$ of keys that meet-in-the-middle at $y \in \mathbb{F}_2^\ell$ is

$\bigl\{\bigl((y/x^\dagger,u), (y+z^\dagger, v) \bigr) : u, v \in \mathbb{F}_2^m \bigr\}.$

Again we ignore the vanishing small chance that $x^\dagger = 0$ . Hence

$|M| = \sum_{y \in \mathbb{F}_2^\ell} |\mathcal{K}_y||\mathcal{K}'_y| = \sum_{y \in \mathbb{F}_2^\ell} 2^{2m} = 2^{\ell+2m}.$

The estimate for the cost is

$2^{2\ell} + 2Mp = 2^{2\ell} + 2^{\ell+2m+1}p.$

Using the heuristic for $p$ from the random cipher, we have $\nu = \ell/n = 1$ , so we need $1+p$ large compared to $2$ . Taking $p=2$ the total cost is $2^{2\ell} + 2^{\ell+2m+2}$ . In this case the chance is $1/2^{2m}$ that the true key is found, but since the second components of each half of the encryption key are irrelevant, this will not worry the attacker. One reason for not using $e_{(a,b)}(x) = x+a$ is that the composed encryption functions for keys $\bigl((a,b),(a',b'))$ are then the same whenever $a+a' = k$ , giving a further collapse. For the composed cipher as defined, since the affine group on $\mathbb{F}_{2^\ell}$ is sharply $2$ -transitive, we could in fact have taken $p=1$ .