Lecture 3: Cryptography II CS 336/536: Computer Network Security Fall 2015 Nitesh Saxena Course Administration Everyone receiving my emails? Lecture slides worked okay? Both ppt and pdf versions Everyone knows how to access the course web page? HW/Lab 1 heads up To be posted coming Monday Labs become active starting next week

NO LAB THIS WEEK 2 Outline of Todays Lecture Block Cipher Modes of Encryption Public Key Crypto Overview and Math Background Public Key Encryption (RSA) Public Key Signatures 3 Block Cipher Encryption Modes 02/26/20

Lecture 1 - Introduction 4 Block Cipher Encryption modes Electronic Code Book (ECB) Cipher Block Chain (CBC) Most popular one Others (we will not cover) Cipher Feed Back (CFB) Output Feed Back (OFB) 02/26/20

Lecture 2 - Cryptography - I 5 Analysis We will analyze each mode in terms of: Security Computational Efficiency (parallelizing encryption/decryption) Transmission Errors Integrity Protection 02/26/20

Lecture 2 - Cryptography - I 6 Electronic Code Book (ECB) Mode Although DES encrypts 64 bits (a block) at a time, it can encrypt a long message (file) in Electronic Code Book (ECB) mode. Deterministic -- If same key is used then identical plaintext blocks map to identical ciphertext 02/26/20 Lecture 2 - Cryptography - I

7 Example why ECB is bad? Tux 02/26/20 Tux encrypted with AES in ECB mode Lecture 2 - Cryptography - I 8 Cipher Block Chain (CBC) Mode encryptio

n decryptio n 02/26/20 Lecture 2 - Cryptography - I 9 CBC Traits Randomized encryption IV Initialization vector serves as the randomness for first block computation; the

ciphertext of the previous block serves as the randomness for the current block computation IV is a random value IV is no secret; it is sent along with the ciphertext blocks (it is part of the ciphertext) 02/26/20 Lecture 2 - Cryptography - I 10 Example why CBC is good? Tux 02/26/20

Tux encrypted with AES in CBC mode Lecture 2 - Cryptography - I 11 CBC More Properties What happens if k-th cipher block CK gets corrupted in transmission. With ECB Only decrypted PK is affected. With CBC? Only blocks PK and PK+1 are affected!! What if one plaintext block PK is changed?

With ECB only CK affected. With CBC all subsequent ciphertext blocks will be affected. Avalanche effect This leads to an effective integrity protection mechanism (or message authentication code (MAC)) 02/26/20 Lecture 2 - Cryptography - I 12 Security of Block Cipher Modes

ECB is not even secure against eavesdroppers (ciphertext only and known plaintext attacks) CBC is secure against CPA attacks (assuming 3DES or AES is used in each block computation); automatically secure against eavesdropping attacks However, not secure against CCA. Why? Intuitively, this is because the ciphertext can be massaged in a meaningful way 13 CBC Mode CCA Attack Assume adversary has eavesdropped upon a ciphertext (C0, C1, C2) -- corresponding to a plaintext (M1, M2). C0 is IV. Adversary is not allowed to query for (C0, C1, C2) itself

With CBC, adversary queries for (C0, C1, C2) and obtains (M1, M2) [X denotes bit-wise complement of X] 14 How to achieve CCA security? Prevent any massaging of the ciphertext Intuitively, this can be achieved by using integrity protection mechanisms (such as MACs), which we will study later The ciphertext is generated using CBC and a MAC is generated on this ciphertext Both ciphertext and the MAC is sent off The other party decrypts only if MAC is valid

02/26/20 Lecture 2.3 - Private Key Cryptography III 15 Advanced Encryption Standard (AES) National Institute of Science and Technology DES is an aging standard that no longer addresses todays needs for strong encryption Triple-DES: Endorsed by NIST as todays defacto standard

AES: The Advanced Encryption Standard Finalized in 2001 Goal To define Federal Information Processing Standard (FIPS) by selecting a new powerful encryption algorithm suitable for encrypting government documents AES candidate algorithms were required to be: Symmetric-key, supporting 128, 192, and 256 bit keys Royalty-Free Unclassified (i.e. public domain) Available for worldwide export 02/26/20

