Constant-Time AES: Removing the Secret-Dependent Table Lookup

The standard software AES implementation is a table lookup. The round function’s S-box is a 256-byte array, and the byte substitution is a load from that array indexed by a state byte. The linear layer is folded into four larger tables of 1,024 bytes each, so that a round becomes sixteen 32-bit loads and twelve XORs. It is compact, it is fast, and its execution time depends on the data it processes. That dependence is not incidental. It is the cipher’s most exploited weakness.

How a load leaks

A processor’s data cache is organised in lines, typically 64 bytes, and a 256-byte table occupies four lines. When a state byte indexes the table, the line containing that entry is loaded into cache. If the line was already present, the load is fast; if not, it is slow. An attacker who can observe which lines are resident — through the total time of an encryption, through a probe that evicts and times specific lines, or through a co-resident process measuring shared cache state — learns which quarter of the table each index fell into.

That is two bits per lookup, sixteen lookups per round, ten rounds. It is not the key directly, but it constrains the key heavily. The first round’s lookup index is the XOR of a plaintext byte and a key byte, both known-structure quantities: for a chosen plaintext the attacker varies one byte and observes which table line is touched, recovering the key byte’s high bits directly. Later rounds require more work, but the first-round leak alone reduces the key space enough that the remainder falls to search.

The first published demonstration was Bernstein’s 2005 analysis, which used the timing of an encryption as a function of plaintext and showed that the server’s key could be recovered from a large number of remote timings. Later work refined the measurement and extended it to the last round, where the leak is against the final round key and hence against the master key through the schedule. The attacks do not require physical access to the machine running the cipher; a shared cache on a multi-tenant host suffices, and network timing jitter is often small enough to average out.

The class of leakage is broader than the cache. Any table indexed by secret data leaks through the cache, through the memory bus in some designs, through speculative execution, and through the branch predictor if the access is conditional. The general principle is that the address of a memory access is a side channel, and a cipher whose addresses depend on the key has a side channel by construction.

Bit-slicing

The cleanest structural fix is to remove the table. Bit-slicing represents the state not as bytes but as bit-planes: for a 128-bit block, eight 16-bit words, where word $i$ holds bit $i$ of each of the sixteen state bytes. A byte value is then spread across the eight words, and the S-box is computed as a Boolean circuit over those eight bit-planes.

The AES S-box circuit is the inverse map in $\mathrm{GF}(2^8)$ followed by the affine transform. Inversion can be computed with a tower-field decomposition: represent $\mathrm{GF}(2^8)$ as a quadratic extension of $\mathrm{GF}(2^4)$, invert in the smaller field, and combine. The resulting circuit uses on the order of a hundred AND, OR, XOR, and NOT operations, with the AND gates providing the nonlinearity. Each operation applies to a whole bit-plane, which is 16 bits wide, so the cost per S-box evaluation is amortised across sixteen bytes.

/* Bit-sliced S-box: the inverse map's nonlinear core, expressed over
   bit-planes. Each uint16_t holds one bit of sixteen state bytes. */
static void sbox_bitslice(uint16_t b[8])
{
    uint16_t t, u;
    /* Tower-field inversion: a handful of AND/XOR stages over planes.
       The AND gates are the only nonlinear steps; every plane is
       processed in parallel, so no memory address depends on data. */
    t = b[0] & b[1];            /* illustrative core; full circuit is longer */
    u = b[2] ^ b[3];
    b[0] ^= t ^ u;
    /* ... remaining stages of the tower-field inversion ... */
}

/* One AES round over 16 parallel blocks held in bit-planes:
   SubBytes is the circuit above, ShiftRows is a plane rotation,
   MixColumns is XOR and xtime over planes, AddRoundKey is XOR. */

The advantage is that the code path is fixed. Every operation is a register operation on a value of known width; there is no load whose address depends on the data, and no branch whose direction depends on it. The disadvantage is that the state representation is transposed, which makes interoperation with a byte-oriented API expensive: data must be transposed in and out, and the transpose itself must be constant-time.

Bit-slicing is not a software-only technique. It maps directly onto SIMD registers, where a 128-bit vector holds 128 parallel blocks’ worth of one bit-plane, and the same circuit then processes 128 blocks at once. The throughput is high and the timing is independent of the data. This is the basis of the fastest portable constant-time AES implementations.

Vector permutes

A second approach keeps the table but changes how it is indexed. Some instruction sets provide a byte-shuffle operation that selects bytes from a register-resident table by an index vector. If the entire 256-byte S-box is loaded into registers — sixteen 128-bit registers, or fewer with wider vectors — the substitution becomes a sequence of shuffles, each handling one 16-byte slice of the table with a comparison-based selection of which slice applies.

