2.2.1.1 Caesar Cipher

It was the ancient example of substitution based ciphers and it was believed to be applied in practice by ancient king Julius Caesar. In Caesar cipher, the smallest unit of a message is replaced by a unit three position next in its alphabet set. Therefore, plaintext message “How are you” will be transformed into “Kru duh brx”.

Caesar cipher is quite easy to implement but prone to brute force attack. Trying all the possible key space to deduce the plaintext from ciphertext is termed as Brute Force attack or exhaustive key search method. The approach is useful only when the key size is smaller otherwise for a larger key size this approach is quite impractical. Therefore, Caesar cipher can be easily decrypted by trying all the 25 keys.

2.2.1.2 Monoalphabetic Cipher

The problem of smaller key space of Caesar cipher was rectified in Monoalphabetic cipher. In Monoalphabetic cipher substitution characters are a random permutation of 26 alphabets. It means B can be replaced by alphabets A to Z, other than B. Furthermore there is no relation among replacement of each character. In other words replacement of A by D (i.e., A + 3 = D) does not mandate replacement of B by E.

Generally, the plaintext is written in well-known language therefore its statistical properties are easily available that can lead to statistical analysis attack on the ciphertext. It is not easy to apply brute force method in this case as it will take a lot more time trying 26! possible combinations of keys¹ or even half of them. But, the frequency of occurrence of characters may lead to statistical analysis attack, i.e., same plaintext symbols always map to same ciphertext symbols [2].

Statistical analysis techniques provide good results if the length of the analyzed text is large. Therefore, good ciphers must hide the statistical properties of plaintext i.e., generates a random sequence of ciphertext symbols. Alternatively, plaintext available can be compressed before encryption to thwart against such attacks. Mathematician Carl Friedrich Gauss suggested an idea of using homophones i.e., multiple occurrences of a symbol will be replaced with different symbols. But, the biggest challenge of occurrence of combinations of two letters known as digraph cannot be removed.

An enhancement to the Monoalphabetic cipher is made by Polygram substitution cipher where a group of plaintext letters is encrypted with a group of ciphertext letters. It may be applied to a group of two (termed bigram or digraph) to N letters (N-gram). For example plaintext block “HIJ” may be encrypted to “KTQ” while “HIK” may be encrypted to “CDS”. This hides the frequency of individual letters.

2.2.1.3 Playfair Cipher

It has been seen that all the previously discussed ciphers were majorly suffering from the occurrence of a digraph in the text. Sir Charles Wheatstone suggested a method to treat diagrams as a single unit. He analyzed that ciphertext generated by one character substitution methods are more likely to preserve much of the plaintext syntax. However, substituting multiple plaintext letters i.e., treating them as a unit will wipe out some of that plaintext. Playfair Cipher is a popular cipher for multiple-letter substitution. This Cipher treats digraphs (i.e., the combination of two letters) of plaintext syntax as a single unit and substitutes them into equivalent cipher digraphs.

Playfair cipher requires a 5 * 5 matrix of letters of a keyword. For example, if the keyword is: Cryptography then the corresponding matrix will be as per Table 2.1:

This matrix is constructed by filling the alphabets of keyword: Cryptography left to right without writing duplicates (r and p). Rest of the matrix is filled by the remaining of the alphabets (a to z) in their actual order. Letters I and J considered as a single letter. Two letters of alphabets are translated at a time as per the following rules:

• A pair of same alphabets will be separated by a filler letter, for example say Z. So “Collect” will be treated in digraphs as “Colzlect”.
• Plaintext letter that comes in the same row will be replaced by their immediate right letter of the same row in a circular manner. So PT will be translated as TC.
• Plaintext letter of the same column will be replaced by the letter beneath from top to down in a circular manner of the same column. So RV will be translated as GR.
• Else, every plaintext character is swapped by the character found at the intersection of its row and remaining plaintext character’s column position. E.g., plaintext unit GQ will be changed to HM, similarly, BN will be changed to AS.

Playfair remains robust cipher for a long time and popularly used during World War I and II. But, the cryptanalysis of the Playfair cipher is also aided by the fact that a digraph and its reverse will encrypt in a similar fashion. It means that if the encryption of MN will be AJ, then encryption of NM will be JA. So by looking for words like: receiver, departed, repairer that begin and end in reversed digraphs may lead intruder to apply frequency analysis method to reveal plaintext.

