Step by step conceptual implementation of AUTHENTICATED Diffie-Hellman?

Question

I'm already doing classic DH with pre-shared key in my setup, and it prevents people knowing the same password from eavesdropping on others' traffic. But it doesn't cover situations where a third party authenticates to the server, then masquerades as the server to an incoming client, performing an authentication and then forwarding the traffic to and from the server transparently to both parties, all the while it is able to read and modify it at will.

Wikipedia contains half an explanation in its DH article about how the authenticated/public key flavor goes, but it's confusing to follow step by step. From what I managed to understand, the private key is g^a%p=PUBKEY then for each one-way encrypted message, g^b=ENCRYPTED_SECRET is computed, and sent to the PUBKEY holder.

I do not understand however, what the PUBKEY holder is supposed to do with ENCRYPTED_SECRET upon receipt in order to retrieve b, if b is indeed what is supposed to even be retrieved. Nor what the formula for this should be, what I exponentiate to what etc.

A step by step would help. Thank you.

Answer 1

Both parties are pub-key holders, so let's call them A and B having their private keys $a$ and $b$.

DH conceptually goes (this is something you already may know):

• A: computes $g_a = g^a \pmod p$ and sends it to B
• B: computes $g_b = g^b \pmod p$ and sends it to A
• A: computes key $K = g_b^a \pmod p = g^{ab} \pmod p$
• B: computes key $K = g_a^b \pmod p = g^{ab} \pmod p$

and now there are several authentication schemes to validate they're really speaking to each other. You may check the X.1035 or SPKE, there are the complete step-by-step recommendations.

Basically I found 2 methods:

• A and B send each other hash of the salt, their public keys, shared password and the computed secret key
• DH parameters ($p$ or $g$) depend from the shared password

Answer 2

In the end I found the information I needed, thank you all for help. I'm leaving this here for future reference.

Key Generation:

generate a random number PRIVKEY as the private key

g ^ PRIVKEY % p = PUBKEY the public key

Public key-encrypted nonce:

generate random n as a nonce

PUB ^ n % p = shared secret (sender side)

g ^ n % p = PUBVAL public value, this is sent over a potentially insecure channel

Private key decryption of shared secret:

PUBVAL ^ PRIVKEY % p = shared secret (receiver side)

The shared secret can then be used as a symmetric encryption key to encrypt the rest of the session.

A third party who intercepts PUBVAL and is in possession of PUBKEY still cannot derive the shared secret without knowing n, which is never revealed. But someone who possesses PRIVKEY doesn't have this problem.

Key sizes:

p the safe prime modulo follows asymmetric key sizes(2048, 3072, 4096 bit...)

PRIVKEY, n randomly generated numbers must be double the expected size of the symmetric security(eg. 256 bit size numbers for 128 bits of security)