Diffie-Hellman

Secret Key Exchange (Diffie-Hellman) - ComputerphileComputerphile · Diffie-Hellman key exchange explained, 9 minKey Exchange Problems - ComputerphileComputerphile · man-in-the-middle attack on Diffie-Hellman, 9 minDiffie-Hellman Key ExchangeArt of the Problem · Diffie-Hellman with the colour-mixing analogy, 5 minDiffie-hellman key exchange | Journey into cryptography | Computer Science | Khan AcademyKhan Academy Labs · short Diffie-Hellman animation, 2 min

Key exchange conceptSearch on YouTubeBookmarkSaved

The ideaSearch on YouTubeBookmarkSaved

The concept is astounding. Two parties carry on a public conversation and still end up with a secret that only the two of them know. The shared secret comes from private secrets and publicly shared information.

Alice knows:     a, q, x_A, y_A, y_B
Bob knows:       a, q, x_B, y_B, y_A
Everyone knows:  a, q, y_A, y_B
Result: one equal value K_AB that only Alice and Bob can compute

Key distribution schemeSearch on YouTubeBookmarkSaved

Primitive rootsSearch on YouTubeBookmarkSaved

A primitive root of a prime number $n$ is an integer $r$ in the range $[1, n-1]$. For $x$ in the range $[0, n-2]$, the values of $r^x \bmod n$ are all different. The slide task returns $-1$ if $n$ is not prime.

Slide example: input $n = 7$. The smallest primitive root is $3$.

The six values $1, 3, 2, 6, 4, 5$ are all different. They cover every nonzero residue mod 7, thus $3$ is a primitive root.

The DH protocolSearch on YouTubeBookmarkSaved

SetupSearch on YouTubeBookmarkSaved

All users agree on global parameters:

• A large prime integer (or polynomial) $q$.
• A number $a$ that is a primitive root mod $q$.

Each user (for example, A) makes a key:

• A chooses a secret key (a number): $x_A \lt q$.
• A computes the public key: $y_A = a^{x_A} \bmod q$.
• A makes the key $y_A$ public.

Shared session keySearch on YouTubeBookmarkSaved

The shared session key for users A and B is $K_{AB}$:

$K_{AB} = a^{x_A \cdot x_B} \bmod q = y_A^{x_B} \bmod q \ (\text{B computes}) = y_B^{x_A} \bmod q \ (\text{A computes})$

Each principal has the public key of the other, its own secret, and $a$ and $q$.

An eavesdropper sees only $q$, $a$, $y_A$ and $y_B$. To get $K_{AB}$, the eavesdropper must find $x_A$ or $x_B$ from $y = a^{x} \bmod q$. This is the discrete logarithm problem, which is hard for a large $q$.

Protocol figureSearch on YouTubeBookmarkSaved

The slide figure shows the protocol for Alice and Bob in parallel:

Session key useSearch on YouTubeBookmarkSaved

$K_{AB}$ is the session key (or pre-key) in a private-key encryption scheme between Alice and Bob. If Alice and Bob communicate again later, they get the same key as before. This is true unless they choose new public keys. They can use nonces and the pre-key to make the session key different.

Worked exampleSearch on YouTubeBookmarkSaved

Parameters and keysSearch on YouTubeBookmarkSaved

Alice and Bob want to swap keys.

Both routes give $K_{AB} = 160$.

Square-and-multiply checkSearch on YouTubeBookmarkSaved

The slide gives only the results. These tables show how to get them. Each row squares the row above, mod 353.

The exponents in binary: $97 = 64 + 32 + 1$ and $233 = 128 + 64 + 32 + 8 + 1$.

Man-in-the-middle attackSearch on YouTubeBookmarkSaved

Key exchange protocolsSearch on YouTubeBookmarkSaved

There are two ways to use DH keys:

• Users can create random private/public DH keys each time they communicate.
• Users can create a known private/public DH key and publish it in a directory. Other users consult the directory and use the keys to communicate securely.

Both methods are vulnerable to a Man-in-the-Middle Attack. Authentication of the keys is necessary.

Attack stepsSearch on YouTubeBookmarkSaved

The slide gives the attack in 7 steps:

1. Darth prepares and creates two private/public keys.
2. Alice transmits her public key to Bob.
3. Darth intercepts this and transmits his first public key to Bob. Darth also calculates a shared key with Alice.
4. Bob receives the public key and calculates the shared key (with Darth instead of Alice).
5. Bob transmits his public key to Alice.
6. Darth intercepts this and transmits his second public key to Alice. Darth calculates a shared key with Bob.
7. Alice receives the key and calculates the shared key (with Darth instead of Bob).

Darth can then intercept, decrypt, re-encrypt and forward all messages between Alice and Bob.

Attack notationSearch on YouTubeBookmarkSaved

The slide uses this notation. Darth has two secrets, $x_{DA}$ and $x_{DB}$.

Darth computes the same two keys from his own secrets: $K_{DAB} = y_B^{x_{DA}} \bmod q$ and $K_{ADB} = y_A^{x_{DB}} \bmod q$.

Bob                       Darth                       Alice
                            <------------ y_A ----------|
 <-------- y'_A ------------|
 |--------- y_B ----------->|
                            |----------- y'_B --------->
K_DAB = y'_A^xB mod q                   K_ADB = y'_B^xA mod q

Darth has a private, unauthenticated channel with each of Alice and Bob.

DefencesSearch on YouTubeBookmarkSaved

The man-in-the-middle attack is also known as the "Bucket Brigade" attack. The defences from the slide are:

• A reliable way to associate a public key with its principal is necessary.
• Public key infrastructure (PKI) is one way.
• The PGP web of trust is another way.
• In some circumstances, scheduling/timing can prevent MITM.

Quick self-testSearch on YouTubeBookmarkSaved