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:

1. SubBytes replaces every byte using the AES S-Box.
2. ShiftRows moves bytes to different columns.
3. MixColumns combines the four bytes in each column.
4. 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
SBox(0x53) = 0xed
...

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]
selectors = [ 3,  9,  0, ...   7]
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
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)
i = high_nibble(encoded)
j = k XOR i

ak  = lookup16(inverse_scaled, k)
iak = lookup16(inverse, i) XOR ak
jak = lookup16(inverse, j) XOR ak
io  = lookup16(inverse, iak) XOR j
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 = AES_SBOX[input]

With the target-specific infinity handling described below, we get the correct S-Box value for every possible input byte. And we only need 16-element lookup tables. Each fits in a SIMD register. You see where this is going.

Folding the rest of the round

MixColumns is evaluated on the constant-free S-Box value a = A(inverse(input)).

It needs both a and a multiplied by 0x02 in the AES field (3a is also needed, but that’s just a + 2a).

Since that operation is linear, a second pair of output tables can produce the doubled value directly:

a2 = lookup16(output2_u, io) XOR lookup16(output2_t, jo)

Four fixed permutations gather the bytes after ShiftRows and arrange the MixColumns contributions:

m0 = permute(a2,       mix0)
m1 = permute(a XOR a2, mix1)
m2 = permute(a,        mix2)
m3 = permute(a,        mix3)

output = m0 XOR m1 XOR m2 XOR m3

How about the affine constant 0x63 we talked about earlier? Turns out that we can omit it.

A vector containing 0x63 in every byte is unchanged by ShiftRows and survives MixColumns because every output row’s coefficients XOR to one:

0x02 XOR 0x03 XOR 0x01 XOR 0x01 = 0x01

Just one final vector XOR restores 0x63.

We can finally AddRoundKey, which is a simple XOR.

To do all this, we only need 15 byte permutations:

Input transformation:          2
Nested inversion:              5
S-Box output and its double:   4
ShiftRows and MixColumns:      4
                              --
Total:                        15

Swizzling infinity

The inversion contains denominators that can be zero. So we need some kind of out-of-range selector to represent infinity.

The inverse tables map a zero denominator to 0x80. XORing that with a nibble can produce anything from 0x80 through 0x8f, but these values all represent the same infinity marker: bit 7 is set, while the low nibble doesn’t matter. When one of them selects from the next 16-byte table, the byte permutation returns zero.

And as mentioned previously, different targets treat out-of-range selectors differently.

A selector between 0 and 15 or between 0x80 and 0xff produces the same output everywhere, even in WebAssembly.

And the circuit described above only produces selectors in 0x00 through 0x0f or 0x80 through 0x8f. So, we’re safe!

The default WebAssembly “strict” SIMD mode doesn’t map well to x86 instructions, so the generated code is pretty inefficient.

Fortunately, WebAssembly later introduced a relaxed-simd variant of the instruction that marks selectors in the 0x10 through 0x7f range as “don’t-care” values and lowers directly to a CPU instruction.

It’s a little sad that WebAssembly support is fragmented and relaxed SIMD isn’t supported everywhere yet, most notably in Safari. At least server runtimes such as Wasmer, WasmEdge, Wasmtime, and WAVM have supported it by default for a long time. And Safari will eventually catch up.

Is this technique worth it compared to lookup tables and bitslicing? It is. Compared to lookup tables, it guarantees constant-time execution. And compared to bitslicing, it doesn’t require bit-level representation changes and introduces less register pressure.

Most importantly, it’s a very good match for how some new AES-based ciphers such as AEGIS and HiAE operate. And we can finally have ciphers with half-decent performance on WebAssembly rumtimes without the WASI-Crypto extensions.