[curves] PAKE use cases & requirements

[Damien Miller]

On Mon Oct 20 2014, Greg Zaverucha wrote:

> After a side conversation, I realize that having more details on the
> OpenSSH use case would help. This is the use case that prompted the
> two requirements in my previous email. This was in Trevor's email from
> Oct 8:

[...]

> Is more information available? Could you sketch how the PAKE and
> existing hashed passwords would work together?

Here's the full email I sent to Trevor off-list.

-d

---------- Forwarded message ----------
Date: Fri, 3 Oct 2014 14:42:52 +1000 (EST)
From: Damien Miller <djm at mindrot.org>
To: Trevor Perrin <trevp at trevp.net>
Cc: mfriedl at gmail.com
Subject: Re: PAKE in OpenSSH

On Thu, 2 Oct 2014, Trevor Perrin wrote:

> Hi Damien, Markus,
>
> I run a mailing list on elliptic curve crypto
> (curves at moderncrypto.org):
>
> https://moderncrypto.org
>
> A number of us are interested in "next-generation" PAKE algorithms
> that would be more efficient and have better security analysis than
> things like J-PAKE or SRP. For example:
>
> https://moderncrypto.org/mail-archive/curves/2014/000288.html
>
> However, it would be nice to have the design informed by real-world
> use cases, and have a chance of real-world deployment.
>
> We're trying to figure out what those use cases would be, and ssh
> seemed like a possibility.
>
> Is there any chance OpenSSH might be interested in a new PAKE, and
> someone might be willing to discuss with us the options / requirements
> etc for something like this?

So, I'm not so much interested in a PAKE for SSH as I am a
zero-knowledge password scheme. A PAKE generally provides this en
passant, but I'm not interested in the output for key exchange, just
authentication.

If you are still interested, some requirements off the top of my head:

1. Has a security proof that withstands scrutiny :)

2. No IPR caveats

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}

4. Low DoS potential.

We don't want a situation where a malicious or misbehaving client can
cause the server to do a lot of needless work.

5. Really nice to have: works with unmodified password hashes.

Ideally, we'd want something that could work with regular /etc/shadow
files without rehashing them. I couldn't figure out how to do this
without passing (at least) the salt to the client and am not sure it's
even possible.

*

One non-goal for us: it doesn't have to be fast. We are considering this
as a candidate to replace password authentication, so in most cases
the slowest element of the protocol is going to be the user typing the
password. With this in mind, the protocol doesn't have to go out of its
way to grind down the number of client/server round-trips or the amount
of computation done (especially given the password hash needs to be slow
and expensive anyway).

We could probably get away with some EC-Schnorr signature variant rather
than a full PAKE for SSH use. We don't need a key at the end of it, just
a bit for the server indicating the client proved it was in possession of
the password and a bit for the client to say whether the server had a
matching hash. That being said, if there was a PAKE that offered these
properties without other deal-breakers, then we'd consider using it.

Hope this helps,
Damien