Implementing AES in C++: 4x4 Array of unint8_t, or 4x1 array of uint32_t?

Question

I'm implementing AES in C++, and, inspired by the way words are handled in SHA, I decided this time to handle the state as a one dimensional array of 4byte unsigned integers as opposed to a two dimensional array of bytes. To get the bytes out of each of word, I use shifts and mod. E.g. to get the first byte in state[0], I would retrieve byteA = (state[0] >> 24); and to get the second, byteB = (state[0] >> 16) % 256;

In the mix columns and substitution steps, I have to extract and replace bytes from the word, but in the shift rows and add key steps, I can operate on an entire row at once, eliminating the need for 4 extra iterations per row.

Unless this would be very specific to my implementation, I'd appreciate some input on which might be faster.

Answer 1

One way to see it is the following: RAM is slow. Modern processors can do several operations in a single clock cycles. However, a RAM access, such as retrieving data from an array based on a computed index, has inherent latencies and concurrencies issues; in the best of cases, you can do one memory access per cycle, and the result is not available for computations until at least one or two cycles later (even if all the data is in L1 cache).

Therefore, generically, it is best to do as little array accesses as possible. Which means grabbing from each array access as much data as possible, such as a full 32-bit word instead of just one byte.

The trouble with generic comments like the one above is that they are, well, generic. Performance issues depend a lot on the involved architectures, the operational constraints, and what you want to achieve; there are several metrics of performance, such as bandwidth, latency, code size, energy consumption... So, really, you have to try. However, most people (including myself) who have tried to implement AES on 32-bit processors (like a PC or an ARM CPU) with at least a few kilobytes of L1 cache, and no hard limit on code size, have found the "32-bit word" structure to be the best -- unless you aim for an implementation which resists to cache timing attacks, in which case you have to do things quite differently, without any array at all.

To investigate the ins and outs of AES software implementation, you could do worse than perusing Brian Gladman's site which is kind of a reference on the subject.

Answer 2

I think what would be faster is using the hardware AES-NI instructions if those are available to you (and as a bonus, you avoid side-channel attacks, and it's much easier to implement, especially if you have intrinsics available to you, that way you don't need to go implement it in assembly).

As for your question, OpenSSL uses four 32-bit integers as the matrix, and is pretty damn fast (you can look at how they do it here). I myself tried a byte-based approach (which I basically copied from a public-domain source, see here), but it doesn't work too well, though it is a bit easier to read in my opinion...

There are a lot of tables because the Galois Field multiplications are precomputed and combined with the row/column operations, which means a single AES encryption boils down to a few exclusive-or operations (to mix the key in) and a couple table lookups per byte per round, which is really fast.