Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I have read a paper on Bit Slicing and Lightweight crypto but cannot understand how bitslicing makes encryption scheme faster.
Please can someone explain with an example exactly how bit slicing makes the code faster (even a single xor example will suffice)? Can bitslicing be applied to any encryption scheme?
Bitslicing is a technique where computation is:
Doing 1 generates a large number of gates: XOR of two $n$-bit words requires $n$ gates; for $n>1$ their addition modulo $2^n$ requires $5n-6$ gates; each 8-bit S-box lookup in AES SubBytes requires about 128 gates; on the other hand rotations, arbitrary bit shuffling, selection or expansion requires no gate.
Doing 2 implements $w$ gates per instruction manipulating $w$-bit registers, and most of the speedup (if any) comes from that parallelization by a factor of $w$ (caveat: the effective $w$ can't be larger than the number of computations to perform simultaneously). Increasingly many embedded CPUs support $w=32=2^5$, CPUs with AVX instructions even support $w=256=2^8$. Most importantly, bitsliced code is immune to cache-related side channels (including timing). As a bonus, it is extremely linear, that makes efficient scheduling of data accesses easier, and there's no branching delay.
On the downside of bitslicing: Most importantly, making $w$ simultaneous operations do not match all workloads! For a single large file and common modes of operation of a block cipher, only CTR (or the flawed ECB) is fully usable (CBC and CFB are usable for decryption only, OFB is unusable). Also, the code is large and relatively complex; conversion from normal to bitsliced form of arguments (and back for results) requires bit transposition, which adds some significant overhead; lots of intermediary results or state data that would fit in registers or L1 cache in a normal implementation, do not.
An upside, independently of speed: bitslicing a cryptographic operation removes any dependency of the duration to the data manipulated (because bitwise operators have fixed duration). This prevents side-channel attacks thru timing analysis (of the operation bitsliced), including the otherwise difficult to avoid cache-related timing attacks during table lookups for S-Tables.
In principle, any cryptographic calculation performed on multiple instances can be bitsliced. However many operations natively handled without bitslicing are unlikely to gain any speed benefit; this includes anything too simple (like the proposed XOR), or with grossly inefficient translation to gates (like modular multiplication, or looking up large arbitrary fixed tables, or sizable dynamic tables), or where the execution flow has too many paths. Refer to Ilmari Karonen's answer for a more detailed classification. And again, we need to be in a position to make several computations in parallel!
The archetypal example of a real cipher where bitslicing can have a speed benefit is (3)DES, as pioneered by Eli Biham's A fast new DES implementation in software (in Proceedings of FSE 1997).
Anything much simpler than DES that I could construct to show the benefit of bitslicing would be far from real-life; so I take as example a purely software implementation of (single) DES, with pre-computed subkeys, on a CPU with like a dozen general-purpose 128-bit registers, 128-bit (cache) memory accesses, for encryption of 128 blocks (1024 arbitrary bytes; I ignore optimizations possible in CTR mode).
A traditional (non-bitsliced) implementation goes:
The S-box loop is customarily unrolled (as well as at least two consecutive executions of the round loop, which makes the exchange essentially free), thus cost is dominated by the numbered steps. We can suppress 1 out of 8 steps 1 and 6. So a good approximation of the cost (ignoring IP and IP-1 for now) is $w$ times 16 times: 9 memory loads (8 of which indexed) and about 38 other simple operations.
Bitsliced DES suppresses the outer block loop, replacing it with operations on $w=128$-bit at each step manipulating block-dependent data:
We'll unroll the round loop (if we want fixed addresses for the load/stores other than for the subkeys, we need two versions depending on if $r$ is odd or even). Independently: we can use that 2 out 6 values loaded at step 1a will be reusable for the next (or/and last) S-box, reducing the effective number of loads at step 1b, at the cost of few extra registers.
In step 2a, an S-box is replaced by boolean operations. Using the expressions derived by Matthew Kwan in Reducing the Gate Count of Bitslice DES (ePrint 2000/051), the average cost goes down to 51 boolean operations per S-box, at the cost of requiring some temporary registers, and somewhat undesirable bursts of stores at step 2d.
So a good approximation of the cost (ignoring initial and final transpositions) is 16 times: 65 memory loads and 32 memory writes (none indexed), and about 440 other operations.
Bitslice DES is thus a winner on speed if we ignore the cost of the initial and final transpositions, even if wide operations are somewhat more costly than narrow ones: memory accesses per round are reduced from $9w=1152$ to $97$; other operations from $38w=4864$ to $440$. That tenfold improvement (for $w=128=2^7$) outweighs the extra cost of the transpositions (which anyway is moderately higher than the cost of $w$ times IP and IP-1: in the end, the same amount of data is transposed). With careful coding, bitslice DES might be faster including for $w=32=2^5$.
The basic idea of bitslicing, or SIMD within a register, involves two parts:
expressing the cipher in terms of single-bit logical operations (AND, OR, XOR, NOT, etc.), as if you were implementing it in hardware, and
carrying out those operations for multiple instances of the cipher in parallel, using bitwise operations on a CPU.
That is, in a bitsliced implementation, instead of having a single variable storing, say, a 32-bit number, you have one variable storing the lowest bit of the number (or, rather, of $n$ numbers, where $n$ is the number of bits your CPU can store in a register), another variable storing the second lowest bit(s) of the number(s), and so on.
Obviously, calculating everything bit-by-bit is (usually) a lot slower than just calculating things the ordinary way. But with an $n$-bit processor, a bitsliced implementation can run up to $n$ instances of the cipher (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 cipher, you end up with a net gain in throughput.
So which kinds of operations work well with bitslicing, and which operations don't?
Bit shifts, rotations and other bit permutations become trivial in a bitsliced implementation, since they just correspond to relabeling variables. Thus, such operations effectively take no time at all in a bitsliced implementation. Since crypto code tends to use such operations a lot, this alone can be a huge win for bitslicing.
(However, this is only true for constant bit shifts. If the shift amount depends on the data being processed, bitslicing it becomes much harder.)
Bitwise logical operations like XOR tend to be near the break-even point. If you have two sets of 32 numbers, each of them with 32 bits, and you want to XOR them with each other, it doesn't really matter if you do it number by number or bit by bit — you'll need to do 32 XORs either way.
Of course, if your CPU has, say, 64-bit or 128-bit registers (like, say, any modern x86 CPU with SSE does), then you can carry out 64 or 128 bitsliced 32-bit XORs, still using only 32 XOR instructions. Thus, bitslicing may still win out for XOR, just because of the extra parallelism.
Addition and subtraction can also be implemented using bitwise logical operations, essentially by implementing an adder circuit. This requires up to five instructions per bit (two XORs, two ANDs and one OR/XOR) to implement a full adder, although this can sometimes be reduced depending on what instructions are available (e.g. something like three-input XOR and majority instruction could allow implementing a full adder in two instruction per bit) and what the result will be used for (e.g. if carry-save addition can be used). Thus, addition and subtraction tend to be somewhat less efficient in a bitsliced implementation, although the increased parallelism mentioned above may still compensate for this.
More complex arithmetic, like multiplication and division, can also in principle be implemented using bitslicing, but the resulting code may be very slow and complicated. Fortunately, these operations are rarely used in ciphers (although public-key crypto sometimes requires them).
Notably, though, (binary) Galois field multiplication is a lot easier to bitslice than ordinary multiplication, due to the absence of carries. Also, multiplication (whether ordinary or in a Galois field) by a constant can be decomposed into a combination of shifts (free!) and additions (or XORs), making it fairly easy to bitslice.
Table lookups are generally very hard to bitslice, for obvious reasons. However, if the look-up table is small and fixed, like the S-boxes in many ciphers, then it may be possible to replace it with a logical circuit that computes the same result, and bitslice that. This is how Eli Biham handled the S-boxes in their original 1997 bitsliced DES implementation, for example. Conveniently, optimized hardware S-box implementations can often be directly translated into bitsliced software implementation. Thus, any ciphers that can be efficiently implemented in hardware (which tends to be a common design criterion) can usually also be bitsliced well.
Conditional code (like if statements) is also rather difficult to bitslice, although there are ways to emulate it with masking. For example, a conditional expression like x = (condition ? a : b) may be rewritten as x = (a & mask) | (b & ~mask), where mask is set to all ones if condition is true, and to all zeros otherwise, and then bitsliced.
A general advantage of bitslicing is that bitsliced code tends to run well on heavily pipelined modern CPU, since it tends to have a low risk of pipeline stalls and plenty of opportunities for optimal instruction reordering. Basically, in normal crypto code, if you calculate something like:
w = x + (y XOR z)
then the XOR calculation must finish before the addition can start, preventing the operations from executing in parallel. In a bitsliced implementation, however, we can e.g. calculate the low-order bits of the XOR first, and then move on to the high-order ones, so that when we start doing the addition, the low-order bits that we need first will have had plenty of time to get ready.
If we want, we can also e.g. interleave the XOR and addition calculations together (or just let the compiler do that for us), only calculating the XOR bits just in time to be ready when we need them for the addition. This can reduce the potential for stalls within the addition code, by letting the processor calculate the XORs while it's waiting for the carry bits to be ready, and may also improve register and/or cache locality.
Also, thanks to the elimination of conditionals, as described above, bitsliced code tends not to suffer from branch misprediction. Conveniently, this also tends to make it resistant to timing attacks, and thus more secure.
All that said, bitslicing also has its downsides. One is that, when processing $n$ instances of the cipher in parallel, you need to store $n$ copies of the cipher state. Thus, whereas in a conventional implementation you might be able to fit the full state in CPU registers, or at least in L1 cache, a bitsliced implementation will use a lot more space, and thus may end up pushing some data out to slower caches, or even to uncached RAM.
This issue can sometimes be partially alleviated by sharing data between cipher instances, e.g. when encrypting multiple data blocks with the same key. Also, clever instruction reordering (by the programmer or by the compiler) may improve cache locality, e.g. by computing multiple operations on, say, the low-order bits of the data (and so keeping the variables storing those bits in registers or in fast cache) before performing the same operations on other bits. Still, in general, a bitsliced cipher implementation is likely to have somewhat poorer cache locality than a non-bitsliced one.
Also, some algorithms just don't bitslice well. A notable example is the RC4 stream cipher, which seems almost designed to frustrate any bitslicing efforts:
It has a large internal state (258 × 8 = 2064 bits per cipher instance), most of which cannot be shared between instances, making a bitsliced implementation require a lot of memory.
Most of that state consists of a constantly changing 8-bit lookup table. Because the lookup table isn't fixed, it cannot be replaced by a logical circuit like, say, the S-boxes in DES or AES can.
Only 4 bytes of the state change per iteration, but one of the bytes that does change is, in effect, pseudorandomly chosen. Running many instances of RC4 in parallel would mean that, on every iteration, many bits of the state would change in some instance (but rarely in more than one).
In fact, I've sometimes wondered if RC4, or some similar algorithm, might not be useful as a deliberately unparallelizable and hardware-unfriendly component in an scrypt-like construction.
Bitslicing is a technique that allows multiple instructions/Data points to be encoded into a single register.
The idea is that you encode several bitwise operations within a single register. So, instead of 32 bitwise OR operations in sequence, you could reduce the total number of operations by cramming the data into SIMD registers and executing in parallel.
So you would change
POR EAX, ECX // Compares A with B
into
OR XMM0, XMM1 // makes up to 32 such comparisons if you have AVX extensions.
Now the downside here is that you have to get the data into the format the simd operation wants such that your result will be an easily consumed block of values. Basically you have to "slice":
A1-A2-A3-A4 OR B-1-B2-B3-B4
Into:
A1-D1 OR B1-E1 = C1-F1
Which isn't free. However, with careful optimization this can result in a significant speed in many circumstances. As an additional bonus, this technique can be used to avoid table lookups in certain situations (https://eprint.iacr.org/2015/727.pdf) helping strengthen the implementation against cache timing attacks.
The reason this technique is well suited to crypto, is that cryptography often uses repeated bitwise operations that can easily be paralellized in this way. The others were right to point you toward the original papers for the implementation details of this:
http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1997/CS/CS0891.pdf
is a good place to start. I'll give a quote from the original paper which sums up a few of the specific advantages of doing DES with SIMD on a 64bit computer:
"The eight S-Boxes can be applied in parallel and thus pipelining can use it without pipeline stalls"
He goes on, but I haven't found the paper in a format that isn't obnoxious to copy and paste from. Read the entire paper, it's short and to the point.
