2
$\begingroup$

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 ?

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ – kelalaka Apr 24 at 21:04
  • $\begingroup$ Also see AES with no SubByte - recover the key $\endgroup$ – kelalaka Apr 24 at 21:10
  • $\begingroup$ 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 ? $\endgroup$ – Katoptriss Apr 24 at 21:16
  • 1
    $\begingroup$ Using SageMath Symbolic calculation and see how does it goes would be my way to do it. $\endgroup$ – kelalaka Apr 24 at 21:18
  • 1
    $\begingroup$ @forest. No, from an old crypto CTF challenge. $\endgroup$ – Katoptriss Apr 27 at 15:52
3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Note: I'm pretty sure this is a HW :). Left it as it is and way later finish? $\endgroup$ – kelalaka Apr 25 at 21:37
  • $\begingroup$ 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. $\endgroup$ – Katoptriss Apr 27 at 15:50
  • 1
    $\begingroup$ @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 ":)". $\endgroup$ – Katoptriss Apr 27 at 15:51
  • $\begingroup$ crypto.meta.stackexchange.com/q/1402/18298 $\endgroup$ – kelalaka Apr 27 at 16:42
  • $\begingroup$ 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. $\endgroup$ – Katoptriss Apr 27 at 17:09

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.