Data Encryption Standard (DES) PDF

Data Encryption Standard Prof. Heba Elnemr Last Chapter have considered: terminology classical cipher techniques substitution ciphers cryptanalysis using letter frequencies transposition ciphers Modern Block Ciphers one of the most widely used types of cryptogra...

Data Encryption Standard Prof. Heba Elnemr Last Chapter have considered: terminology classical cipher techniques substitution ciphers cryptanalysis using letter frequencies transposition ciphers Modern Block Ciphers one of the most widely used types of cryptography algorithms provide strong secrecy and/or authentication services in particular will introduce DES (Data Encryption Standard) Block vs Stream Ciphers block ciphers process messages into blocks, each of which is then en/decrypted A block cipher transforms an input block (a string of input bits of fixed length) into an output block that is a string of output bits of the same fixed length. All of these bits have to be available before the block can be processed like a substitution on very big characters 64-bits or more stream ciphers process messages a bit or byte at a time when en/decrypting, hence process it as a “stream”. many current ciphers are block ciphers, hence are focus of course Block Cipher Principles A block cipher is a type of symmetric encryption which operates on blocks of data. Examples of block ciphers include DES, AES, RC6, and IDEA. A block cipher breaks message into fixed sized blocks Takes one block (plaintext) at a time and transform it into another block of the same length using a user provided secret key Decryption is performed by applying the reverse transformation to the ciphertext block using the same secret key Most symmetric block ciphers are based on a Feistel Cipher Structure Block Cipher Principles A block cipher operates on a plaintext block of n bits to produce a ciphertext block of n bits. There are 2n possible different plaintext blocks and, for the encryption to be reversible, each must produce a unique ciphertext block. In general, for an n-bit general substitution block cipher, the size of the key is n x 2n. For a 64-bit block, which is a desirable length to thwart statistical attacks, the key size is 64 x 264 = 270 = 1021 bits. block ciphers look like an extremely large substitution Shannon and Substitution-Permutation Ciphers in 1949 Shannon introduced idea of substitution-permutation (S-P) networks modern substitution-transposition product cipher these form the basis of modern block ciphers S-P networks are based on the two primitive cryptographic operations we have seen before: substitution (S-box) permutation (P-box) (transposition) He also introduced the ideas of confusion and diffusion, properties of the operation of a secure cipher. According to Shannon, a good cipher should provide confusion and diffusion  Diffusion and Confusion Introduced by Claude Shannon to thwart cryptanalysis based on statistical analysis Assume the attacker has some knowledge of the statistical characteristics of the plaintext Diffusion seeks to make statistical relationship between the plaintext and ciphertext as complex as possible in order to thwart attempts to deduce the key. It is a cryptographic technique invented to increase the redundancy of the plain text by spreading it across rows and columns to prevent attempts to deduce the key. Diffusion hides the relationship between the ciphertext and the plaintext. Transposition (Permutation) is a technique for diffusion Diffusion and Confusion Introduced by Claude Shannon to thwart cryptanalysis based on statistical analysis Assume the attacker has some knowledge of the statistical characteristics of the plaintext Confusion seeks to make relationship between the statistics of the ciphertext and the value of the encryption key as complex as possible, again to thwart attempts to discover the key It is a cryptographic technique ensures that the ciphertext gives no clue about the plaintext. Confusion hides the relationship between the ciphertext and the key Substitution is one of the mechanism for primarily confusion Diffusion and Confusion Feistel Cipher Structure In 1970’s, Horst Feistel invented a suitable (practical) structure which adapted Shannon’s S-P network Encryption and decryption use the same structure S-P network: a special form of substitution- transposition product cipher Product cipher Two or more simple ciphers are performed in sequence in such a way that the final result or product is cryptographically stronger than any of the component ciphers Feistel Cipher Structure The inputs to the encryption algorithm are a plaintext block of length bits and a key. 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 as 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 Ki are different from K and from each other. All rounds have the same structure. Feistel Cipher Structure n sequential rounds A substitution on the left half Li 1. Apply a round function F to the right half Ri and 2. Take XOR of the output of (1) and Li The round function is parameterized by the subkey Ki Ki are derived from the overall key K Following this substitution, a permutation is performed that consists of the interchange of the two halves of the data. Feistel Cipher Design Principles block size increasing size improves security, but slows cipher key size increasing size improves security, makes exhaustive key searching harder, but may slow cipher number of rounds increasing number improves security, but slows cipher subkey generation greater complexity can make analysis harder, but slows cipher round function greater complexity can make analysis harder, but slows cipher fast software en/decryption & ease of analysis are more recent concerns for practical use and testing Feistel Cipher Design Principles 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 algorithm, but use the subkeys Ki in 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. This is a nice feature because it means we need not implement two different algorithms, one for encryption and one for decryption. Data Encryption Standard (DES) A Block cipher Data encrypted in 64-bit blocks using a 56-bit key. Ciphertext is of 64-bit long. Encrypts by series of substitution and transpositions (or permutations) DES has become widely used, especially in financial applications Best known and widely used symmetric algorithm in the world But, no longer is considered secure for highly sensitive applications. DES History The first commercially available Feistel Cipher was developed by IBM in the 1960's; called Lucifer (by Feistel and Coppersmith) US National Bureau of Standards (NBS) issued a call for proposals in 1972 Lucifer was refined, renamed the Data Encryption Algorithm (DEA) in 1974 Adopted as the standard by NBS in 1976 DES is the first official U.S. government cipher intended for commercial use Replacement standard (AES) is in effect 2002 DES Features Features: Block size = 64 bits Key size = 56 bits (in reality, 64 bits, but 8 are used as parity-check bits for error control) Number of rounds = 16 16 sub keys, each 48 bits DES Encryption Overview Key length in DES In the DES specification, the key length is 64 bit: 8 bytes; in each byte, the 8th bit is a parity-check bit Each parity-check bit is the XOR of the previous 7 bits Description DES operates on 64-bit blocks of plaintext. After an initial permutation the block is broken into right half and left half, each being 32 bits long There are 16 rounds of identical operations, call function f, in which data are combined with 16 keys of 48 bits, one for each round After the 16th round the right and left halves are joined, and a final permutation (the inverse of the initial permutation) finishes the algorithm. Because DES’s operation is very repetitive, it is readily implementable in hardware, as well as software DES Encryption Two inputs to the encryption function The 64-bit plaintext to be encrypted The 56-bit key Three phases for processing the plaintext 1. Rearrangement of the plaintext through an initial permutation to produce “permuted input” 2-1. 16 iterations of the same function, which consists of permutation and substitution functions with key 2-2. Swap of left and right halves from output of the last iteration to produce “preoutput” 3. Inverse of the initial permutation on the preoutput to produce the “64-bit ciphertext” Details IP(x) = L0R0 Li = Ri-1 Ri = Li-1 ⊕ f (Ri-1, Ki) Y = IP-1(R16 L16) Note: IP means Initial Permutation Initial Permutation (IP) These two permutation functions are the inverse of each other See the following 64-bit input M: M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 M12 M13 M14 M15 M16 M17 M18 M19 M20 M21 M22 M23 M24 M25 M26 M27 M28 M29 M30 M31 M32 M33 M34 M35 M36 M37 M38 M39 M40 M41 M42 M43 M44 M45 M46 M47 M48 M49 M50 M51 M52 M53 M54 M55 M56 M57 M58 M59 M60 M61 M62 M63 M64 where Mi is a binary digit. Then the permutation X=IP(M) is: M58 M50 M42 M34 M26 M18 M10 M2 M60 M52 M44 M36 M28 M20 M12 M4 M62 M54 M46 M38 M30 M22 M14 M6 M64 M56 M48 M40 M32 M24 M16 M8 M57 M49 M41 M33 M25 M17 M9 M1 M59 M51 M43 M35 M27 M19 M11 M3 M34 M2 M42 M10 M50 M18 M58 M26 M33 M1 M41 M9 M49 M17 M57 M25 Y=IP-1(x) = IP-1(IP(M)) = M Initial Permutation (IP) This table specifies the input permutation on a 64-bit block. The meaning is as follows: the first bit of the output is taken from the 58th bit of the input; the second bit from the 50th bit, and so on, with the last bit of the output taken from the 7th bit of the input. This information is presented as a table for ease of presentation: it is a vector, not a matrix. Initial Permutation (IP) DES Rounds IP(x) = L0R0 Li = Ri-1 Ri = Li-1 ⊕ f (Ri-1, Ki) Y = IP-1(R16 L16) Note that: R16 = L15 ⊕ f (R15, K16) IP-1 means L16 = R15 Inverse Initial Permutation … but they are switched in the pre-output Final -1 Permutation (IP ) The final permutation is the inverse of the initial permutation; the table is interpreted similarly. The output of the Final Permutation has bit 40 of the preoutput block as its first bit, bit 8 as its second bit, and so on, until bit 25 of the preoutput block is the last bit of the output. Final -1 Permutation (IP ) Single Round of DES Algorithm The F Function of DES The overall processing of each iteration: Li = Ri-1 Ri = Li–1 ⊕ F(Ri-1, Ki) Function F consists of: Expansion / Permutation. Substitution Permutation XORs The F Function of DES E is an expansion function which takes a block of 32 bits as input and produces a block of 48 bits as output The F Function of DES E is an expansion function which takes a block of 32 bits as input and produces a block of 48 bits as output S-boxes are the only non-linear elements in DES design Each of the unique selection functions S1, S2,..., S8, takes a 6-bit block as input and yields a 4-bit block as output The F Function of DES The L and R each have 32 bits, and the round key K 48 bits. R(32bits) The F function, on input R and K, E produces 32 bits: 48 bits K (48 bits) + F(R,K) = P(S(E(R)  K)) Where S1 S2 S3 S4 S5 S6 S7 S8 E: expands 32 bits to 48 bits; P S: Shrinks it back to 32 bits; 32 bits P: permutes the 32 bits. S-boxes Eight S-boxes each map 6 to 4 bits S = matrix 4x16, values from 0 to 15 B (6 bit long) = b1b2b3b4b5b6 b1b6 → r = row of the matrix (2 bits: 0,1,2,3) used to select one of the four rows b2b3b4b5 → c = column of the matrix (4 bits: 0,1,…15) used to select a column C (4 bit long) = Binary representation of S(r, c) All the eight boxes are different. Example (S1) Permutation Function (P-box) Key Generation Key Generation Two phases of Key Generation 1. Permutation on the key input (64 bit). 56-bits (the effective key) are selected and permuted using Permuted Choice One (PC-1); and then divided into two 28-bit halves. 2. For each of the 16 iterations, Left-rotate each half separately by either 1 or 2 bits according to a rotation schedule. Select 24-bits from each half, and permute the combined 48 bits (permuted choice 2) (PC-2). This forms a round key.  DES Key Generation (K1 – K16) 64 bit key (including parity-check bits) 28 bit 28 bit Matrix PC-1 and PC-2 are given by the standard (see next slide) 48 bit Ci=LSi(Ci-1) Di=LSi (Di - 1) 8 bits are dropped 48 bits are permuted Ki=PC-2 (Ci Di) LS=Left Shift shift one position if i=1,2,9 or 16 shift two positions otherwise  DES Permuted Choice 1 and 2 (PC-1, PC-2) The bits of the key are numbered from 1 through 64 Parity-check bits (namely, bits 8,16, 24, 32, 40, 48, 56, 64) are not chosen, they do not appear in PC-1 PC-2 selects the 48-bit subkey for each round from the 56-bit key-schedule state Schedule for left shifts DES Permuted Choice 1 and 2 (PC-1, PC-2) Schedule for left shifts DES Permuted Choice 1 and 2 (PC-1, PC-2) PC-2 selects the 48-bit subkey for each round from the 56-bit key-schedule state DES Decryption The same as the encryption process The rule is as follows: Use the ciphertext as input to DES Algorithm Apply the keys Ki in reverse order. i.e. use K16 on the 1st iteration, K15 on the 2nd iteration and so on until K1 on the 16th iteration. Triple DES Use three different keys Encrypt: C = EK3 [ DK2 [ EK1 [P] ] ] Decrypt: P = DK1 [ EK2 [ DK3 [C] ] ] The standard specifies three keying options: 1. Keying option 1: All three keys are independent. 2. Keying option 2: K1 and K2 are independent, and K3 = K1. 3. Keying option 3: All three keys are identical, i.e. K1 = K2 = K3. Using keying option 1: the key space is 56 x 3 = 168 bits No known practical attack against it. Triple DES Many protocols/applications use 3DES (example PGP) PGP is an open-source, freely available software package for e-mail security. The electronic payment industry uses Triple DES and continues to develop and declare standards based upon it (e.g. EMV, Europay-Visa- Mastercard). Keying option 2 provides less security than option 1, with 2 × 56 = 112 key bits. However, this option is stronger than double DES (with K1 and K2). Keying option 3 is equivalent to DES, with only 56 key bits. But suffers from being 3 times slower to run. Blowfish A symmetric block cipher designed by Bruce Schneier in 1993 It takes a variable-length key, from 32 bits to 448 bits, making it ideal for both domestic and exportable use. There are two parts to the Blowfish Algorithm: A part that handles the expansion of the key. break the original key into a set of subkeys. Specifically, ranges from 32 bits to 448 bits. There is a P-array and four 32-bit S-boxes. The P-array contains 18 32-bit subkeys, while each S-box contains 256 entries. A part that handles the encryption of the data. The encryption of the data: 64-bit input is denoted with an x, while the P- array is denoted with a Pi (where i is the iteration). The Blowfish Algorithm: Key Expansion Blowfish has a 64-bit block size uses a 32 to 448 bit key used to generate 18 32-bit subkeys stored in P-array: P1 to P18 S-boxes stored in Si,j , i=1..4, j=0..255 It is a 16-round Feistel cipher and uses large key-dependent S- boxes. The Blowfish Encryption  Blowfish Encryption uses two primitives: addition & XOR data is divided into two 32-bit halves L0 & R0 for i = 1 to 16 do Ri = Li-1 XOR Pi; Li = F[Ri] XOR Ri-1; L17 = R16 XOR P18; R17 = L16 XOR P17; where F[a,b,c,d] = ((S1,a + S2,b) XOR S3,c) + S4,d Break 32-bit Ri into (a,b,c,d)