3
$\begingroup$

Is it safe to use ECDH for challenge-response authentication, with server key being ephemeral?

The goal is that server does not store sensitive data (hashes) and allow clients to use additional security if needed (for example generate and store their key in a smartcard and skip key derivation).

  • Client derives private key from the password, using a strong hash algorithm (similar to bitcoin address generators using passwords)
  • Server generates a key and sends its (ephemeral) public key and a challenge string
  • Client must reply with the challenge, encrypted with the shared key
  • Server checks if decrypting response yields the challenge

Assumptions

  • A secure channel is already established
  • Server has the client's public key stored
$\endgroup$
3
  • 3
    $\begingroup$ Search for AugPAKE (most famously SRP) which is a similar concept, but avoids exposing the password hash to guessing attacks. $\endgroup$ Jul 9, 2017 at 20:55
  • $\begingroup$ Doesnt PAKE require both parts knowing the password? Also, as I said the channel is assumed secure by other means (like TLS). This scheme is intended to make server not need to hold sensitive data. If the server's database ever gets leaked, the attacker would require to use both the curve and hash for bruteforce, which has a high cost for passwords that are not weak. $\endgroup$
    – iovoid
    Jul 10, 2017 at 2:05
  • $\begingroup$ Related: Is it safe to reuse ECDH asymmetric keys for authentication? $\endgroup$
    – e-sushi
    Sep 8, 2017 at 12:08

3 Answers 3

1
$\begingroup$

Client derives private key from the password, using a strong hash algorithm
Server has the client's public key stored

So the server has a hash of the password. This defeats your goal that the server wouldn't have a password hash. All you've done is making your own password hashing function.

A password hash is any value derived deterministically from the password (and a salt, unless you're doing it wrong). Adding a step of private-key-to-public-key calculation into the password hash calculation is just that: adding a step. It's not a particularly useful step: if it was, standard password hashing functions would do it. Since every private key maps to a different public key, it isn't a harmful step in itself, but it doesn't help with security.

Your description of the protocol is missing a step where the server has a salt stored (generated randomly when the password was set) and sends this to the client as part of the challenge. If you don't use a salt, your scheme is vulnerable to rainbow tables, which make cracking multiple passwords stored with the same hash algorithm much more efficient.

There is no way to avoid storing a password hash on the server. How else would the server know that the client knows the password? It needs to have enough information to distinguish the correct password from other inputs. And this is exactly the information that an attacker needs to carry out a brute force password search. The best you can do for password authentication is to make this brute force search as hard as possible. Your proposed scheme doesn't help with that.

If the client has a (strong, randomly generated, and hence impossible to memorize by a normal human) secret value in addition to the password, then it's possible to devise a scheme where the server cannot reconstruct the password even by brute force. (I will not venture to spell out such a scheme in this answer.)

$\endgroup$
0
$\begingroup$

Here’s a link that shows how to implement ECDH with long term public keys and ephemeral shared keys. You could just add this authentication after the TLS handshake as it’s own layer. Think about the openID protocol. You can publish the keys at a well-known-endpoint, it’s not necessary to wrap them in a certificate.

$\endgroup$
-2
$\begingroup$

First off, generating an asymmetric key pair is an expensive operation. As you might know, it is done once (usually while creating a certificate signing request) and used for multiple sessions. Web servers usually use it for a year (check the expiry date of say google.com's certificate)

Servers are typically designed to handle multiple requests from clients and one of the metrics of the quality of the server is to see how much it scales to burst client requests.

If you're talking about one asymmetric key pair per client, it's a huge ask, let alone one key pair per session. Apart from computation power, you need to consider the entropy concerns too. i.e., is my server capable of generating enough high quality randomness to cater all key pair generations?

Having said all this, let's assume you're infact using ephemeral assymetric key pairs. Thing is, you can use them for challenge-response verification as well! Which is what most of the standard protocols do. Once the certificates are exchanged and their signatures are verified, the proof of possession of private key is done using challenge response. To prove A has the right private key, B will encrypt a random string using A's public key and send it to A. A decrypts that using it's private key and sends back the random string in plain text which B verifies. Same thing is done with roles exchanged to prove B has the right private key of its key pair.

If you really want to do the authentication part using ECDH, you can't because

  1. ECDH has a random component in it hence cannot be mapped to a static password.
  2. Any two parties can derive a symmetric key using ECDH. There is no way to tell if you're exchanging keys with the right guy. The authenticity of the keyex parties must be ensured before the keyex is initiated.

Therefore, I would say No, ECDH will not serve your requirement of "server not holding the client's password but still is able to authenticate client".

$\endgroup$
14
  • 3
    $\begingroup$ Could you provide sources for your claims? You state "generating an asymmetric key pair is an expensive operation". Sure, this is true for RSA, but what about for other algorithms, like Ed25519? You also cite entropy concerns, stating that "one asymmetric key pair per client, it's a huge ask, let alone one key pair per session." Are you familiar with how TLS works? If a server cannot handle generating several random values per session, then TLS is also an impossibility. $\endgroup$
    – bkjvbx
    Jul 10, 2017 at 10:03
  • $\begingroup$ ECDH private keys can be derived from hashes for some curves (secp256k1). ECDH keygen can run at more than 200ops/s $\endgroup$
    – iovoid
    Jul 10, 2017 at 11:22
  • $\begingroup$ "Web servers usually use it for a year (check the expiry date of say google.com's certificate)" public key is not related to certificate expiry, same keypair can be reused as wanted. "ECDH has a random component in it hence cannot be mapped to a static password.", as I said, ECDH private key of client is derived from a hash. $\endgroup$
    – iovoid
    Jul 10, 2017 at 23:08
  • $\begingroup$ Hi, following are my responses: $\endgroup$ Jul 12, 2017 at 3:05
  • $\begingroup$ Regarding the entropy requirements, as per link, generating an ECDSA with p-256 curve will require ~(256+64 + (2*256)) = 832 bits (or 104 bytes) of entropy. For TLS, the server needs to generate "server random" and "server hello random" which amounts to 64 bytes. For generating ECDH, we need to generate 32 bytes of random data (used for the private component 'd' whose value is between 1 and 'n' which is the order of the curve. For p-256, n is of size 32.) $\endgroup$ Jul 12, 2017 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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