Symmetric Cryptography: Data Encryption Standard (DES)

Introduction to Symmetric Cryptography and the Data Encryption Standard (DES)

These lecture notes focus on the Data Encryption Standard (DES), a cornerstone of symmetric cryptography presented by Prof. Dr.-Ing. Lucas Vincenzo Davi at the University of Duisburg-Essen for the Cyber Security course in the Summer Semester of 2026. The discussion situates DES within the broader context of cryptography, following previous topics such as modular arithmetic, substitution ciphers, and stream ciphers. DES is classified as a block cipher, and its study encompasses the encryption process, the key schedule (Schlüsselfahrplan), and the decryption mechanism.

Historical Context and Development of DES

The history of DES began in 1972 when the National Bureau of Standards (NBS), now known as the National Institute of Standards and Technology (NIST), issued a call for a standardized encryption algorithm. In 1974, IBM submitted the most promising proposal, based on an algorithm known as a Feistel cipher. Originally, the design intended to encrypt 64-bit blocks using a 128-bit key. However, rumors persisted that the National Security Agency (NSA) influenced the design, specifically by requesting a reduction of the key length to 56 bits. This reduction introduced a vulnerability to brute-force attacks. While there were suspicions of an intentional backdoor within the S-boxes, these claims were never substantiated. DES was officially published as a standard in 1977.

Principles of Confusion and Diffusion according to Claude Shannon

The security of modern block ciphers like DES relies on two fundamental concepts defined by Claude Shannon: confusion and diffusion. Confusion is an operation designed to obscure the relationship between the secret key and the ciphertext; a primary example in DES is the use of substitution tables or S-boxes. Diffusion is an operation that spreads the influence of a single plaintext symbol across numerous ciphertext symbols. This ensures that changing one bit of the plaintext affects many bits of the ciphertext. Bit permutations are the primary examples of diffusion operations. Contemporary block ciphers achieve high security by repeatedly alternating between confusion and diffusion across multiple rounds.

DES Specifications and Technical Parameters

DES is a block cipher that operates on data units of $64\,\text{bits}$. Although it is formally defined with a 64-bit key, the effective key length is only $56\,\text{bits}$. This discrepancy arises because 8 bits are reserved as odd parity bits, meaning every 8th bit is used for error detection rather than security. The encryption process consists of 16 identical rounds. In each round $i$, a unique round key $k_i$ is employed, which is derived from the main 56-bit key through a specific key schedule. The block size remains constant at 64 bits throughout the transformation process, eventually resulting in a 64-bit ciphertext unit.

The Feistel Network Architecture

DES utilizes a Feistel structure, which permits the same algorithm to be used for both encryption and decryption. The process begins with an Initial Permutation (IP), which shuffles the incoming 64 bits of plaintext. The bitstream is then split into two halves: the left half ($L$) and the right half ($R$), each comprising $32\,\text{bits}$. In each of the 16 rounds, the right half ($R_{i-1}$) is passed through a transformation function $f$ alongside a round key $k_i$. The output of this function is then XORed with the left half ($L_{i-1}$) to form the new right half ($R_i$). Meanwhile, the old right half ($R_{i-1}$) becomes the new left half ($L_i$). This swapping occurs in every round except the 16th. After the final round, a 32-bit swap is performed followed by the inverse initial permutation ($IP^{-1}$) to produce the final 64-bit output.

Detailed Mechanics of the Round Function (f)

The internal function $f$ takes a 32-bit input from the right half ($R_{i-1}$) and a 48-bit round key ($k_i$) to produce a 32-bit output. The process involves four distinct steps. First is Expansion ($E$), where the 32-bit input is expanded to $48\,\text{bits}$ by duplicating and repositioning certain bits. This step introduces diffusion because a single input bit can influence multiple S-boxes. Second, the 48-bit expanded result is XORed with the 48-bit round key ($k_i$). This is the stage where the key material is integrated into the data processing. Third, the result is fed into the Substitution Boxes (S-boxes). There are 8 S-boxes, each taking a 6-bit input and producing a 4-bit output ($8 \times 4 = 32\,\text{bits}$). The S-boxes represent the only non-linear component of DES and are the primary source of confusion. Finally, the 32-bit output of the S-boxes undergoes a fixed Permutation ($P$) to further spread the influence of the bits (diffusion) before the XOR operation with the left half.

The S-Box Lookup Process

