[curves] SPAKE2 and SPAKE2 Elligator Edition
trevp at trevp.net
Thu Feb 19 19:53:57 PST 2015
On Thu, Feb 12, 2015 at 1:53 AM, Mike Hamburg <mike at shiftleft.org> wrote:
> 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.
Good topic (SPAKE2 vs SPAKE2-EE).
I think I prefer the SPAKE2 approach using a single generator (i.e.
both parties use a scalarmult of hashed password with generator M, per
Mike Scott's "MIKE").
This works the same on every curve, and has straightforward
- simple = variable-base scalarmult for M^password
- optimized = prebuilt tables scalarmult for M^password
(Merging M^password calculation with the Diffie-Hellman keygen and
variable-base scalarmult doesn't seem worthwhile - since M^password is
used in both, probably best just to calculate it once and use it
Comparing with Elligator Edition:
Performance - Even if Elligator was free, the comparison between
optimized SPAKE2 and SPAKE2-EE would only be:
- 1 variable-base, 2 fixed-base (SPAKE2 single-generator)
- 1 variable-base, 1 fixed-base (SPAKE2-EE)
Assuming fixed-base is 3x faster that would be 20% less compute time.
With your estimate that Elligator 2 takes around half the time of a
fixed-base op, there's only ~10% speed difference. Since PAKE is
usually a "human-in-the-loop" operation on a capable processor, I
don't think this speed difference matters.
Complexity - With your approach, you need a map-to-point function that
will depend on the curve: Elligator 2 for some curves, SWU (or
Elligator Squared?) for others. And implementation details will
depend on the field prime, curve form, and point representation.
Seems like a lot of work to spec out these details, and a lot of room
for implementation mistakes (e.g. not making things constant-time).
Also, the implementor needs access to low-level field arithmetic that
might not be available. For example, your implementations assume an
optimized inverse-square-root function, and const-time conditional
select and swap.
To me, the algorithm and code complexity is a bigger issue than
performance or rigid generator selection, so I think that favors the
"vanilla" SPAKE2 approach.
But I'd like to hear counter-arguments and other opinions.
More information about the Curves