Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
History of AES
3.
Description of AES
3.1.
Add-RoundKey
3.2.
SubBytes
3.3.
ShiftRows
3.4.
MixColumns
4.
AES Key Schedule
4.1.
Word
4.2.
RotWord
4.3.
SubWord
4.4.
RCon
4.5.
Algorithm
5.
Analysis of AES
6.
Frequently Asked Questions
6.1.
Why does AES have different key lengths?
6.2.
Does Rcon have 10 elements for 192-bit and 256-bit keys too?
6.3.
Does increasing key size mean the algorithm is automatically more secure?
7.
Conclusion
Last Updated: Mar 27, 2024
Hard

Advancing the Data Encryption Standard

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

Introduction

As we know, in the modern age, everything has become digital. From communication to storage to financial transactions - we use computers for everything. Thus, it becomes imperative to ensure that data does not fall into the wrong hands. Encryption is used to protect our data from unauthorized access.

Advancing the Data Encryption Standard

Advanced Encryption Standard, or AES, is the current standard for encryption in the world. It is highly secure and used by organizations worldwide for encrypting their data. Let us learn all about it. 

History of AES

Before AES, the encryption standard of the world was DES (Data Encryption Standard). You can learn more about it by reading our article on it - Let’s Set the Standard of Data Encryption. 

However, DES soon became vulnerable to brute-force attacks on its keys. Thus we needed a new standard. The U.S. National Institute of Standards and Technology (NIST) launched a public competition in 1997 to find a replacement for DES. The replacement would be called Advanced Encryption Standard, or AES. They required the candidate ciphers to meet the following requirements. 

  • Have a block length of 128.
     
  • Support key lengths of length- 128,192, and 256 bits
     
  • Be available for worldwide use without any royalty.
     

21 ciphers were submitted, and 15 met the requirements. On October 2, 2000, Rijndael was selected to become the AES. It was adopted as a standard a year later. NIST chose it because of its:

  • Security
     
  • Cost (speed and memory cost)
     
  • Algorithm and Implementation Characteristics (flexibility and simplicity)
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

Description of AES

Let us see the steps that AES uses to encrypt data. AES is a symmetric encryption algorithm, which means it uses the same key for encryption and decryption. We will outline the encryption algorithm below - the decryption algorithm is the same but performed in reverse. 

  • AES has a block length of 128. The key lengths can be 128,192 or 256. 
     
  • AES uses iterated encryption with N rounds.
     
    • For 128-bit keys, N=10.
       
    • For 192-bit keys, N=12.
       
    • For 256-bit keys, N=14.
       
  • AES performs all its operation on a State variable. The state is represented as a 4x4 matrix. Each entry in the matrix is a single byte. This makes 16 bytes, or 128 bits, which is our block size.
     

The following flowchart gives an overview of AES. We will see all the steps in detail in the upcoming sections.  

Flowchart of AES - Overview

Let's see the various steps mentioned. 

  1. In the initialization step, the State variable is initialized to the plaintext. We perform the Add-RoundKey step. 
     
  2. For the first N-1 rounds, we perform SubBytes ( a substitution using an S-box). We perform ShiftRows (A permutation step), followed by MixColumns, and then Add-Round Key.
     
  3. In the last round, SubBytes, ShiftRows, and Add-RoundKey are performed. The final value of State is said to be the ciphertext.
     

Let's now see the various operations used.

Add-RoundKey

In the Add-RoundKey step, the RoundKey (128-bit no matter what the original key length is) is XORed with the State variable. 

SubBytes

SubBytes is a substitution step. It uses a Substitution box to convert all entries in the State variable. The S-box adds non-linearity to the algorithm, preventing attacks such as Linear Cryptanalysis. 
 

The S-boxes in DES were seemingly random. But the S-boxes in AES are derived from finite fields and affine transformations. These topics are beyond the scope of this article. These mathematical functions prevent simple algebraic attacks. The S-box is given below. 

AES S-box

Transformation of a byte using the S-box uses the following steps:

  • Write the byte in hexadecimal notation. 8 bits in hexadecimal form will form 2 letters. 
     
  • The first letter is used to decide the row, and the second byte is used to decide the column.
     
  • For example, to transform a byte 10100110:
    • Convert it to hexadecimal - A6.
       
    • We will see row no A of the S-box and column number 6.
       
    • After conversion, the byte will be 24, or 00100100 in binary.

ShiftRows

In this step, we shift the elements in each row of State by some steps.

  • The first row is left as it is. 
     
  • The elements of the second row are shifted circularly one step to the left. 
     
  • The elements of the third row are shifted 2 steps to the left. 
     
  • The elements of the fourth row are shifted 3 steps to the left. 
Shift Rows Diagrammatic View

