3

Without using Private and Public keypairs, i do not understand how Diffie-Hellman is able to generate a secret key between two parties on the internet without passing something between that could be sniffed. There is a term for this that comes from Generals sending messages through hostile territory. I do not understand the math or logic behind DH and just can not see how it is possible. Someday i will spend another week or two going over the math, but until i can verify, i cannot trust. Further why use it when public private key pairs can be used to establish a shared session key with much less risk?

On the other hand, the uneducated masses historically sling pitchforks into progress. Explain it to me like i am 5, how can DH provide a known secret to two parties over an unencrypted connection without it being intercepted via MITM?

Changed title from: "When a public-private keypair is already in place, why is Diffie-Hellman used at all?"

6

Here's Diffie-Hellman for a student - a five year old does not understand logarithms ;-)

DH uses two ideas:

  • exponentation is fast (2 to the power 3 equals 8) but the reverse process (an exact logarithm) is very time-consuming to do. In reality we take large numbers, but for the sake of explanation small numbers here.
  • exponentation is commutative, i.e. 2 to the power 3 to the power 4 is the same as 2 to the power 4 to the power 3

Say that we want to communicate. We agree upon the base number A that we're going to raise to a certain power. And that doesn't have to be private. We just send A to each other.

Now I choose a big random number for my B. You choose, separately, your own big random number, which we'll call your B. And we both raise this agreed-upon number to that big power. Now, we send that intermediate result to each other. And now I take your intermediate result and raise that to my big power. You take my intermediate result and raise that to your big power. We both end up with the same answer.

A MITM sees A and both of our intermediate results going by, but he can't do the reverse process in reasonable time.

He can't figure out what our powers were that we made up. So we end up being able to choose random numbers, use those to raise a common value to that power, exchange those results, do it again, and we both end up with exactly the same value, which we can then use as a key.

In reality, there are some other requirements to A other than being big (e.g. it has to be prime).

Credit: Answer based on the transcipt of Security Now Episode 34

|improve this answer|||||
6

Diffie-Hellman is a key exchange algorithm. The good question to ask is: exchanging a key, yes, but with whom ?

From a network point of view, you "see" other people only through the packets they send to you; and since everybody can buy the same kind of PC, everybody can send the same packets -- except that some people/system may know some values that other do not. In cryptography, knowledge is power, meaning that you are what you know. If you begin to exchange data with Alice, you know you are talking to Alice and not to Bob because Alice can send some message to you which could have been computed only by someone knowing some given value, and you somehow know that there is someone called "Alice" who knows that value, and someone else called "Bob" who does not.

If, in your model, you don't at least define that there are several possible interlocutors with distinct knowledge, then the notion of "man-in-the-middle" does not even make sense, because all other people, in that model, are identical. If you want to talk about man-in-the-middle attack and how to avoid them, then you must first define who you want to be talking to, and that entails specifying what that system/person knows, that the attacker does not.

In short words: MitM is a special case of impersonation (a double-impersonation, even), where an attacker assumes the identity of somebody else. So you need a notion of "identity" before beginning to discuss MitM attacks.


Now suppose that you have defined a notion of identity. E.g. you are a Web browser and you are trying to reach a URL https://www.example.com/foobar.html. Then the notion of identity is "whoever controls the www.example.com server, as registered in the DNS".

Diffie-Hellman is a key exchange algorithm. This means that it does not include, per se, any kind of authentication. This does not mean that DH is useless; only that it is unlikely to provide alone the entirety of the security feature that you seek to obtain. In practice, several cryptographic algorithms are assembled in a protocol such as SSL/TLS.

Back to our example, Diffie-Hellman is indeed widely used in SSL/TLS, with the "DHE" cipher suites. The whole tower of cryptography looks like this:

  • The server has a public/private key pair fit for signatures (RSA, DSA, ECDSA...).
  • The server generates its half of the DH key exchange, then signs it (with its signature private key), and sends that to the client.
  • The server also sends its signature public key to the client, as a certificate issued by some CA.
  • The client validates the certificate (because the client already knows and trusts the CA) and thus learns the server's public key.
  • The client verifies that the server's certificate contains the expected server name (here: www.example.com).
  • The client verifies the signature on the half-DH sent by the server, using the server's public key.
  • The client computes its own half-DH and sends it to the server.
  • The client and the server complete the DH computation and obtain a shared secret, which is then expanded into symmetric keys for encrypting all the data.

The notion of identity used by the client is that a server owner cannot obtain a valid certificates from a trusted CA unless he effectively controls the relevant domain. So, from the point of view of the client, the "genuine www.example.com server" is "whoever knows a private key corresponding to a public key in a certificate from a trusted CA and containing the www.example.com name". The knowledge of the private key is what makes the server "the right one". The CA links that key (the public key, specifically) to the DNS name.

What protects against MitM here is that the man-in-the-middle does not know the private key (he could generate private keys of his own, but they would not match the public key in the certificate). The signature is the mechanism by which this protection is enacted. That's not Diffie-Hellman which provides that protection. On the other hand, the signature does not result in a shared secret: that is the job of DH.


Summary: you want to obtain a shared secret with some specific server, so that you may encrypt gigabytes of data to be sent to that server. This is a two-parts job: you want a shared secret, but it also has to be with some specific server. DH does the "shared secret" part. You need something else for the other part, e.g. some signature algorithm. This is what happens in SSL or SSH.

|improve this answer|||||
2

Diffie-Hellman on its own does not provide any authentication.

It is true that if two parties agree on a key with DH, third parties that are simply sniffing the traffic are unable to find out the exchanged secret key.

However, DH can be attacked by an active MITM that creates two key exchanges with the same public parameters. One from the client to the MITM and one from the MITM to the server. The MITM fools both the client and the server in this case into thinking that they are talking with eachother.

When servers use DH or its elliptic curve variant, they tend to use it ephemerally while the authentication is provided by RSA / (EC)DSA and the private key infrastructure. (usually X509 certificates) The reason for the ephemeral (EC)DH here is that it provides forward secrecy, which means that if the private key of the server gets stolen at one point in the future, sessions that have occurred in the past (and which have been logged by a sniffing party) cannot be decrypted retrospectively.

EDIT: I forgot to mention the use of fixed DH. In this case, the public parameters as well as a key that is derived from the server's private DH key are in the certificate. In this case the server's private DH key can't be derived from the public parameters nor the public key and with that the certificate provides authentication. (The server is the only one that knows the private key).

That being said, I haven't seen any fixed DH certificates in the wild. In the most cases it's used ephemerally for forward secrecy as mentioned above.

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.