4
Symmetric-key Algorithms
1. Explain DES with its structure. Also explain its function.
Ans.: Data Encryption Standard (DES) is a symmetric-key block cipher that was first published in 1977 by National Institute of Standards and Technology (NIST). It was originally proposed by IBM in 1973 in response to the request for proposals for a national symmetric-key cryptosystem. This encryption standard was adopted by the US government for non-classified information and by various industries for use in security products. DES is also known as the Data Encryption Algorithm (DEA) by ANSI and DEA-1 by ISO.
At the sender's end, DES divides the plaintext into 64-bit blocks and encrypts each block using a 56-bit cipher key to produce a 64-bit ciphertext block. At the receiver's end, the reverse process is followed; that is, DES decrypts the 64-bit ciphertext to obtain 64-bit plaintext. Being a symmetric-key cipher, DES uses the same 56-bit cipher key for both encryption and decryption. Originally, the cipher key is of 64 bits including 8 parity bits; however, the usable bits in key are only 56.
DES involves multiple rounds to produce ciphertext, and the key used in each round (called the round key) is the subset of the general key, called the cipher key; the round keys are generated by the round key generator. Thus, if there are P rounds in the cipher, then the round key generator produces total P round keys (K1, K2,…, KP) where K1 is used in first round, K2 in second round and so on.
DES Structure
Figure 4.1 shows the general structure of the DES encryption algorithm (referred to as the DES cipher); the design of the DES decryption algorithm (referred to as the DES reverse cipher) is also similar, except that the round keys are used in the reverse order from that of encryption. The whole process of producing ciphertext from plaintext comprises 19 stages. The first stage is the initial transposition, which performs keyless straight permutations that are the inverse of each other on the 64-bit plaintext block, according to a predetermined rule. The next 16 stages are the rounds that are functionally similar and, in each round, a different round key Ki of 48 bits derived from the cipher key of 56 bits is used. The second-last stage performs a swap function in which the leftmost 32 bits are exchanged with the rightmost 32 bits. The last stage, final transposition, is simply the opposite of the first stage; that is, it performs inverse transposition on the 64 bits received from the 32-bit swapper to generate
a 64-bit ciphertext block. For example, if in the initial transposition stage, the input bit 2 becomes the output bit 50, then in the final transposition stage, the input bit 50 becomes the output bit 2. At the receiver's end, the decryption is performed using the same key as in encryption; however, the steps are performed in the reverse order.
The structure of one of the 16 rounds (say, i-th round) during encryption in DES is shown in Figure 4.2. It takes two inputs: the leftmost 32 bits as left input (Li) and the rightmost 32 bits as right input (Ri), and produces two outputs, left output (Li+1) and right output (Ri+1), each of 32 bits. The left output (Li+1) is just the right input (Ri). The right output (Ri+1) is obtained by first applying the DES function (f) on the right input (Ri) and the 48-bit key (Ki) being used in the i-th round, denoted as f(Ri, Ki), and then performing the bitwise XOR of the result of DES function and the left input (Li). The structure of decryption round in DES is simply the opposite of the encryption round.
Figure 4.1 General Structure of DES Encryption
Figure 4.2 Structure of Encryption Round
DES Function
The essence of DES is the DES function, f(Ri, Ki). During each round, this function takes the -rightmost 32 bits and applies the 48-bit round key generated for that round on it to produce the 32-bit output. The function comprises four steps (see Figure 4.3), which are described as follows:
1. Expansion P-box: The right output (Ri) of 32 bits is initially fed into the expansion P-box, which expands it to 48 bits, because the key (Ki) used is of 48 bits. For this, the 32 bits of Ri are divided into eight blocks of 4 bits each. Each 4-bit block is then expanded to 6 bits using a predetermined rule, as explained in the following text.
a. Copy the input bits 1, 2, 3 and 4 to output bits 2, 3, 4 and 5, respectively.
b. Copy the input bit 4 of the previous block to output bit 1 of the block under consideration. This step is an exception to the first block.
c. Copy the input bit 1 of the next block to output bit 6 of the block under consideration. This step is an exception to the last (eighth) block.
Notice that in case of first block, the input bit 4 of the last block becomes the output bit 1, while in case of last block, the input bit 1 of the first block becomes the output bit 6. The resulting 48 bits are forwarded to the next step.
2. XOR operation: A bitwise XOR operation is performed on the 48-bit output obtained from the previous step and 48-bit round key Ki, resulting in 48 bits. These 48 bits are forwarded to the next step.
3. S-boxes: The 48-bit output obtained after the XOR operation is broken down into eight groups, with each group consisting of 6 bits. Each group of 6 bits is then fed to one of eight S-boxes. Each S-box follows a predetermined rule to map six inputs to four outputs and, thus, total 32 bits are obtained from eight S-boxes. The rule for substitution in each S-box is based on a table consisting of four rows and 16 columns. To perform the substitution in an S-box, the input bits 1 and 6 (2 bits) together define the row number, and the input bits 2, 3, 4 and 5 (4 bits) together define the column number. Now, the value at the intersection of the computed row and column number defines the 4 output bits. For example, if the input to an S-box is 101011, then the row number is 11 (equivalent to decimal number 3), and the column number is 0101 (equivalent to decimal number 5). Now, if the value at the intersection of third row and fifth column is 6, then the resulting output bits will be 0110.
4. Straight P-box: The 32 bits obtained from S-boxes are input to a straight P-box, which permutes them and produces 32 bits as output. As with the previous operations, the input bits are permuted based on the predetermined rule. For example, the input bit 7 becomes the output bit 2.
Figure 4.3 DES Function
2. Explain key generation of DES with the help of a block diagram.
Ans.: The generation of keys in DES for each round is done by round-key generator. The round-key generator produces sixteen 48-bit keys out of a 56-bit cipher key, one for each round. As in DES, the original key size is 64 bits, including the parity bits; therefore, the parity bits are initially dropped using the parity bit drop process before the actual key generation process starts. The parity bit drop process is actually a compression transposition step that drops the parity bits present at every eighth position (8, 16, 24, 32, 40, 48, 56 and 64) in the 64-bit key, generating a 56-bit key. Then the 56 bits of the key are permuted according to a predetermined rule, as shown in Table 4.1. For example, the bit 1 of the original 56-bit key becomes the eighth bit of the new 56-bit key. This 56-bit key is the actual cipher key used for key generation.
Table 4.1 Parity Drop Box Table
During each round, the round key generator uses the 56-bit cipher key and performs the following steps to generate the key for that round (see Figure 4.4).
1. Divide the plaintext into two halves of 28 bits each.
2. Perform circular left shift operation on each 28-bit half. Shifting is done either by 1 or 2 bits, depending on the round number. In case of rounds 1, 2, 9 and 16, shifting is done by 1 bit, while in the case of the other rounds, shifting is done by 2 bits.
3. After shifting has been performed, both halves are combined again to form a 56-bit part. These 56 bits are then given as input to the compression P-box.
4. The compression P-box, as its name suggests, compresses the 56-bit input to produce 48-bit output. This 48-bit output generated from the P-box is then used as a key for the round.
Figure 4.4 Key Generation in DES
3. Discuss the strength of DES.
Ans.: The strength of any cryptographic system is measured by the fact that how resistive it is to an attack. In case of DES, the strength of the system lies in two important aspects: key size and the use of S-boxes.
Key size: DES uses 56-bit keys in each round, which means 256 (approximately 7.2 * 1016) number of keys. Therefore, a brute-force attack on DES seems practically impossible. However, if we assume that, to get the correct key, only half of the total keys are needed to be examined, a single computer performing one DES encryption per microsecond would still take more than 1000 years to break the DES.
Use of S-boxes: DES uses eight S-boxes (substitution tables) in each round. The internal design of these substitution tables has been kept secret by IBM. Therefore, a suspicion has grown that there may be some weaknesses in the internal design of S-boxes that can be exploited by cryptanalysts to break the DES security. Over the years, a number of studies have appeared which suggest that there is a scope of attacking DES through S-boxes; however, no one has succeeded till date.
4. Comment on the weaknesses of DES.
Ans.: Although the DES cipher is widely used and is resistant to various attacks, some weaknesses are still found in it. The weaknesses have been found in two aspects of DES, in the cipher design and in the cipher key.
Weakness in the Cipher Design
The DES cipher involves a number of S-boxes and P-boxes, which suffer from certain problems. Some weaknesses found in S-boxes are as follows:
In fourth S-box, the last 3 bits in the output can be obtained in the same way as the first bit in the output by performing complement operation on some of the bits in input.
In a single round, the same output can be obtained if the bits in only three neighbouring S-boxes are changed.
Two specific chosen inputs when given to the array of eight S-boxes can result in the same output.
Some weaknesses found in P-boxes are as follows:
The initial and final permutation stages used in DES do not provide any security benefits.
In the expansion permutation used within the DES function, the input bits 1 and 4 of each 4-bit series are repeated in the output.
Weakness in the Cipher Key
The cipher key used in DES has got certain shortcomings, which are described as follows:
Size of cipher key: As the cipher key used in DES is of 56 bits, an intruder needs to examine 256 possible keys in order to attempt a brute-force attack. If a computer with a single processor that can process about one million keys per second is used for examining the whole key domain, it will take more than 2000 years to attempt brute-force attack on DES. In 1977, this period of 2000 years reduced to 120 days when 3500 networked computers and the concept of parallel processing were used. The entire key domain was divided into several parts, and each computer had to examine only some parts. Furthermore, a secret society having 42000 members can break the
cipher and thus, determine the key in 10 days only. Thus, it can be concluded that the DES with a cipher key of 56 bits is not safe enough for use.
Weak keys: Out of 256 keys, there are four keys that comprise either all 0s, all 1s or half 0s and half 1s. These four keys are referred to as the weak keys. When the round keys are created from any of the weak keys, they follow the same pattern as that of the cipher key. For example, a round key created from the weak key containing all 0s or all 1s will also comprise all 0s or 1s, respectively. This is because the cipher key is divided into two equal parts during key generation in DES. Thus, neither substitution nor permutation affects the block containing all 1s or all 0s. The disadvantage of using a weak key lies in the fact that it is the inverse of itself. That is, when a plaintext block is encrypted with a weak key and then the result is further encrypted with the same weak key, we get back the original plaintext block. Exploiting this fact, the intruder can easily attempt to decrypt the intercepted ciphertext using the weak keys. In case the result is the same after two decryptions, it means the intruder has got the key. Therefore, it is recommended that the use of weak keys be avoided.
Semi-weak keys: In 256 keys, there are six pairs of keys that create only two distinct round keys for total 16 rounds, and each key is used in eight rounds. These six key pairs are referred to as semi-weak keys. Each pair of semi-weak keys creates the same two round keys; however, they are used in 16 rounds in different order.
Possible weak keys: There are 48 such keys that create only four different round keys, and each of them is repeated four times. These 48 keys are referred to as possible weak keys.
Key complement: In 256 keys, half of the keys (that is, 255) are the complement of the other half keys. That is, if half of the total keys are known, the remaining half can be obtained by simply inverting the bits (1 to 0 or 0 to 1) of the known keys. This proves to be beneficial to the intruder as now he or she has to examine only half of the key domain to attempt a brute-force attack. This is because of the fact that if the complement of plaintext is encrypted using the complement of a key, then a complement of the ciphertext is obtained.
Key clustering: The situation where two or more different keys result in the same ciphertext from the same plaintext is referred to as key clustering. In DES, each pair of semi-weak keys is a key cluster.
5. What do you understand by differential and linear cryptanalysis of DES?
Ans.: Differential cryptanalysis is a chosen-plaintext attack that was introduced by Eli Biham and Adi Shamir in 1990. The basic idea of this attack is to choose a pair of plaintexts having specific differences and then analysing the corresponding ciphertext pair. The attacker examines how these differences propagate in the ciphertexts as the plaintexts pass through the rounds of DES. Using the differences in the ciphertexts, the attacker determines the probability of different possible keys and, eventually, as ciphertexts are analysed progressively, the actual cipher key emerges. The designers of DES were aware of chosen-plaintext attacks; therefore, they used S-boxes and 16 rounds to encrypt the plaintext in DES. Doing so makes DES invulnerable to differential cryptanalysis as breaking a DES message by differential analysis will need either 247 chosen plaintexts or 255 known plaintexts. Although differential cryptanalysis attacks are much powerful than brute-force attacks, finding 247 chosen plaintexts or 255 known plaintexts is not practically possible. Moreover, if we increase the number of rounds in DES to 20, then a differential cryptanalysis attack needs 264 chosen plaintexts, which is practically impossible, because DES can only have 264 possible plaintexts.
Linear cryptanalysis is a cryptanalysis technique that was introduced by Mitsuru Matsui in 1993. It is a known-plaintext attack that is based on linear approximations. The idea is to perform the XOR operation on some bits in the plaintext and ciphertext together, and then take the XOR of the result; the final result is a single bit that will be the XOR of some bits in the key. The linear cryptanalysis attacks on DES are more vulnerable than differential cryptanalysis attacks, because the designers of DES had no idea about linear cryptanalysis attacks at the time of designing. Also, S-boxes are not very resistant to linear cryptanalysis. A linear cryptanalysis attack can break DES in 243 pairs of known plaintexts. However, it is not practically feasible to find so many pairs.
6. Define Avalanche effect and completeness effect. Also, discuss the strength of DES with regard to these.
Ans.: Both Avalanche effect and completeness are the desirable properties of a block cipher. These properties are described as follows:
Avalanche effect: This property states that any small change made to the plaintext or the key should cause a significant change in the ciphertext. That is, change in a single bit in the plaintext should result in changes in multiple bits in the ciphertext. This property is desired because the lack of it would considerably reduce the key domain to be searched, thus making it easier for a cryptanalyst to attempt a brute-force attack. In general, an encryption method is considered to have a good avalanche effect if change in a single bit of plaintext results in a random change in approximately half of the bits in the ciphertext.
DES has been proved to be very strong with regard to the Avalanche effect. In DES, when two plaintext blocks having only a single bit difference are encrypted using the same key, the ciphertexts obtained do not have much resemblance. Similarly, when the same plaintext is encrypted using two neighbouring keys (keys with only a small difference), we obtain two significantly different ciphertexts.
Completeness effect: This property states that each bit of the ciphertext should depend on -multiple bits of the plaintext or the key. It tightens the concept of avalanche effect even more by requiring that, for each modified bit in the plaintext or the key, the change in ciphertext must be distributed uniformly. In other words, completeness means that the avalanche effect spans across all pairs of bits in the plaintext and ciphertext, almost uniformly. DES represents a strong completeness effect because of the diffusion and confusion produced by the P-boxes and S-boxes used in the DES cipher.
7. What is double DES? Explain the meet-in-the-middle attack.
Ans.: Double DES (2-DES) is the simplest version of multiple-DES. As the name implies, double DES performs DES encryption/decryption twice using two different keys (K1 and K2) of 56 bits each. This increases the key size to 112 bits, thus, increasing the cryptographic strength to double that of normal DES.
At the sender's end, the plaintext P is initially encrypted using DES with key K1 to obtain the temporary ciphertext T = EK1(P). Then, the temporary ciphertext T is again encrypted using DES with key K2 to obtain the final ciphertext C = EK2(T), that is, C = EK2(EK1(P)). At the receiver's end, the reverse process is followed to decrypt the ciphertext, and the keys are used in the reverse order of that of encryption. That is, first the ciphertext C is decrypted using DES with key K2 to obtain the temporary plaintext T′ = DK2(C), and then the temporary plaintext T′ is again decrypted using DES with key K1 to get back the original plaintext P = DK1(T′), that is, P = DK1(DK2(C)). Figure 4.5 shows the encryption and decryption processes in double DES.
Figure 4.5 Encryption and Decryption in Double DES
Meet-in-the-middle Attack
The use of key size of 112 bits implies that an attacker would need 2112 attempts, which is twice that of normal DES, to break the cipher key. However, this is not true because of the meet-in-the-middle attack that was introduced by Merkle and Hellman. In this attack, encryption is performed from one end, decryption is performed from the other and matching the result in the middle, and it is hence that the attack is named so.
The meet-in-the-middle attack is based on the observation that if we have C = EK2(EK1(P)), then we can have EK1(P)= DK2(C), that is, T = T′. To understand how this attack happens, let us consider that the attacker knows a plaintext block P and a ciphertext block C of some message. Now, to determine K1 and K2, the attacker may perform the following steps:
1. For each of the 256 possible values of K1, allocate a large table in the memory and perform the following:
a. Compute the temporary ciphertext T = EK1(P).
b. Store the value of T in the next available row of the table in memory.
After performing the preceding two steps, we get a table containing the values of the temporary ciphertext T.
2. For each of the 256 possible values of K2, perform the following:
a. Compute the temporary plaintext T′ = DK2(C).
b. Compare the value of T′ with all the values in the table of temporary ciphertext T.
c. If T′ matches with any value of T in the table, use the corresponding pair of K1 and K2 to encrypt and decrypt another known pair of plaintext (say, P′) and ciphertext (say, C′) blocks, respectively.
d. If EK1(P′)= DK2(C′), then K1 and K2 are the correct keys and can be used for remaining blocks of the message.
Though the meet-in-the-middle attack is possible on double-DES, it needs a lot of memory space to store the values of T. For example, if a 64-bit plaintext block and a 56-bit key are used, then 256 64-bit blocks (equivalent to 217 bytes) of memory would be needed, which is too high. This makes the meet-in-the-middle attack practically infeasible.
8. Write a short note on triple DES.
Ans.: To overcome the problem of meet-in-the-middle attack in double DES, triple DES (3-DES) was developed. As the name implies, it performs the DES encryption process thrice. There are two implementations of 3-DES: one with two keys, and another with three keys.
3-DES with Two Keys
This version uses two keys, say K1 and K2 of 56 bits each to perform encryption and decryption. At the sender's end, the following three steps are performed to produce ciphertext C from the plaintext P.
1. Encrypt the plaintext P using DES with key K1 to produce T = EK1(P).
2. Decrypt T using DES with key K2 to produce S = DK2(EK1(P)).
3. Encrypt S using DES with key K1 to produce ciphertext C = EK1(DK2(EK1(P))).
Similarly, during decryption, the following three steps are used to obtain plaintext P from ciphertext C.
1. Decrypt the ciphertext C using DES with key K1 to produce T′ = DK1(C).
2. Encrypt T′ using DES with key K2 to produce S′ = EK2(DK1(C)).
3. Decrypt S′ using DES with key K1 to get back the original plaintext P = DK1(EK2(DK1(C))).
The use of two keys in 3-DES increases the key size to 112 bits and provides more secure communication. In addition, there is no special significance of using decryption in the second step. It is simply used to provide backward compatibility with the original DES by putting K1 = K2. In case of K1 = K2, 3-DES becomes equivalent to single DES and, thus, enables the users of 3-DES to decrypt the data encrypted by the users of single DES.
3-DES with Three Keys
This version uses three keys of 56 bits each, and a different key is used for performing encryption/decryption in each step. At the sender's end, the plaintext P is encrypted to form ciphertext C, as shown here:
c = EK3(DK2(EK1(P)))
At the receiver's end, the keys are used in the reverse order from that of encryption to obtain the original plaintext P from the ciphertext C, as shown here:
P = DK1(EK2(DK3(C)))
The use of three different keys increases the key length to 168 bits, making 3-DES three-key version more secure; however, it results in an increased overhead due to managing and transporting one more key. Here, the backward compatibility with DES is provided by having either K1 = K2 or K2 = K3.
9. Explain IDEA encryption and decryption in brief.
Ans.: The International Data Encryption Algorithm (IDEA) is a patented and universally applicable block cryptographic algorithm. It was proposed and launched in 1990 by Xuejia and James, and was initially named as Proposed Encryption Standard (PES). In 1991, some improvements were made in PES, and the new improved version was given the name Improved PES (IPES). Then, it was renamed to IDEA in 1992.
IDEA is a block cipher and is considered one of the strongest cryptographic algorithms. It offers effective protection of stored and transmitted data against unauthorized access by third parties. It uses a 128-bit-long key and both diffusion and confusion for encryption. This makes it more secure than the widely known DES, which is based on the use of a 56-bit key. However, as with DES, IDEA also operates on 64-bit plaintext blocks, and uses the same algorithm for encryption and decryption.
Though IDEA is powerful and strong, it is not as popular as DES because of two reasons. Firstly, it is not free and must be licensed before being used for commercial purposes. Secondly, IDEA keeps only a few history and track records as compared to DES. However, one popular e-mail privacy technique called Pretty Good Privacy (PGP) is based on IDEA.
Working of IDEA
Figure 4.6 shows the broad-level steps involved in the IDEA encryption process. The IDEA algorithm breaks down the 64-bit input data block into four 16-bits data blocks: P1, P2, P3 and P4. These four data blocks are then processed through eight rounds, and each round uses six 16-bit sub-keys generated from the original key. During each round, these data blocks are transformed by applying various arithmetic operations among each other and with the sub-keys. The whole encryption process uses a total of 52 sub-keys (K1 to K52), out of which six sub-keys, K1 to K6, are used in the first round. In the second round, the next six sub-keys, K7 to K12, are used and so on. Finally, the sub-keys K43 to K48 are used in the eighth round. The final step of the encryption process is output transformation, which uses four sub-keys, K49 to K52. The output produced from this step is four blocks of ciphertext: C1, C2, C3 and C4, each of 16 bits, which are then concatenated to form the final 64-bit ciphertext block.
Figure 4.6 IDEA Encryption Process
Encryption Round
Each round of the IDEA encryption process performs a sequence of operations on four plaintext blocks using the corresponding six sub-keys. These operations include XOR, addition and multiplication. It may be noted that addition and multiplication operations here do not imply the ordinary addition and multiplication; rather, they are addition modulo 216 and multiplication modulo (216+1), respectively. The steps involved in an encryption round are as follows:
1. Multiply P1 and K1.
2. Add P2 and K2.
3. Add P3 and K3.
4. Multiply P4 and K4.
5. XOR the results of step 1 and step 3.
6. XOR the results of step 2 and step 4.
7. Multiply the results of step 5 with K5.
8. Add the results of steps 6 and 7.
9. Multiply the results of step 8 with the K6.
10. Add the results of step 7 and step 9.
11. XOR the results of step 1 and step 9 and store the result in R1.
12. XOR the results of step 3 and step 9 and store the result in R2.
13. XOR the results of step 2 and step 10 and store the result in R3.
14. XOR the results of step 4 and step 10 and store the result in R4.
15. Swap the blocks R2 and R3.
The resultant data blocks R1, R2, R3 and R4 in each round are passed to the next round. Note that the eighth round does not involve the last step (step 15); that is, it does not perform the swapping of blocks R2 and R3. After performing all the eight rounds, the final data blocks, R1, R2, R3 and R4, of 16 bits each are passed to the next stage – that is, output transformation.
Output Transformation
This stage applies four keys, K49 to K52, on the input data blocks, R1, R2, R3 and R4, and produces the four ciphertext blocks, C1, C2, C3 and C4, by performing the following steps:
1. Multiply R1 and K49 to obtain C1.
2. Multiply R2 and K50 to obtain C2.
3. Multiply R3 and K51 to obtain C3.
4. Multiply R4 and K52 to obtain C4.
Finally, the four ciphertext blocks (C1, C2, C3 and C4) are combined to form a 64-bit ciphertext block.
Decryption
The decryption process of IDEA is the same as that of the encryption process; however, the sub-keys are used in the reverse order from that of encryption. The sub-keys used for decryption are the inverse of the sub-keys used for encryption.
Strength of IDEA
The IDEA algorithm is resistant to all known cryptanalysis attacks. It uses a 128-bit-long key. Therefore, to attempt a cryptanalysis attack on IDEA, the attacker needs to perform 2128 encryption operations, which is practically infeasible.
10. Explain the sub-key generation in the IDEA algorithm.
Ans.: As each round in the IDEA algorithm uses six sub-keys of 16-bit each and the output transformation step also needs four sub-keys, thus, a total of 52 16-bit sub-keys are required from the key length of 128 bits. For this, a sub-key generation process is used, which generates the sub-keys as follows:
In the first round, six sub-keys of 16 bits each, that is, 96 bits, are required. Therefore, the first 96 bits of 128-bit key (say, K) are used for the first round. The rest of the key bits (97–128) remain unused and, thus, are kept for the second round.
The second round also requires six sub-keys of 16 bits each; that is, a total of 96 bits. However, we have only 32 unused bits of the key K and, therefore, we need 64 bits more. To generate the rest of the bits, the IDEA algorithm uses the key shifting technique. In this technique, the original 128-bit key K is shifted left circularly by 25 bits. After shifting, the 26-th bit of the original key K becomes the first bit of the new key (say, K′), and the 25-th bit of key K becomes the 128-th bit of key K′. Now, the bits 1 to 64 of key K′ and the unused 32 bits (97–128) of key K are used to form six 16-bit sub-keys for the second round.
In the third round, we have 64 unused bits of key K′ generated in the second round, and 32 bits are still required. Thus, the key shifting technique is again applied, and the key K′ is left shifted by 25 bits. This process continues to obtain 96 bits in each round.
The output transformation stage also needs four sub-keys of 16 bits each. Notice that after the eighth round, the key gets exhausted. Thus, the key is left shifted by 25 bits, and the bits 1 to 64 of the newly created key are used to generate four sub-keys (K49 to K52) for this stage.
11. Explain Advanced Encryption Standard.
Ans.: The Advanced Encryption Standard (AES) is the latest and, potentially, the most secure encryption method published by NIST. It is a symmetric-key block cipher that was designed to be a significant improvement over DES/3-DES. In 1990s, the US government decided to standardize the cryptographic algorithm and to name it as AES. In response to this, a lot of proposals were submitted. After long debates, in 2000, the US government chose one of the proposals, the Rijndael algorithm, as AES. This algorithm is named on the surnames of the two Belgian researchers Vincent Rijmen and John Daemen. Finally, in 2001, AES was published as Federal Information Processing Standard (FIPS) 197 by NIST.
General Design of AES
AES is a non-Feistel cipher that operates on a data block of 128 bits (16 bytes) and comprises several rounds for encryption and decryption. It is available in three versions, depending on the key size and the number of rounds used. These versions include AES-128 with key size 128 bits and 10 rounds, AES-192 with key size 192 bits and 12 rounds and AES-256 with key size 256 bits and 14 rounds. Despite the fact that each version uses a different key size, the round keys used in each version are always 128 bits long, which is the same size as that of the plaintext or ciphertext block. In AES, the round keys are generated using the key-expansion algorithm (explained in the next question), and the number of round keys generated is always equal to the number of rounds plus one. Figure 4.7 shows the general design for AES encryption algorithm (referred to as the AES cipher); the design of AES decryption algorithm (referred to as the AES inverse cipher) is also similar, except that the round keys are used in the reverse order from that of encryption.
Figure 4.7 General Design of AES Encryption Cipher
Each round in AES consists of many stages, each of which transforms the 16-byte data block. In AES, the term ‘data block’ is used at the beginning and end of the cipher, while before and after each
stage, the term ‘state’ is used to refer to a data block. A state, like a data block, is also 16-bytes long and contains the data before and after the transformation. Usually, a 16-byte state (say, S) is organized as a 4×4 bytes matrix, and each element of the matrix is referred to as Si,j (0≤i≤3 and 0≤j≤3), where i and j denote the row number and column number, respectively.
Structure of Encryption Round
During encryption, each round, excluding the last one, involves four transformations, namely: Substitute Bytes, Shift Rows, Mix Columns and Add Round Key (see Figure 4.8). Each transformation accepts a state, changes it and creates a new state that is given as input to the next transformation or the next round. The last round in AES comprises only three transformations, except the Mix Columns transformation. Moreover, one Add Round Key transformation is applied before the first round (mentioned as pre-round transformation in Figure 4.7). Each transformation in AES is invertible in nature and, during decryption, the inverse of these transformations, namely, Inverse Substitute Bytes, Inverse Shift Rows, Inverse Mix Columns and Add Round Key (which is self-invertible), are used. Figure 4.8 shows the general structure of an encryption round in AES.
Figure 4.8 General Structure of an Encryption Round
Transformations
All the transformations performed during encryption and decryption fall under four broad categories that include substitution, permutation, mixing and key adding. These transformations are described as follows:
Substitution: As with DES, AES also performs the substitution of bytes, but using a different mechanism. In AES, substitution is performed for all bytes, and that too, using only one table. This implies that if 2 bytes are the same then their transformations are also same, which is contrastive to DES where eight different S-boxes perform transformations. Moreover, the bytes are substituted either with the help of a transformation table or by performing the mathematical calculations in GF(28) field. The two invertible transformations that fall under this category are as follows:
Substitute Bytes: It is the first transformation of a round used during encryption. The input to this transformation is a state organized as a 4×4 matrix of bytes. The bytes in the matrix are substituted one at a time. Thus, there are 16 distinct byte-to-byte transformations. To substitute the bytes using a transformation table, each byte is treated as two hexadecimal digits, where the first digit (left one) specifies the row and the second digit (right one) specifies the column of the substitution table. The value (two hexadecimal digits) at the intersection of the row and the column in the transformation table is the new byte with which the given byte is to be replaced.
Inverse Substitute Bytes: It is used at the decryption side and is the inverse of the Substitute Bytes transformation.
Permutation: AES also permutes the bytes. It performs a byte-level permutation (unlike DES, which works on the bit level), such that the order of bits in each byte does not change in the resultant bytes. The two invertible transformations that fall under this category are as follows:
Shift Rows: It is used at the encryption side. In this transformation, the bytes in the rows of the input state matrix are shifted to the left, and the number of bytes to be shifted depends on the row number. For example, the row 0 is not shifted at all, the row 1 is shifted 1 byte, row 2 is shifted 2 bytes and row 3 is shifted 3 bytes.
Inverse Shift Rows: It is used at the decryption side and is similar to the Shift Rows transformation, except that here the bytes in the rows are shifted to the right.
Mixing: The Substitute Bytes transformation is an intrabyte transformation as it transforms the bytes but does not affect the bits inside the bytes. It also does not take into account the neighbouring bytes. Similarly, the Shift Rows transformation permutes only the bytes but not the bits inside the bytes and, thus, is referred to as a byte-exchange transformation. In contrast, the Mixing is an interbyte transformation in which the bits inside the bytes are changed on the basis of bits in the neighbouring bytes. Mixing transformation takes 4 bytes at a time and combines these bytes to make 4 new bytes. In the combination process, each byte is first -multiplied with a different constant and, then, all the 4 bytes are mixed. For mixing, matrix multiplication is used. AES specifies the following two invertible transformations that fall under this category:
Mix Columns: It is used at the encryption side. This is a column-level transformation that takes one column of input state matrix at a time and transforms it to a new column. For transforming the columns, a constant square matrix is used. The square matrix is multiplied by each column of state matrix resulting into a column. Notice that the bytes multiplication operation is performed in GF(28) field and the bytes addition operation is performed by simply XORing the bits within bytes.
Inverse Mix Columns: It is used at the decryption side and is similar to Mix Columns transformation except that it uses the inverse of the constant square matrix used in Mix Columns transformation.
Key adding: This is the only transformation that makes use of the round key (generated from cipher key) and, thus, is considered an important transformation. To perform key adding transformation, the 128-bit round key is considered as four 32-bit words, and further, each 32-bit word is treated as a column matrix. A self-invertible transformation that falls under this category is as follows:
Add Round Key: Like Mix Columns transformation, it also operates on one column at a time; however, it uses matrix addition operation rather than matrix multiplication. Each column of the state matrix is XORed with the corresponding key word (column matrix) to produce the new column. This transformation is used in both encryption and decryption.
12. What do you mean by key expansion in AES? Explain the key expansion process in AES-128.
Ans.: Key expansion is a process used in AES to generate the round keys from the given cipher key. In AES, the number of round keys generated by this process is always one greater than the number
of rounds. That is, if there are n rounds, the key expansion generates (n+1) keys (say, K0 to Kn), out of which the first round key K0 is used in the Add Round Key transformation before the first round, and the remaining keys (K1 to Kn) are used in the corresponding rounds. In addition, the key expansion generates each round key word-by-word, where each word is an array of 4 bytes. Thus, the total number of words created in n rounds is equal to 4(n+1), denoted as d0, d1,…, d4(n+1)-1.
Key Expansion in AES-128
In AES-128, there are 10 rounds, and the cipher key is 128 bits long. Therefore, the number of keys generated is 11 (K0 to K10), and the number of words created is 44 (d0 to d43). The cipher key of 128 bits is treated as an array of 16 bytes (say, r0 to r15) – that is, four 32-bit words. Before we describe the steps involved in key expansion, we need to know the two routines, RotWord() and SubWord(), as well as round constant RCon, which are used in the process.
RotWord(): The RotWord (which stands for rotate word) routine performs a similar function as that of the Shift Rows transformation, with the exception that it is applied to only one row. It takes a 4-byte word, and shifts each byte of the word to the left with wrapping.
SubWord(): The SubWord (which stands for substitute word) routine performs a similar function as that of the Substitute Bytes transformation, with the exception that it is applied to only 4 bytes (that is, a single word). It takes each byte of a 4-byte word and substitutes it with another byte with the help of transformation table.
RCon: RCon (which stands for round constants) is a 4-byte value where the leftmost byte is non-zero and the rightmost 3 bytes are always zero. As the name implies, this value is fixed for each round. Table 4.2 lists the round constants for 10 rounds of AES-128.
| Round | RCon |
|---|---|
| 1 | (01 00 00 00 00)16 |
| 2 | (02 00 00 00 00)16 |
| 3 | (04 00 00 00 00)16 |
| 4 | (08 00 00 00 00)16 |
| 5 | (10 00 00 00 00)16 |
| 6 | (20 00 00 00 00)16 |
| 7 | (40 00 00 00 00)16 |
| 8 | (80 00 00 00 00)16 |
| 9 | (1B 00 00 00 00)16 |
| 10 | (36 00 00 00 00)16 |
The steps involved in creating 44 words (d0 to d43) from the original cipher key of 16 bytes (r0 to r15) are as follows (see Figure 4.9):
1. The 16 bytes of the cipher key (that is, r0 to r15) form the first four words d0, d1, d2 and d3. That is, d0: = r0r1r2r3, d1: = r4r5r6r7, d2: = r8r9r10r11 and d3: = r12r13r14r15.
2. Create the remaining 40 words using the following process.
for ( i = 4 to 43)do
{
if ( i mod 4)= 0 then
{
s : = SubWord(RotWord( d i-1 ))
ti: = s 
RConi/4
di : = ti di-4
}
else
di: = di-1 di-4
}
Figure 4.9 Key Expansion in AES-128
13. How is the key expansion in AES-192 and AES-256 different from that in AES-128?
Ans.: AES-192 and AES-256 employ a similar key expansion as that of AES-128, however, with a few differences. In AES-192, the cipher key is 192 bits long and is treated as an array of 24 bytes (r0 to r23), that is, six 32-bit words. As there are 12 rounds, the key expansion creates 52 words of round key (d0 to d51), and these words are generated in groups of six. The differences between key expansion in AES-192 and AES-128 are as follows:
1. The 24 bytes of cipher key (that is, r0 to r23) form the first six words (d0 to d5) of the round key.
2. For the remaining words (di, i = 6 to 51), if (i mod 6)= 0 then di: = ti ; else, di-6di: = di-1 . di-6
On the other hand, in AES-256, the cipher key is 256 bits long and is treated as an array of 32 bytes (r0 to r31), that is, eight 32-bit words. As there are 14 rounds, the key expansion creates 60 words of
round key (d0 to d59) and these words are generated in the groups of eight. The differences between key expansion process in AES-256 and AES-128 are as follows:
1. The 32 bytes of the cipher key (that is, r0 to r31) form the first eight words (d0 to d7) of the round key.
2. For the remaining words (di, i = 8 to 59)
if (i mod 8)= 0 then di: = ti di-8; else, di: = di-1 di-8.
if (i mod 4)= 0, but (i mod 8) 0, then di: = SubWord(di-1) di-8.
14. What do you mean by mode of operation in block ciphers? Explain block cipher modes of operation.
Ans.: Modern block ciphers such as DES and AES perform symmetric-key encipherment, thus providing data security. Both DES and AES have been devised to encipher/decipher fixed-size blocks of 64 and 128 bits, respectively. However, in real-life applications, the data to be enciphered is generally of variable size. Thus, some technique is needed to enhance the strength of block ciphers such as DES and AES and to adapt them to such applications so that data of any size can be enciphered. Such technique is referred to as the mode of operation. There are four commonly used block cipher modes of operations that have been suggested by NIST. These modes are discussed in the following sections.
Electronic Code Book (ECB) Mode
This is the simplest mode of operation in which the entire plaintext message is divided into m blocks (P1, P2,…, Pm), with each block containing n (usually n = 64) bits. While breaking the message, if the last block contains less than n bits, padding is used to make it equal to the other blocks.
During encryption, one n-bit block of plaintext (say, Pi) is taken at a time and encrypted using a key K to produce the corresponding n-bit ciphertext block (say, Ci). Each block is encrypted independently of the other blocks, and the same key (say, K) is used for encrypting all the blocks. During decryption also, one block is decrypted at a time, and the same key K is used for decrypting the blocks. Figure 4.10 shows the encryption and decryption processes in the ECB mode.
Figure 4.10 Encryption and Decryption in the ECB Mode
In the ECB mode, since all blocks are encrypted independent of each other, a bit error in one block during transmission will not affect any other block; however, it may cause errors in many bits within the same block. In addition, as the same key is used for encrypting all the blocks, if an n-bit block repeats in the plaintext message, the corresponding ciphertext block also repeats in the ciphertext. That is, two same plaintext blocks always result in the same ciphertext blocks. This makes the ECB mode suitable for sending only short messages, such as an encryption key, for example. For long messages, this mode may not be secure, as there are more chances of repetition in long messages.
Cipher Block Chaining (CBC) Mode
This mode of operation overcomes the problem of the ECB mode by ensuring that the same plaintext blocks will not result in the same ciphertext blocks. For this, in the CBC mode, a plaintext block is encrypted based on the previous ciphertext block. In other words, each ciphertext block depends on the corresponding current plaintext block, as well as on all the previous plaintext blocks. Like the ECB mode, the same key (say, K) is used for encrypting all the blocks.
During encryption, each plaintext block (except the first one) is first XORed with the previous ciphertext block, and then encrypted. As there is no ciphertext block prior to the first block, a data block called initialization vector (IV) is used for this. The value of this vector is randomly generated and is agreed upon by the sender and the receiver. During decryption, each ciphertext block is first decrypted using the same key (K) that was used for encryption, and then the decrypted result is XORed with the previous ciphertext block to obtain the corresponding plaintext block. In case of the first ciphertext block, the output of the decryption algorithm is XORed with IV, as used in the encryption process. Figure 4.11 shows the encryption and decryption processes in the CBC mode.
Figure 4.11 Encryption and Decryption in the CBC Mode
Cipher Feedback (CFB) Mode
The block ciphers including DES and AES operate on 64 and 128 blocks of data, respectively, and thus, are not suitable for character-oriented applications where we need to encrypt/decrypt the smaller units (say, 8 bits) at a time. In such situations, stream ciphers prove useful. The CFB is the mode that enables converting DES (or AES) into a stream cipher. As with the CBC mode, the CFB mode also uses an initialization vector (IV) that consists of 64 bits. The contents of IV are stored in the shift register. To understand how the CFB mode works, consider that d bits are to be encrypted/decrypted at a time. The following steps are used during encryption (see Figure 4.12):
1. Encrypt IV, which is stored in the shift register using the block cipher such as DES with key K, to produce an encrypted IV.
2. Take the r leftmost bits of encrypted IV and XOR them with r bits of the plaintext to be encrypted, thus producing an r-bit ciphertext (say, C). Send the ciphertext C to the receiver.
3. Shift the contents of IV stored in the shift register left by r positions, and fill the rightmost r positions with r bits of C.
4. Repeat steps 1 to 3 until the whole plaintext message is encrypted.
Figure 4.12 Encryption in the CFB Mode
During decryption, the same process is used, except that now the XOR operation is performed on the received ciphertext and the output of encryption algorithm to produce the plaintext. It should be noted that the encryption algorithm, and not the decryption algorithm, is used during decryption also.
Output Feedback (OFB) Mode
This mode is similar to the CFB mode, except that in this mode, instead of feeding ciphertext as an input to the shift register in the next stage of the encryption process, the output of IV encryption (that is, encrypted IV) is fed into the shift register. Thus, the ciphertext does not take any part in the encryption process. Figure 4.13 shows the encryption process in the OFB mode.
Figure 4.13 Encryption in the OFB Mode
An advantage of the OFB mode is that bit errors are not propagated. This means that if a bit error occurs in the ciphertext during transmission, then only the corresponding plaintext bit will be erroneous, rather than the whole message. However, an attacker can simultaneously make changes to the ciphertext and checksum of the message in a controlled way. Thus, there is no way to detect this change.
Multiple-choice Questions
1. There are _________ encryption rounds in IDEA.
(a) 5
(b) 16
(c) 10
(d) 8
2. DES encrypts/decrypts blocks of _________ bits.
(a) 128
(b) 64
(c) 56
(d) 192
3. The algorithm in the AES cipher was actually given by _________.
(a) Rijndael
(b) IDEA
(c) Blowfish
(d) None of these
4. Which of the following modes of operations does not make use of an initialization vector?
(a) Cipher block chaining
(b) Output feedback
(c) Cipher feedback
(d) Electronic codebook
5. Each round in DES uses _________ S-boxes.
(a) Five
(b) Ten
(c) Eight
(d) Six
6. Which of the following services is based on the IDEA algorithm?
(a) PGP
(b) S/MIME
(c) SET
(d) SSL
7. Which of the following transformations belong to permutation?
(a) Inverse sub-bytes
(b) Shift Rows
(c) Add Round Key
(d) All of these
8. The key expansion in AES-256 creates _________ words.
(a) 44
(b) 52
(c) 60
(d) 54
Answers
1. (d)
2. (b)
3. (a)
4. (d)
5. (c)
6. (a)
7. (b)
8. (c)