AES and DES - reusing the same round keys

Question

Both DES and AES use key expansion to generate the round keys (for Feistel network or for the AddRoundKey operation). Each round uses a different key. Why do we need that? Why we cannot use the same key in each round?

Answer 1

Before discussing the Slide attack, first, observe that the DES uses a 48-bit key per round produced by its key-schedule. If the DES uses the same key for every round then the key-space will be $2^{48}$ not $2^{56}$. Therefore it can be trivially broken by simple brute-force of two p3.16xlarge instances on AWS.

The Slide attack

Wagner and Biryokov called your type of key-schedule homogenous. This occurs when the key-schedule produce periodic subkeys and in the simplest case, the period is 1, as in your question.

While the brute-force requires $\mathcal{O}(2^{n})$, the slide attack on block cipher (if works) requires $\mathcal{O}(2^{n/2})$ and for Feistel ciphers requires $\mathcal{O}(2^{n/4})$ since the $F$ function modifies only half of the block.

The attack is independent of round numbers, all it needs the $F$, the round function, is a weak permutation; i.e. given two equations $F(x_1,k) = y_1$ and $F(x_2,k) = y_2$ it is easy to extract the key $k$, as 3 rounds of DES which is a weak permutation.

Idea

Let a block cipher with $r$ rounds, then;

$X_j = F_1(X_{j-1})$ where $ 1 \leq j \leq r$ and $x_j$ represent the internal outputs, $X_0$ is plaintext and $X_r$ is the ciphertext.

In the period 1 case, $F_j = F_{j+1}$ for all $j \geq 1$.

Slid pair

A pair of $(P,C)$ and $(P',C')$ is called a slid pair if $F(P)=P'$ and $F(C) = C'$.

Attack

Obtain $2^{n/2}$ known-plaintext $(P_i,C_i)$ and look for slid pairs. By birthday paradox, it is expected to find one pair with this property.

When the round function is weak, testing a slid pair condition will be easy, and some key bits of the cipher will be recovered.

Note: This slide attack requires $2^{64}$ known plaintexts and has a time complexity of $2^{128}$ encryptions for AES and this is greater than exhaustive key search!

---

Efficient Slide Attacks

Bar-On et. al improved the original sliding attack with their work 1K-AES has that use the same key for every round with data and time complexity $2^{64}$. The result shows that 1K-AES is insecure.

Countermeasures

For slide attacks to work, also the key schedule must exhibit a large degree of symmetry. Therefore one need methods to break the symmetry

1. Don't use periodic key scheduling algorithms
2. A simple yet efficient countermeasure is utilizing round constant, as in AES's rcon values and similarly as in PRINCE, LED, Simon and Speck,...