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