2.2.1.4 Polyalphabetic Cipher

Monoalphabetic cipher uses the same substitution rule for each substitution but in Polyalphabetic cipher rule changes with each letter or alphabet according to key value as per Table 2.2.

An early example of Polyalphabetic cipher is Vigenere cipher. Each letter of plaintext substituted into cipher as per the corresponding key value. For example, key: abracadabra and plaintext: “Can you meet me at midnight”, then corresponding ciphertext will be as shown in Table 2.3.

Generally, the key string is shorter than the message length like “abracadabra” is the key in the above example, so a same key string is appended and repeated for entire message length, or as an alternate, plaintext may be appended to the key. It is quite difficult to implement a frequency analysis method on Polyalphabetic cipher as the output is having multiple ciphertext letters corresponding to the same plaintext letter. For a key length N; Cipher consists of N monoalphabetic substitution cipher and the plaintext letters at positions 1, N, 2N, etc., will be encrypted by same monoalphabetic substitution cipher. This may be useful to decrypt each monoalphabetic cipher. The same cipher will be produced if two same sequence of plaintext appears at a distance that is an integer multiple of keyword length e.g., plaintext “hello to hell” and key “welcome” will produce ciphertext dIqkcfsdIqk.

It is not difficult for the intruder to steal the information for a shorter key length. Therefore, it is recommended that length of key and plaintext should be same, and key should be a random permutation of 26 letters of the alphabet.

2.2.2 Transposition Based

Transposition is a technique to rearrange the order of plaintext elements to produce ciphertext. This technique is based upon permutation of the plaintext, i.e., SECURITY can be transposed to SCRYEIUT. Some popularly used transposition ciphers namely Simple Columnar and Rail Fence are discussed for better understanding of the approaches.

2.2.2.1 Simple Columnar

In this approach plaintext message is written in the rows of a certain size matrix and cipher is produced by reading its contents column-wise. The order to read the column is determined by the secret keyword shared among the communicating parties. If the keyword is given in alphabets, then, it is to be first converted into numbers according to their alphabetic order. For example, if the keyword is “BASH”, then the corresponding key will be 2143. For example, to encipher the plaintext “I AM SENDING YOU A MESSAGE” with keyword “SECRET, a two-dimensional matrix of 4 rows and 6 (keyword length) column is required. Number of rows (M) can be calculated as ⌈Length (plaintext)/Length (keyword) ⌉².

Thus, the final matrix is as per Table 2.4.

Three places of the matrix left vacant after filling the matrix with plaintext. These vacant places should be filled with random letters instead of filling with a single padding character (for example “X”). The ciphertext will be written in the blocks of five to avoid guessing of keyword length. Thus, the cipher text is MNMEA IAGEY SPSGE QIDUA NOSJ.

2.2.2.2 Rail Fence Cipher

In Rail Fence transposition technique, plaintext characters are arranged diagonally and processed row by row to produce ciphertext. The number of rows is termed as the depth of the cipher. For example, plaintext “this is secret” will be arranged in depth of 2 as shown in Table 2.5. Depth is also known as ‘rail’ justifying its name as ‘Rail Fence’.

The corresponding ciphertext is produced by reading the characters row by row, therefore ciphertext is:

The number of rows (rails) can be more than two to enhance the robustness of the cipher. The strength of the cipher can be judged on the basis that the intruder can simply start assuming that there are two rows hence letters 1, 3, 5, … of the message are from the same row and 2,4,6, … are from another. If this is not the case then intruder will assume three rows hence letters 1,5,9, ... are in the first row, letters 2,4,6,8, … are in second and 3,7,11 are in row number three.

Generally, many modern security algorithms achieve information security by applying multiple rounds of substitution and transportation in a combined fashion [3].

2.3.1.1 One Time Pad (OTP)

To begin with the simplest approach of a stream cipher, we illustrate the One Time Pad (OTP) invented by Vernam in 1917. The OTP cipher considered to be first secured stream cipher. In OTP, plaintext, ciphertext, and key value consist of binary numbers:

1. Plaintext := Ciphertext := {0,1}ⁿ
2. Key value :=.{0,1}ⁿ

Key value is a random stream of bits whose length is equal to the length of plaintext message and the cipher is defined as:

In OTP, the encryption process is simply XOR³ of key and plaintext message, so

XOR operation is also termed as modulo two additions as the results of modulo-two additions are exactly same as of XOR operations.

