Exhaustive search attacks

Ideal ciphers

A block cipher is a function $E:\mathcal K \times \mathcal M \rightarrow \mathcal C$. Here we shall let $|\mathcal K| = n$ and $|\mathcal M| = |\mathcal C| = poly(n)$, where $n$ is called the security parameter. A block cipher $E$ is called an ideal cipher if for any $m\in \mathcal M$, $Adv(E(k,m),r)$ is negligible for $r \in_r \{0,1\}^{poly(n)}$ and $k \in_r \mathcal K$. Another characterization of an ideal block cipher $E$ is $\{E(k,m)\} \approx_p \{f_k(m)\}$ for any $m\in \mathcal M$, where ${f_k}$ are a random subset of the family of all invertible functions from $\mathcal M$ to $\mathcal C$. The second characterization is especially helpful, because it allows us to approximate an ideal cipher by a random invertible functions.

Fact. Let $E:\mathcal K\times\mathcal M\rightarrow \mathcal C$ be an ideal cipher. For all $c,m$, the probability that a cipher-text can only be decrypted by the encryption key is $$P\{k'\neq k, E(k',m)=c\} \le \sum_{k'\in\mathcal K,k'\neq k} P\{E(k',m)=c\} \le \frac{|\mathcal K|}{|\mathcal M|}.$$ Assuming that DES is ideal, the probability that one can recover a unique key from $N$ input-output pairs is larger than $1-N2^{56-64N}$. When $n=1$, the probability is roughly 99.5% --- already high enough for an exhaustive search attack to be reasonable.

Attacks on block ciphers

To attack a block cipher $(E,D)$, we are given a few input-output pairs $(m_i, c_i=E(k,m_i))$, $i=1,...,n$ to find the key $k$. The ciphers we are interested here are DES and some of its strengthened versions
DES:   $E(k,m)$ for $k\in \{0,1\}^{56}$, $m\in \{0,1\}^{64}$
2DES: $E^2((k_1,k_2),m) = E(k_2,E(k_1,m))$
3DES: $E^3((k_1,k_2,k_3),m) = E(k_3,D(k_2,E(k_1,m)))$
DX:     $E^x((k_1,k_2,k_3),m) = k_3\oplus E(k_2, k_1\oplus m)$

DES Challenge: Broken by exhaustive search attack since 1997.

2DES Challenge: Given $c,m$, find $k_1,k_2$ such that $E(k_2,E(k_1,m))=c$.

1. Build a sorted table $T$ such that for each $k_1$, $T[k_1]=E(k_1,m)$.
2. For each $k_1$, check whether $D(k_2,c)$ is in the table.

Both steps take $O(56 \cdot 2^{56})=O(2^{62})$ time and $O(2^{56})$ space, which turns out to be the total cost of the attack (called the meet-in-the-middle attack). This complexity is considered tractable with technology of nowadays.

3DES Challenge: Given $c,m$, find $k_1,k_2,k_3$ such that $E(k_3,D(k_2,E(k_1,m)))=c$.

1. Build a sorted table $T$ such that for each $k_1$, $T[k_1]=E(k_1,m)$.
2. For each $k_1,k_2$, check whether $E(k_2,D(k_3,c))$ is in the table.

The first step takes $O(56\cdot 2^{56})$ time and the second step takes $O(56\cdot 2^{56}\cdot 2^{56})=O(2^{118})$ time. Both steps take $O(2^{56})$ space. In practice, we regard a cipher as sufficiently secure if it takes $\omega(2^{90})$ time to compromise. This is why 3DES is widely used today while DES and 2DES are not.