# [curves] SPAKE2 and SPAKE2 Elligator Edition

Mike Hamburg mike at shiftleft.org
Thu Feb 12 01:53:15 PST 2015

```Hello curves,

It's been suggested that I explain Elligator and SPAKE2-EE in more
detail.  Get ready for a wall of text.

TL;DR: SPAKE2-EE is probably slightly better overall than SPAKE2. It's
slightly faster, has better security assumptions, and makes one or two
cases that can arise in SPAKE2 slightly easier.  It's also more
complicated to spec and implement, since you need Elligator.
SPAKE2-vanilla needs more complicated optimizations to achieve its top
speed, but at least you don't have to spec them.

Elligator 2:

Elligator 2 is a map from the base field F to any elliptic curve E (over
a large characteristic field) with a point of order 2. There's also an
Elligator 1 but it's more complicated and has more restrictions, so
let's stick with Elligator 2.  If the curve doesn't have a point of
order 2 (eg, the NIST curves), then the Shallue-Woestijne-Ulas (SWU)
algorithm has very similar characteristics, and is only slightly more
complicated.

Any curve with a point of order 2 is isomorphic to one of the form y^2 =
f(x) = x (x^2 + Ax + B), i.e. Weierstrass form with the point of order 2
at (0,0).  From there, the idea is to come up with two values x1 and x2
where one of them has a y on the curve and the other does not.  To do
this, it suffices that:

x1^2 + Ax1 + B = x2^2 + Ax2 + B, and
x1 / x2 is not square in F

The first condition is equivalent to x1 + x2 = -A.  The second condition
is equivalent to x1 = ur^2 x2, where r is arbitrary and u is a fixed
nonsquare value, eg -1 if p==3 mod 4.  (If r=0 then actually x1/x2 = 0
will be square, but that's good enough because (0,0) is on the curve.)
Solving these two equations gives x2 = -A/(1+ur^2), and x1 = ur^2 *
that.  Notice that if you plug 1/ur into the equation for x1 you get x2
and vice-versa.

So Elligator is conceptually pretty simple:

* Map your input value to a field element r.
* Compute whether f(-A/(1+ur^2)) is square.  If so, compute its square root.
* If not, compute the square root of f(-Aur^2/(1+ur^2)) = ur^2
f(-A/(1+ur^2)).

There are two important optimizations here.  The first is that you can
compute f(-A/(1+ur^2)) projectively, so you don't have to divide.  If it
ends up as C/D, then you can compute s = sqrt(CD) and then have y = s/D,
again projectively; or if you use the isqrt trick you can compute the
actual value of y.  This latter technique is better, because you can
easily enforce the spec that y is "positive" if you chose x1 and
"negative" if you chose x2, for your favorite definition of those terms
(even, Legendre symbol, whatever).

The other important optimization is to compute both square roots in one
step.  For example, if p == 3 mod 4, then u=-1 and x^((p+1)/4) =
sqrt(+-x).  So compute f(...)^((p+1)/4).  If it comes out as
sqrt(f(...)), good.  If not, it's sqrt(-f(...)) but you want
sqrt(-r^2f(...)).  So multiply it by r and you're good.  In 5-mod-8
world, sqrt(-1) takes the place of -1 here.

But you didn't want to hash to a Weierstrass curve.  You wanted to hash
to an Edwards curve.  No problem.  Just hash to the isomorphic
Montgomery curve, and apply the isomorphism, all in projective
coordinates.  Or, in cases like SPAKE2, you'll need to multiply by 4 so
that you get something in the main subgroup.  You can hash to Edwards
and multiply by 4, or you can hash to the isogenous Montgomery curve

All in all, this means you can compute Elligator 2 in projective
coordinates with maybe one isqrt, a dozen muls, 35 lines of code, a
couple cond-selects (or multiplies by values you know in advance to be
+-1), and some careful testing.

Elligator 2 is implemented in C as one of the many available point ops in:

http://sourceforge.net/p/ed448goldilocks/code/ci/decaf/tree/src/ec_point.c

This is an unnecessarily nasty implementation, because it maps to affine
(using the inverse square root trick) instead of to projective.  Not
worth it.  The Decaf version is simpler.

In the case of Decaf, the main spec is in terms of a Jacobi quartic,
rather than a Weierstrass or Edwards curve, but all the actual math
takes place in twisted Edwards.  The Jacobi quartic is isomorphic to L_d
: y^2 = x(x-1)(x-d).  So you can do Elligator to that curve -- remember
that Elligator 2 doesn't require a Montgomery curve -- and then use the
2-isogeny from there to the twisted Edwards curve where it does all its
math.  Same deal as with the Montgomery/Edwards combination, slightly
different formulas.

This is implemented in C as decaf_point_from_hash_nonuniform in

http://sourceforge.net/p/ed448goldilocks/code/ci/decaf/tree/src/decaf.c

There's also a function decaf_point_from_hash_uniform which calls
Elligator twice and adds the results.  This is indifferentiable from a
random oracle, but twice as slow.  It's not necessary in most protocols,
because they really only need an argument that looks like "for all you
know, the hashed point on the curve could secretly have an embedded CDH
challenge" and that doesn't require uniformity, only almost-uniformity
and almost-invertibility.

For an RFC-style spec, you'd probably want to turn one of these C
functions into a few lines of Python and specify that exact computation.

OK, now on to PAKE.

Elligator is 1:1 on [0,(p-1)/2], and it's easy to invert the map for
those points in E where it has an inverse.  This matters for EKE,
though, and we're talking about SPAKE2.  Remember that SPAKE2 works like so:

Let g, M and N be random generators of G, with no known relationship in
the group.  Let "password" be a suitably stretched salted hash of the
actual password.  Either the client has to retrieve the salt, or it's
equal to her username and the server's name.

Alice -> Bob: A := g^x M^password, ID_Alice
Bob -> Alice: B := g^y N^password, ID_Bob

This can be optimized by a double-exp, possibly with fixed bases if you
precomputed a table for M and one for N.  Also, the server can just

They can implement the division as written, or they can use a

Then both sides compute validators and session key vA,vB,sk =
H(A,B,ID_Alice,ID_Bob,g^xy,password).  The session messages are included
to prevent tampering.  The password is included as an artifact of the
security proof, and is probably technically unnecessary.  For augmented
versions of SPAKE2, a hash of password is also a good enough artifact.
Anyway, the two sides exchange validators and then start using the
session key.

The two DH flows and the two validation flows can each happen
simultaneously, or more likely Bob's two flows will be merged but
Alice's will remain separate.

SPAKE2-EE

SPAKE2-EE ("Elligator Edition") is a simple variant of this protocol, in
the cofactor, and likewise for N.  It's very important to clear the
cofactor here, or to use a g which generates the entire group and not
just the main subgroup; otherwise the cofactor components of the
password hash will leak. Decaf's Elligator variant clears the cofactor
for you; Goldilocks' does not.

Putting Elligator in clearly doesn't hurt the security of the protocol
in the ROM, because for all the attacker knows
h*Elligator(H("M",password)) is actually equal to, or at least morally
equivalent to, M^password.  The rigorous proof proceeds almost exactly
the same as SPAKE2 proof, but with an extra invocation of the random
oracle model.

As far as I see it, SPAKE2-EE's advantage is that it's slightly tidier
than SPAKE2 proper, because it removes the static-DH assumption.  In
SPAKE2, you have to convince people that you generated M and N with no
relationship to g, because an adversary knowing the discrete log of M
base g can mount a dictionary attack against everyone.  (I believe that
the same is only true for N if the flow ordering allows Alice to
authenticate first.)  It shouldn't be hard to generate such an M,N, but
it's even better if you don't have to.

SPAKE2-EE has a small performance advantage over SPAKE2 proper, at least
when Elligator is implemented as described above.  That implementation
takes under 1M/bit since the expensive part is the square root, but even
if you precompute tables for M,N, it will cost at least 1.8M/bit to
compute M^password and again 1.8M/bit for N.

The cost is that you have to spec and implement Elligator, which is
annoying but not terrible.  At the same time, there won't be any
temptation to implement double-fixed-base-comb-exp routines to improve
performance.

More-symmetric and less-symmetric PAKE:

It's not very important that M != N.  I'm pretty sure the proof Trevor
cited of this is wrong, but I'm also pretty sure that a proof exists
under slightly worse assumptions than the original.

Alternatively, N^password can be dropped, so long as Bob sends his
validator first.  (If Alice sends hers first without N^password, then a
fake Bob clearly has a dictionary attack because his first
password-related computation is to check the validator.)  This doesn't
harm the proof IIRC, it just adds the ordering restriction.

These are both provable under some CDH variant (eg, GapDH if you like
shorter proofs with unrealistic assumptions, otherwise straight CDH with
tightness loss) in the random oracle model.

SPAKE2-EE has the same properties as SPAKE2 with respect to these two
options.  It also has another option, which is that Alice and Bob use
either temporary identities (IP address, etc) or even just random
nonces, and replace M with h*Elligator(H(nonce_M,password)) and likewise
for N.

Augmentation:

SPAKE2 can be augmented, where the server's credentials (i.e. Bob's
strengthening function.  Alice can compute g^(y*password2) from Bob's
flow because she knows password2 and g^y.  Bob can compute it because he
hash function when they compute the session key.  Dan and Victor's book
calls this PAKE2+ and contains a security proof, but then again that
book isn't published.

I suspect that many PAKEs can be augmented in a similar way, but they
usually aren't specified with augmentation.

SPAKE2 can even be doubly augmented, where Alice does the same thing,
but I'm not sure if there's any application to that.