Digital signatures in SSL/TLS-like protocols The TLS protocol includes an optional Server Key Exchange message that is signed by the server. It seems to me that this message is digitally signed only to prove to the client that the message originated from the server. 

The general purpose of a Digital Signature is to provide a proof of origin that can be verified by anyone at any time, without any prior communication with the signer. Providing such a proof to the client regarding the origin of the Server Key Exchange message is overkill, in the sense that it might require the client and server to implement Digital Signature generation and verification algorithms that might be redundant.

Wouldn't the following alternative provide a similar proof, and in addition be reducible to the CDH problem?

Presume the client $C$ and server $S$ share a set of parameters defining a group $G$, suitable for Diffie Hellman, and that $C$ already has the public key $y \equiv g^x \in G$ of the server.

$C: $ Generates random $a,v$ and $A \equiv g^a$ and $V \equiv g^v$ and sends $A,V$.

$S: $ Generates a random $u$ and $U \equiv g^u$, calculates $premasterkey \equiv V^u$ and $k \equiv A^x$ and $H = HMAC(k,U)$ and sends $U,H$.

$C: $ Calculates $k' \equiv y^a$ and verifies that $HMAC(k',U) = H$. If OK, calculates $premasterkey' \equiv U^v$; otherwise aborts.

(Note: The random values of the Hello messages as well as the Finished messages should be added for completeness.)

The above protocol should require one less modular exponentiation calculation client side compared to the DHE_DSS cipher suites defined in TLS, would only require the implementation of the DH algorithm for $G$, but would on the other hand not allow the server to precalculate the DSA $r$ values.

Is there any other reason to use a digital signature in the Server Key Exchange message, than the order of the protocol steps being put there because it wouldn't matter much for DHE_RSA how it is done (digital signature in Server Key Exchange or an extra key transport message sent by the client earlier)?
So what you are doing here are two Diffie-Hellman key exchanges in parallel – one with the server's static Diffie-Hellman key pair $(x,y)$ and the client's ephemeral key pair $(a,A)$ to calculate $k = k'$, and one with completely ephemeral keys to calculate the actual pre_master_secret. $k$ is only used as a MAC key to authenticate the server's exchange message.


  Presume the client $C$ and server $S$ share a set of parameters defining
  a group $G$, suitable for Diffie Hellman, and that $C$ already has the
  public key $y≡g^x∈G$ of the server.


This second condition is not realistic in many circumstances – i.e. not for the normal WWW usage, where you often want to connect to a server you don't know beforehand.

In this case we would then use the same way as now – deliver the server's public key $y$ together with a certificate (chain) which proves that the key belongs actually to the server we want to connect to.
To check these certificates, the client would need to implement a signature verification algorithm anyways. The existing DH_DSS and DH_RSS key exchange types work just this way, by the way, for their static Diffie-Hellman key (but there is just one exchange, not two).

Then, how could we fit this into the TLS handshake protocol?
We have these messages sent by the participants:


  Client                                               Server

  ClientHello                  --------&gt;
                                                  ServerHello
                                                 Certificate*
                                           ServerKeyExchange*
                                          CertificateRequest*
                               &lt;--------      ServerHelloDone
  Certificate*
  ClientKeyExchange
  CertificateVerify*
  [ChangeCipherSpec]
  Finished                     --------&gt;
                                           [ChangeCipherSpec]
                               &lt;--------             Finished
  Application Data             &lt;-------&gt;     Application Data



The ClientHello message doesn't really have space for the messages $A$ and $V$ to be sent – even less since at this point the cipher suite isn't even selected.
We could put something in the Extensions part, but I think this is not what they were made for.

The server's next bunch of messages has the selection of the Cipher Suite (including the key exchange protocol) in the ServerHello, so from here one the server can send related messages. So here we would send the server's static public DH key $y$ in the Certificate message (inside a certificate). 

The client would then send in its ClientKeyExchange its two public keys $A$ and $V$.

We now see the problem: There is no more place for the next message from the server where he would send $U$ and $H$, since the Finished messages are more or less only a MAC of the handshake messages with the master secret as a key, and the client's Finished is even sent before the server one's (and already encrypted with the negotiated keys).

But if we look again more detailed, we see that actually $U$ is not depending on anything what the client sent us, so the server can send it already in the first step, in the ServerKeyExchange message, just after $y$ and its certificate.

Sending $H$ (the MAC for $U$ using $k$ as a key) is not really necessary, as the Finished message from the server side has a similar function. What would be necessary instead would be to incorporate $k$ (i.e. the server's certified DH key pair) somehow into the pre_master_secret. Simple concatenation of $V^u = U^v$ and $k = k'$ should do here (the master secret is then derived using a PRF, including the random values from the Hello messages).

So the final key exchange protocol would look like this (omitting the stuff which is not relevant for the actual key exchange, like ClientHello, ServerHello, ServerHelloDone):


$S$:

send $y = g^x$ (with certificates) in Certificate,
send $U = g^u$ in ServerKeyExchange.

$C$:

check certificates for $y$,
send $A = g^a$, $V = g^v$ in ClientKeyExchange,
calculate $P = y^a||U^v$, $M = PRF(P, …)$ (this is the master secret),
use $M$ to derive the encryption/authentication keys,
switch on encryption (ChangeCipherSpec),
send $F_C = PRF(M, C, …)$ in Finished.

$S$:

calculate $P' = A^x||V^u$, $M' = PRF(P, …)$, $F_C' = PRF(M', C, …)$,
check $F_C \stackrel{?}= F_C'$,
use $M$ to derive the encryption/authentication keys,
switch on encryption (ChangeCipherSpec),
send $F_S' = PRF(M', S, …)$ in Finished.

$C$:

calculate $F_S = PRF(M, S, …)$
check $F_S \stackrel?= F_S'$.
Start sending application data.



This actually is a hybrid between the DH_anon and the DH_* key exchange types. And if the server's public key is already known to the client, we can omit the Certificate message and/or the certificate checking.


  Is there any other reason to use a digital signature in the
  Server Key Exchange message, than the order of the protocol
  steps being put there because it wouldn't matter much for
  DHE_RSA how it is done (digital signature in Server Key Exchange
  or an extra key transport message sent by the client earlier)?


The DHE_RSA and DHE_DSS key exchange protocol needs a signature in the Server Key Exchange message, since there is no other way for the client to verify that the message (and the public DH key) actually comes from the right server. In the DH_RSA and DH_DSS key exchange protocols, instead the (static) public key is contained in the server's certificate (which itself also contains a signature, but usually one created long before).

In our new protocol (i.e. my variant of your protocol), we don't need a signature, and still succeeded to fit it into the TLS handshake order.