Review until now
- Crypto for communication vs. for storage
- "" for confidentiality vs. integrity
- hybrids (email)
- common thread: key management
Key management: hard part of crypto
- teach principles, not tools, for key mgmnt
- each key has 1 purpose
- different key for sign and encrypt, so encryption not interpreted as signing
- different key for encrypting vs. MACing
- different for Alice -> Bob traffic vs. Bob -> Alice traffic
- reflection attack (send msgs back to sender). If same key, message appears valid
- want to avoid adversary "repurposing" content
Assume key's vulnerability increases ...
- the more you use it
- more places that it's stored
- longer you have it
- "Good for 1 year or 10,000 uses"
Other principles
- Change keys periodically
- Use temporary, throwaway keys where possible
- Be careful about where you keey your keeps (common vulnerability in storage)
- Adversary can record traffic, study and crack key later (be aware)
- Overwrite old keys in memory, don't let it get paged out to disk
What if don't use MAC, just encrypt msg and Hash(msg)?
[ msg H(msg) ] (encrypted)
[ msg XOR R1 H(msg) XOR R2 ]
[ msg' XOR R1 H(msg') XOR R2 ]
XOR-based crypto
- if adversary guesses msg, can determine R1
- then, can compute H(msg) and get R2
- if had used HMAC(K,msg) adversary can't compute HMAC because needs key
How to agree on shared secret key? Can use one key to generate more.
Diffie-Hellman alg. for key agreement
- relies on Discrete Log Problem (DLP)
- discrete log:
- given a prime p, and g properly chosen (generator Z*p)
- and given g^x mod p, find x (like finding log of g^x)
- as far as know, DLP is hard, no efficient alg. to find x
- no one has a proof it is hard, taken on faith
Method
Alice Bob
<----- agree publicly on p, g ----->
choose random a choose random b
compute g^a mod p, computer g^b mod p
send to Bob -------> <---- send to Alice
compute (g^b mod p)^a compute (g^a mod p)^b
= g^ba mod p = g^ab mod p
<==== two sides equal! shared secret g^ab mod p =====>
Adversary would have to solve DLP to get a or b.
- interesting: seems like getting something for nothing, a shared secret for nothing
- mysterious: public conversation generates private knowledge
Example: play chess vs. 2 grandmasters... they carry on conversations, you do their moves. Play black on one side, white on the other
Setup:
GM Bob: black Me: black
[ ] [ ]
Me: white GM Alice: white
I play 2 games, use moves of GM Bob against Alice, and vice versa. I can play like a grandmaster!
In terms of crypto...
Alice Zeke Bob
sends a ---> <---- sends b
<----- intercept a, send z1
intercept b, send z2 --->
<== shared secret g^az1 ====> <== shared secret g^az2 ==>
Zeke can read/change messages.
- D-H gives you a shared secret with someone, but don't know who it is
- Worry about man-in-middle attack
- Alice, Bob need direct connection to compare keys
- Each person generates private D-H key a. Compute public D-H key g^a mod p
- Publish everyone's public D-H keys
- Reuse a, g^a mod p every time you make connection
Can bob figure out a? No! Divide g^ab mod p by g^b mod p, just gives you g^a mod p, which was sent.
Mechanism for verifying public keys
- best way: person-to-person verification, if people know each other
- if don't recognize person, can't trust key
- can use a referral from someone you do know (digital certificate)
- dig. cert: "Alice's public key is _____, signed Diane"
- sufficient if: know Diane's public key and trust Diane
- don't get something for nothing
Centralized
- one organization vouches for everyone's keys (bring papers, go in person, get certificate)
- need excellent security; if root key compromised, than can create forged certificate for anyone
- use government (DMV)
- one certificate replaces each plastic ID card
Web of trust (decentralized)
- many certificates... big bag of certificates
- people emerge as "commonly used" certificates
PKI always "just around the corner"
- mystery: why hasn't it taken off?
- Reasons
- doing PKI right is expensive
- economics: what type of background check can you do for $20?
Revocation
- how to revoke invalid keys/certificates that are no longer true?
- use revocation list; need way to remove compromised keys