The S-boxes are identified as the cryptographic core of DES. An example of a lookup in S-box 1 ($S_1$) involves an input of 6 bits. For an input binary value such as $b = 100101_2$ (which is 37 in decimal), the first and last bits ($1$ and $1$) are combined to determine the row (row $11_2 = 3$), and the middle four bits ($0010_2 = 2$) determine the column (column 2, noting that indexing starts at 0). The value at the intersection of the 4th row and 3rd column in the $S_1$ table is then selected. In this hypothetical lookup, the result might be $8$, represented as the 4-bit binary string $1000_2$. Because S-boxes are non-linear, they are essential for resisting mathematical cryptanalysis.

The DES Key Schedule (Schlüsselfahrplan)

The key schedule describes how the 16 round keys ($k_1$ to $k_{16}$) are generated from the initial 64-bit key ($K$). First, the Permuted Choice 1 (PC-1) operation removes the parity bits (every 8th bit) and shuffles the remaining 56 bits. These 56 bits are split into two 28-bit halves, labeled $C_0$ and $D_0$. In each subsequent round, both halves are subjected to one or more cyclic left shifts (the number of shifts depends on the round number). After the shifts, the halves are concatenated and passed through Permuted Choice 2 (PC-2), which selects and shuffles bits to compress the 56 bits into a 48-bit round key ($k_i$). This ensures that a different subset of the key is used in every round.

Decentralization and the Avalanche Effect

A critical property of a secure cipher is the Avalanche Effect. In DES, the combination of the Expansion box, the non-linear S-boxes, and the Permutation $P$ ensures that after the 5th round, every single bit of the ciphertext is a function of every single bit of both the plaintext and the key. This means that a minor change in the input (even a single bit) results in a drastic, unpredictable change in the output ciphertext.

DES Decryption and Symmetry

Decryption in DES is remarkably similar to encryption due to the Feistel network architecture. The same algorithm is used, and the hardware or software implementation remains identical with one major exception: the round keys must be applied in reverse order. While encryption uses keys in the order $k_1, k_2, \dots, k_{16}$, decryption uses them in the order $k_{16}, k_{15}, \dots, k_1$. The decryption process begins by applying the Initial Permutation (IP) to the ciphertext, which effectively reverses the final $IP^{-1}$ of the encryption. The rounds then proceed normally, using the reversed keys to mathematically "undo" the transformations of the encryption rounds.

Security Analysis and Cryptanalysis

While no fundamental mathematical flaws were found in the S-boxes, DES is vulnerable to several types of attacks. Brute-force attacks are the most significant threat today; with a key space of $2^{56}$, modern hardware can break DES in a matter of hours. On average, a successful brute-force search requires testing $2^{55}$ keys. Furthermore, DES exhibits a complement property: if $c_k(x) = y$, then $c_{\overline{k}}(\overline{x}) = \overline{y}$. This observation theoretically reduces the worst-case brute-force effort from $2^{56}$ to $2^{55}$, and the average effort to $2^{54}$.

Two advanced forms of cryptanalysis were also discussed:

1. Differential Cryptanalysis (Shamir and Biham): This method examines how differences in plaintext pairs result in differences in ciphertext pairs. DES was specifically designed (via its S-box configurations) to be resistant to this attack.
2. Linear Cryptanalysis (Matsui and Yamagishi): This method seeks linear approximations of the cipher's internal logic. It requires approximately $2^{47}$ known plaintexts to succeed.

Additionally, DES has four "weak keys" for which the encryption operation is its own inverse, meaning $E_k(E_k(x)) = x$. In such cases, encrypting a block twice with the same weak key returns the original plaintext.

Triple-DES (3DES) and Future Alternatives

To address the short key length of DES without designing an entirely new algorithm, Triple-DES (3DES) was introduced. Triple-DES applies the DES algorithm three times, typically in the Encrypt-Decrypt-Encrypt (EDE) mode: $Ciphertext = E_{k3}(D_{k2}(E_{k1}(Plaintext)))$. This mode allows for backward compatibility with single DES if all three keys are the same ($k1 = k2 = k3$). With three independent keys, the nominal key length is $168\,\text{bits}$ ($3 \times 56$). However, due to the Meet-in-the-Middle attack, Double-DES (using only two DES operations) is not sufficiently secure, as it does not significantly increase effective security over a single DES. Triple-DES provides an effective security level of approximately $112\,\text{bits}$.

Despite its improved security, Triple-DES has significant drawbacks: it is three times slower than DES, inefficient in software, and retains the small 64-bit block size of the original standard. Furthermore, it is not considered long-term secure against quantum computers due to its maximum 168-bit key length. Consequently, while DES and Triple-DES are still used in legacy systems (such as some banking cards and digital IDs), the Advanced Encryption Standard (AES) has largely replaced them as the modern industry standard.