Key Establishment mini notes

13.1 Introduction

13.1.1 Some Terminology

• Key Establishment: Process of creating a shared secret between parties.
• Key Transport: One party creates a secret and securely sends it to others.
• Key Agreement: All parties contribute to deriving a shared secret. No single party determines the key. (e.g., Diffie-Hellman)

13.1.2 Key Freshness and Key Derivation

• Session Key / Ephemeral Key ($k_{ses}$): Key used for a limited time (e.g., one session).

  • Advantage: Limits damage if key is compromised; less ciphertext per key aids security.

• Key Derivation Function (KDF): Derives session keys ($k_{ses}$) from a long-term shared secret ($K_{AB}$) and often a non-secret parameter ($r$).

  • Goal: Efficiently generate fresh keys without costly re-establishment.
  • Property: Should be a one-way function (hard to find $K_{AB}$ from $k_{ses}$).

  k_{ses} = KDF(K_{AB}, r)

KDF Examples (Alice and Bob share $K_{AB}$)

1. Nonce-based: One party (e.g., Bob) generates a nonce ($r$, number used once) and sends it. Both compute $k_{ses}$.

   • Formula (using encryption): $$k_{ses}=e_{K_{AB}}(r)$$
   • Example:
     1. Bob generates random nonce $r=12345$.
     2. Bob sends $r$ to Alice.
     3. Alice computes $k_{ses}=AE{S}_{K_{AB}}(12345)$.
     4. Bob computes $k_{ses}=AE{S}_{K_{AB}}(12345)$.

2. Counter-based: Use a synchronized counter ($cnt$).

   • Formula (using encryption): $$k_{ses}=e_{K_{AB}}(cnt)$$
   • Example (assuming $cnt=1$ for the first session key):
     1. Alice computes $k_{ses,1}=AE{S}_{K_{AB}}(1)$.
     2. Bob computes $k_{ses,1}=AE{S}_{K_{AB}}(1)$.
     3. For next key, both increment $cnt$ to 2 and compute $k_{ses,2}=AE{S}_{K_{AB}}(2)$.
   • Advantage: No value needs to be transmitted if perfectly synchronized.

3. HMAC-based: Use HMAC with nonce or counter.

   • Formula (using nonce $r$): $$k_{ses}=HMA{C}_{K_{AB}}(r)$$
   • Example (using $r=12345$):
     1. Bob generates $r=12345$.
     2. Bob sends $r$ to Alice.
     3. Alice computes $k_{ses}=HMAC-SHA256_{K_{AB}}(12345)$.
     4. Bob computes $k_{ses}=HMAC-SHA256_{K_{AB}}(12345)$.

13.1.3 The $n^2$ Key Distribution Problem (Symmetric Keys)

• Problem with pre-distributing unique symmetric keys between all pairs of $n$ users.
• Each user stores: $n-1$ keys.
• Total symmetric key pairs needed: $$N=\frac{n(n-1)}{2}=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$$
• Total keys distributed/stored across system: $n(n-1)\approx n^2$.
• Adding a new user requires establishing $n$ new secure channels to distribute keys to all existing users.
• Example ($n=4$ users: A, B, C, D):
  • Keys needed: $K_{AB},K_{AC},K_{AD},K_{BC},K_{BD},K_{CD}$.
  • Total pairs: $N=\frac{4(4-1)}{2}=\frac{12}{2}=6$.
  • Alice stores: $K_{AB},K_{AC},K_{AD}$ (3 keys = $n-1$).
• Example ($n=750$ users):
  • Total pairs: $N=\frac{750(749)}{2}=280,875$. Scalability issue.

13.2 Key Establishment Using Symmetric-Key Techniques

Relies on a trusted third party: Key Distribution Center (KDC).

13.2.1 Key Establishment with a KDC

• Prerequisite: Each user $U$ shares a unique long-term Key Encryption Key (KEK) $k_U$ with the KDC (e.g., $k_A$ for Alice, $k_B$ for Bob). KEKs distributed via secure channel initially.
• Goal: KDC generates a short-term session key ($k_{ses}$) for Alice and Bob and distributes it securely using KEKs.

Basic Protocol (Conceptual)

