Introduction To Cryptography PDF

INTRODUCTION TO Cryptography - ANWITAMAN DATTA Etymology & definition κρυπτός (kryptós): hidden/secret γράφειν (graphein): writing A traditional definition: The practice and study of techniques for secure communication in the presence of adversarial behavior...

INTRODUCTION TO Cryptography - ANWITAMAN DATTA Etymology & definition κρυπτός (kryptós): hidden/secret γράφειν (graphein): writing A traditional definition: The practice and study of techniques for secure communication in the presence of adversarial behavior © Anwitaman DATTA A more expansive interpretation: The scientific study of techniques for securing digital information, transactions, and distributed computations (in the presence of adversarial behavior) The big picture ⌘ Many aspects to realizing a proper security solution: cryptology is (just) one (yet very) important and necessary ingredient 1.1 Overview of Cryptology (and This Book) 3 focus of this course © Anwitaman DATTA Fig. 1.3 Overview of the field of cryptology Course roadmap basic cryptographic primitives & protocols for confidentiality, integrity and authentication © Anwitaman DATTA  Scenario 1.2 Symmetric Cryptography 5 notAlice get and into Bob the want handstoofcarry theirout private communication over an insecure channel competitors, or of foreign intelligence agencies for - Oscar, the adversary, trying to learn the content “x” of the private communication that matter. © Anwitaman DATTA Fig. 1.4 Communication over an insecure channel Secret key cryptography a.k.a. Symmetric key cryptography © Anwitaman DATTA Sender/Receiver share a common secret key k - Encryption & Decryption both done with same key (hence, symmetric)  Note that the alphabet is wrapped around, so that the letter following Z is A. We can define the transformation by listing all possibilities, as follows: Example plain: a b c d e f g h i j k l m n o p q r s t u v w x y z Substitution cipher: Substitute each letter of the alphabet with some other letter cipher: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C One ⌘ Let usof the asimplest assign form numerical of substitution equivalent cipher: k-shift cipher to each letter: - consider the following numerical equivalent assignment to each letter: Symmetric key cryptography a b c d e f g h i j k l m 0 1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x y z 13 14 15 16 17 18 19 20 21 22 23 24 25 © Anwitaman DATTA ⌘ The Then k-shift cipher the algorithm can beuses the mappings: expressed LEGEND as follows. For each plaintext letter p , substi- tute the ciphertext letter C:2 p plain text Encryption: C = E(k,p) = (p+k) mod 26 C cipher text Decryption:C p= =E(3, p) = (p= +(C-k) D(k,C) 3) modmod 26 26 k secret key E() encryption algorithm A shift may be of any amount, so that the general CaesarD() algorithm is decryption algorithm C = E(k, p) = (p + k) mod 26 (2.1)  Example Substitution cipher: Substitute each letter of the alphabet with some other letter ⌘ k-shift cipher Symmetric key cryptography Since the “algorithm” is known, a brute-force attack (exhaustive search for the “key”), i.e., checking 25 possibilities, in this case, would suffice. If one is lucky, the search can be terminated much earlier. If any random permutation is used as a (monoalphabetic) substitution cipher: Fragment of a possible cipher: © Anwitaman DATTA AàX B àH Cà R … ZàL How many distinct possibilities of mapping are there?  The ciphertext to be solved is UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ Example As a first step, the relative frequency of the letters can be determined and compared to a standard frequency distribution for English, such as is shown in Figure 2.5 (based on [LEWA00]). If the message were long enough, this technique Substitution cipher: Substitute each letter of the alphabet with some other letter alone might be sufficient, but because this is a relatively short message, we cannot expect an exact match. In any case, the relative frequencies of the letters in the ciphertext (in percentages) are as follows: P 13.33 H 5.83 F 3.33 B 1.67 C 0.00 If any random permutation is used as a cipher (26!, i.e. ~ 4*10^26 mappings): Z 11.67 S 8.33 D E 5.00 5.00 W Q 3.33 2.50 G Y 1.67 1.67 K L 0.00 0.00 Symmetric key cryptography U 8.33 V 4.17 T 2.50 I 0.83 N 0.00 O 7.50 X 4.17 A 1.67 J 0.83 R 0.00 Brute-force attack will take much longer than the age of the universe to crack it! M 6.67 14 12.702 While brute-force attack is not practical any 12 longer, cryptanalysis exploiting the statistical 10 properties pf the plaintext can be used to 9.056 Relative frequency (%) 8.167 easily crack monoalphabetic substitution! © Anwitaman DATTA 7.507 8 6.996 6.749 6.327 6.094 5.987 6 4.253 4.025 4 2.782 2.758 2.406 2.360 2.228 2.015 1.974 1.929 1.492 2 0.978 0.772 0.153 0.150 0.095 0.074 0 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z  Polyalphabetic cipher Vigenère cipher A set of monoalphabetic ciphers used, choice of cipher in each step determined by a key Symmetric key cryptography plaintext: p0 , p1 , p2 ,...pn 1 keyword: k0 , k1 , k2 ,...km 1 encryption: Ci = (pi + k i mod m ) mod 26 © Anwitaman DATTA decryption: pi = (Ci k i mod m ) mod 26  Polyalphabetic cipher Vigenère cipher example 50 CHAPTER CHAPTER 2 / 2CLASSICAL ENCRYPTION / CLASSICAL ENCRYPTION TECHNIQUES TECHNIQUES key: deceptivedeceptivedeceptive key: plaintext: deceptivedeceptivedeceptive wearediscoveredsaveyourself Symmetric key cryptography plaintext: ciphertext: wearediscoveredsaveyourself ZICVTWQNGRZGVTWAVZHCQYGLMGJ ciphertext: Expressed numerically, we ZICVTWQNGRZGVTWAVZHCQYGLMGJ have the following result. Expressed key numerically, 3 4 2 we4 have 15 19the8 following 21 4 3 result. 4 2 4 15 plaintext 22 4 0 17 4 3 8 18 2 14 21 4 17 4 ciphertext 25 8 2 21 19 22 16 13 6 17 25 6 21 19 key 3 4 2 4 15 19 8 21 4 3 4 2 4 15 © Anwitaman DATTA plaintext key 22 19 8 4 21 04 17 3 4 4 2 34 158 19 188 2 21 414 21 4 17 4 ⌘ Multiple substitutions for the same plaintext letter plaintext 3 18 0 be21 - However: there 4 24 repetitions 14 20 17 18 4 11 5 ciphertext 25 may8 2 periodic 21 19 22 16 13 6 17 25 6 21 19 - Once an attacker ciphertext 22 0 guesses 21 25 the7 keyword 2 16 24length, 6 11 12 6 9 the attacker can attack individual monoalphabetic ciphers key The strength of19this cipher 8 21 4 is that there 3 multiple are 4 2 4 letters ciphertext 15 for 19each8 21 4 plaintext letter, one for each unique letter of the keyword. Thus, the letter frequency plaintext 3 18 0 21 4 24 14 20 17 18 4 11 5  One time pad Vernam cipher If the keyword is as long as the plaintext, and hence same substitution is never (systematically) repeated Symmetric key cryptography Mathematically (provably) impossible to break without knowing the key Not practical: Why? © Anwitaman DATTA  TASOIINEHIUSRNPSTOTCNQE All the mechanisms discussed so far used substitution A fundamentally different technique is to rearrange the plain text in some kind of Symmetric key cryptography permutation Easy to recognize: same letter frequencies as plain text. Simplest example: rail fence technique - Arrange ciphertext in matrices of varying sizes, and play around Plaintext: TRANSPOSITION TECHNIQUE with rearrangements Take odd letters: TASOIIN… - Di/tri-grams help: in guessing © Anwitaman DATTA Take even letters: RNPSTOT… matrix dimension, interpolating Merge the two: TASOIINEHIUSRNPSTOTCNQE column permutation However: Reapplication makes it harder to guess the matrix dimension Note: More sophisticated transpositions are possible! or interpolate the column permutation  Putting the three ideas together Symmetric key cryptography Substitute plaintext symbols Substitution Poly-alphabetic substitution is better resilient to frequency analysis Reorder (permute) the sequence of Transposition symbols © Anwitaman DATTA (Re-)apply multiple times the smaller Cascade units of encryption, to realize a stronger encryption  Putting the three ideas together 56 Example: Enigma cipher Direction of motion A 24 21 26 20 1 8 A A With 3 rotors we can have 26*26*26 = 17,576 different B 25 3 1 1 2 18 B B Symmetric key cryptography monoalphabetic substitutions before repetitions C 26 15 2 6 3 26 C C D 1 1 3 4 4 17 D D E 2 19 4 15 5 20 E E F 3 10 5 3 6 22 F F G 4 14 6 14 7 10 G G H 5 26 7 12 8 3 H H I 6 20 8 23 9 13 I J 7 8 9 5 10 11 J J K 8 16 10 16 11 4 K K L 9 7 11 2 12 23 L L M 10 22 12 22 13 5 M M N 11 4 13 19 14 24 N N O 12 11 14 11 15 9 O O P 13 5 15 18 16 12 P P © Anwitaman DATTA Q 14 17 16 25 17 25 Q Q R 15 9 17 24 18 16 R R S 16 12 18 13 19 19 S S T 17 23 19 7 20 6 T T U 18 18 20 10 21 15 U U V 19 2 21 8 22 21 V V W 20 25 22 21 23 2 W W X 21 6 23 9 24 7 X X Y 22 24 24 26 25 1 Y Y Z 23 13 25 17 26 14 Z Z Fast rotor Medium rotor Slow rotor (a) Initial setting Figure 2.8 Three-Rotor Machine with Wiring Represented b  Block ciphers (a) Stream cipher using algorithmic bit-str A block of plaintext is processed together, to b bits create a block of ciphertext (of same size). Plaintext Symmetric key cryptography e.g.: DES, AES, … - can be used to create a stream cipher Key Encryption Essentially a mapping (for a b-bits block) (K) algorithm - Input space: 2b - Output space: 2b © Anwitaman DATTA How many such mappings exist? Ciphertext - In general? - That are reversible? (2b)! b bits (b) Block cipher  cipher and can be used to define any reversible mapping bet ciphertext. Feistel refers to this as the ideal block cipher, because imum number of possible encryption mappings from the plaintex Block ciphers 70 CHAPTER 3 / BLOCK CIPHERS AND THE DATA ENCRYPTION STANDARD Table 3.1 Encryption and Decryption Tables for Su Cipher of Figure 3.2 4-bit input Plaintext Ciphertext Ciphertext Pla 4 to 16 decoder 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0000 1110 0000 1 0001 0100 0001 0 Symmetric key cryptography 0010 1101 0010 0 0011 0001 0011 1 0100 0010 0100 0 0101 1111 0101 1 0110 1011 0110 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0111 1000 0111 1 16 to 4 encoder 1000 0011 1000 0 1001 1010 1001 1 © Anwitaman DATTA 4-bit output Figure 3.2 General n-bit-n-bit Block Substitution (shown with n = 4) 1010 0110 1010 1 1011 1100 1011 0 4×24 bits required to represent mapping defined by a tabulation, as shown in Table 3.1. This is the most general form of block 1100 0101 1100 1 cipher and can be used to define any reversible mapping between plaintext and - Ideal block cipher ciphertext. Feistel refers to this as the ideal block cipher, because it allows for the max- 1101 1001 1101 0 imum number of possible encryption mappings from the plaintext block [FEIS75]. 1110 0000 1110 0 - Practical? 1111 0111 1111 0 Table 3.1 Encryption and Decryption Tables for Substitution Cipher of Figure 3.2 Plaintext Ciphertext Ciphertext Plaintext  Feistel structure An instance of block cipher design Split input in two halves - Alternatively repeat: Symmetric key cryptography - Substitution with round function F(-,Ki) and XOR - Permutation: swap halves © Anwitaman DATTA  DES Date Encryption Standard based on Feistel’s work at IBM since late 1960s Symmetric key cryptography © Anwitaman DATTA Somewhat opaque and controversial process of design of the F-box  AES Advanced Encryption Standard Substitution-Permutation network: - 128 bits plaintext input Symmetric key cryptography - 16/24/32 byte keywords AES-128, AES-192, AES-256 - 10/12/14 rounds - Four types of transforms per round © Anwitaman DATTA  AES: Advanced Encryption Standard aka Rijndael A peek inside AES: Not examinable Vincent Rijmen Joan Daemen born in 1970 born in 1965 © Anwitaman DATTA  AES: Advanced Encryption Standard aka Rijndael All AES operations are on 8-bit byte strings A peek inside AES: Not examinable - Addition, multiplication and division in Galois Field: GF(28) - Uses polynomial arithmetic - All AES GF(28) computations are based on the irreducible polynomial © Anwitaman DATTA  AES Big picture Substitution-Permutation network: A peek inside AES: Not examinable - 128 bits plaintext input - 16/24/32 byte keywords AES-128, AES-192, AES-256 - 10/12/14 rounds - Four types of transforms per round © Anwitaman DATTA  AES Big picture Inputs: A peek inside AES: Not examinable in0 in4 in8 in12 s0,0 - Plaintext 4×4 column major order matrix of bytes (termed as the state) in1 in5 in9 in13 s1,0 - Cipher key - which is expanded into round keys in2 in6 in10 in14 s2,0 - serves as an input to AddRoundKey transformation in each round in3 in7 in11 in15 s3,0 © Anwitaman DATTA k0 k4 k8 k12 k1 k5 k9 k13 w0 k2 k6 k10 k14  AES Key expansion: round keys generation Expand into N+1 round keys A peek inside AES: Not examinable - Four word (16 byte) key mapped into a linear array of 44 words (176 bytes) - Function g() involves byte rotation, substitution and XOR with some round constant Purpose - Diffusion of cipher key differences © Anwitaman DATTA - Non-linearity and elimination of symmetries  A peek inside AES: Not examinable AES Substitute Bytes Transform © Anwitaman DATTA  AES S-box: look-up table 5.3 / AES TRANSFORMATION FUNCTIONS 157 Table 5.2 AES S-Boxes ➙ y A peek inside AES: Not examinable 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76 1 CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0 2 B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15 3 04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75 4 09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84 5 53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF 6 D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8 7 51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2 x ➙ 8 CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73 9 60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB © Anwitaman DATTA A E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79 B E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08 C BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A D 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E E E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF F 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16 (a) S-box  b3¿ 1 1 1 1 0 0 0 1 b 0 Byte at row y, Byte at row y H X = H X H 3X + H X (5.2) column x yx column x b4¿ 1 1 1 1 1 0 0 0 b4 0 initialized to yx initialized to y AES S-box: construction b5¿ b6¿ 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 0 b5 b6 1 1 Inverse b7¿ 0 0 0 1 1 1 1 1 b7 0 in GF(28) Equation (5.2) has to be interpreted carefully. In ordinary matrix multiplica- 4 tion, each element in the product matrix is the sum of products of the elements of one rowExample: Byte to bit b′0 0 0 and one column. In this case, each element in the product matrix is the A peek inside AES: Not examinable column vector b1′ 1 0 bitwise -XOR95ofHEX ∈GF(2 products 8) of elements of one row and one column. Furthermore, the b′2 0 1 final addition shown -1 in Equation (5.2) is a bitwise XOR. Recall from Section 4.7 b3′ 1 0 that the-bitwise 95 XOR =8Ais [refer additionto question pool 2: Q8] 8 = in GF(2 ). b′0 1 0 0 0 1 1 b01 11 b′4 0 1 As- an8A example,=consider 10001010 the input value {95}. The multiplicative inverse in b1′ 1 1 0 0 0 1 b11 11 b′5 0 0 8 - 1HEX 2 GF(2 ) is {95} = {8A}, which is 10001010 in binary. Using Equation (5.2), b′2 1 1 1 0 0 0 b21 01 b′6 1 0 b3′ 1 1 1 1 0 0 b30 01 b′7 0 1 = + 1 0 0 0 1 1 1 1 0 1 1 1 0 b′4 1 1 1 1 1 0 b40 00 ′ 0 1 1 1 1 1 0 10 1 1 0 0 0 1 1 1 1 1 0 1 1 b5 b5 ′ b6 0 0 1 1 1 1 1 0 b6 1 1 1 1 0 0 0 1 1 0 0 0 0 0 ′ b7 0 0 0 1 1 1 1 1 b7 0 1 1 1 1 0 0 0 1 1 0 1 0 1 H X H X!H X = H X!H X = H X 1 1 1 1 1 0 0 0 0 0 0 0 0 © Anwitaman DATTA 0 1 1 1 1 1 0 0 0 1 0 1 1 Bit column vector to byte 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 S(yx) 4 For a brief review of the rules of matrix and vector multiplication, refer to Appendix E. - S(95)=2A (a) Calculation of byte at (a) Ca row y, column x of S-box row y, Figure 5.6 Constuction of S-Box and IS-Box  AES S-box: design rationale - Low correlation between input/output bits A peek inside AES: Not examinable - Output a non-linear function of input using multiplicative inverse provides non-linearity - Constant chosen so that: there are no fixed points: S(a)=a there are no opposite fixed points: S(a)= a̅ a̅ is the bit-wise complement of a - S-box is invertible, but there are no self-inverses AES constant © Anwitaman DATTA S(a)≠IS(a)  AES ShiftRows Transform A peek inside AES: Not examinable © Anwitaman DATTA - ith row gets i-1left circular shift 4 bytes of a column are spread to four different columns  s3,0 s3,1 s3,2 s3,3 s3,3 s3,0 s3,1 s3,2 AES MixColumns Transform (a) Shift row transformation GF(28) operations A peek inside AES: Not examinable 2 3 1 1 1 2 3 1 " ! 1 1 2 3 3 1 1 2 s0,0 s0,1 s0,2 s0,3 s'0,0 s'0,1 s'0,2 s'0,3 s'1,0 s'1,1 s'1,2 s'1,3 © Anwitaman DATTA s1,0 s1,1 s1,2 s1,3 s2,0 s2,1 s2,2 s2,3 s'2,0 s'2,1 s'2,2 s'2,3 s3,0 s3,1 s3,2 s3,3 s'3,0 s'3,1 s'3,2 s'3,3 (b) Mix column transformation  s3,0 s3,1 s3,2 s3,3 s3,3 s3,0 s3,1 s3,2 AES MixColumns Transform (a) Shift row transformation GF(28) operations A peek inside AES: Not examinable 2 3 1 1 1 2 3 1 " ! 1 1 2 3 3 1 1 2 s0,0 s0,1 s0,2 s0,3 s'0,0 s'0,1 s'0,2 s'0,3 s'1,0 s'1,1 s'1,2 s'1,3 © Anwitaman DATTA s1,0 s1,1 s1,2 s1,3 s2,0 s2,1 s2,2 s2,3 s'2,0 s'2,1 s'2,2 s'2,3 s3,0 s3,1 s3,2 s3,3 s'3,0 s'3,1 s'3,2 s'3,3 (b) Mix column transformation  AES MixColumns Transform: Example A peek inside AES: Not examinable - Multiplication by 2 (is essentially multiplication by x in polynomial representation) can be realized using a 1-bit left shift - Followed by a conditional XOR with 00011011 if leftmost bit of original value prior to shift is 1. © Anwitaman DATTA Why? Something to do with the irreducible polynomial …  AES MixColumns Transform: Example A peek inside AES: Not examinable Note: {87}=1000 0111 © Anwitaman DATTA Note: {6E}=0110 1110  mation, called AddRoundKey, the 128 bits of State are bitwise XORed with the 128 bits of the round key. As shown in Figure 5.5b, the operation is viewed as a columnwise operation between the 4 bytes of a State column and one word of the AES round key; it can also be viewed as a byte-level operation. The following is an AddRoundKey example Transform: Example of AddRoundKey: 47 40 A3 4C AC 19 28 57 EB 59 8B 1B A peek inside AES: Not examinable 37 D4 70 9F 77 FA D1 5C 40 2E A1 C3 94 E4 3A 42 ! 66 DC 29 00 = F2 38 13 42 ED A5 A6 BC F3 21 41 6A 1E 84 E7 D6 The The128 first bits of isthe matrix state State, arethebitwise and second XORed matrix is with the 128 the round key. bits of inverse Theround the keyadd round key transformation is identical to the forward add round key transformation, because the XOR operation is its own inverse. RATIONALE The add round key transformation is as simple as possible and affects © Anwitaman DATTA every bit of State. The complexity of the round key expansion, plus the complexity of the other stages of AES, ensure security. Figure 5.8 is another view of a single round of AES, emphasizing the mecha- nisms and inputs of each transformation.  AES wrap-up - The cipher begins and ends with an AddRoundKey stage. Why? Symmetric key cryptography It’s in effect a Vernam (one-time pad) cipher - The other three stages together provide confusion, diffusion and non-linearity, but by themselves, they provide no security. Why? No secrets involved in the other steps © Anwitaman DATTA  Beyond a block - Making do with a broken/obsolete cipher - Encrypting data larger than the block size Symmetric key cryptography - Realizing stream cipher using a block cipher © Anwitaman DATTA  P = D(K1, D(K2, C)) or DES, this scheme apparently involves a key length of 56 * 2 = 112 bits, result- 1998, DES broken! ng in a dramatic increase in cryptographic strength. But we need to examine the lgorithm more closely. Use DES multiple times in a cascade! How many times? Symmetric key cryptography K1 K2 X E E C © Anwitaman DATTA P Encryption Use DES twice, with two keys - It “may” helpK2us achieve an effective K1 key size of 2×56 = 112 bits?  P = D(K1, D(K2, C)) For DES, this scheme apparently involves a key length of 56 * 2 = ing in a dramatic increase in cryptographic strength. But we need t 2DES algorithm more closely. Use DES twice, with two keys K1 K2 - It “may” help us achieve an effective key size Symmetric key cryptography X of 2×56 = 112 bits? P E E C Encryption Any (potential) concerns? K2 K1 X C D D P © Anwitaman DATTA Decryption (a) Double encryption K1 K2 K1 A B P E D E Encryption  P = D(K1, D(K2, C)) For DES, this scheme apparently involves a key length of 56 * 2 = ing in a dramatic increase in cryptographic strength. But we need t 2DES algorithm more closely. Use DES twice, with two keys K1 K2 - It “may” help us achieve an effective key size Symmetric key cryptography X of 2×56 = 112 bits? P E E C Encryption Any (potential) concerns? K2 K1 Potential issue #1: C D X D P - What if: © Anwitaman DATTA Decryption Turns out not to be of concern! (a) Double encryption K1 K2 K1 A B P E D E Encryption  P = D(K1, D(K2, C)) For DES, this scheme apparently involves a key length of 56 * 2 = ing in a dramatic increase in cryptographic strength. But we need t 2DES algorithm more closely. Use DES twice, with two keys K1 K2 - It “may” help us achieve an effective key size Symmetric key cryptography X of 2×56 = 112 bits? P E E C Encryption Any (potential) concerns? K2 K1 Potential issue #2: C D X D P - Exploit: © Anwitaman DATTA Decryption Meet-in-the-middle attack using known plain/cipher-text (a) Doublepairs encryption K1 K2 K1 That’s why one needs 3DES P E A D Encryption B E  Not fitting in a block, now what? 1 byte of data comes intermittently, block cipher Symmetric key cryptography has128 bits input/128 bits output... 1KB data, block cipher has 128 bits input © Anwitaman DATTA... 1TB data, block cipher has 128 bits input  Plaintext is larger than block size - Simplest solution: Just chunk the plaintext and encrypt separately - This is known as Electronic Code Book (ECB) Symmetric key cryptography 200 CHAPTER 6 / BLOCK CIPHER OPERATION P1 P2 PN K K K © Anwitaman DATTA Encrypt Encrypt Encrypt C1 C2 CN (a) Encryption  Plaintext is larger than block size - Simplest solution: Just chunk the plaintext and encrypt separately - This is known as Electronic Code Book (ECB) Symmetric key cryptography - ECB is good for short messages, but not for large ones (particularly if plain-text is likely to repeat, since then, so will the cipher-text!) © Anwitaman DATTA  ship to the plaintext block.Therefore, repeating patterns of b bits are not exposed.As with the ECB mode, the CBC mode requires that the last block be padded to a full b bits if it is a partial block. Plaintext is larger than block size For decryption, each cipher block is passed through the decryption algorithm. The result is XORed with the preceding ciphertext block to produce the plaintext block. To see that this works, we can write Cipher block chaining (CBC) Cj = E(K, [Cj - 1 ! Pj]) - Design concern: choosing a good initial vector (IV) - Limitation: No “random access” since decryption is possible only in stages Symmetric key cryptography P1 P2 PN IV CN–1 K K K © Anwitaman DATTA Encrypt Encrypt Encrypt C1 C2 CN (a) Encryption  Stream cipher with a block cipher? Cipher Feedback Mode (CFB) - The plain-text is not itself being input to the cipher, but the bit-string 204 CHAPTER 6 / BLOCK CIPHER OPERATION Symmetric key cryptography being XORed with the plaintext depends on the prior plain-text CN–1 Shift register Shift register IV b – s bits s bits b – s bits s bits K K K Encrypt Encrypt Encrypt © Anwitaman DATTA Select Discard Select Discard Select Discard s bits b – s bits s bits b – s bits s bits b – s bits s bits s bits s bits P1 P2 PN C1 C2 CN s bits s bits s bits (a) Encryption - Note: there are other ways to realize a stream cipher using a block cipher A note on cryptanalysis © Anwitaman DATTA  Kerckhoffs' Auguste Kerckhoffs (1835-1903) principle © Anwitaman DATTA a cryptosystem should be secure, even if everything about the system, except the key, is public knowledge in contrast to security through obscurity PUBLIC KEY CRYPTO © Anwitaman DATTA  System model Alice creates a private/public key pair - Knowing just the public key, one cannot infer the Asymmetric key cryptography private key - Data is encrypted with one key but it can be decrypted only with the other key (and not with the encryption key!) So then, knowing plain/cipher-text pair in itself should also not compromise the cipher (e.g., by disclosing the © Anwitaman DATTA private key).  System model - Alice keeps the private key Asymmetric key cryptography - Everyone and their cat can have the public key © Anwitaman DATTA  Either of the two related keys can be used for encryption, with the other used for decryption. Confidential communication A public-key encryption scheme has six ingredients (Figure 9.1a; compare with Figure 2.1). Assuming a mechanism Confidential info to guarantee this Bobs's e.g., trusted PKI public key Publicly known info Asymmetric key cryptography ring Joy Ted Alice Receiver’s Mike Public Key PUa Alice's public PRa Alice's private key key X= © Anwitaman DATTA Transmitted X ciphertext D[PRa, Y] Y = E[PUa, X] Plaintext Plaintext Encryption algorithm Decryption algorithm input output (e.g., RSA) Bob (a) Encryption with public key Alice  Transmitted X= X ciphertext D[PRa, Y] Y = E[PUa, X] Authentication Plaintext input Encryption algorithm (e.g., RSA) Decryption algorithm Plaintext output Digital signature Bob (a) Encryption with public key Alice Confidential info Asymmetric key cryptography Alice's public key Publicly known info ring Joy Ted Sender’s Bob Mike Private Key PRb Bob's private PUb Bob's public key key X= © Anwitaman DATTA X Transmitted D[PUb, Y] ciphertext Y = E[PRb, X] Plaintext Plaintext Encryption algorithm Decryption algorithm input output (e.g., RSA) Note: Not all public-key cryptosystems Bob (b) Encryption with private key Alice support use of either key for encryption, Figure 9.1 Public-Key Cryptography and the other for decryption.  Authentication Digital signature: A more pragmatic approach Asymmetric key cryptography For confidentiality: © Anwitaman DATTA - Need to encrypt the whole digitally signed data as the plaintext. - Four encrypt/decrypt operations! Note: We will discuss later more about certificates and hash functions  Putting things together Authentication and confidentiality: both together, efficiently Asymmetric key cryptography message message encrypt/sign with append signed hash hash sender’s private key with message PKI generate a (symmetric crypto) session key we know? © Anwitaman DATTA How do append and transmit encrypt the session key encrypt with the w/ receiver’s public key session key Note: The certificate has not been shown here explicitly, but may also be part of the payload  Session key - Why not establish a symmetric key once and reuse it across different sessions? Asymmetric key cryptography © Anwitaman DATTA  Trap door functions - Easy to compute in one direction - Difficult to compute in other direction (finding the inverse) Asymmetric key cryptography but easy to compute, with some special information (trapdoor) i ng t go k! c no ba © Anwitaman DATTA  Trap door functions A peek inside RSA: Not examinable Most widely-used public-key algorithms rely on the difficulty of one of three mathematical problems: - the integer factorization problem (RSA assumption) - the discrete logarithm problem - the elliptic-curve discrete logarithm problem © Anwitaman DATTA  Post Quantum Crypto Shor’s algorithm, relying on a Quantum computer, renders the afore-mentioned hard Asymmetric key cryptography problems easy to solve! Necessitating new quantum-resistant cryptographic solutions! © Anwitaman DATTA  Public Key Infrastructure - A certificate authority (CA): issues, signs and stores the digital certificates Asymmetric key cryptography - digitally sign (using the CA's own private key) and publish the public key bound to a given user. - Certificate chain - A registration authority (RA): the identification and authentication of certificate applicants, the approval or rejection of certificate applications, initiating certificate revocations or suspensions under certain circumstances, processing subscriber requests to revoke or suspend their certificates, and © Anwitaman DATTA approving or rejecting requests by subscribers to renew or re-key their certificates [Definition as per The Internet Engineering Task Force's RFC 3647] - RAs, how