What are the alternatives to ECDSA for an authentication protocol?

Question

In an authentication protocol, S has a public/private key pair known to C, and S and C have established a secure channel (for example, using DH or ECDH, or any other key exchange protocol). C wishes to determine whether the peer over this secure channel possesses the private key.

In ECDSA, the key pair is an elliptic curve key pair, and the signature algorithm uses the DSA scheme (DSS) with the elliptic curve. The DSA scheme is known to have some undesirable properties -- weaknesses in the RNG are a real concern, considering that an attacker can obtain a million signatures.

If authentication only is required, we don't need a fully-blown signature scheme (ie, the ability to sign arbitrary messages is not required). What alternative schemes could be used which avoid the scary property that re-use of the identification key in multiple signatures will eventually leak it?

One simple scheme follows:

1. C uses IES to encrypt a nonce N1, and sends this to S (this is the elliptic curve integrated encryption scheme).
2. S then sends HMAC(key=Z, N1) back to the C, where Z is a shared secret obtained via the key exchange phase (remember, we've already established a shared channel using DH or some other method).

This proves possession of the private key: the private key is required for S to have obtained N1 from EIS(N1). The server is not a decryption oracle -- it doesn't decrypt arbitrary messages on behalf of C, but rather replies with the HMAC of the decrypted value. Finally, because the shared secret Z was mixed in, which was jointly determined by C and S, the signature can't be used to perform a man in the middle attack: someone wishing to impersonate S to C is sent by C the encrypted N1, but can't forward it to S for signing, because the signature is tied to the channel's Z.

Question

1. Does my dead-simple scheme have a name? Is it weak? It appears to avoid the DSA problem where multiple signatures may eventually reveal the key, but I haven't done all the algebra to be sure!
2. What are the popular standard solutions to the problem? FHMQV is patented, sadly, but it's designed exactly for this situation, isn't it. I guess the popular solution appears to be ECDSA (used in TLS, SSH), which I'd hope to avoid.

Remarks

1. Menezes' article "elliptic curve signature schemes" in the "Encyclopedia of Cryptography and Security" lists DSA, Schnorr, Nyberg-Rueppel as the various known elliptic curve signature schemes. DSA is the one I don't like, and Nyberg-Rueppel apparently has exactly the same weakness as DSA (two signatures using nonces with any known bits in common leak private key information). Schnorr signatures look good, but they don't seem to be widely used.
2. Hugo Krawczyk's HCR (Hashed Challenge-Response, based on XCR, Exponential Challenge-Response) looks very promising too -- it's a beefed-up version of Schnorr that is supposed to be more robust. I think it's covered by Patent EP1847062B1 though, which expires around 2025 apparently.

Answer 1

In answer to question 2, you could use RSA instead for the signature algorithm. While people are moving to ECDSA due to it being faster, there's nothing inherently wrong with RSA still.

Answer 2

Though a weak RNG is a problem for ECDSA, this can be fixed in two ways:

1. By using a non-weak RNG (that's not that hard, on modern computers; it is cheap embedded systems who may have trouble obtaining a decent source of randomness).

2. By using derandomization, as described in RFC 6979. This is compatible with ECDSA (uses the same public and private key pairs; verifiers are unchanged) but removes the need for a random source (weak or strong) or any state.

---

It is unclear what your protocol is trying to achieve; I suspect it does not do what you actually want it to do. When considering an SSH-like situation, you want the client and server to establish a shared secret such that the client (respectively the server) has some reasonable guarantee that it talks to the genuine server (respectively the genuine client). In your protocol, you assume that client and server already obtained such a shared secret Z, with some guarantee that the Z was produced with a DH between client and server, not between client and attacker-impersonating-the-server. In other words, you solve the problem by assuming that it is already solved...

In all generality, authentication is about making sure that the peer in some protocol is really the owner of some specific secret value V. Let's take the point of view of the server. The server wants to know whether an alleged client really knows the V value. Details then depend on that V:

• If the secret value is known to the client only, not to the server, then we are in the realm of asymmetric cryptography. V must be the private part of a private/public key pair, and a signature is the right tool for that.

• If the secret value is known to both the client and the server, then this can be done with symmetric cryptography.

With an SSH connection:

• The server always has a public/private key pair; the server computes a signature that the client verifies. The client authenticates the server by virtue of validating that signature with regards to the known server public key (SSH clients remember server keys, in the .ssh/known_hosts file).

• The server may want to authenticate the client with a password. In that case, the password is a shared secret between client and server; or the server may store only a hashed version of the password. The client simply sends the password to the server, and it can do so safely because at that point, the client has already authenticated the server and can use the negotiated DH key to encrypt the data.

  If the server prefers key-based client authentication, then the client has a public/private key pair, the public key is known to the server (the .ssh/authorized_keys file), and the client computes a signature.

In SSL/TLS, the "remembering public keys" is replaced with X.509 certificates. The core concept remains the same, though, and signatures are used.

TLS also supports some less widely used key exchange protocols to be used when client and server want to authenticate each other from a shared secret, without using any public/private key pair at all; these are the PSK cipher suites, and SRP (the latter is more complex but much stronger when the shared secret has low entropy, i.e. is a password).