Using plain Diffe-Hellman for server authentication with known public key

Question

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.

Examples:

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) \}$

Answer 1

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.