Key Exchange

Please read my previous article on TLS to understand the key exchange step.

Key exchange is a protocol, where keys are shared between two trusted parties over an untrusted network. The keys can then be used to perform other cryptographic operations like encryption, decryption, signing, etc. Key exchange is a fundamental construct used to secure internet traffic (an untrusted network) using TLS. The protocol used during a specific communication over the internet is represented by the agreed cipher suite between the parties while establishing a TLS channel. For example, in the cipher suite definition TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256, the key exchange algorithm to be used is represented in the beginning, i.e., ECDHE.

Commonly Used Protocols

DHE (Diffie-Hellman Key Exchange)

Goal: We have a symmetric encryption scheme and want to agree on keys that we can use to encrypt the messages, over an unsecured channel.

Steps:

1. We each pick a number, generally large, and keep it a secret, even from each other. I will pick x, and you will pick y.
2. We agree on two more numbers, both prime, which anybody can know. We will call them g and n.
3. I will calculate g_xmodn and tell you my answer. You will calculate g_ymodn and tell me your answer.
4. Our shared key is g_xymodn=(g_ymodn)_xmodn=(g_xmodn)_ymodn.

It is important to note that DHE is not limited to two parties, and several parties can take part by performing iterations on the protocol. The strength of the algorithm is the difficulty of factoring large-enough prime numbers.

EC-DH (Elliptic Curve Diffie-Hellman Key Exchange)

Goal: We have a symmetric encryption scheme and want to agree on keys that we can use to encrypt the messages, over an unsecured channel. This is a variant of DHE (explained above), but instead of using a prime number and relying on the difficulty of prime number factorization, uses elliptic curves to represent the key materials.

Steps:

1. We each pick a public key d (random selected integer) and private key pair representing a point in the elliptic curve such that Q = d.G (where G is the domain parameter of the curve being used). Let the key pairs be (d_A, Q_A) and (d_B, Q_B).
2. They share the public keys (Q_A and Q_B) between them over the unsecured network. The public keys can be static and shared by a X.509 certificate, or they can be ephemeral, where-in the algorithm is called ECDHE (the ‘E’ at the end stands for ephemeral).
3. Then both parties computes point in the elliptic curve such that (x_k, y_k) = d_A.Q_B = d_A.d_B.G=d_B.d_A.G=d_B.Q_A.
4. x_k is the shared key between both the parties, which can be used to further derive additional symmetric keys.

RSA Asymmetric Encryption

Goal: I want anybody to be able to encrypt a message, but I’m the only one who can decrypt it. I do not want to share decryption keys with anybody.

Steps:

1. I choose two large primes, p, and q.
2. I calculate n such that pq=n.
3. I calculate t such that (p−1)(q−1)=t.
4. I choose an integer e that is both less than t and coprime with t.
5. I find d such that d is the multiplicative inverse of emodt.
6. I release (e,n) as my public key, and retain (d,n) as my private key.
7. When you communicate with me, you treat your message as a large number m. The ciphertext c is given by c=m_emodn, and decrypted by m=c_dmodn.

Quantum Key Exchange

Most of the above-used algorithms are not resistant to post-quantum cryptoanalysis and can supposedly be broken using an applicable quantum computer in hand. There is huge on-going research to come up with newer and resistant algorithms for key exchange and other cryptographic operations. These algorithms use the quantum states (i.e. qubits) to operate on the key materials to achieve the goals. Most of the protocols are very experimental. Two of known are:

BB84 protocol

E91 protocol

Here is an exhaustive list of quantum key exchange protocols.