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.

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.

  • Indeed! RSA really is king at the moment, but are there really no decent unencumbered EC-based schemes? I should have said that the identities (certificates issued) are definitely EC ones. – Nicholas Wilson Jul 10 '14 at 14:20
  • tools.ietf.org/html/rfc6979 describes a way to to generate the troubling variable deterministically. I do not know if there's any implementation out there, though. – abaj Jul 10 '14 at 14:35
  • Thanks, that's very helpful -- it's certainly a big relief to know that the signature nonce can be generated in this way, although I'm still suspicious: if there's just a quarter of a bit of correlation between two k values then watching successive signatures yields an eventual leak of the key. Plus, in real-world use of DSA, this has lead to genuine exploits (eg Bitcoin on Android), so I'm glad that there are ways of using DSA without having to trust the platform RNG. – Nicholas Wilson Jul 10 '14 at 16:53
  • @user49555: at least libgcrypt implements RFC 6979 since version 1.6.0 (released on December 2013). – Tom Leek Jul 10 '14 at 17:03

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).

  • Re: assuming they already have a shared secret Z -- that's exactly what DH does! For example, in TLS, the popular cipher suite TLS_ECDH_ECDSA_WITH_AES_128_CBC_SHA performs Diffie-Hellman to obtain Z, then additionally the server sends the client a DSA signature using its EC key to verify that it possesses the key in the certificate. Setting up a shared secret isn't the hard part -- it's the identity verification setup I'm interested in, which is sometimes a built-in stage (like in ECMQV) but often a separate stage (eg any cipher suite which uses ECDH alongside RSA keys). – Nicholas Wilson Jul 10 '14 at 16:35
  • In particular, the DH Z in SSH and TLS suites is not authenticated - it's just a shared secret which is typically separately authenticated by use of an RSA or DSA signature. I'm not assuming in my construction that the DH Z is authenticated. – Nicholas Wilson Jul 10 '14 at 16:56

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.