[curves] PAKE use cases & requirements

[Brian Warner]

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