7
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ the round constants are generally hardcoded and take up only a handful of bytes, as the key/block size combinations are less for AES than for Rijndael $\endgroup$ – Richie Frame Jan 6 '17 at 0:41
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ if Rcon(i) replaced with i, won't make any difference since Rcon[0-32] are unique. $\endgroup$ – Error Jan 6 '17 at 8:51
3
$\begingroup$

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.

$\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.