Based upon the properties of XOR, decryption of the ciphertext is:

OTP approach is efficient and fast to encrypt and decrypt plaintext. However, it requires a large key size to thwart against attacks. If plaintext P and its OTP encryption C are given, it is possible to find out the OTP key K.

Now, XOR both the side by P

Readers must note that encryption process is often randomized while decryption process is always deterministic.

2.3.1.2 RC-4

RC-4 (Rivest Cipher) is a stream cipher algorithm that uses variable length secret key ranging from 1 to 256-bytes. It was developed in 1987 by Ron Rivest. RC-4 generates a keystream in the form of a bit which is XOR’d with the plaintext to produce ciphertext.

Working of RC-4 is divided into two parts namely: initialization of state vector and key generation. Initialization phase uses a key K as a seed value to populate state vector (array) S, and the key generation phase produces key in the form of pseudo-random bit streams. The idea of the key generation phase is to use a key value as a seed to generate a look-up table that can be used to produce pseudo-random bit streams, which act as key values. Array S is basically a 256-byte long state vector, which is populated using the small pseudo-code given below:

As the key length is variable, it can be less than 256 bytes, therefore, a temporary array T of size 256 bytes is used to copy the key value. If key length is less than 256 bytes, key values will be repeated to fill the array T.

The code is permuting the initial values of state vector S which were initialized from 0 to 255 in the beginning. The second loop which takes key values to produce the value of index j indicates that the values of state vector S are dependent upon key K. Once this code is over, the second phase, i.e., key generation starts. The pseudo code of the key generation phase is shown below:

In the pseudo code, PRK stands for Pseudo-Random Key and P [0: N-1] denotes to plaintext. The code suggests that the value of index i is incremented in each iteration, and the value at that index is used to compute next index value j. Then, values at both the indexes in the state vector S are swapped. It means every iteration will make changes in the state look-up table. Values of S[i] and S[j] are added and ‘modulo 256’ operator is used to limit the result in the range of 0 to 255. Finally, the value at this index which is shown as tmp” in the code is used to fetch the value from state vector S. This value is the key for this iteration. The key value is XOR’d with the plaintext and this process is repeated for next byte of plaintext and so on. RC-4 generates pseudo-random bytes of the key at a time, which can be XOR’d with the byte of plaintext to produce ciphertext byte, i.e., operations of RC-4 are byte oriented. Figure 2.4 illustrates the operations of RC-4 graphically.

RC-4 is a simple and easy to implement encryption algorithm that works fast in software. HTTPS and WEP (Wired Equivalence Privacy) incorporates RC-4. However, WEP protocol is no longer considered secure due to the way of implementing RC-4 in it. Nevertheless, the problem is not with RC-4, but the way it is implemented.

2.3.1.3 A5/1

A5/1 is a stream cipher algorithm used to encrypt the telephonic conversations. It was first used by the Global System of Mobile (GSM) based mobiles as a built-in support to provide confidentiality to their users. Initially, A5/1 remained secret by GSM service providers, but, later, it was reverse engineered and analyzed by cryptanalysts.

A5/1 uses a secret key of size 64-bit and an initialization vector (IV) of size 22-bit. IV is obtained from a publically known frame number of 22-bit. The key component of A5/1 stream encryption is a linear feedback shift register (LFSR). It incorporates three LFSRs namely R1, R2, and R3 of size 19-bit, 22-bit, and 23-bit, respectively. LFSRs uses their bit number 8, 10, and 10, respectively, as clocking bit, i.e., LFSRs are clocked regularly as per the value of their corresponding clocking bit. Clocking decision involves all the three registers. Clocking bit of all the three LFSRs are used to compute majority value using the following formula:

In Figure 2.5, a clock controlling unit is indicated that controls the clocking decision of A5/1. LFSRs whose clocking bit agrees with the computed majority are clocked i.e., LFSR R1 will be clocked if its 8^th bit (clocking bit) agrees with the majority. In every clock cycle, LFSRs updates according to their primitive polynomial as shown in Table 2.6, Only last bit of LFSRs contributes to the output which is calculated by XORing the values of Most Significant Bit (MSB) of R1, R2, and R3. Following expression summarizes the output:

Using one bit per clock cycle, A5/1 produces a 228-bit output stream. The first half of the output stream is used to encrypt uplink data while the remaining half is used to encrypt downlink data.