This step ensures that the 4 columns are not encrypted separately. If this were excluded, AES would just be encrypting the 4 columns one by one independently of each other. This would reduce security and make AES easier to break. 

MixColumns

In this step, we perform matrix multiplication. However, this is not the usual matrix multiplication. 

As you may recall, multiplying matrices involves multiplication as well as addition. 

For AES, the multiplication is performed as multiplication in a particular finite field. XOR replaces the addition step. The details have been left as they are beyond the scope of this article. 

MixColumns matrix multiplication

Where A1, A2,A3, A4 represent the elements of a column of State. This operation is performed for all columns one by one. 

AES Key Schedule

We've seen all the steps of the rounds in AES. Let's see how AES creates multiple subkeys from a single key. Before we see the key schedule algorithm, let's see some terms and operations. We will see the key schedule for a 128-bit key. The steps for 192 and 256-bit keys are similar. 

Word

A word consists of 4 bytes or 32 bits. The key scheduling algorithm of AES works on words. It produces 16-byte round keys, or 4-word round keys. 

RotWord

RotWord is an operation used in the key scheduling algorithm. RotWord simply shifts a word to the left circularly. 

RotWord(A1,A2,A3,A4) = (A2,A3,A4,A1)

SubWord

SubWord simply applies the AES S-box (that we saw above), to each of the 4 bytes in a word.

RCon

RCon is an array of 10 words. These are constants, defined below.

  • RCon[1]  =  01000000 
     
  • RCon[2]  =  02000000 
     
  • RCon[3]  =  04000000 
     
  • RCon[4]  =  08000000 
     
  • RCon[5]  =  10000000 
     
  • RCon[6]  =  20000000 
     
  • RCon[7]  =  40000000 
     
  • RCon[8]  =  80000000 
     
  • RCon[9]  =  1B000000 
     
  • RCon[10]  =  36000000
     

Algorithm

We have 10 rounds, each of them requires a key. Additionally, the initialization step also requires a round key. So, we need 11 round keys in total, each of 16 bytes (4 words). 

Hence, we need a total of 44 words. 

The algorithm returns an expanded key, which is an array of those 44 words. The expanded key is a concatenation of all the round keys. 

Let w be the final expanded key, with w[i] representing the ith word of the expanded key. Thus, w has a length of 44. w1,w2,w3,w4 make up a single round key, similarly, for w5,w6,w7,w8, and so on.

The algorithm to construct w is as follows. It is presented as pseudocode.

for (i=0 to 3):
w[i] = (key[4i], key[4i + 1], key[4i + 2], key[4i + 3])
for (i=4 to 43):
temp = w[i-1]
if (i%4==0):
temp = SubWord(RotWord(temp)) ⊕ RCon[i/4]
w[i] = w[i-4] ⊕ temp
return (w[0], w[1]....... w[43])

Analysis of AES

  • Currently, AES is secure against all known attacks. 
     
  • AES is the only publicly available algorithm that the US National Security Agency (NSA) has approved for encrypting top-secret information. Top-secret is the highest level of confidentiality in the US. 
     
  • There have been some attacks created against versions of AES that use fewer rounds than specified, such as related-key attacks. However, most of these are unrealistic in practice and only hold academic significance.
     
  • All known attacks against  AES would take too much time, too much storage, or both, and hence are not practically feasible. 
     
  • According to leaked information, the NSA is doing research on how to break AES using Tau Statistics. 

Frequently Asked Questions

Why does AES have different key lengths?

AES supports different key lengths because some things require different levels of security. For top secret information, 192 or 256-bit encryption is used. For information that is run on low-power hardware and does not need extreme security, we can use the 128-bit version.

Does Rcon have 10 elements for 192-bit and 256-bit keys too?

No, for longer key lengths, RCon also has more elements. The key schedule algorithm we specified was for 128-bit keys. RCon is an operation in a key schedule algorithm. It is an array of 10 words. 

Does increasing key size mean the algorithm is automatically more secure?

No, this is not true. While generally, longer keys mean more security, many algorithms with a good key length have been broken due to other faults. That means increasing key size does not guarantee a more secure system.

Conclusion

This blog has explored AES or Advanced Encryption Algorithm. We saw the history behind it, and how it came to be the standard for encryption in the modern world. We discussed its working in detail. All major governments and private organizations use AES to encrypt data. It is secure against all known attacks.

If you liked this article, check out our other articles on Cryptography:

You can practice questions on various problems on Coding Ninjas Studio, attempt mock tests. You can also go through interview experiences, interview bundle, go along guided paths for preparations, and a lot more!

Keep coding, keep reading Ninjas. 

Previous article
Let’s Set the Standard of Data Encryption
Next article
Introduction to Modes of Operations
Live masterclass