# Are ZKPPs possible with server-side hashed passwords?

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?

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.

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?

• 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. – Maarten Bodewes May 3 '14 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 '14 at 17:50
• No, that's just a badly constructed PBKDF2 (which you should use to "hash" your password if you take that route). – Maarten Bodewes May 4 '14 at 11:45