Lecture 2.3 - Private Key Cryptography III 16 AES AES Round-3 Finalist Algorithms: MARS Candidate offering from IBM RC6 Developed by Ron Rivest of RSA Labs, creator of the widely used RC4 algorithm Twofish

From Counterpane Internet Security, Inc. Serpent Designed by Ross Anderson, Eli Biham and Lars Knudsen Rijndael: the winner! Designed by Joan Daemen and Vincent Rijmen 02/26/20 Lecture 2.3 - Private Key Cryptography III 17

Other Symmetric Ciphers and their applications IDEA (used in PGP) Blowfish (password hashing in OpenBSD) RC4 (used in WEP), RC5 SAFER (used in Bluetooth) 02/26/20 Lecture 2.3 - Private Key Cryptography III

18 Some Questions Double encryption in DES increases the key space size from 2^56 to 2^112 true or false? Is known-plaintext an active or a passive attack? Is chosen-ciphertext attack an active or a passive attack? Reverse Engineering is applied to what design of systems open or closed? Alice needs to send a 64-bit long top-secret letter to Bob. Which of the ciphers that we studied today should she use?

02/26/20 Lecture 2.2 - Private Key Cryptography II 19 Some Questions C=DES(K,P); where (P, C are 64-bit long blocks). What would be DES(K,PPPP) in ECB mode? What it would be in CBC mode? ECB is secure for sending just one block of data: true or false? Is it okay to re-use IV in CBC? Why/why not? Is ECB secure against CPA?

Is CBC secure against CPA? 02/26/20 Lecture 2.3 - Private Key Cryptography III 20 Public Key Crypto Overview and Math Background 02/26/20 Lecture 1 - Introduction

21 Recall: Private Key/Public Key Cryptography Private Key: Sender and receiver share a common (private) key Encryption and Decryption is done using the private key Also called conventional/shared-key/single-key/ symmetric-key cryptography Public Key: Every user has a private key and a public key

Encryption is done using the public key and Decryption using private key Also called two-key/asymmetric-key cryptography 22 Private key cryptography revisited. Good: Quite efficient Bad: Key distribution and management is a serious problem 23 Public key cryptography model Good: Key management problem potentially simpler

Bad: Much slower than private key crypto (well see later!) 24 Public Key Encryption Two keys: public encryption key e private decryption key d Encryption easy when e is known Decryption easy when d is known

Decryption hard when d is not known Well study such public key encryption schemes; first we need some mathematical background. 25 Public Key Encryption: Security Notions Very similar to what we studied for private key encryption Whats the difference? 26 Group: Definition

(G,.) (where G is a set and . : GxGG) is said to be a group if following properties are satisfied: 1. Closure : for any a, b G, a.b G 2. Associativity : for any a, b, c G, a.(b.c)=(a.b).c 3. Identity : there is an identity element such that a.e = e.a = a, for any a G 4. Inverse : there exists an element a-1 for every a in G, such that a.a-1 = a-1.a = e 02/26/20 Lecture 1 - Introduction 27

Groups: Examples Set of all integers with respect to addition --(Z, +) Set of all integers with respect to multiplication (Z,*) not a group Set of all real numbers with respect to multiplication (R,*) Set of all integers modulo m with respect to modulo addition (Zm, modular addition) 28 Multiplicative inverses in Zm 1 is the multiplicative identity in Zm x 1 x(mod m) 1 x(mod m)

Multiplicative inverse (x*x-1=1 mod m) SOME, but not ALL elements have unique multiplicative inverse. In Z9 : 3*0=0, 3*1=3, 3*2=6, 3*3=0, 3*4=3, 3*5=6, , so 3 does not have a multiplicative inverse (mod 9) On the other hand, 4*2=8, 4*3=3, 4*4=7, 4*5=2, 4*6=6, 4*7=1, so 4-1=7, (mod 9) 02/26/20 Public Key Cryptography -- II 29 Which numbers have inverses?

In Zm, x has a multiplicative inverse if and only if x and m are relatively prime or gcd(x,m)=1 E.g., 4 in Z9 02/26/20 Public Key Cryptography -- II 30 Modular Exponentiation: Square and Multiply method Usual approach to computing xc mod n is inefficient when c is large. Instead, represent c as bit string bk-1 b0 and

