Linear AES : expression of K in AES(P) = AP+K

I am currently trying to attack a modified AES with an identity S-box. I found this topic which explains that we have the equation $$AES(P) = AP + K$$, with $$A$$ a 128x128 matrix that is not key-dependent and can easily be computed, and $$K$$ a key-dependent constant. However, I fail to understand where this $$K$$ comes from exactly. Also, would knowing its value and its expression be enough to retrieve the master key ?

• It needs calculation. As said, every affine transformation can be represented in the form. So you need to calculate it. The constant $K$ is depend on the key means it contains the key schedule. My advice start for the first round then extend it to the second. The key needs key schedule. – kelalaka Apr 24 at 21:04
• – kelalaka Apr 24 at 21:10
• I would gladly calculate it, but as I said, I don't know what it is. Hence my topic. It is said that the matrix $A$ comes from ShiftRows and MixColumns, so I suppose $K$ is only constructed with AddRoundKey, but then ? It is, maybe, every round key added together ? – Katoptriss Apr 24 at 21:16
• Using SageMath Symbolic calculation and see how does it goes would be my way to do it. – kelalaka Apr 24 at 21:18
• @forest. No, from an old crypto CTF challenge. – Katoptriss Apr 27 at 15:52

This question is taken from an old Capture the Flag competition, but I believe that there is strong didactic value in presenting a full answer. However, I'm still quite new to SE, so if anyone wishes to edit or delete this answer to make it more appropriate, I promise to accept this without complaint or resentment. Regardless of whether they agree with me or not I hope that all members of the community will assume good intent on the part of other members.

I'm going to do everything bitwise (i.e. over $$GF(2)$$ as you have specified that $$A$$ be a $$128\times 128$$ matrix. It is possible to rework this over $$GF(256)$$ in the usual AES basis by treating $$8\times 8$$ matrices as elements of $$GF(256)$$. I'll build things up to make things fit neatly into the formatting, but you should find expansion easy enough. Throughout, $$O$$ denotes an all zeroes matrix (of appropriate size). I've not checked any of these calculation numerically and there may be errors of endianness.

Some 8-by-8 matrices
We write $$I$$ for the 8-by-8 identity matrix over $$GF(2)$$ and $$X=\left(\matrix{0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\1&0&0&0&1&0&0&0\\ 1&0&0&0&0&1&0&0\\0&0&0&0&0&0&1&0\\1&0&0&0&0&0&0&1\\1&0&0&0&0&0&0&0 }\right)$$ note that if we have an 8-long column vector representing an element of $$GF(256)$$ in the polynomial basis $$x^8+x^4+x^3+x+1$$ with the top entry being the coefficient of $$x^7$$ then multiplying by $$X$$ is the same as multiplying by $$x$$ in the field $$GF(256)$$.

Some 32-by-32 matrices
We build larger matrices from our $$8\times8$$ matrices. Let $$C=\left(\matrix{X&X+I&I&I\\I&X&X+I&I\\I&I&X&X+I\\X+I&I&I&X\\}\right)$$ which is a 4\by4 matrix of 8-by-8 sub matrices making a 32-by-32 matrix. Multiplication of a 32-long column vector by $$C$$ is equivalent to the action of AES column mixing on a single column. We also write $$\sigma_0=\left(\matrix{I&0&0&0\\0&0&0&0\\0&0&0&0\\0&0&0&0\\}\right)$$ $$\sigma_1=\left(\matrix{0&0&0&0\\0&I&0&0\\0&0&0&0\\0&0&0&0\\}\right)$$ $$\sigma_2=\left(\matrix{0&0&0&0\\0&0&0&0\\0&0&I&0\\0&0&0&0\\}\right)$$ $$\sigma_3=\left(\matrix{0&0&0&0\\0&0&0&0\\0&0&0&0\\0&0&0&I\\}\right).$$

Some 128-by-128 matrices
We write $$S=\left(\matrix{\sigma_0&\sigma_1&\sigma_2&\sigma_3\\\sigma_3&\sigma_0&\sigma_1&\sigma_2\\\sigma_2&\sigma_3&\sigma_0&\sigma_1\\\sigma_1&\sigma_2&\sigma_3&\sigma_0\\}\right)$$ note that multiplying a 128-long vector by $$S$$ corresponds to the AES shift rows operation. We also write $$M=\left(\matrix{C&0&0&0\\0&C&0&0\\0&0&C&0\\0&0&0&C\\}\right)$$ and note that multiplying a 128-long vector by $$M$$ corresponds to the AES mix columns operation. We also write $$R=MS$$.

