Merge remote-tracking branch 'yawning/feature16533'

5 files changed, 80 insertions, 50 deletions

diff --git a/changes/feature16533 b/changes/feature16533
new file mode 100644
index 0000000000..e9fea94c7e
--- /dev/null
+++ b/changes/feature16533
@@ -0,0 +1,4 @@
+  o Minor features (performance)
+    - Improve the runtime speed of Ed25519 signature verification by using
+      Ed25519-donna's batch verification support when there are a lot of
+      signatures to verify at once. Implements ticket 16533.
diff --git a/src/common/crypto.c b/src/common/crypto.c
index 2121383c75..6d4b0d7e16 100644
--- a/src/common/crypto.c
+++ b/src/common/crypto.c
@@ -2365,11 +2365,20 @@ crypto_seed_rng(void)
 }
 
 /** Write <b>n</b> bytes of strong random data to <b>to</b>. Return 0 on
- * success, -1 on failure.
+ * success, -1 on failure, with support for mocking for unit tests.
  */
 MOCK_IMPL(int,
 crypto_rand, (char *to, size_t n))
 {
+  return crypto_rand_unmocked(to, n);
+}
+
+/** Write <b>n</b> bytes of strong random data to <b>to</b>. Return 0 on
+ * success, -1 on failure.  Most callers will want crypto_rand instead.
+ */
+int
+crypto_rand_unmocked(char *to, size_t n)
+{
   int r;
   tor_assert(n < INT_MAX);
   tor_assert(to);
diff --git a/src/common/crypto.h b/src/common/crypto.h
index 368e9d8e32..6256f7346b 100644
--- a/src/common/crypto.h
+++ b/src/common/crypto.h
@@ -260,6 +260,7 @@ int crypto_expand_key_material_rfc5869_sha256(
 /* random numbers */
 int crypto_seed_rng(void);
 MOCK_DECL(int,crypto_rand,(char *to, size_t n));
+int crypto_rand_unmocked(char *to, size_t n);
 int crypto_strongest_rand(uint8_t *out, size_t out_len);
 int crypto_rand_int(unsigned int max);
 int crypto_rand_int_range(unsigned int min, unsigned int max);
diff --git a/src/common/crypto_ed25519.c b/src/common/crypto_ed25519.c
index 3a629322cb..7e995f4616 100644
--- a/src/common/crypto_ed25519.c
+++ b/src/common/crypto_ed25519.c
@@ -37,6 +37,8 @@ typedef struct {
               unsigned char *);
   int (*sign)(unsigned char *, const unsigned char *, size_t,
               const unsigned char *, const unsigned char *);
+  int (*open_batch)(const unsigned char **, size_t *, const unsigned char **,
+                    const unsigned char **, size_t, int *);
 
   int (*blind_secret_key)(unsigned char *, const unsigned char *,
                           const unsigned char *);
@@ -57,6 +59,7 @@ static const ed25519_impl_t impl_ref10 = {
 
   ed25519_ref10_open,
   ed25519_ref10_sign,
+  NULL,
 
   ed25519_ref10_blind_secret_key,
   ed25519_ref10_blind_public_key,
@@ -74,6 +77,7 @@ static const ed25519_impl_t impl_donna = {
 
   ed25519_donna_open,
   ed25519_donna_sign,
+  ed25519_sign_open_batch_donna,
 
   ed25519_donna_blind_secret_key,
   ed25519_donna_blind_public_key,
@@ -197,57 +201,69 @@ ed25519_checksig_batch(int *okay_out,
                        const ed25519_checkable_t *checkable,
                        int n_checkable)
 {
-  int res, i;
-
-  res = 0;
-  for (i = 0; i < n_checkable; ++i) {
-    const ed25519_checkable_t *ch = &checkable[i];
-    int r = ed25519_checksig(&ch->signature, ch->msg, ch->len, ch->pubkey);
-    if (r < 0)
-      --res;
-    if (okay_out)
-      okay_out[i] = (r == 0);
-  }
-
-#if 0
-  /* This is how we'd do it if we were using ed25519_donna.  I'll keep this
-   * code around here in case we ever do that. */
-  const uint8_t **ms;
-  size_t *lens;
-  const uint8_t **pks;
-  const uint8_t **sigs;
-  int *oks;
-
-  ms = tor_malloc(sizeof(uint8_t*)*n_checkable);
-  lens = tor_malloc(sizeof(size_t)*n_checkable);
-  pks = tor_malloc(sizeof(uint8_t*)*n_checkable);
-  sigs = tor_malloc(sizeof(uint8_t*)*n_checkable);
-  oks = okay_out ? okay_out : tor_malloc(sizeof(int)*n_checkable);
-
-  for (i = 0; i < n_checkable; ++i) {
-    ms[i] = checkable[i].msg;
-    lens[i] = checkable[i].len;
-    pks[i] = checkable[i].pubkey->pubkey;
-    sigs[i] = checkable[i].signature.sig;
-    oks[i] = 0;
-  }
-
-  ed25519_sign_open_batch_donna_fb(ms, lens, pks, sigs, n_checkable, oks);
+  int i, res;
+  const ed25519_impl_t *impl = get_ed_impl();
 
-  res = 0;
-  for (i = 0; i < n_checkable; ++i) {
-    /* XXX/yawning: Propagate to okay_out? */
-    if (!oks[i])
-      --res;
+  if (impl->open_batch == NULL) {
+    /* No batch verification implementation available, fake it by checking the
+     * each signature individually.
+     */
+    res = 0;
+    for (i = 0; i < n_checkable; ++i) {
+      const ed25519_checkable_t *ch = &checkable[i];
+      int r = ed25519_checksig(&ch->signature, ch->msg, ch->len, ch->pubkey);
+      if (r < 0)
+        --res;
+      if (okay_out)
+        okay_out[i] = (r == 0);
+    }
+  } else {
+    /* ed25519-donna style batch verification available.
+     *
+     * Theoretically, this should only be called if n_checkable >= 3, since
+     * that's the threshold where the batch verification actually kicks in,
+     * but the only difference is a few mallocs/frees.
+     */
+    const uint8_t **ms;
+    size_t *lens;
+    const uint8_t **pks;
+    const uint8_t **sigs;
+    int *oks;
+    int all_ok;
+
+    ms = tor_malloc(sizeof(uint8_t*)*n_checkable);
+    lens = tor_malloc(sizeof(size_t)*n_checkable);
+    pks = tor_malloc(sizeof(uint8_t*)*n_checkable);
+    sigs = tor_malloc(sizeof(uint8_t*)*n_checkable);
+    oks = okay_out ? okay_out : tor_malloc(sizeof(int)*n_checkable);
+
+    for (i = 0; i < n_checkable; ++i) {
+      ms[i] = checkable[i].msg;
+      lens[i] = checkable[i].len;
+      pks[i] = checkable[i].pubkey->pubkey;
+      sigs[i] = checkable[i].signature.sig;
+      oks[i] = 0;
+    }
+
+    res = 0;
+    all_ok = impl->open_batch(ms, lens, pks, sigs, n_checkable, oks);
+    for (i = 0; i < n_checkable; ++i) {
+      if (!oks[i])
+        --res;
+    }
+    /* XXX: For now sanity check oks with the return value.  Once we have
+     * more confidence in the code, if `all_ok == 0` we can skip iterating
+     * over oks since all the signatures were found to be valid.
+     */
+    tor_assert(((res == 0) && !all_ok) || ((res < 0) && all_ok));
+
+    tor_free(ms);
+    tor_free(lens);
+    tor_free(pks);
+    if (! okay_out)
+      tor_free(oks);
   }
 
-  tor_free(ms);
-  tor_free(lens);
-  tor_free(pks);
-  if (! okay_out)
-    tor_free(oks);
-#endif
-
   return res;
 }
 
diff --git a/src/ext/ed25519/donna/ed25519-randombytes-custom.h b/src/ext/ed25519/donna/ed25519-randombytes-custom.h
index e49368bbaf..3fb0959fc4 100644
--- a/src/ext/ed25519/donna/ed25519-randombytes-custom.h
+++ b/src/ext/ed25519/donna/ed25519-randombytes-custom.h
@@ -13,5 +13,5 @@
 static void
 ED25519_FN(ed25519_randombytes_unsafe) (void *p, size_t len)
 {
-  crypto_rand(p, len);
+  crypto_rand_unmocked(p, len);
 }