With only 64-bit of key size, A5/1 seems weak using today’s modern day computer systems. However, A5/1 is used in many countries to protect their GSM networks. Many countries also use A5/2 which is also a similar kind of stream cipher but it is designed to be weaker than A5/1 [4].

Confusion:

Confusion is intended to conceal the relationship between plaintext and ciphertext. In easier words, it is a technique to make sure that ciphertext does not reveal the pattern of plaintext. The process of confusion uses the key in a complex manner that even when an intruder knows the statistics; it is still difficult to infer the key. Confusion means that every bit of ciphertext depends upon many bits of the key. Therefore, changing a single bit in the key will drastically change the cipher.

Diffusion: It spreads the statistical properties of plaintext while producing ciphertext. Thus, diffusion dissipates the statistical structure of plaintext over most of the ciphertext. Diffusion complicates the statistics of the ciphertext, so it is difficult to discover plaintext through ciphertext. Shannon suggested a network of substitution and permutation to achieve confusion and diffusion in a strong cipher. An algorithm will be known for good diffusion if each of its plaintext bits and key bits affects half of the output bits. A good degree of avalanche effect is a major requirement of any cryptographic algorithm. Otherwise, the cryptanalyst can find out plaintext given some ciphertext or cryptanalyst can figure out key having a pair of plaintext and ciphertext. In order to illustrate the avalanche effect, an example of hash algorithm SHA-1 is shown in Table 2.7.

So, it is clear that in the second string only “hello” word is replaced with “hell” but there is a significant change in their corresponding hash value. This is a good example of the avalanche effect in the hash function. In order to achieve a strong avalanche effect most of the modern cryptographic algorithms combine both confusion and diffusion methods.

2.3.2.1 Feistel Cipher Structure

In the early 1970s, IBM realized that the customers are demanding some form of encryption to protect their information stored or transferred digitally. Therefore, IBM formed a group called crypto group and the head of the group was German-born physicist and cryptographer Horst Feistel. His first designed algorithm called Lucifer that accepts a secret key length and block length of 128 bit.

The design of Horst Feistel is popularly known as Feistel network. Feistel network is a symmetric structure used to design most of the block cipher algorithms (except AES). The goal behind building the Feistel network was to develop an invertible function, i.e., a structure that can be used in both encryption and decryption with the change in parameters only. In Feistel network, plaintext passes through a sequence of N-iterations of a round function whose working will be more precisely discussed successively. In each round, 2w-bit plaintext is divided into two equal halves and transformed with the help of secret key and round function. Working of round function remains the same in every iteration and every round produces 2w-bit output. It is worth mention here that the structure of each round is exactly identical, but, input parameters like intermediate ciphertext, secret key value, etc., are quite different. In each round, a unique key value is produced with the help of a key generating function. Finally, the ciphertext is generated after performing final permutation to the output of the last round.

For example, plaintext of size 2w-bit is divided into two equal halves portions termed left and right. As shown in Figure 2.7, right half of first round (R0) is fed directly into the left half of second round (L1) and processed with a secret key (K) in round function (F). Whereas, left half of first round (L0) is XOR’d with the processed output of round function. This procedure is repeated up to a total number of rounds (N) and the final combined value of left and right portions is treated as ciphertext.

Transformations made at each round are summarized through the following equations

(2.1)

(2.2)

Value of i = 1, 2…..n

In the Feistel network, encryption and decryption process are structurally identical. Therefore, in decryption process, ciphertext is used as input and the sub-key K_i is used in reverse sequence of encryption, i.e., K_n will be used in the first round, K_n-1 in the next and so on.

In order to prove the Feistel network is really reversible, let’s construct inverse of Feistel network’s round, i.e., if we are given Ri + 1 and Li + 1, we need to find out Ri and Li and so on. With the help of Figure 2.8, it can be said that: Ri = Li + 1 and Li = Ri+1 XOR F (Li + 1). The inverse of a round function in Feistel structure is shown in Figure 2.9.

It is clear that the inverse of a Feistel round is much similar to its original round or it can be said that they are the mirror image of each other. Thus, putting together the inverse of all these rounds, the inverse of the entire Feistel structure can be obtained.

2.3.2.2 Data Encryption Standard (DES)

