### The Data Encryption Standard (DES)

Try a demo of

#### Encoding schemes: From characters to integers and bits

In cryptography we often encrypt and sign messages that contains characters, but asymmetric key cryptosystems (Alice and Bob uses different keys) such as RSA and ElGamal are based on arithmetic operations on integer. And symmetric key cryptosystems (Alice and Bob uses the same key) such as DES and AES are based on bitwise operations on bits (a bit is either equal 0 or 1 and is an abbreviation for binary digit). Therefore, we have to convert the characters into integers or bits before we apply the cryptosystem to the message.

Because a computer can only handle bits, there already exists a method for converting characters into integers or bits, that uses the ASCII (American Standard Code for Information Interchange) table. A part of the ASCII table from Wikipedia is listed in the following table (notice that the binary representation on the Wikipedia site is only seven bits but we use eight bits, i.e. we have prepended an extra 0):

(space) 32 20 00100000
! 33 21 00100001
$\vdots$ $\vdots$ $\vdots$ $\vdots$
A 64 40 01000001
B 66 42 01000010
$\vdots$ $\vdots$ $\vdots$ $\vdots$
a 97 61 01100001
b 98 62 01100010
$\vdots$ $\vdots$ $\vdots$ $\vdots$

E.g. if Alice wants to send the message "Hey Bob!" encrypted to Bob with a symmetric key cryptosystem, she first converts it into its integer representation and then into its binary representation:

\eqalign{ H &\rightarrow 72 &&\rightarrow 01001000 \\ e &\rightarrow 101 &&\rightarrow 01100101 \\ y &\rightarrow 121 &&\rightarrow 01111001 \\ &\rightarrow 32 &&\rightarrow 00100000 \\ B &\rightarrow 66 &&\rightarrow 01000010 \\ o &\rightarrow 111 &&\rightarrow 01101111 \\ b &\rightarrow 98 &&\rightarrow 01100010 \\ ! &\rightarrow 33 &&\rightarrow 00100001 }

I.e. the message "Hey Bob!" is represented with integers as "72 101 121 32 66 111 98 33" and in binary as "01001000 01100101 01111001 00100000 01000010 01101111 01100010 00100001".

#### Bitwise operators

In math we are all familiar with the arithmetic operations such as addition, subtraction, multiplication and division. However, a computer works on bit strings, i.e. strings of 0's and 1's, and therefore needs similar operations when given two bit strings. The most important bitwise operations are NOT, AND, OR and XOR. In the following we give the result of the operations with one or two bits as input.

The NOT operation is often represented as !:

• $!0 = 1$
• $!1 = 0$

The AND operation is represented as $\wedge$:

• $0 \wedge 0 = 0$
• $1 \wedge 0 = 0$
• $0 \wedge 1 = 0$
• $1 \wedge 1 = 1$

The OR operation is represented as $\vee$:

• $0 \vee 0 = 0$
• $1 \vee 0 = 1$
• $0 \vee 1 = 1$
• $1 \vee 1 = 1$

The XOR (exclusive OR) operation is represented as $\oplus$:

• $0 \oplus 0 = 0$
• $1 \oplus 0 = 1$
• $0 \oplus 1 = 1$
• $1 \oplus 1 = 0$

#### PRF- and CPA-security of symmetric key cryptosystems

Alice and Bob's adversary Eve can make the following types of attacks on a symmetric key cryptosystem such as DES and AES:

• Ciphertext only attack: Eve tries to guess the key used to encrypt an observed ciphertext sent between Alice and Bob.
• Known plaintext attack: Eve somehow know the plaintext of an observed ciphertext sent between Alice and Bob and tries to guess the key.
• Chosen plaintext attack (CPA): Eve cheats Alice or Bob to encrypt a message of her choice and with her knowledge of the ciphertext and plaintext she tries to guess the used key.
• Chosen ciphertext attack (CCA): Eve can send a ciphertext to Alice or Bob and they return the decrypted message. With her knowledge of the ciphertext and plaintext she tries to guess the used key.

Symmetric key cryptosystems can be divided into two groups; deterministic and probabilistic cryptosystems. A deterministic cryptosystem such as DES and AES uses no randomness during the encryption, i.e. the same plaintext encrypted twice with the same key returns always the same ciphertext (which can be observed by Eve). This problem can be solved with a probabilistic cryptosystem such as the various modes of operations there exists for DES and AES, which uses randomness in form of an initialization vector.

