summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMatthias Schiffer <mschiffer@universe-factory.net>2015-01-09 17:31:10 +0100
committerMatthias Schiffer <mschiffer@universe-factory.net>2015-01-09 17:31:10 +0100
commit68462604fa5441c692f9442f70ea30ac69252ae4 (patch)
tree91fb961143a4981e9ff1a0dbd375c1740e318a5c
parent7286aff2c39a52ab9a92a815dd54d21dd7ed6871 (diff)
downloadfastd-68462604fa5441c692f9442f70ea30ac69252ae4.tar
fastd-68462604fa5441c692f9442f70ea30ac69252ae4.zip
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.
-rw-r--r--src/protocols/ec25519_fhmqvc/ec25519_fhmqvc.c3
-rw-r--r--src/protocols/ec25519_fhmqvc/ec25519_fhmqvc.h23
-rw-r--r--src/protocols/ec25519_fhmqvc/handshake.c14
-rw-r--r--src/protocols/ec25519_fhmqvc/state.c13
4 files changed, 47 insertions, 6 deletions
diff --git a/src/protocols/ec25519_fhmqvc/ec25519_fhmqvc.c b/src/protocols/ec25519_fhmqvc/ec25519_fhmqvc.c
index 17f8268..97cdb3d 100644
--- a/src/protocols/ec25519_fhmqvc/ec25519_fhmqvc.c
+++ b/src/protocols/ec25519_fhmqvc/ec25519_fhmqvc.c
@@ -71,6 +71,9 @@ static fastd_protocol_config_t * protocol_init(void) {
ecc_25519_scalarmult_base(&work, &protocol_config->key.secret);
ecc_25519_store_packed(&protocol_config->key.public.int256, &work);
+ if (!divide_key(&protocol_config->key.secret))
+ exit_error("invalid secret key");
+
return protocol_config;
}
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);
+}
diff --git a/src/protocols/ec25519_fhmqvc/handshake.c b/src/protocols/ec25519_fhmqvc/handshake.c
index ee93e7a..b1c6242 100644
--- a/src/protocols/ec25519_fhmqvc/handshake.c
+++ b/src/protocols/ec25519_fhmqvc/handshake.c
@@ -192,7 +192,7 @@ static bool make_shared_handshake_key(bool initiator, const keypair_t *handshake
if (!ecc_25519_load_packed(&workXY, &peer_handshake_key->int256))
return false;
- if (!fastd_protocol_ec25519_fhmqvc_check_key(&workXY))
+ if (ecc_25519_is_identity(&workXY))
return false;
if (initiator) {
@@ -235,6 +235,18 @@ static bool make_shared_handshake_key(bool initiator, const keypair_t *handshake
}
ecc_25519_add(&work, &workXY, &work);
+
+ /*
+ Both our secret keys have been divided by 8 before, so we multiply
+ the point with 8 here to compensate.
+
+ By multiplying with 8, we prevent small-subgroup attacks (8 is the order
+ of the curves twist, see djb's Curve25519 paper). While the factor 8 should
+ be in the private keys anyways, the reduction modulo the subgroup order (in ecc_25519_gf_*)
+ will only preserve it if the point actually lies on our subgroup.
+ */
+ octuple_point(&work);
+
ecc_25519_scalarmult(&work, &s, &work);
if (ecc_25519_is_identity(&work))
diff --git a/src/protocols/ec25519_fhmqvc/state.c b/src/protocols/ec25519_fhmqvc/state.c
index 79bb6e2..cfb9028 100644
--- a/src/protocols/ec25519_fhmqvc/state.c
+++ b/src/protocols/ec25519_fhmqvc/state.c
@@ -46,12 +46,15 @@ static void init_protocol_state(void) {
/** Generates a new ephemeral keypair */
static void new_handshake_key(keypair_t *key) {
- fastd_random_bytes(key->secret.p, SECRETKEYBYTES, false);
- ecc_25519_gf_sanitize_secret(&key->secret, &key->secret);
+ fastd_random_bytes(key->secret.p, SECRETKEYBYTES, false);
+ ecc_25519_gf_sanitize_secret(&key->secret, &key->secret);
- ecc_25519_work_t work;
- ecc_25519_scalarmult_base(&work, &key->secret);
- ecc_25519_store_packed(&key->public.int256, &work);
+ ecc_25519_work_t work;
+ ecc_25519_scalarmult_base(&work, &key->secret);
+ ecc_25519_store_packed(&key->public.int256, &work);
+
+ if (!divide_key(&key->secret))
+ exit_bug("generated invalid ephemeral key");
}
/**