# AES with no SubByte - recover the key

I was wondering if it was possible to recover an AES-128 blockcipher key, knowing that there is no substitution box (it can be seen as the identity mapping). I thought it would be feasible.

I implemented this AES version and I tried, first, a DFA. Because MixColumn and ShiftRow are both linear operations we can inject manually a fault on a given byte at the 9th round, before the mix column. Then I used phoenixAES to compute the last round Key, but it is not working (I have modified the Sbox in the phoenixAES programm).

The only other solution I see now is to express each round key as a function of the master key (the key schedule is now linear) and to use the fact that $$AES(P)=AP+K$$ where K depends only on the round keys (we can compute its exact expression) in order to solve a linear system, but it seems really grueling.

Do you know if the Rijndael box is needed to perform a DFA on AES (the error diffusion should be the same with every box ?!)

Do you see an other way to solve this problem ?

## 1 Answer

where K depends only on the round keys (we can compute its exact expression) in order to solve a linear system, but it seems really grueling

Actually, it doesn't look bad at all; that's 128 linear equations in 128 variables (over $$GF(2)$$); Gaussian elimination should be able to give you an answer in $$128^3 \approx. 2,000,000$$ bit operations; hardly infeasible (and certainly easier than any fault attack).

The only tricky bit is that the 128 equations are likely not linearly independent (a random set of 128 $$GF(2)$$ linear equations over 128 variables is linearly independent circa 29% of the time); if they are not linearly independent, then there will be multiple solutions (or none at all); multiple solutions imply multiple keys that are all correct solutions; your Gaussian elimination code will need to deal with that situation.

• Thanks for your answer. The part which scares me is not solving the linear system, it's to express each Round Key as a function of the master key. I used a complete sheet of paper to express the key from round 1 to 5 and they are not the longest ones (even if there is a lot of simplifications due to the identity Sbox).. – JeanJean Jun 7 at 15:41
• @JeanJean: once you have the master key, mapping that to the various subkeys is straight-forward (just take the standard AES implementation, and remove the sbox references in the key expansion logic) – poncho Jun 7 at 17:49
• @JeanJean: Doing it on paper will indeed surely be grueling. For a computer, it should be trivial. – Ilmari Karonen Jun 7 at 18:01
• @poncho I am trying to recover the master key, not to do its expansion – JeanJean Jun 7 at 19:19
• @JeanJean Then solve for the master key directly; Gaussian elimination can do that... – poncho Jun 7 at 20:45