[curves] password authenticated key exchange (PAKE)

[Mike Hamburg]

On 10/2/2014 5:48 PM, David Leon Gil wrote:
> Are you considering PAKE in something Dolev-Yao-ish (i.e., with a
> strong KCI assumption) or a bideniable model?
>
> (I assume Dolev-Yao-ish in the following.)
Yeah, Dolev-Yao-ish, though bideniable would be kind of cool too.  I 
guess that's another knob I haven't thought of, though I don't know how 
easy it is to turn.
> On Thu, Oct 2, 2014 at 6:54 PM, Michael Hamburg <mike at shiftleft.org> wrote:
>> Explicit key confirmation: Require or no?
> Should be optional but possible; am I right in thinking it always
> requires an additional round?
Yeah.  Also if each side sends one flow, then both of them have to use 
the password, not just the first person.
>> Augmentation: Should the server’s credential be insufficient to log in without a dictionary attack?  Maybe augmentation on both sides is even desirable, for some reason?
> Certainly yes to the first for client-server; it's a lovely property.
>
> Isn't it necessary in the peer-to-peer situation? (Otherwise, by
> symmetry, a form of KCI is possible.)
>
> (I'm assuming you mean a per-client credential. A PAKE protocol that
> provides this also needs to be secure against KCI, in an appropriately
> strong formulation.)
Right, so I mean that both parties can derive a key from the password, 
and that key doesn't suffice to impersonate the other party.  I can 
imagine a use for this, like a password manager or something, but I'm 
not sure anyone cares about it.
>> Security model: Does anyone care about GapDH, DDH, SquareDH etc assumptions?  This is definitely in the random oracle model, by the way.
> I'd very strongly prefer DDH. GapDH is okay. Anything more exotic is
> asking for trouble, but eh, hardly anyone cares. (But the "generic
> group" assumption would be unacceptable.)
>
> Are there tightness issues? I'd be reasonably happy with a tight GapDH
> reduction, even with a (very) non-tight DDH reduction.
Yeah, tightness is basically it.  The GapDH reduction would be pretty 
tight, which I guess is typical for GapDH.  Tightness is also why I was 
considering some sort of SquareDH (i.e. given g, g^x, 
determine/distinguish g^x^2).  I think basing the system on SquareDH 
instead of DDH improves its performance in the case that explicit key 
confirmation is optional, possibly unless you accept a big tightness loss.

I might also be able to prove under straight CDH (in the ROM) but almost 
definitely non-tightly.
>> On a somewhat related note, is there any desire to encrypt the user name?  A man in the middle can recover it at the cost of disrupting the session, but it should be possible to hide it from passive eavesdroppers (at the cost of more rounds and more complexity).
> Does it *require* more rounds? (I.e., what's the problem with the
> obvious approach of encrypting under the server's static key, for the
> client-server case?) PFS would require an additional round, I think...
Well, it doesn't require more rounds if you know the server's static key 
ahead of time, but usually in PAKE you don't.

Thanks,
-- Mike