Originally published by Robert Beisert at fortcollinsprogram.robert-beisert.com

Encryption Case Study: DES

Fair warning: this is a bit more technical than most of my posts. The basic idea I want to convey is this – if we combine several simple operations and repeat them multiple times, we can create encryptions that are very hard to crack.

We’ve covered some basic encryption concepts so far, so let’s take a look at a classic block encryption technique – the Data Encryption Standard (DES) encryption.

Ideas

The basic idea of the DES encryption is to apply four simple operations on each 64-bit block of your plaintext data. These operations are:

1. Expansion – Transform the first 32-bit block into 48 bits (treated like 8 6-bit pieces) using a special permutation function

2. Key mixing – XOR the expanded key with 48 bits of the “subkey” – a stream cipher generated from a 64-bit key

3. Substitution – Transform each 6-bit piece back into a 4-bit result using a specialized lookup table

4. Permutation – Rearrange the resulting 32-bit block using a particular permutation function

5. (implied) We swap the first and last 32-bits between every operation, which spreads the encryption out

We call each 6-bit piece an “S-box”, because these are the values that are passed into the substitution function (and, originally, these were individual chips). We also have an “E-box” which performs the expansion, and a “P-box” which performs the permutation. All of these boxes were originally specially designed chips, but now we can perform the algorithm using structures that do basically the same thing.

The Subkeys

A moment ago, I mentioned that the DES encryption standard used a 64-bit key, but that’s only half-true. The “key schedule” is generated using 7 bits from each byte, with the last bit used as a “parity check” (a bit that ensures that the key is probably what we originally wanted to input). Functionally, we only get 56 bits for our key, which is one big reason the standard was discarded (now we can crack a 56-bit key in a few seconds, tops).

The DES uses what we call “Permuted Choice boxes”, or PCs, to do something special to the first 28 and the last 28 bits of the key. At each stage, the first 28 will be shifted by 1 or 2 bits, and the last 28 will be shifted by 1 or 2 bits. This shift is programmed into the PCs, so it’s easy to replicate these shifts when the time comes to decrypt our message.

As a result, we create a new 56-bit key block for every stage of the DES encryption. We take the left-most 24 bits from both the first and last 28 bits to create a 48-bit “stream cipher”.

The Magic

Each operation in this encryption is so simple, it could be done on one circuit board back in the 1970s. How can we be sure that something so simple produces suitable randomness to prevent easy decryption?

We do it a BUNCH of times.

For every 64-bit block of plaintext, we perform the encryption 16 times. That means that each 32-bit block has been expanded, mixed, substituted, and permuted 8 times, with a different key each time (complexity of about 256 operations). Because each operation scrambles the ciphertext a bit more, it’s fairly difficult to crack the encryption without having the original key – there are just too many operations…

The Problem

The biggest problem with the DES standard is that we know how it works. We have documentation on how the encryption is done, and we know how to decrypt the resulting ciphertext. Because computers have only gotten faster over time, brute-force attacks are embarassingly easy.

There was also a fear that the NSA had built a backdoor into the encryption that would make it easy for them to crack any ciphertext they intercepted. It took years to prove that the algorithm had no backdoors, by which time pretty much anyone could crack DES. Bummer.

Why it Matters

We still talk about DES for a few simple reasons:

1. It’s not that complicated by encryption standards

2. The same principles are applied in modern encryption techniques, which use much larger keys and only slightly more complicated algorithms.

Basically, if you can figure out how DES works, you can fairly easily figure out more modern encryption techniques.

photo by: