Merge remote-tracking branch 'yawning/feature16467_9663'

6 files changed, 327 insertions, 17 deletions

diff --git a/src/common/crypto.c b/src/common/crypto.c
index 934679e67a..88a23f5b14 100644
--- a/src/common/crypto.c
+++ b/src/common/crypto.c
@@ -25,6 +25,8 @@
 
 #define CRYPTO_PRIVATE
 #include "crypto.h"
+#include "crypto_curve25519.h"
+#include "crypto_ed25519.h"
 
 #if OPENSSL_VERSION_NUMBER < OPENSSL_V_SERIES(1,0,0)
 #error "We require OpenSSL >= 1.0.0"
@@ -305,6 +307,9 @@ crypto_early_init(void)
       return -1;
     if (crypto_init_siphash_key() < 0)
       return -1;
+
+    curve25519_init();
+    ed25519_init();
   }
   return 0;
 }
diff --git a/src/common/crypto_curve25519.c b/src/common/crypto_curve25519.c
index 5bb14b0d95..80b0d88952 100644
--- a/src/common/crypto_curve25519.c
+++ b/src/common/crypto_curve25519.c
@@ -14,6 +14,8 @@
 #include "util.h"
 #include "torlog.h"
 
+#include "ed25519/donna/ed25519_donna_tor.h"
+
 /* ==============================
    Part 1: wrap a suitable curve25519 implementation as curve25519_impl
    ============================== */
