Add a wrapper around, and test and build support for, curve25519.

We want to use donna-c64 when we have a GCC with support for
64x64->uint128_t multiplying.  If not, we want to use libnacl if we
can, unless it's giving us the unsafe "ref" implementation.  And if
that isn't going to work, we'd like to use the
portable-and-safe-but-slow 32-bit "donna" implementation.

We might need more library searching for the correct libnacl,
especially once the next libnacl release is out -- it's likely to have
bunches of better curve25519 implementations.

I also define a set of curve25519 wrapper functions, though it really
shouldn't be necessary.

We should eventually make the -donna*.c files get build with
-fomit-frame-pointer, since that can make a difference.

5 files changed, 331 insertions, 1 deletions

diff --git a/configure.ac b/configure.ac
index 9963a97d4..927283435 100644
--- a/configure.ac
+++ b/configure.ac
@@ -36,6 +36,8 @@ AC_ARG_ENABLE(static-zlib,
    AS_HELP_STRING(--enable-static-zlib, Link against a static zlib library. Requires --with-zlib-dir))
 AC_ARG_ENABLE(static-tor,
    AS_HELP_STRING(--enable-static-tor, Create an entirely static Tor binary. Requires --with-openssl-dir and --with-libevent-dir and --with-zlib-dir))
+AC_ARG_ENABLE(curve25519,
+   AS_HELP_STRING(--disable-curve25519, Build Tor with no curve25519 elliptic-curve crypto support))
 
 if test "$enable_static_tor" = "yes"; then
   enable_static_libevent="yes";
@@ -638,6 +640,103 @@ if test "$upnp" = "true"; then
     fi
 fi
 
+dnl ============================================================
+dnl We need an implementation of curve25519.
+
+dnl set these defaults.
+have_a_curve25519=no
+build_curve25519_donna=no
+build_curve25519_donna_c64=no
+use_curve25519_donna=no
+use_curve25519_nacl=no
+CURVE25519_LIBS=
+
+if test x$enable_curve25519 != xno; then
+
+  dnl The best choice is using curve25519-donna-c64, but that requires
+  dnl that we
+  AC_CACHE_CHECK([whether we can use curve25519-donna-c64],
+    tor_cv_can_use_curve25519_donna_c64,
+    [AC_RUN_IFELSE(
+      [AC_LANG_PROGRAM([dnl
+        #include <stdint.h>
+        typedef unsigned uint128_t __attribute__((mode(TI)));
+	], [dnl
+          uint64_t a = ((uint64_t)2000000000) * 1000000000;
+	  uint64_t b = ((uint64_t)1234567890) << 24;
+	  uint128_t c = ((uint128_t)a) * b;
+	  return ((uint64_t)(c>>96)) == 522859 &&
+	         ((uint64_t)(c>>64))&0xffffffffL == 3604448702L &&
+                 ((uint64_t)(c>>32))&0xffffffffL == 2351960064L &&
+                 ((uint64_t)(c))&0xffffffffL == 0;
+        ])],
+	[tor_cv_can_use_curve25519_donna_c64=yes],
+        [tor_cv_can_use_curve25519_donna_c64=no],
+	[AC_COMPILE_IFELSE(
+          [AC_LANG_PROGRAM([dnl
+            #include <stdint.h>
+            typedef unsigned uint128_t __attribute__((mode(TI)));
+            ], [dnl
+              uint64_t a = ((uint64_t)2000000000) * 1000000000;
+	      uint64_t b = ((uint64_t)1234567890) << 24;
+	      uint128_t c = ((uint128_t)a) * b;
+	      return ((uint64_t)(c>>96)) == 522859 &&
+	             ((uint64_t)(c>>64))&0xffffffffL == 3604448702L &&
+                     ((uint64_t)(c>>32))&0xffffffffL == 2351960064L &&
+                     ((uint64_t)(c))&0xffffffffL == 0;
+            ])],
+            [tor_cv_can_use_curve25519_donna_c64=cross],
+	    [tor_cv_can_use_curve25519_donna_c64=no])])])
+
+  AC_CACHE_CHECK([whether we can use curve25519 from nacl],
+    tor_cv_can_use_curve25519_nacl,
+    [tor_saved_LIBS="$LIBS"
+     LIBS="$LIBS -lnacl"
+     AC_LINK_IFELSE(
+       [AC_LANG_PROGRAM([dnl
+         #include <crypto_scalarmult_curve25519.h>
+         #ifdef crypto_scalarmult_curve25519_ref_BYTES
+	 #error Hey, this is the reference implementation!
+	 #endif
+       ], [
+	 unsigned char *a, *b, *c; crypto_scalarmult_curve25519(a,b,c);
+       ])], [tor_cv_can_use_curve25519_nacl=yes],
+       [tor_cv_can_use_curve25519_nacl=no])
+     LIBS="$tor_saved_LIBS" ])
+
+   dnl Okay, now we need to figure out which one to actually use. Fall back
+   dnl to curve25519-donna.c
+
+   if test x$tor_cv_can_use_curve25519_donna_c64 != xno; then
+     build_curve25519_donna_c64=yes
+     use_curve25519_donna=yes
+   elif test x$tor_cv_can_use_curve25519_nacl = xyes; then
+     use_curve25519_nacl=yes
+     CURVE25519_LIBS=-lnacl
+   else
+     build_curve25519_donna=yes
+     use_curve25519_donna=yes
+   fi
+   have_a_curve25519=yes
+fi
+
+if test x$have_a_curve25519 = xyes; then
+  AC_DEFINE(CURVE25519_ENABLED, 1,
+            [Defined if we have a curve25519 implementation])
+fi
+if test x$use_curve25519_donna = xyes; then
+  AC_DEFINE(USE_CURVE25519_DONNA, 1,
+            [Defined if we should use an internal curve25519_donna{,_c64} implementation])
+fi
+if test x$use_curve25519_nacl = xyes; then
+  AC_DEFINE(USE_CURVE25519_NACL, 1,
+            [Defined if we should use a curve25519 from nacl])
+fi
+AM_CONDITIONAL(BUILD_CURVE25519_DONNA, test x$build_curve25519_donna = xyes)
+AM_CONDITIONAL(BUILD_CURVE25519_DONNA_C64, test x$build_curve25519_donna_c64 = xyes)
+AM_CONDITIONAL(CURVE25519_ENABLED, test x$have_a_curve25519 = xyes)
+AC_SUBST(CURVE25519_LIBS)
+
 dnl Make sure to enable support for large off_t if available.
 AC_SYS_LARGEFILE
 
