Network Security Public Key Cryptography 02/27/06 Hofstra University Network Security Course, CSC290A 1 Public Key Cryptography Agenda: Message authentication authentication codes and hash functions Public key encryption

principles and algorithms Exchange of conventional keys Digital signatures Revisit key management 02/27/06 Hofstra University Network Security Course, CSC290A 2 Recall Security Services Confidentiality protection from passive attacks Authentication you are who you say you are

Integrity received as sent, no modifications, insertions, shuffling or replays 02/27/06 Hofstra University Network Security Course, CSC290A 3 Security Attacks Passive threats Release of message contents

Traffic analysis eavesdropping, monitoring transmissions conventional encryption helped here 02/27/06 Hofstra University Network Security Course, CSC290A 4 Security Attacks

On the Internet, nobody knows youre a dog - by Peter Steiner, New York, July 5, 1993 02/27/06 Hofstra University Network Security Course, CSC290A 5 Security Attacks Active threats Masquerad e Replay

Modification of message contents Denial of service Message authentication helps prevents these! 02/27/06 Hofstra University Network Security Course, CSC290A

6 What Is Message Authentication Its the source, of course! Procedure that allows communicating parties to verify that received messages are authentic Characteristics: source is authentic masquerading contents unaltered message modification timely sequencing replay 02/27/06 Hofstra University Network

Security Course, CSC290A 7 Can We Use Conventional Encryption? Only sender and receiver share a key Include a time stamp Include error detection code and sequence number 02/27/06 Hofstra University Network Security Course, CSC290A

8 Message Authentication Sans Encryption Append an authentication tag to a message Message read independent of authentication function No message confidentiality 02/27/06 Hofstra University Network Security Course, CSC290A

9 Message Authentication w/o Confidentiality Application that broadcasts a message only one destination needs to monitor for authentication Too heavy a load to decrypt random authentication checking Computer executables and files checked when assurance required 02/27/06 Hofstra University Network Security Course, CSC290A

10 Life Without Authentication 02/27/06 Hofstra University Network Security Course, CSC290A 11 Message Authentication Code Message Authentication Code (MAC) use a secret key to

generate a small block of data that is appended to the message Assume: A and B share a common secret key KAB MACM = F(KAB,M) 02/27/06 Hofstra University Network Security Course, CSC290A 12 Message Authentication Code 02/27/06

Hofstra University Network Security Course, CSC290A 13 Message Authentication Code Receiver assured that message is not altered no modification Receiver assured that the message is from the alleged sender no masquerading Include a sequence number, assured proper sequence no replay

02/27/06 Hofstra University Network Security Course, CSC290A 14 Message Authentication Code DES is used Need not be reversible Checksum Stands up to attack But there is an alternative... 02/27/06

Hofstra University Network Security Course, CSC290A 15 One Way Hash Function Hash function accepts a variable size message M as input and produces a fixed-size message digest H(M) as output No secret key as input Message digest is sent with the message for authentication Produces a fingerprint of the message

02/27/06 Hofstra University Network Security Course, CSC290A 16 One Way Hash Function Message digest H(M) Shared key Authenticity is assured 02/27/06

Hofstra University Network Security Course, CSC290A 17 One Way Hash Function Digital signature No key distribution Less computation since message does not have to be encrypted 02/27/06 Hofstra University Network Security Course, CSC290A

18 One Way Hash Function Ideally We Would Like To Avoid Encryption Encryption software is slow Encryption hardware costs arent cheap Hardware optimized toward large data sizes Algorithms covered by patents Algorithms subject to export control 02/27/06 Hofstra University Network

Security Course, CSC290A 19 One Way Hash Function Assumes secret value SAB MDM||M MDM = H(SAB||M) No encryption for message authentication Secret value never sent; cant modify the message Important technique for Digital Signatures 02/27/06 Hofstra University Network

Security Course, CSC290A 20 Hash Function Requirements 1. 2. 3. wea k 4.

5. 6. H can be applied to a block of data of any size H produces a fixed length output H(x) is relatively easy to compute For any given code h, it is computationally infeasible to find x such that H(x) = h one For any given block x, itway is computationally infeasible to find y x with H(y) = H(x)

weak collision resistance It is computationally infeasible to find strong any pair (x,y) such that H(x) = H(y) 02/27/06 Hofstra University Network Security Course, CSC290A 21 Simple Hash Functions Input: sequence of n-bit block

