How to Keep a Secret — From Doodles to DES

All the implementations can be found in my GitHub Repository.

Remember how when you were a kid, you and your friends came up with your own secret alphabet? Mine consisted out of weird doodles that looked too alike, was used only a few times, and soon forgotten. But most importantly, this alphabet fulfilled its purpose. It allowed us kids to communicate secretly with each other, using a code known only to us - a secret society of friends.

Though kids are not the only ones who want to hide their secrets. In the adult world, such code is called a cipher or an encryption function. Only the person who has a right key gets access to the hidden information.

What encryption functions are there?

I’m sure you have heard of the Caesar cipher, one of the oldest ciphers in history. It creates a new alphabet by shifting letters of the old one by n positions. So if we had a word, CAESAR, and we would want to encrypt it with a key n=3, we would get:

CAESAR -> FDHVDU

This is a very simple encryption. Therefore, it’s also very easy to crack either by brute force (just trying out all 26 keys) or by linguistic analysis that looks at letter frequencies in the plaintext and compares them to the letter frequencies in the cipher. So, for example, the most common letter in the English language is “E”, therefore it’s most likely that the most frequently occurring letter in the cipher might be “E”. (An example of the program that breaks Caesar cipher can be found here)

Another example is a Vigenère cipher. This one is more complicated, as the key is a word out of letters, so basically two alphabets are being shifted separately. Both encryption and decryption can be performed using the same Vigenère square:

   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B  B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C  C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D  D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E  E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F  F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G  G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H  H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I  I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J  J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K  K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L  L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M  M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N  N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O  O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P  P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q  Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R  R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S  S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T  T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U  U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V  V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W  W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X  X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y  Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z  Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

Alternatively, we could imagine all letters as numbers:

$E_i = (P_i + K_i) \bmod 26$ $D_i = (C_i - K_i) \bmod 26$

where $P_i$ = letter of plaintext, $K_i$ = key letter, $C_i$ = letter of ciphertext.

Though Vigenère can still be cracked. The only hard part is to find out the length of the key. There’re different ways to do it. On my GitHub I explained how to crack Vigenère cipher using Kasiski examination and wrote an implementation for both Caesar and Vigenère ciphers.

DES

Another type of cipher is a block cipher. In 1970s, one of the most famous block ciphers, DES (Data Encryption Standard), was created by IBM. For many years DES was used as a default protection of bank cards, financial transactions via ATMs, and SWIFT (Society for Worldwide Interbank Financial Telecommunication).

It’s a block cipher, so to encrypt the text, you need to first divide it into 64-bit blocks (if needed, pad the last block by adding the required amount of zeroes). Each block is then encrypted according to this scheme:

Now about each step in details.

Initial and final permutations

Before the beginning of the encryption, plaintext undergoes a small transformation called Initial Permutation. It just changes the position of each bit of plaintext in a predetermined pattern:

IP
50 42 34 26 18 10  2
52 44 36 28 20 12  4
54 46 38 30 22 14  6
56 48 40 32 24 16  8
49 41 33 25 17  9  1
51 43 35 27 19 11  3
53 45 37 29 21 13  5
55 47 39 31 23 15  7

This IP is reversed after the encryption process is completed. An inverse pattern is applied:

IP⁻¹
8 48 16 56 24 64 32
7 47 15 55 23 63 31
6 46 14 54 22 62 30
5 45 13 53 21 61 29
4 44 12 52 20 60 28
3 43 11 51 19 59 27
2 42 10 50 18 58 26
1 41  9 49 17 57 25

A lot of sources claim IP to be an additional security measurement, which is completely wrong. It is a deterministic, invertible, publicly known operation. Its only purpose was to ease hardware implementation in the 1970s. Now we would have zero need for it. So IP and IP⁻¹ solve rather an electrical engineering problem than a cryptographic one.

Feistel network

In 1973 German-born cryptographer Horst Feistel came up with a symmetric block cipher construction that became a crucial part of DES. The encryption pattern that you’ve already seen in the scheme can also be represented as an equation:

$L_r = R_{r-1}$ $R_r = L_{r-1} \oplus f(R_{r-1},\, K_r)$

$\oplus$ here stands for a bitwise addition modulo 2 (= in a binary system) called XOR.

The Feistel cipher uses a round function for encryption, which means that the same transformation is applied multiple times. Usually a Feistel network consists of more than 3 rounds. DES performs 16 rounds of encryption for additional security.

Key and subkeys

Each round $r$ needs a 48-bit subkey $K_r$. Subkeys are generated from a 64 bit key, that consists out of a 56 random bits sequence (actual key) plus 8 parity check bits (for detecting possible errors). Creation of these subkeys starts with a permutation PC-1 (yes, there’ll be a lot of permutations today so get ready). It doesn’t only switch the positions of the bits but also divides the key in two parts, C and D:

C
49 41 33 25 17  9
58 50 42 34 26 18
2 59 51 43 35 27
11  3 60 52 44 36

D
55 47 39 31 23 15
62 54 46 38 30 22
6 61 53 45 37 29
13  5 28 20 12  4

