[curves] PAKE questions

[Mike Hamburg]

On 2/8/2015 10:08 PM, Trevor Perrin wrote:
> 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?
Code complexity goes up slightly, because you have to implement 
Elligator or similar.  Elligator's map to the curve is 30-40 lines of 
code to do in constant time (with one arithmetic op, condswap etc per 
line).  This is for the decaf version of Elligator 2, mapping 
fixed-length byte sequences to the even points on a twisted Edwards 
curve in extended coordinates; other versions might be over or under.

Compute costs go down at least slightly.  Elligator costs one isqrt and 
~14 field muls.  You can optimize ordinary SPAKE2 by computing g^x M^pw 
with a double-scalarmul and precomputed combs on both g and M, but the 
incremental cost of M^pw won't go much below 2 field muls per bit, which 
is at least twice as much.  Also if you do this then you aren't saving 
code complexity, but at least you have the choice between simple and fast.

Of course, on the client side you're probably running scrypt also, tuned 
so that the actual EC is a small fraction of the cost, and on the server 
side you cached the point to avoid running scrypt, so perf doesn't 
really matter.
>>> 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.
I don't think their proof is right, but I only skimmed it so I'm not 
sure.  Aside from using the wrong formalism (they need at the very least 
a PRF in addition to a MAC, and more serious problems with proof 
structure), they seem to be assuming that the adversary has a pass_c in 
mind when impersonating a client (or _s for a server). But basically the 
whole goal of a PAKE security proof is to show that this is the best an 
adversary can do.  Also, I don't think they modeled MITM attacks.

But I'm pretty sure that you can prove SPAKE2-symmetric secure assuming 
square-CDH in the ROM, or with gap-square-CDH (almost the same as GapDH) 
with a tighter bound but also in the ROM.  In other words, it should be 
like SPAKE2 proper, but with a square-CDH instead of ordinary CDH.
>>> 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.
... but on reconsideration, I would recommend hashing instead; see below.
> 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
Yeah, that also works.  Probably.

Keep in mind that for both EC and classic DLP, rigidity doesn't matter 
here in the way that it might theoretically matter for curve selection.  
DLP and the like are randomly self-reducible within a single curve / mod 
a single prime.  If DLP (or CDH) is weak in one in a billion random 
points, it's weak everywhere.  If it's weak for the two least points on 
the curve or two least numbers mod a prime, it doesn't easily follow 
that it's weak everywhere.  Consider, for example, p = 2^n-3.  (This 
can't be a safe prime, but you get the idea.)

So hashing to the curve or field is slightly theoretically better; 
choosing the least generator is cute and probably good enough. 
Basically, hashing is invoking ROM and choosing the least one is 
invoking GGM.  Unless there's something I'm missing?

Cheers,
-- Mike