AES gets swizzled - Frank DENIS random thoughts.

Skip to main content

There’s an old problem with AES when implemented in software: it’s either slow or insecure.

AES has a state of sixteen bytes, and a round has four steps:

SubBytes replaces every byte using the AES S-Box.

ShiftRows moves bytes to different columns.

MixColumns combines the four bytes in each column.

AddRoundKey XORs another sixteen-byte value.

And SubBytes is the annoying part, because it applies a random-looking permutation to every byte:

SBox(0x00) = 0x63<br>SBox(0x53) = 0xed<br>...

An obvious way to implement that is by using lookup tables.

But here’s the problem: the lookup indices are secret data, and accessing a cache line that was just accessed and is still in the cache is slightly faster than accessing other addresses.

Taking advantage of this, an adversary on the same machine can learn information about the secret indices. For example, DJB recovered AES keys from remote timings, and Osvik, Shamir, and Tromer demonstrated cross-process attacks against OpenSSL and disk encryption.

That was mostly solved on modern mobile, desktop, and server CPUs by adding AES instructions.

But old is new again. With new platforms such as WebAssembly, even when running on such CPUs, applications can’t use AES instructions, so they have to reimplement AES themselves. Sigh.

A common way to avoid using lookup tables is bitslicing: using a circuit of logical operations applied to a different representation of the AES state, where all the bits expected to follow the same circuit are packed together in a register.

It works very well in hardware, but in software, performance is generally still not great, especially compared to what CPU AES instructions can do.

But there’s a third option that’s surprisingly not well known and was originally described by Mike Hamburg in Accelerating AES with Vector Permute Instructions.

A lookup table inside a register

Modern CPUs, even when accessed via WebAssembly, include something nice: SIMD registers that contain 16 bytes or more.

A lot of instructions can be used with such registers, but a very common one, which (oh, joy!) is even accessible in WebAssembly, treats one 16-byte vector as a table and another as sixteen selectors:

table = [t0, t1, t2, ... t15]<br>selectors = [ 3, 9, 0, ... 7]<br>result = [t3, t9, t0, ... t7]

A single instruction effectively performs sixteen lookups in parallel. The table is kept in a register, so there are no memory lookups, and (barring microarchitectural vulnerabilities) no side channels.

This is something that all CPUs with SIMD instructions support. On x86, it’s called PSHUFB, on ARM, TBL, and WebAssembly has a corresponding instruction called i8x16.swizzle, which any sane compiler can map directly to PSHUFB or TBL.

When selectors are between 0 and 15, the behavior is as expected, and the same across all targets.

Values outside that range are target-specific, which is important for WebAssembly (more about that later).

Turning 256 values into 16 by 16

The AES S-Box isn’t actually random. It’s defined as:

S(b) = A(inverse(b)) XOR 0x63

The byte is inverted in the AES finite field. Then a fixed linear bit transformation A and the constant 0x63 are applied. And the inverse of zero is defined as zero.

AES uses a finite field with 256 elements, commonly written GF(2^8). And the same field can be represented as a quadratic extension of a 16-element field:

GF(2^8) is isomorphic to GF(2^4)[t] / (t^2 + t + zeta)

With these binary encodings, field addition in both GF(2^8) and GF(2^4) is bitwise XOR.

Here zeta is chosen so that the quadratic polynomial is irreducible.

And here’s something interesting:

256 = 16 * 16

This is just a reversible change of coordinates.

And in the new representation, one byte becomes a pair of encoded four-bit field components, while addition and multiplication keep working as expected.

A linear input transformation produces those components:

lo = input & 0x0f<br>hi = input >> 4

encoded = lookup16(input_map_lo, lo) XOR lookup16(input_map_hi, hi)

See? The low and high nibble contributions can be looked up separately because the transform is linear.

With two permutations, we can transform all sixteen AES state bytes.

Inversion with small register tables

Hamburg’s nested-inversion construction reduces the nonlinear part of the field inverse to five small lookups:

k = low_nibble(encoded)<br>i = high_nibble(encoded)<br>j = k XOR i

ak = lookup16(inverse_scaled, k)<br>iak = lookup16(inverse, i) XOR ak<br>jak = lookup16(inverse, j) XOR ak<br>io = lookup16(inverse, iak) XOR j<br>jo = lookup16(inverse, jak) XOR i

The stages use scaled and skewed representations, so treating every value as an ordinary nibble in one fixed GF(2^4) basis gives incorrect results.

So, two output tables apply the remaining factors, return to the normal AES byte basis, and apply the linear part of the S-Box affine map:

a = lookup16(output_u, io) XOR lookup16(output_t, jo)

a XOR 0x63 =...