Model
- Alice sends d0, d1, d2... to Bob
- Zeke controls network (can add, remove, modify msgs)
- Zeke's goal: get Bob to accept msg that Alice didn't send
- Alice and Bob don't care about confidentiality or availability
Can't solve with hashes alone (public hash function)
- Zeke can make fake msg and hash it
- Need something only Alice can do (Alice has a random secret key K from a large space)
- Assume Bob knows K
- Don't get something for nothing, need some shared secret. K exchanged previously.
- Leverage 1 secret (K) into integrity for whole channel.
Not a MAC address (used in networking)
Alice has data d, computes m = MAC(K,d)
- Alice sends (d,m) to Bob
- Zeke may alter this to (d', m')
- Bob accepts if m' = MAC(K,d'), ignores otherwise
Properties of MAC
- Maps 2 inputs (160 bit key and arbitrary size data) to 160-bit output
- "Strong MAC" definition:
- Imagine game where adversary knows MAC, but not K
- Adversary can choose d, and we tell him MAC(K, d)
- Adv. can study this as much as he wants
- Adv. picks a new d (different from previous ones) and guesses MAC(K,d)
- Adv. wins if does better than random guessing
- MAC strong if adv. can't win
- MAC like a black box
One more detail
- Zeke can't modify, but can reorder, add, remove msgs
- TCP/IP deals with added, removed, duplicated msgs: Use sequence numbers and retransmissions
- MAC must cover sequence number and data
- Send i, di, MAC(k, i || di ), where || is concatenation
- "glue" i and di together (i is number, di is ith msg)
First try: Hash (doesn't work)
- Use MAC(K,d) = Hash(K || d) [K is key, d is msg]
- Look at hash block diagram, and how it chains
- Adversary can extend message given H(K || d)
- Can compute H(K || d || x) = MAC(K, d || x)
- In reality, have padding in msg. before X. Can also use "this is end of msg" with escape characters. But still ugly.
Second try: Hash (doesn't work)
- Use MAC(K, d) = Hash(d || K) [concatenate in other order]
- Can't add msg, since need K at end
- Subtle birthday attack lets adversary cut search space
- 2^160 goes to 2^80 search space
- See 2 di's that have same MAC, can substitute them
HMAC: the MAC of choice
- HMAC(K,d) = Hash( (K XOR z1) || Hash( (K XOR z2) || d ) )
- z1 = 0x363636...
- z2 = 0x5c5c5c...
- Internet standard RFC 2104
- Theorem: if Hash is "strong" then HMAC is "strong"
Challenge/response login protocol
- User has K, server has K stored (K = password or Hash(password) )
- Server chooses random challenge R, sends to user
- User computes m = MAC(K, R), sends m to server
- Server accepts if received m = MAC(K, R)
Users carry own password info
- Server alone knows K
- Give Alice [name, Hash(password), expiration, MAC(K || name || Hash(password) || expiration) ]
- To login, alice provides [...] and password (server recomputes hash, MAC, etc. on its own)
- Server doesn't have to remember who is authorized, offload data to user
- Like server sending message to itself (it hashes message, give it to Alice. Later, she presents the msg the server originally created].
- Note: Alice never stores her password, only hash(password). Server MACs the hash, can check MAC in future.
Alice sends d0, d1, d2 ... to Bob
Goal: prevent Zeke from learning d0, d1, d2...
Use a "cipher" or "encryption algorithm"
Cipher model
- Alice takes message d, encrypts it with algorithm E and key K (call this result E_k(d) )
- Alice sends E_k(d) to Bob, visible by Zeke
- Bob decrypts with decrypt. alg. D, and key K [call this result D_k( E_k(d) ) ]
- Bob gets d back (since D_k and E_k are inverses)
- "Strong cipher" is one where adversary cannot guess d (after seeing E_k(d) ) better than chance