In a good deterministic cryptosystem there should be no relation between the plaintext and ciphertext whatsoever when the key is unknown, i.e. encryption in a deterministic cryptosystem should behave like a truly random function. If this is the case we say that the encryption function is a pseudo-random function (PRF) and the cryptosystem is PRF-secure if Eve's advantage in guessing correct in the following game is negligible:

Eve sends a message $m$ to an oracle and it returns a ciphertext $c$ where $c$ is either an encryption of $m$ using the encryption function of the cryptosystem or an encryption of $m$ using a truly random function. Eve then tries to guess which encryption function the oracle used.

With a probabilistic cryptosystem we can achieve higher security compared to a deterministic cryptosystem and therefore we require that Eve can't tell the difference between a real encryption of hers message $m$ and an encryption of a random message with no relation at all to $m$. We say that a probabilistic cryptosystem is CPA-secure if Eve's advantage in guessing correct in the following game is negligible:

Eve sends a message $m$ to an oracle and it returns a ciphertext $c$ where $c$ is either an encryption of $m$ or a random message with the same length as $m$. Eve then tries to guess what $c$ is an encryption of.

Hence, if a probabilistic cryptosystem is CPA-secure the only information that a ciphertext leaks is the length of the encrypted message.

#### The cryptography explained

The Data Encryption Standard (DES) cryptosystem was developed by IBM in the early 1970s in association with the United States National Security Agency (NSA) as a modification of an earlier cryptosystem called Lucifer. In 1977 DES was adopted as a government standard and it was only expected that DES would be used as a standard for 10-15 years, however it was a standard until 1999 where developing of its replacement the Advanced Encryption Standard (AES) had begun.

DES is a special type of iterated cipher called a Feistel cipher because the encryption and decryption algorithm are almost the same. The only difference is that during decrypting are the round keys used in reverse order compared to encryption.

In DES uses Alice and Bob the same 56-bit key $K$ (the key is actually 64-bit, but 8 bits are used to validate the key) for encrypting and decrypting where plaintexts and ciphertexts are 64-bit. Because Alice and Bob uses the same key is DES called a symmetric cryptosystem where e.g. Alice sends the key to Bob with an asymmetric cryptosystem such as RSA or ElGamal. The reason why symmetric key cryptosystems are used when they first have to use an asymmetric cryptosystem to exchange the key, is because they are much faster than asymmetric cryptosystems.

A big difference between the following description of DES and an asymmetric cryptosystem is that we will operate with bits and their bitwise operations instead of integers and their arithmetic operations. And hence, plaintexts and ciphertexts are sometimes referred to as blocks in symmetric cryptosystems because they are bitstrings.

As previously described is DES based on the iterated Feistel cipher where the block (the plaintext or ciphertext) in each round (iteration) is divided into two halves $L^{i}$ and $R^{i}$ of equal length. Then in each round are $L^{i}$ and $R^{i}$ computed as:

\eqalign{ L^{i} &= R^{i-1} \\ R^{i} &= L^{i-1} \oplus f(R^{i-1}, K^{i}) }

where $f$ is called the round function and is given the right half of the previously block $R^{i-1}$ and the current round key $K^{i}$ as input.

The encryption and decryption algorithm in DES is the above round repeated 16 times as illustrated in Figure 1 (see below) where the bock $x$ (the plaintext or ciphertext) is first permuted accordingly to the initial permutation $IP$ where the output is the two halves $L^{0}$ and $R^{0}$ (each 32-bit) which is used in the first round, i.e. $IP(x) = L^{0}R^{0}$. After the 16 rounds is the block again permuted accordingly to the inverse initial permutation $IP^{-1}$ where the output $y$ is either the ciphertext (encryption) or the plaintext (decryption), i.e. $y = IP^{-1}(R^{16}L^{16})$ (notice that the two halves $L^{16}$ and $R^{16}$ are swapped before the inverse permutation is applied). The two permutations $IP$ and $IP^{-1}$ are fixed and have no cryptographic influence.

