Validity of authentication scheme?

Question

Here's an authentication scheme I had in mind that combines the simplicity of HTTP Digest Authentication and the security of real crypto primitives. I have in mind the user-level authentication, ie login/password, not the TLS level.

I'd like to see if anything can go wrong with such a scheme:

Registration

• User chooses password $p$
• User generates salt $s$
• User generates key material $m=KDF(s, p)$
• User generates assymetric authentication keypair, say DSA, using $m$ as the "random" source, where randomness comes from the salt: $priv/pub$
• User sends server $s$ and $pub$ as authentication material

Login

• Server generates challenge $c$
• Server sends challenge $c$ and salt $s$ to client
• Client re-generates the private/public keypair with $s$ and $p$ and signs the challenge with the signing key
• Client sends the signed challenge, server verifies with $pub$

This scheme has some advantages over other methods of authentication:

• Actual password never leaves the client
• User doesn't have to generate and keep a certificate, a password is enough
• Instead of depending on the password only, the $priv/pub$ keypair also depends on a salt so that 2 users with the same passwords don't accidentally share anything

I guess the most important thing to consider here is whether the salt generation is "random enough" to accommodate even the worst case (everyone has the same password)

Would that scheme be sound to implement ? Are there any flaws that would make it foolish ?

Answer 1

Would that scheme be sound to implement ? Are there any flaws that would make it foolish ?

I believe it's sound.

Note that SRP is a proven authentication protocol that has similar security characteristics. It has more round-trips, though.

I guess the most important thing to consider here is whether the salt generation is "random enough" to accommodate even the worst case (everyone has the same password)

A 256-bit random number is a good salt. It will never collide with another 256-bit random number anywhere, unless your RNG is broken. But a random salt is not enough.

If an attacker ever sees a signed challenge or gets the public key from the database, they can brute force the password that generates a matching key-pair. Therefore, the KDF should be a strong password based KDF, e.g. PBKDF2 with a high iteration count, or perhaps scrypt.

---

I used something similar in a (non-public) project. There the salt was generated by the server (because I wasn't sure clients had entropy), so it could even check that it didn't collide with any current salts. I used Ed25519 as the public key system; key generation from a seed is trivial for it.