CS 854 Hot Topics in Computer and Communications Security Fall 2006 Introduction to Cryptography and Security II 1 Announcements Paper assignments are nearly done See website Assignment: See website Due September 25 By email Please send all emails containing reviews, assignment solutions,.. to [email protected] Omit +cs854 if you have a question, want to set up an appointment,

2 System Model Alice and Bob want to communicate securely Trudy may intercept, delete, add, or modify messages Alice channel data secure sender data, control messages secure receiver Bob

data Trudy 3 Threat Model Q: What can a bad guy do? A: a lot! eavesdrop: passively intercept messages actively insert, modify, or delete messages into connection impersonation: can fake (spoof) source address in

network packet (or any field in packet) hijacking: take over ongoing connection by removing sender or receiver, inserting himself in place denial of service: prevent service from being used by others (e.g., by overloading resources) but (typically) not drop a nuclear bomb on Alice and Bob 4 The language of cryptography plaintext Alices K encryptio A n key encryption ciphertext algorithm

Bobs K decryptio Bn key decryption plaintext algorithm symmetric-key crypto: sender and receiver keys identical and secret public-key crypto: encryption key public, decryption key secret (private) 5 Block and Stream Ciphers Block cipher: operates on fix-sixed blocks at a time todays ciphers: 128 bits reversible plaintext and ciphertext have same size common key sizes: 128 or 256 bit Kerckhofs principle: structure of cipher is publicly known

Stream cipher: operates on single bit (byte) at a time 6 Public key cryptography + Bobs public B key K K plaintext encryption ciphertext + message, m algorithm K (m) B - Bobs private B key

decryption plaintext algorithm message - + m = KB (K (m)) B 7 RSA: another important property The following property will be very useful later: - + K (K (m)) B B + = m= K (K (m)) B B use private key first, followed by

public key Result is the same! use public key first, followed by private key 8 Overview Network security Symmetric-key encryption Public-key encryption Message integrity and authentication Entity authentication Key distribution Computer security 9 Digital Signatures Cryptographic technique analogous to

hand-written signatures. sender (Bob) digitally signs document, establishing he is document owner/creator. verifiable, nonforgeable, nonrepudiable: recipient (Alice) can prove to third party that Bob, and no one else (including Alice), must have signed document message integrity does not always require nonrepudiation See later 10 Digital Signatures - K , Bob signs m by applying his private key B - B(m) creating signature K KB Bobs private m, K - (m) B

key Bobs message, m Dear Alice Oh, how I have missed you. I think of you all the time! (blah blah blah) Signing algorithm Bobs message, m, and its digital signature Bob Algorithms: RSA - +

+ Remember K (K (m)) = m= K (K (m)) B B B B DSA (Digital Signature Algorithm) 11 Digital Signatures (more) Suppose Alice receives msg m, digital signature KB- (m) Alice verifies m signed by Bob by applying Bobs public key K +to K -(m) then checks K +(K (m) ) = m. B B B B

+ (m) If KB(K ) = m, whoever signed m must have used B Bobs private key. Alice thus verifies that: Bob signed m. No one else signed m. Bob signed m and not m. Non-repudiation: Alice can take m, and signature KB(m) to court and prove that Bob signed m. 12 (Cryptographic) Hash Functions Computationally expensive to sign long messages m Goal: fixed-length, easyto-compute digital fingerprint H(m) message digest, cryptographic hash

function can compute KB(H(m)) instead of KB(m) large message m H: Hash Function H(m) 13 Digital signature = signed message digest Bob sends digitally signed message: large message m

H: Hash function Bobs private key KB signature H(m) Signing algorithm signature + Alice verifies signature and integrity of digitally signed message:

KB(H(m)) KB(H(m)) large message Bobs m H: Hash function public key + KB Remove signature H(m)

