2
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • $\begingroup$ 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$? $\endgroup$
    – mikeazo
    Jan 31, 2018 at 14:05
  • $\begingroup$ 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. $\endgroup$
    – dusk
    Jan 31, 2018 at 14:32
  • $\begingroup$ 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. $\endgroup$
    – mikeazo
    Jan 31, 2018 at 14:36
  • 3
    $\begingroup$ 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. $\endgroup$
    – SEJPM
    Jan 31, 2018 at 15:17
  • 1
    $\begingroup$ @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. $\endgroup$
    – mikeazo
    Jan 31, 2018 at 15:59

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I may add the best current symmetric PAKE later (if I can clearly identify it). $\endgroup$
    – SEJPM
    Jul 24, 2018 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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