Key Establishment

Introductions

Important question — how do Bob and Alice create a key that they share?
They could share the key in person, e.g. using a USB drive.
Alice could generate a key and then encrypt it with Bob’s public key
- If someone records the conversation and then steals Bob’s private key, they can decrypt everything
- If you do have a shared key, it is important to prove ownership
  - encrypt a random number
  - encrypt a sequence number
  - encrypt a timestamp
- All of these prevent a replay attack
Key agreement protocol — both parties contribute some information to derive a shared key
- the generated key is ephemeral — used only for a short time, destroyed after use
- no long term secrets — so even if an attacker steals Bob’s private key and has a record of the conversation, they can’t compute the derived key

“allows two parties with no prior contact nor any pre-shared keying material, to establish a shared secret by exchanging numbers over a channel readable by everyone else.” Pretty amazing!
Diffie-Hellman protocol
- g and p are fixed and known for all users
  - p is prime
  - g is a primitive root modulo p
  - for every integer a in g that is coprime to p, there is some integer k for which g^k ≡ a (mod p)
  - g is a generator of the multiplicative group of integers modulo p
- A : chooses a private value, a in the range [1, p - 2]
- A → B : g^a mod p
- B : chooses a private value b in the range [1, p - 2], computes K = (g^a)^b mod p
- B → A : g^b mod p
- A: computes K = (g^b)^a mod p
- depends on g^ab = g^ba

Computing a from g^a and public parameters g and p is called the discrete logarithm problem — computationally difficult if p is chosen with certain properties
Once you derive DH key K, you put it into a key derivation function to get the actual key used.
Textbook DH is unauthenticated — an active attacker can easily subvert it.

The STS protocol, discussed in the book, adds digital signatures to DH. We will later see DH in TLS.

forward secrecy — disclosure of a long-term secret does not compromise the secrecy of session keys used for earlier sessions
known-key security — compromised session keys do not allow later impersonation or compromise future session keys
entity authentication and liveness — if you verify an entity is actively participating in a protocol, this gives you liveness
key-use confirmation — you can verify a party has a session key without verifying who they are
implicit authentication — encrypting a session key using RSA — you know the other party is the only one that can get the session key, but you don’t know if they have received it
implicit authentication + key-use confirmation = explicit authentication
if you want to see details, study the STS implementation details, then read through the informal explanation of the properties provided