Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Block And Stream Ciphers
2.1.
Block Ciphers
2.2.
Stream Ciphers
3.
Iterative And Feistel Ciphers
3.1.
Iterative Ciphers
3.2.
Feistel Cipher
4.
DES - Data Encryption Standard
4.1.
History of DES
4.2.
Initial and Final Permutation
4.3.
Subkey Generator Algorithm
4.4.
Rounds
5.
Analysis of DES
6.
Applications of DES
7.
Frequently Asked Questions
7.1.
What is Differential Cryptanalysis, and why is DES resistant to it?
7.2.
If DES is not recommended anymore, what is the current standard for encryption?
7.3.
If the initial and final permutation rounds of DES don't provide any security, why are they used?
8.
Conclusion
Last Updated: Mar 27, 2024
Hard

Let’s Set the Standard of Data Encryption

Author Satvik Gupta
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Having standards while dealing with any situation, process or technology is crucial. These standards define the quality of work or output achieved. While we are learning cryptography, it is essential to know encryption standards. The Data Encryption Standard came into existence in 1973 when the National Institute of Standards and Technology (NIST) published a solicitation in the Federal Register.

Let’s Set the Standard of Data Encryption

In this blog, we will learn about the class of ciphers DES (Data Encryption Standard) belongs to, its features, and working, and finally, we will go through a deep analysis of DES.

Block And Stream Ciphers

Most modern ciphers can be divided into two types - block and stream

Block Ciphers

These ciphers' plaintext (text to be encrypted) is divided into fixed-size blocks. Typical block sizes include 64-bits, 128-bits, and 256-bits, although theoretically, we can use any size. Blocks are encrypted or decrypted one at a time.

Stream Ciphers

In these ciphers, a keystream is constructed from the initial key. The length of the keystream should at least be equal to the length of the plaintext. The ciphertext is calculated by performing an exclusive-or (XOR) operation of the plaintext and the keystream. The plaintext is calculated using the reverse - XOR of the ciphertext and the keystream. 

To read more about the block and stream ciphers and their differences, you can refer to our article - How are Block Ciphers Different From Stream Ciphers?

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 - K1, K2, K3, …. KN. 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

takes two inputs - the current state wi-1 (the current partially encrypted text) and the key for the round Ki

w0 is the original plaintext. 

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

wN is the final output - the cipher text. 

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

wr = g(wr-1,Kr)

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 wi is divided into two parts - Li and R, of equal length. These are the left and right parts. So, if the block size is 64 bits, Land Rwill be 32 bits each. 

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

Li = Ri-1

Ri = Li-1 ⊕ f(Ri-1,Ki)

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 took the current state (wi-1 , divided into two parts Li-1 and Ri-1), and the round key Ki as inputs. It produced the next state wi (Li and Rcan be combined to form wi) as output.

One Round of Feistel Encryption

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. 

Flowchart for DES

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. 

Initial and final permutation

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

L0R0 = Initial Permutation of Plaintext

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

Ciphertext = Final permutation of R16L16 

Notice that we have swapped L16 and R16 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. 
Compression Permutation 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.

Subkey Generation Flowchart

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 - Li-1 and Ri-1, the outputs of the previous round. The round also gets the round key Ki.
  2. As DES is a Feistel Cipher, we follow the rules of Feistel Ciphers:

Li = Ri-1

Ri = Li-1 ⊕ f(Ri-1,Ki)

3. The f function gets 2 inputs - Ri-1 (32-bit) and Ki (the 48-bit round key). To allow us to do operations on them, we need to make them the same size. 
Therefore, we expand Ri-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.

Expansion Permutation E box

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

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

B = E(Ri-1) ⊕ K

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

B = B1B2B3B4B5B6B7B8

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.

S box

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 Bi be Ci

7. The conversion using S-boxes is done for B1, B2,…. B8 - producing outputs C1,C2, …. C8
Let the concatenation of the outputs be C.

C = C1C2C3C4C5C6C7C8

8. C is the final output of the function f

One round of DES


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 256, 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:

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!

Previous article
How to launch a linear attack on an SPN?
Next article
Advancing the Data Encryption Standard
Live masterclass