Add blinding support to ed25519-donna (Not yet used).

Integrating it the "wrong" way into common/crypto_ed25519.c passes
`make check`, and there appear to be some known answer tests for this,
so I assume I got it right.

Blinding a public key goes from 139.10 usec to 70.78 usec using
ed25519-donna (NB: Turboboost/phase of moon), though the code isn't
critical path, so supporting it is mostly done for completeness.

3 files changed, 90 insertions, 0 deletions

diff --git a/src/ext/ed25519/donna/README.tor b/src/ext/ed25519/donna/README.tor
index 6053c88f28..fa11a36771 100644
--- a/src/ext/ed25519/donna/README.tor
+++ b/src/ext/ed25519/donna/README.tor
@@ -17,6 +17,9 @@ as of 8757bd4cd209cb032853ece0ce413f122eef212c.
       in a function and the entire file is included to allow for
       runtime validation.
 
+    * There's an implementation of multiplicative key blinding so we
+      can use it for next-gen hidden service descriptors.
+
  * `ED25519_FN(ed25519_randombytes_unsafe)` is now static.
 
  * `ed25519-randombytes-custom.h` has the appropriate code to call
diff --git a/src/ext/ed25519/donna/ed25519_donna_tor.h b/src/ext/ed25519/donna/ed25519_donna_tor.h
index f41744d758..a5a53f38bb 100644
--- a/src/ext/ed25519/donna/ed25519_donna_tor.h
+++ b/src/ext/ed25519/donna/ed25519_donna_tor.h
@@ -21,4 +21,10 @@ int ed25519_donna_open(const unsigned char *signature, const unsigned char *m,
 int ed25519_donna_sign(unsigned char *sig, const unsigned char *m, size_t mlen,
   const unsigned char *sk, const unsigned char *pk);
 
+int ed25519_donna_blind_secret_key(unsigned char *out, const unsigned char *inp,
+  const unsigned char *param);
+
+int ed25519_donna_blind_public_key(unsigned char *out, const unsigned char *inp,
+  const unsigned char *param);
+
 #endif
diff --git a/src/ext/ed25519/donna/ed25519_tor.c b/src/ext/ed25519/donna/ed25519_tor.c
index c0eeeb8805..5f2c9c9561 100644
--- a/src/ext/ed25519/donna/ed25519_tor.c
+++ b/src/ext/ed25519/donna/ed25519_tor.c
@@ -44,6 +44,8 @@ typedef unsigned char ed25519_signature[64];
 typedef unsigned char ed25519_public_key[32];
 typedef unsigned char ed25519_secret_key[32];
 
+static void gettweak(unsigned char *out, const unsigned char *param);
+
 static int ED25519_FN(ed25519_sign_open) (const unsigned char *m, size_t mlen,
   const ed25519_public_key pk, const ed25519_signature RS);
 
@@ -135,6 +137,8 @@ ED25519_FN(curved25519_scalarmult_basepoint) (curved25519_key pk, const curved25
     * Private key generation using Tor's CSPRNG.
 
     * Routines that deal with the private key now use the expanded form.
+
+    * Support for multiplicative key blinding has been added.
  */
 
 int
@@ -236,5 +240,82 @@ ed25519_donna_sign(unsigned char *sig, const unsigned char *m, size_t mlen,
   return 0;
 }
 
+static void
+gettweak(unsigned char *out, const unsigned char *param)
+{
+  static const char str[] = "Derive temporary signing key";
+  ed25519_hash_context ctx;
+
+  ed25519_hash_init(&ctx);
+  ed25519_hash_update(&ctx, (const unsigned char*)str, strlen(str));
+  ed25519_hash_update(&ctx, param, 32);
+  ed25519_hash_final(&ctx, out);
+
+  out[0] &= 248;  /* Is this necessary ? */
+  out[31] &= 63;
+  out[31] |= 64;
+}
+
+int
+ed25519_donna_blind_secret_key(unsigned char *out, const unsigned char *inp,
+  const unsigned char *param)
+{
+  static const char str[] = "Derive temporary signing key hash input";
+  unsigned char tweak[64];
+  ed25519_hash_context ctx;
+  bignum256modm ALIGN(16) sk, t;
+
+  gettweak(tweak, param);
+  expand256_modm(t, tweak, 32);
+
+  expand256_modm(sk, inp, 32);
+  mul256_modm(sk, sk, t);
+  contract256_modm(out, sk);
+
+  ed25519_hash_init(&ctx);
+  ed25519_hash_update(&ctx, (const unsigned char*)str, strlen(str));
+  ed25519_hash_update(&ctx, inp + 32, 32);
+  ed25519_hash_final(&ctx, tweak);
+
+  memcpy(out + 32, tweak, 32);
+
+  memwipe(sk, 0, sizeof(sk));
+  memwipe(t, 0, sizeof(t));
+  memwipe(tweak, 0, sizeof(tweak));
+
+  return 0;
+}
+
+int
+ed25519_donna_blind_public_key(unsigned char *out, const unsigned char *inp,
+  const unsigned char *param)
+{
+  static const bignum256modm zero = { 0 };
+  unsigned char tweak[64];
+  unsigned char pkcopy[32];
+  ge25519 ALIGN(16) A, Aprime;
+  bignum256modm ALIGN(16) t;
+
+  gettweak(tweak, param);
+  expand256_modm(t, tweak, 32);
+
+  /* No "ge25519_unpack", negate the public key. */
+  memcpy(pkcopy, inp, 32);
+  pkcopy[31] ^= (1<<7);
+  ge25519_unpack_negative_vartime(&A, pkcopy);
+
+  /* A' = [tweak] * A + [0] * basepoint. */
+  ge25519_double_scalarmult_vartime(&Aprime, &A, t, zero);
+  ge25519_pack(out, &Aprime);
+
+  memwipe(tweak, 0, sizeof(tweak));
+  memwipe(pkcopy, 0, sizeof(pkcopy));
+  memwipe(&A, 0, sizeof(A));
+  memwipe(&Aprime, 0, sizeof(Aprime));
+  memwipe(t, 0, sizeof(t));
+
+  return 0;
+}
+
 #include "test-internals.c"