Other considerations aside, is it possible to use DH with an established public key (together with fixed g, p, q) to safely authenticate a server instead of using some signing algorithm?

In other words, we will replace $SIG_S(Data)$ in some protocol with this scheme. The steps described below can be merged with whatever protocol is used, so it doesn't need to add more steps.

Client $C$ knows $g$, $p$, $q$ and $g^s$.

  1. $C \rightarrow S : \{ g^c \} $
  2. Server generates a random value $N_S$.
  3. $K \leftarrow KDF(N_S, g^{cs})$
  4. $S \rightarrow C : \{ N_S, HMAC_K(Data) \}$ where $Data$ is the relevant data signed in the protocol we're modifying.
  5. $C$ constructs $K$ and verifies that the HMAC calculation matches.

Assume that none of $K$, $N_S$, $g^s$ or $g^c$ is ever recycled for any other use (such as key generation).

What I wonder is if this would be an acceptable replacement for signing with DSA/RSA/etc to prove identity in this particular setup.


Plain STS with server authentication only

  1. $C \rightarrow S: \{ g^x$ }
  2. $S \rightarrow C: \{ g^y, S, \{ SIG_S(g^x, g^y) \}_{K_s} \}$

Plain STS modified

  1. $C \rightarrow S: \{ g^x, g^c \}$
  2. $S \rightarrow C: \{ g^y, S, \{ N_S, HMAC_K(g^x, g^y) \}_{K_s} \}$

Plain SIGMA with server authentication only

  1. $C \rightarrow S: \{ g^x$ }
  2. $S \rightarrow C: \{ g^y, S, SIG_S(g^x, g^y), MAC_{K_m}(S) \}$

Plain SIGMA modified

  1. $C \rightarrow S: \{ g^x, g^c \}$
  2. $S \rightarrow C: \{ g^y, S, N_S, HMAC_K(g^x, g^y), MAC_{K_m}(S) \}$
  • $\begingroup$ Client $C$ is different from the $C$ in $g^C$, correct? $\endgroup$
    – mikeazo
    Jul 1 '13 at 20:12
  • $\begingroup$ Do you mean $\:HMAC_K(N_S-1)\:$? $\;\;$ $\endgroup$
    – user991
    Jul 1 '13 at 20:16
  • $\begingroup$ Even if that is the case, the OP's idea runs into very important subtleties, such as facing an analogue of CCA2 attacks as described in my answer, and revealing an HMAC value, which means that $N_S$ must be chosen so that it will never be HMACed in any other context. $\:$ $\endgroup$
    – user991
    Jul 1 '13 at 20:17
  • $\begingroup$ @mikeazo Yes. That was clumsy of me. $\endgroup$
    – Nuoji
    Jul 1 '13 at 20:25
  • $\begingroup$ @RickyDemer I've read that answer (regarding the CCA2 attack) but I'm still not sure if I understand it. In this case, $K$, $g^{s}$, $g^{cs}$ and $N_{s}$ are only ever used for the authentication. There is no relation to any DH keys that are used for key exchange etc. C must also be understood to never reuse $g^{c}$, as this is basically the client's "challenge" to server. How do you mean that $N_{s}$ might be HMACed in other contexts? $\endgroup$
    – Nuoji
    Jul 1 '13 at 20:37

An adversary can (repeatedly) submit $h$ as $g^c$ to get a random $N_s$ such that the adversary will
be able to test, with heuristically overwhelming accuracy, whether or not $\: \operatorname{KDF}(N_s,h^s) = x \;$.
An adversary could also attempt to learn something more about what session key the
server obtained, by sending an alleged ciphertext to the server after the key agreement.
(In particular, an adversary could do those things after seeing the client's actual value of $g^c$.)

It would be tricky to show security against such an attack without also showing
security against the case where, for each $h$ value, the adversary will learn
$\langle N_s,\operatorname{KDF}(N_s,h^s)\rangle\:$ for a random $N_s$ (chosen after the adversary chose $h$).
Such a security result would be somewhat analogous to CCA2 security; the analogy would be better
if $N_s$ was the same each time. $\;\;$ Unlike when I previously addressed a similar construction, I am now convinced that this will hold under $\:$KEA1 + KDF-is-a-random-oracle + computational-diffie-hellman$\:$ .
Under those three assumptions, the key agreement will be secure against an adversary
that can choose the server nonces $N_s$, including the ability to cause them to repeat.

The four signing algorithms that you might prefer over the above are BLS,BB,ECDSA.
(That's four because the middle one gives a variant that does use a random oracle.)

However, there are potential efficiency improvements that can be
obtained for only a known and very minor decrease in security.
In particular, in three of your four examples, it will only decrease security against an
active adversary that nonetheless does not have reliable communications with both honest parties.

For the first example and the last two examples, the encryption or MAC with $K_s$ or $K_m$ respectively
will defend against an adversary that [can modify a message in transit but will later
be unable to communicate with either $C$ or $S\hspace{.02 in}$] carrying out a "weak misbinding".
(I use the term "weak" because that is something an adversary with full control over
the communiations channel can necessarily do, no matter what protocol is used.)

Furthermore, for the first example, the encryption won't necessarily
succeed at that goal, although I suspect that it heuristically should.

For STSsao, encrypting the signature will (also) stop a passive eavesdropper
from being able to show that the server carried out a key agreement.

Those are the only reasons to use $K_s$ and $K_m$.
If one declines to use the relevant key, then one obviously should also not derive that key.

  • $\begingroup$ For STSsao, the main reason for encrypting the signature is to show that the signature did indeed come from S. Otherwise an adversary could insert their own credentials e.g. assuming no encryption an adversary could replace the server response with $\{ g^y, E, SIG_E(g^x, g^y \}$. In the SIGMA paper, they point out that using encryption is weak for verification, and thus removing the encryption and replacing it with a $MAC(S)_{K_s}$. $\endgroup$
    – Nuoji
    Jul 6 '13 at 10:17
  • $\begingroup$ An adversary who inserted their own credentials could just choose their own $g^y$ too. $\hspace{1.28 in}$ (Although I might be missing something here.) $\;\;\;$ $\endgroup$
    – user991
    Jul 6 '13 at 10:33
  • $\begingroup$ After inserting the fake authentication, the adversary can then allow the server-client protocol to continue running. Depending on the later protocol, this may or may not be an attack vector. $\endgroup$
    – Nuoji
    Jul 6 '13 at 13:58
  • $\begingroup$ Since the adversary could ordinarily instead just connect to $S$ and then run a "MitM", your suggestion would only make a difference if the adversary loses its connection to $C$ or $S$. $\:$ $\endgroup$
    – user991
    Jul 6 '13 at 20:56

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.