Processed: one block at a time producing an n-bit hash function Simplest: Bit-by-bit XOR of every block C i =b i1 b i2 b im Longitudinal redundancy check 02/27/06 Hofstra University Network Security Course, CSC290A 22 Bitwise XOR Problem: Eliminate predictability of data One-bit circular shift for each block is

used to randomize the input 02/27/06 Hofstra University Network Security Course, CSC290A 23 SHA-1 Secure Hash Function Developed by NIST in 1995 Input is processed in 512-bit blocks Produces as output a 160-bit message digest Every bit of the hash code is a function of every bit of the input

Very secure so far! 02/27/06 Hofstra University Network Security Course, CSC290A 24 SHA-1 Secure Hash Function append append padding bits length

output compression function Every bit of the hash code is a function of every bit of the input! 02/27/06 Hofstra University Network Security Course, CSC290A 25 SHA-1 Secure Hash Function

02/27/06 Hofstra University Network Security Course, CSC290A 26 Other Hash Functions Most follow basic structure of SHA-1 This is also called an iterated hash function Ralph Merkle 1979 If the compression function is collision resistant, then so is the resultant iterated hash function Newer designs simply refine this structure

02/27/06 Hofstra University Network Security Course, CSC290A 27 MD5 Message Digest Ron Rivest - 1992 RFC 1321 Input: arbitrary Output: 128-bit digest Most widely used secure hash algorithm until recently Security of 128-bit hash code has

become questionable (1996, 2004) 02/27/06 Hofstra University Network Security Course, CSC290A 28 RIPEMD-160 European RIPE Project 1997 Same group launched an attack on MD5 Extended from 128 to 160-bit message digest 02/27/06

Hofstra University Network Security Course, CSC290A 29 HMAC Effort to develop a MAC derived from a cryptographic hash code Executes faster in software No export restrictions Relies on a secret key RFC 2104 list design objectives Used in Ipsec Simultaneously verify integrity and authenticity

02/27/06 Hofstra University Network Security Course, CSC290A 30 HMAC Structure Message, M secret key output 02/27/06

By passing Si and So through the hash algorithm, we have pseudoradomly generated two keys from K. Hofstra University Network Security Course, CSC290A 31 Public Key Encryption Diffie and Hellman 1976 First revolutionary advance in

cryptography in thousands of years Based on mathematical functions not bit manipulation Asymmetric, two separate key Profound effect on confidentiality, key distribution and authentication 02/27/06 Hofstra University Network Security Course, CSC290A 32 Public Key Encryption Whitfield Diffie

Martin Hellman Famous Paper: New Directions In Cryptography - 1976 02/27/06 Hofstra University Network Security Course, CSC290A 33 Public Key Structure Plaintext: message input into the algorithm Encryption algorithm: transformations

on plaintext Public & Private Key: pair of keys, one for encryption; one for decryption Ciphertext: scrambled message Decryption algorithm: produces original plaintext 02/27/06 Hofstra University Network Security Course, CSC290A 34 Folklore 1969 Alternative Culture Film The names have stuck

This is meaningless trivia!!! 02/27/06 Hofstra University Network Security Course, CSC290A 35 Public Key Encryption 02/27/06 Hofstra University Network Security Course, CSC290A

36 The Basic Steps Each user generates a pair of keys The public key goes in a public register The private key is kept private If Bob wishes to send a private message to Alice, Bob encrypts the message using Alices public key When Alice receives the message, she decrypts using her private key 02/27/06 Hofstra University Network Security Course, CSC290A

37 Public Key Authentication 02/27/06 Hofstra University Network Security Course, CSC290A 38 Public Key Applications Encryption/decryption encrypts a message with the recipients public key

Digital signature sender signs a message with private key Key Exchange two sides cooperate to exchange a session key 02/27/06 Hofstra University Network Security Course, CSC290A 39 Requirements For Public Key HINT:

PUBLIC PRIVATE Easy for party B to generate pairs: public key KUb ; private key KRb Easy for sender A to generate cipertext using public key: C = E KUb(M) Easy for receiver B to decrypt using the private key to recover original message M = DKRb(C) = DKRb[E KUb(M)] 02/27/06 Hofstra University Network

Security Course, CSC290A 40 Requirements For Public Key It is computationally infeasible for an opponent, knowing the public key KUb to determine the private key KRb It is computationally infeasible for an opponent, knowing the public key KUb and a ciphertext, C, to recover the original message, M Either of the two related keys can be used for encryption, with the other used for decryption