use the following algorithm: z = 1 For i = k-1 downto 0 do z = z2 mod n if bi = 1 then z = z* x mod n 02/26/20 Public Key Cryptography -- II 31 Example: 30 mod 77 37

z = z2 mod n if bi = 1 then z = z* x mod n i 02/26/20 b z 5 1 30

= 1*1*30 mod 77 4 0 53 = 30*30 mod 77 3 0

37 = 53*53 mod 77 2 1 29 77 = 37*37*30 mod 1

0 71 = 29*29 mod 77 0 1 2 = 71*71*30 mod 77

Public Key Cryptography -- II 32 Other Definitions The number of elements in a group is called the order of the group Order of an element a is the lowest i (>0) such that ai = e (identity) Public Key Cryptography -- II 33 Lagranges Theorem

Order of an element in a group divides the order of the group 02/26/20 Public Key Cryptography -- II 34 Eulers totient function Given positive integer n, Eulers totient function (n) is the number of positive numbers less than n that are relatively prime to n ( p ) p 1

Fact: If p is prime then {1,2,3,,p-1} are relatively prime to p. 02/26/20 Public Key Cryptography -- II 35 Eulers totient function Fact: If p and q are prime and n=pq then (n) ( p 1)(q 1) Each number that is not divisible by p or by

q is relatively prime to pq. E.g. p = 5, q = 7: {1,2,3,4,-,6,-,8,9,-,11,12,13,-,-,16,17,18,19,-,-,22 ,23,24,-,26,27,-,29,-,31,32,33,34,-} pq p - (q-1) = (p-1)*(q-1) 02/26/20 Public Key Cryptography -- II 36 Eulers Theorem and Fermats Theorem If a is relatively prime to n then ( n ) a

1 mod n If a is relatively prime to p then ap-1 = 1 mod p Proof : follows from Lagranges Theorem 02/26/20 Public Key Cryptography -- II 37 Eulers Theorem and Fermats Theorem EG: Compute 9100 mod 17: p =17, so p-1 = 16. 100 = 616+4. Therefore, 9100=9616+4=(916)6(9)4 . So mod 17 we have 9100

(916)6(9)4 (mod 17) (1)6(9)4 (mod 17) (81)2 (mod 17) 16 02/26/20 Public Key Cryptography -- II 38 Some questions 2-1 mod 4 =? Find x such that x = 4 (mod 5) x = 7 (mod 8) x = 3 (mod 9)

Order of a group is 5. What can be the order of an element in this group? 02/26/20 Public Key Cryptography -- II 39 Further Reading Chapter 4 of Stallings Chapter 2.4 of HAC 02/26/20

Public Key Cryptography -- II 40 The RSA Cryptosystem (Encryption) 41 Textbook RSA: KeyGen Alice wants people to be able to send her encrypted messages. She chooses two (large) prime numbers, p and q and computes n=pq and (n). [large = 1024 bits +] She chooses a number e such that e is relatively prime to (n) and computes d, the inverse of e in Z (n ) , i.e., ed =1 mod (n)

She publicizes the pair (e,n) as her public key. (e is called RSA exponent, n is called RSA modulus). She keeps d secret and destroys p, q, and (n) Plaintext and ciphertext messages are elements of Zn and e is the encryption key. 42 RSA: Encryption Bob wants to send a message x (an element of Zn*) to Alice. He looks up her encryption key, (e,n), in a directory. The encrypted message is e y E ( x) x mod n Bob sends y to Alice.

43 RSA: Decryption To decrypt the message e y E ( x) x mod n shes received from Bob, Alice computes d D( y ) y mod n Claim: D(y) = x 44 RSA: why does it all work

Need to show D[E[x]] = x E[x] and D[y] can be computed efficiently if keys are known E-1[y] cannot be computed efficiently without knowledge of the (private) decryption key d. Also, it should be possible to select keys reasonably efficiently This does not have to be done too often, so efficiency requirements are less stringent. 45 E and D are Inverses d

