Diffie-Hellman Key Exchange

The first published public-key algorithm appeared in the seminal paper by Diffie and Hellman that defined public-key cryptography and is generally referred to as Diffie-Hellman key exchange.A number of commercial products employ this key exchange technique.

 

The purpose of the algorithm is to enable two users to securely exchange a key that can then be used for subsequent encryption of messages. The algorithm itself is limited to the exchange of secret values.
 

The Diffie-Hellman algorithm depends for its effectiveness on the difficulty of computing discrete logarithms. Briefly, we can define the discrete logarithm in the following way. The primitive root of a prime number $p$ as one whose powers modulo $p$ generate all the integers from 1 to p$ - 1$. That is, if $a$ is a primitive root of the prime number $p$, then the numbers $$a \pmod p, a^2 \pmod p, \ldots, a^{p - 1} \pmod p$$ are distinct and consist of the integers from 1 through $p - 1$ in some permutation.

For any integer $b$ and a primitive root a of prime number $p$, we can find a unique exponent $i$ such that

$$b \equiv a^i \pmod p, \quad \quad where \quad 0 \le i \le (p - 1)$$

The exponent $i$ is referred to as the discrete logarithm of $b$ for the base $a$, mod $p$. We express this value as $dlog_{a,p}(b)$

The Algorithm
Figure below  summarizes the Diffie-Hellman key exchange algorithm. For thisscheme, there are two publicly known numbers: a prime number $q$ and an integer $α$ that is a primitive root of $q$. 

 

Suppose the users A and B wish to exchange a key. User $A$ selects a random integer $X_A \lt q$ and computes $Y_A = a^{X_A} mod q$. 

 

Similarly, user $B$ independently selects a random integer $X_B \lt q$ and computes $Y_B = a^{X_B} mod q.$

Each side keeps the $X$ value private and makes the $Y$ value available publicly to the other side. User $A$ computes the key as $K = (Y_B)^{X_A} \pmod q$ and user $B$ computes the key as $K = (Y_A)^{X_B} \pmod q$ . These two calculations produce identical results:

The result is that the two sides have exchanged a secret value. Furthermore,because $X_A$ and $X_B$ are private, an adversary only has the following ingredients to work with: $q, a, Y_A$, and $Y_B.$ Thus, the adversary is forced to take a discrete logarithm to determine the key. For example, to determine the private key of user $B$, an adversary must compute
 

$$X_B = dlog_{a,q}(Y_B)$$
The adversary can then calculate the key $K$ in the same manner as user $B$ calculates it.

The security of the Diffie-Hellman key exchange lies in the fact that, while it is relatively easy to calculate exponentials modulo a prime, it is very difficult to calculate discrete logarithms. For large primes, the latter task is considered infeasible.

Example

 

Here is an example. Key exchange is based on the use of the prime number $q = 353$ and a primitive root of 353, in this case $a = 3$. A and B select secret keys $X_A = 97$ and $X_B = 233$, respectively. Each computes its public key:

$$A \text{ computes } Y_A = 3^{97} \text{ mod } 353 = 40 .$$
$$B \text{ computes } Y_B = 3^{233} \text{ mod } 353 = 248 .$$

After they exchange public keys, each can compute the common secret key:

$$A \text{ computes } K = (Y_B)^{X_A} \text{ mod } 353 = 24897 \text{ mod } 353 = 160.$$
$$B \text{ computes } K = (Y_A)^{X_B} \text{ mod } 353 = 40233 \text{ mod } 353 = 160.$$

We assume an attacker would have available the following information:
$q = 353; a = 3; Y_A = 40; Y_B = 248$

 

In this simple example, it would be possible by brute force to determine the secret key 160. In particular, an attacker E can determine the common key by discovering a solution to the equation $3^a\; mod\; 353 = 40$ or the equation $3^b \;mod \;353 = 248$. The brute-force approach is to calculate powers of 3 modulo 353, stopping when the result equals either 40 or 248. The desired answer is reached with the exponent value of 97, which provides $3^{97}\; mod\; 353 = 40$.With larger numbers, the problem becomes impractical.

Key Exchange Protocols
Figure below shows a simple protocol that makes use of the Diffie-Hellman calculation. Suppose that user $A$ wishes to set up a connection with user $B$ and use a secret key to encrypt messages on that connection. User $A$ can generate a one-time private key $X_A$, calculate $Y_A$, and send that to user $B$. User $B$ responds by generating a private value $X_B$, calculating $Y_B$, and sending $Y_B$ to user $A$. Both users can now calculate the key. The necessary public values $q$ and a would need to be known ahead of time. Alternatively, user $A$ could pick values for $q$ and $a$ and include those in the first message.

As an example of another use of the Diffie-Hellman algorithm, suppose that a group of users (e.g., all users on a LAN) each generate a long-lasting private value $X_i$ (for user $i$) and calculate a public value $Y_i$. These public values, together with global public values for $q$ and $α$, are stored in some central directory. At any time, user $j$ can access user $i$’s public value, calculate a secret key, and use that to send an encrypted message to user $A$. If the central directory is trusted, then this form of communication provides both confidentiality and a degree of authentication.Because only $i$ and $j$ can determine the key, no other user can read the message (confidentiality). Recipient $i$ knows that only user $j$ could have created a message using this key (authentication). However, the technique does not protect against replay attacks.

Python Code - Diffie Hellman Key Exchange

# Step 1: Agree on a large prime number q and base g (public information)

q = 353 # Prime number

g = 3   # Base (primitive root modulo q)

# Step 2: Alice chooses a private key (Xa) and computes her public key (Ya)

Xa = 97 # Alice's private key (this is secret)

Ya = pow(g, Xa, q)  # Alice's public key (Ya = g^a mod p)