M = DKRb[EKUb(M)]= DKUb[EKRb(M)] 02/27/06 Hofstra University Network Security Course, CSC290A 41 RSA Algorithm Ron Rivest, Adi Shamir, Len Adleman 1978 Most widely accepted and implemented approach to public key encryption Block cipher where M and C are integers between 0 and n-1 for some n Following form:

C = Me mod n M = Cd mod n = (Me)d mod n = Med mod n 02/27/06 Hofstra University Network Security Course, CSC290A 42 RSA Algorithm Sender and receiver know the values of n and e, but only the receiver knows the value of d Public key: KU = {e,n} Private key: KR = {d,n}

02/27/06 Hofstra University Network Security Course, CSC290A 43 RSA Requirements It is possible to find values of e, d, n such that Med = M mod n for all M

magic! 02/27/06 Hofstra University Network Security Course, CSC290A 44 RSA Algorithm 02/27/06 Hofstra University Network Security Course, CSC290A 45

RSA Algorithm 02/27/06 Hofstra University Network Security Course, CSC290A 46 RSA Example Select two prime numbers, p=7 and q=17 this is the Calculate n = pq = 7 x 17 = 119 modulus Euler

Calculate (n) = (p-1)(q-1) = 96 totient Select e such that e is relatively prime to (n) = 96 and less than (n) ; in this case, e= 5 Determine d such that de = 1 mod 96 and d<96. The correct value is d = 77, because multiplicative inverse 77 x 5 = 385 = 4 x 96 + 1 of e 02/27/06 Hofstra University Network Security Course, CSC290A

47 RSA Example M C e 02/27/06 M d Hofstra University Network Security Course, CSC290A

48 RSA Strength Brute force attack: try all possible keys the larger e and d the more secure The larger the key, the slower the system For large n with large prime factors, factoring is a hard problem Cracked in 1994 a 428 bit key; $100 Currently 1024 key size is considered strong enough 02/27/06

Hofstra University Network Security Course, CSC290A 49 Diffie-Hellman Key Exchange Enables two users to exchange a secret key securely. 02/27/06 Hofstra University Network Security Course, CSC290A 50

Diffie-Hellman Key Exchange 02/27/06 Hofstra University Network Security Course, CSC290A 51 Diffie-Hellman Key Exchange 02/27/06

Hofstra University Network Security Course, CSC290A 52 Other Public Key Algorithms Digital Signature Standard (DSS) makes use of SHA-1 and presents a new digital signature algorithm (DSA) Only used for digital signatures not encryption or key exchange 02/27/06

Hofstra University Network Security Course, CSC290A 53 Other Public Key Algorithms Elliptic Curve Cryptography (ECC) it is beginning to challenge RSA Equal security for a far smaller bit size Confidence level is not as high yet 02/27/06 Hofstra University Network

Security Course, CSC290A 54 Digital Signatures Use the private key to encrypt a message Entire encrypted message serves as a digital signature Encrypt a small block that is a function of the document, called an authenticator (e.g., SHA-1) 02/27/06 Hofstra University Network Security Course, CSC290A

55 Public Key Authentication 02/27/06 Hofstra University Network Security Course, CSC290A 56 Digital Certificate Certificate consists of a public key plus a user ID of the key owner,

with the whole block signed by a trusted third party, the certificate authority (CA) X.509 standard SSL, SET and S/MIME Verisign is primary vendor 02/27/06 Hofstra University Network Security Course, CSC290A 57 Public Key Certificate Use 02/27/06

Hofstra University Network Security Course, CSC290A 58 Important URLs http://www.abanet.org/scitech/ec/isc/dsg-tutoria l.html Discusses the legal implications of digital signature usage. (American Bar Association) http://www.rsasecurity.com/rsalabs/cryptobytes/ index.html Take a look at Volume 2, No. 1 - Spring 1996 for the Aysmmetric Encryption: Evolution and Enhancements

02/27/06 Hofstra University Network Security Course, CSC290A 59 Homework Read Chapter Three Scan Appendix 3A 02/27/06 Hofstra University Network Security Course, CSC290A

60 Assignment 1 Pick sun.com and one other site. Using whois and ARIN, get as much information as possible about the IP addressing, the DNS and the site (location, owner, etc.) Problems (p83): 3.5,c and 3.6 Due next class March 6 02/27/06 Hofstra University Network Security Course, CSC290A

61