1. Alice requests session key for Bob from KDC: $RQST(I{D}_A,I{D}_B)$.
2. KDC generates random $k_{ses}$.
3. KDC encrypts $k_{ses}$ for Alice and Bob using their respective KEKs:
   • $y_A=e_{k_A}(k_{ses})$
   • $y_B=e_{k_B}(k_{ses})$
4. KDC sends $y_A$ to Alice, $y_B$ to Bob (conceptually, via separate secure channels formed by KEKs).
5. Alice decrypts: $k_{ses}=d_{k_A}(y_A)$.
6. Bob decrypts: $k_{ses}=d_{k_B}(y_B)$.

Modified Protocol (More Practical)

1. Alice $\to$ KDC: $RQST(I{D}_A,I{D}_B)$.
2. KDC generates $k_{ses}$. Computes $y_A=e_{k_A}(k_{ses})$ and $y_B=e_{k_B}(k_{ses})$.
3. KDC $\to$ Alice: $y_A,y_B$. (Sends Bob’s encrypted key to Alice).
4. Alice decrypts $k_{ses}=d_{k_A}(y_A)$.
5. Alice $\to$ Bob: $y_B$, $y=e_{k_{ses}}(x)$ (Sends Bob his encrypted key plus the first message encrypted with $k_{ses}$).
6. Bob decrypts $k_{ses}=d_{k_B}(y_B)$.
7. Bob decrypts message $x=d_{k_{ses}}(y)$.

• Advantage over $n^2$: Only $n$ KEKs needed ($k_A,k_B,...$).

Security Issues

• Replay Attack: Attacker (Oscar) records old $y_A,y_B$ (or just $y_B$ in modified protocol) and replays them later. Alice/Bob might unknowingly reuse a compromised old $k_{ses}$. Needs mechanism for freshness (timestamps, nonces).
• Key Confirmation Attack (on basic/modified protocols): Alice doesn’t know if Bob actually received $k_{ses}$. Oscar (malicious user with KEK $k_O$) can trick Alice into using a key shared with him instead of Bob.
  1. Alice $\to$ KDC: $RQST(I{D}_A,I{D}_B)$.
  2. Oscar intercepts, changes request to KDC: $RQST(I{D}_A,I{D}_O)$.
  3. KDC $\to$ Oscar (intended for Alice): $y_A=e_{k_A}(k_{ses})$, $y_O=e_{k_O}(k_{ses})$.
  4. Oscar intercepts, decrypts $k_{ses}=d_{k_O}(y_O)$. Forwards $y_A$ to Alice (maybe along with $y_O$ disguised as $y_B$).
  5. Alice decrypts $k_{ses}=d_{k_A}(y_A)$, believes she shares it with Bob.
  6. Alice $\to$ Oscar (thinking it’s Bob): $y=e_{k_{ses}}(x)$.
  7. Oscar decrypts $x=d_{k_{ses}}(y)$.

13.2.2 Kerberos (Simplified)

• Solves Replay and Key Confirmation issues. Uses KDC (called Authentication Server).
• Includes mechanisms for Timeliness and Key Confirmation.

Protocol Steps (Simplified)

1. Alice $\to$ KDC: $RQST(I{D}_A,I{D}_B,r_A)$ (Includes a nonce $r_A$).
2. KDC generates $k_{ses}$, Lifetime $T$. Creates:
   • $y_A=e_{k_A}(k_{ses},r_A,T,I{D}_B)$ (Ticket for Alice: includes $k_{ses}$, verified nonce $r_A$, lifetime $T$, Bob’s ID $I{D}_B$).
   • $y_B=e_{k_B}(k_{ses},I{D}_A,T)$ (Ticket for Bob: includes $k_{ses}$, Alice’s ID $I{D}_A$, lifetime $T$).
3. KDC $\to$ Alice: $y_A,y_B$.
4. Alice decrypts $y_A$ with $k_A$.
   • Verifies $r_A$ (confirms KDC response is fresh and for her request).
   • Verifies $I{D}_B$ (confirms key is intended for Bob).
   • Extracts $k_{ses}$ and $T$.
5. Alice generates Timestamp $T_S$. Creates Authenticator:
   • $y_{AB}=e_{k_{ses}}(I{D}_A,T_S)$.
6. Alice $\to$ Bob: $y_B$, $y_{AB}$ (Ticket for Bob + Authenticator).
7. Bob decrypts $y_B$ with $k_B$.
   • Verifies $I{D}_A$ (confirms key is for session with Alice).
   • Extracts $k_{ses}$ and $T$.