@@ -30,6 +32,10 @@ int curve25519_donna(uint8_t *mypublic,
 #endif
 #endif
 
+static void pick_curve25519_basepoint_impl(void);
+
+static int curve25519_use_ed = -1;
+
 STATIC int
 curve25519_impl(uint8_t *output, const uint8_t *secret,
                 const uint8_t *basepoint)
@@ -50,6 +56,34 @@ curve25519_impl(uint8_t *output, const uint8_t *secret,
   return r;
 }
 
+STATIC int
+curve25519_basepoint_impl(uint8_t *output, const uint8_t *secret)
+{
+  int r = 0;
+  if (PREDICT_UNLIKELY(curve25519_use_ed == -1)) {
+    pick_curve25519_basepoint_impl();
+  }
+
+  /* TODO: Someone should benchmark curved25519_scalarmult_basepoint versus
+   * an optimized NaCl build to see which should be used when compiled with
+   * NaCl available.  I suspected that the ed25519 optimization always wins.
+   */
+  if (PREDICT_LIKELY(curve25519_use_ed == 1)) {
+    curved25519_scalarmult_basepoint_donna(output, secret);
+    r = 0;
+  } else {
+    static const uint8_t basepoint[32] = {9};
+    r = curve25519_impl(output, secret, basepoint);
+  }
+  return r;
+}
+
+void
+curve25519_set_impl_params(int use_ed)
+{
+  curve25519_use_ed = use_ed;
+}
+
 /* ==============================
    Part 2: Wrap curve25519_impl with some convenience types and functions.
    ============================== */
@@ -113,9 +147,7 @@ void
 curve25519_public_key_generate(curve25519_public_key_t *key_out,
                                const curve25519_secret_key_t *seckey)
 {
-  static const uint8_t basepoint[32] = {9};
-
-  curve25519_impl(key_out->public_key, seckey->secret_key, basepoint);
+  curve25519_basepoint_impl(key_out->public_key, seckey->secret_key);
 }
 
 int
@@ -283,3 +315,84 @@ curve25519_handshake(uint8_t *output,
   curve25519_impl(output, skey->secret_key, pkey->public_key);
 }
 
+/** Check whether the ed25519-based curve25519 basepoint optimization seems to
+ * be working. If so, return 0; otherwise return -1. */
+static int
+curve25519_basepoint_spot_check(void)
+{
+  static const uint8_t alicesk[32] = {
+    0x77,0x07,0x6d,0x0a,0x73,0x18,0xa5,0x7d,
+    0x3c,0x16,0xc1,0x72,0x51,0xb2,0x66,0x45,
+    0xdf,0x4c,0x2f,0x87,0xeb,0xc0,0x99,0x2a,
+    0xb1,0x77,0xfb,0xa5,0x1d,0xb9,0x2c,0x2a
+  };
+  static const uint8_t alicepk[32] = {
+    0x85,0x20,0xf0,0x09,0x89,0x30,0xa7,0x54,
+    0x74,0x8b,0x7d,0xdc,0xb4,0x3e,0xf7,0x5a,
+    0x0d,0xbf,0x3a,0x0d,0x26,0x38,0x1a,0xf4,
+    0xeb,0xa4,0xa9,0x8e,0xaa,0x9b,0x4e,0x6a
+  };
+  const int loop_max=200;
+  int save_use_ed = curve25519_use_ed;
+  unsigned char e1[32] = { 5 };
+  unsigned char e2[32] = { 5 };
+  unsigned char x[32],y[32];
+  int i;
+  int r=0;
+
+  /* Check the most basic possible sanity via the test secret/public key pair
+   * used in "Cryptography in NaCl - 2. Secret keys and public keys".  This
+   * may catch catastrophic failures on systems where Curve25519 is expensive, 
+   * without requiring a ton of key generation.
+   */
+  curve25519_use_ed = 1;
+  r |= curve25519_basepoint_impl(x, alicesk);
+  if (fast_memneq(x, alicepk, 32))
+    goto fail;
+
+  /* Ok, the optimization appears to produce passable results, try a few more
+   * values, maybe there's something subtle wrong.
+   */
+  for (i = 0; i < loop_max; ++i) {
+    curve25519_use_ed = 0;
+    r |= curve25519_basepoint_impl(x, e1);
+    curve25519_use_ed = 1;
+    r |= curve25519_basepoint_impl(y, e2);
+    if (fast_memneq(x,y,32))
+      goto fail;
+    memcpy(e1, x, 32);
+    memcpy(e2, x, 32);
+  }
+
+  goto end;
+ fail:
+  r = -1;
+ end:
+  curve25519_use_ed = save_use_ed;
+  return r;
+}
+
+/** Choose whether to use the ed25519-based curve25519-basepoint
+ * implementation. */
+static void
+pick_curve25519_basepoint_impl(void)
+{
+  curve25519_use_ed = 1;
+
+  if (curve25519_basepoint_spot_check() == 0)
+    return;
+
+  log_warn(LD_CRYPTO, "The ed25519-based curve25519 basepoint "
+           "multiplication seems broken; using the curve25519 "
+           "implementation.");
+  curve25519_use_ed = 0;
+}
+
+/** Initialize the curve25519 implementations. This is necessary if you're
+ * going to use them in a multithreaded setting, and not otherwise. */
+void
+curve25519_init(void)
+{
+  pick_curve25519_basepoint_impl();
+}
+
diff --git a/src/common/crypto_curve25519.h b/src/common/crypto_curve25519.h
index 48e8a6d962..d53743986c 100644
--- a/src/common/crypto_curve25519.h
+++ b/src/common/crypto_curve25519.h
@@ -61,6 +61,8 @@ int curve25519_rand_seckey_bytes(uint8_t *out, int extra_strong);
 #ifdef CRYPTO_CURVE25519_PRIVATE
 STATIC int curve25519_impl(uint8_t *output, const uint8_t *secret,
                            const uint8_t *basepoint);
+
+STATIC int curve25519_basepoint_impl(uint8_t *output, const uint8_t *secret);
 #endif
 
 #define CURVE25519_BASE64_PADDED_LEN 44
@@ -82,5 +84,8 @@ ssize_t crypto_read_tagged_contents_from_file(const char *fname,
                                               uint8_t *data_out,
                                               ssize_t data_out_len);
 
+void curve25519_set_impl_params(int use_ed);
+void curve25519_init(void);
+
 #endif
 
diff --git a/src/common/crypto_ed25519.c b/src/common/crypto_ed25519.c
index 6b93751dda..599a1ca9b7 100644
--- a/src/common/crypto_ed25519.c
+++ b/src/common/crypto_ed25519.c
@@ -16,9 +16,81 @@
 #include "util.h"
 
 #include "ed25519/ref10/ed25519_ref10.h"
+#include "ed25519/donna/ed25519_donna_tor.h"
 
 #include <openssl/sha.h>
 
+static void pick_ed25519_impl(void);
+static int ed25519_impl_spot_check(void);
+
+/** An Ed25519 implementation */
+typedef struct {
+  int (*selftest)(void);
+
+  int (*seckey)(unsigned char *);
+  int (*seckey_expand)(unsigned char *, const unsigned char *);
+  int (*pubkey)(unsigned char *, const unsigned char *);
+  int (*keygen)(unsigned char *, unsigned char *);
+
+  int (*open)(const unsigned char *, const unsigned char *, size_t, const
+              unsigned char *);
+  int (*sign)(unsigned char *, const unsigned char *, size_t,
+              const unsigned char *, const unsigned char *);
+
+  int (*blind_secret_key)(unsigned char *, const unsigned char *,
+                          const unsigned char *);
+  int (*blind_public_key)(unsigned char *, const unsigned char *,
+                          const unsigned char *);
+
+  int (*pubkey_from_curve25519_pubkey)(unsigned char *, const unsigned char *,
+                                       int);
+} ed25519_impl_t;
+
+static const ed25519_impl_t impl_ref10 = {
+  NULL,
+
+  ed25519_ref10_seckey,
+  ed25519_ref10_seckey_expand,
+  ed25519_ref10_pubkey,
+  ed25519_ref10_keygen,
+
+  ed25519_ref10_open,
+  ed25519_ref10_sign,
+
+  ed25519_ref10_blind_secret_key,
+  ed25519_ref10_blind_public_key,
+
+  ed25519_ref10_pubkey_from_curve25519_pubkey,
+};
+
+static const ed25519_impl_t impl_donna = {
+  ed25519_donna_selftest,
+
+  ed25519_donna_seckey,
+  ed25519_donna_seckey_expand,
+  ed25519_donna_pubkey,
+  ed25519_donna_keygen,
+
+  ed25519_donna_open,
+  ed25519_donna_sign,
+
+  ed25519_donna_blind_secret_key,
+  ed25519_donna_blind_public_key,
+
+  ed25519_donna_pubkey_from_curve25519_pubkey,
+};
+
+static const ed25519_impl_t *ed25519_impl = NULL;
+
+static inline const ed25519_impl_t *
+get_ed_impl(void)
+{
+  if (PREDICT_UNLIKELY(ed25519_impl == NULL)) {
+    pick_ed25519_impl();
+  }
+  return ed25519_impl;
+}
+
 /**
  * Initialize a new ed25519 secret key in <b>seckey_out</b>.  If
  * <b>extra_strong</b>, take the RNG inputs directly from the operating
@@ -33,7 +105,7 @@ ed25519_secret_key_generate(ed25519_secret_key_t *seckey_out,
   if (! extra_strong || crypto_strongest_rand(seed, sizeof(seed)) < 0)
     crypto_rand((char*)seed, sizeof(seed));
 
-  r = ed25519_ref10_seckey_expand(seckey_out->seckey, seed);
+  r = get_ed_impl()->seckey_expand(seckey_out->seckey, seed);
   memwipe(seed, 0, sizeof(seed));
 
   return r < 0 ? -1 : 0;
@@ -47,8 +119,8 @@ int
 ed25519_secret_key_from_seed(ed25519_secret_key_t *seckey_out,
                              const uint8_t *seed)
 {
-  if (ed25519_ref10_seckey_expand(seckey_out->seckey, seed) < 0)
-    return -1;
+  if (get_ed_impl()->seckey_expand(seckey_out->seckey, seed) < 0)
+     return -1;
   return 0;
 }
 
@@ -60,7 +132,7 @@ int
 ed25519_public_key_generate(ed25519_public_key_t *pubkey_out,
                         const ed25519_secret_key_t *seckey)
 {
-  if (ed25519_ref10_pubkey(pubkey_out->pubkey, seckey->seckey) < 0)
+  if (get_ed_impl()->pubkey(pubkey_out->pubkey, seckey->seckey) < 0)
     return -1;
   return 0;
 }
@@ -88,10 +160,9 @@ ed25519_sign(ed25519_signature_t *signature_out,
              const uint8_t *msg, size_t len,
              const ed25519_keypair_t *keypair)
 {
-
-  if (ed25519_ref10_sign(signature_out->sig, msg, len,
-                         keypair->seckey.seckey,
-                         keypair->pubkey.pubkey) < 0) {
+  if (get_ed_impl()->sign(signature_out->sig, msg, len,
+                          keypair->seckey.seckey,
+                          keypair->pubkey.pubkey) < 0) {
     return -1;
   }
 
@@ -110,7 +181,7 @@ ed25519_checksig(const ed25519_signature_t *signature,
                  const ed25519_public_key_t *pubkey)
 {
   return
-    ed25519_ref10_open(signature->sig, msg, len, pubkey->pubkey) < 0 ? -1 : 0;
+    get_ed_impl()->open(signature->sig, msg, len, pubkey->pubkey) < 0 ? -1 : 0;
 }
 
 /** Validate every signature among those in <b>checkable</b>, which contains
@@ -164,6 +235,7 @@ ed25519_checksig_batch(int *okay_out,
 
   res = 0;
   for (i = 0; i < n_checkable; ++i) {
+    /* XXX/yawning: Propagate to okay_out? */
     if (!oks[i])
       --res;
   }