For your purely linear AES, a round of encryption consists of multiplying by $$R$$ and adding round key apart from the last round which consists only of multiplying by $$S$$ and adding round key (there is also a pre-add of key before any rounds. Thus for AES-128 which has 10 rounds $$A=SR^9$$ for AES-192 $$A=SR^{11}$$ and for AES-256 $$A=SR^{13}.$$

If we write $$k_0,\ldots k_{10}$$ for the AES-128 rounds keys written as 128-long vectors, we have $$K=k_{10}+Sk_9+SRk_8+SR^2k_7+SR^3k_6+SR^4k_5+\cdots+SR^9k_0$$ likewise for AES-192 $$K=k_{12}+Sk_{11}+SRk_{10}+SR^2k_9+SR^3k_8+SR^4k_7+\cdots+SR^{11}k_0$$ and AES-256 $$K=k_{14}+Sk_{13}+SRk_{12}+SR^2k_{11}+SR^3k_{10}+SR^4k_9+\cdots+SR^{13}k_0.$$

Expressions for round keys in regular AES
Knowledge of $$K$$ is sufficient to recover any plaintext from its corresponding ciphertext and vice-versa. However, it might also be of interest to recover the actual master key. In the case of 192-bit and 256-bit variants, this will not be possible as the are only $$2^{128}$$ possible values of $$K$$ and so each value of $$K$$ almost certainly corresponds to multiple master keys.

In the 128-bit case it is possible that master keys uniquely correspond to $$K$$-values. To investigate this, we delve deeper into the key schedule. The key schedule itself in standard AES makes use of the $$S$$-box. This means that the round keys themselves are non-linear functions of the master key. Although the non-linear function for each round key is a bijection, there is no guarantee that the linear combination of them to make $$K$$ is bijective and in all probability it is not. In any event, the non-linearity makes recovery of the master key from $$K$$ considerably more onerous than we would like.

Linear round keys
On the other hand, if we assume that our linear AES also eschews the $$S$$-box in the key schedule, we can recover the master key. We introduce another 32-by-32 matrix

$$T=\left(\matrix{0&I&0&0\\ 0&0&I&0\\ 0&0&0&I\\ I&0&0&0}\right)$$

whose action on a 32-bit word written as a column vector is to rotate the bytes of the word left. We also introduce the 128-by-128 matrix $$U=\left(\matrix{I&0&0&T\\ I&I&0&T\\ I&I&I&T\\ I&I&I&I+T\\}\right).$$ With this notation if we write $$k$$ for the master key we have $$k_0=k$$ and $$k_{i+1}=Uk_i+r_i$$ where $$r_i$$ is the 128-long vector which is zero apart from the last 16-bits which take the values 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36 for $$i=1,\ldots,10$$. Thus in this case $$K= (U^{10}+SU^9+SRU^8+SR^2U^7+\cdots+SR^9)k+(r_{10}+Sr_9+SRr_8+SR^2r_7+SR^8r_1)$$ writing $$V=U^{10}+SU^9+SRU^8+SR^2U^7+\cdots+SR^9$$ and $$r=r_{10}+Sr_9+SRr_8+SR^2r_7+SR^8r_1$$ we then have $$k=V^{-1}(K+r).$$

• Note: I'm pretty sure this is a HW :). Left it as it is and way later finish? – kelalaka Apr 25 at 21:37
• I think I see now. By expressing the round keys with the master key bits in K, the system of linear equations mentioned in the related topics should appear, and I should be able to retrieve the key by solving it. – Katoptriss Apr 27 at 15:50
• @kelalaka. No, this comes from a crypto challenge where I'm just asked "crack this" without hints or general directions. You should avoid assuming things with an arrogant ":)". – Katoptriss Apr 27 at 15:51
• crypto.meta.stackexchange.com/q/1402/18298 – kelalaka Apr 27 at 16:42
• Keyword is "running". Mine is non-competitive and three years old. I can provide a link if you or anyone wants to confirm it personally. – Katoptriss Apr 27 at 17:09