
	Bitslice DES key search

	Written by Matthew Kwan - mkwan@cs.mu.oz.au


What you have here is a bitslice implementation of DES optimized for
the RSA challenge key search. It will only work on 64-bit machines,
and it will only work quickly on RISC machines with lots of registers.

You are welcome to use this source code to compete in the RSA challenge.
If you win, please give credit where it is due (i.e. to me!), and maybe
you could see it in your soul to split some of the $10,000 prizemoney
as well?

The RSA key challenge values are -

Plaintext:  cd 81 19 9f 3a 14 05 e1
Ciphertext: 79 45 81 c0 a0 6e 40 a2


To clarify my notation the key bits are numbered, left to right,
k55, k54, k53, ..., k3, k2, k1, k0


The guts of the program is the function

	unsigned long	dessecr64 (const unsigned long *inputs);

It evaluates 64 keys simultaneously, where the keys bits are represented
in bitslice form in the inputs array.

The key bits k47, k41, k26, k13, k11, and k3 are constants, such that
all 64 combinations are evaluated simultaneously. Because these 6 bits
all enter the same S-box (S1) in the first round, the output of this
S-box will evaluate to a constant. If the compiler does its job properly
this should remove 100 instructions or so.

The remaining 50 keys bits are taken from the inputs array, whose values
are typically either 0 or 0xffffffffffffffff (usually entered as ~0UL).
Check the documentation in the source to see which array input corresponds
to which key bit.

The function returns a 64-bit value that indicates which key was
successful - i.e. it usually returns zero. Because ciphertext bits
are known at the output of the S-boxes in the 15th round, and we
typically can reject all 64 keys after 6 or 7 bits are known, the
function will usually only execute 14 and a bit rounds.

On average, this means about 11000 instructions are executed to evaluate
64 keys, or 172 per key. Some CPUs are capable of two instructions per
clock cycle, so you might be able to achieve one key per 86 clock cycles.


The "main.c" file contains routines to get useful results out of the
bitslice function. It probably isn't much use for practical key attacks,
but it is easily adaptable.

The main function checks for the command-line option "-P". If it is
present, it runs a performance check rather than a key search.

The function

	void	search1024 (unsigned long *key);

uses Gray code to iterate through the 16 values of key[46] .. key[49],
and passes these values to dessecr64(). As a result, it ends up searching
16x64 = 1024 keys. Hence its name.

If it finds a valid key, it calls the key_found() function. This
simply prints out the key. You may want to rewrite it to set off a
fire alarm or something.

The function keysearch() will call search1024() 2^46 times. If you
have the patience to wait.
