Cryptographic Key Exchange

We previously discussed the difference between symmetric and asymmetric encryption, and today we’ll talk about how the keys are actually exchanged.

In general, cryptographic key exchange or encrypted key exchange (EKE) protocols work by allowing the two parties to generate a shared secret without revealing the secret to any third parties. This is typically done using a combination of public key cryptography and mathematical algorithms. The shared secret can then be used as a key for a symmetric cipher, which allows the two parties to communicate securely.

Usage

As method uses public key, it naturally only applies to the asymmetric encryption, as in symmetric encryption the keys are not shared — known and agreed upon in advance.

Cryptographic key exchange is a method of securely exchanging cryptographic keys over a network. It is a fundamental aspect of many cryptographic protocols, as it allows two parties to establish a shared secret that can be used to securely communicate with each other.

The exchange is used in a variety of applications, including secure communication, secure online transactions, and access control. It is often used to establish a secure connection between two parties, such as a client and a server, or between two devices. So before any files can be sent securely over protocols like FTPS, HTTPS, and SFTP, the two communicating parties must first engage in a key exchange.

Overview

In the most general form of EKE, at least one party encrypts an ephemeral (one-time) public key using a password, and sends it to a second party, who decrypts it and uses it to negotiate a shared key with the first party.

Another variation of this scheme exists, called Augmented-EKE. Augmented methods have the added goal of ensuring that password verification data stolen from a server cannot be used by an attacker to masquerade as the client, unless the attacker first determines the password (e.g. by performing a brute force attack on the stolen data).

The two most popular key exchange algorithms are RSA and Diffie-Hellman (now known as Diffie-Helmlman-Merkle). It probably wouldn’t be too much of a stretch to say that the advent of these two key exchange protocols accelerated the growth of the Internet, especially business-wise. That’s because these two protocols allowed clients and servers, as well as servers and servers, to exchange cryptographic keys over an insecure medium (the Internet) and in turn enable them to transact electronically in a secure manner.

Lately, the emergence of elliptic curve cryptography has introduced new exchange protocols like ECDH (Elliptic Curve Diffie-Hellman) and ECDHE (Elliptic Curve Diffie-Hellman Ephemeral).

We’ll focus on the Diffie-Hellman family, known as DH-EKE, which has survived multiple attacks over the years and has led to improved variations.

Diffie-Hellman

In 1976, Whitfield Diffie and Martin Hellman published a cryptographic protocol called the Diffie–Hellman key exchange (D–H) based on concepts developed by Hellman’s PhD student Ralph Merkle. The protocol enables users to securely exchange secret keys even if an opponent is monitoring that communication channel. It is based on the idea of using exponentiation in a finite field to generate a shared secret that can be used to encrypt and decrypt messages.

Here is an example of the Diffie-Hellman key exchange process and as illustrated in the diagram below:

Alice and Bob agree on a finite field and a prime number within that field (this is known as the “modulus”). Let’s say they choose the finite field GF(23), p, and the prime number 5, g.

1. Alice selects a secret integer, “a”, and Bob selects a secret integer, “b”. These integers will be used to generate the shared secret.
2. Alice computes A = 5^a mod 23 and sends A to Bob. Bob computes B = 5^b mod 23 and sends B to Alice.
3. Alice computes the shared secret by performing the following calculation: sharedSecret = B^a mod 23. Bob computes the shared secret using the same calculation: sharedSecret = A^b mod 23.
4. Both Alice and Bob now have the shared secret, which they can use as a key to encrypt and decrypt messages.

From the Alice’s side:

# Alice's side of thNote that in this example, the shared secret is the same for both Alice and Bob, even though they used different secret integers to generate it. This is because the shared secret is generated using a mathematical function that is commutative, meaning that the order of the operands does not affect the result. This property is what allows Alice and Bob to establish a shared secret without revealing their secret integers to each other.e key exchange

# Choose finite field and prime number
field = GF(23)
prime = 5

