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.

A basic ZKPP (Zero Knowledge Password Proof) is based on the server being able to challenge the client, and the client can then prove it knows the password (in such a way that is verifiable to the server) without transmitting the password itself.

However, in order for the server to issue the challenge and verify the response, it seems like the server would need to have the password in plaintext. Anybody gaining access to the server would be able to simply retrieve the password.

Is it possible to create a ZKPP such that the server only maintains a hashed version of the password, and yet is still able to issue the challenge and verification?

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

Short answer: YES. (Though see the note on "hashed" below.)


Intro

The remote authentication protocols where server does not know the plaintext password are generally known as augmented password authenticated key agreement (PAKE). You can see this wikipedia article for details of PAKE algorithms (augmented and non-augmented). You may find this reference useful to find out more about the common protocols.


Not hash

Usual symmetric key cryptography is not sufficient for creating augmented PAKE mechanisms. Therefore, in augmented PAKE mechanisms (as far as I know them) it is not sufficient for the server to store hash of password. They mechanisms are based on operations commonly used in public-key cryptography (such as Finite Field Cryptography) and thus, the material stored by server is commonly something akin to a public key instead of hash. (Functionally this can be considered to be similar, but the storage space consumed per user is more than traditional password hashes require.)

The augmented PAKE ZKPP algorithms include e.g. SPEKE, Augmented-EKE, and SRP.

share|improve this answer
add comment

I don't know how it's done in practice, but here's a theoretical perspective:

  • Have an OWF Family, say modular exponentiation.
  • For a password $x$ store $g^x$ on the server.
  • Run the following ZKPP:

    1. server chooses a random $y ∈ Z_p^*$ and computes $g^y , (g^x)^y$ and send $g^y$ to the client
    2. client computes $t = (g^y)^x$ and sends it back to server
    3. server check $t \stackrel{?}{=} (g^x)^y $

Cute, right?

share|improve this answer
    
I guess that you can still brute force x by calculating $g^x'$ until you have a match. In that sense the protocol is not that different from ones that store a hashed value I suppose. –  owlstead May 3 at 17:02
    
well, not really, suppose you use a PRNG to map an ordinary password (as seed) to a 128 bit string, and use that as $x$.. now brute forcing $x$ is really hard.. :) –  Subhayan May 3 at 17:50
    
No, that's just a badly constructed PBKDF2 (which you should use to "hash" your password if you take that route). –  owlstead May 4 at 11:45
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.