[curves] PAKE use cases & requirements

[Michael Hamburg]

> On Oct 20, 2014, at 8:04 PM, Watson Ladd <watsonbladd at gmail.com> wrote:
> 
> On Mon, Oct 20, 2014 at 6:18 PM, Damien Miller <djm at mindrot.org> wrote:
>> On Mon, 20 Oct 2014, Watson Ladd wrote:
>> 
>>> Based on that it seems that the Secret Millionaire Protocol is a
>>> possibility, but could load the server more than necessary. SPAKE2 is
>>> also worthy of consideration.
>> 
>> AFAIK none of these solve:
>> 
>>>> 3. Can work with hashed passwords.
>>>> 
>>>> I.e. the server stores some H=F(password, salt) but the client gets
>>>> to use the password directly. Disclosure of H yields no more to the
>>>> attacker than disclosure of a password file that has been sensibly
>>>> hashed today (e.g. with bcrypt).
>>>> 
>>>> The password hash should probably reuse one of the good current
>>>> ones (bcrypt or scrypt). E.g. by storing something like
>>>> G^{BCRYPT(pw,salt) mod P}
>> 
>> My somewhat clumsy experimental JPAKE implementation for OpenSSH
>> didn't either - it used the password hash as the shared secret to be
>> authenticated against and therefore would allow logins (via JPAKE) to an
>> attacker with access to the password hashes alone.
> 
> Okay, here is a protocol that solves that problem, but you are not
> going to like it:
> 
> Let G_1xG_2->G_T be a bilinear group, g_1, g_2 generators of G_1 and
> G_2. Let the server store BCRYPT(pw, salt)g_2. Then when a client
> authenticates the server sends rg_1, the client responds with
> BCRYPT(pw, salt)rg_1, and the server checks that
> e(BCRYPT(pw,salt)rg_1, g_2)=e(rg_1, BCRYPT(pw_salt)g_2). This is an
> instance of the Computational Co-Diffie Hellman Problem.
> 
> Sincerely,
> Watson Ladd
>> 
>> -d

You’re right.  I don’t like it, for two reasons.

One, the Linux password hash isn’t BCRYPT(pw,salt) g_2 over a bilinear group.  The original ask was “unmodified” password hashes.

Two, it isn’t secure.  A fake server can dictionary-attack the password after one interaction.  You know this must be the case, because the server doesn’t use the password until the “check” step.

The modified ask is achievable and is a good idea, but IIUC it’s the same as “augmentation”: what’s stored on the server isn’t password-equivalent without a dictionary attack.  Augmentation is not terribly difficult and doesn’t require bilinear groups.  The easiest way is just to have the server store H1(pw,salt), g^H2(pw,salt).  Then do an un-augmented protocol with H1(…) as the password.  At some point in the protocol the server chooses y and sends something equivalent to g^y.  At the end, both sides toss g^(y * H2(pw,salt)) into their final hash computation which produces the session key.  The server knows y and g^H2(…); the client knows g^y and H2(…).  Breaking something like this will generally be equivalent to CDH in the ROM.

I think the original ask is infeasible to combine with augmentation.  It might not be technically impossible because of standard results in multiparty computation, but good luck turning bcrypt into a garbled circuit.  Damien’s “clumsy” technique is probably the best one.

Cheers,
— Mike