In the 1970s, digital communication was just beginning to take off. Technology was improving and computer networks were expanding, and so was the volume of information being shared through those networks. With every new party entering the digital landscape came new cryptographic challenges, a major one being how to develop new secure ways of communication fast enough to keep up with the growing demand. For any given channel between two parties to be secure, the channel needs at least one key to encrypt and decrypt messages sent on that channel. Traditional ways of secretly deciding on those keys at the time, such as physically delivering the key, were expensive and time consuming, and were insufficient for the new era. Enter cryptographers Whitfield Diffie and Martin Hellman, who proposed a new method of creating keys in their 1976 paper “New Directions in Cryptography” only using public methods of communication.
The method they proposed worked like so:
Say we have two users, Alice and Bob, who want to decide on a shared private key to encrypt their message, but all communication between them can be overheard by other people. If they communicate their key to each other at all, they risk rendering their message readable to everyone. Instead of ever sharing their key, Alice and Bob publicly agree on two numbers q and p where p is prime. They independently come up with the numbers
sharing them with nobody. Then, they each compute
for their respective X’s, and share their values
Y is easy to compute from X, but note that finding what X is from Y is quite difficult. For example, try to compute
With a calculator, it takes only a few seconds to find the answer: 4. But what if you only knew Y = 4, and were trying to solve
You’d have to guess and check, which might be possible when X = 4, but what if X = 1000? Or 1,243,797,979,807,396,832,410? It would probably take you a while to find it. In a real encryption process, X would be very large, as would the prime p —it would take a lot of guessing and checking. Now that we know that their X’s are safe, even if they publish their Y’s, let’s go back to Alice and Bob
Alice can now use Bob’s Y to compute
And Bob can similarly compute
Thus both users can relatively easily arrive at the same shared key, but the only public information is p, q, Ya, Yb, so it would be difficult for an outside person to compute, as they would have to solve
This equation is called the discrete logarithm problem, and solving it is believed to be computationally hard, although this has yet to be proven. However no easy solution has been found and the best algorithm currently used to solve this, the number field sieve, runs in exponential time (2 to the power of a polynomial) which is generally slow enough to be unfeasible to hackers.
So, this is a neat mathematical trick, but why should you care? Because it’s such a neat trick, and avoids costly secure key exchanges for systems with millions of users, that it is accepted as a secure key exchange by two thirds of frequently visited websites. So in fact, the security of this fun abstract algebra result matters quite a bit. Unfortunately, the system has some concerning vulnerabilities.
In 1976, existing methods for solving the discrete log problem were so inefficient that this process was quite secure. As a result, some internet servers still allow key exchanges when the prime p is as small as 512 bits. The problem with this is that both the math used to solve this problem and the computers that do the math are getting faster all the time. In 2019 cryptographers were able to solve the discrete logarithm problem with a prime p that was 795 bits long, which suggests any site secured with a 512 bit prime could be vulnerable to attack.
Another issue is that for our users Alice and Bob to arrive at the same secret key, they need to communicate their Y’s to each other. Since they are communicating through some public (and thus vulnerable) channel, it is possible for what is called a man in the middle attack, where someone else intercepts their communication, pretending to be the other user. So Bob and Alice unwittingly construct keys based on numbers given by a third party, and anything they encrypt with those keys is not truly safe.
Thus, while the Diffie-Hellman key exchange is a useful trick in efficiently communicating keys, it does not totally escape the dangers of public communication, and must be used in conjunction with other security processes to be viable.
Further reading:
https://ee.stanford.edu/~hellman/publications/24.pdf — the original paper
https://wstein.org/edu/124/lectures/lecture8/html/node5.html -further explanation of the math
https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf — a dense but interesting analysis of the system’s shortcomings
