hpr-knowledge-base/hpr_transcripts/hpr2510.txt

Episode: 2510
Title: HPR2510: 26 - Diffie-Hellman-Merkle Key Exchange
Source: https://hub.hackerpublicradio.org/ccdn.php?filename=/eps/hpr2510/hpr2510.mp3
Transcribed: 2025-10-19 04:24:23

---

This in HBR episode 2,510 entitled 26 Diffie Helm and Merkel Key Exchange and in part
on the series Privacy and Security, it is hosted by a huker and in about 21 minutes long
and carry my clean flag.
The summary is a basic explanation on how Diffie Helm and Merkel Key Exchange works.
This episode of HBR is brought to you by an honesthost.com.
Get 15% discount on all shared hosting with the offer code HBR15.
That's HBR15.
Better web hosting that's honest and fair at an honesthost.com.
Hello, this is a huker welcoming you to Hacker Public Radio and another exciting episode.
This time I'm going to return to talking about security.
It's been a while since I did a security podcast and I think we're about to do for one.
I'm calling this Diffie Helm and Merkel Key Exchange.
The first thing that probably you're going to be thinking is, wait a minute, I've heard of Diffie Helm and who's this Merkel guy?
Well, he was actually the person who started all of this.
So, in fact, Martin Helm and himself said that Merkel should be corrected because Diffie and Helm and built upon his work.
So, I will quote from Martin Helm and the system has since become known as Diffie Helm and 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 Merkel and hence should be called Diffie Helm and Merkel Key Exchange if names are to be associated with it.
I hope this small pulpit might help in that endeavor to recognize Merkel's equal contribution to the invention of public key cryptography.
Well, I may return as we go along to just calling it Diffie Helm and I wanted to take a moment to acknowledge what Ralph Merkel did and I'm going to explain what he did because these things are kind of interesting.
What did Ralph Merkel do?
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.
For instance, if you print up a sheet of keys with instructions as to which key to use for kind of a key of the day system or one time pads or all of these things, which are extremely secure once they've been distributed.
But you have to worry about the distribution because your sheet of instructions could be intercepted in some way and then your communications would be compromised.
Now Merkel came up with ways to solve this problem and one of the first ones was what were called Merkel puzzles.
So what is Merkel puzzles?
Well, the idea was that Bob and remember in cryptography, Alice and Bob are always the two people trying to communicate.
So Bob would prepare a series of puzzles that is encrypted messages with an unknown key.
Bob would make lots of these and send them to Alice.
Now, the crucial part is that they are very carefully designed so that any one of them can be brute force attacked in a reasonable period of time, but not all of them.
If you were trying to do all of them, you would discover that that is now computationally infeasible.
In other words, that would require so many resources over such a long period that it's just not practical.
In cryptography, you run across the phrase computationally infeasible a lot because there are very few things that are impossible.
But we can make them to all intents and purposes impractical.
If it's going to take six centuries to brute force, the solution to a encrypted message, for most purposes, that's probably OK.
It's not impossible to crack it is just highly unlikely.
So, with the Merkel puzzles, Bob sends a whole bunch of these over to Alice, and then Alice picks one.
It doesn't matter which one, she just picks one, and brute force solves it.
And when she opens it up, she discovers that the message contains an identifier as well as a session key.
So, she uses the session key to encrypt a reply to Bob, and can send the identifier along 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, and in these things Eve is always 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.
So, in 1996, Ralph Merkel was awarded the ACM award for the invention of public key cryptography.
So, there's our discussion of Ralph Merkel, interesting fellow. He's done a lot of other things since then.
You know, fire up your browser, Google Ralph Merkel. He's worth knowing more about.
But, what happened with that?
In 1976, Whitfield Diffie and Martin Hellman published a paper called New Directions in Cryptography, which first presented their idea for key exchange.
Now, I'm going to keep the math at a level I can understand, so this may be somewhat oversimplified, but I think it is going to be essentially accurate.
Now, as before, Alice and Bob want to communicate securely, but Eve is trying to eavesdrop on what they say. So, how can they do this?
Well, 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 it involves modular arithmetic.
Now, 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 10 o'clock and you need to meet someone in three hours, that means you need to meet them at 1 o'clock, not 13 o'clock.
That's what we mean by wrapping around. Now, there is more to modular arithmetic, but this is enough to establish what we need to know to understand the Diffie Hellman approach.
So, 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, which will refer to as G, and the prime modulus, which will refer to as P.
Now, generally, the base number does not need to be terribly large.
This could be as small as 4 or 5, but the modulus should be a large prime number.
Now, this is the number at which your calculations wrap around.
So, 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 themselves. Alice does not know Bob's secret number.
Neither does Bob know Alice's secret number, so let's call Alice's number lowercase A and Bob's number lowercase B.
These don't need to be prime numbers. They just need to be secret numbers.
So, Alice does a calculation, and the result capital A is found by taking the base G and raising it to the power of lowercase A,
and then taking that mod P, which means you do the power calculation, the exponent, and then you apply modular arithmetic using the modulus.
So, whatever number you came up with, it's going to wrap around at some point, and you're going to take a look at that.
Now, Bob does a similar computation only he uses his secret number, lowercase B, instead of lowercase A, and computes the result uppercase B equals G to the power of lowercase B mod P.
They then exchange these numbers, which are still secret.
When Alice gets uppercase B, she does not know what lowercase B is, and it is computationally infeasible to brute force attack it.
Similarly, Bob does not know what lowercase A is when he gets uppercase A.
And remember, uppercase A and uppercase B have been publicly observable. They've been transmitted in the clear.
So, each of them takes this number, and they repeat the process that they did originally with the new number.
So, Alice takes uppercase B and creates a shared secret by taking uppercase B, raising it to the power of lowercase A, modulus P.
And Bob creates the same shared secret by taking uppercase A to the power of lowercase B, modulus P.
And when this is done, it turns out Alice and Bob have created the same shared secret.
Now, if you take a little look at the mathematics of this, you'll see that it really does work out.
But, in the abstract, it can be kind of hard to follow. So, let's create an example.
We'll use very small numbers for the example. So, let's say that G, the initial base is 4.
The modulus P is 11.
And note that is a prime number, which was one of the things that we had to do here.
Then, Alice's secret number, lowercase A, is 6.
And Bob's secret number, lowercase B, is 8.
So, Alice first computes 4 to the power of 6, modulus 11.
Well, 4 to the 6th power is 4,096.
But now we have to apply modulus 11.
Since wrapping around every 11 is equivalent to dividing by 11 and keeping only the remainder, the answer turns out to be 4.
Now, for Bob, he computes 4 to the power of 8, modulus 11.
4 to the 8th power is 65,536.
Applying modulus 11, we find the remainder is 9.
Well, Alice sends Bob the number 4.
That was the result of her calculation. Bob sends Alice the number 9.
That was the result of his calculation.
So, Alice takes that 9, raises it to the power of 6, modulus 11.
Well, 9 to the 6th power is 531,441.
Applying modulus 11, we get a remainder of 9.
Bob takes Alice's number of 4 and raises it to the power of 8, modulus 11.
Well, actually, we did that one already.
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.
Try some more examples if you're still not certain about this,
but it is a fact that you can do this calculation with any set of numbers,
and you're always going to come out with identical answers at the end.
So, what you have is a way that Alice and Bob could start with secret numbers
that they don't know what each other's secret number is,
and can arrive at a shared secret through openly observable communications.
Well, that's an absolutely fantastic result.
So, in practice, how is Diffie-Hellman employed?
Now, you know, the number P, the modulus, is publicly available.
The numbers A and B, lowercase A and lowercase B, are the secrets.
And all three of those numbers should be much larger than our example.
I just used small numbers so that you could follow the math a little bit easier,
you know, in today's day of spreadsheets, try some big ones,
and have some fun with it if you like, but math is math.
Now, cracking a Diffie-Hellman-shared secret key is an example of something called a discrete logarithm problem.
Now, you may recall from earlier discussion, discrete logarithm is one of the three major ways of doing encryption.
That can be applied in various kinds of public key cryptography and things like that.
So, the idea, you know, we had factoring large prime numbers, which was the RSA,
we had discrete logarithms, which is El Gamal, and then lately the elliptical curve.
Those were the three different methods that we have discussed.
So, this example of a discrete logarithm, because you're trying to find an integer solution of G to the power A times B mod P,
where G and P are known, but A and B are unknown.
Now, there are some special cases that are fairly easily solvable,
but at this point, there is no general solution to discrete logarithm problems that is feasible.
Another thing about Diffie-Hellman, you can use it with more than two people,
for instance, add Carol to the conversation, and then you'll wind up with G to the power A times B times C, Modulus P.
Generally speaking, if you follow the rules, Diffie-Hellman is considered secure against eavesdropping.
So, it doesn't matter who is watching your messages, you can communicate securely.
But there is a weakness.
One of the biggest problems with Diffie-Hellman is that there's no form of authentication.
So, can Alice really be certain she's 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 have to say.
Of course, if she is ever absent when they try and communicate, that would alert Alice and Bob that their channel had been compromised.
But this is a good example of why in practice public key cryptography, like RSA, is used to establish initial communication in most cases.
And that channel is then used to create the shared key, without worry about man in the middle attacks.
So, if you recall from some of our earlier discussions, we first noted this when we were talking about cryptography as applied to email,
and then with cryptography as applied to certificates, and then cryptography as applied to SSH, which is also certificates.
They're all basically the same kind of problem with the same kind of solution, the same math, et cetera, and we would always say you would establish open communication with the public key,
and then switch to a shared secret to continue the discussion.
And so now you can see why that's so important. It's not just that the symmetric encryption is more efficient, although it is,
but it's also the fact that there's no good way of avoiding man in the middle attacks when you're doing a Diffie helmet.
So, a broader source of possible weakness comes with solubility of the discrete algorithm problem.
It may not be feasible now. We may not have a general solution right now, but these things are constantly being researched.
And as we've said before, this is an arms race. Capabilities are being upgraded.
There are certain types of discrete logarithm problems that are now fairly easy to solve.
And this is one of those areas where capabilities only ever increase.
That is why Diffie helmet approaches are being modified to use elliptic curve algorithms, because elliptic curve is very efficient and much harder to brute force.
Still, Diffie helmet has an important role in cryptography, and particularly for something called forward secrecy, which is the problem you have if someone stores your encrypted messages in anticipation of future advances in decryption.
But that's a topic for another day. I think we've probably done enough, and I imagine one or two of you are scratching your heads going, what on earth did he just say?
Well, if you had any trouble following this, the link in the show notes. There will be a link in the show notes that will take you to my website, and you can see this is all written out all of the numbers and examples that I used, and that might make things a little bit easier for you.
But in any case, this is a hookah for hacker public radio. Thanks for listening to my little program, and as always, I want to remind you to support free software. Bye-bye.
You've been listening to Hacker Public Radio at Hacker Public Radio.org. We are a community podcast network that releases shows every weekday Monday through Friday.
Today's show, like all our shows, was contributed by an HBR listener like yourself. If you ever thought of recording a podcast, then click on our contributing to find out how easy it really is.
Hacker Public Radio was founded by the digital dog pound and the Infonomicon Computer Club, and is part of the binary revolution at binwreff.com.
If you have comments on today's show, please email the host directly, leave a comment on the website, or record a follow-up episode yourself. Unless otherwise status, today's show is released on the creative comments, attribution, share a life, 3.0 license.
You