ec25519-fhmqvc: optimize handshake by using embedded group element verification

Using the embedded group element verification allows us to get away without
explicit verification, thus needing one scalar multiplication less. This reduces
the number of expensive operations needed for a handshake to three: one Galois
field square root (for key unpacking) and two scalar multiplications.

For this optimization to be secure, private keys must be divisible by 8. This is
the case for all keys generated with all but extremely old versions of fastd
(pre-0.4). If fastd finds that its secret is not divisible by 8, it will refuse
to start now.

1 files changed, 23 insertions, 0 deletions

diff --git a/src/protocols/ec25519_fhmqvc/ec25519_fhmqvc.h b/src/protocols/ec25519_fhmqvc/ec25519_fhmqvc.h
index 8dd8456..e2034bd 100644
--- a/src/protocols/ec25519_fhmqvc/ec25519_fhmqvc.h
+++ b/src/protocols/ec25519_fhmqvc/ec25519_fhmqvc.h
@@ -138,3 +138,26 @@ static inline void hexdump(char out[65], const unsigned char d[32]) {
 static inline bool is_session_valid(const protocol_session_t *session) {
 	return (session->method && session->method->provider->session_is_valid(session->method_state));
 }
+
+
+/** Devides a secret key by 8 (for some optimizations) */
+static inline bool divide_key(ecc_int256_t *key) {
+	uint8_t c = 0, c2;
+	ssize_t i;
+
+	for (i = 31; i >= 0; i--) {
+		c2 = key->p[i] << 5;
+		key->p[i] = (key->p[i] >> 3) | c;
+		c = c2;
+	}
+
+	return (c == 0);
+}
+
+/** Multiplies a point by 8 */
+static inline void octuple_point(ecc_25519_work_t *p) {
+	ecc_25519_work_t work;
+	ecc_25519_double(&work, p);
+	ecc_25519_double(&work, &work);
+	ecc_25519_double(p, &work);
+}