13. Key Establishment

Distribution of cryptographic keys to protect subsequent sessions. In TLS, public keys allow clients/servers to share a new communication key.

Kerberos: key establishment without public keys.

Key Management

Key management has four phases:

Key generation: keys should be generated such that they are all equally likely to occur
Key distribution: keys should be distributed in a secure fashion
Key protection: keys should be accessible only to authorized parties
Key destruction: once a key has performed its function, it should be destroyed such that it (TODO the encrypted data?) has value to an attacker

Hierarchy

Keys often organized into a hierarchy. In a two-level hierarchy, there are long- and short-term keys:

Long-term/static keys are used to protect the distribution of session keys. They may last anywhere from a few hours to a few years, depending on the application
Short-term/session/ephemeral keys are used to protect communications in a session. They may last anywhere from a few seconds to a few hours, depending on the application

Key Establishment

Symmetric keys with ciphers (e.g. AES, MAC) are used in practice for session keys as as they are more efficient than public key algorithms.

Long-term keys can be symmetric or asymmetric.

Key Distribution Security Goals

Authentication: they should be able to authenticate that the receiver is the party they intended to send the key to.

Confidentiality: no adversary can obtain the session key accepted by a particular party.

In formal models, the protocol is broken if the adversary can distinguish the session key from a random string.

Mutual and Unilateral Authentication

Mutual authentication: both parties achieve the authentication goal.

Unilateral authentication: only one party achieves the authentication goal. This is done by most real-world key establishment protocols: typically clients authenticate the server with client authentication happening later.

Adversary Capabilities

A strong adversary knows the details of the cryptographic algorithms and can:

Eavesdrop on all messages
Alter messages sent
Re-route messages to any other party
Obtain the session key used in any previous run

Distribution of Pre-Shared Keys

A trusted authority (TA) generates and distributes long-term keys to all users when they join the system. Their involvement ends here in the pre-distribution phase so if there are no new users they can go offline.

A simple scheme is to assign a secret key for each pair of users, but this will not scale well as the number of keys grows quadratically.

Probabilistic schemes reduce key material at each party by forwarding messages to other parties that hopefully have a link to the final receiver. Hence, it offers only a high probability of a secure channel between any two parties and requires other nodes to be trusted as they must decrypt and re-encrypt the message. This is suitable for sensor networks.

Key Distribution using Symmetric Keys

Key distribution with online server.

A TA shares a long-term shared key with each user. They distribute session keys to users when requested and hence, the TA is highly trusted and is a single point of attack. Scalability may also be a problem.

Needham-Schroeder Protocol

Widely-known key establishment protocol published 1978. Found vulnerable to replay attacks in 1981 - attacker can replay old messages that a honest party will accept an old session key.

Notation:

Two parties, $A$ and $B$
TA $S$
$A$ and $S$ share a long-term key $K_{AS}$
$B$ and $S$ share a long-term key $K_{AS}$
New session key $K_{AB}$ generated by $S$
Nonce $N_A$ , $N_B$ randomly generated by $A$ and $B$ respectively for one-time use
$A \to B: M$ : $A$ sends message $M$ to $B$
$\{M\}_K$ : message $M$ encrypted using key $K$ . There is assumed to be some authentication mechanism

Protocol:

\begin{aligned} \text{1.}\>& A \to S: \mathrm{ID}_A, \mathrm{ID}_B, N_A \\ \text{2.}\>& S \to A: \left\{ K_{AB}, \mathrm{ID}_A, \mathrm{ID}_B, N_A, \left\{ K_{AB}, \mathrm{ID}_A, \mathrm{ID}_B \right\}_{K_{BS}} \right\}_{K_{AS}} \\ \text{3.}\>& A \to B: \left\{ K_{AB}, \mathrm{ID}_A, \mathrm{ID}_B \right\}_{K_{BS}}, \mathrm{ID}_A \\ \text{4.}\>& B \to A: \{ N_B \}_{K_{AB}} \\ \text{5.}\>& A \to B: \{ N_B - 1 \}_{K_{AB}} \end{aligned}

Replay Attacks

If an attacker $C$ gets a previous session key $K'_{AB}$ , they can masquarade as $A$ and persuade $B$ to use the old key (steps 3-5).

To defend against this, the established key must be fresh for each session:

Random challenges (nonces)
Timestamps
Counters

The repaired protocol uses random challenges. After $A$ establishes request for connection with $B$ :

\begin{aligned} \text{1.}\>& B \to A: \mathrm{ID}_B, N_B \\ \text{2.}\>& A \to S: \mathrm{ID}_A, \mathrm{ID}_B, N_A, N_B \\ \text{3.}\>& S \to A: \left\{ K_{AB}, \mathrm{ID}_A, \mathrm{ID}_B, N_A \right\}_{K_{AS}}, \left\{ K_{AB}, \mathrm{ID}_A, \mathrm{ID}_B, N_B \right\}_{K_{BS}} \\ \text{4.}\>& A \to B: \left\{ K_{AB}, \mathrm{ID}_A, \mathrm{ID}_B, N_B \right\}_{K_{BS}} \end{aligned}

Tickets can also be used: if $A$ wishes to communicate with $B$ , $S$ generates ticket $\left\{ K_{AB}, \mathrm{ID}_A, \mathrm{ID}_B, T_B \right\}_{K_{BS}}$ where $T_B$ is a validity period - $A$ can use the ticket for this duration.

\begin{aligned} \text{1.}\>& A \to S: \mathrm{ID}_A, \mathrm{ID}_B, N_A \\ \text{2.}\>& S \to A: \left\{ K_{AB}, \mathrm{ID}_A, \mathrm{ID}_B, N_A \right\}_{K_{AS}}, \text{ticket} \\ \text{3.}\>& A \to B: \text{ticket} \end{aligned}

