Different ways/algorithms for implementing AES

Question

I have seen a couple software implementations of the Advanced Encryption Standard. They are pretty much straight forward, i.e. they are implemented exactly the same way as the AES is described. This makes an implementation of AES very easy to achieve. Nevertheless I was wondering if there are other ways of implementing it? Other algorithms for achieving a faster or more secure implementation?

For example, with ECC I know that there are different algorithms for implementing the point multiplication (double-and-add, double-and-add-always, Montgomery Algorithm).

So, are there different algorithms for implementing AES?

Answer 1

To my knowledge there are at least 4 ways to implement AES.

I. lookup tables

For simple blocs, lookup tables are fast but they are sensible to timings attacks.

Here is an example of lookup table implementation:

b0 = T0[ a0 >> 24 ] ^ T1[(a1 >> 16) & 0xff] ^ T2[(a2 >>  8) & 0xff] ^ T3[ a3 & 0xff] ^ rk[4];
b1 = T0[ a1 >> 24 ] ^ T1[(a2 >> 16) & 0xff] ^ T2[(a3 >>  8) & 0xff] ^ T3[ a0 & 0xff] ^ rk[5];
b2 = T0[ a2 >> 24 ] ^ T1[(a3 >> 16) & 0xff] ^ T2[(a0 >>  8) & 0xff] ^ T3[ a1 & 0xff] ^ rk[6];
b3 = T0[ a3 >> 24 ] ^ T1[(a0 >> 16) & 0xff] ^ T2[(a1 >>  8) & 0xff] ^ T3[ a2 & 0xff] ^ rk[7];

II. With Inversion in $GF(2)[X]$

One can represent a polynomial of degree 7 in $GF(2)[X]$ by a number in $GF(2^8)$. (2.1.4 Polynomials over a Field, p. 13, The Design of Rinjdael) or in other word a byte.

By going back to the initial definition, one can implement subBytes is such way and have it potentially protected against timing attacks.

III. Bit sliced

Wait! This is slow as hell!

In order to gain speed, we can have a look at a bit sliced version. Bit slicing is basically writing an hardware implementation in software, considering that each bit is a different input and operations as gates applied at the same time.

In 2007 Matsui and Nakajima propose a bit-sliced implementation of AES-CTR, about 30% faster than the table lookup version. It uses 128 bits vector registers and computes 128 blocs of AES at the same time. The only draw back is that you need 2kB of data to encrypt to benefit from the speed up. But that is still useful in the case of HDD encryption ...

Two years later P. Schwabe and E. Käsper implement another version 20% faster and that does not have this 2kB requirement.

IV. But I need more SPEED !

In 2010, Intel provides a hardware AES instruction.

aesenc xmm1, xmm3   % xmm1 - data, xmm3 - key

Which leads to:

# Encrypt the block.
pxor       %xmm5,  %xmm0
aesenc     %xmm6,  %xmm0
aesenc     %xmm7,  %xmm0
aesenc     %xmm8,  %xmm0
aesenc     %xmm9,  %xmm0
aesenc     %xmm10, %xmm0
aesenc     %xmm11, %xmm0
aesenc     %xmm12, %xmm0
aesenc     %xmm13, %xmm0
aesenc     %xmm14, %xmm0
aesenclast %xmm15, %xmm0

source

V. More readings:

Implementing AES 2000-2010: performance and security challenges by Emilia Käsper

How can bit slicing be constant time, when Mix Columns is in the cipher

Answer 2

There are mainly differences if and how lookup tables are used. This is mainly a balancing act between protection against timing attacks, performance and code size:

For instance, Bouncy Castle has three engines:

• a "normal" engine that uses a table of 256 entries
• a fast one with an 8K table and finally
• one without a table, which is less susceptible to timing attacks and has a small code size)

They are all based on Brian Gladman's implementation of the Rijndael - now hosted on GitHub (https://github.com/BrianGladman/AES/blob/master/aes.txt). AES is a subset of that cipher.

---

There are of course also implementations for GPU's, coprocessors, processors (Intel's AES-NI), FPGA's etc. etc. etc. but above are the main configuration options for implementing the cipher in software you'll see.