H(m) equal ? 14 Properties of H(m) Input: arbitrarily long string of bits Output: fixed-size (i.e., H() is many to one) Given m, easy to compute H(m) One-way property/pre-image resistant For any given value x, it is computationally infeasible to find m such that H(m) = x Weak-collision resistance/2nd pre-image resistant For any given message m1, it is computationally infeasible to find m2 such that H(m1) = H(m2) Strong-collision resistance/collision resistance It is computationally infeasible to find a pair (m 1,m2)

such that H(m1) = H(m2) 15 Brute-Force Attacks Given: hash function with n-bit output Brute-force pre-image attack requires about 2n attempts Brute-force collision attack requires only 2n/2 attempts! Birthday paradox If 23 people in a room, chance that two of them will have same birthday exceeds 50% In general: approximately square root of #possible values 16 Hash Function Algorithms MD5 (RFC 1321) designed by Rivest in 1991, based on MD4, widely used

128-bit message digest MD5 is no longer strong-collision resistant but strong-collision resistance is only of theoretical interest? See assignment. stay away from MD5 SHA-1 ( NIST, FIPS PUB 180-1) designed by NSA, based on MD4 160-bit message digest security against collision-resistance has been weakened to (at most) 263 (brute force: 280) (maybe?) use SHA-256 17 (Other) Weaknesses of MD5/SHA-x Length extension: Given messages m1 and m2, where m2 = m1 || x, H(m2) can be computed based only on H(m1) and x (|| denotes concatenation) dont need m1 Attacker could add content

Partial-message collision: If H(m1) = H(m2), then H(m1||r) = H(m2||r) 18 Message Authentication Code (MAC) MAC allows Alice and Bob to communicate such that each of them can be sure that received messages were not tampered with no non-repudiation Keyed hash function can be used for implementing MAC e.g., x = SHA-1(k||m), transmit m and x

only Alice and Bob know k not secure against length-extension attack HMAC = H(k XOR a || H(k XOR b || m)) a,b: specified constants H: preferably SHA-256 19 Random Oracle Model Invented by Bellare and Rogaway in 1995 Build provably secure protocols based on random oracles Black box with state that responds to every query with a random response, except for already seen queries Actual protocol approximates random oracle with (efficient) real primitive

In practice, random oracles typically model cryptographic hash functions Today it is standard to prove a cryptographic protocol secure (at least) in the random oracle model Caveat: (contrived) protocols have been constructed that are provably secure in random oracle model, but insecure in real implementation 20 Random Oracle Model Real primitive is good if indistinguishable from random function of certain type Pseudorandom

Types of random oracles Random hash function models cryptographic hash Unlimited input to fixed output Random generator models stream cipher Fixed input to unlimited output Random permutation models block cipher Fixed input to fixed output 21 Overview Network security Symmetric-key encryption Public-key encryption Message integrity and authentication Entity authentication Key distribution

Computer security 22 Entity Authentication Prove that you are who you claim to be Based on what you know password what you own badge what you are fingerprint 23

Passwords User enters password, computer compares it with password in file Bad if file gets stolen Store only password hashes in file Use salt to avoid dictionary attacks due to weak passwords E.g., UNIX Susceptible to replay attacks if attacker can sniff traffic exchanged between user and computer Use secure channel (e.g., SSL, see later)

Challenge-response protocols Zero-knowledge protocols 24 Challenge-Response Symmetric-key techniques Assume that both parties know secret k B -> A: r A -> B: Ek(r) In practice, we want mutual authentication and agreement on session key Kerberos, Needham-Schroeder Require third party with whom each of A and B shares a secret Does not require shared secret between A and B 25 Needham-Schroeder Protocol 1. A -> T: A || B || NA

A: Alice B: Bob T: Trent 2. T -> A: KAT ( NA || K || B || KBT ( K || A ) ) 3. A -> B: KBT ( K || A ) 4. B -> A: K ( NB ) 5. A -> B: K ( NB - 1) vulnerable to a replay attack if an old session key has been compromised then message 3 can be resent convincing B that is communicating with A modifications to address this require: timestamps (Denning 81) or extra nonce (Neuman 93) 26 Challenge-Response Public-key techniques

