2

With relation to the necessity of a verifier being transmitted from the client to the server prior to any handshake steps, I was wondering how this is supposed to happen securely? To me this seems like a user registration before using the system, but doesn't that defeat the idea of zero-knowledge password proof?

I'm having trouble understanding how you are supposed to keep the veifier a non-public variable when it's required to be sent from the client to the server in the first place. Would an initial ping to the server followed by a request for communication suffice? (But that doesn't really keep the verifier a secret...)

2 Answers 2

3

First, there is no zero-knowledge proof for a password. A ZK proof is about the following setup:

  • There is a publicly known hard problem.
  • Entity P (let's call him Piotr) knows a solution to the hard problem.
  • Piotr wants to convince entity V (Victor) that he knows a solution, but without revealing it to Victor, or to anybody spying on the connection, and in such a way that the full transcript of the protocol would not be, by itself, a convincing proof of Piotr's knowledge (Victor is convinced because he took part in the protocol, but a phony transcript could be made and an outsider cannot be as convinced as Victor unless he trusts Victor for having run the protocol truthfully). That's the "zero-knowledge" part.

The trouble with passwords is that they are susceptible to exhaustive search -- by virtue of being remembered by average humans, passwords must fit in a relatively small space and it is possible to find a password with good probability of success by enumerating potential passwords. That's a dictionary attack. A public known problem to which the password would be solution (e.g. a hash value computed over the password) would allow anybody to run a dictionary attack at his leisure (an offline dictionary attack) and that's precisely what protocols like SRP strive to avoid.

So, no ZK for passwords, and SRP is not ZK.

SRP is a Password Authenticated Key Exchange protocol, which aims at establishing a shared secret key between Piotr and Victor, and authenticating Piotr and Victor to each other with regards to their knowledge of the password (or of some value deterministically derived from the password). What PAKE protocols achieve is that nobody spying on the exchanged messages, or even impersonating Piotr or Victor, learns anything about the password: not only is the password not revealed to outsiders, but such attackers cannot even obtain anything which would allow them to run an offline dictionary attack. This is what PAKE protocols do, and what a simpler scheme does not (such as using the shared password directly as key to encrypt further exchanges -- this is known as "pre-shared key" and is vulnerable to offline dictionary attacks).

Nevertheless, PAKE protocols, like any other password-based protocol, assumes that some prior out-of-band secure communication had taken place in some way. This is intrinsic: Victor wants to authenticate Piotr. Who is Piotr ? What distinguishes Piotr from anybody else ? For authentication to make sense, Victor must have some a priori knowledge of what makes Piotr different from, say, Pavel or Prokhor; in a networked computer world, what distinguishes entities from each other is what they can do, and what they can do (as observed through an ethernet link) is what they can compute which depends on what they know.

Password-based protocols are based on the idea that Piotr has some knowledge of a password (that Pavel does not know), enabling him to do something which Victor can verify in some way. What Victor knows of the password necessarily enables him to run an offline dictionary attack on the password (Victor can run the protocol with himself, executing both parts of the protocol, trying out any potential password). We saw that offline dictionary attacks are a problem, and that PAKE avoids them -- so whatever Victor knows about the password MUST NOT be public. Hence the need for a prior secure communication.

In a Web context, the prior secure communication is usually a registration page sent over SSL (HTTPS). From the point of view of the server (Victor), it does not really matter who Piotr is, as long as Victor can keep track of each registered user in the following sense: Victor wants to be sure that this is the same Piotr all along. So Piotr registers on Victor by sending his password, and then, later on, Piotr comes back and Victor authenticates him relatively to this password. Note that such a context requires that, at some point, Piotr and Victor could have a secure tunnel where Victor is authenticated by Piotr: that's what SSL provides, authentication of Victor being done through Victor's certificate. If Victor has a certificate which is good enough for Piotr, then they can do SSL again at will, and within a SSL tunnel Piotr can simply show his password again -- in that context, PAKE protocols like SRP do not have great practical value.

PAKE protocols are really good when the prior communication took place in a non-Internet way. For instance, Piotr and Victor met each other, or phoned to each other, and could exchange some secret data by uttering it. Some data which can be vocalized and heard by humans, that's a password. Then, they can enter the password into their respective software, e.g. Victor manually creates an account for Piotr on his server, with the agreed-upon password. In that setup, PAKE protocols are meaningful, even with SSL (there is an RFC for that), because it avoids all of the friggin' certificate business (finding Web browsers with the corresponding client support might be challenging, though).

3

You seem to be talking about Password-Authenticated Key Exchange protocols.

But the problem you're describing is a general one: It is (currently) impossible to create an authenticated channel out of thin air. The best we have is PKI, a scheme to delegate the authentication to centralized entities which can be trusted by the client for their particular purpose, so that we don't have to explicitly authenticate each and every party we talk to.

Given PKI and thus server authentication, you can initialize a zero-knowledge mutual password-authentication within a secure channel created by server-side-authentication. Just the way that people today register accounts and passwords in an SSL-secured channel.

The difference is how vulnerable your protocol is to variety of different attacks in later stages of the transaction: Do I have a chance to capture your password in each and every login-process? What does the server and browser know at the end of a ZK-login? What is the impact of misunderstood PKI certificate warnings, assuming that the warning is caused by an active attack in 0.1% of the cases?

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .