Ralph Merkle
Although this is usually referred to in the simpler form of Diffie-Hellman, no less an authority than Martin Hellman has said that it should also be credited to Ralph Merkle, whose work Diffie and Hellman built upon:
The system…has since become known as Diffie–Hellman key exchange. While that system was first described in a paper by Diffie and me, it is a public key distribution system, a concept developed by Merkle, and hence should be called ‘Diffie–Hellman–Merkle key exchange’ if names are to be associated with it. I hope this small pulpit might help in that endeavor to recognize Merkle’s equal contribution to the invention of public key cryptography.
So, what did Ralph Merkle do exactly? He pioneered the whole field of key exchange when communications were observable. You see, the whole problem of key exchange was always getting the key distributed without a breach of security. If you print up a sheet of keys with instructions as to which key to use (e.g. a “key of the day” system), you have to worry about this sheet being intercepted in some way and therefore having your communications compromised. Merkle came up with ways to solve this problem such as the Merkle Puzzles. The idea was that Bob would prepare a series of “puzzles”, i.e. encrypted messages with an unknown key. Bob would make lots of these, and send them to Alice. Now the crucial part is that any one of these puzzles can be solved through a brute-force attack, but solving all of them would be computationally infeasible, i.e., would require so many resources over such a long period that it as not practical to do that. Alice picks just one of these encrypted messages, brute force solves it, and discovers the message contains an identifier as well as a session key. She uses the session key to encrypt a reply to Bob, and can send the identifier in the clear to let Bob know which one she solved and hence which key she used. This can be in the clear because Eve (the eavesdropper) cannot know which puzzle the identifier refers to since it was encrypted within the message. Eve’s best strategy is to brute force all of the puzzles, but as we said this is not really practical.
In 1996 Ralph Merkle was awarded the ACM award for the invention of Public Key Cryptography
Diffie-Hellman
In 1976 Whitfield Diffie and Martin Hellman published a paper called New Directions in Cryptography which first presented their idea for key exchange. I’m going to keep the math at a level I can understand, so this may be somewhat oversimplified, but I think essentially accurate.
As before, Alice and Bob want to communicate securely, but Eve is trying to eavesdrop on what they say. So can they do this? They need to have a way to establish a shared key they can use to encrypt their communications, and somehow do this even though they are communicating over open channels. The solution is pretty clever, and involves Modular Arithmetic. This type of math involves numbers which “wrap around” when a certain value is reached. A good example is a standard clock, which wraps around at the number 12. So if it is ten o’clock, and you need to meet someone in three hours, that means you need to meet them at one o’clock, not thirteen o’clock. There is more to modular arithmetic, but this is enough to establish what we need to know to understand the Diffie-Hellman approach.
Step one in Diffie-Hellman is that there is information that is publicly available, and information that is secret. Information that is publicly available can be sent “in the clear” over a public communications channel. You don’t really care who may be looking. In Diffie-Hellman, the public information includes:
- The prime base number g
- the prime modulus p
Generally, the base number does not need to be terribly large, but the modulus should be a large prime number. This is the number at which your calculations “wrap around”. You assume that Eve has both of these numbers because they are publicly available.
Then Alice and Bob each have a secret number, known only to each of them. Alice does not know Bob’s secret number, neither does Bob know Alice’s secret number. Let’s call Alice’s number a, and Bob’s number b. These do not need to be prime numbers, just secret.
So Alice does a computation A = g^a mod p, which is the base g raised to the power a, and then applying the modular arithmetic to the answer using modulus p. Bob does a similar computation, only he uses his secret number b instead of a, and computes B = g^b mod p. They then exchange these numbers, which are still secret. When Alice gets B = g^b mod p, she does not know what b is, and it is computationally infeasible to brute force attack it. Similarly, Bob does not know what a is when he gets A = g^a mod p. Each of them then takes this secret number, and does the same process. Alice takes B, creates a shared secret S = B^a mod p, and Bob creates S = A^b mod p. And when this is done, it runs out Alice and Bob have created the same shared secret!
This can be hard to follow in abstract, so let’s try an example using very small numbers.
- g = 4
- p = 11
- a = 6
- b = 8
So, Alice first computes 4^6 mod 11. 4 to the 6th power is 4096, but we now have to apply the modulus of 11. Since wrapping around every 11 is equivalent to dividing by 11 and keeping only the remainder, the answer is 4.
Now for Bob. He computes 4^8 mod 11. 4 to the 8th power is 65,536. Applying modulus 11, we find the remainder is 9.
Alice sends Bob the number 4, and Bob sends Alice the number 9.
Alice then computes 9^6 mod 11. 9 to the 6th power is 531,441. Applying modulus 11, we get a remainder of 9.
Bob computes 4^8 mod 11. 4 to the 8th power is 65,536. Applying modulus 11, we find the remainder is 9.
So, in the end both Alice and Bob have a shared secret, the number 9.
Diffie-Hellman in practice
Generally speaking, you want the number p (publicly available) and the numbers a and b (secrets) to be much larger than in our example (g can be small without harming security). Cracking a Diffie-Hellman shared secret key is an example of a discrete logarithm problem because you are essentially trying to find the integer solution of g^(ab) mod p, where g and p are known, but a and b are unknown. There are some special cases that are easily solvable, but there is no general solution that is feasible. And you can use Diffie-Hellman with more than two people. For instance, add in Carol to the conversation, and you wind up in the end with g^(abc) mod p. Generally speaking, if you follow the rules, Diffie-Hellman is considered secure against eavesdropping.
However, there are weaknesses to the Diffie-Hellman process. One of the biggest is that there is no form of authentication involved, so can Alice really be certain she is communicating with Bob, and vice-versa? It is quite feasible to launch a man-in-the-middle attack if Mallory were to intercept Alice’s message to Bob and Bob’s message to Alice, she could establish two key exchanges (one with Alice and one with Bob), and simply route messages through herself, reading everything they say. Of course, if she is ever absent when they try to communicate, that would alert Alice and Bob that their channel had been compromised. This is why in practice Public Key cryptography (e.g. RSA) is used to establish initial communication in most cases, and that channel then is used to create the shared key without worry about man-in-the-middle attacks.
The broader source of possible weakness comes with the solubility of the discrete algorithm problem. Like so much of cryptography, this is an arms race where capabilities are being upgraded. Certain types of discrete logarithm problems are now fairly easy to solve, and in this area capabilities only ever increase. That is why Diffie-Hellman approaches are being modified to use elliptic curve algorithms. Still, Diffie-Hellman has an important role in cryptography, particularly for forward secrecy, which is the problem you have if someone stores your encrypted messages in anticipation of future advances in decryption. But that is a topic for another day.
Listen to the audio version of this post on Hacker Public Radio!
