Let’s Set the Standard of Data Encryption

Iterative And Feistel Ciphers

Before we detail how DES works, we need to study 2 important classes of ciphers - Iterative and Feistel Ciphers.

Iterative Ciphers

Iterative Ciphers are also known as round ciphers. In these, encryption/decryption takes place in N rounds. A key K is used to create N sub-keys - K¹, K², K³, …. K^N. The sub-keys are used in each round for encryption in that round. The output of one round is the input to the next round. E.g., the output of round 1 provides the input for round 2, and so on.

Encryption in each round is done by a function g. 

g takes two inputs - the current state w^i-1 (the current partially encrypted text) and the key for the round Kⁱ. 

w⁰ is the original plaintext. 

w¹ is the output of the first round (and the input of the second round). 

w^N is the final output - the cipher text. 

The function g is used to encrypt the data in the following way.

w^r = g(w^r-1,K^r)

The specification of the function g is left to the cipher. Any cipher that follows this format is termed an iterative cipher. 

Feistel Cipher

Feistel Ciphers are special iterative ciphers in which each state wⁱ is divided into two parts - Lⁱ and Rⁱ , of equal length. These are the left and right parts. So, if the block size is 64 bits, Lⁱ and Rⁱ will be 32 bits each. 

The function g in Feistel Ciphers does the following two operations:

Lⁱ = R^i-1

Rⁱ = L^i-1 ⊕ f(R^i-1,Kⁱ)

Where f is left for the cipher to decide. Each cipher can define its own f function. 

Using the function f and the equations described above, we see that the function g took the current state (w^i-1 , divided into two parts L^i-1 and R^i-1), and the round key Kⁱ as inputs. It produced the next state wⁱ (Lⁱ and Rⁱ can be combined to form wⁱ) as output.

One Round of Feistel Encryption

If all this isn't clear, it will become clear when we study DES. 

DES - Data Encryption Standard

The DES extends to the Data Encryption Standard. The NIST(National Institute of Standards and Technology) established it as a standard. IBM developed it. This algorithm uses a 56-bit key to encrypt data of size 64-bit from plaintext into a 64-bit cipher text. The DES consists of 16 rounds of encryption. Since it is a symmetric key algorithm, it uses the same key for encryption and decryption.

History of DES

The given points summarise the history of DES from its inception:

✅ It was initially termed LUCIFER by IBM researchers.

✅ DES is based on the Feistel block cipher named after Horst Feistel.

✅ It uses 16 rounds of the Feistel cycle with a different key in each round.

✅ DES was first published in the Federal Register on 17 March 1975.

✅ Initially, it was expected that DES would last for 10-15 years, but it lasted much more than that. It was renewed as the official standard for encryption in 1999.

✅ The NSA (National Security Agency) of the USA was involved in its development, which raised questions about its security and the possible presence of backdoors.

✅ It is currently not recommended and has been shown to be vulnerable to brute-force attacks.

DES is a 16-round Feistel cipher having a block length of 64 bits. It encrypts a plaintext of length 64 using a 56-bit key to get a ciphertext of length 64.

The flowchart for DES looks like this. 

Let's go through all the steps of the DES algorithm. You will need to know about Permutations and Substitutions, so if you don't already know - go through our article on Substitution and Permutation Networks (SPN) in Cryptography. 

Initial and Final Permutation

We are discussing these steps together because they are logically the same, even if they occur at different stages. 

The 64 bits are put through a permutation in the initial permutation step. The permutation rule is predefined and fixed. The final permutation step is simply the inverse of the initial permutation. For example, in the initial permutation - the 58th bit is brought to the 1st bit position. In the final permutation, the 1st bit is moved to the 58th position. 

The permutation rules are shown here. 

The initial permutation is used to produce the input in the following way:

L⁰R⁰ = Initial Permutation of Plaintext

The final ciphertext is produced using the ciphertext in the following way. 

Ciphertext = Final permutation of R¹⁶L¹⁶ 

Notice that we have swapped L¹⁶ and R¹⁶ before applying the final permutation. The initial and final permutation steps don't have any cryptographic effect on DES, i.e., they don't provide any extra security. 

Subkey Generator Algorithm

Let's see how DES converts a 56-bit key into sixteen 48-bit subkeys. This is done with the subkey generator algorithm, also called the key scheduling algorithm or the round key generator algorithm. 

The algorithm works in 16 rounds since it has to produce 16 subkeys. The output of each round is used as the input of the next round. The input to the first round is the original 56-bit key.

1. In each round, the 56-bit input is split into two 28-bit parts. 
    
2. Each 28-bit is circularly shifted left by 1 or 2 bits. In rounds 1,2,9, and 16 - one bit is shifted. In all other rounds, 2 bits are shifted. 
    
3. Out of the 56 bits so produced, 48 are selected and permuted.  Some bits will be dropped. 
   The selection and permutation happen according to this table, termed a D-box. 

You can see that some bits (such as bit-18) have been dropped. There were 56 inputs, but the size of the box is 48. These 48 cells of the box are taken in order as the 48-bit subkey for this round.

The flowchart for Subkey Generation looks like this.

Rounds

The central part of DES is the 16 encryption rounds. Let us see how they take place. The following steps occur for each round - i.e., 16 times. 

