[curves] PAKE use cases & requirements

[Watson Ladd]

On Mon, Oct 20, 2014 at 5:21 PM, Damien Miller <djm at mindrot.org> wrote:
> 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.

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.

>
> -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
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin