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 ?
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&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0\\0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0&amp;0\\0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0&amp;0\\1&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0&amp;0\\ 1&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0&amp;0\\0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1&amp;0\\1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;1\\1&amp;0&amp;0&amp;0&amp;0&amp;0&amp;0&amp;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&amp;X+I&amp;I&amp;I\\I&amp;X&amp;X+I&amp;I\\I&amp;I&amp;X&amp;X+I\\X+I&amp;I&amp;I&amp;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&amp;0&amp;0&amp;0\\0&amp;0&amp;0&amp;0\\0&amp;0&amp;0&amp;0\\0&amp;0&amp;0&amp;0\\}\right)$$
$$\sigma_1=\left(\matrix{0&amp;0&amp;0&amp;0\\0&amp;I&amp;0&amp;0\\0&amp;0&amp;0&amp;0\\0&amp;0&amp;0&amp;0\\}\right)$$
$$\sigma_2=\left(\matrix{0&amp;0&amp;0&amp;0\\0&amp;0&amp;0&amp;0\\0&amp;0&amp;I&amp;0\\0&amp;0&amp;0&amp;0\\}\right)$$
$$\sigma_3=\left(\matrix{0&amp;0&amp;0&amp;0\\0&amp;0&amp;0&amp;0\\0&amp;0&amp;0&amp;0\\0&amp;0&amp;0&amp;I\\}\right).$$
Some 128-by-128 matrices
We write
$$S=\left(\matrix{\sigma_0&amp;\sigma_1&amp;\sigma_2&amp;\sigma_3\\\sigma_3&amp;\sigma_0&amp;\sigma_1&amp;\sigma_2\\\sigma_2&amp;\sigma_3&amp;\sigma_0&amp;\sigma_1\\\sigma_1&amp;\sigma_2&amp;\sigma_3&amp;\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&amp;0&amp;0&amp;0\\0&amp;C&amp;0&amp;0\\0&amp;0&amp;C&amp;0\\0&amp;0&amp;0&amp;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&amp;I&amp;0&amp;0\\ 0&amp;0&amp;I&amp;0\\ 0&amp;0&amp;0&amp;I\\ I&amp;0&amp;0&amp;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&amp;0&amp;0&amp;T\\ I&amp;I&amp;0&amp;T\\ I&amp;I&amp;I&amp;T\\ I&amp;I&amp;I&amp;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).$$