Advanced Encryption Stadard (AES)

Table of contents

1. Definition
2. Reference
3. Deep Dive

---

Definition

Advanced Encryption Standard (AES) is the encryption standard set by the U.S. National Institute of Standards and Technology (NIST) in 2001, which is a type of symmetric cryptography. It means that the two objects have the same secret key that should not be revealed to attackers. AES is devised firstly by two Belgian cryptographers, Joan Daemen and Vincent Rijmen, who submitted a proposal to NIST. In this proposal, they proposed ‘Rijndael’ algorithm that is a family of ciphers with different key and block sizes. AES is widely used today as it is a much stronger than DES and triple DES despite being harder to implement. In the past, older encryption methods were sufficient for protecting sensitive information, but they no longer meet today’s security needs. That’s where AES encryption comes in. AES offers a high level of security and has become the go-to choice for encrypting sensitive data.

Reference

Please refer to the listed reference below. That help you understand what is AES.

• Blcok Cipher Mode
• Plaintest Wikipedia
• Ciphertext Wikipedia
• AES Lecture Note Purdue
• Substitute Bytes Transformation
• Multiplicative Inverse Wikipedia
• AES Basic
• Animated AES Encryption Steps
• Galua Field Lecture - Kor
• Multiplecative Inverse and how to extract S-Box Table
• How to calculate Mix Column-Kor
• AES Explanation from Microchip
• AES Step By Step Hands On

Deep Dive

1. Advanced Encryption Stnadard (AES)
   • In this chapter, we will take a look at AES128-CBC (Cipher Block Changing) and AES128-ECB (Electronic codebook) which are used widely.
   • AES has several mode according to specific formulas which is used in encryption process as shown in [Pic.1]

   
   [Pic.1] AES Mode

   • AES supports a couple of different key size that has different rounds. The main difference of using different key is how you generate the key schedule from the key. See the table below.

     Rounds	Key Size
     10 rounds	128-bits
     12 rounds	192-bits
     14 rounds	256-bits

   • Except for the last round in each case, all other rounds are identical.
   • In terms of computation, we normally use ‘Matrix’ as consisting of a 4x4 arrays of bytes as shown in [Pic.2]

   
   [Pic.2] AES128 Matrix Notation

   • Note that the first four bytes of a 128-bit input block occupy the first column in the 4 × 4 array of bytes. The next four bytes occupy the second column, and so on.

   The 4 × 4 array of bytes shown above is referred to as the state array in AES!!

   • AES also has the notion of a word. A word consists of four bytes, that is 32 bits (8 bits x 4). Therefore, each column of the state array is a word, as is each row.
   • Each round of processing works on the input state array and produces an output state array.
   • The output state array produced by the last round is rearranged into a 128-bit output block.
   • Unlike DES, the decryption algorithm differs substantially from the encryption algorithm. Although, overall, very similar steps are used in encryption and decryption, their implementations are not identical and the order in which the steps are invoked is different, as mentioned previously.
   • AES is an iterated block cipher in which plaintext is subject to multiple rounds of processing, with each round applying the same overall transformation function to the incoming block. [Pic.3] will help you understand how AES processing work.

   
   [Pic.3] AES128-CBC Mode Encryption

   • AES is a type of key-alternating block ciphers. In such ciphers, each round first applies a diffusion-achieving transformation operation, which is a combination of linear and nonlinear steps, to the entire incoming block, which is then followed by the application of the round key to the entire block.
   • About the security of AES, considering how many years have passed since the cipher was introduced in 2001, all of the threats against the cipher remain theoretical — meaning that their time complexity is way beyond what any computer system will be able to handle for a long time to come.
   • AES was designed using the wide-trail strategy.
2. AES Encryption KEY
   • Key is input parameter of AES encryption and decryption processing. As shown in [Pic.2], the size of Key shall be 128 bits. For the compuration processing, KEY is also arranged in the form of an array of 4 × 4 bytes. Just think about that, from the computation of matrix, a input plain text and key should have same form.
   • The four column words of the key array are expanded into a schedule of 44 words as shown in [Pic.4] (Kn represents a word).

   Note that the reason of this expansion is that AES128-CBC conducts 10 rounds and each round consumes four words from the key schedule. Thus, the resulting size of this expansion shall be 40 word. For the first 4 words of 44 words, they are used for adding to the input state array before any round-based processing can begin. This 4 words is called Initial Vector. And the remaining 40 words used for the ten rounds of processing that are required for the case a 128-bit encryption key.

   
   [Pic.4] AES128 KEY Expansion

