I am working on implementing the SPAKE2 algorithm for a krb5
pre-authentication mechanism, and would like to double-check some
conclusions I've drawn about elliptic curve implementations.
For SPAKE2, I need to compute T=xG+wM and K=x(S-wN), where x is a random
scalar, w is a scalar derived from a shared secret, G is the base point,
and M and N are constant points in the subgroup of the base point, and S
is a point presented by the other party. (There is a similar pair of
computations by the other party, S=yG+wN and K=y(T-wM).) Side channels
which reveal information about x, w, xG, wM, or wN could affect the
security of the mechanism. I also need to be able to serialize and
deserialize the scalar x; side channels in that serialization could also
affect the security of the mechanism. Performance on common platforms
is important, as password-based initial authentication currently only
uses symmetric operations. A 128-bit security level is adequate.
The conclusions I have come to are:
* OpenSSL's P-256 is the fastest applicable open-source implementation
usable by a C library. Curve25519 implementations are inapplicable
because they don't do point addition. The curve math primitives of
current ed25519 implementations are not applicable because verifier
operations (such as double multiply) are not implemented in constant
* There may be some timing-channel pitfalls in nistz256 point
addition, but only in vanishingly unlikely cases (xG=wM, S=wN, w is
the order of the base point, etc.).
* On architectures where nistz256 is not implemented, a default
OpenSSL build will use the generic Weierstrass implementation. I
haven't been able to determine whether there are significant timing
channels in that implementation.
* There are likely timing channels in the serialization of scalars,
due to BIGNUM being variable-length. They might not be significant
enough to be exploitable.
> * On architectures where nistz256 is not implemented, a default
> OpenSSL build will use the generic Weierstrass implementation. I
> haven't been able to determine whether there are significant timing
> channels in that implementation.
Researches have been beating up "the generic Weierstrass
implementation" since 2009.