8
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Search "slide attack".(I lack expertise, and currently time, for a detailed answer). $\endgroup$ – fgrieu Nov 1 '18 at 12:23
6
$\begingroup$

Before discussion about the Slide attack, first, observe that the DES uses 48-bit key per round produced by it's key-schedule. If the DES uses the same key for every round than 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 to find one pair with this property.

When the round function is weak, testing a slid pair condition will be easy, and some key bit 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

  1. Don't use periodic key scheduling algorithms
  2. Utilize round constant, as in AES, PRINCE, LED, Simon and Speck,...
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.