Data Encryption Standard used to be the most popularly used symmetric block cipher algorithm. The purpose of DES was to provide a standard method for protecting sensitive commercial information. Feistel’s suggestion was to keep the key length to 128-bit. But, NBS decided to reduce the key length to be 56-bit. Reduction in size of key length proved as a fatal decision and in the year 1997, DES was broken by exhaustive search method. In the year 2000 Advanced Encryption Standard (AES) was finalized as the next-generation encryption algorithm. Nevertheless, DES was widely deployed in banking and commerce industry before being replaced by AES. These days, the successor of DES known as Triple Data Encryption Standard (TDES) is widely used conventional encryption algorithms. DES operates on a block of 64-bit plaintext and uses a 56-bit key. As shown macroscopically in Figure 2.10, DES has 16 Feistel rounds of encryption. Each round requires a different key (K1-K16) of 48-bit produced through a key generator. Key generation mechanism accepts the initial 56-bit key and subsequently generates unique keys of 48-bit for all the iterations of round function by performing some transformations. Due to reversible design, decryption in DES uses the same structure and key (reverse order).

DES is based upon Feistel network; therefore, its working is similar to Feistel network. The output of an i^th iteration in a round can be summarized as:

 (2.3)

 (2.4)

An initial and final permutation is used to add permutations in DES. Working of each portion of DES is discussed subsequently.

Expansion Permutation:

Expansion permutation expands 32-bit right half value (R_i-1) to 48-bit so that it can be XOR’d with 48-bit sub-key. In order to do so, R_i-1 is divided into 8 equal parts of 4-bit each. Now every 4-bit part will be expanded into 6-bit to make it a total 48-bit. This will be done by simply copying certain values of 4-bit input using a predetermined rule of expansion permutation table (Appendix). Numbers in the table indicate bit positions and each row in the table is having six values out of which border values are highlighted, and these highlighted values are added in each row of 4-bit to convert to 6-bit. The first row shows that the bit at positions 1, 2, 3, and 4 in the input will be copied at positions 2, 3, 4, and 5 in the output. The first position of output will be filled by the 32-bit value of the input and 6^th position of output will be filled by 5^th-bit value. Thus remaining rows of 4-bit will also be transformed into 6-bit. Figure 2.12 further demystify the approach used to convert the 32-bit value of the right half into 48-bit.

Substitution (S) Boxes:

This is a very important part of DES and adds the Shannon’s suggested confusion phenomena into it. S-boxes again convert the 48-bit value to 32-bit.

DES uses eight S-boxes having 6-bit input and 4-bit output. The substitution is based upon the predetermined table of 4 rows and 16 columns. This table is different for every S-box and contained 64 (4 * 16) random values which can be represented with 4-bit, i.e., 0 to 15. In order to choose a value from 64 values, 6-bit input is used. As shown in Figure 2.13 that first and last bit of the 6-bit input determines the particular row and bit ranging from 2 to 5 (4 bit) is used to find the column number of the table. Thus, the entry corresponding to the given row and column is taken as a 4-bit value corresponding to the given 6-bit value.

To further clarify the working of S-box, take an example whose graphical representation is shown in Figure 2.14. Suppose the 6-bit input for S-box-1 is: 101010, it means an entry in the table of S-box 1 corresponding to row 10 (2 in decimal) and column 0101 (5 in decimal) is-06 (binary equivalent 0110). Thus string 101010 will be converted to 0110. Each S-box is having a different Table that is shown in the Appendix 2.8.

Key Generator:

Actual key size in DES is 64-bit, but before the process starts, every 8^th bit of key, i.e., 8, 16, 24, 32, 40, 48, 56, 64, is discarded. These bits can be used for parity checking to ensure that the key does not contain any error. Key generator as shown in Figure 2.11, divides input 56-bit key into two equal halves of 28-bit each, namely, C₀ and D₀ and then pass through Permutation Choice-1 (PC-1) function for permutation. Every iteration performs Left Circular Shift on these 28-bit values. Schedule of left circular shift is also fixed in every round and is shown in Appendix 2.5. These shifted values fulfill the following two purposes:

1. Serve as input for the next iteration, i.e., C₁ and D₁
2. Serve as input to Permutation Choice-2 (PC-2) function resulting in a 48-bit key K_i. Permutation choice-2 function is basically a compression permutation as it compresses 56-bit key into 48-bit. This 48-bit key is used as the key for round function and process continued for remaining 15 rounds. Tables of PC-1 and PC-2 are predefined and shown in Appendix 2.3 and 2.4 respectively.

