S. Erfani, ECE Dept., University of Windsor 0688-590-18 Network Security
Conventional Encryption: Modern Technologies
We mentioned that the statistical weakness in substitution ciphers is that they don’t change the frequency of alphabetic letters. For example, if a substitution cipher scheme were used to obtain the ciphertext:
CFGPSFGJWF
A cryptanalyst may initially guess that the most frequent ciphertext letter (F) is corresponding to a disguised E. If this guess is correct, the cryptanalyst is on the road to cracking the ciphertext. The 2nd best guess is if (F) is not really a disguised (E), it may then be a (T). The cryptanalyst can also guess that the most frequent two-letter pattern in longer ciphertext may correspond to a (TH), and so forth.
Note that with the help of computers, statistical analysis for cryptanalytic purposes can be prepared much quicker.
Note 1:We need to eliminate statistical relationship between the ciphertext and the underlying plaintext.
Note 2:Combining transposition and substitution diffuses the statistical structure of plaintext over the ciphertext. This method is referred to as diffusion. Diffusion dissipates or disperses parts of letters throughout the ciphertext.
Note 3:In addition to diffusion, we may need to create confusion to prevent the cryptanalyst from using ciphertext to figure out the secret encryption key. Confusion usually means that the cipher scheme should be complex such that even one can figure out some ciphertext patterns, she cannot use the cipher method and pattern to figure out the secret key. As cipher scheme or an algorithm providing good confusion will have a complex functional relationship between the plaintext /key pair and the ciphertext.
Note 4:Confusion obscures the relationship between the plaintext and the ciphertext, while diffusion dissipates the redundancy of the plaintext by spreading it out over the ciphertext.
Note 5: Ciphers that use confusion and diffusion are called product ciphers. Each application of confusion and diffusion is called a round. Product ciphers that use many rounds are called iterated product ciphers. The idea is to make the encryption function so complex and involuted that makes it almost impossible to discover the encryption key.
Note 6:The computational complexity of an encryption algorithm is often measured by two variables:
-T (for time complexity)
-S (for space complexity, or computing memory requirement)
Note 7:An encryption algorithm is said to be computationally secure if the following two criteria are met:
-The time complexity exceeds the useful lifetime of the information.
-The space complexity exceeds the value of the encrypted information.
2.1P-box and S-box
Transposition and substitution can be implemented with simple, hardware circuits. For example, Fig. 1 below shows a device, called P-box (P stands for permutation), used to implement the following transposition cipher on an 8-bit input:
X / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8(x) / 4 / 7 / 1 / 8 / 2 / 3 / 5 / 6
P-box
Fig. 1
By appropriately internal wiring, a P-box can be made to perform any transposition, and do it at practically the speed of light.
Substitutions can be performed by S-boxes (S stands for substitution), as
shown in fig. 2 below.
S-box
Fig. 1
Fig. 2
In this example, a 3-bit plaintext is entered into the S-box, and 3-bit ciphertext is output. The 3-bit input selects one of the eight lines exiting from the encoder and sets it to 1; all the other lines are 0. The second stage in an S-box is a simple P-box, as described earlier. The third stage is a decoder, which encodes the resulting output line of the P-box in binary again. For example, if the eight octal numbers 0 1 2 3 4 5 6 7 were input one after another, the output sequence in Fig. 2 would be 2 4 5 0 6 7 1 3. In other words, 0 has been replaced by 2; 1 has been replaced by 4, etc. Again by appropriately wiring of the P-box inside the S-box, any substitution can be accomplished.
The real power of these basic elements only becomes apparent when we cascade a whole series of boxes to form a product cipher, as shown in Fig. 3 below.
Product Cipher
Fig. 3
In this example, 12 input lines are transposed by the first stage. In the second stage, the input is broken up into four groups of 3 bits, each of which is substituted independently of each others. By including four stages of permutation-substitution network in this product cipher, the output is made to be an exceedingly complicated function of the input.
2.2The Feistel cipher
Feistel proposed the use of a cipher that alternates substitutions and permutations, as we described above. This is a practical implementation of a product cipher that alternates confusion and diffusion functions. Fig. 4 below shows the Feistel cipher scheme.
Fig. 4 – Feistel Cipher
The inputs to the encryption algorithm are a plaintext block of length 2w bits and a key K. The plaintext block is divided into two halves, L0 and R0. The two halves of the data pass through n rounds of processing and then combine to produce the ciphertext block. Each round i has inputs Li-1 and Ri-1, derived from the previous round, as well as a subkey Ki, derived from the overall K. in general, the subkeys are different from K and from each other.
All rounds have the same structure. A substitution is performed on the left half of the data. This is done by applying a round function F to the right half of the data and then taking the exclusive OR of the output of that function and the left half of the data. The round function has the same general structure for each round but is parameterized by the round subkey Ki . Following this substitution, a permutation is performed that consists of the interchange of the two halves of the data.
Note 1:The Feistel structure is a particular form of the substitution permutation network (SPN) proposed by Claude Shannon in his paper in 1949.
Note 2:The security of a Feistel structure depends on the choice of the following parameters and design features:
(1) Block Size:Larger block sizes mean greater security. A block size of 64 bits is reasonable and is nearly universal in block cipher design.
(2)Key Size:Larger key size means greater security but may decrease encryption/decryption speed. Key sizes of 64 bits or less are now widely considered to be inadequate, and 128 bits has become a common size.
(3)Number of Rounds: The multiple rounds offer increasing security. A typical size is 16 rounds.
(4)Subkey Generation Algorithm:Greater complexity in this algorithm should lead to greater difficulty of cryptanalysis.
(5)Round Function:Greater complexity generally means greater resistance to cryptanalysis.
Note 3:Feistel cipher is an example of product ciphers, in which one encryption is applied to the result of another. Product ciphers resemble the product or composition of two functions in mathematics. Therefore, if ek1(.) and e’k2(.) are two transposition ciphers following a regular pattern, their product ek1(ek2(y)) is also a regular pattern. That is, the product cipher formed by using the output of ek1(.) as the input to ek2(.) is a complicated function, but it is still regular.
Note 4:The Caesar’s substitution and mono-alphabetic transposition ciphers are stream ciphers; i.e., they convert one symbol of plaintext immediately into a symbol of ciphertext. Block cipher encrypts a group of plaintext symbols as one block. Hill cipher, Feistel cipher and other transpositions are examples of block ciphers. Block ciphers work on blocks of plaintext and produce blocks of ciphertext, as shown for Feistel cipher.
Note 5:In a Feistel cipher, shown in Fig. 4, each state is divided into two halves of equal length, say Li and Ri. The round function g is:
G(Li-1, Ri-1, Ki) = (Li, Ri)
where:
Li = Ri-1
Ri = Li-1 f (Ri-1, Ki)
The exclusive OR (XOR) has the following properties:
A B C = A B C
D D = 0
E 0 = E
Therefore the function f in Feistel cipher does not need to satisfy any type of one-to-one property; i.e., injectivity property. This is because a Feistel-type round function is always invertible, given the round key, as shown below:
Li-1 f (Ri-1,Ki) f (Ri-1,Ki) = Ri f (Ri-1,Ki)
Ri-1 = Li
Note 6:(Feistel Decryption Algorithm)
The process of decryption with a Feistel cipher is essentially the same as the encryption process. The rule is as follows:
“Use the ciphertext as input to the Feistel structure, but use the subkey Kiin reverse order”
That is, use Kn in the first round, Kn-1 in the second round, and so on until K1 is used in the last round. Therefore, we need not to implement two different algorithms (or structures), one for encryption one for decryption.
2.3Long and Random Number Keys
It seems that the safety of the Feistel and similar ciphers depends on the size and randomness of the key used. Also, XOR used in the round function is a basic machine instruction on computers, making it easier to implement this algorithm, as shown in the following figure.
EncryptionDecryption
Fig 5 – Use of Long Size Key.
2.4Symmetric Encryption Systems
The algorithms presented in this chapter so far are all single key or conventional encryption algorithms, in which both the encryptor and the decryptor use the same key, which must be kept secret. Single key systems are called symmetric encryption systems or secret key, or sometimes private key systems.
The symmetric systems provide a two-way secure channel to their users. Alice and Bob share a secret key, and they can both encrypt information to send to each other as well as decrypt information received from the other.
The symmetry of this situation is a major advantage. However, symmetric key systems have several difficulties:
(a)If the key is compromised, the opponents, such as Oscar, can immediately decrypt all encrypted information they have available. For this reason, in practice, the keys are changed fairly frequently so that a compromised key will reveal only a limited amount of information.
(b) Distribution of keys becomes a problem. Keys must be transmitted with utmost security. For applications that extend throughout the world, this can be a complex task. One approach is to distribute the keys pieces under separate channels, so that any one discovery will not produce full key. This approach is shown in the following Fig 6.
K1 / K2 / K3 / K4 / k5Encrypted Channel
Courier
K2 / K5keykey
Fig 6 – Key Distribution in Pieces
(c) It can be shown that the number of keys increases with the square of the number of people exchanging secret information.
(d) The symmetric key encryption systems described so far have been relatively weak, vulnerable to various cryptanalysis attacks. A secure symmetric key system must be based on mathematically complex problems, problems that have interested mathematicians for years. In the next section we describe a secure encryption algorithm adopted in 1977 by the USA National Institute of Standards and Technology (NIST) called Data Encryption Algorithm (DEA) or Data Encryption Standard (DES).
2.5The Data Encryption Standard ( DES )
The Data Encryption Standard (DES) is a system developed for the U.S. government for use accepted as a cryptographic standard both in the United States and aboard. Many hardware and software systems have been designed using the DES. However, recently its adequacy has been questioned.
2.5.1Background and History
The new era in cryptography began in the late 1960’s, when companies began needing secure ways to send files. At the time, there was no industry standard – no widely accepted encryption method that had a universal seal of approval.
Financial institutions in particular wanted a standard encryption method that they could have confidence in and could use for data exchange. Because U.S. national security depends on secure cryptography, government agencies involved in cryptography, such as the National Security Agency (NSA) had not been open with their expertise. [Some people say that NSA stands for “No Such Agency” or “Never Say Anything”!].
In 1972, NIST, then known as the National Bureau of Standards, issued a call for proposal for a public encryption algorithm. This led ultimately to the adoption of Data Encryption Standard, or DES, which became the most widely used cryptosystem in the world. DES was developed at IBM, as a modification of an earlier system known as Lucifer. Much of the underlying DES cipher research is credited to the IBM researcher, Horst Feistel, who in 1967 began experimenting with a combination of substitution and transposition ciphers. The Feistel Cipher was described earlier in this chapter. Before computers, transposition was difficult to mechanize and too complex to do by hand. Increases in the size of computer memory made it possible for Feistel to use transposition in his system. Feistel blocks are still used in many (if not most) symmetric encryption systems.
DES did not evolved into the standard without significant discussion and even suspicion by some participants–suspicion that still continues. NIST requested and received assistance from NSA on DES development. Some people have said that NSA modified DES so that the agency could easily reclaim plaintext without using a brute force attack, installing what is commonly known as a trapdoor function. NSA shortened the secret key originally proposed by IBM to 56 bits from 128 bits.
Even in the 1970’s, it was argued that a special – purpose machine could be built to carry out a known plaintext attack, which would essentially perform an exhaustic search for the key. That is given a 64-bit plaintext x and corresponding ciphertext y, every possible key would be tested until a key K is found such that
ek (x) = y. As early as 1977, one could build a VLSI chip, which could test106 keys per second. A machine with 106 chips could search the entire key-space in about a day.
Some people believe that NSA altered IBM’s algorithm to ensure that IBM had not secretly included its own trapdoor function. Some people also believe that NSA wanted to control the use of DES and expected DES to be implemented only in hardware.
Despite the controversy, DES was adopted as the federal standard for unclassified document in 1977, as Federal Information Processing Standard 46 (FIPS PUB 46). It is the most widely used cryptographic method in history.
The 1977 DES standard mandated a review every five years. In 1983, DES was approved for five more years. Then in 1993, DES was again approved for yet another five years. In 1997, NIST solicited candidates for a new secret key encryption standard, Advanced Encryption Standard (AES). NIST announced the candidates for AES, successor to DES, in 1999, and in October 2000, NIST selected Rijndael . (See < >).
2.5.2Description of DES
DES is a special type of iterated cipher called a Feistel cipher. We described the basic form of a Feistel cipher earlier. An outline of DES is shown in Fig 7. Plaintext is encrypted in blocks of 64 bits, yielding 64 bits of ciphertext. In other words, DES is a 16-round Feistel cipher having block length 64; it encrypts a plaintext bit-string x (of length 64) using a 56-bit key K, obtaining a ciphertext bit-string ( of length 64 ). The algorithm, which is parameterized by this 56-bit key, has 19 distinct stages. The first stage is a key–independent transposition (permutation) on the 64-bit plaintext. The last stage is the exact inverse of this transposition. The stage prior to the last one exchanges the leftmost 32bits with the rightmost 32 bits. The remaining 16 stages are consisting of 16 iterations of the identical functions but are parameterized by different subkeys. The algorithm has been designed to allow decryption to be done with the same key as encryption. The steps are just run in the reverse order.
The left–hand side of the figure shows that first the 64-bit plaintext passes through the initial permutation (IP), which rearranges the bits to produce the permutated input.
Fig 7 – General Description of DES Encryption Algorithm
This is followed by 16 rounds of iterations; the left and right halves of the output from round 16 are swapped to produce an input to be passed through a permutation function (IP)-1, to produce the 64bit ciphertext.
The righthand portion of Figure 7 shows the way in which the 56bit key is used. Initially the key is passed through a permutation function (i.e., permuted choice 1 in this figure). Then, for each of the 16 iterations, a subkey Ki is produced by the combination of a left circular shift and a permutation (permutated choice 2 in this figure). The permutation function is the same for each iteration, but a different subkey is produced because of the repeated shifting of the key bits.
The operation of one of these 16 rounds is illustrated in Fig. 8 (above). Each round takes two 32bit inputs and produces two 32bit outputs. The left and right halves of each 64bit intermediate value are treated as separate 32bit quantities, labeled L (left) and R (right). The overall processing at each iteration can be summarized in the following formulas:
where denotes XOR function. That is, the left output is simply a copy of the right input. The right output is the bit-wise EXCLUSIVE OR of the left input and a function of the right input and the key for this round, Ki. All the complexity lies in this function. This complex function involves both permutation and substitution operation.
The function F consists of four steps, carried out in sequence. First, a 48bit number, E, is constructed by expanding the 32bit Ri-1 according to a fixed transposition and duplication rule. Second, E and Ki are EXCLUSIVE ORed together. This output is then partitioned into eight groups of 6 bits each, each of which is fed into a different “Sbox”. Each of the 64 possible inputs to an Sbox is mapped onto a 4bit output. This step uses eight Sboxes. Each Sbox mapped six bits to four bits. Finally, the 84 bits, outputs of eight Sboxes, are passed through a permutation operator, i.e. a Pbox.
In each of the 16 iterations, a different key is used. Figure 7 shows that before the algorithm starts, a 56bit transposition is applied to the key. Figure 8 shows that just before each iteration, the key is partitioned into two 28bit units, each of which is rotated left (i.e. circular left shift) by a number of bits dependent on the iteration number. Ki is derived from this rotated key by applying yet another 56bit transposition to it. A different 48bit subset of the 56bit is extracted and permuted on each round.