[curves] PAKE questions

[Brian Warner]

On 2/7/15 2:21 PM, Michael Hamburg wrote:

> The disadvantage of this is that you need to implement Elligator or
> some other map to the curve, but the advantage is that the parties’
> IDs can be more than just “client” or “server”.

How is this different than the static idA/idB that's usually hashed
(along with the transcript) into the final key? I imagine it's more
tightly bound somehow..

> For the field, you can set MapToCurve to just be a full-domain hash
> function.

That's a hash function with an output range of Zp*, right? Do people
typically implement that with hash-to-larger-and-modulo (accepting a
fraction of a bit of bias), or try-try-again (no bias but variable
runtime)? Or hash-to-necessary-bits and accept more bias?

>> I've got a 2048-bit integer group running in 16ms on a fast computer,
>> 110ms on a slower one, and it'd be nice to bring that down a little
>> bit.
> 
> Are you using pow(x,e,p)?  It ought to be faster than that.

Yeah, pow(x,e,p) on python2.7 . It looks like a single pow() takes 4ms,
but there are several of them. Alice computes G*x and M*pw when building
the first message. She verifies the incoming point (MSG_Y*q) and
computes -N*pw and (MSG_Y-that)*x during receipt of the second mesage.

That's 5 exponentiations, and when I added the point-verification check
(which I forgot the first time through, like always), it takes 20.5ms to
do the whole side, so that about accounts for it.

The code is in https://github.com/warner/python-spake2 if you want to
take a look. Run "python setup.py speed" for the benchmarks.

>> 1: Dealing with the cofactor

> If you’re going to drop a coordinate, then send a sign bit in its
> place. You even have an extra (256th) bit to use without breaking
> alignment. You can’t (easily) use the Montgomery ladder anyway.

Yeah, so I need to decompress the point before doing anything with it,
right? I can't use the Curve25519 trick of ignoring Y everywhere?

>>  Z = (MSG_X*cofactor - N*pw*cofactor) * y
>>
>> Are we on the right track?
> 
> Yeah, that. Or just *y*cofactor, since multiplication distributes and
> commutes.

Is it safe to do that after the subtraction? I know the subgroup's "*"
is distributive, but I was concerned that we'd leave the subgroup with
the (nonmember-N*pw) and then all bets would be off.

> *Shameless plug*:
> If you’d like, I can get Decaf up and running on TwistEd25519 in
> Python. Decaf divides the cofactor by 4, and also conveniently
> implements a hash to the curve.

That'd be fun :).

>> Alice then XORs the keys that come out of her two instances. Bob does
>> the same.
> 
> This is probably fine, but watch out for the reflection attack! If an
> attacker reflects Alice’s messages and she accepts them, then she will
> xor the session key with itself and get 0. Bob will too. Bad times.

Sigh, once again my implementation didn't guard against trivial things
like that.. unit test now added :).

>> 5: Hashing the password

I'll think more about this one.. I seem to recall that simply stretching
it before the exponent didn't accomplish what I wanted, but I have to
nail down exactly why.

thanks!
 -Brian