# Implementing AES MixColumns with fewest XOR gates

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:

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.

• 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. – poncho Jun 22 '15 at 15:20
• 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? – poncho Jun 22 '15 at 15:29
• 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. – fgrieu Jun 22 '15 at 18:42
• 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. – fgrieu Jun 22 '15 at 19:00
• 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. – RFuentess Jun 25 '15 at 8:46