Kerberos

Now on V5, released 1995. Standardized as RFC 4120. Used in Windows as the default domain authentication method.

Kerberos allows:

Secure network authentication service in an insecure network
Single sign-on: users only need to enter their username/password once per session
Access to different online services using individual tickets
Session keys to be established in an authenticated and confidential fashion

It is a 3-level protocol:

Level 1

Client $C$ interacts with authentication server $AS$ to obtain a ticket-granting ticket at the start of a session.

\begin{aligned} \text{1.}\> C \to AS&: \mathrm{ID}_C, \mathrm{ID}_{TGS}, N_1 \\ \text{2.}\> AS \to C&: \left\{ K_{C, TGS}, \mathrm{ID}_{TGS}, N_1 \right\}_{K_{C}}, \text{ticket}_{TGS} \end{aligned}

Where:

$K_C$ is the symmetric key shared between $AS$ and $C$ , usually generated on login from $C$
$K_{C, TGS}$ is the symmetric key generated by $AS$
$N_1$ is the nonce generated by $C$ to ensure $K_{C, TGS}$ is fresh
$K_{TGS}$ is the long-term key shared between $AS$ and $TGS$
$\text{ticket}_{TGS} = \{ K_{C, TGS}, \mathrm{ID}_C, T_1 \}_{K_{TGS}}$ is valid for some validity period $T_1$ .

At the end of this exchange, $C$ has a ticket-granting ticket that can be used to obtain different service-granting tickets from the ticket-granting server.

Level 2

Client $C$ interacts with ticket granting server $TGS$ :

\begin{aligned} \text{1.}\> C \to TGS&: \mathrm{ID}_V, N_2, \text{ticket}_{TGS}, \text{authenticator}_{TGS} \\ \text{2.}\> TGS \to C &: \mathrm{ID}_C, \text{ticket}_V, \{ K_{C, V}, N_2, \mathrm{ID}_V \}_{K_{C, TGS}} \end{aligned}

Where:

$K_{C, V}$ is a session key shared between $V$ and $C$
$K_V$ is a long-term key shared between $V$ and $TGS$
$N_2$ is a nonce
$\text{ticket}_V = \left\{ K_{C, V}, \mathrm{ID}_C, T_2 \right\}_{K_V}$ is a ticket for service $V$ with validity period $T_2$
$\text{authenticator}_{TGS} = \left\{ \mathrm{ID}_C, TS_1 \right\}_{K_{C, TGS}}$ where $TS_1$ is a timestamp
- The ticket-granting server must check that the timestamp is valid

The ticket-granting server must also check that the client has permission to access the service $V$ .

In practice, the AS and TGS are the same machine.

Level 3

Client $C$ interacts with application server $V$ :

\begin{aligned} \text{1.}\> C \to V&: \text{ticket}_V, \text{authenticator}_V \\ \text{2.}\> V \to C&: \left\{ TS_2 \right\}_{K_{C, V}} \end{aligned}

Where:

$\text{authenticator}_V = \left\{ \textrm{ID}_C, TS_2 \right\}_{K_{C, V}}$

The reply from $V$ is intended to provide mutual authentication, allowing $C$ to verify they are talking to the right $V$ .

Limitations

Realms (domains over which an authentication server has authority to authenticate a user) must share keys with every other realm, so although multiple realms are supported it has limited scalability.

$K_{C}$ is derived from the user’s password, so offline password guessing is possible.

Key Distribution using Asymmetric Cryptography

No online TA is required. Instead, public keys (managed by PKI - certificates and CAs) is used for authentication. Users are trusted to generate good session keys (so hopefully each party has a good PRNG).

Key transport: user chooses key material and sends it to another party (encrypted, possibly signed). Does NOT provide forward secrecy.

Key agreement: Diffie-Hellman or some other protocol where both parties provide input to the key. The messages are signed, providing authentication. Provides forwards secrecy.

TLS supports both key transport and agreement.

Forward Secrecy

If a long-term key is compromised, the attacker can now claim to be the owner of the key. If key transport is used, all previous session keys will be compromised.

A protocol provides (perfect) forwards secrecy if compromise of the long-term secret keys do not reveal session keys previously agreed using the long-term keys.

Signed Diffie-Hellman

Computations done in $\mathbb{Z}_p^*$ . Notation:

Generator $g$
Random values $a$ and $b$ chosen by each party where $1 \le a, b \le p - 1$
$\mathrm{Sign}_A(m)$ is a signature on message $m$ from $A$ signed with their signing/long-term key
$\mathrm{Sign}_B(m)$ is a signature on message $m$ from $B$ signed with their signing/long-term key
$\mathrm{ID}_A$ and $\mathrm{ID}_B$ are $A$ and $B$ ’s identities respectively
Both parties know each other’s public verification key
Long-term signing keys provide only authentication, hence it has perfect forward secrecy

Protocol:

$A$ sends $\mathrm{ID}_A$ , $g^a$
$B$ sends $\mathrm{ID}_B$ , $g^b$ and $\mathrm{Sign}_B(\mathrm{ID}_A \| \mathrm{ID}_A \| g^b || g^a)$
- $A$ checks signature. If valid, computes session key $K_{AB} = (g^b)^a = g^{ab}$
A sends $\mathrm{Sign}_B(\mathrm{ID}_A \| \mathrm{ID}_B \| g^a || g^b)$
- $B$ checks signature. If valid, computes session key $K_{AB} = (g^a)^b = g^{ab}$