In AES, why do we multiply the columns by a polynomial with a repeating coefficient?

Joseph Van Name

3/2/24, 4:22 PM

In the MixColumns step of AES, one multiplies each of the columns of the $4\times 4$ box of bytes by the polynomial $a(x)=\{03\}x^3+\{01\}x^2+\{01\}x+\{02\}$ (modulo $x^4+1$). But in this polynomial, the coefficient $\{01\}=1$ is repeated twice. Why is it acceptable for the MixColumns step of AES to have a repeated coefficient? Are there any known or conjectured attacks against AES that take advantage of this repeated coefficient? It seems like a repeated coefficient makes it easier to track how a byte propagates through the block through the rounds of encryption.

1 + 0

aes

symmetric

Score:3

Crypto

kodlu

3/2/24, 11:57 PM

The propagation trails of AES have been extensively analysed. As far as I recall, the repeated coefficient does not play a role. Look up Square attack, Boomerang attacks, others; You are welcome to try to discover a weakness based on the repeated coefficient.

The main impact of this MixColumns design is not repeated coefficients but the fact that the coefficients are low weight (chosen to be so for efficiency).

There are some results exploiting these properties. Some relevant papers are below:

A New Structural-Differential Property of 5-Round AES Lorenzo Grassi, Christian Rechberger, and Sondre Rønjom here

MixColumns Coefficient Property and Security of the AES with A Secret S-Box, Abderrahmane Nitaj and Amr Youssef, AFRICACRYPT 2020 here

I must say that the last paper uses the low weight structure of the MixColumns matrix to mount an attack on an "AES" with secret S-box, to help recover the S-box. This is not really an important weakness, IMO.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: In AES, why do we multiply the columns by a polynomial with a repeating coefficient?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.