8. Bob decrypts $y_{AB}$ with $k_{ses}$.
   • Verifies $I{D}_A$ (confirms authenticator is from Alice).
   • Verifies $T_S$ (checks if timestamp is recent, prevents replay of $y_{AB}$).

Security Features

• Timeliness: Lifetime $T$ limits key validity. Timestamp $T_S$ ensures freshness of Alice’s contact with Bob. Requires loosely synchronized clocks.
• Key Confirmation:
  • Alice confirms KDC via $r_A$. Confirms key is for Bob via $I{D}_B$ in $y_A$.
  • Bob confirms key is for Alice via $I{D}_A$ in $y_B$. Confirms current message is from Alice via $I{D}_A$ in $y_{AB}$ (authenticator).

13.2.3 Remaining Problems with Symmetric-Key Distribution (KDC/Kerberos)

• Communication Requirements: KDC must be online and contacted for new sessions.
• Secure Channel for Initialization: Initial KEK distribution requires a secure channel.
• Single Point of Failure: KDC database compromise reveals all KEKs. System unusable.
• No Perfect Forward Secrecy (PFS):
  • Definition 13.1 (PFS): Compromise of long-term keys (KEKs) does not compromise past session keys ($k_{ses}$).
  • KDC/Kerberos lack PFS. If KEK $k_A$ is compromised, attacker can decrypt past session keys by decrypting stored $y_A$ messages.

13.3 Key Establishment Using Asymmetric Techniques

• Can provide Key Transport (e.g., RSA/Elgamal encryption) or Key Agreement (e.g., DHKE).
• Doesn’t require secure channel for key distribution, but requires authenticated channel.

13.3.1 Man-in-the-Middle (MIM) Attack

• Major threat to asymmetric schemes if public keys are not authenticated.
• Attacker (Oscar) sits between Alice and Bob, intercepts and replaces public keys with his own.

Attack on Diffie-Hellman Key Exchange (DHKE)

• Normal DHKE:

  • Public parameters: prime $p$, generator $\alpha$.
  • Alice: chooses private $a$, computes public $A={\alpha }^a(\mathrm{mod}p)$.
  • Bob: chooses private $b$, computes public $B={\alpha }^b(\mathrm{mod}p)$.
  • Alice sends $A$ to Bob. Bob sends $B$ to Alice.
  • Alice computes $K_{AB}=B^a=({\alpha }^b{)}^a={\alpha }^{ab}(\mathrm{mod}p)$.
  • Bob computes $K_{AB}=A^b=({\alpha }^a{)}^b={\alpha }^{ab}(\mathrm{mod}p)$.

• MIM Attack Steps:

  1. Alice $\to$ (Oscar intercepts): $A={\alpha }^a(\mathrm{mod}p)$.
  2. Oscar $\to$ Bob: $\tilde{A}={\alpha }^o(\mathrm{mod}p)$ (Oscar’s public key, pretending it’s Alice’s). Oscar chose private $o$.
  3. Bob $\to$ (Oscar intercepts): $B={\alpha }^b(\mathrm{mod}p)$.
  4. Oscar $\to$ Alice: $\tilde{B}={\alpha }^o(\mathrm{mod}p)$ (Oscar’s public key, pretending it’s Bob’s).

• Keys Established:

  • Alice computes (thinks it’s with Bob): $$K_{AO}=(\tilde{B}{)}^a=({\alpha }^o{)}^a={\alpha }^{oa}(\mathrm{mod}p)$$
  • Bob computes (thinks it’s with Alice): $$K_{BO}=(\tilde{A}{)}^b=({\alpha }^o{)}^b={\alpha }^{ob}(\mathrm{mod}p)$$
  • Oscar computes (with Alice): $$K_{AO}=A^o=({\alpha }^a{)}^o={\alpha }^{ao}(\mathrm{mod}p)$$
  • Oscar computes (with Bob): $$K_{BO}=B^o=({\alpha }^b{)}^o={\alpha }^{bo}(\mathrm{mod}p)$$

• Result: Alice shares $K_{AO}$ with Oscar. Bob shares $K_{BO}$ with Oscar. Alice and Bob think they share $K_{AB}$. Oscar can decrypt, read, modify, and re-encrypt all traffic.

13.3.2 Certificates

