[curves] SPAKE2 and SPAKE2 Elligator Edition

[Trevor Perrin]

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.

Thanks Mike,

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
implementation choices:
 - 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
twice?)


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.


Trevor