Zero Knowledge Password schemes

So in my previous post I was lamenting that as it stands today, for the majority of the Internet, when I authenticate to a website I have to send them my password.  It's obvious that if that wasn't a requirement then this would be better.

This caused me to read up more on Zero-Knowledge Password authentication schemes, and I came across the Secure Remote Password (SRP) Protocol (very nicely summarised here).  However, in the security analysis (given on the linked page) of SRP there was the following property:

"If the host's password file is captured and the intruder learns the value of v, it should still not allow the intruder to impersonate the user without an expensive dictionary search."

To me, this is not good enough.  Or at least if I am giving my list of all criteria I would like my authentication protocol to meet, one of them would be that "even if the password file is captured an attacker cannot recover the password".  This sounds like an impossible dream, but I hope it is not. 

Initially I imagined a change to SRP that I thought might do the job.  If we had 2 generators for the group, g1 and g2 (so in the current scheme replace references to g with g1), and 2 passwords, P1 and P2, then we could construct v as:

1. x1 = H(s1, P1)
2. x2 = H(s2, P2)
3. v = g1^x1 . g2^x2

The rest of the protocol could be minimally altered to accommodate this.  Hopefully you can see that an attacker with access to v, s1 and s2, could in fact hit upon multiple P1 and P2 values that create the same v value.  So even if the attacker was able to create all possible P1 and P2 values, they would not be able to tell if they were the actual password values.

But the suggestion has a drawback.  Well it has a couple.  Firstly it requires the use of 2 independent passwords.  Secondly, if an attacker got the password files for 2 different sites using the same g1 and g2 (and using the same group) then they could solve for P1 and P2 (from a list of candidates after a brute-force attack).  Lastly, my analysis is optimistic in saying that multiple solutions exist because the range of possible passwords is so much smaller than the range of possible x values.

Still, it's fun to play with these ideas, and you never if you might hit on the right combination :)