diff --git a/src/common/crypto_curve25519.c b/src/common/crypto_curve25519.c
new file mode 100644
index 000000000..1985e8af2
--- /dev/null
+++ b/src/common/crypto_curve25519.c
@@ -0,0 +1,88 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/* Wrapper code for a curve25519 implementation. */
+
+#define CRYPTO_CURVE25519_PRIVATE
+#include "orconfig.h"
+#include "crypto.h"
+#include "crypto_curve25519.h"
+#include "util.h"
+
+/* ==============================
+   Part 1: wrap a suitable curve25519 implementation as curve25519_impl
+   ============================== */
+
+#ifdef USE_CURVE25519_DONNA
+int curve25519_donna(uint8_t *mypublic,
+                     const uint8_t *secret, const uint8_t *basepoint);
+#endif
+#ifdef USE_CURVE25519_NACL
+#include <crypto_scalarmult_curve25519.h>
+#endif
+
+int
+curve25519_impl(uint8_t *output, const uint8_t *secret,
+                const uint8_t *basepoint)
+{
+#ifdef USE_CURVE25519_DONNA
+  return curve25519_donna(output, secret, basepoint);
+#elif defined(USE_CURVE25519_NACL)
+  return crypto_scalarmult_curve25519(output, secret, basepoint);
+#else
+#error "No implementation of curve25519 is available."
+#endif
+}
+
+/* ==============================
+   Part 2: Wrap curve25519_impl with some convenience types and functions.
+   ============================== */
+
+/**
+ * Return true iff a curve25519_public_key_t seems valid. (It's not necessary
+ * to see if the point is on the curve, since the twist is also secure, but we
+ * do need to make sure that it isn't the point at infinity.) */
+int
+curve25519_public_key_is_ok(const curve25519_public_key_t *key)
+{
+  static const uint8_t zero[] =
+    "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
+    "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
+
+  return tor_memneq(key->public_key, zero, CURVE25519_PUBKEY_LEN);
+}
+
+/** Generate a new keypair and return the secret key.  If <b>extra_strong</b>
+ * is true, this key is possibly going to get used more than once, so
+ * use a better-than-usual RNG. */
+void
+curve25519_secret_key_generate(curve25519_secret_key_t *key_out,
+                               int extra_strong)
+{
+  (void)extra_strong;
+
+  crypto_rand((char*)key_out->secret_key, 32);
+  key_out->secret_key[0] &= 248;
+  key_out->secret_key[31] &= 127;
+  key_out->secret_key[31] |= 64;
+}
+
+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);
+}
+
+/** Perform the curve25519 ECDH handshake with <b>skey</b> and <b>pkey</b>,
+ * writing CURVE25519_OUTPUT_LEN bytes of output into <b>output</b>. */
+void
+curve25519_handshake(uint8_t *output,
+                     const curve25519_secret_key_t *skey,
+                     const curve25519_public_key_t *pkey)
+{
+  curve25519_impl(output, skey->secret_key, pkey->public_key);
+}
+
diff --git a/src/common/crypto_curve25519.h b/src/common/crypto_curve25519.h
new file mode 100644
index 000000000..3e093be7b
--- /dev/null
+++ b/src/common/crypto_curve25519.h
@@ -0,0 +1,43 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_CRYPTO_CURVE25519_H
+#define TOR_CRYPTO_CURVE25519_H
+
+#include "torint.h"
+
+/** Length of a curve25519 public key when encoded. */
+#define CURVE25519_PUBKEY_LEN 32
+/** Length of a curve25519 secret key when encoded. */
+#define CURVE25519_SECKEY_LEN 32
+/** Length of the result of a curve25519 handshake. */
+#define CURVE25519_OUTPUT_LEN 32
+
+/** Wrapper type for a curve25519 public key */
+typedef struct curve25519_public_key_t {
+  uint8_t public_key[CURVE25519_PUBKEY_LEN];
+} curve25519_public_key_t;
+
+/** Wrapper type for a curve25519 secret key */
+typedef struct curve25519_secret_key_t {
+  uint8_t secret_key[CURVE25519_SECKEY_LEN];
+} curve25519_secret_key_t;
+
+int curve25519_public_key_is_ok(const curve25519_public_key_t *);
+
+void curve25519_secret_key_generate(curve25519_secret_key_t *key_out,
+                                    int extra_strong);
+void curve25519_public_key_generate(curve25519_public_key_t *key_out,
+                                    const curve25519_secret_key_t *seckey);
+
+void curve25519_handshake(uint8_t *output,
+                          const curve25519_secret_key_t *,
+                          const curve25519_public_key_t *);
+
+#ifdef CRYPTO_CURVE25519_PRIVATE
+int curve25519_impl(uint8_t *output, const uint8_t *secret,
+                    const uint8_t *basepoint);
+#endif
+
+#endif
+
diff --git a/src/common/include.am b/src/common/include.am
index 0fdc72057..f986ba66d 100644
--- a/src/common/include.am
+++ b/src/common/include.am
@@ -14,6 +14,22 @@ else
 libor_extra_source=
 endif
 
