From 0f3eeca9b80ff42cf17f9d8b1b4b45588ea9fbad Mon Sep 17 00:00:00 2001 From: Yawning Angel Date: Mon, 6 Jul 2015 09:40:28 +0000 Subject: 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. --- src/common/include.am | 1 + 1 file changed, 1 insertion(+) (limited to 'src/common') 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 -- cgit v1.2.3-54-g00ecf From f079c27761a676f7c4200f7275112edd0b5e1270 Mon Sep 17 00:00:00 2001 From: Yawning Angel Date: Mon, 6 Jul 2015 09:57:23 +0000 Subject: Integrate the accelerated Curve25519 scalar basemult. Integration work scavanged from nickm's `ticket8897_9663_v2` branch, with minor modifications. Tor will still sanity check the output but now also attempts to catch extreme breakage by spot checking the optimized implementation vs known values from the NaCl documentation. Implements feature 9663. --- changes/feature9663 | 5 ++ src/common/crypto.c | 3 ++ src/common/crypto_curve25519.c | 119 +++++++++++++++++++++++++++++++++++++++-- src/common/crypto_curve25519.h | 5 ++ src/test/bench.c | 15 +++++- src/test/test_crypto.c | 25 +++++++++ 6 files changed, 168 insertions(+), 4 deletions(-) create mode 100644 changes/feature9663 (limited to 'src/common') diff --git a/changes/feature9663 b/changes/feature9663 new file mode 100644 index 0000000000..c02e08d034 --- /dev/null +++ b/changes/feature9663 @@ -0,0 +1,5 @@ + o Minor feature (performance): + - Improve the runtime speed of the ntor handshake by using an + optimized curve25519 basepoint scalarmult implementation from the + public-domain ed25519-donna by Andrew M. ("floodyberry"), based on + ideas by Adam Langley. Implements ticket 9663. diff --git a/src/common/crypto.c b/src/common/crypto.c index 934679e67a..c9745dd0e6 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -25,6 +25,7 @@ #define CRYPTO_PRIVATE #include "crypto.h" +#include "crypto_curve25519.h" #if OPENSSL_VERSION_NUMBER < OPENSSL_V_SERIES(1,0,0) #error "We require OpenSSL >= 1.0.0" @@ -305,6 +306,8 @@ crypto_early_init(void) return -1; if (crypto_init_siphash_key() < 0) return -1; + + curve25519_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/test/bench.c b/src/test/bench.c index bc2b1f04d8..dbff7d0262 100644 --- a/src/test/bench.c +++ b/src/test/bench.c @@ -177,7 +177,7 @@ bench_onion_TAP(void) } static void -bench_onion_ntor(void) +bench_onion_ntor_impl(void) { const int iters = 1<<10; int i; @@ -234,6 +234,19 @@ bench_onion_ntor(void) dimap_free(keymap, NULL); } +static void +bench_onion_ntor(void) +{ + int ed; + + for (ed = 0; ed <= 1; ++ed) { + printf("Ed25519-based basepoint multiply = %s.\n", + (ed == 0) ? "disabled" : "enabled"); + curve25519_set_impl_params(ed); + bench_onion_ntor_impl(); + } +} + static void bench_ed25519(void) { diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c index 6cba850f30..bc88248db0 100644 --- a/src/test/test_crypto.c +++ b/src/test/test_crypto.c @@ -1124,6 +1124,29 @@ test_crypto_curve25519_impl(void *arg) tor_free(mem_op_hex_tmp); } +static void +test_crypto_curve25519_basepoint(void *arg) +{ + uint8_t secret[32]; + uint8_t public1[32]; + uint8_t public2[32]; + const int iters = 2048; + int i; + (void) arg; + + for (i = 0; i < iters; ++i) { + crypto_rand((char*)secret, 32); + curve25519_set_impl_params(1); /* Use optimization */ + curve25519_basepoint_impl(public1, secret); + curve25519_set_impl_params(0); /* Disable optimization */ + curve25519_basepoint_impl(public2, secret); + tt_mem_op(public1, OP_EQ, public2, 32); + } + + done: + ; +} + static void test_crypto_curve25519_wrappers(void *arg) { @@ -1733,6 +1756,8 @@ struct testcase_t crypto_tests[] = { { "hkdf_sha256", test_crypto_hkdf_sha256, 0, NULL, NULL }, { "curve25519_impl", test_crypto_curve25519_impl, 0, NULL, NULL }, { "curve25519_impl_hibit", test_crypto_curve25519_impl, 0, NULL, (void*)"y"}, + { "curve25519_basepoint", + test_crypto_curve25519_basepoint, TT_FORK, NULL, NULL }, { "curve25519_wrappers", test_crypto_curve25519_wrappers, 0, NULL, NULL }, { "curve25519_encode", test_crypto_curve25519_encode, 0, NULL, NULL }, { "curve25519_persist", test_crypto_curve25519_persist, 0, NULL, NULL }, -- cgit v1.2.3-54-g00ecf From 840e68d9171d62a1fdaf0395e248daad2cbe014f Mon Sep 17 00:00:00 2001 From: Yawning Angel Date: Mon, 6 Jul 2015 10:11:10 +0000 Subject: Integrate and enable ed25519-donna. The runtime sanity checking is slightly different from the optimized basepoint stuff in that it uses a given implementation's self tests if available, and checks if signing/verification works with a test vector from the IETF EdDSA draft. The unit tests include a new testcase that will fuzz donna against ref0, including the blinding and curve25519 key conversion routines. If this is something that should be done at runtime (No?), the code can be stolen from there. Note: Integrating batch verification is not done yet. --- changes/feature16467 | 4 + src/common/crypto.c | 2 + src/common/crypto_ed25519.c | 211 +++++++++++++++++++++++++++++++++++++++++--- src/common/crypto_ed25519.h | 3 + src/test/bench.c | 15 +++- src/test/test_crypto.c | 72 +++++++++++++++ 6 files changed, 292 insertions(+), 15 deletions(-) create mode 100644 changes/feature16467 (limited to 'src/common') diff --git a/changes/feature16467 b/changes/feature16467 new file mode 100644 index 0000000000..5cd30fd1d9 --- /dev/null +++ b/changes/feature16467 @@ -0,0 +1,4 @@ + o Minor feature (performance): + - Improve the runtime speed of Ed25519 operations by using the + public-domain ed25519-donna by Andrew M. ("floodyberry"). Implements + ticket 16467. diff --git a/src/common/crypto.c b/src/common/crypto.c index c9745dd0e6..88a23f5b14 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -26,6 +26,7 @@ #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" @@ -308,6 +309,7 @@ crypto_early_init(void) return -1; curve25519_init(); + ed25519_init(); } return 0; } 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 +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 seckey_out. If * extra_strong, 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 checkable, 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/test/bench.c b/src/test/bench.c index dbff7d0262..2a27377c80 100644 --- a/src/test/bench.c +++ b/src/test/bench.c @@ -248,7 +248,7 @@ bench_onion_ntor(void) } static void -bench_ed25519(void) +bench_ed25519_impl(void) { uint64_t start, end; const int iters = 1<<12; @@ -304,6 +304,19 @@ bench_ed25519(void) MICROCOUNT(start, end, iters)); } +static void +bench_ed25519(void) +{ + int donna; + + for (donna = 0; donna <= 1; ++donna) { + printf("Ed25519-donna = %s.\n", + (donna == 0) ? "disabled" : "enabled"); + ed25519_set_impl_params(donna); + bench_ed25519_impl(); + } +} + static void bench_cell_aes(void) { diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c index bc88248db0..2bc477083c 100644 --- a/src/test/test_crypto.c +++ b/src/test/test_crypto.c @@ -1636,6 +1636,77 @@ test_crypto_ed25519_testvectors(void *arg) tor_free(mem_op_hex_tmp); } +static void +test_crypto_ed25519_fuzz_donna(void *arg) +{ + const unsigned iters = 1024; + uint8_t msg[1024]; + unsigned i; + (void)arg; + + tt_assert(sizeof(msg) == iters); + crypto_rand((char*) msg, sizeof(msg)); + + /* Fuzz Ed25519-donna vs ref10, alternating the implementation used to + * generate keys/sign per iteration. + */ + for (i = 0; i < iters; ++i) { + const int use_donna = i & 1; + uint8_t blinding[32]; + curve25519_keypair_t ckp; + ed25519_keypair_t kp, kp_blind, kp_curve25519; + ed25519_public_key_t pk, pk_blind, pk_curve25519; + ed25519_signature_t sig, sig_blind; + int bit = 0; + + crypto_rand((char*) blinding, sizeof(blinding)); + + /* Impl. A: + * 1. Generate a keypair. + * 2. Blinded the keypair. + * 3. Sign a message (unblinded). + * 4. Sign a message (blinded). + * 5. Generate a curve25519 keypair, and convert it to Ed25519. + */ + ed25519_set_impl_params(use_donna); + tt_int_op(0, OP_EQ, ed25519_keypair_generate(&kp, i&1)); + tt_int_op(0, OP_EQ, ed25519_keypair_blind(&kp_blind, &kp, blinding)); + tt_int_op(0, OP_EQ, ed25519_sign(&sig, msg, i, &kp)); + tt_int_op(0, OP_EQ, ed25519_sign(&sig_blind, msg, i, &kp_blind)); + + tt_int_op(0, OP_EQ, curve25519_keypair_generate(&ckp, i&1)); + tt_int_op(0, OP_EQ, ed25519_keypair_from_curve25519_keypair( + &kp_curve25519, &bit, &ckp)); + + /* Impl. B: + * 1. Validate the public key by rederiving it. + * 2. Validate the blinded public key by rederiving it. + * 3. Validate the unblinded signature (and test a invalid signature). + * 4. Validate the blinded signature. + * 5. Validate the public key (from Curve25519) by rederiving it. + */ + ed25519_set_impl_params(!use_donna); + tt_int_op(0, OP_EQ, ed25519_public_key_generate(&pk, &kp.seckey)); + tt_mem_op(pk.pubkey, OP_EQ, kp.pubkey.pubkey, 32); + + tt_int_op(0, OP_EQ, ed25519_public_blind(&pk_blind, &kp.pubkey, blinding)); + tt_mem_op(pk_blind.pubkey, OP_EQ, kp_blind.pubkey.pubkey, 32); + + tt_int_op(0, OP_EQ, ed25519_checksig(&sig, msg, i, &pk)); + sig.sig[0] ^= 15; + tt_int_op(-1, OP_EQ, ed25519_checksig(&sig, msg, sizeof(msg), &pk)); + + tt_int_op(0, OP_EQ, ed25519_checksig(&sig_blind, msg, i, &pk_blind)); + + tt_int_op(0, OP_EQ, ed25519_public_key_from_curve25519_public_key( + &pk_curve25519, &ckp.pubkey, bit)); + tt_mem_op(pk_curve25519.pubkey, OP_EQ, kp_curve25519.pubkey.pubkey, 32); + } + + done: + ; +} + static void test_crypto_siphash(void *arg) { @@ -1767,6 +1838,7 @@ struct testcase_t crypto_tests[] = { { "ed25519_convert", test_crypto_ed25519_convert, 0, NULL, NULL }, { "ed25519_blinding", test_crypto_ed25519_blinding, 0, NULL, NULL }, { "ed25519_testvectors", test_crypto_ed25519_testvectors, 0, NULL, NULL }, + { "ed25519_fuzz_donna", test_crypto_ed25519_fuzz_donna, TT_FORK, NULL, NULL }, { "siphash", test_crypto_siphash, 0, NULL, NULL }, END_OF_TESTCASES }; -- cgit v1.2.3-54-g00ecf