the bitslice method

Darrell Kindred (dkindred@cmu.edu)
Thu, 29 May 1997 12:23:57 -0400


First, a quick correction on the Solaris question:

I wrote:
> SunOS 5.5.1 is the same thing as Solaris 2.5.1, so no,
> 64-bit code won't work on that machine.

While it is true that SunOS 5.5.1 is the same thing as
2.5.1, my second claim (that 64-bit arithmetic won't work)
may not be true. An investigation is under way.

Now, a little bit about "bitslicing"...

Andy Church writes:
> Curiosity attack: What _is_ bitslicing, anyway?
> What makes it faster than "regular" clients?

The basic idea is that if you have a CPU that operates on
N-bit integers, you can treat it like N processors each
operating on single bits. So for a 32-bit CPU, you get 32
"virtual processors", and for a 64-bit CPU, you get 64.
The parallel machine you're simulating is of the "SIMD"
(single instruction, multiple data) model; that is, all the
"processors" execute the same instruction at each step, but
they operate on different data.

Now, this certainly doesn't mean you can do everything 32 or
64 times as fast, because your virtual processors only work
on a single bit at a time, so it takes more steps for them
to accomplish most tasks. However, the calculations
necessary to compute DES are well-suited to this kind of
single-bit operation. In a bit-parallel (or "bitslice") DES
keysearch approach, you test 32 or 64 different keys at
once--one key per virtual processor. It turns out that you
can check a block of 64 keys this way in substantially fewer
steps than it would take to test the 64 keys one at a time,
using a conventional approach.

The main reason that DES is faster to run using the
bit-parallel technique is that computing the DES function
requires doing lots of different bit-level operations, such
as permuting the individual bits of a 64-bit chunk of data,
or applying an arbitrary function to six bits of one word
and inserting the four-bit result into another word. These
operations are difficult to do efficiently on general-purpose
CPUs, but when you're operating on one bit at a time, they
become simpler.

It's been fun writing the bit-parallel code; in some ways
the process is more like designing a digital circuit than
it is like conventional programming (see the paper below for
details).

Eli Biham was the first person (to my knowledge) to describe
a bit-parallel DES implementation. You can read his paper,
"A Fast New DES Implementation in Software", in the
proceedings of Fast Software Encryption 4 (1997). It's
also available in postscript here:

http://www.cs.technion.ac.il/~biham/publications.html

- Darrell