[openssl-users] Elliptic curve implementation sanity check

[Greg Hudson]

I am working on implementing the SPAKE2 algorithm[1] 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
  time.

* 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.

Does that all seem correct?

[1] https://tools.ietf.org/html/draft-irtf-cfrg-spake2