commit 0f3eeca9b80ff42cf17f9d8b1b4b45588ea9fbad Author: Yawning Angel yawning@schwanenlied.me Date: Mon Jul 6 09:40:28 2015 +0000
Integrate ed25519-donna (Not yet used).
Integrate ed25519-donna into the build process, and provide an interface that matches the `ref10` code. Apart from the blinding and Curve25519 key conversion, this functions as a drop-in replacement for ref10 (verified by modifying crypto_ed25519.c).
Tests pass, and the benchmarks claim it is quite a bit faster, however actually using the code requires additional integration work. --- .gitignore | 2 + src/common/include.am | 1 + src/ext/ed25519/donna/README.tor | 32 +++ src/ext/ed25519/donna/ed25519-donna-portable.h | 15 ++ src/ext/ed25519/donna/ed25519-randombytes-custom.h | 9 + src/ext/ed25519/donna/ed25519_donna_tor.h | 24 ++ src/ext/ed25519/donna/ed25519_tor.c | 240 ++++++++++++++++++++ src/ext/ed25519/donna/test-internals.c | 34 ++- src/ext/include.am | 41 ++++ 9 files changed, 388 insertions(+), 10 deletions(-)
diff --git a/.gitignore b/.gitignore index 6d87d61..cfa8e7e 100644 --- a/.gitignore +++ b/.gitignore @@ -144,6 +144,8 @@ cscope.* # /src/ext/ /src/ext/ed25519/ref10/libed25519_ref10.a /src/ext/ed25519/ref10/libed25519_ref10.lib +/src/ext/ed25519/donna/libed25519_donna.a +/src/ext/ed25519/donna/libed25519_donna.lib
# /src/or/ /src/or/Makefile diff --git a/src/common/include.am b/src/common/include.am index 789f400..de93131 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 diff --git a/src/ext/ed25519/donna/README.tor b/src/ext/ed25519/donna/README.tor new file mode 100644 index 0000000..6053c88 --- /dev/null +++ b/src/ext/ed25519/donna/README.tor @@ -0,0 +1,32 @@ + +We've made the following changes to the stock ed25519-donna from +as of 8757bd4cd209cb032853ece0ce413f122eef212c. + + * Tor uses copies of `ed25519-donna.h` and `ed25519.c`, named + `ed25519_donna_tor.h` and `ed25591_tor.c`. + + The main functional differences between the standard ed25519-donna + and the Tor specific version are: + + * The external interface has been reworked to match that provided + by Tor's copy of the SUPERCOP `ref10` code. + + * The secret (aka private) key is now stored/used in expanded form. + + * The internal math tests from `test-internals.c` have been wrapped + in a function and the entire file is included to allow for + runtime validation. + + * `ED25519_FN(ed25519_randombytes_unsafe)` is now static. + + * `ed25519-randombytes-custom.h` has the appropriate code to call + Tor's `crypto_rand()` routine, instead of directly using OpenSSL's + CSPRNG. + + * OSX pollutes the global namespace with an `ALIGN` macro, which is + undef-ed right before the donna `ALIGN` macro is defined. + + * If building with Clang's AddressSanitizer, disable inline assembly + since the compilation will fail in `ge25519_scalarmult_base_choose_niels` + on x86_64 targets due to running out of registers. + diff --git a/src/ext/ed25519/donna/ed25519-donna-portable.h b/src/ext/ed25519/donna/ed25519-donna-portable.h index 0a0f7fc..44fa840 100644 --- a/src/ext/ed25519/donna/ed25519-donna-portable.h +++ b/src/ext/ed25519/donna/ed25519-donna-portable.h @@ -20,6 +20,8 @@ #include <sys/param.h> #define DONNA_INLINE inline __attribute__((always_inline)) #define DONNA_NOINLINE __attribute__((noinline)) + /* Tor: OSX pollutes the global namespace with an ALIGN macro. */ + #undef ALIGN #define ALIGN(x) __attribute__((aligned(x))) #define ROTL32(a,b) (((a) << (b)) | ((a) >> (32 - b))) #define ROTR32(a,b) (((a) >> (b)) | ((a) << (32 - b))) @@ -129,6 +131,19 @@ static inline void U64TO8_LE(unsigned char *p, const uint64_t v) { } #endif
+/* Tor: Detect and disable inline assembly when clang's AddressSanitizer + * is present, due to compilation failing because it runs out of registers. + * + * The alternative is to annotate `ge25519_scalarmult_base_choose_niels` + * and selectively disable AddressSanitizer insturmentation, however doing + * things this way results in a "more sanitized" binary. + */ +#if defined(__has_feature) + #if __has_feature(address_sanitizer) + #define ED25519_NO_INLINE_ASM + #endif +#endif + #include <stdlib.h> #include <string.h>
diff --git a/src/ext/ed25519/donna/ed25519-randombytes-custom.h b/src/ext/ed25519/donna/ed25519-randombytes-custom.h index 9f51063..e49368b 100644 --- a/src/ext/ed25519/donna/ed25519-randombytes-custom.h +++ b/src/ext/ed25519/donna/ed25519-randombytes-custom.h @@ -6,3 +6,12 @@ ed25519_randombytes_unsafe is used by the batch verification function to create random scalars */ + +/* Tor: Instead of calling OpenSSL's CSPRNG directly, call the wrapper. */ +#include "crypto.h" + +static void +ED25519_FN(ed25519_randombytes_unsafe) (void *p, size_t len) +{ + crypto_rand(p, len); +} diff --git a/src/ext/ed25519/donna/ed25519_donna_tor.h b/src/ext/ed25519/donna/ed25519_donna_tor.h new file mode 100644 index 0000000..f41744d --- /dev/null +++ b/src/ext/ed25519/donna/ed25519_donna_tor.h @@ -0,0 +1,24 @@ +/* Added for Tor. */ +#ifndef SRC_EXT_ED25519_DONNA_H_INCLUDED_ +#define SRC_EXT_ED25519_DONNA_H_INCLUDED_ +#include <torint.h> + +typedef unsigned char curved25519_key[32]; + +int ed25519_sign_open_batch_donna(const unsigned char **m, size_t *mlen, const unsigned char **pk, const unsigned char **RS, size_t num, int *valid); +void curved25519_scalarmult_basepoint_donna(curved25519_key pk, const curved25519_key e); + +/* Tor specific interface to match the `ref10` glue code. */ +int ed25519_donna_selftest(void); +int ed25519_donna_seckey(unsigned char *sk); +int ed25519_donna_seckey_expand(unsigned char *sk, const unsigned char *sk_seed); +int ed25519_donna_pubkey(unsigned char *pk, const unsigned char *sk); +int ed25519_donna_keygen(unsigned char *pk, unsigned char *sk); + +int ed25519_donna_open(const unsigned char *signature, const unsigned char *m, + size_t mlen, const unsigned char *pk); + +int ed25519_donna_sign(unsigned char *sig, const unsigned char *m, size_t mlen, + const unsigned char *sk, const unsigned char *pk); + +#endif diff --git a/src/ext/ed25519/donna/ed25519_tor.c b/src/ext/ed25519/donna/ed25519_tor.c new file mode 100644 index 0000000..c0eeeb8 --- /dev/null +++ b/src/ext/ed25519/donna/ed25519_tor.c @@ -0,0 +1,240 @@ +/* + Public domain by Andrew M. liquidsun@gmail.com + + Ed25519 reference implementation using Ed25519-donna +*/ + +/* + Tor specific notes: + + This file is used by Tor instead of `ed25519.c` as the number of + changes/additions is non-trivial. + + Tor modifications to `ed25519.c`: + * 'Tab` -> ' '. + * Include `ed25519_donna_tor.h` instead of `ed25519.h`. + + * The external interface has been reworked to match that provided + by Tor's copy of the SUPERCOP `ref10` code. + + * The secret (aka private) key is now stored/used in expanded form. + + * The internal math tests from `test-internals.c` have been wrapped + in a function and the entire file is included to allow for + runtime validation. + */ + + +/* define ED25519_SUFFIX to have it appended to the end of each public function */ +#if !defined(ED25519_SUFFIX) +#define ED25519_SUFFIX +#endif + +#define ED25519_FN3(fn,suffix) fn##suffix +#define ED25519_FN2(fn,suffix) ED25519_FN3(fn,suffix) +#define ED25519_FN(fn) ED25519_FN2(fn,ED25519_SUFFIX) + + +#include "ed25519-donna.h" +#include "ed25519_donna_tor.h" +#include "ed25519-randombytes.h" +#include "ed25519-hash.h" + +typedef unsigned char ed25519_signature[64]; +typedef unsigned char ed25519_public_key[32]; +typedef unsigned char ed25519_secret_key[32]; + +static int ED25519_FN(ed25519_sign_open) (const unsigned char *m, size_t mlen, + const ed25519_public_key pk, const ed25519_signature RS); + + +/* + Generates a (extsk[0..31]) and aExt (extsk[32..63]) +*/ + +DONNA_INLINE static void +ed25519_extsk(hash_512bits extsk, const ed25519_secret_key sk) { + ed25519_hash(extsk, sk, 32); + extsk[0] &= 248; + extsk[31] &= 127; + extsk[31] |= 64; +} + +static void +ed25519_hram(hash_512bits hram, const ed25519_signature RS, const ed25519_public_key pk, const unsigned char *m, size_t mlen) { + ed25519_hash_context ctx; + ed25519_hash_init(&ctx); + ed25519_hash_update(&ctx, RS, 32); + ed25519_hash_update(&ctx, pk, 32); + ed25519_hash_update(&ctx, m, mlen); + ed25519_hash_final(&ctx, hram); +} + +static int +ED25519_FN(ed25519_sign_open) (const unsigned char *m, size_t mlen, const ed25519_public_key pk, const ed25519_signature RS) { + ge25519 ALIGN(16) R, A; + hash_512bits hash; + bignum256modm hram, S; + unsigned char checkR[32]; + + if ((RS[63] & 224) || !ge25519_unpack_negative_vartime(&A, pk)) + return -1; + + /* hram = H(R,A,m) */ + ed25519_hram(hash, RS, pk, m, mlen); + expand256_modm(hram, hash, 64); + + /* S */ + expand256_modm(S, RS + 32, 32); + + /* SB - H(R,A,m)A */ + ge25519_double_scalarmult_vartime(&R, &A, hram, S); + ge25519_pack(checkR, &R); + + /* check that R = SB - H(R,A,m)A */ + return ed25519_verify(RS, checkR, 32) ? 0 : -1; +} + +#include "ed25519-donna-batchverify.h" + +/* + Fast Curve25519 basepoint scalar multiplication +*/ + +void +ED25519_FN(curved25519_scalarmult_basepoint) (curved25519_key pk, const curved25519_key e) { + curved25519_key ec; + bignum256modm s; + bignum25519 ALIGN(16) yplusz, zminusy; + ge25519 ALIGN(16) p; + size_t i; + + /* clamp */ + for (i = 0; i < 32; i++) ec[i] = e[i]; + ec[0] &= 248; + ec[31] &= 127; + ec[31] |= 64; + + expand_raw256_modm(s, ec); + + /* scalar * basepoint */ + ge25519_scalarmult_base_niels(&p, ge25519_niels_base_multiples, s); + + /* u = (y + z) / (z - y) */ + curve25519_add(yplusz, p.y, p.z); + curve25519_sub(zminusy, p.z, p.y); + curve25519_recip(zminusy, zminusy); + curve25519_mul(yplusz, yplusz, zminusy); + curve25519_contract(pk, yplusz); +} + +/* + Tor has a specific idea of how an Ed25519 implementaion should behave. + Implement such a beast using the ed25519-donna primitives/internals. + + * Private key generation using Tor's CSPRNG. + + * Routines that deal with the private key now use the expanded form. + */ + +int +ed25519_donna_seckey(unsigned char *sk) +{ + ed25519_secret_key seed; + + if (crypto_strongest_rand(seed, 32)) + return -1; + + ed25519_extsk(sk, seed); + + memwipe(seed, 0, sizeof(seed)); + + return 0; +} + +int +ed25519_donna_seckey_expand(unsigned char *sk, const unsigned char *skseed) +{ + ed25519_extsk(sk, skseed); + + return 0; +} + +int +ed25519_donna_pubkey(unsigned char *pk, const unsigned char *sk) +{ + bignum256modm a; + ge25519 ALIGN(16) A; + + /* A = aB */ + expand256_modm(a, sk, 32); + ge25519_scalarmult_base_niels(&A, ge25519_niels_base_multiples, a); + ge25519_pack(pk, &A); + + return 0; +} + +int +ed25519_donna_keygen(unsigned char *pk, unsigned char *sk) +{ + int ok; + ok = ed25519_donna_seckey(sk); + ed25519_donna_pubkey(pk, sk); + + return ok; +} + +int +ed25519_donna_open(const unsigned char *signature, const unsigned char *m, + size_t mlen, const unsigned char *pk) +{ + /* Wrap the ed25519-donna routine, since it is also used by the batch + * verification code. + */ + return ED25519_FN(ed25519_sign_open)(m, mlen, pk, signature); +} + +int +ed25519_donna_sign(unsigned char *sig, const unsigned char *m, size_t mlen, + const unsigned char *sk, const unsigned char *pk) +{ + ed25519_hash_context ctx; + bignum256modm r, S, a; + ge25519 ALIGN(16) R; + hash_512bits hashr, hram; + + /* This is equivalent to the removed `ED25519_FN(ed25519_sign)` routine, + * except that the key expansion step is omitted as sk already is in expanded + * form. + */ + + /* r = H(aExt[32..64], m) */ + ed25519_hash_init(&ctx); + ed25519_hash_update(&ctx, sk + 32, 32); + ed25519_hash_update(&ctx, m, mlen); + ed25519_hash_final(&ctx, hashr); + expand256_modm(r, hashr, 64); + + /* R = rB */ + ge25519_scalarmult_base_niels(&R, ge25519_niels_base_multiples, r); + ge25519_pack(sig, &R); + + /* S = H(R,A,m).. */ + ed25519_hram(hram, sig, pk, m, mlen); + expand256_modm(S, hram, 64); + + /* S = H(R,A,m)a */ + expand256_modm(a, sk, 32); + mul256_modm(S, S, a); + + /* S = (r + H(R,A,m)a) */ + add256_modm(S, S, r); + + /* S = (r + H(R,A,m)a) mod L */ + contract256_modm(sig + 32, S); + + return 0; +} + +#include "test-internals.c" + diff --git a/src/ext/ed25519/donna/test-internals.c b/src/ext/ed25519/donna/test-internals.c index 3c67df5..fe9db9d 100644 --- a/src/ext/ed25519/donna/test-internals.c +++ b/src/ext/ed25519/donna/test-internals.c @@ -1,19 +1,22 @@ -#include <stdio.h> -#include "ed25519-donna.h" +/* Tor: Removed, file is inclued in ed25519.c instead. */ +/* #include <stdio.h> */ +/* #include "ed25519-donna.h" */
static int -test_adds() { +test_adds(void) { #if defined(HAVE_UINT128) && !defined(ED25519_SSE2) /* largest result for each limb from a mult or square: all elements except r1 reduced, r1 overflowed as far as possible */ static const bignum25519 max_bignum = { 0x7ffffffffffff,0x8000000001230,0x7ffffffffffff,0x7ffffffffffff,0x7ffffffffffff };
+#if 0 /* what max_bignum should fully reduce to */ static const unsigned char max_bignum_raw[32] = { 0x12,0x00,0x00,0x00,0x00,0x00,0x88,0x91,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00 }; +#endif
/* (max_bignum + max_bignum)^2 */ static const unsigned char max_bignum2_squared_raw[32] = { @@ -46,9 +49,9 @@ test_adds() { }; #endif unsigned char result[32]; - static const bignum25519 ALIGN(16) zero = {0}; - bignum25519 ALIGN(16) a, b, c; - size_t i; + /* static const bignum25519 ALIGN(16) zero = {0}; */ + bignum25519 ALIGN(16) a, b /* , c */; + /* size_t i; */
/* a = (max_bignum + max_bignum) */ curve25519_add(a, max_bignum, max_bignum); @@ -80,7 +83,7 @@ test_adds() { }
static int -test_subs() { +test_subs(void) { #if defined(HAVE_UINT128) && !defined(ED25519_SSE2) /* largest result for each limb from a mult or square: all elements except r1 reduced, r1 overflowed as far as possible */ static const bignum25519 max_bignum = { @@ -119,8 +122,8 @@ test_subs() { #endif unsigned char result[32]; static const bignum25519 ALIGN(16) zero = {0}; - bignum25519 ALIGN(16) a, b, c; - size_t i; + bignum25519 ALIGN(16) a, b /* , c */; + /* size_t i; */
/* a = max_bignum - 0, which expands to 2p + max_bignum - 0 */ curve25519_sub(a, max_bignum, zero); @@ -158,7 +161,8 @@ test_subs() { return 0; }
- +/* Tor: Removed, tests are invoked as a function instead. */ +#if 0 int main() { int ret = 0; @@ -172,5 +176,15 @@ main() { if (!ret) printf("success\n"); return ret; } +#endif
+/* Tor: Added for initialization self-testing. */ +int +ed25519_donna_selftest(void) +{ + int ret = 0; + ret |= test_adds(); + ret |= test_subs(); + return (ret == 0) ? 0 : -1; +}
diff --git a/src/ext/include.am b/src/ext/include.am index 40923aa..ea8f0bc 100644 --- a/src/ext/include.am +++ b/src/ext/include.am @@ -93,3 +93,44 @@ noinst_HEADERS += $(ED25519_REF10_HDRS) LIBED25519_REF10=src/ext/ed25519/ref10/libed25519_ref10.a noinst_LIBRARIES += $(LIBED25519_REF10)
+src_ext_ed25519_donna_libed25519_donna_a_CFLAGS= \ + -DED25519_CUSTOMRANDOM \ + -DED25519_SUFFIX=_donna + +src_ext_ed25519_donna_libed25519_donna_a_SOURCES= \ + src/ext/ed25519/donna/ed25519_tor.c + +ED25519_DONNA_HDRS = \ + src/ext/ed25519/donna/curve25519-donna-32bit.h \ + src/ext/ed25519/donna/curve25519-donna-64bit.h \ + src/ext/ed25519/donna/curve25519-donna-helpers.h \ + src/ext/ed25519/donna/curve25519-donna-sse2.h \ + src/ext/ed25519/donna/ed25519-donna-32bit-sse2.h \ + src/ext/ed25519/donna/ed25519-donna-32bit-tables.h \ + src/ext/ed25519/donna/ed25519-donna-64bit-sse2.h \ + src/ext/ed25519/donna/ed25519-donna-64bit-tables.h \ + src/ext/ed25519/donna/ed25519-donna-64bit-x86-32bit.h \ + src/ext/ed25519/donna/ed25519-donna-64bit-x86.h \ + src/ext/ed25519/donna/ed25519-donna-basepoint-table.h \ + src/ext/ed25519/donna/ed25519-donna-batchverify.h \ + src/ext/ed25519/donna/ed25519-donna.h \ + src/ext/ed25519/donna/ed25519-donna-impl-base.h \ + src/ext/ed25519/donna/ed25519-donna-impl-sse2.h \ + src/ext/ed25519/donna/ed25519-donna-portable.h \ + src/ext/ed25519/donna/ed25519-donna-portable-identify.h \ + src/ext/ed25519/donna/ed25519_donna_tor.h \ + src/ext/ed25519/donna/ed25519.h \ + src/ext/ed25519/donna/ed25519-hash-custom.h \ + src/ext/ed25519/donna/ed25519-hash.h \ + src/ext/ed25519/donna/ed25519-randombytes-custom.h \ + src/ext/ed25519/donna/ed25519-randombytes.h \ + src/ext/ed25519/donna/modm-donna-32bit.h \ + src/ext/ed25519/donna/modm-donna-64bit.h \ + src/ext/ed25519/donna/regression.h \ + src/ext/ed25519/donna/test-ticks.h + +noinst_HEADERS += $(ED25519_DONNA_HDRS) + +LIBED25519_DONNA=src/ext/ed25519/donna/libed25519_donna.a +noinst_LIBRARIES += $(LIBED25519_DONNA) +