Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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!

share|improve this question
add comment

3 Answers

up vote 5 down vote accepted

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).

share|improve this answer
    
Thanks poncho, I appreciate this direction. EKE looks like good protocol to use. –  hobeau Dec 16 '11 at 20:26
    
@hobeau: EKE is a good protocol, but implementing it correctly is trickier than it looks. You might want to look at datatracker.ietf.org/doc/rfc6124 for some implementation suggestions. –  poncho Dec 16 '11 at 20:40
    
I've been researching it a bit and it looks like the patent on EKE has expired? Another good reason to use it? –  hobeau Dec 16 '11 at 20:51
    
Yes; if it hadn't expired, I wouldn't have mentioned it. –  poncho Dec 16 '11 at 20:59
    
Awesome! I have a couple more questions about it but I think I should start a new question. Thank you so much for your help! –  hobeau Dec 16 '11 at 21:17
add comment

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

share|improve this answer
add comment

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).

share|improve this answer
    
I actually can be more precise about augmented EKE. It's patent US Patent 5,440,635 will only expire in August 2013. –  jmd Jul 13 '12 at 17:01
    
It is expired now :) –  Michael J. Gray Mar 6 at 2:46
    
yes, so I updated the answer. –  jmd Mar 6 at 12:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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