For questions about bitsliced (SIMD-within-a-register / SWAR) implementation of ciphers and other cryptographic primitives.

Bitslicing, also known as "SIMD within a register" (SWAR), is a technique used to compute multiple evaluations of a function (such as a block cipher, a hash, etc.) in parallel on a single CPU core using bitwise logical operations (AND, OR, XOR, NOT).

In a bitsliced implementation, instead of having a single variable storing, say, a 32-bit number, one would have one variable storing the lowest bit of the number (or, rather, of $n$ numbers, where $n$ is the number of bits the CPU can store in a register), another variable storing the second lowest bit(s) of the number(s), and so on, for a total of 32 variables.

While calculating everything bit-by-bit is generally slower than just calculating things the ordinary way, an $n$-bit processor can run up to $n$ bitsliced instances of the function (e.g. to encrypt up to $n$ blocks of data) in parallel. Thus, as long as the bitsliced implementation is no more than $n$ times slower to run a single instance of the function, it will yield a net gain in throughput.

The main advantages of bitslicing are:

  • Potentially higher throughput than conventional software implementations, especially for functions designed for hardware implementation or for CPUs with a narrow register width.

  • Strong immunity to timing attacks (and potentially some resistance to other side channel attacks) due to the (necessary) elimination of data-dependent branches.

However, not all functions are well suited to bitslicing. While most basic arithmetic and logical operations bitslice well, functions that manipulate large amounts of mutable state or which require data-dependent table lookups can be difficult or impossible to bitslice.

Also, bitslicing necessarily trades off latency for throughput: while the overall time to compute $n$ parallel evaluations of a function using a bitsliced implementation may be lower than with a conventional implementation, the minimum time needed to get the results for one evaluation is almost surely higher. Thus, bitslicing is poorly suited for sequential uses like CBC encryption, where the input to one evaluation of the function depends on the output of the previous one, or for latency-critical applications where getting one result fast is important.

history | excerpt history