DES Implementation Collection

Multiple implementations of DES (Data Encryption Standard) encryption and decryption. Includes the following:

• des.py

  Straightforward but slow. Well documented and easy to follow; a good learning tool for people new to DES.

• des.c

  Conversion of des.py into C.

• des_64.c

  Optimized based on techniques described below in the optimizations section. Useful learning tool to understand these optimizations

• crack/

  Distributed, optimized key search (known plaintext attack). Takes a known plaintext, ciphertext pair and tries every key until one of them works. More information in /crack/README.rst

All implementations except for crack/ are learning tools for DES and optimizations. In contrast, crack/ is fully optimized and not meant for readability, although it is well commented and as readable as it can be without sacrificing speed.

The software is licensed under the MIT license (see LICENSE.txt), so you can modify and reuse this code without any restrictions. If you re-use a large part of the code, attribution would be nice, but not required.

Contributions are welcome!

des.py

To encrypt, run des.py using Python and pass in your plaintext and key in hex:

$ python des.py beefbeefbeefbeef 0123456789abcdef
45c4afc7a174e828

Here, beefbeefbeefbeef is the plaintext and 0123456789abcdef is the key. They both must be 16 hex digits.

To decrypt, use the -d option and give ciphertext instead of plaintext:

$ python des.py -d 45c4afc7a174e828 0123456789abcdef
beefbeefbeefbeef

ASCII Input/Output

If you want to give the plaintext with 8 ASCII characters, use the -a option:

$ python des.py -a ascichrs 0123456789abcdef
065c67acb4b351d6

When decrypting, -a will instead convert the resulting plaintext into ASCII:

$ python des.py -a -d 065c67acb4b351d6 0123456789abcdef
ascichrs

Verbose Output

You can also use the -v option to have it show detailed step by step calculations:

$ python des.py -v beefbeefbeefbeef 0123456789abcdef

Use this for your homework!

des.c and des_64.c

You will need GNU Make and gcc. To compile, run make:

$ make

This will create executables des and des_64.

For now, there is no way to provide input on the command line. Sorry, it's in the TODO list. You will have to put the input in the code yourself. Currently des and des_64 are set up to run many encryptions as a speed test.

Optimizations

These optimizations were proposed by Eli Biham in the paper "A Fast New DES Implementation in Software".

64-Bit Parallel

This is a way to do 64 encryptions simultaneously utilizing 64-bit integers.

Consider the normal way to do 64 encryptions at once. We would store each key, plaintext and ciphertext in an array. Then, every time we do an operation, we do it to all 64. Now consider how one of these values, the key for example, is stored. They would be stored in an array like this:

Normal Format

	Bit 1	Bit 2	Bit 3	Bit 4	Bit 5	...
int64 Key 1	a	b	c	d	e	...
int64 Key 2	f	g	h	i	j	...
int64 Key 3	k	l	m	n	o	...
int64 Key 4	p	q	r	s	t	...
int64 Key 5	u	v	w	x	y	...
...	...	...	...	...	...	...

Each row contains a key. We can store each key as a 64-bit integer, so we would have an array of 64 integers. Now suppose we transpose the table above:

Zipped Format

	Key 1	Key 2	Key 3	Key 4	Key 5	...
int64 Bit 1	a	f	k	p	u	...
int64 Bit 2	b	g	l	q	v	...
int64 Bit 3	c	h	m	r	w	...
int64 Bit 4	d	i	n	s	x	...
int64 Bit 5	e	j	o	t	y	...
...	...	...	...	...	...	...

We store each row in a 64-bit integer, again giving us an array of 64 integers. We call this zipped format. Now instead of looping through each of the 64 parallel encryptions to do an operation, we can just do the operation on one 64-bit integer. For example, Doing an xor with two elements of arrays in this format, a single xor instruction will simultaneously do an xor for all 64 encryptions.

When you see functions like zip_64_bit in the code, these convert from normal to zipped format. Since this is like transposing a matrix, zip_64_bit is its own inverse.

Permutation Elimination

Permutations are expensive and DES requires a lot of them. But we don't actually have to permute things in memory in order to compute the result. Instead, we can index the bit that would be used if the permutation were actually performed. Biham explains this as "changing the naming of the registers." This includes the expansion step as well.

This is best explained by example. Consider this pseudocode:

bit a, b, x, y
swap(a, b)
x = xor(a, x)
y = xor(b, y)

It's pretty obvious the swap is unnecessary:

bit a, b, x, y
x = xor(b, x)
y = xor(a, y)

Eliminating permutations is the same idea on a larger scale.

Bitwise S-Boxes

Traditionally, s-boxes are implemented with lookup tables. But s-boxes can actually be implemented using nothing but logic gate operations, which is much faster, especially when using the 64-bit parallel optimization.

Finding the optimum logic design of s-boxes is very non-trivial. A Eli Biham talks about this in his paper "A Fast New DES Implementation in Software", but Matthew Kwan's page entitled bitslice has much more up to date information, as well as some history.

The fastest implementation I know about is implemented in John the Ripper. They actually have multiple implementations, and the fastest one is automatically chosen.

This project's bitwise DES s-box implementation can be found in include/sbox.h, which defines functions s0 through s7. I didn't come up with any designs myself.