It is to be mentioned again that in the very beginning, 64-bit plaintext is divided into two equal halves namely left and right halves. All the transformations discussed so far are applicable to the only the right half. As depicted in Eq. (2.4), 32-bit output of function F mentioned above is XOR’d with 32-bit left half and produces the 32-bit right half for next round. 32-bit right half portion of previous round is copied directly into 32-bit left half of next round as per Eq. (2.3). The process is repeated for 16 iterations of round structure. The right and left output of 16^th round are swapped and it is termed as pre-output. Pre-output is delivered to Final Permutation (also called Inverse Initial Permutation) to produces the final 64-bit ciphertext output.

The decryption process in DES is same as of encryption. The difference is only in the sequence of the key, which is reversed key. It means key will be used as K₁₆, K₁₅, K₁₄, ... K₁ for all 16 rounds of decryption process respectively [1].

Linear Cryptanalysis:

Linear cryptanalysis is a known plaintext attach based upon the linear calculations of parity bit of all the three entities namely plaintext, ciphertext, and key. It requires 2⁴³ known plaintexts and ciphertext pairs to discover the key. The goal of linear cryptanalysis is to find out the secret key in less than 2⁵⁶ time, i.e., less time than the brute force attack. It is assumed that during linear cryptanalysis attacker possess many input and output pairs of plaintext and corresponding ciphertext.

Let C= DES (K, M), suppose for random K, M, there is dependence among message, ciphertext and plaintext such that if we XOR a subset of plaintext with a subset of ciphertext, it produces a subset of the key bit with a probability of ½.

If this probability is ½, it means both the sides are completely independent, i.e., given many pairs of message and cipher, an attacker cannot figure out the key bit. But, due to a bug in the design of 5^th S-box of DES, this probability is actually ½ + epsilon (Ɛ), not exactly ½. Tiny linearity in the 5^th S-box generates liner equations as given below through entire circuit:

For, DES, this Ɛ is very low (i.e., 1/2²¹ ~ 0.0000000477), but there is a bias that leads to a linear attack on DES. A theorem suggests that given 1/Ɛ² random pair of plaintext and corresponding ciphertext, the probability that the above relationship will be correct for more than ½ of the time is more than 97.7%. It is mentioned that for DES, Ɛ =1/2²¹, so with 2⁴² (i.e., 1/Ɛ²) pairs of plaintext and ciphertext, an attacker can find out XOR of some of the key bit. Therefore, around 14 key bit can be predicted using this relationship once by going through a backward direction and once by going through forwarding direction. When 14 bits are predicted, the brute force method can be applied to remaining 42 bits (56 − 14 = 42). Brute force on 42 bits will take 2⁴² time or roughly 2⁴³, which is very less than 2⁵⁶

Therefore, in linear cryptanalysis total attack time is 2⁴³ with 2⁴² random plaintext and ciphertext pairs [6].

2.3.2.3 Triple Data Encryption Standard (TDES)

As the computational capacity of modern machines is increasing tremendously, it is not difficult to brute force a 56-bit long key. Therefore to achieve more security a variation of DES named Triple DES (TDES) is in use. The term variation is used because TDES is not a new algorithm and is based upon DES algorithm differing only in key length.

As per its name, it applies DES algorithm three times on a single block of plaintext with a different key each time. Parameters of 3DES are 64-bit block size, 48 rounds (3 * 16), and key size 3 * 56 = 168-bit. TDES was standardized in 1999 and is in use of the electronic payment industry. The layout of 3DES is shown in Figure 2.15.

TDES uses three keys each of 56 bit length and follow the sequence of Encryption-Decryption-Encryption that is summarized as:

Where E_k denotes encryption of plaintext using key k and Dk denotes decryption using key k.

Readers might be wondering why its Encryption, Decryption, Encryption instead of Encryption, Encryption, Encryption. So, to justify this, suppose all three keys are the same, i.e., k₁ = k₂ = k₃ = k, then the above-stated formula becomes:

Key options in TDES:

TDES algorithm uses three consecutive keys viz. k₁, k₂, k₃ so keying option can be described in Table 2.8. Option 1 is TDES with total key size 168-bit. Option 2 uses two keys with key size 112 also known as double DES and option 3 is simple DES.

Option	Description	Key size	Security level
1.	All keys are independent	56 * 3 = 168	High
2.	k1, k2 are independent while k3=k1	56 * 2 = 112	More than DES
3.	All three keys are same	56	Equal to DES

