المحاضرة 4.pdf

Cryptography and Network Security Chapter 3 Fourth Edition by William Stallings Lecture slides by Lawrie Brown By: Raja Alwami Modern Block Ciphers now look at modern block ciphers one of the most widely used types of cryptographic algorithms provide secrecy /a...

Cryptography and Network Security Chapter 3 Fourth Edition by William Stallings Lecture slides by Lawrie Brown By: Raja Alwami Modern Block Ciphers now look at modern block ciphers one of the most widely used types of cryptographic algorithms provide secrecy /authentication services focus on DES (Data Encryption Standard) to illustrate block cipher design principles lecturer: Raja Alwami Block vs Stream Ciphers block ciphers process messages in blocks, each of which is then en/decrypted 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 many current ciphers are block ciphers broader range of applications lecturer: Raja Alwami Block vs Stream Ciphers block ciphers process messages in blocks, each of which is then en/decrypted 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 many current ciphers are block ciphers broader range of applications lecturer: Raja Alwami Block Cipher Principles most symmetric block ciphers are based on a Feistel Cipher Structure needed since must be able to decrypt ciphertext to recover messages efficiently block ciphers look like an extremely large substitution would need table of 264 entries for a 64-bit block instead create from smaller building blocks using idea of a product cipher lecturer: Raja Alwami Data Encryption Standard (DES) most widely used block cipher in world adopted in 1977 by NBS (now NIST) as FIPS PUB 46 encrypts 64-bit data using 56-bit key has widespread use has been considerable controversy over its security lecturer: Raja Alwami DES History IBM developed Lucifer cipher by team led by Feistel in late 60’s used 64-bit data blocks with 128-bit key then redeveloped as a commercial cipher with input from NSA and others in 1973 NBS issued request for proposals for a national cipher standard IBM submitted their revised Lucifer which was eventually accepted as the DES lecturer: Raja Alwami DES Design Controversy although DES standard is public was considerable controversy over design in choice of 56-bit key (vs Lucifer 128-bit) and because design criteria were classified subsequent events and public analysis show in fact design was appropriate use of DES has flourished especially in financial applications still standardised for legacy application use lecturer: Raja Alwami  SIMPLIFIED DATA ENCRYPTION STANDARD (S-DES) Simplified DES, developed by Professor Edward Schaefer of Santa Clara University, is an educational rather than a secure encryption algorithm. It has similar properties and structure to DES with much smaller parameters. OVERVIEW ▪ The S-DES encryption algorithm takes an 8-bit block of plaintext (example: 10111101) and a 10-bit key as input and produces an 8-bit block of ciphertext as output. ▪ The S-DES decryption algorithm takes an 8-bit block of ciphertext and the same 10-bit key used to produce that ciphertext as input and produces the original 8-bit block of plaintext. ▪ The S-DES encryption algorithm takes an 8-bit block of plaintext (example: 10111101) and a 10-bit key as input and produces an 8-bit block of ciphertext as output. lecturer: Raja Alwami The S-DES decryption algorithm takes an 8-bit block of ciphertext and the same 10-bit key used to produce that ciphertext as input and produces the original 8-bit block of plaintext. lecturer: Raja Alwami Reference :William Stallings, Cryptography and Network Security: Principles and Practice, PHI 3rd Edition, 2006 The encryption algorithm involves five functions: an initial permutation (IP); a complex function labeled fK, which involves both permutation and substitution operations and depends on a key input; a simple permutation function that switches (SW) the two halves of the data; the function fK again; and finally a permutation function that is the inverse of the initial permutation (IP–1). ▪ The use of multiple stages of permutation and substitution results in a more complex algorithm, which increases the difficulty of cryptanalysis. ▪ The function fK takes as input not only the data passing through the encryption algorithm, but also an 8-bit key. The algorithm could have been designed to work with a 16-bit key, consisting of two 8-bit subkeys, one used for each occurrence of fK. Alternatively, a single 8-bit key could have been used, with the same key used twice in the algorithm. ▪ A compromise is to use a 10-bit key from which two 8-bit subkeys are generated. In this case, the key is first subjected to a permutation (P10). Then a shift operation is performed. The output of the shift operation then passes through a permutation function that produces an 8-bit output (P8) for the first subkey (K1). The output of the shift operation also feeds into another shift and another instance of P8 to produce the second subkey (K2). lecturer: Raja Alwami lecturer: Raja Alwami ▪ We can concisely express the encryption algorithm as a composition1 of functions: ▪ IP-1 ○ fK2 ○ SW ○ fK1 ○ IP ▪ which can also be written as: ▪ ciphertext = IP-1( fK2 (SW (fK1 (IP(plaintext))))) ▪ where K1 = P8(Shift(P10(key))) ▪ K2 = P8(Shift(Shift(P10(key)))) CS8792-CRYPTOGRPHY AND NETWORK SECURITY ▪ Decryption is essentially the reverse of encryption: ▪ plaintext = IP-1( fK1 (SW (fK2 (IP(ciphertext))))) lecturer: Raja Alwami KEY GENERATION ▪ S-DES depends on the use of a 10-bit key shared between sender and receiver. ▪ From this key, two 8-bit subkeys are produced for use in particular stages of the encryption and decryption algorithm lecturer: Raja Alwami ▪ First, permute the key in the following fashion. Let the 10-bit key be designated as (k1, k2, k3, k4, k5, k6, k7, k8, k9, k10). Then the permutation P10 is defined as: ▪ P10(k1, k2, k3, k4, k5, k6, k7, k8, k9, k10) = (k3, k5, k2, k7, k4, k10, k1, k9, k8, k6) ▪ P10 can be concisely defined by the display: ▪ This table is read from left to right; each position in the table gives the identity of the input bit that produces the output bit in that position. ▪ So the first output bit is bit 3 of the input; the second output bit is bit 5 of the input, and so on. For example, the key (1010000010) is permuted to (1000001100). lecturer: Raja Alwami ▪ Next, perform a circular left shift (LS-1), or rotation, separately on the first five bits and the second five bits. In our example, the result is (00001 11000). Next we apply P8, which picks out and permutes 8 of the 10 bits according to the following rule: lecturer: Raja Alwami S-DES ENCRYPTION ▪ encryption involves the sequential application of five functions. ▪ Initial and Final Permutations ▪ The input to the algorithm is an 8-bit block of plaintext, which we first permute using the IP function: ▪ IP 2 6 3 1 4 8 5 7 ▪ This retains all 8 bits of the plaintext but mixes them up. ▪ At the end of the algorithm, the inverse permutation is used: ▪ IP–1 4 1 3 5 7 2 86 ▪ It is easy to show by example that the second permutation is indeed the reverse of the first; that is, IP–1(IP(X)) = X. lecturer: Raja Alwami The Function fK ▪ The most complex component of S-DES is the function fK, which consists of a combination of permutation and substitution functions. ▪ The functions can be expressed as follows. ▪ Let L and R be the leftmost 4 bits and rightmost 4 bits of the 8-bit input to fK, and let F be a mapping (not necessarily one to one) from 4-bit strings to 4-bit strings. ▪ Then we let ▪ f K(L, R) = (L ! F(R, SK), R) ▪ where SK is a subkey and ! is the bit-by-bit exclusive-OR function. ▪ For example, suppose the output of the IP stage is (10111101) and F(1101, SK) = (1110) for some key SK. ▪ Then fK(10111101) = (01011101) because (1011) ! (1110) = (0101). ▪ We now describe the mapping F. The input is a 4-bit number (n1n2n3n4). ▪ The first operation is an expansion/permutation operation: lecturer: Raja Alwami  For what follows, it is clearer to depict the result in this fashion: ▪ The 8-bit subkey K1 = (k11, k12, k13, k14, k15, k16, k17, k18) is added to this value using exclusive OR ▪ Let us rename these 8 bits: lecturer: Raja Alwami The first 4 bits (first row of the preceding matrix) are fed into the S-box S0 to produce a 2- bit output, and the remaining 4 bits (second row) are fed into S1 to produce another 2-bit output. These two boxes are defined as follows: The S-boxes operate as follows. ▪ The first and fourth input bits are treated as a 2-bit number that specify a row of the S-box, and the second and third input bits specify a column of the Sbox. The entry in that row and column, in base 2, is the 2-bit output. For example, if (p0,0p0,3) = (00) and (p0,1p0,2) = (10), then the output is from row 0, column 2 of S0, which is 3, or (11) in binary. Similarly, (p1,0p1,3) and (p1,1p1,2) are used to index into a row and column of S1 to produce an additional 2 bits. ▪ Next, the 4 bits produced by S0 and S1 undergo a further permutation as follows lecturer: Raja Alwami ▪ The output of P4 is the output of the function F. The Switch Function The function fK only alters the leftmost 4 bits of the input. The switch function (SW) interchanges the left and right 4 bits so that the second instance of fK operates on a different 4 bits. In this second instance, the E/P, S0, S1, and P4 functions are the same. The key input is K2. lecturer: Raja Alwami Substitution and Transposition - Substitution -Replace one character with another - Example ROT13 * A replace by N, B by O etc… * P=ROT13(ROT13(P)) * key can determine replacements -Transposition -Change the order of characters * E.g. ABCD might become CADB * key can determine ordering -Many symmetric cipher use sophisticated combination both techniques. lecturer: Raja Alwami Symmetric Encryption-Data Encryption Standard (DES) -US Federal Standard since 1976 -DES uses 56 bit key and 64 bit size of blocks -DES encryption and decryption algorithms are public, but the design principles are kept secret. Properties- * Used for message content encryption * Fast and efficient -Several serious flaws and attacks known * No longer considered ‘fit for purpose’. - The longer the encryption keys, the stronger the security lecturer: Raja Alwami Symmetric Encryption- DES -Can break through any cipher by trying all keys that possibly exist. -However, in brute force attacks, the time taken to break a cipher is directly proportional to the length of the key lecturer: Raja Alwami Asymmetric Encryption -In asymmetric cryptosystems the key to decrypt a ciphertext is not the same as the encryption key -Thus we have a seperate encryption and a decryption key, KE, KD Ciphertext = E(KE, P) Plaintext = D(KD, C lecturer: Raja Alwami An Asymmetric Cipher -The two parties have their own keys, KE, KD, and are able to encrypt/decrypt the original message -In the model below it is P = D(KD, C) = D(KD, E(KE, P)) lecturer: Raja Alwami Public Key Ciphers -The best example and most commonly used version of asymmetric encryption is public key cryptography -Keys come in pairs; each user has a key that does not have to be kept secret and can be freely advertised for others to download; to that key corresponds another that remains secret with the user (‘private’) -One’s public key can be used to encrypt a message that only the owner of its corresponding private key can decrypt P = D(KPRIV, E(KPUB, P)) lecturer: Raja Alwami Public Key Ciphers (cont’d)  The key pair satisfies mathematical relations so that:  Some algorithms (e.g. RSA) display properties where either of the keys can be used to encrypt and the other to decrypt  P = D(KPUB, E(KPRIV, P));  Knowing the one key and the algorithm does not reveal the other key  For N users only O(N) keys required: N public + N private  Famous example of public key algorithm is the RSA (Rivest-Shamir- Adleman) lecturer: Raja Alwami Secrecy and Authenticity lecturer: Raja Alwami lecturer: Raja Alwami The RSA Algorithm  RSA (Rivest, Shamir Adleman) is a popular asymmetric key encryption standard.  It is based on number theory (more specifically the difficulty in factorizing a large number).  The key size ranges between 512 and 2048 bits.  It is used in many e-commerce applications such as the Secure Electronic Transaction(SET) protocol for credit card payment. lecturer: Raja Alwami RSA Algorithm lecturer: Raja Alwami Example -RSA lecturer: Raja Alwami lecturer: Raja Alwami