Then to both parts we apply a circular shift left operation, which basically moves all the bits to the left by n positions. The bits that have “fallen out” are attached on the right. For example, if n is 2:

10 1111  <<2
1111 10

How big n is depends on the round r:

Round	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
n	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

After each round a subkey is produced by permutating C and D again, this time using PC-2:

PC-2
17 11 24  1  5
28 15  6 21 10
19 12  4 26  8
7 27 20 13  2
52 31 37 47 55
40 51 45 33 48
49 39 56 34 53
42 50 36 29 32

E-Function

Now the right 32-bit-long block R0 has to be transformed into a 48-bit-long one to match a subkey. During this process, certain bits are doubled and moved. This expansion E is just like IP, a publicly known one, and is defined through this table:

E
1  2  3  4  5
5  6  7  8  9
9 10 11 12 13
13 14 15 16 17
17 18 19 20 21
21 22 23 24 25
25 26 27 28 29
29 30 31 32  1

Now when both the right block and subkey have the same length, we just XOR them and feed the result into the S-boxes.

Well, why not just generate a 32-bit subkey in the first place and save these extra steps? As we've already said, an S-box is a 6-to-4-bit transformation, which means the number of bits has to be divisible by six. 48 bits were found to be the best number of bits since it gives enough s-boxes for security without affecting the efficiency. Moreover, such transformation contributes to diffusion and therefore provides additional security.

S-boxes

The function used inside the Feistel network of DES is called a substitution box, or S-box. It is a 6-to-4-bit substitution mapping that makes encryption nonlinear and therefore secure as it deletes 2 bits of information each time. Now in simple language: What is this substitution box?

Imagine it as an actual box with a tiny person inside of it. We put in a small piece of paper with six bits on it, for example:

A person inside an S-box splits the input in two parts:

Outer bits (1st and last):  1 _ _ _ _ 0  →  10
Inner bits (middle four):   _ 0 1 1 1 _  →  0111

Then a little worker looks at the table on the wall and finds a field that corresponds to the outer and inner bits of the input:

	0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
00	0010	1100	0100	0001	0111	1010	1011	0110	1000	0101	0011	1111	1101	0000	1110	1001
01	1110	1011	0010	1100	0100	0111	1101	0001	0101	0000	1111	1010	0011	1001	1000	0110
10	0100	0010	0001	1011	1010	1101	0111	1000	1111	1001	1100	0101	0110	0011	0000	1110
11	1011	1000	1100	0111	0001	1110	0010	1101	0110	1111	0000	1001	1010	0100	0101	0011

He takes a new piece of paper and writes there:

and hands it out back to us. This way we got the following transformation:

101110 → 1000

It’s crucial that each out of eight S-boxes has its own table for 6-to-4 bit substitution. This ensures that each bit undergoes as many transformations as possible.

Additional permutation

The result that was handed out to us from the s-boxes needs to be permuted. Even though this permutation P is predefined and publicly known, it will still serve as an extra protection from an attacker, as it ensures that in the next round a bit goes into another S-box.

Now that we’ve covered each step in detail, look at the scheme in the beginning again. It should look much less scary now.

Decryption of DES

To decrypt DES, use the same scheme as we used for encryption: just pretend that ciphertext is now your plaintext and repeat the whole “encryption”. The only difference between encryption and decryption is that the subkeys need to be applied in reverse order: start with $K_{16}$, finish with $K_1$.

If all the permutations and steps are publicly known, can’t we just trace back the plaintext?

No. The main security mechanisms are S-boxes: they take in 6 bits but give out only 4, which means some information gets lost. If we wanted to trace it back, we would have multiple candidates for each four bits we got on the exit. And even if we decided to just trace each candidate back, not only it would’ve been too many candidates after 16 rounds of Feistel network, but also we would’ve had to crack a XOR operation between text and an unknown subkey that comes right before the S-boxes. The combination of an unknown input and information loss is exactly the reason why DES has never been broken mathematically.

However, the algorithm was still retired on 19.05.2005 simply because hardware became capable enough to crack an encryption by brute-forcing all possible $2^{56}$ keys. Now the Advanced Encryption Standard (AES) is used instead, but this is a topic for another time.

Are encryption and hash functions the same thing?

No. Even though both hash and encryption functions provide certain security, each of them has distinct properties and therefore different areas of application.

Hash functions are irreversible, which makes them perfect for authentication (a detailed explanation with an example can be found in my previous post about digital signatures).

Encryption has, in turn, a reverse process called decryption, which reveals the original plaintext to anyone who has a key. This makes the cipher a perfect tool for chatting in privacy. For example, each time you start a new chat in WhatsApp, you see something like “Messages and calls are end-to-end encrypted.”

Then how are ciphers connected to the history of hashes we have been talking about in all the previous posts?

You see, I was about to cover the next step in the history of hashes, but that construction was based on DES, so I thought a separate post that introduces the concept of ciphers properly might be a good idea. Small spoiler for the future post: a compression function combined with a symmetric block cipher (such as DES) gives you a cryptographically secure hash function. Exactly our goal!

My sources and further readings:

Official DES description by NIST
Chapter 7 from the Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone
Short history of DES