On 2/8/2015 10:08 PM, Trevor Perrin wrote:
On Sat, Feb 7, 2015 at 2:21 PM, Michael Hamburg <m...@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
_______________________________________________
Curves mailing list
Curves@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