Meet-In-The-Middle attack (MITM) on 2DES:

Suppose, given a pair of message M = {m₁, m₂,….m₁₀} and corresponding ciphertext C = {c₁,c₂…c₁₀}, and the goal is to find out key pairs {k₁, k₂} such that

If we apply decryption with key k1 on both the side of this equation, then:

This final equation says that key k₂ encrypts plaintext M to a value, which is same to the decryption of cipher C by key k₁. As shown in Figure 2.16, this attack is called “meet in the middle” and it will take time lesser than exhaustive search.

Total time taken by “meet-in-the-middle” attack on 2DES is around 2⁶³ that is very less than 2¹¹² of exhaustive search. 2⁶³ is really very less time and approximately equal to the time taken by an exhaustive search on DES. Therefore, 2DES is not a recommended block cipher. What if the same attack is applied to 3DES? Figure 2.17 indicates the point where “meet-in-the-middle” attack can be applied to 3DES.

In the forward direction, a table of 2⁵⁶ entries of encryptions of plaintext is to be created, and then try to decrypt cipher with all 2¹¹² possible key values until a collision in the encryption table is found. But, this leads to an approximate 2¹¹² time that is still much-much larger to brute force. Therefore, 3DES is the NIST standard and DES is no more used in its original form.

2.3.2.4 International Data Encryption Algorithm (IDEA)

IDEA is eight rounds, 64-bit symmetric block cipher using 128-bit key size. This algorithm provides full protection of information from unauthorized access by intruders. IDEA is far better in security than 56-bit key based widely used Data Encryption Standard (DES). Instead of look-up tables or S-Box used in DES, IDEA uses a complex transform by the combination of XOR, binary addition and multiplication of 16-bit integers.

The IDEA algorithm depicted graphically in Figure 2.18 begins by dividing 64-bit Input block into four equal words of 16-bit each, namely A, B, C, and D. IDEA uses eight rounds of computation and each requires six subkeys (16-bit each). After eight rounds of computations, the output transformation process uses four subkeys. Thus, entire IDEA encryption process uses 52 number of (i.e., 8 * 6 + 4) 16-bit subkeys that are generated by an initial 128-bit master key.

Key Management:

Master key (128-bit) is initially divided into eight 16-bit words and is used as first eight subkeys out of 52 sub keys as mentioned above. Subsequent subkeys (52 – 8 = 44) for the next rounds are generated by rotating 25-bit left to an initial 128-bit master key. The starting process of dividing master key into eight sub keys is again repeated for the next rounds.

2.3.2.5 Blowfish

Blowfish is publically available general-purpose symmetric block cipher encryption algorithm which is based upon Feistel structure. Blowfish was proposed as a replacement to DES which was getting older and slower. It was proposed as a software encryption algorithm that could work easily on 32-bit machines.

The similarity of Blowfish with its predecessor is the use of 64-bit block size of the plain text. However, Blowfish uses a variable key length ranging from 32 to 448-bit. Normally, Blowfish uses 16 rounds of Feistel structure.

Encryption:

The 64-bit input plaintext is divided into two equal halves, namely, RE and LE. Then, following operations are repeated for each round function, i.e., repeated 16 times.

The above expressions can be generalized as:

Here ⊕ denotes bitwise exclusive-OR, F is the function used in each round, and P denotes that array holding sub-keys.

As shown in Figure 2.19 the output of the 16^th round is to generate final encryption in the following way:

Basically, the output of the 16^th round is swapped again to produce LE₁₇ and RE₁₇, which are merged to produce final 64-bit ciphertext. Figure 2.19 indicates that function F in a round is having four S-boxes and each S-box takes 8-bit input and produces a 32-bit output which is XOR’d and added to produce 32-bit output.

Decryption process in Blowfish uses encryption structure with reverse oder key. But, first P₁₇ and P₁₈ are XOR’d with ciphertext, then, remaining sub-keys are used in reverse order.

Blowfish uses a very large key which makes it more robust toward any security attack. Generation of a key in advance makes it suitable for applications, which do not need new key often. Blowfish was designed to run in software-based encryption so its encryption speed is fast. Moreover, it is not patented that makes it more easy to use in many applications.

However, producing key is a slow and intensive task in Blowfish that might be a limitation of the same in many areas. It is also found that the first four rounds of Blowfish can be compromised by second order differential attack. Therefore, the creator of Blowfish proposed its successor Twofish encryption algorithm.

