Encryption Algorithms — Decrypted!
What is encryption? Why do we use it?
Encryption is a method by which plain readable text or data is converted into an encoded text, that can only be decoded or converted back into readable text by another person with access to a decryption key. This is usually done so that important data remains inaccessible to unauthorized users to help protect private information, sensitive data, and enhance the security of communication between client apps and servers.
How to encrypt data?
Now that the importance of encryption has been enumerated, we will learn how to encrypt data. An encryption key uses an ‘encryption algorithm’ to perform the process of encryption, usually called a cipher.
The encryption algorithm is of two types: symmetric and asymmetric key algorithms.
With ‘symmetric key algorithm’, both encryption and decryption keys are the same, so the same key must be used to enable secure communication. Symmetric algorithm encryptions are commonly used for bulk data encryption and are fast and easily implemented by hardware. The downside is that anyone with that decryption key can decrypt your data even if it is not intended for them.
Two of the most important symmetric key algorithms widely used are — Data Encryption Standard (DES) and Advanced Encryption Standard (AES).
DES is a symmetric block cipher with a key length of 56-bits, while AES is a more mathematically efficient and elegant cryptographic algorithm, with an option for choosing 128-bit, 192-bit or 256-bit key, making it exponentially stronger than the 56-bit key of DES.
In asymmetric key algorithm encryption, two separate but mathematically linked encryption keys are used. A public key is used to encrypt the data and can be distributed while the private key is used to decrypt the data and, therefore, is kept private.
Through the use of a private key, asymmetric encryption eliminates the preliminary exchange of secret keys, allows for public keys to be shared with anyone, and provides an underlying architecture for digital certificates, digital signatures, and a Public Key Infrastructure (PKI). The disadvantages are that it is slower than symmetric algorithm encryption and that it requires greater computation power.
This article aims to briefly explain the steps involved in encryption and decryption using AES and DES. In the last section, we shall further venture into how AES could provide the necessary security that DES failed to.
What is the DES algorithm?
The DES (Data Encryption Standard) algorithm is basically a symmetric-key block cipher created in the early 1970s based on the Feistel Structure. The algorithm takes plain text in 64-bit blocks as input and converts them into ciphertext using 48-bit keys.
Why the Feistel Structure?
A modern block cipher is typically used to replace a block of N bits from plaintext with a block of N bits from the ciphertext. Let us consider an example for N = 4: With 4-bits, there are 16 different possible patterns (The bit pattern 0000 represents integer 0, the bit pattern 0001 represents integer 1, and so on).
For an ideal block cipher, the relationship between input and output blocks must be random and invertible, and must thus be a one-to-one function of input block mapped to a unique output block.
Now, if we consider 64-bit block encryption, each possible input block can be thought to consist of 2⁶⁴ integers and for each such integer, a 64-bit output block. Thus, the size of the encryption key will be of size 64 × 2⁶⁴ ≈ 10²¹.
This size of the encryption key would make the above idea impractical. Thus, the Feistel structure was introduced to solve this problem.
Implementing DES algorithm — the Feistel structure
The DES algorithm for encryption and decryption is based on the Feistel Structure.
A cryptographic system based on Feistel structure uses the same basic algorithm for both encryption and decryption. It consists of multiple rounds of processing of the plaintext, with each round consisting of a substitution step followed by a permutation step. The input block to each round is divided into two halves with L and R, denoting the left half and right half respectively.
The algorithmic implementation of DES is known as the Data Encryption Algorithm(DEA). The following figure shows a single round of processing in DEA consisting of the following major steps:
- Key transformation
- Expansion permutation
- S-Box permutation
- P-Box permutation
- XOR and swap
For decryption, the same algorithm is used with the order of the 16 round keys reversed.
DES encryption was broken in 1999 by Electronics Frontiers Foundation, introducing the need for a better algorithm.
What is the AES algorithm?
AES is a slight variation of the Rijndael cipher invented by two Belgian cryptographers Joan Daemen and Vincent Rijmen in 2000. It is a block cipher with a block length of 128 bits. It allows for three different key lengths: 128, 192, or 256 bits. Encryption consists of 10 rounds of processing for 128-bit keys, 12 rounds for 192-bit keys, and 14 rounds for 256-bit keys, where except for the last round in each case, all rounds are identical.
In this section, the key length is taken to be 128 bits, and thus there would be 10 rounds of processing.
Each round of processing includes one single-byte based substitution step, a row-wise permutation step, a column-wise mixing step, and the addition of the round key.
Implementing AES cipher
We consider the 128-bit block to be a 4 × 4 array of bytes, arranged as follows:
Notice that the first four bytes of the 128-bit input block occupy the first column in the array, the next four bytes occupy the second column, and so on.
This 4 × 4 array of bytes is referred to as the state array in AES.
There is another common useful term associated with AES: word.
A word consists of four bytes (32 bits). Hence, each column of the state array is a word, as is each row. The output state array obtained after the final step is rearranged into a 128-bit output block again.
Steps involved for encryption
The input state array is first XORed with the first four words of the key schedule. It is then continued to the subsequent steps: Each round consists of the following four steps:
- Substitute bytes
- Shift rows
- Mix columns, and
- Add round key.
The last step consists of XORing the output of the previous three steps with four words from the key schedule.
Step 1: Substitute bytes for the encryption chain
Let xᵢₙ be a byte of the state array for which we seek a substitute byte xₒᵤₜ. We can write xₒᵤₜ = f(xᵢₙ). The function f() involves two nonlinear operations:
(i) Finding the multiplicative inverse x′ = xᵢₙ−1 in GF(28 ), and then
(ii) Scrambling the bits of x′ by XORing x′ with four different circularly rotated versions of itself and with a special constant byte c = 0x63. The four circular rotations are through 4, 5, 6, and 7-bit positions to the right. This bit scrambling step can also be expressed by the relation: xₒᵤₜ = A · x ′ + c.
Step 2: Shifting rows
The ShiftRows transformation consists of
- 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, and
- circularly shifting the last row by three bytes to the left.
Now, we can imagine how the array representation of the state array is paramount.
This operation on the state array can be represented by
Recall that the input block is written column-wise (The first four bytes of the input block fill the first column of the state array, the next four bytes the second column, etc). As a result, shifting the rows in the manner indicated scrambles up the byte order of the input block.
Step 3: Mixing columns
Each byte of a column is replaced by a function of all the bytes in the same column such that: Each byte in a column is replaced by two times that byte, plus three times the next byte, plus the byte that comes next, plus the byte that follows. The words ‘next’ and ‘follow’ refer to bytes in the same column, and their meaning is circular, in the sense that the byte that is next to the one in the last row is the one in the first row.
For the bytes in the first row of the state array, this operation can be stated as
For the bytes in the second row of the state array, this operation can be stated as
For the bytes in the third row of the state array, this operation can be stated as
And, for the bytes in the fourth row of the state array, this operation can be stated as
More compactly, the column operations can be shown as:
where, on the left-hand side, when a row of the leftmost matrix multiples a column of the state array matrix, additions involved are meant to be XOR operations.
The corresponding transformation during decryption is given by:
Step 4: Adding round key
Each round has its own round key that is derived from the original 128-bit encryption key in the manner described in this section. The last step of each round (for both encryption and decryption) involves XORing of the round key with the state array. The 128-bit round key is derived from the original 128-bit encryption key using the AES Key Expansion algorithm.
What makes AES secure?
Unlike DES, in AES, 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 discussed, DES was based on the Feistel network. On the other hand, what AES uses is a substitution-permutation network in a more general sense. Each round of processing in AES involves byte-level substitutions followed by word-level permutations. Speaking generally, DES also involves substitutions and permutations, except that the permutations are based on the Feistel notion of dividing the input block into two halves, processing each half separately, and then swapping the two halves.
Moreover, AES is an example of a key-alternating block cipher. In such ciphers, each round first applies a diffusion-achieving transformation operation (which may be 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. Comparing that to DES which is based on the Feistel structure where, for each round, one-half of the block passes through unchanged and the other half goes through a transformation that depends on the S-boxes and the round key.
Another noteworthy point is that DES is a bit-oriented cipher (The substitution step in DES requires bit-level access to the block coming into a round) whereas AES is a byte-oriented cipher, which makes for convenient and fast software implementation of AES.
Key alternating ciphers lend themselves well to the theoretical analysis of the security of the ciphers.
A similarity that can be noted is that like DES, 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.
Considering the number of years that have passed since the cipher was introduced in 2001, all of the threats against the cipher remain theoretical — meaning that its time complexity is way beyond what any computer system will be able to handle for a long time to come.
To visualize it, consider the example to evaluate the time required to recover 56-bit DES and 128-bit AES key :
Assuming that the single evaluation of a block cipher takes 10 operations, and 10¹⁴ ≈ 2⁴⁶ operations can be performed per second in the least, then our hypothetical machine would take ≈ 362 seconds to find a 56-bit DES key, and ≈ 36 quadrillion years to find a 128-bit AES key.
Why should we learn DES cipher?
Despite DES losing the giant position of being the go-to data encryption standard algorithm, it’s still worth learning. There will always be room for the DES algorithm in cryptography because it was the foundation for subsequent encryption algorithms, and can be used to understand the current encryption methods better.
To learn more about how to implement AES using python, the following tutorial shares examples using module Crypto.cipher — click here.
References
- The AES standard is described in this official document, here.
- For further details on the cryptanalysis of AES ciphers and the various attacks on block ciphers, ‘Lecture Notes on Computer and Network Security by Avi Kak’ can be referred to.
This article is published as a part of the ‘Hacker Series’ under Spider Research and Development Club, NIT Trichy on a Web Wednesday!