# Step 3: Bob chooses a private key (Xb) and computes his public key (Yb)

Xb = 233  # Bob's private key (this is secret)

Yb = pow(g, Xb, q)  # Bob's public key (B = g^b mod p)

# Step 4: Exchange public keys (Ya and Yb) over a public channel

# Assume Alice receives Bob's public key Yb and Bob receives Alice's public key Ya

# Step 5: Alice computes the shared secret key using Bob's public key (Yb)

shared_secret_Alice = pow(Yb, Xa, q)  # (B^a mod p)

# Step 6: Bob computes the shared secret key using Alice's public key (Ya)

shared_secret_Bob = pow(Ya, Xb, q)  # (A^b mod p)

# The shared secret key should be the same for both Alice and Bob

print(f"Alice's Shared Secret: {shared_secret_Alice}")

print(f"Bob's Shared Secret: {shared_secret_Bob}")

# Verify if both shared secrets are the same

if shared_secret_Alice == shared_secret_Bob:

    print("The key exchange was successful! Both parties have the same shared secret.")

else:

    print("The key exchange failed. The shared secrets do not match.")

Output

Alice's Shared Secret: 160

Bob's Shared Secret: 160

The key exchange was successful! Both parties have the same shared secret.

Man-in-the-Middle Attack

The protocol depicted in Figure above is insecure against a man-in-the-middle attack. Suppose Alice and Bob wish to exchange keys, and Darth is the adversary. The attack proceeds as follows.

1. Darth prepares for the attack by generating two random private keys $X_{D1}$ and $X_{D2}$  then computing the corresponding public keys $Y_{D1}$ and $Y_{D2}$.

2. Alice transmits $Y_A$ to Bob.

3.Darth intercepts $Y_A$ and transmits $Y_{D1}$ to Bob. Darth also calculates $K2=(Y_A)^{X_{D2}} \pmod{q}$

4. Bob receives $Y_{D1}$ and calculates $K1=(Y_{D1})^{X_B} \pmod{q}$

5. Bob transmits $Y_B$ to Alice.

6. Darth intercepts $Y_B$ and transmits $Y_{D2}$ to Alice. Darth calculates $K1 = (Y_B)^{X_{D1}} \pmod q$

7.Alice receives $Y_{D2}$  and calculates $K2 = (Y_{D2})^{X_A} \pmod q$

At this point, Bob and Alice think that they share a secret key, but instead Bob and Darth share secret key $K1$ and Alice and Darth share secret key $K2$. All future communication between Bob and Alice is compromised in the following way.

1. Alice sends an encrypted message . $M:E(K2,M)$

2. Darth intercepts the encrypted message and decrypts it to recover  $M$.

3. Darth sends Bob $E(K1, M)$ or $E(K1, M')$, where $M'$  is any message. In the first case, Darth simply wants to eavesdrop on the communication without altering it. In the second case, Darth wants to modify the message going to Bob.

The key exchange protocol is vulnerable to such an attack because it does not authenticate the participants. This vulnerability can be overcome with the use of digital signatures and public-key certificates.

Python Code - Man in The Middle Attack

# Step 1: Agree on a large prime number q and base g (public information)

q = 23  # Prime number

g = 5   # Base (primitive root modulo p)

# Alice and Bob's private keys (normally secret)

Xa = 6  # Alice's private key

Xb = 15 # Bob's private key

# Step 2: The Man-in-the-Middle (Mallory) intercepts the communication

# Darth (the attacker) chooses her own private keys

d_alice = 10  # Darth's private key with Alice

d_bob = 20    # Darth's private key with Bob

# Step 3: Alice calculates her public key (Ya) and sends it to Bob, but Darth intercepts it

Ya = pow(g, Xa, q)  # Alice's public key

# Darth intercepts Alice's public key and sends her own to Bob

D_bob= pow(g, d_bob, q)  # Darths's public key with Bob

# Step 4: Bob calculates his public key (Yb) and sends it to Alice, but Darth intercepts it

Yb = pow(g, Xb, q)  # Bob's public key

# Darth intercepts Bob's public key and sends her own to Alice

D_alice = pow(g, d_alice, q)  # Darth's public key with Alice

# Step 5: Alice receives Mallory's (fake) public key instead of Bob's and computes the shared secret

shared_secret_Alice = pow(D_alice, Xa, q)  # (D_bob^a mod p)

# Bob receives Darths's (fake) public key instead of Alice's and computes the shared secret

shared_secret_Bob = pow(D_bob, Xb, q)  # (D_alice ^b mod p)

# Step 6: Darth computes the shared secrets with both Alice and Bob

shared_secret_Dart_with_Alice = pow(Ya, d_alice, q)  # (A^m_alice mod p)

shared_secret_Dart_with_Bob = pow(Yb, d_bob, q)  # (Yb^m_bob mod p)

# Output the shared secrets

print(f"Alice's Shared Secret: {shared_secret_Alice}")

print(f"Bob's Shared Secret: {shared_secret_Bob}")

print(f"Darth's Shared Secret with Alice: {shared_secret_Dart_with_Alice}")

print(f"Darth's Shared Secret with Bob: {shared_secret_Dart_with_Bob}")

# Verify if Alice and Bob's shared secrets match Dart secrets

if shared_secret_Alice == shared_secret_Dart_with_Alice and shared_secret_Bob == shared_secret_Dart_with_Bob:

    print("Man-in-the-Middle attack successful! Darth has intercepted the communication.")

else:

    print("The Man-in-the-Middle attack failed.")

Output 

Alice's Shared Secret: 3

Bob's Shared Secret: 13

Darth's Shared Secret with Alice: 3

Darth's Shared Secret with Bob: 13

Man-in-the-Middle attack successful! Darth has intercepted the communication.