[curves] PAKE use cases & requirements

[Michael Hamburg]

I asked Dan Boneh about this, and we didn’t figure out an answer in our brief meeting but he said it’s a good problem.

Makwa with a public N, where nobody holds the trapdoor, is a good idea since you can outsource it.  You can’t check the answer, though… which is OK, I guess?

Another option, which is also way out there:

Let H(password) = H1(discrete log(H2(password))), where the discrete log is computed over a weak elliptic curve which is unique per user but doesn’t depend on the password.  Perhaps the curve has ~2^50 points on it, requiring ~2^25 work, which will take a couple seconds.

The discrete log calculation can be offloaded to the server, by sending H2(password) * g^r, where r is random mod the order of the curve.  Subtracting r at the end gives the answer, and the answer can be checked easily.

The problem is, n discrete logs can be batched into O(sqrt(n)) times longer than a single one.  So if the database has a million passwords, they can be checked in the time required for 1000 logins.  So Makwa probably works better.

Cheers,
— Mike

> On Oct 21, 2014, at 7:01 PM, Brian Warner <warner at lothar.com> wrote:
> 
> On 10/16/14 3:34 PM, Greg Zaverucha wrote:
> 
>> Are there PAKE schemes where the augmented option adds a workfactor
>> for the server role only? The goal being to make brute force attacks
>> more expensive if the verification information is compromised.
> 
> I haven't found one yet. I suspect it's impossible, but I have no idea
> how you'd prove that.
> 
> This was part of the reason that we switched Firefox Accounts from the
> SRP-based protocol that I'd built to the simpler plain-old-scrypt
> scheme. I liked the zero-knowledge aspects of SRP (or any PAKE system,
> augmented or symmetric), but the lack of server-side key-stretching
> meant that any protection against server compromise must come from the
> client. In our SRP-based protocol, the client did about 1.0 seconds of
> scrypt (N/r/p = 64k/8/1) before using the stretched result as the SRP
> "password". This made life difficult for slow clients, such as ones
> implemented in web-page javascript.
> 
> One crazy idea: Thomas Pornin has a password-hashing.net submission
> named "Makwa", based on repeated squaring modulo a composite Blum
> integer, which enables a certain amount of delegation (safely letting
> someone else do part of the key-stretching work for you). I've wondered
> if this might be usable as a primitive in a PAKE protocol, using
> "square-N-times" instead of "multiply-N-times" as the group operation.
> 
> The upside/downside is that there's a secret key (the factors of the
> Blum modulus) which lets you bypass the stretching and exponentiate
> directly. For many login-like settings, this is fine (you keep the
> factors offline, or throw them away after setup), and even useful (you
> can batch-update the stretched verifiers without needing client
> involvement). But for Pond/Petmail-like invitation schemes, with no
> trusted server, the existence of this secret key is uncomfortable, as
> the safety of your stretching depends upon the creator of your group
> parameters honestly throwing it away.
> 
> cheers,
> -Brian
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves