3
$\begingroup$

I'm using the mul2, mul3, mul9, mul11, mul13 and mul14 tables for the MixColumn and InvMixColumn steps in AES-128. However, I got these off some Github repository, and now I'm looking for an actual source explaining how these were calculated and so on.

I cannot find anything proper on Google, can anyone help me out?

$\endgroup$
  • 1
    $\begingroup$ It might help if you actually showed us these tables, or at least described what they do. In any case, the definitive source for questions about how AES is supposed to work is FIPS 197, even if it may not directly answer your specific question here. $\endgroup$ – Ilmari Karonen Jun 10 at 9:08
  • $\begingroup$ They can be seen here: crypto.stackexchange.com/questions/62603/… However, they refer to the same github as I have used. $\endgroup$ – Satoutan Jun 10 at 9:12
7
+50
$\begingroup$

It looks like those are just precalculated tables for multiplication by the constants 2, 3, 9, 11, 13 and 14 in the AES finite field. We already have several questions about how multiplication in finite fields in general, and in the AES representation of GF(28) specifically, is done, such as:

and even:

That said, I would not recommend using lookup tables for these multiplications at all, since they can be easily calculated at runtime. Not only do lookup tables introduce the risk of timing attacks and other side channel attacks (since memory lookups don't always run in constant time), but they are also often less efficient than calculating the multiplication directly, both on high-end CPUs (where memory access is relatively slow) and on low-end microcontrollers (where memory itself is often a scarce resource).

The usual way to do multiplication in GF(2n) is using the double-and-add algorithm, also known as "Russian peasant multiplication", which uses only two primitive arithmetic operations:

  1. addition, which in GF(2n) is simply bitwise XOR, and
  2. doubling, i.e. multiplication by 2 (or by $x$, in the polynomial representation), which requires a left shift followed by a polynomial modular reduction, and can be efficiently implemented e.g. like this in C:

    static inline uint8_t dbl(uint8_t a) {
        return (a << 1) ^ (0x11b & -(a >> 7));
    }
    

Both of these operations can be fairly easily implemented without branches or table lookups, which means they can be usually expected to run in constant time (although one must, of course, always watch out for possibly compiler and/or CPU optimizations that could reintroduce data-dependent timing variations). Using these primitive operations, we can write a general AES finite field multiplication routine e.g. like this:

uint8_t gmul(uint8_t a, uint8_t b) {
    uint8_t p = 0;
    while (b > 0) {
        p ^= a & -(b & 1);         /* add a to p if the lowest bit of b is set */
        a = dbl(a);                /* multiply a by 2 in the finite field */
        b >>= 1;                   /* shift the next bit of b to the lowest position */
    }
    return p;
}

Note that the running time of the code above depends on b, and specifically on the position of its highest set bit, but (hopefully, assuming a reasonable compiler and CPU) not on a. If we wanted, we could also make the timing fully independent of b by replacing while (b > 0) with a fixed 8 iteration loop such as for (int i = 0; i < 8; i++), but this isn't really needed if b is a public constant.

However, for multiplication by a constant b, we don't really need this general routine at all; knowing the value of b, we can manually unroll the loop and eliminate any steps we know are not needed, leaving just e.g.:

uint8_t mul2(uint8_t a) {
    return dbl(a);
}
uint8_t mul3(uint8_t a) {  /* 3 = 2 + 1 */
    return dbl(a) ^ a;
}
uint8_t mul9(uint8_t a) {  /* 9 = 8 + 1 */
    return dbl(dbl(dbl(a))) ^ a;
}
uint8_t mul11(uint8_t a) {  /* 11 = 8 + 2 + 1 */
    uint8_t a2 = dbl(a), a4 = dbl(a2), a8 = dbl(a4);
    return a8 ^ a2 ^ a;
}
uint8_t mul13(uint8_t a) {  /* 13 = 8 + 4 + 1 */
    uint8_t a2 = dbl(a), a4 = dbl(a2), a8 = dbl(a4);
    return a8 ^ a4 ^ a;
}
uint8_t mul14(uint8_t a) {  /* 14 = 8 + 4 + 2 */
    uint8_t a2 = dbl(a), a4 = dbl(a2), a8 = dbl(a4);
    return a8 ^ a4 ^ a2;
}

Also note that, for AES (Inv)MixColumns, you're going to need to multiply each input byte by four different constants in a specific pattern and sum (i.e. XOR) the results. It's possible to do this more efficiently by splitting the finite field multiplications into doublings and XORs and applying the distributive law dbl(x) ^ dbl(y) == dbl(x ^ y), e.g. like this:

void mix_columns(uint8_t cols[4]) {
    uint8_t a = cols[0], b = cols[1], c = cols[2], d = cols[3];
    cols[0] = dbl(a ^ b) ^ b ^ c ^ d;  /* 2a + 3b + c + d */
    cols[1] = dbl(b ^ c) ^ c ^ d ^ a;  /* 2b + 3c + d + a */
    cols[2] = dbl(c ^ d) ^ d ^ a ^ b;  /* 2c + 3d + a + b */
    cols[3] = dbl(d ^ a) ^ a ^ b ^ c;  /* 2d + 3a + b + c */
}

void inv_mix_columns(uint8_t cols[4]) {
    uint8_t a = cols[0], b = cols[1], c = cols[2], d = cols[3];
    uint8_t x = dbl(a ^ b ^ c ^ d), y = dbl(x ^ a ^ c), z = dbl(x ^ b ^ d);
    cols[0] = dbl(y ^ a ^ b) ^ b ^ c ^ d;  /* 14a + 11b + 13c + 9d */
    cols[1] = dbl(z ^ b ^ c) ^ c ^ d ^ a;  /* 14b + 11c + 13d + 9a */
    cols[2] = dbl(y ^ c ^ d) ^ d ^ a ^ b;  /* 14c + 11d + 13a + 9b */
    cols[3] = dbl(z ^ d ^ a) ^ a ^ b ^ c;  /* 14d + 11a + 13b + 9c */
}

(Online demo with self-test.)

Further performance improvements may be possible e.g. through the use of bitslicing techniques.

$\endgroup$
  • $\begingroup$ That's a particularly excellent answer. $\endgroup$ – b degnan Jun 11 at 9:21
3
$\begingroup$

The calculations of mul2, mul3, mul9, mul11, mul13 and mul14 tables is based on multiplying each byte from 0 to 255 with 2 (for mul2) and so on for others.

This is galois field multiplication using irreducible polynomial ( $𝑥^8+𝑥^4+𝑥^3+𝑥+1$). mult2 is xtime (macro) in AES source code:

#include <stdio.h>

#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0x1b))

void mul2(){

  for(int i =0;i<256;i++){
      printf("%02x,",xtime(i)&0xFF);
      if(i>0 & (i+1)%16==0) printf("\n");
  }
  printf("\n");
}
int main(){
      mul2();


      return 0;

}

the mul3, mul9, mul11, mul13 and mul14 is based on iterative xtime and $\oplus$. This question will help you for mul3, mul9, mul11, mul13 and mul14 calculations.

$\endgroup$

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.