cs-lecture3-DES.pdf

Lecture 3 -symmetric key cryptography (DES) 3.1 Symmetric and Asymmetric Encryption Systems Recall that the two basic kinds of encryptions are symmetric (also called "secret key") and asymmetric (also called "public key"). a. Symmetric Encryption Systems  Symmetric al...

Lecture 3 -symmetric key cryptography (DES) 3.1 Symmetric and Asymmetric Encryption Systems Recall that the two basic kinds of encryptions are symmetric (also called "secret key") and asymmetric (also called "public key"). a. Symmetric Encryption Systems  Symmetric algorithms use one key, which works for both encryption and decryption.  The decryption algorithm is closely related to the encryption one. (For example, the Caesar cipher with a shift of 3 uses the encryption algorithm "substitute the character three letters later (addition operation) in the alphabet" with the decryption "substitute the character three letters earlier (subtraction operation) in the alphabet.") (i.e decryption is the reverse of encryption)  Provide a two-way channel to their users: A and B share a secret key, and they can both encrypt information to send to the other as well as decrypt information from the other.  As long as the key remains secret, the system also provides authentication proof that a message received was not fabricated by someone other than the declared sender. (Authenticity is ensured because only the legitimate sender can produce a message that will decrypt properly with the shared key)  Key distribution is the major difficulty in using symmetric encryption How do A and B obtain their shared secret key? And only A and B can use that key for their encrypted communications. If A wants to share encrypted communication with another user C, A and C need a different shared key. In general, n users who want to communicate in pairs need n * (n - 1)/2 keys, if n =6 then the number of keys = 6*(6-1)/2= 6*5/2=15. In other words, the number of keys needed increases at a rate proportional to the square of the number of users. 18  Lecture 3 -symmetric key cryptography (DES) b. Asymmetric Encryption Systems Public key systems, on the other hand, excel at key management. By the nature of the public key approach, you can send a public key in an e-mail message or post it in a public directory. Only the corresponding private key, which presumably is kept private, can decrypt what has been encrypted with the public key. But for both kinds of encryption, a key must be kept well secured. Once the symmetric or private key is known by an outsider, all messages written previously or in the future can be decrypted (and hence read or modified) by the outsider. So, for all encryption algorithms, key management is a major issue. It involves storing, safeguarding, and activating keys. 3.2 Stream and Block Ciphers  Stream ciphers; that is, they convert one symbol of plaintext immediately into a symbol of ciphertext. (Most of the ciphers we have presented so far are stream cipher with the exception is the columnar transposition cipher.)  The transformation depends only on the symbol, the key, and the control information of the encipherment algorithm.  A model of stream enciphering is shown in Figure below.  Problem: Some kinds of errors, such as skipping a character in the key during encryption, affect the encryption of all future characters. However, such errors can sometimes be recognized during decryption because the plaintext will be properly recovered up to a point, and then all following characters will be wrong. If that is the case,  Solution: the receiver may be able to recover from the error by dropping a character of the key on the receiving end. Once the receiver has successfully recalibrated the key with the ciphertext, there will be no further effects from this error.  To address this problem and make it harder for a cryptanalyst to break the code, we can use block ciphers. A block cipher encrypts a group of plaintext symbols as one block. 19  Lecture 3 -symmetric key cryptography (DES)  The columnar transposition and other transpositions are examples of block ciphers. In the columnar transposition, the entire message is translated as one block. The block size need not have any particular relationship to the size of a character. Block ciphers work on blocks of plaintext and produce blocks of ciphertext, as shown Figure below. Comparing Stream and Block Algorithms Stream Encryption Block Encryption Algorithms Algorithms Advantages Speed of transformation. Because each High diffusion. symbol is encrypted without regard for any Information from the other plaintext symbols, each symbol can be plain-text is diffused into encrypted as soon as it is read. Thus, the time several ciphertext to encrypt a symbol depends only on the symbols. One ciphertext encryption algorithm itself, not on the time it block may depend on takes to receive more plaintext. several plaintext letters. Low error propagation. Because each symbol Immunity to insertion of is separately encoded, an error in the symbols. Because blocks encryption process affects only that of symbols are character. enciphered, it is impossible to insert a single symbol into one block. The length of the block would then be incorrect, and the decipherment would quickly reveal the insertion. Disadvantages Low diffusion. Each symbol is separately Slowness of encryption. enciphered. Therefore, all the information of The person or machine that symbol is contained in one symbol of the using a block cipher ciphertext. must wait until an entire block of plaintext symbols has been received before starting 20  Lecture 3 -symmetric key cryptography (DES) the encryption process. Susceptibility to malicious insertions and Error propagation. An modifications. Because each symbol is error will affect the separately enciphered, an active interceptor transformation of all who has broken the code can splice together other characters in the pieces of previous messages and transmit a same block. spurious new message that may look authentic. 3.3 Confusion and Diffusion  Confusion: An encrypting algorithm should take the information from the plaintext and transform it so that the interceptor cannot readily recognize the message; he should not be able to predict what will happen to the ciphertext by changing one character in the plaintext.  An algorithm providing good confusion has a complex functional relationship between the plaintext/key pair and the ciphertext. In this way, it will take an interceptor a long time to determine the relationship between plaintext, key, and ciphertext; therefore, it will take the interceptor a long time to break the code.  As an example, consider the Caesar cipher. This algorithm is not good for providing confusion because an analyst who deduces the transformation of a few letters can also predict the transformation of the remaining letters, with no additional information.  By contrast, a one-time pad (with a key effectively as long as the message length) provides good confusion because one plaintext letter can be transformed to any ciphertext letter at different places in the output. There is no apparent pattern to transforming a single plaintext letter.  Diffusion: The cipher should also spread the information from the plaintext over the entire ciphertext so that changes in the plaintext affect many parts of the ciphertext.  Good diffusion means that the interceptor needs access to much of the ciphertext to be able to infer the algorithm. 3.4 The Data Encryption Standard  The Data Encryption Standard (DES) , a system developed for the U.S. government, was intended for use by the general public. It has been officially accepted as a cryptographic standard both in the United States and abroad.  The call specified desirable criteria for such an algorithm: 1. able to provide a high level of security 2. specified and easy to understand 21  Lecture 3 -symmetric key cryptography (DES) 3. publishable so that security does not depend on the secrecy of the algorithm 4. available to all users 5. adaptable for use in diverse applications 6. economical to implement in electronic devices 7. efficient to use 8. able to be validated 9. exportable  DES is a careful and complex combination of two fundamental building blocks of encryption: substitution and transposition. The algorithm derives its strength from repeated application of these two techniques, one on top of the other, for a total of 16 cycles.  The algorithm begins by encrypting the plaintext as blocks of 64 bits.  The key is 64 bits long, but in fact it can be any 56-bit number. (The extra 8 bits are often used as check digits and do not affect encryption in normal implementations.) The user can change the key at will any time there is uncertainty about the security of the old key.  The algorithm, leverages the two techniques Shannon identified to conceal information: confusion and diffusion. That is, the algorithm accomplishes two things: ensuring that the output bits have no obvious relationship to the input bits and spreading the effect of one plaintext bit to other bits in the ciphertext. Substitution provides the confusion, and Transposition provides the diffusion.  DES uses only standard arithmetic and logical operations on numbers up to 64 bits long, so it is suitable for implementation in software on most current computers. 3.5 Overview of the DES Algorithm 1. Input to the DES is divided into blocks of 64 bits. 2. The 64 data bits are permuted by a so-called initial permutation. 3. Next begins the sequence of operations known as a cycle. 3.1 The 64 permuted data bits are broken into a left half and a right half of 32 bits each. 3.2 The key is shifted left by a number of bits and permuted. 3.3 The key is combined with the right half, which is then combined with the left half. The result of these combinations becomes the new right half; 3.4 The old right half becomes the new left half. 4. The cycles are repeated 16 times. 22  Lecture 3 -symmetric key cryptography (DES) 5. After the last cycle is a final permutation, which is the inverse of the initial permutation 23 Lecture 3 -symmetric key cryptography (DES) 24  Lecture 3 -symmetric key cryptography (DES) 3.5.1 Details of Each Cycle of the Algorithm Each cycle of the algorithm is really four separate operations. 1. a right half is expanded from 32 bits to 48 by repeating certain bits(expansion permutations). 2. Then, it is combined with a 48-bit of the key (the 56-bit key is reduced to 48 bits by choosing only certain bits (permuted choices). 3. The result of this operation is then substituted for another result and condensed to 32 bits at the same time. 4. The 32 bits are permuted and then combined with the left half to yield a new right half. This whole process is shown in Figure below Mathematical representation of a single round Li=Ri-1 Ri = Li-1 ⊕f(Ri-1,Ki), f(Ri-1, Ki)=P(S(E(Ri-1) ⊕ Ki)) P: permutation S: substitution E:expansion 25  Lecture 3 -symmetric key cryptography (DES) 3.5.1.1 Types of permutation DES algorithm use 3 types of permutation as shown in figure below 1. Permutation: this type is implemented in IP,IP-1,P,PC-1 tables, and have the following properties:  n*n input/output, one to one mapping  The Permutation table are read from left to right in descending rows.  In the IP table, the plaintext bytes are sorted into columns so that the odd numbered bits are in the lower half,and the even number are in the upper halve. IP-1 order the bit in the coloum at the even index (2,4,6,8) then return to odd index(1,3,5,7) IP IP-1 58 50 42 34 26 18 10 2 40 8 48 16 56 24 64 32 60 52 44 36 28 20 12 4 39 7 47 15 55 23 63 31 62 54 46 38 30 22 14 6 L0 38 6 46 14 54 22 62 30 64 56 48 40 32 24 16 8 37 5 45 13 53 21 61 29 57 49 41 33 25 17 9 1 36 4 44 12 52 20 60 28 59 51 43 35 27 19 11 3 R0 35 3 43 11 51 19 59 27 61 53 45 37 29 21 13 5 34 2 42 10 50 18 58 26 63 55 47 39 31 23 15 7 33 1 41 9 49 17 57 25 26  Lecture 3 -symmetric key cryptography (DES) P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 DES initial permutation and inverse (IP and IP-1, P) 2. Expansion Permutation: its uses in the E- table, and has the following properties  n*m, one to many The expansion permutes the order of the bits and also repeats of 16 bit positions in the E-table. It is this, which gives the expansion of the 32-bit into a new 48-bit block. . The expansion has two purposes: to make the intermediate halves of the ciphertext comparable in size to the key and to provide a longer result that can later be compressed. E E-bit 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 27  Lecture 3 -symmetric key cryptography (DES) 3. Choice permutation: used in PC-1,PC-2 and has the following properties n*m, many to one mapping. 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 Permuted-Choice-1 (PC1) Permuted-Choice-2 (PC2) 3.5.1.2 Substitutions  Substitutions are performed by eight S-boxes.  An S-box is a permuted choice function by which six bits of data are replaced by four bits.  The 48-bit input is divided into eight 6-bit blocks, identified as B1B2... B8; block Bj is operated on by S-box Sj.  The S-boxes are substitutions based on a table of 4 rows and 16 columns. Suppose that block Bj is the six bits b1b2b3b4b5b6. Bits b1 and b6, taken together, form a two-bit binary number b1b6, having a decimal value from 0 to 3. Call this value r. Bits b2, b3, b4, and b5 taken together form a 4-bit binary number b2b3b4b5, having a decimal value from 0 to 15. Call this value c. The substitutions from the S-boxes transform each 6-bit block Bj into the 4-bit result shown in row r, column c of section Si.  For example, assume that block B7 in binary is 010011. Then, r = 01 = 1 and c = 1001 = 9. The transformation of block B7 is found in row 1, column 9 of Sbox- 7. The value 3 = 0011 is substituted for the value 010011. 28 Lecture 3 -symmetric key cryptography (DES) 29  Lecture 3 -symmetric key cryptography (DES) 3.6 Key Transformation  The 64-bit key immediately becomes a 56-bit key by deletion of every eighth Bit using PC-1 table.  At each step in the cycle, the key is split into two 28-bit halves, the halves are shifted left circularly by a specified number of digits, the halves are then pasted together again, and 48 of these 56 bits are permuted using PC-2 table to use as a key during this cycle.. For the full 16 round of DES, the schedule of left shifts is: Key iteration 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Left Shift 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 30  Lecture 3 -symmetric key cryptography (DES) 3.7 The Decryption Process The same DES algorithm is used both for encryption and decryption. This result is true because cycle (i) drives from cycle (i-1) Li = Ri-1. Ri = Li-1 ⊕ f (Ri-1, Ki). Where ⊕ is the exclusive-or operation, and f is the function computed in an expand shift substitute permute cycle. These two equations show that the result of each cycle depends only on the previous cycle. By rewriting these equations in terms of - and - , we get Ri-1 = Li. Li-1 = Ri ⊕ f (Ri-1, Ki) = Ri ⊕ f (Li, Ki).  The last two equations show that these same values could be obtained from the results of later cycles. It is this property that makes the DES a reversible procedure; we can encrypt a string and also decrypt the result to derive the plaintext again.  With the DES it is possible to go forward and encrypt or to go backwards and decrypt using the same function f. The only change is that the keys must be taken in reverse order (k16, k15, …, k1) for decryption.  That one algorithm can be used either to encrypt or decrypt is very convenient for a hardware or software implementation of the DES. 3.8 Security of the DES  S-box Design of the Algorithm 1. No S-box is a linear or affine function of its input; that is, the four output bits cannot be expressed as a system of linear equations of the six input bits. 2. Changing one bit in the input of an S-box results in changing at least two output bits; that is, the S- boxes diffuse their information well throughout their outputs. 31  Lecture 3 -symmetric key cryptography (DES) 3. The S-boxes were chosen to minimize the difference between the number of 1s and 0s when any single input bit is held constant; that is, holding a single bit constant as a 0 or 1 and changing the bits around it should not lead to disproportionately many 0s or 1s in the output.  Number of iterations  With only one cycle, a single ciphertext bit is affected only by a few bits of plaintext. With more cycles, the diffusion becomes greater, so ideally no one ciphertext bit depends on any subset of plaintext bits.  Experiments have shown that 8 iterations are sufficient to eliminate any observed dependence. Thus, the 16 iterations of the DES should surely be adequate.  Key Length There are 256 56-bit keys. If someone could test one every 100 milliseconds, the time to test all keys would be 7.2 * 1015 seconds, or about 228 million years. If the test took only one microsecond, then the total time for the search is (only!) about 2,280 years 3.9 Weaknesses of the DES  Weak Keys These keys are called "weak keys." The same thing happens if one half of the key is all 0s and the other half is all 1s. Since these keys are known, they can simply be avoided, so this, too, is not a serious problem.  Semiweak Keys Specific pairs of keys have identical decryption. That is, there are two Different keys, k1 and k2, for which c = DES(p, k1) and c = DES(p, k2). This similarity implies that k1 can decrypt a message encrypted under k2. 3.10 Examples and Questions Practical example1 Let the plaintext be (Caligula) and the key (Claudius), each of them made up of eight letters and will thereby encrypt in a single block. 32  Lecture 3 -symmetric key cryptography (DES) 1. Key Transformation  The ASCII character of (Claudius ), may be used to generate the one-round , 48- bit key k1.thus , with a ’parity’ bit inserted into the rightmost position, we have: C = 67 = 10000110 l = 108 = 11011001 a = 97 = 11000010 u = 117 = 11101010 d = 100 = 11001000 i = 105 = 11010011 u = 117 = 11101010 s = 115 = 11100110  The 64 bit are fed into the 56-element permutation pc-1, i.e 1 1 1 1 1 1 1 1 1 1 1 1 1 1 C0 1 0 1 1 0 0 1 0 0 0 0 0 1 0 D0 1 1 1 0 1 1 0  The parity bits are ‘lost’ leaving two 28-bit 1 1 0 0 0 0 0 subsets c0 and d0 which are then shifted one place to the 0 1 0 1 0 1 1 left. The output is  C0 = 11111111 0 1 0 0 0 1 0 1111111 0110010 000010 C1 = 1111111 1111111 0110010 0000101 D0 = 11101101 1000000 10 10110 100010 D1 = 1101101 1000000 10 10110 1000101  The 56-bit string c1d1, it is now sent to the permutation pc-2. This gives Permuted-choice PC-2 33  Lecture 3 -symmetric key cryptography (DES) 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 K1 0 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 And, reading off the rows in descending order, the output is the 48-bit key K1=111011 110101 001111 110111 000010 100111 000100 001111 2. Encryption Process  the plaintext (Caligula), the ASCII codes C = 67 = 01000011 a = 97 = 01100001 l = 108 = 01101100 i = 105 = 011011001 g = 103 = 01100111 u = 117 = 01110101 l = 108 = 01101100 a = 97 = 01100001  Preprocessing: the initial permutation IP. Initial Permutation IP 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 L0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 R0 0 0 0 1 0 0 0 1 Reading off the rows from top to bottom gives the 64-bit initial text T0 which, in turn, is broken up into the two32-bit blocks: 34  Lecture 3 -symmetric key cryptography (DES) L0 = 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 1 0 1 1 R0 = 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1  Processing: Cycle (1)/ Round(1) Inner Operation R0 expanded to the 48 bit block 1R0. Using Expansion permutation-E-table E-table expansion 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1R0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1R0 = 10000000 00010111 11111100 00100101 10000000 10100010 1. Key xor the 48-bit block 1R0 meet and XORed with the 48-bit key K1 to yield 2R0 = 1R0 ⊕ K1, i.e. 1R0 = 10000000 00010111 11111100 00100101 10000000 10100010 K1 = 11101111 01010011 11110111 00001010 01110001 00001111 2R0 = 01101111 01000100 00001011 00101111 11110001 10101101 2. S-box operation The 48-bit block 2R1 enters its appropriate substitution box s1 to s8 35  Lecture 3 -symmetric key cryptography (DES) Selection box 1 2 3 4 5 6 7 8 Input 011011 110100 010000 001011 001011 111111 000110 101101 index S1(1,13)=5 S2(2,10)=12 S3(0,8)=1 S4(1,5)=15 S5(1,5)=7 S6(3,15)=13 S7(0,3)=14 S8(3,6)=8 Output 0101 1100 0001 1111 0111 1101 1110 1000 3. the output is the eight 4-bit blocks which combine to give 32-bit : Permutation P 3R0 = 01011100 00011111 01111101 11101000 3R0 now enters into the permutation P to give 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 0 4R0 1 0 1 1 0 1 0 0 1 1 0 1 1 0 1 1 And the output is 4R0 = f (R0, K1) = 10111100 01011100 1011010 011011011 This completes the 4-stage function on R0. 4. R1 = L0⊕4R0 4R0 is now XORed with the as yet untouched left-half L0 to obtain the right-hand block R1 = L0⊕4R0, i.e. 4R0 = 10111100 01011100 10110100 11011011 L0 = 11111111 00100000 01110100 10111011 R1 = 01000011 01111100 11000000 01100000 In a sense, R0 has been converted into the complex pseudorandom bit string 4R0 by means of the function f and the key k1. This ‘secondary key’ then ‘encrypts’ L0 and Ro while the original R0 becomes L1. Since this is a variant ‘one-round’ DES, the two 32-bit blocks R1 And L1 do not change position but form the 64-bit pre-output block T1 which is: 36  Lecture 3 -symmetric key cryptography (DES) T1 R1 = L0⊕ 4R0 L1 = R0 01000011 01111100 11000000 01100000 00000000 11111110 01001100 00010001 Example2: Assume the result of the round 16 for DES encryption is L16=01000011 01111100 11000000 R16=00000000 11111110 01001100 01100000 00010001 Find the output cipher text/  Find T= 01000011 01111100 11000000 01100000 00000000 11111110 01001100 00010001  Sending T to the inverse permutation IP-1 gives: Reading off the rows yields (US keyboard ) the cipher text (B’8821}$). Inverse initial Permutation Bit position ASCII ciphertext 0 1 0 0 0 0 1 0 1-8 B 0 1 1 0 0 0 0 0 9 - 16 ’ 0 0 1 1 1 0 0 0 17 - 24 8 0 0 1 1 1 0 0 0 25 - 32 Output 8 0 0 1 1 0 0 1 0 33 - 40 2 0 0 1 1 0 0 0 1 41 - 48 1 0 1 1 1 1 1 0 1 49 – 56 } 0 0 1 0 0 1 0 0 57 – 64 $ Questions: Q1) In a DES algorithm, you have: C1=1100101010111100011010101111 37  Lecture 3 -symmetric key cryptography (DES) D1=1100000011111100010100001111 Find k3. Q2) In a DES algorithm you have the initial key= Shankoti, find the key of the first round k1. Q3) In a DES algorithm, you have: C8=1100101010111100011010101111 D8=1100000011111100010100001111 find k12. Q5) If the input to the S-Box is 110101010101010011001110100101001000110011110011 What is the output? Q6) Use the one-round DES algorithm to encrypt (Get busy) using the key (Sean Paul). Q7) In the 16th round of the DES algorithm you get: R15=10110111100000011010011110100011 L15=01111100011100011010101100010101 And the result of the S-Box is 3R15=01111100011100011010101100010101 What is the cipher text. Q8) The input to the inner function of the DES algorithm is: R7=10111100101010001110100001001011 And K8=011111011011111011011110000001111101110010101010 What is the output [f (R7, k8)]. 38