D( y ) y mod n ( x e mod n) d mod n e d ( x ) mod n x ed mod n x t ( n ) 1 ( x t mod n

Because ed 1 mod ( n) ( n ) t ) x mod n 1 x mod n x mod n From Eulers Theorem 46 Tiny RSA example. Let p = 7, q = 11. Then n = 77 and (n) 60

Choose e = 13. Then d = 13-1 mod 60 = 37. Let message = 2. E(2) = 213 mod 77 = 30. D(30) = 3037 mod 77=2 47 Slightly Larger RSA example. Let p = 47, q = 71. Then n = 3337 and

( pq) 46 * 70 3220 Choose e = 79. Then d = 79-1 mod 3220 = 1019. Let message = 688232 Break it into 3 digit blocks to encrypt. E(688) = 68879 mod 3337 = 1570. E(232) = 23279 mod 3337 = 2756 D(1570) = 15701019 mod 3337 = 688. D(2756) = 27561019 mod 3337 = 232. 48 Security of RSA: RSA assumption Suppose Oscar intercepts the encrypted message y that Bob has sent to Alice. Oscar can look up (e,n) in the public directory (just as Bob did when he encrypted the

message) If Oscar can compute d = e-1 mod (n)then he can use D ( y ) y d mod n x to recover the plaintext x. If Oscar can compute (n,) he can compute d (the same way Alice did). 49 Security of RSA: factoring Oscar knows that n is the product of two primes If he can factor n, he can compute (n) But factoring large numbers is very difficult: Grade school method takes

divisions. Prohibitive for large n, such asO160 ( n )bits Better factorization algorithms exist, but they are still too slow for large n Lower bound for factorization is an open problem 50 How big should n be? Today we need n to be at least 1024-bits This is equivalent to security provided by 80-bit long keys in private-key crypto No other attack on RSA function known Except some side channel attacks, based on

timing, power analysis, etc. But, these exploit certain physical charactesistics, not a theoretical weakness in the cryptosystem! 51 Key selection To select keys we need efficient algorithms to Select large primes Primes are dense so choose randomly. Probabilistic primality testing methods known. Work in logarithmic time. Compute multiplicative inverses Efficient algorithm (Extended Euclidean algorithm)

exists 52 RSA in Practice Textbook RSA is insecure Known-plaintext? CPA? CCA? In practice, we use a randomized version of RSA, called RSA-OAEP Use PKCS#1 standard for RSA encryption http://www.rsa.com/rsalabs/node.asp?id=2125 Interested in details of OAEP: refer to (section 3.1 of)

http://isis.poly.edu/courses/cs6903/Lectures/lecture13.pdf 53 Some questions c1 = RSA_Enc(m1), c2 = RSA_Enc(m2). What is RSA_Enc(m1m2)? Homomorphic property What is RSA_Enc(2m1)? Malleability (not a good property!) 54 Some Questions

RSA stands for Robust Security Algorithm, right? If e is small (such as 3) Encryption is faster than decryption or the other way round? Private key crypto has key distribution problem and Public key crypto is slow How about a hybrid approach? Do you know how ssl/ssh works? 55 Some Questions I encrypt m with Alices RSA PK, I get c I encryt m again, I get --? What does this mean?

What if I do the above with DES? 56 Further Reading Stallings Chapter 11 HAC Chapter 9 02/26/20 Lecture 4: Hash Functions 57

Digital Signatures 02/26/20 Lecture 1 - Introduction 58 Public Key Signatures Signer has public key, private key pair Signer signs using its private key Verifier verifies using public key of the signer Lecture 3.4: Public Key Cryptography IV

Security Notion/Model for Signatures Existential Forgery under (adaptively) chosen message attack (CMA) Adversary (adaptively) chooses messages mi of its choice Obtains the signature si on each mi Outputs any message m ( mi) and a signature s on m Lecture 3.4: Public Key Cryptography IV RSA Signatures

Key Generation: same as in encryption Sign(m): s = md mod N Verify(m,s): (se == m mod N) The above text-book version is insecure; why? In practice, we use a randomized version of RSA (implemented in PKCS#1) Hash the message and then sign the hash Lecture 3.4: Public Key Cryptography IV