Challenge - Response protocol - how to incorporate client randomness

Question

I am designing a challenge-response protocol to enable a client to authenticate to a server. The client has a private key, and a certificate (issued by a trusted CA). At this point in the protocol, the server knows who the client claims to be, but wants to prove it. My first attempt was:

$C ← S : r_S$

$C → S : S_C (r_S)$

where:

• $r_S$ is a random challenge generated by $S$ (the server).
• $S_C(r_S)$ is a signature of the challenge, signed with $C$'s (the Client's) private key.

The problem with that, is that the private-key + certificate may be used for other purposes than identifying the client to the server. (For example, authorizing invoice payments.) A compromised server could send the client the hash of an invoice payment authorization, and get back the necessary signature to authorize it.

Next attempt:

$C ← S : r_S$

$C → S : r_C, S_C (H(r_S | r_C))$

where:

• $r_C$ is a random nonce generated by $C$.
• H is a suitable cryptographic hash function
• other terms are as above

Is this secure? Specifically, can a compromised server use such a scheme to calculate $S_C(V)$ for some predetermined value $V$?

In particular,

• would it be safer to put $r_C$ first in the concatenation?
• and is simple concatenation good enough, or do I need to do something like calculate $\text{HMAC}_K(r_S|r_C)$ using a hardcoded key $K$ or even $\text{HMAC}_{r_C}(r_S)$ (using $r_C$ as the key to the HMAC)?

Answer 1

1. Using the same certificate/private key for different purposes should not be allowed whenever possible.
2. The answer to your question firstly relies on the security of the signature scheme you use. If the signature scheme is unforgeable, then you should be largely fine. Unforgeability means the malicious server who can chosen any messages and get the corresponding signatures but still cannot forge a signature of a message which it has not queried. The server gets only signatures of $H(r_s||r_c)$, but cannot generate other signatures. Then the question is how likely $H(r_s||r_c) =m$ where $m$ is something meaningful and the server wants the signature of it. In this case, unforgeability is not enough because the server simply can reuse the signature without needing to forge one. If $H$ you use is collision resistance and $r_c$ is long enough, then $H(r_s||r_c)$ should be a uniformly random value. It is unlikely $H(r_s||r_c)$ is meaningful and the probability of this case is negligible.
3. The order does not matter and MAC is not needed. Note here the message gets signed is $H(r_s||r_c)$ (this hash value will be hashed by the hash function used by the signature scheme), not $r_s||r_c$.