Prove that other party owns private key corresponding to a public key Either by decrypting ciphertext or signing challenges Be careful about messages whose (seemingly random) content is (entirely) determined by somebody else Used in SSL (see later) Assumes that both parties have each others (authentic) public key 27 Signing Random Challenges Alice encrypts m with RSA and sends c = me to Bob Eve captures c, wants m Eve opens authenticated connection to

Alice, authentication based on signing of random challenges Eve computes c = rc, where r is random Eve asks Alice to sign c Alice returns cd = rcd = rmed = rm to Eve, since rm looks random Eve computes rm/r = m 28 Broken Challenge-Response Protocol I am Alice R Bob computes + - - K A (R) send me your public key

+ KA KA(K A(R)) = R + K (K (R)) = R A A and knows only Alice could have the private key, that encrypted R such that 29 Man (woman) in the middle attack Trudy poses as Alice (to Bob) and as Bob (to Alice) I am Alice R

I am Alice R K (R) T K (R) A Send me your public key + K T Send me your public key + K A - + m = K (K (m)) A A

+ K (m) A Trudy gets - + m = K (K (m)) T m T to sends Alice encrypted with Alices public key + K (m) T 30 Man (woman) in the middle attack

Trudy poses as Alice (to Bob) and as Bob (to Alice) Difficult to detect: Bob receives everything that Alice sends, and vice versa. (e.g., so Bob, Alice can meet one week later and recall conversation) problem is that Trudy receives all messages as well! 31 Zero-knowledge Techniques E.g., Secure Remote Password Protocol (SRP) User proves to server that he knows password without revealing any information about password to server (and eavesdropper) Server knows only (exponentiated) salted password hash

32 Alternatives to Passwords Weak password -> Dictionary attack Strong password -> Users forget it/write it down Alternatives: One-time passwords Typically requires hardware/software support Passphrases Also susceptible to dictionary attacks Biometrics What if my digitized fingerprint gets stolen?

Graphical passwords See later in course Client authentication is not sufficient, also require server authentication to avoid MITM or Phishing attacks 33 Good Cryptographic Practices Dont use encryption for message integrity Dont sign random messages Use session keys Dont use same key for multiple cryptographic algorithms in a protocol Order of authentication and encryption

authenticate-first can be (theoretically) insecure encrypt-first discards bogus messages earlier encrypt-first exposes authentication function to attacker encrypt-first authenticates ciphertext, not plaintext 34 Good Cryptographic Practices Use publicly reviewed cryptographic software packages if possible E.g., OpenSSL Use a good random number generator Design your own cryptographic protocol only if really necessary Consult experts, have it publicly reviewed Might still not be sufficient

35 Needham-Schroeder Public Key Authentication Protocol Provides public key retrieval and authentication T distributes public keys, A and B have Ts public key 1. A -> T: A, B 2. T -> A: KT- ( KB+, B ) 3. A -> B: KB+ ( NA, A ) 4. B -> T: B, A 5. T -> B: KT- ( KA+, A ) 6. B -> A: KA+ ( NA, NB ) 7. A -> B: KB+ ( NB ) 36 Needham-Schroeder Public Key Authentication Protocol Designed in 1978, serious flaw found in 1995 Concentrate on messages exchanging nonces

3. A -> B: KB+ ( NA, A ) 6. B -> A: KA+ ( NA, NB ) 7. A -> B: KB+ ( NB ) Mallory, M, while communicating with A, can impersonate A to B 3. A -> M: KM+ ( NA, A ) M -> B: KB+ ( NA, A ) Fix: include identity of 6. B -> M: KA+ ( NA, NB ) sender in 6 + M -> A: KA ( NA, NB ) 7. A -> M: KM+ ( NB ) Another flaw: encryption M -> B: KB+ ( NB ) is used for nonce integrity 37