AES with no SubByte - recover the key

Question

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 ?

Answer 1

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.