2.3.2.6 CAST-128

In order to thwart against linear and differential cryptanalysis, Carlise Adams and Stafford Tavares proposed CAST encryption algorithms in 1996. CAST is a basically a family of symmetric key encryption/decryption algorithms and CAST-128 is a prevalent algorithm of this family that uses a 128-bit long key. Like DES, CAST-128 is also based upon the well-proven design principles of Feistel structure, but, it provides strict avalanche criteria which was absent in DES. Interestingly, it provides better performance by using lesser rounds than DES. CAST incorporates certain changes in round function and key schedule that makes it more suitable for software implementation too. The main idea of CAST algorithm is to use large S-box to thwart against linear and differential cryptanalysis, i.e., it uses 8 × 32 size S-box rather than 6 × 4 size of DES. It uses exclusive OR, addition and subtraction modulo 2³² operations. It uses eight S-boxes from which four are used in key scheduling while four are used in round function.

CAST-128 seems structurally identical to Blowfish. But, CAST-128 uses fixed length S-boxes while Blowfish uses key-dependent S-boxes unlike.

The similarity of CAST-128 with its predecessor is the use of 64-bit block size of plaintext. However, CAST-128 uses a variable key length ranging from 40 to 128-bit (128-bit key size is recommended). Key range increments in octets, i.e., 48-bit will be the next possible key size after 40-bit. Normally, CAST-128 uses 12 rounds of Feistel structure if key length is lesser than 80-bit, otherwise, CAST-128 uses all 16 rounds. In case of shorter key lengths than 128-bit, the key is padded with zero bytes. Example shown in Table 2.9 illustrates the padding of key and sample plaintexts (in octets).

Encryption:

Input plaintext block of 64-bit is divided into two equal halves of 32-bit each, namely, L₀ and R₀. Following iterations are calculated for all the 16 rounds of CAST encryption:

40-bit key	12 32 26 89 67
Padded 128-bit key	12 32 26 89 67 00 00 00 00 00 00 00 00 00 00
64-bit plain text	AB EF 24 01 34 13

Here F is the round function and CAST-128 uses three structurally identical round functions having a basic difference in the choice of operations as shown in Figure 2.20. The major difference in round functions is the change in the position of basic operations viz. addition modulo 2³², subtraction modulo 2³², and exclusive OR. Figure 2.20 shows only the first three rounds of CAST-128 to indicate that three types of functions are used one after another. Then, this pattern is repeated for remaining rounds of CAST-128.

Function F consists of four S-boxes having 8-bit input and 32-bit output. To understand the working of function F in a round function, an intermediate variable X is used to store the result of keys masking and rotations with the right half of plaintext/intermediate ciphertext. Thus, the value of X for the first round is:

This intermediate value X is divided into four equal parts each of 8-bit and fed into four S-boxes respectively to add non-linearity. The output of S-boxes is combined using three different ways in all the three types of functions in the round. The final output of the function in round 1 in the form of intermediate value X is as follows:

Here S₀, S₁, S₂, and S₃ are the 32-bit output of four S-boxes used in the function and ⊕ is eXclusive OR, − is subtraction modulo 2³², and, + is addition modulo 2³².

Similarly, a reader can derive the expressions for rounds 2 and 3. After the end of the 16^th round, both halves are swapped and merged to produce 64-bit ciphertext.

Decryption process in CAST-128 uses the same encryption structure with key in reverse sequence.

Although CAST-128, which is also known as CAST5 is patented by Entrust, it can be used for profitable and non-profitable use without any royalty. Mostly 3DES is used to secure the communication of multimedia objects in an e-mail through Secure/Multipurpose Internet Mail Extensions (S/MIME). But, 3DES is found slow in many cases; therefore, according to internet drafts, use of CAST-128 in securing S/MIME provides good speed with security. E-mail encryption standard Pretty Good Privacy (PGP) and open source based GNU Public Guard (BPG) also makes use of CAST-128.

CAST-128 is vulnerable to linear cryptanalysis through known plaintext attack. Therefore, CAST-256 is proposed as a robust successor of CAST-128 in RFC 2612. Table 2.10 summarizes the differences between CAST-128 and Blowfish encryption algorithm [7].

Practice Set

APPENDIX A: Tables of Data Encryption Standard [1]