What is the importance of Rcon in Rjindael's key expansion from a security prespective?

Question

I do not see why the Rcon function is important, it looks like a waste of cycles.

$$\operatorname{Rcon}(i) = 2^{i-1} \bmod p(x)$$ is in $\operatorname{GF}(2^8)$, where $p(x)$ is the irreducible polynomial $x^8+x^4+x^3+x+1$.

Answer 1

According to Section 3.8 of "The Design of Rijndael", authored by the cipher's creators, the purpose is to eliminate symmetries in the key schedule:

The non-linear function is realized by means of the application of $\mathrm S_\mathrm{RD}$ to the four bytes of the column, an additional cyclic rotation of the bytes within the column and the addition of a round constant (for elimination of symmetry). The round constants are independent of $\mathrm N_\mathrm k$, and defined by a recursion rule in $\operatorname{GF}(2^8)$:

(Emphasis mine.)

Section 5.8 elaborates a bit more on this:

For the key schedule in Rijndael the criteria are less ambitious. Basically, the key schedule is there for three purposes.

1. The first one is the introduction of asymmetry. Asymmetry in the key schedule prevents symmetry in the round transformation and between the rounds leading to weaknesses or allows attacks. Examples of such weaknesses are the complementation property of the DES or weak keys such as in the DES [28]. Examples of attacks that exploit symmetry are slide attacks.

(Emphasis mine.)

To summarize: Adding the round constants $\mathrm{Rcon}$ is a very cheap way (it's not that many cycles) to make each step of the key schedule slightly different, avoiding a variety of attacks that have become apparent in the past.

Answer 2

Adding a bit more detail to the first answer, a round constant in a key schedule (or the main cipher) protects against attacks based on the symmetry of rounds.

The AES schedule uses the user input key to produce a set of unguessable and unrelated round keys. The round key generation function is the same for each round however. The round constant changes each round a little to avoid symmetry. Without the round constant, weak or related key attacks become possible.

Even with the round constant, an impractical related key attack is possible.

The general area of interest here is symmetric attacks on a cipher. The Slide Attack and similar are good examples. There are several papers of interest on that link.

As a very simple related key example, if the key schedule is just based on a long user input key then a key like #FFFFFFFF...FFFF will lead to every round being exactly the same. A related key attack is easily created by producing a pair of keys with an difference (likely xor) of #FFFF00000..0000. So if the round key size is 32-bits then all of the rounds will use the same key except the first round. Differential cryptanalysis on a single round is likely simple thus the cipher is quickly broken.

Weak keys are too be avoided as a matter of design. The round constant can help with that as well but are insufficient.