As illustrated in Figure 1 uses each round a 48-bit round key $K^{i}$, but as previously described agrees Alice and Bob only on a single 56-bit key $K$. To solve this problem they use a key schedule which diverts from the 56-bit key $K$ the 16 round keys $K^{1}, K^{2}, \dots, K^{16}$ where $K^{i}$ is a certain permuted selection of bits from $K$.

The round function $f$ is illustrated in Figure 2 and executes the following steps:

1. First is the right half $R^{i-1}$ expanded from 32-bit to 48-bit with the expansion function $E$ by repeating 16 of the bits.
2. $E(R^{-1})$ is then XORed with the round key $K^{i}$ and the result is divided into eight blocks of 6-bit, i.e. $B = E(R^{-1}) \oplus K^{i}$ where $B=B_{1}B_{2} \dots B_{6}$.
3. Each of the 6-bit blocks $B_{i}$ are then substituted with a 4-bit block $C_{i}$ using a S-box $S_{i}$, i.e. $C_{i} = S_{i}(B_{i})$. In DES are there eight S-boxes and each S-box is a look-up table with 4 rows and 16 columns where each row contains the numbers 0 to 15 permuted in a specific order (the permutations where chosen to prevent certain types of attacks, see below). Given the 6-bit string $B_{i} = b_{1}b_{2}b_{3}b_{4}b_{5}b_{6}$ and the S-box $S_{i}$ the result $C_{i}$ is computed as follows: The two bits $b_{1}b_{6}$ determines the binary representation of the row $0 \leq r_{i} \leq 3$ in $S_{i}$ and the four bits $b_{2}b_{3}b_{4}b_{5}$ determines the binary representation of the column $0 \leq c_{i} \leq 15$ in $S_{i}$. The entry $(r_{i},c_{i})$ in $S_{i}$, which is a number between 0 and 15, is then converted to a binary number and denoted $C_{i}$.
4. Finally is the 32-bit string $C = C_{1}C_{2} \dots C_{8}$ permuted according to the permutation $P$ and $P(C)$ is the output of the function $f$.
###### Figure 2: The $f$ function

To clarify the use of the S-boxes we show how to compute the output $C_{1}$ when given the input $B_{1} = 011011$ and the S-box $S_{1}$ (see below). The first and last bits are $b_{1}b_{6} = 01$, which is the binary representation of the integer 1, i.e. the row is $r_{1} = 1$. The middle four bits are $b_{2}b_{3}b_{4}b_{5} = 1101$, which is the binary representation of the integer 13, i.e. the column is $c_{1} = 13$. Finally the result is the integer in entry $(1, 13)$ (remember the first row and the first column in the table starts at index 0) which is $5$ and in binary $0101$, i.e. $C_{1} = 0101$.

The S-box $S_{1}$
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

The S-boxes were designed to prevent certain types of attacks, especially a method called differential cryptanalysis which was discovered by IBM in the 1970s but kept secret in almost 20 years until it was rediscovered by Biham and Shamir in the early 1990s. Therefore, at the time DES was proposed some people suggested that the S-boxes might contain hidden trapdoors which would allow the NSA to decrypt messages while claiming that DES was secure. But when Biham and Shamir (re)discovered differential cryptanalysis it was clear that the S-boxes were designed to prevent this type of attack and not to make DES insecure.