• Solution to MIM: Authenticate public keys. Bind an identity ($I{D}_A$) to a public key ($k_{pub,A}$).
• Mechanism: Digital Signature by a trusted Certification Authority (CA).
• Certificate Structure (Basic): $$Cer{t}_A=[\underset{\text{data}}{\underbrace{(k_{pub,A},I{D}_A)}},\underset{\text{CA’s signature on data}}{\underbrace{si{g}_{k_{pr,CA}}(k_{pub,A},I{D}_A)}}]$$
  • $k_{pr,CA}$ is the CA’s private signing key.
• Verification: Anyone knowing the CA’s public verification key ($k_{pub,CA}$) can verify the signature. If valid, they trust that $k_{pub,A}$ belongs to $I{D}_A$.
• Requires: Receiver must have the authentic public key of the CA ($k_{pub,CA}$).

Certificate Generation

• User-Provided Keys: Alice generates $(k_{pub,A},k_{pr,A})$. Sends $k_{pub,A},I{D}_A$ to CA via authenticated channel. CA verifies Alice’s identity, signs, returns $Cer{t}_A$.
• CA-Generated Keys: Alice requests certificate for $I{D}_A$ via authenticated channel. CA verifies identity, generates $(k_{pub,A},k_{pr,A})$, signs $k_{pub,A}$, returns $Cer{t}_A$ and $k_{pr,A}$ via authenticated and secure channel.

DHKE with Certificates

1. Alice sends $A={\alpha }^a(\mathrm{mod}p)$ and $Cer{t}_A$ (containing $A$ or signed $A$).
2. Bob sends $B={\alpha }^b(\mathrm{mod}p)$ and $Cer{t}_B$ (containing $B$ or signed $B$).
3. Alice verifies $Cer{t}_B$ using $k_{pub,CA}$. If valid, computes $K_{AB}=B^a(\mathrm{mod}p)$.
4. Bob verifies $Cer{t}_A$ using $k_{pub,CA}$. If valid, computes $K_{AB}=A^b(\mathrm{mod}p)$.

• MIM prevented: Oscar cannot fake $Cer{t}_A$ or $Cer{t}_B$ without $k_{pr,CA}$. If Oscar replaces $A$ with $\tilde{A}$ and $Cer{t}_A$ with $Cer{t}_O$, Bob’s verification of $Cer{t}_O$ would show the identity $I{D}_O$, not $I{D}_A$.

Trust

• Transfer of Trust: Users trust the CA’s public key ($k_{pub,CA}$). By verifying certificates, they extend trust to the public keys within those certificates.
• Authenticated Channel needed only once: For initially obtaining the trusted $k_{pub,CA}$. Often pre-installed in software (browsers, OS).
• Chain of Trust: If CA1 signs CA2’s public key, and Alice trusts CA1, she can verify CA2’s certificate, obtain trusted $k_{pub,CA2}$, and then verify certificates issued by CA2.

13.3.3 Public-Key Infrastructures (PKI) and CAs

• PKI: The entire system of hardware, software, policies, CAs, certificates to manage public keys.
• Complex issues: CA hierarchies, certificate revocation, policy.

X.509 Certificates

• A standard format for public key certificates (used in TLS/SSL, S/MIME, etc.).
• Key Fields:
  • Version
  • Serial Number (unique from issuer)
  • Signature Algorithm ID (e.g., sha256WithRSAEncryption)
  • Issuer (CA’s distinguished name)
  • Validity Period (Not Before, Not After dates)
  • Subject (Owner’s distinguished name - $I{D}_A$)
  • Subject Public Key Info (Algorithm ID, Parameters, The key $k_{pub,A}$)
  • Issuer Unique ID (optional)
  • Subject Unique ID (optional)
  • Extensions (optional, e.g., key usage constraints)
  • CA’s Signature on all above fields.

Chain of Certificate Authorities (CAs)

• Reality: Multiple CAs exist. Users may not directly trust the CA that issued a specific certificate.
• CAs can issue certificates for other CAs (cross-certification or hierarchical).
• Example: Alice trusts Root CA. Root CA certifies Intermediate CA1. Intermediate CA1 certifies Bob’s Leaf CA. Bob’s Leaf CA certifies Bob’s certificate $Cer{t}_B$. Alice verifies the chain: Root $\to$ CA1 $\to$ Leaf CA $\to$ Bob.