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:
- C uses IES to encrypt a nonce
N1, and sends this to S (this is the elliptic curve integrated encryption scheme).
- S then sends
HMAC(key=Z, N1)back to the C, where
Zis 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
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
- 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!
- 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.
- 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.
- 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.