# Diffie-Hellman based password challenge response scheme

A very commonly used (examples: HTTP digest auth/CHAP/Kerberos) authentication scheme is something that looks like:

Setup.

• Client and server both know a password $p$.

Authentication.

• Server sends a random challenge $\alpha$.
• Client computes $r = \text{KDF}(p || \alpha)$ and sends $r$ to the server.
• Server computes $r' = \text{KDF}(p || \alpha)$ and checks $r' \overset{?}{=} r$.

This scheme is also described in other questions (example). Now this scheme has the disadvantage that the server needs to know the plaintext password. Could we make a public-key-based scheme for challenge response authentication?

For example, we could use elliptic curve arithmetic:

Setup.

• Client has a secret password $p$ (with reasonable entropy) and from this derives a key $k$ using a hash function.
• The client computes $[k]P = Q_k$ and the server will store this value as the user's public key.

Authentication.

• Server sends a random challenge $Q_\alpha = [\alpha]P$.
• Client computes $Q_s = [k]Q_\alpha$ and sends $Q_s$ to the server.
• The server computes $Q_s' = [\alpha]Q_k$ and checks $Q_s' \overset{?}{=} Q_s$.

Does this scheme work? Why would most systems use HMAC-based scheme instead?

• If $p$ has sufficient entropy and you can derive the key $k$ in such a way that recovering $p$ from $k$ is hard, why not just use $k$ in your original protocol (with the $KDF$) instead? Does your proposed elliptic curve variant provide any additional protections that are not provided when using $k$? – mikeazo Jan 31 '18 at 14:05
• Do you mean that the server stores a derived key from the user? In this case the server still needs to store a private value. If this value is breached, the attacker can authenticate as the user. In the second scheme, this is not the case. The server only stores a public value. – dsprenkels Jan 31 '18 at 14:32
• I guess I don't understand your use case. Typically a server stores a salted/hashed version of the password. When I try to authenticate I send the password. The server salts and hashes the password I send and compares with the saved version. If they match, I am in. An attacker stealing the salted/hashed version of the password cannot log in as me. – mikeazo Jan 31 '18 at 14:36
• You are aware that for practical applications you should use proper Password Authenticated Key Exchanges (PAKEs)? These will yield you a shared key iff the client has the password associated to some server-side verifier. – SEJPM Jan 31 '18 at 15:17
• @SEJPM, that is where I was going next. It has been a while since I have looked at things like SRP, but it seems very relevant here. – mikeazo Jan 31 '18 at 15:59

First off, what you are trying to construct here is called an augmented or asymmetric password-based key exchange (aPAKE). As for your concrete construction:

Does this scheme work?

Yes, it will be functionally correct.

Does it actually achieve the security guarantees of an aPAKE scheme? No, an attacker can look at the transcript, see $Q_s=[k]Q_a$ and knows both $Q_s$ and $Q_a$ and thus can just off-line brute-force the password.

The first (symmetric) scheme you mentioned suffers from the same problem.

Could we make a public-key-based scheme for challenge response authentication?

This is what aPAKE schemes do, the most notable protocols are:

• the Secure Remote Password Protocol (SRP), mostly because it was first to be standardized in RFC 2945.
• OPAQUE which is the current state-of-the-art when it comes to (simple) aPAKEs.
• If you also want to assume an auxilliary 2nd device for the user, OpTFA is the state-of-the-art.
• If the user "only" has a device capable of running an (EC)DH key agreement (like a smartcard), then PTR-PAKE is the best you can get.

Example implementations (in C) of OPAQUE and PTR-PAKE can be found in libsphinx.

• I may add the best current symmetric PAKE later (if I can clearly identify it). – SEJPM Jul 24 '18 at 11:17