+if BUILD_CURVE25519_DONNA
+libcrypto_extra_source= \
+	src/ext/curve25519_donna/curve25519-donna.c \
+	src/common/crypto_curve25519.c
+else
+if BUILD_CURVE25519_DONNA_C64
+libcrypto_extra_source= \
+	src/ext/curve25519_donna/curve25519-donna-c64.c \
+	src/common/crypto_curve25519.c
+else
+if CURVE25519_ENABLED
+libcrypto_extra_source=src/common/crypto_curve25519.c
+endif
+endif
+endif
+
 src_common_libor_a_SOURCES = \
   src/common/address.c					\
   src/common/compat.c					\
@@ -31,7 +47,8 @@ src_common_libor_crypto_a_SOURCES = \
   src/common/aes.c		\
   src/common/crypto.c		\
   src/common/torgzip.c		\
-  src/common/tortls.c
+  src/common/tortls.c		\
+  $(libcrypto_extra_source)
 
 src_common_libor_event_a_SOURCES = src/common/compat_libevent.c
 
@@ -43,6 +60,7 @@ COMMONHEADERS = \
   src/common/compat_libevent.h			\
   src/common/container.h			\
   src/common/crypto.h				\
+  src/common/crypto_curve25519.h		\
   src/common/di_ops.h				\
   src/common/memarea.h				\
   src/common/mempool.h				\
diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c
index 28e293743..8aadd979a 100644
--- a/src/test/test_crypto.c
+++ b/src/test/test_crypto.c
@@ -5,9 +5,13 @@
 
 #include "orconfig.h"
 #define CRYPTO_PRIVATE
+#define CRYPTO_CURVE25519_PRIVATE
 #include "or.h"
 #include "test.h"
 #include "aes.h"
+#ifdef CURVE25519_ENABLED
+#include "crypto_curve25519.h"
+#endif
 
 /** Run unit tests for Diffie-Hellman functionality. */
 static void
@@ -929,6 +933,80 @@ test_crypto_hkdf_sha256(void *arg)
 #undef EXPAND
 }
 
+#ifdef CURVE25519_ENABLED
+static void
+test_crypto_curve25519_impl(void *arg)
+{
+  /* adapted from curve25519_donna, which adapted it from test-curve25519
+     version 20050915, by D. J. Bernstein, Public domain. */
+
+  unsigned char e1k[32];
+  unsigned char e2k[32];
+  unsigned char e1e2k[32];
+  unsigned char e2e1k[32];
+  unsigned char e1[32] = {3};
+  unsigned char e2[32] = {5};
+  unsigned char k[32] = {9};
+  int loop, i;
+  const int loop_max=10000;
+  char *mem_op_hex_tmp = NULL;
+
+  (void)arg;
+
+  for (loop = 0; loop < loop_max; ++loop) {
+    curve25519_impl(e1k,e1,k);
+    curve25519_impl(e2e1k,e2,e1k);
+    curve25519_impl(e2k,e2,k);
+    curve25519_impl(e1e2k,e1,e2k);
+    test_memeq(e1e2k, e2e1k, 32);
+    if (loop == loop_max-1) {
+      break;
+    }
+    for (i = 0;i < 32;++i) e1[i] ^= e2k[i];
+    for (i = 0;i < 32;++i) e2[i] ^= e1k[i];
+    for (i = 0;i < 32;++i) k[i] ^= e1e2k[i];
+  }
+
+  test_memeq_hex(e1,
+                 "4faf81190869fd742a33691b0e0824d5"
+                 "7e0329f4dd2819f5f32d130f1296b500");
+  test_memeq_hex(e2k,
+                 "05aec13f92286f3a781ccae98995a3b9"
+                 "e0544770bc7de853b38f9100489e3e79");
+  test_memeq_hex(e1e2k,
+                 "cd6e8269104eb5aaee886bd2071fba88"
+                 "bd13861475516bc2cd2b6e005e805064");
+
+ done:
+  tor_free(mem_op_hex_tmp);
+}
+
+static void
+test_crypto_curve25519_wrappers(void *arg)
+{
+  curve25519_public_key_t pubkey1, pubkey2;
+  curve25519_secret_key_t seckey1, seckey2;
+
+  uint8_t output1[CURVE25519_OUTPUT_LEN];
+  uint8_t output2[CURVE25519_OUTPUT_LEN];
+  (void)arg;
+
+  /* Test a simple handshake, serializing and deserializing some stuff. */
+  curve25519_secret_key_generate(&seckey1, 0);
+  curve25519_secret_key_generate(&seckey2, 0);
+  curve25519_public_key_generate(&pubkey1, &seckey1);
+  curve25519_public_key_generate(&pubkey2, &seckey2);
+  test_assert(curve25519_public_key_is_ok(&pubkey1));
+  test_assert(curve25519_public_key_is_ok(&pubkey2));
+  curve25519_handshake(output1, &seckey1, &pubkey2);
+  curve25519_handshake(output2, &seckey2, &pubkey1);
+  test_memeq(output1, output2, sizeof(output1));
+
+ done:
+  ;
+}
+#endif
+
 static void *
 pass_data_setup_fn(const struct testcase_t *testcase)
 {
@@ -962,6 +1040,10 @@ struct testcase_t crypto_tests[] = {
   CRYPTO_LEGACY(base32_decode),
   { "kdf_TAP", test_crypto_kdf_TAP, 0, NULL, NULL },
   { "hkdf_sha256", test_crypto_hkdf_sha256, 0, NULL, NULL },
+#ifdef CURVE25519_ENABLED
+  { "curve25519_impl", test_crypto_curve25519_impl, 0, NULL, NULL },
+  { "curve25519_wrappers", test_crypto_curve25519_wrappers, 0, NULL, NULL },
+#endif
   END_OF_TESTCASES
 };