# Choose secret integer
secretA = 6

# Compute A and send to Bob
A = (prime ^ secretA) mod field
send A to Bob

# Receive B from Bob
B = receive from Bob

# Compute shared secret
sharedSecret = (B ^ secretA) mod field

And the Bob’s side:

# Bob's side of the key exchange

# Choose secret integer
secretB = 15

# Compute B and send to Alice
B = (prime ^ secretB) mod field
send B to Alice

# Receive A from Alice
A = receive from Alice

# Compute shared secret
sharedSecret = (A ^ secretB) mod field

Note that in this example, the shared secret is the same for both Alice and Bob, even though they used different secret integers to generate it. This is because the shared secret is generated using a mathematical function that is commutative, meaning that the order of the operands does not affect the result.

This property is what allows Alice and Bob to establish a shared secret without revealing their secret integers to each other.

The reason why D-H exchange work, is discrete logarithm cryptography, which is based on the difficulty of solving the discrete logarithm problem.

Briefly, it is a mathematical problem that involves finding the integer “x” in the equation “g^x = y mod p”, where “g” and “y” are known, and “p” is a prime number. This problem is considered difficult to solve because there is no known efficient algorithm for finding the value of “x” for arbitrary values of “g”, “y”, and “p”.

Overall, while Diffie-Hellman is a widely used and effective key exchange protocol, however there several practical limitations, which makes Elliptic Curve Diffie-Hellman (ECDH) a preferable choice, if possible.

Elliptic Curve Diffie-Hellman (ECDH)

Elliptic Curve Diffie-Hellman (ECDH) is a variant of the Diffie-Hellman key exchange protocol that uses elliptic curve cryptography instead of traditional exponentiation in a finite field. ECDH has several advantages over ordinary Diffie-Hellman:

1. ECDH is more efficient: Elliptic curve operations are generally faster and require less computational power than finite field operations, making ECDH more efficient than ordinary Diffie-Hellman. Read more about how it works and its advantages in the previous article.
2. ECDH is more secure: Elliptic curve cryptography is generally considered to be more secure than finite field cryptography, as it is more resistant to certain types of attacks.
3. ECDH keys are shorter: Because elliptic curve operations use smaller numbers, ECDH keys are generally shorter than ordinary Diffie-Hellman keys, making them easier to transmit and store.
4. ECDH has a smaller key size: Because elliptic curve operations are more efficient and secure, ECDH can achieve the same level of security as ordinary Diffie-Hellman with a smaller key size. This can be particularly useful in applications where key size is a limiting factor, such as in certain types of hardware devices.

Overall, ECDH is a more efficient and secure variant of the Diffie-Hellman key exchange protocol, and it is widely used in a variety of applications. One aspect, however, which still remains an issue is Forward secrecy and is solved in its variation — Elliptic Curve Diffie-Hellman Ephemeral (ECDHE).

Elliptic Curve Diffie-Hellman Ephemeral (ECDHE)

Elliptic Curve Diffie-Hellman Ephemeral (ECDHE) is a variant of Elliptic Curve Diffie-Hellman (ECDH), that uses ephemeral keys.

In ECDHE, each party generates a new, short-lived key pair for each session, rather than using a long-lived static key pair as in ECDH. This has several advantages:

1. Improved security: Because ECDHE uses ephemeral keys that are only used for a single session, it is more resistant to certain types of attacks, such as replay attacks, in which an attacker captures and reuses a key from a previous session.
2. Forward secrecy: In ECDHE, the shared secret is derived from the ephemeral keys, which are discarded after the session. This means that even if an attacker obtains a copy of the ephemeral keys, they will not be able to decrypt past communication, as the shared secret is no longer known.
3. Simplified key management: In ECDHE, each party generates a new key pair for each session, rather than managing a long-lived static key pair. This can simplify key management and reduce the risk of key compromise.

Overall, ECDHE is a more secure and flexible variant of ECDH that is well-suited for use in applications where security and forward secrecy are important considerations.