1. Each round gets two 32-bit data - L^i-1 and R^i-1, the outputs of the previous round. The round also gets the round key Kⁱ.
2. As DES is a Feistel Cipher, we follow the rules of Feistel Ciphers:

Lⁱ = R^i-1

Rⁱ = L^i-1 ⊕ f(R^i-1,Kⁱ)

3. The f function gets 2 inputs - R^i-1 (32-bit) and Kⁱ (the 48-bit round key). To allow us to do operations on them, we need to make them the same size. 
Therefore, we expand R^i-1 to 48-bits using an Expansion Box E. This process is called Expansion-Permutation, as the bits are also permuted. 16 of the original bits are repeated. 
The permutation box E looks like this.

You can see multiple bits are repeating. This is necessary to get to 48 bits.

4. The output of the expansion box - E(R^i-1) is XORed with the 48-bit round key Kⁱ to produce a 48-bit output. Let's call this output B. 

B = E(R^i-1) ⊕ K

5. B is written as the concatenation of eight 6-bit strings. 

B = B₁B₂B₃B₄B₅B₆B₇B₈

6. DES uses 8 S-boxes that convert a 6-bit input to a 4-bit output. The S-boxes are tables for which we need both a row and a column to find the output. The S-boxes have 4 rows and 16 columns.

For a 6-bit input - the concatenation of the 1st bit and the 6th bit decides the row number. 
The concatenation of the 2nd,3rd,4th, and 5th bit decides the column number. 
Let's see with an example. 
Consider the S-box given below. Let's take our 6-bit input as 101110.

The row number is decided by the 1st and 6th bit - 1 and 0 - which make 10. 
10 in binary means 2 - which means we need to look in the second row.

The 2nd,3rd,4th, and 5th bits are - 0111, which is 7. 

So, we need to look at the 2nd row (1) and the 7th column (6) - the output will be 13.
13 in binary is 1101.
Thus, we see that our 6-bit input has been converted to 4-bits. Let the output of converting B_i be C_i. 

7. The conversion using S-boxes is done for B₁, B_2,…. B₈ - producing outputs C₁,C₂, …. C₈. 
Let the concatenation of the outputs be C.

C = C₁C₂C₃C₄C₅C₆C₇C₈

8. C is the final output of the function f. 

The above figure shows one round in DES. The function f is as described above. The steps shown in the figure above are repeated 16 times for 16 rounds. The final output is put through the final permutation step (as already discussed), which produces our final ciphertext.

Analysis of DES

The following points give a critical analysis of the DES:

❄️ When DES was proposed as an encryption standard, it attracted a lot of criticism, mainly regarding the S-boxes.

❄️ The S-boxes were the only non-linear components of the cryptosystem and thus became critical for security.

❄️ People argued that the DES contained “trapdoors” and that the National Security Agency could easily decrypt messages.

❄️ In reality, the S-boxes were designed to withstand the differential attacks on DES, making the differential cryptanalysis attacks tough to execute.

❄️ Another criticism around DES was that it contained a keyspace of size 2^56, which is pretty small, especially compared to its predecessor, the LUCIFER.

❄️ The reason IBM gave for this reduction was that eight parity check bits were used and the rest 56 for storage. However, it is known that the NSA was the one to convince them to reduce the key length to 56 bits. This has caused some people to speculate about the actual reason for reducing the key length.

❄️ Other than exhaustive key search, differential and linear cryptanalysis are the two most famous attacks on DES. However, they are not thought to be practical. In practice, brute-force search has been found to be the most efficient. 

Applications of DES

Let's look at some of the critical use cases of DES:

💡It is used when encryption of a not-so-high standard is needed.

💡It is used for random number generation.

💡It is used to develop the Triple DES ( a 168-bit key using three keys), which provides a higher amount of security and is approved for use by NIST until 2030. 

💡Even though it is not currently used for security purposes, DES has provided the basis behind many modern ciphers, such as CAST, Blowfish, IDEA, etc.

Frequently Asked Questions

What is Differential Cryptanalysis, and why is DES resistant to it?

Differential Cryptanalysis is a method to attack ciphers and find the key used without knowing it beforehand. DES is resistant to it because the authors of DES knew about it secretly before the technique was released openly. They specifically designed the S-boxes to be resistant to it.

If DES is not recommended anymore, what is the current standard for encryption?

DES has been replaced by AES (Advanced Encryption Algorithm) as the current standard for encryption. It is the most secure and recommended algorithm for use as of today.

If the initial and final permutation rounds of DES don't provide any security, why are they used?

It is unclear as to why they have been used. It is theorized that the authors wanted to implement DES directly on hardware, and such expensive computations would ensure that no one imitated it using software, since software at the time was computationally expensive.

Conclusion

This blog has shed light on Data Encryption Standard. It is a sophisticated encryption algorithm that gave the basis to the ciphers widely used in today's world. We learned about the class of ciphers DES belongs to, the history of DES, its inner workings, analysis, and applications.

Check out other related articles to learn more:

• 💡What is Cryptography?
• 💡Cryptography digital signature.
• 💡Cryptography hash function

And many more on our platform Coding Ninjas Studio.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!