[curves] PAKE questions

[Trevor Perrin]

On Sat, Feb 7, 2015 at 2:21 PM, Michael Hamburg <mike at shiftleft.org> wrote:
>
> One thing worth considering is “SPAKE2 Elligator Edition”.  This is SPAKE2,
> except that you replace M^password, N^password with
>
> cofactor * MapToCurve(H(“M to the password”, password)),
> cofactor * MapToCurve(H(“N to the password”, password)).
>
> 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”.
[...]
> Also, this gets rid of the static DH assumption (i.e. that an attacker can MITM
> the protocol if they know the discrete logs of M and N), but if you choose your
> points in a sleeveless way that doesn’t matter much.

Could you say more about the advantages of Elligator here?

Setting M == N is easy - Mike Scott proposed it in 2001 [1], and
Kobara/Imai published a proof in 2003 [2].  So that simplifies the
protocol, and seems adequate for the "simultaneous initiate" case
(Pond, Petmail, 802.11S).

Choosing extra generator(s) so their discrete log isn't known seems OK
provided group parameters and generators are chosen rigidly - more
below.

SPAKE2 maps the password to a point via a fixed-based scalar mult.  If
we replace this with the Elligator map, how do compute costs, and code
complexity, change?


>> 3: Simultaneous Init (M==N)
>>
>> I don't know what the best term is for this, but most of the PAKE
>> algorithms I've seen assign roles to the two parties, and bake those
>> into the messages. I'm sure this makes the proofs easier to build, and
>> might block some sort of reflection attack (what happens if the attacker
>> echoes Alice's message back to her.. could that help them learn the key
>> or the password?).
>
> Yeah, it’s mostly a proof artifact.  The main difference is that it lets you use the CDH
> problem (in the ROM) instead of CDH-squaring.

Kobara/Imai uses DDH without the ROM.  I'd be interested in your
opinion of their proof.


>> 4: Choosing M and N (aka U/V in PAKE2)
>>
>> SPAKE2 requires two "arbitrary public elements" to blind the passwords,
>> but what wasn't obvious to me when I first started was that it's
>> important that nobody knows the discrete log of either one (otherwise an
>> active attacker gets a dictionary attack, I think). Since the easiest
>> way to pick a random element is to start with a random scalar, it's a
>> subtle failure mode for implementors.
>>
>> Picking an arbitrary member of a an elliptic curve subgroup usually
>> means picking a random X coordinate, finding the 0 or 2 points that
>> match (50/50 chance), choose one, then see if it's in the subgroup.
>> Small cofactors make this probable(?) enough that random hunt-and-peck
>> will yield a result quickly, and you can make it more rigid/"sleeveless"
>> by starting your random search at SHA256("") or something.
[...]
> Yes, this works.  Though I like Michael Scott’s idea of using 2 and 3 mod
> a safe prime, if you aren’t using EC.

If using compressed points and a rigidly-generated curve, why not do
something similar and choose the extra generator to have the smallest
possible uncompressed coordinate (or smallest possible with sign bit =
0)?  Seems simpler to explain / specify / implement, and quite rigid.


Trevor