Cryptography Basics – Key exchange
Review
Integrity: prevent Mallory from tampering
v’ == MACk(m’) k
Bob
k
Bob
p := Dk(c)
◦ Message Authentication Code
◦ Hashes -> HMAC
◦ Use: SHA2, SHA3
k
m, v:= MAC (m) k
m’, v’
Confidentiality: prevent eavesdropper (Eve) from learning the (plaintext) message
◦ Streamciphers
◦ AES-CTR, ChaCha20
◦ Block ciphers
◦ AES-CBC (caution: padding oracles!)
k
c := E (p) k
Eve
Alice
Mallory
Best practice: Authenticated ciphers (e.g. AES-GCM) ◦ Encrypt,thenMAC
?
Sharing k Amazing fact:
Alice and Bob can have a public conversation to derive a shared key!
Diffie-Hellman (D-H) key exchange
1976: Whit Diffie, Marty Hellman
with ideas from Ralph Merkle
(earlier, in secret, by Malcolm Williamson of British intelligence agency)
Relies on a mathematical hardness assumption called discrete log problem (a problem believed to be hard)
3.
Computes x
= (gb mod p)a mod p =gba modp
Computes x′
= (ga mod p)b mod p =gab modp
Diffie-Hellman protocol
D-H protocol
1. 2.
Alice and Bob agree on public parameters (maybe in standards doc*, or pick them) p: a large “safe prime” s.t. (p-1)/2 is also prime
g: a square mod p (but not 1)
Alice
Generates random secret value a.
a
b
Bob
Generates random secret value b.
(0 < b < p)
(0 < a < p)
gb mod p
ga mod p
(Notice that x == x′)
Can use k := HMAC0(x) as a shared key.
DH passive eavesdropping attack
a
b
ga mod p
Eve wants to compute x = gab mod p Best known approach:
ga mod p
Find a or b, then compute x
Finding y given gy mod p is an instance of the discrete log problem:
gb mod p Best practice: Use large DH group size (e.g. 2048-bit primes)
or a more secure group (Elliptic curve cryptography)
[Breakout exercise: what about Mallory (active attacks)?]
No known efficient algorithm*
gb mod p
Man-in-the-middle (MITM) attack
a' b'
b
a
Alice does D-H exchange,
really with Mallory
Bob does D-H exchange,
ga modp gb' mod p
ga' modp gb mod p
kBob = ga’b mod p
really with Mallory
kAlice = gab’ mod p Alice and Bob each think they are talking with the other,
but really Mallory is between them and knows both secrets
Bottom line:
D-H gives you secure connection, but you don’t know who’s on the other end!
Defending D-H against MITM attacks
◦ Cross your fingers and hope there isn’t an active adversary.
◦ Rely on out-of-band communication between users. [Examples?]
◦ Rely on physical contact to make sure there’s no MITM. [Examples?] ◦ Integrate D-H with user authentication.
If Alice is using a password to log in to Bob, leverage the password:
Instead of a fixed g, derive g from the password – Mallory can’t participate w/o knowing password.
◦ Use digital signatures. [More next week.]
Public key encryption
Can Alice share a “public key” (ga mod p) and have anyone encrypt a message only she can read?
Public key encryption
Can Alice share a “public key” (ga mod p) and have anyone encrypt a message only she can read? Diffie-Hellman doesn’t allow this directly, but with some math:
Alice’s public key is A= ga mod p and her private key is a
Bob has Alice’s public key, and a message m he wants to send her:
◦ Pick a random value r [0,p-2]
◦ Compute R= gr mod p
◦ ComputeS=m*Armodp
◦ Send Alice (R,S)
To decrypt:
◦ Alice computes S*R-a mod p = m*Ar *gr(-a) mod p = m*gargr(-a) mod p = m*gar-ar mod p = m*g0 mod p = m