• 10.3 - Diffie Hellman Key Exchange

How can the parties share a secret key in the first place?

Merkles Puzzle

To summarise there are at least three distinct problems related to the use of private key encryption:

1. key distribution
2. storing and maintaining large number of secret keys
3. inapplicability of private key cryptography to open systems

Partial Solution: KDC-Key Distribution Centre

One way to address some of the concerns from the previous section is to use a key-distribution centre to establish shared keys.

One approach is to utilise the KDC in an online fashion to generate keys “on demand” whenever two parties wish to communicate securely.

Say the KDS shares key $key_A$ with Alice, and $key_B$ with Bob. At some late time when Alice wishes to communicate securely with Bob, she can simply ask the KDC.

The KDC then chooses a new random key called a session key and sends this key to Alice encrypted using $key_A$ and to Bob encrypted using $key_B$.

Advantages of this approach include:

1. Each party now stores only one long-term secret key. KDC has to store many long term keys. However, the KDC can be kept in a secure location and be given the highest possible protection against network attacks.
2. When a new party joins the communication, a key has to be setup between the joining party and the KDC. No other party has to update their keys.

KDCs can alleviate two of the problems we discussed before.

1. Simplify key distribution
2. reduce the complexity of key management

However, there are some drawbacks,

1. Successful attack on the KDC will result in a complete break of the system. makes KDC a high valued target.
2. KDC is a single point of failure. If KDC is down the entire communication is down. - Can be handled by replicating the KDC service. but complicates key distribution and increases the attack surface.

Protocols for key distribution using KDC:

1. Needham-Schroeder Protocol

Key Exchange: Diffie-Hellman Protocol

KDCs and protocols like Kerberos are commonly used in practice. But these approaches still require a secure communication channel that can be used to share private keys. So these approaches still do not solve the problem of key distribution in open systems like the Internet.

Setting and definition of security:

Setting:

• We consider a setting with two parties say Alice and Bob who run a probabilistic protocol $\Pi$ in order to generate a shared, secret key; $\Pi$ can be viewed as set of instructions for generating keys
• At the end of the protocol, Alice and Bob output keys $k_A, k_B \in \{0, 1\}^n$
• The basic correctness requirement is that $k_A = k_B$

Security:

• A key exchange protocol is secure if the key output by Alice and Bob is completely unguessable by an eavesdropper adversary.
• This is formally defined by requiring that an adversary who has eavesdropped on an execution of the protocol should be unable to distinguish the key $k$ generated by the execution form a uniform key of length $n$

Diffie-Hellman Key Exchange

Background:

• Set of invertible elements:

  $$\mathbb{Z}_n^* = \{x \in \mathbb{Z_n} \mid gcd(x, N)=1\}$$

• The set $\mathbb{Z}_p^*$ is a cyclic group

• $\exists g \in Z_p^*$ such that $\{g^1, g^2 \cdots, g^{p-1}\} = Z_p^*$

• $g$ is called as a generator of the cyclic group.

• Discrete Logarithm:

  • Fix a prime $p \gt 2$ and a generator $g \in \mathbb{Z_p^*}$
  • Consider $f(x) = g^{x}\mod{p}$
  • Then the inverse of the above function is the discrete logarithm problem and is intractable for large n-bit primes.

• The intractability of the Discrete logarithm is used as a basis for diffie-hellman key exchange.

Construction:

• Common Input: Parties agree on a public generator $g$ and prime $p$
• Protocol:
• Alice chooses a uniform $x \in \mathbb{Z_p}$ and computes $h_A = g^x$ and sends to Bob
• Bob chooses a uniform $y \in \mathbb{Z_p}$ and computes $h_B = g^y$ and sends to Bob.
• Alice receives $h_B$ and computes $k = h_B^x$
• Bob receives $h_A$ and computes $k = h_A^y$

The protocol is correct as

Discussion:

The Diffie-Hellman protocol in its basic form is typically not used in practice due to its insecurity against MITM attack.