Diffie-Hellman key exchange in End-to-End Encryption (E2EE)
When it comes to data encryption, there are mainly two types — Symmetric and Asymmetric. Popular encryption methods like AES uses symmetric key encryption whereas RSA uses an asymmetric approach.
Nowadays, chat applications use end-to-end encryption to protect users’ chat messages from getting compromised by hackers or by the organization itself. End-to-end encryption (E2EE) asserts encryption and decryption to take place at the clients’ devices (end destinations). This allows the ciphered texts to transmit via an insecure and public channel, such as the internet, without the messages being compromised.
Let’s look at E2EE using both asymmetric and symmetric approaches.
Using ASYMMETRIC encryption in Chat applications
Asymmetric encryption requires two types of keys — a public and a private key-pair. The following diagrams explain the process of
- Public key exchange
- Sending and receiving messages using this method.
Note: Alice’s keys are denoted by orange while Bob’s keys are denoted by blue color.
Messages in E2EE can be encrypted using the receiver’s public key at the sender’s end so that it can only be decrypted at the receiver’s end using his/her private key.
The public keys of users can be stored in the database and can be serviced upon client’s request while the private keys can reside on users’ devices.
Using SYMMETRIC encryption in Chat applications
This method is relatively simple than the asymmetric approach. It requires both clients to unanimously decide on a common key for encryption and decryption.
The challenge?
How will Alice and Bob share the common key via the insecure channel? This where Diffie-Hellman key exchange method comes in. The objective is…
To obtain the common key without even exchanging the key at the first place.
This is done by GENERATING the key at the clients’ side independently and ending with a same key! Sounds interesting?…
It involves
- A large prime number (P),
- It’s primitive root (g) and
- A private key for each client.
(P) and (g) can be exchanged via the insecure channel.
Alice generates a number (A) at her end using her private key (a) as A = g^a modulo P , where ^ denotes power of. Likewise Bob generates a number (B) at his end using his private key (b) as B = g^b modulo P.
Now they can share this newly generated keys (A) and (B) via the insecure channel as no one can reverse engineer it to get back their private keys (a) or (b).
Why???
This is so because even if you know the values of (g) and (P), it becomes practically impossible to deduce (a) or (b) since you don’t know how many revolutions g^a modulo P or g^b modulo P made between 0 and P-1.
This is the power of modulo. You can have a very large number inside a determined boundary using modulo! In this case, the boundary is between 0 and P-1 inclusive.
So at this point, Alice receives (B) and Bob receives (A). Alice can now generate the common key by common key = B^a modulo P at her end. Likewise Bob can generate the the same using common key = A^b modulo P at his end. The two formulae will generate the same result! Now both of them can exchange messages by encrypting and decrypting using this newly generated common key.
You can also understand this using color mixing.
Suppose the common color (yellow) is the large prime number (P). After it mixes with red (a) or green (b) private keys, the resulting colors are orange and blue respectively. There is no way to get the red (a) or the green (b) back from these mixtures as you don’t know the amount of colors getting mixed in. Because of this, these mixtures can be exchanged openly. Alice adds her red (a) with Bob’s mixture to get the brownish color and Bob mixes his green (b) with Alice’s mixture to get the same brownish color.
Try it with actual numbers!
Take any prime number (P), it’s primitive root (g) and private keys (a) and (b).
Here P = 23, g = 5, a = 3 and b = 7.
Applying the Diffie-Hellman algorithm, we got the common key as 14 for both Alice and Bob.
Conclusion
Both Alice and Bob generated the same number despite the fact that they didn’t know each other’s private key. The important thing to note is that the prime number (P) should be large enough, approximately 4096 bits, because a small prime number will lead the modulo circle to have less numbers which can be easy to brute-force.
In the chat application, (P) and (g) can be exposed to the clients using which they can generate their public key (g^a modulo P). These public keys can be exchanged freely in between the clients to create the symmetric key at their end, hence completing Diffie-Hellman.
References
https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange
https://www.youtube.com/watch?v=Yjrfm_oRO0w&t=349s