3. Overall Structure of AES128-CBC Processing
   • AES Computation structure of Encryption and Decryption is shown in [Pic.5].
   • The input state array is XORed with the first four words of the key schedule.
   • The same thing happens during decryption — except doing XOR the ciphertext state array with the last four words of the key schedule.

   
   [Pic.5] AES128 Encryption Processing Structure

   • AES128 Encryption and Decryption step are decribed in the table below from programming perspective. Each round has 4 steps excpet the last round.

     Step	Encryption	Decryption
     1st	Substitue Bytes Transformation	Inverse Shift Rows
     2nd	Shift Rows	Inverse Substitue Bytes Transformation
     3rd	Mix Columns	Add round key
     4th	Add round key	Inverse Mix Columns

   The last round for encryption does not involve the “Mix columns” step. The last round for decryption does not involve the “Inverse mix columns” step.

   1. Encryption
      • Step 1: Substitue Bytes Transformation
        • The Substitute Bytes transformation, also known as the “SubBytes” or “S-Box” operation, is a nonlinear substitution operation that replaces each byte in the input data with a corresponding byte from a fixed substitution table called the “S-Box.
        • The S-Box is a predefined, constant table (Look up table) containing 256 entries, each 8 bits in length. The S-Box is carefully designed to introduce non-linearity and confusion into the data, making it resistant to various cryptographic attacks, such as differential and linear cryptanalysis.
        • The S-Box is a fixed, publicly known component of the AES algorithm and serves to obscure the relationship between the input and the output, making it more challenging for attackers to deduce patterns or information about the encrypted data. S-Box (Look Up Table) is implemented with GF(2^8) and bit scrambling.
        • The SubBytes transformation helps in achieving the confusion and diffusion properties required for a strong encryption algorithm.
        • Confusion ensures that the relationship between the key and the ciphertext is complex, making it difficult to analyze, while diffusion ensures that changes in one part of the plaintext affect a large part of the ciphertext.
        • Thus, The goal of the substitution step is to reduce the correlation between the input bits and the output bits at the byte level.

        The bit scrambling part of the substitution step ensures that the substitution cannot be described in the form of evaluating a simple mathematical function.

        
        [Pic.6] S-Box Look Up Table in GF(2^8)

        • When we extract the S-Box Look Up table, we apply Multiplicative Inverse (MI) and bit scrambling based on the resulting MI.
        • The specific calucation of MI and Bit Scrambling can be found at [Multiplecative Inverse Cal] and AES Lecture Note Purdue repectively
      • Step 2: Shift Rows
        • Animated-Shift Rows can be found in [AES Animation Explanation]
        • The rule of shift rows is as follows.
          • Not shifting the first row of the state array at all.
          • Circularly shifting the second row by one byte to the left.
          • Circularly shifting the third row by two bytes to the left.
          • Circularly shifting the last row by three bytes to the left
      • Step 3: Mix Columns
        • This step operates on the State column by column. Each column is treated as a vector of bytes and is multiplied by a fixed matrix to get the column for the modified State.
        • The fixed Matrix for Mix Colums step is shown in [Pic.7].

          
          [Pic.7] Fixed Matrix in GF(2^8)

        • A column of a stat matrix is multiplied by the fixed matrix as shown in [Pic.8].

          
          [Pic.8] Mixed Column Step Equation in GF(2^8)

        Note that The additions are merely XOR operations in the AES world. Note that, when you compute ‘mutiply’ matrixs, we should consider the range of galois field GF(2^8) of each element. If the result go beyond the GF, we need to compute ‘mod’ computation. See [Pic.9] as an example

        
        [Pic.9] Multiplication in GF(2^8)

      • Step 4: Add round key
        • Feed the encrypted output from n round cipher block to the next round plain text (actually do XOR computation between these two inputs ot the next cipher block)
        • [Pic.3] above will help you understand this step.
      • Key Expansion Algorithm
        • The AES Key Expansion algorithm is used to derive the 128-bit round key for each round from the original 128-bit encryption key.
        • We will get the initial key of 128-bits. The first four bytes of the first column of the encryption key constitute the word w0, the next four bytes the word w1, and so on. See [Pic.10].

        
        [Pic.9] Key Expansion Fist Step

        • The words [w0, w1, w2, w3] are bitwise XOR’ed with the input block before the round-based processing begins.
        • The remaining 40 words of the key schedule are used fourwords at a time in each of the 10 rounds.
        • [Pic.11] illustrate how to excute key expansion algorithm from the initial key. In this picture, the function ‘g’ consists of the follwing steps. The return value from g function is only utilized, when calculation the first word of a each word group (i.e., w4, w8, w12, w16 …)
          • Step 1: Perform a one-byte left circular rotation on the argument 4-byte word.
          • Step 2: Perform a byte substitution for each byte of the word returned by the previous step by using the same 16 × 16 lookup table as used in the SubBytes step of the encryption rounds.
          • Step 3: XOR the bytes obtained from the previous step with what is known as a round constant. The round constant is a word whose three rightmost bytes are always zero. Therefore, XOR’ing with the round constant amounts to XOR’ing with just its leftmost byte.
          • As an example of the follwing first word of a each group, it shall be w4 = w0 XOR g(w3)
          • The remaining 3 words of each word group will be calculated by follwing [Pic.11]

        
        [Pic.11] Key Expansion Processing Step

      • You can get high level intution of the entire process of AES encryption in [Pic.12].

      
      [Pic.12] AES Block Cipher Process

   2. Decryption
      • The decryption process is a straightforward reverse of the encryption algorithm as shown in [Pic.13]. Let’s take a look at the corresponding reverse steps.

      
      [Pic.13] AES Decryption Flow Chart

      • Step 1: Inverse Shift Rows
        • For encryption, we did the circularly left-shifting by 0, 1, 2, and 3 for each row. For decryption, we do the circularly right-shifting by 0, 1, 2, and 3
      • Step 2: Inverse Substitue Bytes Transformation
        • For InvSub, we utilize another look up table as shown in [Pic.14], which is called ‘Inverse S-Box’.

        
        [Pic.14] S-Box for Decryption

      • Step 3: Add round key
        • XOR computation with a key and a encrypted input.
      • Step 4: Inverse Mix Columns
        • This step is exactly the inverse process of MixColumns used for encryption. It performs a matrix multiplication of the state with a static matrix.