2
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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).. $\endgroup$ – JeanJean Jun 7 at 15:41
  • $\begingroup$ @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) $\endgroup$ – poncho Jun 7 at 17:49
  • $\begingroup$ @JeanJean: Doing it on paper will indeed surely be grueling. For a computer, it should be trivial. $\endgroup$ – Ilmari Karonen Jun 7 at 18:01
  • $\begingroup$ @poncho I am trying to recover the master key, not to do its expansion $\endgroup$ – JeanJean Jun 7 at 19:19
  • $\begingroup$ @JeanJean Then solve for the master key directly; Gaussian elimination can do that... $\endgroup$ – poncho Jun 7 at 20:45

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.