The selection is the delicate part. For each state byte, the implementation computes which of the sixteen table slices contains the desired entry, and then uses masks to select the corresponding shuffle result. The masks are computed arithmetically from the index, not by a branch, so the sequence of executed instructions is the same for every input. The cost is roughly four to eight instructions per byte substitution instead of one load, which is a significant slowdown but far less than a full bit-sliced circuit.

The critical requirement is that the shuffle instruction’s timing not depend on the index pattern. Some implementations of byte-shuffle have data-dependent timing on particular microarchitectures; a constant-time construction must be checked against the specific processor. This is a general hazard in side-channel work: an instruction that is constant-time on one generation may not be on the next, and the property has to be verified rather than assumed.

Hardware instructions and their boundary

Processors with AES instructions sidestep the problem entirely. The AESENC and related instructions perform one round — SubBytes, ShiftRows, MixColumns, AddRoundKey — in a single instruction with a fixed latency. There is no table in memory and no data-dependent address, so the instruction is constant-time with respect to the data by construction. The key schedule has its own instructions, and the key expansion’s S-box step is likewise performed in hardware.

This does not make the surrounding code constant-time. The mode of operation still has to handle data, and the boundary between the cipher and its mode is where leaks move to. A common pattern is that the cipher is fast and constant-time while the mode’s padding check, tag comparison, or error handling branches on secret data. Constant-time comparison of authentication tags, in particular, is a requirement that the cipher cannot supply — a tag check that returns early on the first mismatched byte leaks the position of the first difference, and repeated queries recover the tag.

Key loading is another boundary. If the round keys are expanded once and stored, the expanded key is a larger secret than the master key and sits in memory for the lifetime of the context. If they are expanded per block, the expansion’s S-box lookups are themselves a leak unless done in hardware or bit-sliced. The choice depends on whether the threat model includes memory disclosure, which is a different question from cache timing.

Verifying the property

Constant-time code cannot be validated by testing. A test that runs the code on many inputs and measures the time distribution can fail to detect a leak that depends on a rare input, and a passing test proves nothing about the inputs not tried. The practical methods are static analysis of the generated machine code and formal verification of the source.

The static approach checks the compiled output for the properties that matter: no conditional branch whose condition depends on a secret, no memory access whose address depends on a secret, no variable-latency instruction applied to a secret. Compilers complicate this, because a branchless source construct can compile to a branch, and a constant-time select can compile to a conditional move on one target and a branch on another. The check has to be performed on the binary that ships.

The formal approach annotates the source with a notion of secret and asks a verifier to prove that the observable behaviour — timing, memory addresses, branch directions — is independent of the annotations. Several tools do this for C and for assembly, and their use is now standard for cryptographic libraries. The property they prove is stronger than any test can establish, and it is also narrower: it says nothing about power consumption, electromagnetic emanation, or the behaviour of the microarchitecture’s speculative units, all of which are separate channels.

What the cost buys

The performance comparison is not close. A table-based AES on a general-purpose processor without AES instructions runs at a few cycles per byte; a bit-sliced implementation is several times slower per block but parallelises across blocks; a hardware-assisted implementation is faster than either and constant-time. The choice is therefore driven by the platform and the threat model rather than by a single best answer.

The threat model is the part that is often decided badly. A cipher running on a dedicated appliance with no co-resident processes and no network-observable timing has a much smaller exposure than the same cipher running in a shared cloud tenant. The cache-timing literature’s central point is that the exposure is often not where the implementer assumes: it is in the shared last-level cache, in the timing of a remote request, and in the difference between the fastest and slowest paths through the code.

For designs that cannot avoid table lookups — a cipher with a large S-box and no hardware support — the mitigation is to combine the lookup with a blinding step, so that the index is randomised by a per-encryption mask and the table itself is permuted consistently. The mask is removed after the lookup. This does not remove the leak, since the address still depends on the blinded index, but it makes the address depend on a fresh random value rather than on the key, and the attacker must average across many independent masks. The cost is two extra operations per lookup plus a mask generation, and the security depends on the mask’s quality and on the attacker’s inability to correlate observations across mask values.

The boundary between cipher and mode is where most real leaks live, and it moves as constructions change. A tweakable construction such as XTS computes its tweak by encrypting a sector number, and that encryption is a block cipher invocation whose own timing must be checked; a mode that branches on a padding byte does the same damage as a table lookup inside the round function. The cipher can only be as constant-time as its surroundings.

The interaction with the rest of the cipher is worth noting. Bit-slicing changes the representation of the state but not the cipher, so the round structure, the key schedule, and the mode are unaffected. The state matrix layout is still the same permutation, just expressed in a transposed form, and the S-box construction is still the same function evaluated as a circuit rather than a table. The constant-time constraint is orthogonal to the design; it constrains the implementation only.