Another property of the S-boxes that is vital to the security of DES is that the S-boxes are the only non-linear function in DES (the linear functions are the permutation $P$ and the expanding function $E$). A cryptosystem that is only based on linear functions is easy to break with e.g. a known plaintext attack (given a plaintext and its corresponding ciphertext it's easy to compute the secret key). A function $g$ is linear if it satisfies that $g(A \oplus B) = g(A) \oplus g(B)$ for two bitstrings $A$ and $B$. E.g. let $A = 101000$ and $A = 011011$. We now want to show that the permutation $P$ and the expanding function $E$ are linear, but the S-boxes $S_{i}$ are non-linear. Assume that the permutation is given as $P(X) = x_{2}x_{4}x_{1}x_{3}x_{5}x_{6}$:

\eqalign{ P(A) \oplus P(B) &= P(101000) \oplus P(011011) = 001100 \oplus 100111 = 101011 \\ P(A \oplus B) &= P(101000 \oplus 011011) = P(110011) = 101011 }

i.e. $P(A \oplus B) = P(A) \oplus P(B)$ and the permutation is a linear function. Now assume the expanding function is given by $E(X) = x_{1}x_{2}x_{3}x_{4}x_{3}x_{4}x_{5}x_{6}$, i.e. it expands 6-bit to 8-bit:

\eqalign{ E(A) \oplus P(B) &= E(101000) \oplus E(011011) = 10101000 \oplus 01101011 = 11000011 \\ E(A \oplus B) &= E(101000 \oplus 011011) = E(110011) = 11000011}

i.e. $E(A \oplus B) = E(A) \oplus E(B)$ and the expanding function is linear. FInally for the S-boxes we use the S-box $S_{1}$:

\eqalign{ S_{1}(A) \oplus S_{1}(B) &= S_{1}(101000) \oplus S_{1}(011011) = 1101 \oplus 0101 = 1000 \\ S_{1}(A \oplus B) &= S_{1}(101000 \oplus 011011) = S_{1}(110011) = 1011 }

i.e. $S_{1}(A \oplus B) \neq S_{1}(A) \oplus S_{1}(B)$ and the S-boxes are non-linear functions.

A serious flaw of DES is its short 56-bit keys and already in the 1990s it became feasible to break DES by a brute-force attack. I.e. given an input block $x$ and an output block $y$, we run the DES algorithm $DES$ with difference keys until $y = DES_{K}(x)$, and hence we have found the used key $K$. One solution to this problem is to use DES multiple times. The most used method is called Triple DES and runs the DES algorithm three times using different keys:

$y = TDES_{K_{1},K_{2},K_{3}}(x) = DES_{K_1}(DES_{K_2}(DES_{K_3}(x)))$

Notice that $K_{1}$, $K_{2}$ and $K_{3}$ are not the 48-bit round keys but 56-bit main keys.

A variant of Triple DES replace the middle DES encryption by a DES decryption, i.e. the middle DES algorithm runs with the round keys in reverse order. Now, if we chooses the keys in this version as $K_{1} = K_{2} = K_{3}$ it's the same as running the DES algorithm once because we first encrypts and then decrypts the message which have no influence and finally we encrypts the message again. Another variant chooses the keys as $K_{1} = K_{3}$, which reduces the key size. Finally, a variant called DES-X uses a single DES encryption combined with the input block $x$ XORed with $K_{1}$ and the output block $y$ XORed with $K_{3}$:

$y = XDES_{K_{1},K_{2},K_{3}}(x) = DES_{K_2}(x \oplus K_{1}) \oplus K_{3}$

##### The protocol
 Key exchange Alice and Bob agree on the 56-bit key $K$. Encryption Alice: Uses the key $K$ in the key schedule to generate the 16 48-bit round keys $K^{1}, K^{2}, \dots, K^{16}$. Uses the round keys in the order $K^{1}, K^{2}, \dots, K^{16}$ in the DES algorithm $DES$ to encrypt the message $m$ by $c = DES_{K}(m)$. Alice sends the 64-bit ciphertext $c$ to Bob. Decryption Bob: Uses the key $K$ in the key schedule to generate the 16 48-bit round keys $K^{1}, K^{2}, \dots, K^{16}$. Uses the round keys in the reverse order $K^{16}, K^{15}, \dots, K^{1}$ in the DES algorithm $DES$ to decrypt the ciphertext $c$ by $m = DES_{K}(c)$.

Try a demo of the encryption scheme here.

##### Example

Alice wants to send an encrypted message $m$ to Bob. They first agree on a 56-bit key $K = 10101001 \dots$ and both generates the 16 48-bit round keys with the key schedule:

\eqalign{ K^{1} &= \dots 10001000 \\ K^{2} &= \dots 11110001 \\ &\vdots \\ K^{16} &= \dots 00000000 }

Alice then encrypts the 64-bit message $m = 10110011 \dots$ using the round keys in the order $K^{1}, K^{2}, \dots K^{16}$ and sends the 64-bit ciphertext $c = DES_{K}(m) = 10101011 \dots$ to Bob.

Bob decrypts the received ciphertext with the round keys in the reverse order $K^{16}, K^{15}, \dots K^{1}$ by computing $m = DES_{K}(c) = 10110011 \dots$.