Why Bit-Slicing Eliminates Cache Timing Attacks

Bit-slicing is a software technique that reconstructs algorithms entirely out of bitwise Boolean logic, eliminating data-dependent memory lookup latencies in cryptographic operations. By replacing memory-based lookup tables (such as S-boxes) with purely logical instructions executed across CPU registers, bit-slicing ensures that execution time remains constant regardless of the input data or secret key, effectively neutralizing cache-timing side-channel attacks.

The Problem with Data-Dependent Memory Lookups

In standard cryptographic implementations, non-linear transformations—such as the substitution boxes (S-boxes) in AES or DES—are traditionally implemented as lookup tables stored in memory. When an algorithm accesses a table element, the memory address depends directly on sensitive data, such as a combination of the plaintext and the secret key.

Modern CPUs rely on complex memory hierarchies, including L1, L2, and L3 caches. If a requested memory address is already in the cache, the CPU retrieves it quickly (a cache hit). If it is not, the CPU incurs a delay while fetching the data from main memory (a cache miss). Attackers can measure these slight timing variations to infer which memory addresses were accessed, ultimately reconstructing the secret cryptographic key.

How Bit-Slicing Replaces Memory Accesses

Introduced by Eli Biham in 1997, bit-slicing views an \(N\)-bit processor register not as a single integer, but as a vector of \(N\) single-bit values. Data is transposed so that the \(i\)-th bits of \(N\) different blocks (or internal state variables) are stored across parallel registers.

Under this model:

1. Substitution via Boolean Logic: Instead of querying an array in RAM or cache, mathematical transformations are synthesized into a combinatorial logic circuit composed strictly of basic Boolean operations: AND, OR, XOR, and NOT.
2. Execution in Registers: Every operation occurs directly inside CPU registers and the Arithmetic Logic Unit (ALU), entirely bypassing the memory subsystem during computation.
3. Implicit Parallelism: Because standard registers operate on 64, 128, 256, or 512 bits simultaneously (such as with AVX or NEON extensions), the bit-sliced circuit computes operations for multiple data blocks in parallel.

Why Latency Becomes Deterministic

Bit-slicing achieves constant-time execution due to the hardware-level characteristics of modern ALUs:

• Instruction Timing Invariance: On virtually all CPU architectures, bitwise logic instructions (AND, XOR, etc.) execute in a fixed number of clock cycles (typically one cycle). The execution time does not depend on whether the bits are 0 or 1.
• Absence of Memory Addresses: Because secret data is never converted into memory addresses, memory access patterns cannot leak information. There are no table reads to produce variable cache hits or misses.
• Branch-Free Control Flow: Bit-sliced implementations do not use data-dependent branches or conditional jumps, removing timing variations caused by CPU branch predictors.

By reducing state transformations to uniform sequences of hardware-level logic gates, bit-slicing decouples execution latency from the values of the processed binary data, guaranteeing constant-time performance and robust resistance against timing attacks.