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$
1
  • 3
    $\begingroup$ Search "slide attack".(I lack expertise, and currently time, for a detailed answer). $\endgroup$
    – fgrieu
    Nov 1, 2018 at 12:23

1 Answer 1

6
$\begingroup$

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,...
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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