@@ -229,9 +301,9 @@ ed25519_public_key_from_curve25519_public_key(ed25519_public_key_t *pubkey,
                                      const curve25519_public_key_t *pubkey_in,
                                      int signbit)
 {
-  return ed25519_ref10_pubkey_from_curve25519_pubkey(pubkey->pubkey,
-                                                     pubkey_in->public_key,
-                                                     signbit);
+  return get_ed_impl()->pubkey_from_curve25519_pubkey(pubkey->pubkey,
+                                                      pubkey_in->public_key,
+                                                      signbit);
 }
 
 /**
@@ -251,7 +323,7 @@ ed25519_keypair_blind(ed25519_keypair_t *out,
 {
   ed25519_public_key_t pubkey_check;
 
-  ed25519_ref10_blind_secret_key(out->seckey.seckey,
+  get_ed_impl()->blind_secret_key(out->seckey.seckey,
                                   inp->seckey.seckey, param);
 
   ed25519_public_blind(&pubkey_check, &inp->pubkey, param);
@@ -274,7 +346,7 @@ ed25519_public_blind(ed25519_public_key_t *out,
                      const ed25519_public_key_t *inp,
                      const uint8_t *param)
 {
-  ed25519_ref10_blind_public_key(out->pubkey, inp->pubkey, param);
+  get_ed_impl()->blind_public_key(out->pubkey, inp->pubkey, param);
   return 0;
 }
 
@@ -372,3 +444,114 @@ ed25519_pubkey_eq(const ed25519_public_key_t *key1,
   return tor_memeq(key1->pubkey, key2->pubkey, ED25519_PUBKEY_LEN);
 }
 
+/** Check whether the given Ed25519 implementation seems to be working.
+ * If so, return 0; otherwise return -1. */
+static int
+ed25519_impl_spot_check(void)
+{
+  static const uint8_t alicesk[32] = {
+    0xc5,0xaa,0x8d,0xf4,0x3f,0x9f,0x83,0x7b,
+    0xed,0xb7,0x44,0x2f,0x31,0xdc,0xb7,0xb1,
+    0x66,0xd3,0x85,0x35,0x07,0x6f,0x09,0x4b,
+    0x85,0xce,0x3a,0x2e,0x0b,0x44,0x58,0xf7
+  };
+  static const uint8_t alicepk[32] = {
+    0xfc,0x51,0xcd,0x8e,0x62,0x18,0xa1,0xa3,
+    0x8d,0xa4,0x7e,0xd0,0x02,0x30,0xf0,0x58,
+    0x08,0x16,0xed,0x13,0xba,0x33,0x03,0xac,
+    0x5d,0xeb,0x91,0x15,0x48,0x90,0x80,0x25
+  };
+  static const uint8_t alicemsg[2] = { 0xaf, 0x82 };
+  static const uint8_t alicesig[64] = {
+    0x62,0x91,0xd6,0x57,0xde,0xec,0x24,0x02,
+    0x48,0x27,0xe6,0x9c,0x3a,0xbe,0x01,0xa3,
+    0x0c,0xe5,0x48,0xa2,0x84,0x74,0x3a,0x44,
+    0x5e,0x36,0x80,0xd7,0xdb,0x5a,0xc3,0xac,
+    0x18,0xff,0x9b,0x53,0x8d,0x16,0xf2,0x90,
+    0xae,0x67,0xf7,0x60,0x98,0x4d,0xc6,0x59,
+    0x4a,0x7c,0x15,0xe9,0x71,0x6e,0xd2,0x8d,
+    0xc0,0x27,0xbe,0xce,0xea,0x1e,0xc4,0x0a
+  };
+  const ed25519_impl_t *impl = get_ed_impl();
+  uint8_t sk[ED25519_SECKEY_LEN];
+  uint8_t pk[ED25519_PUBKEY_LEN];
+  uint8_t sig[ED25519_SIG_LEN];
+  int r = 0;
+
+  /* Some implementations (eg: The modified Ed25519-donna) have handy self-test
+   * code that sanity-checks the internals.  If present, use that to screen out
+   * catastrophic errors like massive compiler failure.
+   */
+  if (impl->selftest && impl->selftest() != 0)
+    goto fail;
+
+  /* Validate results versus known answer tests.  People really should be
+   * running "make test" instead of relying on this, but it's better than
+   * nothing.
+   *
+   * Test vectors taken from "EdDSA & Ed25519 - 6. Test Vectors for Ed25519
+   * (TEST3)" (draft-josefsson-eddsa-ed25519-03).
+   */
+
+  /* Key expansion, public key derivation. */
+  if (impl->seckey_expand(sk, alicesk) < 0)
+    goto fail;
+  if (impl->pubkey(pk, sk) < 0)
+    goto fail;
+  if (fast_memneq(pk, alicepk, ED25519_PUBKEY_LEN))
+    goto fail;
+
+  /* Signing, verification. */
+  if (impl->sign(sig, alicemsg, sizeof(alicemsg), sk, pk) < 0)
+    return -1;
+  if (fast_memneq(sig, alicesig, ED25519_SIG_LEN))
+    return -1;
+  if (impl->open(sig, alicemsg, sizeof(alicemsg), pk) < 0)
+    return -1;
+
+  /* XXX/yawning: Someone that's more paranoid than I am, can write "Assume
+   * ref0 is cannonical, and fuzz impl against it" if they want, but I doubt
+   * that will catch anything that the known answer tests won't.
+   */
+  goto end;
+
+ fail:
+  r = -1;
+ end:
+  return r;
+}
+
+/** Force the Ed25519 implementation to a given one, without sanity checking
+ * the output.  Used for testing.
+ */
+void
+ed25519_set_impl_params(int use_donna)
+{
+  if (use_donna)
+    ed25519_impl = &impl_donna;
+  else
+    ed25519_impl = &impl_ref10;
+}
+
+/** Choose whether to use the Ed25519-donna implementation. */
+static void
+pick_ed25519_impl(void)
+{
+  ed25519_impl = &impl_donna;
+
+  if (ed25519_impl_spot_check() == 0)
+    return;
+
+  log_warn(LD_CRYPTO, "The Ed25519-donna implementation seems broken; using "
+           "the ref10 implementation.");
+  ed25519_impl = &impl_ref10;
+}
+
+/* Initialize the Ed25519 implementation. This is neccessary if you're
+ * going to use them in a multithreaded setting, and not otherwise. */
+void
+ed25519_init(void)
+{
+  pick_ed25519_impl();
+}
+
diff --git a/src/common/crypto_ed25519.h b/src/common/crypto_ed25519.h
index 4d20406d06..d942461cfe 100644
--- a/src/common/crypto_ed25519.h
+++ b/src/common/crypto_ed25519.h
@@ -123,5 +123,8 @@ void ed25519_keypair_free(ed25519_keypair_t *kp);
 int ed25519_pubkey_eq(const ed25519_public_key_t *key1,
                       const ed25519_public_key_t *key2);
 
+void ed25519_set_impl_params(int use_donna);
+void ed25519_init(void);
+
 #endif
 
diff --git a/src/common/include.am b/src/common/include.am
index 789f4003c9..de93131615 100644
--- a/src/common/include.am
+++ b/src/common/include.am
@@ -43,6 +43,7 @@ endif
 endif
 
 LIBDONNA += $(LIBED25519_REF10)
+LIBDONNA += $(LIBED25519_DONNA)
 
 if THREADS_PTHREADS
 threads_impl_source=src/common/compat_pthreads.c