Zero Knowledge Password Proof

Question

I'm working on implementing a cryptographic system and I'm trying to understand the Zero Knowledge Password Proof concept. So here's some background:

To generate a secret key I am:

• Doing an ECDH key exchange and generating 2 secret keys. One key is to encrypt messages and the other key is to HMAC sign the data. To derive the secret keys I am sending the username from the client along with the public keys and using the password on the client and server to derive the encryption keys by running the ECDH keys through a KDF function so that if the keys were retrieved the passwords could not be known.
• Once I have these secret keys I want to use them to encrypt a message that does not include the password to send over to the server to authenticate that the client does indeed have the correct password.

I want to make sure that I implement this properly and I know that if I encrypt something that is preknown to the server that could be insecure because of some attacks that involve knowing the plaintext as well as the cipher. Do I need to just create a random string to encrypt? Any thoughts? Thanks!

Answer 1

I don't believe your protocol meets the standard definition of Zero Knowledge Proof, as a cheating verifier can learn more information about the secret than allowed. In particular, suppose we have a cheating verifier (server) that has a list of one million potential passwords. Then, he can run your protocol with a client that knows the password, run the KDF with all one million passwords, and see which one allows him to decrypt the message. This allows the cheating verifier to check his entire dictionary of passwords at once.

If you are looking for a password verification protocol that avoids such weaknesses, I suggest you look at either the SRP protocol or the EKE protocol; both were designed specifically to avoid such weaknesses.

Now, as for your question about encrypting known plaintext, well, that's not actually a concern. Strong encryption method (say, AES with a good mode) are designed to be strong against known (or even chosen) plaintexts. Now, in your case, since you're just verifying knowledge of the shared key, you don't even need to encrypt anything; generating an HMAC of some standard data would be sufficient (or, at least, it would be if your protocol didn't have the above problem).

Answer 2

There's one important difference about SRP and EKE that wasn't clearly explained above :

• SRP is an augmented password authenticated key exchange
• EKE (at least the initial version that RFC 6124 uses) is not

This means that with EKE as described in RFC 6124 both the server and the client must know the password.
Whereas with SRP the server only knows a verifier and does not have direct access to the password.

However the verifier used with SRP is sensible to brute force attacks on the password : If the verifiers are stolen, attackers will be able to recover many password by testing each verifier against dictionary values. There's no way to avoid that and still be able to do the cryptographic calculations needed.
So the advantage may not be as big as it seems.

It's likely that RFC6124 uses only the standard and not the augmented version of EKE because at the time it was issued the augmented version was still protected by a patent (which has expired in August 2013).

Answer 3

If you are going to use SRP to authenticate your users, you may be interested in the Javascript implementation of SRP v.6 included in the Javascript Crypto Library, AGPL licensed.

Crypto protocols could be tricky to implement correctly, luckily SRP has been already implemented in many languages and environments. Here is a list from the official Standord website