Authenticated Diffie Hellman Key Exchange

Question

It appears that the textbook version of Diffie-Hellman is susceptible to man in the middle attack and the use of digital signatures could prevent this attack from occurring.

Digital signatures could be implemented during the Diffie-Hellman key exchange in the following way

1. Alice has a pair of public/private key (SKa,PKa).
2. Bob has a pair of public/private key(SKb,PKb).
3. Alice generates her secret key Ka uses her private key SKa to sign (g^Ka) to produce Signature s(m)
4. Alice uses Bob public key PKb to encrypt her secret key Ka.
5. Alice sends over encrypted Ka and s(m) over to Bob
6. Bob will use his private key SKb to decrypt encrypted Ka to get C and use Alice public key PKa on s(m) to get D
7. Bob authenticates by ensuring that the C == D

I have three questions with regard to this

1. Is this how authenticated diffie-hellman key exchange using digital signatures is normally done? If not, how is it normally done?
2. Why do we bother with this form of key exchange where the sender and receiver must send their keys to each other before using the combined key when we can just encrypt the key using the senders private key followed by the receiver public key and send it to the other party?
3. Are there any flaws with my implementation of authenticated Diffie-Hellman key exchange?

Answer 1

Your description is a bit confused and appears to be wrong. In particular, we see Alice computing here Diffie-Hellman half g^K_A and then proceed to send... her Diffie-Hellman secret K_A to Bob, which is not at all what she should do.

Plain Diffie-Hellman works the following way:

• Alice generates (randomly) her secret K_A and computes g^K_A.
• Bob generates (randomly) his secret K_B and computes g^K_B.
• Alice sends g^K_A to Bob.
• Bob sends g^K_B to Alice.
• Alice computes (g^K_B)^K_A, using her secret K_A and the value sent by Bob.
• Bob computes (g^K_A)^K_B, using his secret K_B and the value sent by Alice.

By the magic of mathematics, Alice and Bob ends up with the same value, which is the shared secret that they thereafter use for whatever cryptography they need to talk to each other.

For the authenticated variant, the same computations are done; but Alice and Bob also own asymmetric key pairs usable for digital signatures, and they use them: Alice signs whatever she sends to Bob, and Bob verifies that signature (using Alice's public key). Similarly, Bob signs what he sends to Alice, and Alice verifies that signature (using Bob's public key).

Note that a no point whatsoever does Alice send K_A (he "DH secret") to Bob in any form. Neither does Bob send K_B to Alice. And there is no encryption anywhere. You may encounter many tutorials that purport to explain digital signatures in terms of encryption (usually as "encryption with the private key"). These explanation are remnants of older times (the late 1970s, in fact, in the original Disco era) and are, in fact, plain wrong and very confusing. So don't think in those terms. Signatures are signatures, encryption is encryption.

---

Authenticated DH is what is done in, for instance, in SSL/TLS with the "DHE" cipher suites. It is also what happens in SSH (version 2).

There are two main reasons for using such an "ephemeral" Diffie-Hellman ("ephemeral" because Alice and Bob generate their DH secrets K_A and K_B on the fly):

• The "permanent" key pairs owned by Alice and Bob may be unfit for anything else than signatures. A source of confusion (again) is that there is not one algorithm called RSA; there are at least two, one for encryption and one for signatures, and they appear to be able to use the same kind of key pairs. However, even if a RSA key pair can be used both for encryption and signatures, there are good reasons not to do so. There are also other signature algorithms (e.g. ECDSA) whose keys cannot be used (at least not easily) for encryption.

• Using ephemeral DH secrets provides Forward Secrecy, which is good. Namely, the permanent keys of Alice and Bob must be stored somewhere; so they could, potentially, be stolen afterwards. With simple RSA-based key exchange (no DH, Alice encrypts a random session key with Bob's public key and Bob decrypts it), the ulterior key thief could use it to decrypt a past session. With the DH and the signatures, this issue does not occur; even if Alice's and Bob's signature private keys are revealed afterwards, their past communications cannot be decrypted. The whole concept of forward secrecy revolves around the idea that the "DH secrets", being generated on-the-fly, kept in RAM only, and destroyed immediately after completion of the DH key exchange, are immune to ulterior theft.