I'm playing with Contiki (O.S. for constrained devices such as sensors and micro-controllers) and particularly with the AES encryption in software (the one available in Contiki source code).

I'm trying to complete the code by adding the decryption operation, but I'm confused with the inverse MixColumns operation. They are using the paper Lightweight MixColumns for it (because it can reduce the number of XOR gates in hardware). On the page 257 they state that:

Inverse MixColumns hardware optimization

QUESTION: Would be correct to say that the first line is equivalent to the following code? (inspired by a similar question) :

 //buf1 * 9 =  ((( buf1 x2) x2) x2)+ buf1    
 buf1  =  state[buf4] ^ state[buf4 + 1] ^ state[buf4 + 2] ^ state[buf4 + 3];
 buf2 = galois_mul2(buf1);
 buf2 = galois_mul2(buf2);
 buf1 = galois_mul2(buf2) ^ buf1;

Currently, my decryption function is not working, but not sure if it's because I'm screwing up in another part of the code or at this point.

  • 3
    $\begingroup$ I haven't gone through your question; however if you want to track down where in the algorithm you made mistakes, you may want to look at the detailed test vector in FIPS 197 (section A.1); that details the internal state after every single operations; it's invaluable in getting an AES implementation working. $\endgroup$
    – poncho
    Jun 22, 2015 at 15:20
  • 1
    $\begingroup$ At first glance, your code looks correct. Have you gone through the detailed test vectors, and see that the input into the invmixcol is correct, and that the output is not? $\endgroup$
    – poncho
    Jun 22, 2015 at 15:29
  • $\begingroup$ If I correctly read the formula quoted for InvMixColumns, it has (for each of four j) 23 byte XORs and 13 table lookups of two different tables (or 9 table lookups of three different tables). Some code that I have around has 25 byte XORs and 7 table lookups of a single table, the doubling table used in MixColumns. That seems preferable both in hardware and software for 8-bit gear. I'll try to dig where I got the equations, which seem better than those proposed in that Lightweight MixColumns paper. $\endgroup$
    – fgrieu
    Jun 22, 2015 at 18:42
  • 1
    $\begingroup$ Could not immediately locate how I got my formula, but I dug here nice public code that I know works, with aes_mixColumns_invusing 21 XORs and 9 table lookups of a single table (or 7 table lookups of two tables). That seems to beat the Lightweight MixColumns paper on all counts. I did not use exactly that in my own code because lookups are slower than XOR, extra tables waste space, and it uses a temporary that I manage to avoid. $\endgroup$
    – fgrieu
    Jun 22, 2015 at 19:00
  • $\begingroup$ Hello @fgrieu half of the code (The ciphering) was already made by the Contiki community but strangely the other half was never added (and zero mention to the paper from where the mix-column was inspired). I'll later read the code you published. $\endgroup$
    – RFuentess
    Jun 25, 2015 at 8:46

1 Answer 1


many thanks to everyone. When I was reading originally the FIPS 197 document I made one big mistake: I assumed that the appendix C had only the cipher portion, similar to the appendix B, and missed the uncipher portions.

Answering my own question, yes, translation of the variable temp to the one I proposed initially was correct. However, my error come from another part: For ciphering, you can save directly the results in the state array, but for the decryption you need 3 auxiliary variables more.

I'll clean the code a little more and try to suggest an update to the Contiki repository with my part.

Again, many thanks to everyone by guiding this misled soul


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.