[curves] PAKE questions

[Michael Hamburg]

> On Feb 7, 2015, at 4:30 PM, Brian Warner <warner at lothar.com> wrote:
> 
> 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..

If the hash to the curve is based on idA / idB, then you don’t need to figure
out which party uses M and which uses N, which is something you were
concerned about.

>> 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?

Hash larger and modulo.  Security-level bits larger (128 or whatever) is good
enough even for a prime that’s not close to a power of 2.  Especially here
because it doesn’t have to be uniform anyway.

>>> 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.

Ah, that makes more sense.

>>> 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?

Right.

>>> 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.

The whole group’s * is distributive.

>> *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 :).

OK, I’ll see what I can do.

>>> 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 :).

There was a Stanford crypto problem set where you had to design a protocol
for something.  A lot of people had a very similar bug in their design.

>>> 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

In the earlier thread, it was because you didn’t want to push the work to the
client.  Is that still a requirement?  I don’t have a solution for it.

Cheers,
— Mike