January 2013 - tor-commits - lists.torproject.org

[tor/master] Merge branch 'ntor-resquashed'
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit b1bdecd703879ca09bf63bf1453a70c4b80ac96d Merge: ee41826 d3de0b9 Author: Nick Mathewson <nickm(a)torproject.org> Date: Thu Jan 3 11:52:41 2013 -0500 Merge branch 'ntor-resquashed' Conflicts: src/or/cpuworker.c src/or/or.h src/test/bench.c .gitignore | 7 +- changes/ntor | 40 + configure.ac | 99 +++ doc/tor.1.txt | 10 + src/common/crypto.c | 163 +++- src/common/crypto.h | 13 +- src/common/crypto_curve25519.c | 180 ++++ src/common/crypto_curve25519.h | 61 ++ src/common/di_ops.c | 89 ++ src/common/di_ops.h | 16 + src/common/include.am | 26 +- src/ext/README | 5 +- src/ext/curve25519_donna/README | 44 + src/ext/curve25519_donna/curve25519-donna-c64.c | 449 ++++++++++ src/ext/curve25519_donna/curve25519-donna.c | 730 ++++++++++++++++ src/or/channeltls.c | 2 + src/or/circuitbuild.c | 330 +++++--- src/or/circuitbuild.h | 16 +- src/or/circuitlist.c | 13 +- src/or/circuituse.c | 4 +- src/or/command.c | 75 ++- src/or/config.c | 1 + src/or/cpuworker.c | 205 +++-- src/or/cpuworker.h | 3 +- src/or/dirserv.c | 3 +- src/or/dirvote.c | 9 + src/or/dirvote.h | 6 +- src/or/entrynodes.c | 2 +- src/or/include.am | 15 +- src/or/microdesc.c | 1 + src/or/nodelist.c | 12 + src/or/nodelist.h | 1 + src/or/onion.c | 1032 +++++++++++++++++------ src/or/onion.h | 118 ++- src/or/onion_fast.c | 123 +++ src/or/onion_fast.h | 38 + src/or/onion_ntor.c | 295 +++++++ src/or/onion_ntor.h | 63 ++ src/or/onion_tap.c | 218 +++++ src/or/onion_tap.h | 37 + src/or/or.h | 64 +- src/or/relay.c | 28 +- src/or/rendclient.c | 14 +- src/or/rendmid.c | 4 +- src/or/rendservice.c | 14 +- src/or/router.c | 224 +++++- src/or/router.h | 6 + src/or/routerlist.c | 1 + src/or/routerparse.c | 36 + src/test/bench.c | 143 ++++- src/test/include.am | 19 +- src/test/ntor_ref.py | 387 +++++++++ src/test/test.c | 77 ++- src/test/test_cell_formats.c | 502 +++++++++++ src/test/test_containers.c | 45 + src/test/test_crypto.c | 181 ++++ src/test/test_ntor_cl.c | 166 ++++ src/test/test_util.c | 10 + src/tools/include.am | 2 + 59 files changed, 5876 insertions(+), 601 deletions(-) diff --cc src/or/config.c index 6086621,979d09c..9905a94 --- a/src/or/config.c +++ b/src/or/config.c @@@ -388,8 -382,8 +388,9 @@@ static config_var_t option_vars_[] = V(UpdateBridgesFromAuthority, BOOL, "0"), V(UseBridges, BOOL, "0"), V(UseEntryGuards, BOOL, "1"), + V(UseEntryGuardsAsDirGuards, BOOL, "1"), V(UseMicrodescriptors, AUTOBOOL, "auto"), + V(UseNTorHandshake, AUTOBOOL, "auto"), V(User, STRING, NULL), V(UserspaceIOCPBuffers, BOOL, "0"), VAR("V1AuthoritativeDirectory",BOOL, V1AuthoritativeDir, "0"), diff --cc src/or/or.h index bc2cdae,b5718a8..7b8ff70 --- a/src/or/or.h +++ b/src/or/or.h @@@ -2553,10 -2534,22 +2570,24 @@@ typedef enum MICRODESC_DIRINFO=1 << 6, } dirinfo_type_t; +#define ALL_DIRINFO ((dirinfo_type_t)((1<<7)-1)) + #define CRYPT_PATH_MAGIC 0x70127012u + struct fast_handshake_state_t; + struct ntor_handshake_state_t; + #define ONION_HANDSHAKE_TYPE_TAP 0x0000 + #define ONION_HANDSHAKE_TYPE_FAST 0x0001 + #define ONION_HANDSHAKE_TYPE_NTOR 0x0002 + typedef struct { + uint16_t tag; + union { + struct fast_handshake_state_t *fast; + crypto_dh_t *tap; + struct ntor_handshake_state_t *ntor; + } u; + } onion_handshake_state_t; + /** Holds accounting information for a single step in the layered encryption * performed by a circuit. Used only at the client edge of a circuit. */ typedef struct crypt_path_t { @@@ -2735,26 -2724,13 +2762,24 @@@ typedef struct circuit_t * more. */ int deliver_window; - /** For storage while n_chan is pending - * (state CIRCUIT_STATE_CHAN_WAIT). When defined, it is always - * length ONIONSKIN_CHALLENGE_LEN. */ - char *n_chan_onionskin; + /** For storage while n_chan is pending (state CIRCUIT_STATE_CHAN_WAIT). */ + struct create_cell_t *n_chan_create_cell; - /** When was this circuit created? We keep this timestamp with a higher - * resolution than most so that the circuit-build-time tracking code can - * get millisecond resolution. */ + /** When did circuit construction actually begin (ie send the + * CREATE cell or begin cannibalization). + * + * Note: This timer will get reset if we decide to cannibalize + * a circuit. It may also get reset during certain phases of hidden + * service circuit use. + * + * We keep this timestamp with a higher resolution than most so that the + * circuit-build-time tracking code can get millisecond resolution. + */ + struct timeval timestamp_began; + + /** This timestamp marks when the init_circuit_base constructor ran. */ struct timeval timestamp_created; + /** When the circuit was first used, or 0 if the circuit is clean. * * XXXX023 Note that some code will artifically adjust this value backward @@@ -3875,8 -3802,8 +3901,10 @@@ typedef struct int IPv6Exit; /**< Do we support exiting to IPv6 addresses? */ + char *TLSECGroup; /**< One of "P256", "P224", or nil for auto */ + + /** Autobool: should we use the ntor handshake if we can? */ + int UseNTorHandshake; } or_options_t; /** Persistent state for an onion router, as saved to disk. */ diff --cc src/or/rendservice.c index e70f969,4f3fdf4..fc76f56 --- a/src/or/rendservice.c +++ b/src/or/rendservice.c @@@ -1382,11 -1382,8 +1382,11 @@@ rend_service_introduce(origin_circuit_ dh = NULL; if (circuit_init_cpath_crypto(cpath,keys+DIGEST_LEN,1)<0) goto err; - memcpy(cpath->handshake_digest, keys, DIGEST_LEN); + memcpy(cpath->rend_circ_nonce, keys, DIGEST_LEN); + /* For path bias: This intro circuit was used successfully */ + circuit->path_state = PATH_STATE_USE_SUCCEEDED; + goto done; log_error: diff --cc src/test/bench.c index da1ae9b,2c40cdf..8b91b07 --- a/src/test/bench.c +++ b/src/test/bench.c @@@ -15,17 -15,15 +15,23 @@@ const char tor_git_revision[] = "" #include "orconfig.h" #define RELAY_PRIVATE + #define CONFIG_PRIVATE #include "or.h" + #include "onion_tap.h" #include "relay.h" +#include <openssl/opensslv.h> +#include <openssl/evp.h> - #if OPENSSL_VERSION_NUMBER >= OPENSSL_V_SERIES(1,0,0) +#ifndef OPENSSL_NO_EC +#include <openssl/ec.h> +#include <openssl/ecdh.h> +#include <openssl/obj_mac.h> +#endif ++ + #include "config.h" + #ifdef CURVE25519_ENABLED + #include "crypto_curve25519.h" + #include "onion_ntor.h" #endif #if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_PROCESS_CPUTIME_ID) @@@ -355,13 -387,12 +480,17 @@@ typedef struct benchmark_t static struct benchmark_t benchmarks[] = { ENT(dmap), ENT(aes), + ENT(onion_TAP), + #ifdef CURVE25519_ENABLED + ENT(onion_ntor), + #endif ENT(cell_aes), ENT(cell_ops), + ENT(dh), +#ifdef HAVE_EC_BENCHMARKS + ENT(ecdh_p256), + ENT(ecdh_p224), +#endif {NULL,NULL,0} };

1 0

[tor/master] Check all crypto_rand return values for ntor.
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit d3de0b91fb322c00d11857d89a8420af0d466e39 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Dec 25 22:43:01 2012 -0500 Check all crypto_rand return values for ntor. --- src/common/crypto_curve25519.c | 15 ++++++++++----- src/common/crypto_curve25519.h | 8 ++++---- src/or/onion_fast.c | 7 +++++-- src/or/onion_ntor.c | 5 ++++- src/or/router.c | 6 ++++-- 5 files changed, 27 insertions(+), 14 deletions(-) diff --git a/src/common/crypto_curve25519.c b/src/common/crypto_curve25519.c index f3ecdb5..a4ab65c 100644 --- a/src/common/crypto_curve25519.c +++ b/src/common/crypto_curve25519.c @@ -54,14 +54,15 @@ curve25519_public_key_is_ok(const curve25519_public_key_t *key) /** Generate a new keypair and return the secret key. If extra_strong * is true, this key is possibly going to get used more than once, so - * use a better-than-usual RNG. */ -void + * use a better-than-usual RNG. Return 0 on success, -1 on failure. */ +int curve25519_secret_key_generate(curve25519_secret_key_t *key_out, int extra_strong) { uint8_t k_tmp[CURVE25519_SECKEY_LEN]; - crypto_rand((char*)key_out->secret_key, CURVE25519_SECKEY_LEN); + if (crypto_rand((char*)key_out->secret_key, CURVE25519_SECKEY_LEN) < 0) + return -1; if (extra_strong && !crypto_strongest_rand(k_tmp, CURVE25519_SECKEY_LEN)) { /* If they asked for extra-strong entropy and we have some, use it as an * HMAC key to improve not-so-good entopy rather than using it directly, @@ -74,6 +75,8 @@ curve25519_secret_key_generate(curve25519_secret_key_t *key_out, key_out->secret_key[0] &= 248; key_out->secret_key[31] &= 127; key_out->secret_key[31] |= 64; + + return 0; } void @@ -85,12 +88,14 @@ curve25519_public_key_generate(curve25519_public_key_t *key_out, curve25519_impl(key_out->public_key, seckey->secret_key, basepoint); } -void +int curve25519_keypair_generate(curve25519_keypair_t *keypair_out, int extra_strong) { - curve25519_secret_key_generate(&keypair_out->seckey, extra_strong); + if (curve25519_secret_key_generate(&keypair_out->seckey, extra_strong) < 0) + return -1; curve25519_public_key_generate(&keypair_out->pubkey, &keypair_out->seckey); + return 0; } int diff --git a/src/common/crypto_curve25519.h b/src/common/crypto_curve25519.h index c43017e..e768b8c 100644 --- a/src/common/crypto_curve25519.h +++ b/src/common/crypto_curve25519.h @@ -32,12 +32,12 @@ typedef struct curve25519_keypair_t { #ifdef CURVE25519_ENABLED 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); +int 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_keypair_generate(curve25519_keypair_t *keypair_out, - int extra_strong); +int curve25519_keypair_generate(curve25519_keypair_t *keypair_out, + int extra_strong); void curve25519_handshake(uint8_t *output, const curve25519_secret_key_t *, diff --git a/src/or/onion_fast.c b/src/or/onion_fast.c index eb9eceb..c1a0523 100644 --- a/src/or/onion_fast.c +++ b/src/or/onion_fast.c @@ -29,8 +29,11 @@ fast_onionskin_create(fast_handshake_state_t **handshake_state_out, uint8_t *handshake_out) { fast_handshake_state_t *s; - *handshake_state_out = s =tor_malloc(sizeof(fast_handshake_state_t)); - crypto_rand((char*)s->state, sizeof(s->state)); + *handshake_state_out = s = tor_malloc(sizeof(fast_handshake_state_t)); + if (crypto_rand((char*)s->state, sizeof(s->state)) < 0) { + tor_free(s); + return -1; + } memcpy(handshake_out, s->state, DIGEST_LEN); return 0; } diff --git a/src/or/onion_ntor.c b/src/or/onion_ntor.c index b601d1e..58ab107 100644 --- a/src/or/onion_ntor.c +++ b/src/or/onion_ntor.c @@ -78,7 +78,10 @@ onion_skin_ntor_create(const uint8_t *router_id, memcpy(state->router_id, router_id, DIGEST_LEN); memcpy(&state->pubkey_B, router_key, sizeof(curve25519_public_key_t)); - curve25519_secret_key_generate(&state->seckey_x, 0); + if (curve25519_secret_key_generate(&state->seckey_x, 0) < 0) { + tor_free(state); + return -1; + } curve25519_public_key_generate(&state->pubkey_X, &state->seckey_x); op = onion_skin_out; diff --git a/src/or/router.c b/src/or/router.c index 961fd48..cc9702d 100644 --- a/src/or/router.c +++ b/src/or/router.c @@ -339,7 +339,8 @@ rotate_onion_key(void) tor_free(fname_prev); fname = get_datadir_fname2("keys", "secret_onion_key_ntor"); fname_prev = get_datadir_fname2("keys", "secret_onion_key_ntor.old"); - curve25519_keypair_generate(&new_curve25519_keypair, 1); + if (curve25519_keypair_generate(&new_curve25519_keypair, 1) < 0) + goto error; if (file_status(fname) == FN_FILE) { if (replace_file(fname, fname_prev)) goto error; @@ -481,7 +482,8 @@ init_curve25519_keypair_from_file(curve25519_keypair_t *keys_out, } log_info(LD_GENERAL, "No key found in \"%s\"; generating fresh key.", fname); - curve25519_keypair_generate(keys_out, 1); + if (curve25519_keypair_generate(keys_out, 1) < 0) + goto error; if (curve25519_keypair_write_to_file(keys_out, fname, tag)<0) { log(severity, LD_FS, "Couldn't write generated key to \"%s\".", fname);

1 0

[tor/master] Add a crypto_dh_dup, for benchmark support
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit 3c3084e1656888d43be3b92169734a6195ec6d75 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Nov 28 15:38:37 2012 -0500 Add a crypto_dh_dup, for benchmark support --- src/common/crypto.c | 10 ++++++++++ src/common/crypto.h | 1 + 2 files changed, 11 insertions(+), 0 deletions(-) diff --git a/src/common/crypto.c b/src/common/crypto.c index 39f5a4a..37d8433 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -2036,6 +2036,16 @@ crypto_dh_new(int dh_type) return NULL; } +/** Return a copy of dh, sharing its internal state. */ +crypto_dh_t * +crypto_dh_dup(const crypto_dh_t *dh) +{ + crypto_dh_t *dh_new = tor_malloc_zero(sizeof(crypto_dh_t)); + dh_new->dh = dh->dh; + DH_up_ref(dh->dh); + return dh_new; +} + /** Return the length of the DH key in dh, in bytes. */ int diff --git a/src/common/crypto.h b/src/common/crypto.h index 4c5fa6a..eb8b1de 100644 --- a/src/common/crypto.h +++ b/src/common/crypto.h @@ -230,6 +230,7 @@ void crypto_hmac_sha256(char *hmac_out, #define DH_TYPE_REND 2 #define DH_TYPE_TLS 3 crypto_dh_t *crypto_dh_new(int dh_type); +crypto_dh_t *crypto_dh_dup(const crypto_dh_t *dh); int crypto_dh_get_bytes(crypto_dh_t *dh); int crypto_dh_generate_public(crypto_dh_t *dh); int crypto_dh_get_public(crypto_dh_t *dh, char *pubkey_out,

1 0

[tor/master] Add benchmark to test onionskin performance.
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit 4f60bca1c1cb5ba07730d8f20a4647cc9494b6c6 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Nov 28 15:39:00 2012 -0500 Add benchmark to test onionskin performance. --- src/test/bench.c | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 76 insertions(+), 0 deletions(-) diff --git a/src/test/bench.c b/src/test/bench.c index 2e65d0b..cf8ba4a 100644 --- a/src/test/bench.c +++ b/src/test/bench.c @@ -15,9 +15,12 @@ const char tor_git_revision[] = ""; #include "orconfig.h" #define RELAY_PRIVATE +#define CONFIG_PRIVATE #include "or.h" +#include "onion.h" #include "relay.h" +#include "config.h" #if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_PROCESS_CPUTIME_ID) static uint64_t nanostart; @@ -97,6 +100,66 @@ bench_aes(void) } static void +bench_onion_TAP(void) +{ + const int iters = 1<<9; + int i; + crypto_pk_t *key, *key2; + uint64_t start, end; + char os[ONIONSKIN_CHALLENGE_LEN]; + char or[ONIONSKIN_REPLY_LEN]; + crypto_dh_t *dh_out; + + key = crypto_pk_new(); + key2 = crypto_pk_new(); + crypto_pk_generate_key_with_bits(key, 1024); + crypto_pk_generate_key_with_bits(key2, 1024); + + reset_perftime(); + start = perftime(); + for (i = 0; i < iters; ++i) { + onion_skin_create(key, &dh_out, os); + crypto_dh_free(dh_out); + } + end = perftime(); + printf("Client-side, part 1: %f msec.\n", NANOCOUNT(start, end, iters)/1e6); + + onion_skin_create(key, &dh_out, os); + start = perftime(); + for (i = 0; i < iters; ++i) { + char key_out[CPATH_KEY_MATERIAL_LEN]; + onion_skin_server_handshake(os, key, NULL, or, key_out, sizeof(key_out)); + } + end = perftime(); + printf("Server-side, key guessed right: %f msec\n", + NANOCOUNT(start, end, iters)/1e6); + + start = perftime(); + for (i = 0; i < iters; ++i) { + char key_out[CPATH_KEY_MATERIAL_LEN]; + onion_skin_server_handshake(os, key2, key, or, key_out, sizeof(key_out)); + } + end = perftime(); + printf("Server-side, key guessed wrong: %f msec.\n", + NANOCOUNT(start, end, iters)/1e6); + + start = perftime(); + for (i = 0; i < iters; ++i) { + crypto_dh_t *dh; + char key_out[CPATH_KEY_MATERIAL_LEN]; + int s; + dh = crypto_dh_dup(dh_out); + s = onion_skin_client_handshake(dh, or, key_out, sizeof(key_out)); + tor_assert(s == 0); + } + end = perftime(); + printf("Client-side, part 2: %f msec.\n", + NANOCOUNT(start, end, iters)/1e6); + + crypto_pk_free(key); +} + +static void bench_cell_aes(void) { uint64_t start, end; @@ -261,6 +324,7 @@ typedef struct benchmark_t { static struct benchmark_t benchmarks[] = { ENT(dmap), ENT(aes), + ENT(onion_TAP), ENT(cell_aes), ENT(cell_ops), {NULL,NULL,0} @@ -286,6 +350,8 @@ main(int argc, const char **argv) int i; int list=0, n_enabled=0; benchmark_t *b; + char *errmsg; + or_options_t *options; tor_threads_init(); @@ -306,6 +372,16 @@ main(int argc, const char **argv) reset_perftime(); crypto_seed_rng(1); + options = options_new(); + init_logging(); + options->command = CMD_RUN_UNITTESTS; + options->DataDirectory = tor_strdup(""); + options_init(options); + if (set_options(options, &errmsg) < 0) { + printf("Failed to set initial options: %s\n", errmsg); + tor_free(errmsg); + return 1; + } for (b = benchmarks; b->name; ++b) { if (b->enabled || n_enabled == 0) {

1 0

[tor/master] Add a unit test for the old KDF while we're at it
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit 014e69054d5a09664753d149eb5556ec059bcb11 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Dec 3 12:34:05 2012 -0500 Add a unit test for the old KDF while we're at it --- src/test/test_crypto.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 48 insertions(+), 0 deletions(-) diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c index 6c73138..28e2937 100644 --- a/src/test/test_crypto.c +++ b/src/test/test_crypto.c @@ -833,6 +833,52 @@ test_crypto_base32_decode(void) } static void +test_crypto_kdf_TAP(void *arg) +{ + uint8_t key_material[100]; + int r; + char *mem_op_hex_tmp = NULL; + + (void)arg; +#define EXPAND(s) \ + r = crypto_expand_key_material_TAP( \ + (const uint8_t*)(s), strlen(s), \ + key_material, 100) + + /* Test vectors generated with a little python script; feel free to write + * your own. */ + memset(key_material, 0, sizeof(key_material)); + EXPAND(""); + tt_int_op(r, ==, 0); + test_memeq_hex(key_material, + "5ba93c9db0cff93f52b521d7420e43f6eda2784fbf8b4530d8" + "d246dd74ac53a13471bba17941dff7c4ea21bb365bbeeaf5f2" + "c654883e56d11e43c44e9842926af7ca0a8cca12604f945414" + "f07b01e13da42c6cf1de3abfdea9b95f34687cbbe92b9a7383"); + + EXPAND("Tor"); + tt_int_op(r, ==, 0); + test_memeq_hex(key_material, + "776c6214fc647aaa5f683c737ee66ec44f03d0372e1cce6922" + "7950f236ddf1e329a7ce7c227903303f525a8c6662426e8034" + "870642a6dabbd41b5d97ec9bf2312ea729992f48f8ea2d0ba8" + "3f45dfda1a80bdc8b80de01b23e3e0ffae099b3e4ccf28dc28"); + + EXPAND("AN ALARMING ITEM TO FIND ON A MONTHLY AUTO-DEBIT NOTICE"); + tt_int_op(r, ==, 0); + test_memeq_hex(key_material, + "a340b5d126086c3ab29c2af4179196dbf95e1c72431419d331" + "4844bf8f6afb6098db952b95581fb6c33625709d6f4400b8e7" + "ace18a70579fad83c0982ef73f89395bcc39493ad53a685854" + "daf2ba9b78733b805d9a6824c907ee1dba5ac27a1e466d4d10"); + + done: + tor_free(mem_op_hex_tmp); + +#undef EXPAND +} + +static void test_crypto_hkdf_sha256(void *arg) { uint8_t key_material[100]; @@ -880,6 +926,7 @@ test_crypto_hkdf_sha256(void *arg) done: tor_free(mem_op_hex_tmp); +#undef EXPAND } static void * @@ -913,6 +960,7 @@ struct testcase_t crypto_tests[] = { { "aes_iv_AES", test_crypto_aes_iv, TT_FORK, &pass_data, (void*)"aes" }, { "aes_iv_EVP", test_crypto_aes_iv, TT_FORK, &pass_data, (void*)"evp" }, CRYPTO_LEGACY(base32_decode), + { "kdf_TAP", test_crypto_kdf_TAP, 0, NULL, NULL }, { "hkdf_sha256", test_crypto_hkdf_sha256, 0, NULL, NULL }, END_OF_TESTCASES };

1 0

[tor/master] Implement HKDF from RFC5869
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit 6921d1fd2520df54b29125221eea06f230d78e61 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Dec 3 12:20:05 2012 -0500 Implement HKDF from RFC5869 This is a customizable extract-and-expand HMAC-KDF for deriving keys. It derives from RFC5869, which derives its rationale from Krawczyk, H., "Cryptographic Extraction and Key Derivation: The HKDF Scheme", Proceedings of CRYPTO 2010, 2010, <http://eprint.iacr.org/2010/264>. I'm also renaming the existing KDF, now that Tor has two of them. This is the key derivation scheme specified in ntor. There are also unit tests. --- src/common/crypto.c | 76 +++++++++++++++++++++++++++++++++++++++++++---- src/common/crypto.h | 11 ++++++- src/or/onion.c | 12 ++++---- src/test/test_crypto.c | 51 ++++++++++++++++++++++++++++++++ 4 files changed, 135 insertions(+), 15 deletions(-) diff --git a/src/common/crypto.c b/src/common/crypto.c index 37d8433..2147738 100644 --- a/src/common/crypto.c +++ b/src/common/crypto.c @@ -2184,8 +2184,8 @@ crypto_dh_compute_secret(int severity, crypto_dh_t *dh, goto error; } secret_len = result; - if (crypto_expand_key_material(secret_tmp, secret_len, - secret_out, secret_bytes_out)<0) + if (crypto_expand_key_material_TAP((uint8_t*)secret_tmp, secret_len, + (uint8_t*)secret_out, secret_bytes_out)<0) goto error; secret_len = secret_bytes_out; @@ -2211,15 +2211,18 @@ crypto_dh_compute_secret(int severity, crypto_dh_t *dh, * key_out by taking the first key_out_len bytes of * H(K | [00]) | H(K | [01]) | .... * + * This is the key expansion algorithm used in the "TAP" circuit extension + * mechanism; it shouldn't be used for new protocols. + * * Return 0 on success, -1 on failure. */ int -crypto_expand_key_material(const char *key_in, size_t key_in_len, - char *key_out, size_t key_out_len) +crypto_expand_key_material_TAP(const uint8_t *key_in, size_t key_in_len, + uint8_t *key_out, size_t key_out_len) { int i; - char *cp, *tmp = tor_malloc(key_in_len+1); - char digest[DIGEST_LEN]; + uint8_t *cp, *tmp = tor_malloc(key_in_len+1); + uint8_t digest[DIGEST_LEN]; /* If we try to get more than this amount of key data, we'll repeat blocks.*/ tor_assert(key_out_len <= DIGEST_LEN*256); @@ -2228,7 +2231,7 @@ crypto_expand_key_material(const char *key_in, size_t key_in_len, for (cp = key_out, i=0; cp < key_out+key_out_len; ++i, cp += DIGEST_LEN) { tmp[key_in_len] = i; - if (crypto_digest(digest, tmp, key_in_len+1)) + if (crypto_digest((char*)digest, (const char *)tmp, key_in_len+1)) goto err; memcpy(cp, digest, MIN(DIGEST_LEN, key_out_len-(cp-key_out))); } @@ -2244,6 +2247,65 @@ crypto_expand_key_material(const char *key_in, size_t key_in_len, return -1; } +/** Expand some secret key material according to RFC5869, using SHA256 as the + * underlying hash. The key_in_len bytes at key_in are the + * secret key material; the salt_in_len bytes at salt_in and the + * info_in_len bytes in info_in_len are the algorithm's "salt" + * and "info" parameters respectively. On success, write key_out_len + * bytes to key_out and return 0. On failure, return -1. + */ +int +crypto_expand_key_material_rfc5869_sha256( + const uint8_t *key_in, size_t key_in_len, + const uint8_t *salt_in, size_t salt_in_len, + const uint8_t *info_in, size_t info_in_len, + uint8_t *key_out, size_t key_out_len) +{ + uint8_t prk[DIGEST256_LEN]; + uint8_t tmp[DIGEST256_LEN + 128 + 1]; + uint8_t mac[DIGEST256_LEN]; + int i; + uint8_t *outp; + size_t tmp_len; + + crypto_hmac_sha256((char*)prk, + (const char*)salt_in, salt_in_len, + (const char*)key_in, key_in_len); + + /* If we try to get more than this amount of key data, we'll repeat blocks.*/ + tor_assert(key_out_len <= DIGEST256_LEN * 256); + tor_assert(info_in_len <= 128); + memset(tmp, 0, sizeof(tmp)); + outp = key_out; + i = 1; + + while (key_out_len) { + size_t n; + if (i > 1) { + memcpy(tmp, mac, DIGEST256_LEN); + memcpy(tmp+DIGEST256_LEN, info_in, info_in_len); + tmp[DIGEST256_LEN+info_in_len] = i; + tmp_len = DIGEST256_LEN + info_in_len + 1; + } else { + memcpy(tmp, info_in, info_in_len); + tmp[info_in_len] = i; + tmp_len = info_in_len + 1; + } + crypto_hmac_sha256((char*)mac, + (const char*)prk, DIGEST256_LEN, + (const char*)tmp, tmp_len); + n = key_out_len < DIGEST256_LEN ? key_out_len : DIGEST256_LEN; + memcpy(outp, mac, n); + key_out_len -= n; + outp += n; + ++i; + } + + memwipe(tmp, 0, sizeof(tmp)); + memwipe(mac, 0, sizeof(mac)); + return 0; +} + /** Free a DH key exchange object. */ void diff --git a/src/common/crypto.h b/src/common/crypto.h index eb8b1de..2d31e8d 100644 --- a/src/common/crypto.h +++ b/src/common/crypto.h @@ -239,8 +239,15 @@ ssize_t crypto_dh_compute_secret(int severity, crypto_dh_t *dh, const char *pubkey, size_t pubkey_len, char *secret_out, size_t secret_out_len); void crypto_dh_free(crypto_dh_t *dh); -int crypto_expand_key_material(const char *key_in, size_t in_len, - char *key_out, size_t key_out_len); + +int crypto_expand_key_material_TAP(const uint8_t *key_in, + size_t key_in_len, + uint8_t *key_out, size_t key_out_len); +int crypto_expand_key_material_rfc5869_sha256( + const uint8_t *key_in, size_t key_in_len, + const uint8_t *salt_in, size_t salt_in_len, + const uint8_t *info_in, size_t info_in_len, + uint8_t *key_out, size_t key_out_len); /* random numbers */ int crypto_seed_rng(int startup); diff --git a/src/or/onion.c b/src/or/onion.c index cce4bdf..4720515 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -362,8 +362,8 @@ fast_server_handshake(const uint8_t *key_in, /* DIGEST_LEN bytes */ uint8_t *key_out, size_t key_out_len) { - char tmp[DIGEST_LEN+DIGEST_LEN]; - char *out = NULL; + uint8_t tmp[DIGEST_LEN+DIGEST_LEN]; + uint8_t *out = NULL; size_t out_len; int r = -1; @@ -374,7 +374,7 @@ fast_server_handshake(const uint8_t *key_in, /* DIGEST_LEN bytes */ memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN); out_len = key_out_len+DIGEST_LEN; out = tor_malloc(out_len); - if (crypto_expand_key_material(tmp, sizeof(tmp), out, out_len)) { + if (crypto_expand_key_material_TAP(tmp, sizeof(tmp), out, out_len)) { goto done; } memcpy(handshake_reply_out+DIGEST_LEN, out, DIGEST_LEN); @@ -405,8 +405,8 @@ fast_client_handshake(const uint8_t *handshake_state,/*DIGEST_LEN bytes*/ uint8_t *key_out, size_t key_out_len) { - char tmp[DIGEST_LEN+DIGEST_LEN]; - char *out; + uint8_t tmp[DIGEST_LEN+DIGEST_LEN]; + uint8_t *out; size_t out_len; int r = -1; @@ -414,7 +414,7 @@ fast_client_handshake(const uint8_t *handshake_state,/*DIGEST_LEN bytes*/ memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN); out_len = key_out_len+DIGEST_LEN; out = tor_malloc(out_len); - if (crypto_expand_key_material(tmp, sizeof(tmp), out, out_len)) { + if (crypto_expand_key_material_TAP(tmp, sizeof(tmp), out, out_len)) { goto done; } if (tor_memneq(out, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) { diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c index fd983de..6c73138 100644 --- a/src/test/test_crypto.c +++ b/src/test/test_crypto.c @@ -832,6 +832,56 @@ test_crypto_base32_decode(void) ; } +static void +test_crypto_hkdf_sha256(void *arg) +{ + uint8_t key_material[100]; + const uint8_t salt[] = "ntor-curve25519-sha256-1:key_extract"; + const size_t salt_len = strlen((char*)salt); + const uint8_t m_expand[] = "ntor-curve25519-sha256-1:key_expand"; + const size_t m_expand_len = strlen((char*)m_expand); + int r; + char *mem_op_hex_tmp = NULL; + + (void)arg; + +#define EXPAND(s) \ + r = crypto_expand_key_material_rfc5869_sha256( \ + (const uint8_t*)(s), strlen(s), \ + salt, salt_len, \ + m_expand, m_expand_len, \ + key_material, 100) + + /* Test vectors generated with ntor_ref.py */ + memset(key_material, 0, sizeof(key_material)); + EXPAND(""); + tt_int_op(r, ==, 0); + test_memeq_hex(key_material, + "d3490ed48b12a48f9547861583573fe3f19aafe3f81dc7fc75" + "eeed96d741b3290f941576c1f9f0b2d463d1ec7ab2c6bf71cd" + "d7f826c6298c00dbfe6711635d7005f0269493edf6046cc7e7" + "dcf6abe0d20c77cf363e8ffe358927817a3d3e73712cee28d8"); + + EXPAND("Tor"); + tt_int_op(r, ==, 0); + test_memeq_hex(key_material, + "5521492a85139a8d9107a2d5c0d9c91610d0f95989975ebee6" + "c02a4f8d622a6cfdf9b7c7edd3832e2760ded1eac309b76f8d" + "66c4a3c4d6225429b3a016e3c3d45911152fc87bc2de9630c3" + "961be9fdb9f93197ea8e5977180801926d3321fa21513e59ac"); + + EXPAND("AN ALARMING ITEM TO FIND ON YOUR CREDIT-RATING STATEMENT"); + tt_int_op(r, ==, 0); + test_memeq_hex(key_material, + "a2aa9b50da7e481d30463adb8f233ff06e9571a0ca6ab6df0f" + "b206fa34e5bc78d063fc291501beec53b36e5a0e434561200c" + "5f8bd13e0f88b3459600b4dc21d69363e2895321c06184879d" + "94b18f078411be70b767c7fc40679a9440a0c95ea83a23efbf"); + + done: + tor_free(mem_op_hex_tmp); +} + static void * pass_data_setup_fn(const struct testcase_t *testcase) { @@ -863,6 +913,7 @@ struct testcase_t crypto_tests[] = { { "aes_iv_AES", test_crypto_aes_iv, TT_FORK, &pass_data, (void*)"aes" }, { "aes_iv_EVP", test_crypto_aes_iv, TT_FORK, &pass_data, (void*)"evp" }, CRYPTO_LEGACY(base32_decode), + { "hkdf_sha256", test_crypto_hkdf_sha256, 0, NULL, NULL }, END_OF_TESTCASES };

1 0

[tor/master] Add a data-invariant linear-search map structure
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit cfab9f0755e3f7f0b49879ed9771fd2d325051a2 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Dec 3 13:10:33 2012 -0500 Add a data-invariant linear-search map structure I'm going to use this for looking op keys server-side for ntor. --- src/common/di_ops.c | 72 ++++++++++++++++++++++++++++++++++++++++++++ src/common/di_ops.h | 14 ++++++++ src/test/test_containers.c | 45 +++++++++++++++++++++++++++ 3 files changed, 131 insertions(+), 0 deletions(-) diff --git a/src/common/di_ops.c b/src/common/di_ops.c index 418d6e3..b73a3cc 100644 --- a/src/common/di_ops.c +++ b/src/common/di_ops.c @@ -8,6 +8,8 @@ #include "orconfig.h" #include "di_ops.h" +#include "torlog.h" +#include "util.h" /** * Timing-safe version of memcmp. As memcmp, compare the sz bytes at @@ -131,3 +133,73 @@ tor_memeq(const void *a, const void *b, size_t sz) return 1 & ((any_difference - 1) >> 8); } +/* Implement di_digest256_map_t as a linked list of entries. */ +struct di_digest256_map_t { + struct di_digest256_map_t *next; + uint8_t key[32]; + void *val; +}; + +/** Release all storage held in map, calling free_fn on each value + * as we go. */ +void +dimap_free(di_digest256_map_t *map, dimap_free_fn free_fn) +{ + while (map) { + di_digest256_map_t *victim = map; + map = map->next; + if (free_fn) + free_fn(victim->val); + tor_free(victim); + } +} + +/** Adjust the map at *map, adding an entry for key -> + * val, where key is a DIGEST256_LEN-byte key. + * + * The caller MUST NOT add a key that already appears in the map. + */ +void +dimap_add_entry(di_digest256_map_t **map, + const uint8_t *key, void *val) +{ + di_digest256_map_t *new_ent; + { + void *old_val = dimap_search(*map, key, NULL); + tor_assert(! old_val); + tor_assert(val); + } + new_ent = tor_malloc_zero(sizeof(di_digest256_map_t)); + new_ent->next = *map; + memcpy(new_ent->key, key, 32); + new_ent->val = val; + *map = new_ent; +} + +/** Search the map at map for an entry whose key is key (a + * DIGEST256_LEN-byte key) returning the corresponding value if we found one, + * and returning dflt_val if the key wasn't found. + * + * This operation takes an amount of time dependent only on the length of + * map, not on the position or presence of key within map. + */ +void * +dimap_search(const di_digest256_map_t *map, const uint8_t *key, + void *dflt_val) +{ + uintptr_t result = (uintptr_t)dflt_val; + + while (map) { + uintptr_t r = (uintptr_t) tor_memeq(map->key, key, 32); + r -= 1; /* Now r is (uintptr_t)-1 if memeq returned false, and + * 0 if memeq returned true. */ + + result &= r; + result |= ((uintptr_t)(map->val)) & ~r; + + map = map->next; + } + + return (void *)result; +} + diff --git a/src/common/di_ops.h b/src/common/di_ops.h index 8f0bb69..a86f56c 100644 --- a/src/common/di_ops.h +++ b/src/common/di_ops.h @@ -27,5 +27,19 @@ int tor_memeq(const void *a, const void *b, size_t sz); #define fast_memeq(a,b,c) (0==memcmp((a),(b),(c))) #define fast_memneq(a,b,c) (0!=memcmp((a),(b),(c))) +/** A type for a map from DIGEST256_LEN-byte blobs to void*, such that + * data lookups take an amount of time proportional only to the size + * of the map, and not to the position or presence of the item in the map. + * + * Not efficient for large maps! */ +typedef struct di_digest256_map_t di_digest256_map_t; +typedef void (*dimap_free_fn)(void *); + +void dimap_free(di_digest256_map_t *map, dimap_free_fn free_fn); +void dimap_add_entry(di_digest256_map_t **map, + const uint8_t *key, void *val); +void *dimap_search(const di_digest256_map_t *map, const uint8_t *key, + void *dflt_val); + #endif diff --git a/src/test/test_containers.c b/src/test/test_containers.c index 399ef8e..b41b3c6 100644 --- a/src/test/test_containers.c +++ b/src/test/test_containers.c @@ -782,6 +782,50 @@ test_container_order_functions(void) ; } +static void +test_di_map(void *arg) +{ + di_digest256_map_t *map = NULL; + const uint8_t key1[] = "In view of the fact that it was "; + const uint8_t key2[] = "superficially convincing, being "; + const uint8_t key3[] = "properly enciphered in a one-tim"; + const uint8_t key4[] = "e cipher scheduled for use today"; + char *v1 = tor_strdup(", it came close to causing a disaster..."); + char *v2 = tor_strdup("I regret to have to advise you that the mission"); + char *v3 = tor_strdup("was actually initiated..."); + /* -- John Brunner, _The Shockwave Rider_ */ + + (void)arg; + + /* Try searching on an empty map. */ + tt_ptr_op(NULL, ==, dimap_search(map, key1, NULL)); + tt_ptr_op(NULL, ==, dimap_search(map, key2, NULL)); + tt_ptr_op(v3, ==, dimap_search(map, key2, v3)); + dimap_free(map, NULL); + map = NULL; + + /* Add a single entry. */ + dimap_add_entry(&map, key1, v1); + tt_ptr_op(NULL, ==, dimap_search(map, key2, NULL)); + tt_ptr_op(v3, ==, dimap_search(map, key2, v3)); + tt_ptr_op(v1, ==, dimap_search(map, key1, NULL)); + + /* Now try it with three entries in the map. */ + dimap_add_entry(&map, key2, v2); + dimap_add_entry(&map, key3, v3); + tt_ptr_op(v1, ==, dimap_search(map, key1, NULL)); + tt_ptr_op(v2, ==, dimap_search(map, key2, NULL)); + tt_ptr_op(v3, ==, dimap_search(map, key3, NULL)); + tt_ptr_op(NULL, ==, dimap_search(map, key4, NULL)); + tt_ptr_op(v1, ==, dimap_search(map, key4, v1)); + + done: + tor_free(v1); + tor_free(v2); + tor_free(v3); + dimap_free(map, NULL); +} + #define CONTAINER_LEGACY(name) \ { #name, legacy_test_helper, 0, &legacy_setup, test_container_ ## name } @@ -796,6 +840,7 @@ struct testcase_t container_tests[] = { CONTAINER_LEGACY(strmap), CONTAINER_LEGACY(pqueue), CONTAINER_LEGACY(order_functions), + { "di_map", test_di_map, 0, NULL, NULL }, END_OF_TESTCASES };

1 0

[tor/master] curve25519-donna-c64: work on bigendian and alignment-happy systems
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit f06966023a4000de24feebaa2ca8438abb10c16c Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Dec 3 22:17:12 2012 -0500 curve25519-donna-c64: work on bigendian and alignment-happy systems There was one place in curve25519-donna-c64 that was relying on unaligned access and relying on little-endian values. This patch fixes that. I've sent Adam a pull request. --- src/ext/README | 3 +- src/ext/curve25519_donna/curve25519-donna-c64.c | 49 ++++++++++++++++++----- 2 files changed, 41 insertions(+), 11 deletions(-) diff --git a/src/ext/README b/src/ext/README index cd23f29..8147691 100644 --- a/src/ext/README +++ b/src/ext/README @@ -39,4 +39,5 @@ tor_queue.h curve25519_donna/*.c A copy of Adam Langley's curve25519-donna mostly-portable - implementations of curve25519. + implementations of curve25519, with a couple of portability + changes which Adam hasn't merged yet. diff --git a/src/ext/curve25519_donna/curve25519-donna-c64.c b/src/ext/curve25519_donna/curve25519-donna-c64.c index 1a8fdb6..b30bfbf 100644 --- a/src/ext/curve25519_donna/curve25519-donna-c64.c +++ b/src/ext/curve25519_donna/curve25519-donna-c64.c @@ -186,14 +186,43 @@ fsquare_times(felem output, const felem in, limb count) { output[4] = r4; } +/* Load a little-endian 64-bit number */ +limb +load_limb(const u8 *in) +{ + return + ((limb)in[0]) | + (((limb)in[1]) << 8) | + (((limb)in[2]) << 16) | + (((limb)in[3]) << 24) | + (((limb)in[4]) << 32) | + (((limb)in[5]) << 40) | + (((limb)in[6]) << 48) | + (((limb)in[7]) << 56); +} + +void +store_limb(u8 *out, limb in) +{ + out[0] = in & 0xff; + out[1] = (in >> 8) & 0xff; + out[2] = (in >> 16) & 0xff; + out[3] = (in >> 24) & 0xff; + out[4] = (in >> 32) & 0xff; + out[5] = (in >> 40) & 0xff; + out[6] = (in >> 48) & 0xff; + out[7] = (in >> 56) & 0xff; +} + /* Take a little-endian, 32-byte number and expand it into polynomial form */ static void -fexpand(limb *output, const u8 *in) { - output[0] = *((const uint64_t *)(in)) & 0x7ffffffffffff; - output[1] = (*((const uint64_t *)(in+6)) >> 3) & 0x7ffffffffffff; - output[2] = (*((const uint64_t *)(in+12)) >> 6) & 0x7ffffffffffff; - output[3] = (*((const uint64_t *)(in+19)) >> 1) & 0x7ffffffffffff; - output[4] = (*((const uint64_t *)(in+24)) >> 12) & 0x7ffffffffffff; +fexpand(limb *output, const u8 *in) +{ + output[0] = load_limb(in) & 0x7ffffffffffff; + output[1] = (load_limb(in+6) >> 3) & 0x7ffffffffffff; + output[2] = (load_limb(in+12) >> 6) & 0x7ffffffffffff; + output[3] = (load_limb(in+19) >> 1) & 0x7ffffffffffff; + output[4] = (load_limb(in+24) >> 12) & 0x7ffffffffffff; } /* Take a fully reduced polynomial form number and contract it into a @@ -248,10 +277,10 @@ fcontract(u8 *output, const felem input) { t[4] += t[3] >> 51; t[3] &= 0x7ffffffffffff; t[4] &= 0x7ffffffffffff; - *((uint64_t *)(output)) = t[0] | (t[1] << 51); - *((uint64_t *)(output+8)) = (t[1] >> 13) | (t[2] << 38); - *((uint64_t *)(output+16)) = (t[2] >> 26) | (t[3] << 25); - *((uint64_t *)(output+24)) = (t[3] >> 39) | (t[4] << 12); + store_limb(output, t[0] | (t[1] << 51)); + store_limb(output+8, (t[1] >> 13) | (t[2] << 38)); + store_limb(output+16, (t[2] >> 26) | (t[3] << 25)); + store_limb(output+24, (t[3] >> 39) | (t[4] << 12)); } /* Input: Q, Q', Q-Q'

1 0

[tor/master] Add fallback implementations for curve25519: curve25519_donna
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit 9c3c571c0c51bc11717b795d800b6523ff4ccfd8 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Dec 3 14:50:48 2012 -0500 Add fallback implementations for curve25519: curve25519_donna This is copied from Adam Langley's curve25519-donna package, as of commit 09427c9cab32075c06c3487aa01628030e1c5ae7. --- src/ext/README | 5 +- src/ext/curve25519_donna/README | 44 ++ src/ext/curve25519_donna/curve25519-donna-c64.c | 421 +++++++++++++ src/ext/curve25519_donna/curve25519-donna.c | 724 +++++++++++++++++++++++ 4 files changed, 1193 insertions(+), 1 deletions(-) diff --git a/src/ext/README b/src/ext/README index 8c850be..cd23f29 100644 --- a/src/ext/README +++ b/src/ext/README @@ -36,4 +36,7 @@ tor_queue.h sys/queue.h, and the ones that do have diverged in incompatible ways. (CIRCLEQ or no CIRCLEQ? SIMPLQ or STAILQ?) - +curve25519_donna/*.c + + A copy of Adam Langley's curve25519-donna mostly-portable + implementations of curve25519. diff --git a/src/ext/curve25519_donna/README b/src/ext/curve25519_donna/README new file mode 100644 index 0000000..9f77bd7 --- /dev/null +++ b/src/ext/curve25519_donna/README @@ -0,0 +1,44 @@ +See http://code.google.com/p/curve25519-donna/ for details. + +BUILDING: + +If you run `make`, two .a archives will be built, similar to djb's curve25519 +code. Alternatively, read on: + +The C implementation is contained within curve25519-donna.c. It has no external +dependancies and is BSD licenced. You can copy/include/link it directly in with +your program. Recommended C flags: -O2 + +The x86-64 bit implementation is contained within curve25519-donna-x86-64.c and +curve25519-donna-x86-64.s. Build like this: + +% cpp curve25519-donna-x86-64.s > curve25519-donna-x86-64.s.pp +% as -o curve25519-donna-x86-64.s.o curve25519-donna-x86-64.s.pp +% gcc -O2 -c curve25519-donna-x86-64.c + +Then the two .o files can be linked in + +USAGE: + +The usage is exactly the same as djb's code (as described at +http://cr.yp.to/ecdh.html) expect that the function is called curve25519_donna. + +In short, + +To generate a private key, generate 32 random bytes and: + + mysecret[0] &= 248; + mysecret[31] &= 127; + mysecret[31] |= 64; + +To generate the public key, just do + + static const uint8_t basepoint[32] = {9}; + curve25519_donna(mypublic, mysecret, basepoint); + +To generate an agreed key do: + uint8_t shared_key[32]; + curve25519_donna(shared_key, mysecret, theirpublic); + +And hash the shared_key with a cryptographic hash function before using. + diff --git a/src/ext/curve25519_donna/curve25519-donna-c64.c b/src/ext/curve25519_donna/curve25519-donna-c64.c new file mode 100644 index 0000000..4f9dcc0 --- /dev/null +++ b/src/ext/curve25519_donna/curve25519-donna-c64.c @@ -0,0 +1,421 @@ +/* Copyright 2008, Google Inc. + * All rights reserved. + * + * Code released into the public domain. + * + * curve25519-donna: Curve25519 elliptic curve, public key function + * + * http://code.google.com/p/curve25519-donna/ + * + * Adam Langley <agl(a)imperialviolet.org> + * + * Derived from public domain C code by Daniel J. Bernstein <djb(a)cr.yp.to> + * + * More information about curve25519 can be found here + * http://cr.yp.to/ecdh.html + * + * djb's sample implementation of curve25519 is written in a special assembly + * language called qhasm and uses the floating point registers. + * + * This is, almost, a clean room reimplementation from the curve25519 paper. It + * uses many of the tricks described therein. Only the crecip function is taken + * from the sample implementation. + */ + +#include <string.h> +#include <stdint.h> + +typedef uint8_t u8; +typedef uint64_t limb; +typedef limb felem[5]; +// This is a special gcc mode for 128-bit integers. It's implemented on 64-bit +// platforms only as far as I know. +typedef unsigned uint128_t __attribute__((mode(TI))); + +#undef force_inline +#define force_inline __attribute__((always_inline)) + +/* Sum two numbers: output += in */ +static void force_inline +fsum(limb *output, const limb *in) { + output[0] += in[0]; + output[1] += in[1]; + output[2] += in[2]; + output[3] += in[3]; + output[4] += in[4]; +} + +/* Find the difference of two numbers: output = in - output + * (note the order of the arguments!) + * + * Assumes that out[i] < 2**52 + * On return, out[i] < 2**55 + */ +static void force_inline +fdifference_backwards(felem out, const felem in) { + /* 152 is 19 << 3 */ + static const limb two54m152 = (((limb)1) << 54) - 152; + static const limb two54m8 = (((limb)1) << 54) - 8; + + out[0] = in[0] + two54m152 - out[0]; + out[1] = in[1] + two54m8 - out[1]; + out[2] = in[2] + two54m8 - out[2]; + out[3] = in[3] + two54m8 - out[3]; + out[4] = in[4] + two54m8 - out[4]; +} + +/* Multiply a number by a scalar: output = in * scalar */ +static void force_inline +fscalar_product(felem output, const felem in, const limb scalar) { + uint128_t a; + + a = ((uint128_t) in[0]) * scalar; + output[0] = ((limb)a) & 0x7ffffffffffff; + + a = ((uint128_t) in[1]) * scalar + ((limb) (a >> 51)); + output[1] = ((limb)a) & 0x7ffffffffffff; + + a = ((uint128_t) in[2]) * scalar + ((limb) (a >> 51)); + output[2] = ((limb)a) & 0x7ffffffffffff; + + a = ((uint128_t) in[3]) * scalar + ((limb) (a >> 51)); + output[3] = ((limb)a) & 0x7ffffffffffff; + + a = ((uint128_t) in[4]) * scalar + ((limb) (a >> 51)); + output[4] = ((limb)a) & 0x7ffffffffffff; + + output[0] += (a >> 51) * 19; +} + +/* Multiply two numbers: output = in2 * in + * + * output must be distinct to both inputs. The inputs are reduced coefficient + * form, the output is not. + * + * Assumes that in[i] < 2**55 and likewise for in2. + * On return, output[i] < 2**52 + */ +static void force_inline +fmul(felem output, const felem in2, const felem in) { + uint128_t t[5]; + limb r0,r1,r2,r3,r4,s0,s1,s2,s3,s4,c; + + r0 = in[0]; + r1 = in[1]; + r2 = in[2]; + r3 = in[3]; + r4 = in[4]; + + s0 = in2[0]; + s1 = in2[1]; + s2 = in2[2]; + s3 = in2[3]; + s4 = in2[4]; + + t[0] = ((uint128_t) r0) * s0; + t[1] = ((uint128_t) r0) * s1 + ((uint128_t) r1) * s0; + t[2] = ((uint128_t) r0) * s2 + ((uint128_t) r2) * s0 + ((uint128_t) r1) * s1; + t[3] = ((uint128_t) r0) * s3 + ((uint128_t) r3) * s0 + ((uint128_t) r1) * s2 + ((uint128_t) r2) * s1; + t[4] = ((uint128_t) r0) * s4 + ((uint128_t) r4) * s0 + ((uint128_t) r3) * s1 + ((uint128_t) r1) * s3 + ((uint128_t) r2) * s2; + + r4 *= 19; + r1 *= 19; + r2 *= 19; + r3 *= 19; + + t[0] += ((uint128_t) r4) * s1 + ((uint128_t) r1) * s4 + ((uint128_t) r2) * s3 + ((uint128_t) r3) * s2; + t[1] += ((uint128_t) r4) * s2 + ((uint128_t) r2) * s4 + ((uint128_t) r3) * s3; + t[2] += ((uint128_t) r4) * s3 + ((uint128_t) r3) * s4; + t[3] += ((uint128_t) r4) * s4; + + r0 = (limb)t[0] & 0x7ffffffffffff; c = (limb)(t[0] >> 51); + t[1] += c; r1 = (limb)t[1] & 0x7ffffffffffff; c = (limb)(t[1] >> 51); + t[2] += c; r2 = (limb)t[2] & 0x7ffffffffffff; c = (limb)(t[2] >> 51); + t[3] += c; r3 = (limb)t[3] & 0x7ffffffffffff; c = (limb)(t[3] >> 51); + t[4] += c; r4 = (limb)t[4] & 0x7ffffffffffff; c = (limb)(t[4] >> 51); + r0 += c * 19; c = r0 >> 51; r0 = r0 & 0x7ffffffffffff; + r1 += c; c = r1 >> 51; r1 = r1 & 0x7ffffffffffff; + r2 += c; + + output[0] = r0; + output[1] = r1; + output[2] = r2; + output[3] = r3; + output[4] = r4; +} + +static void force_inline +fsquare_times(felem output, const felem in, limb count) { + uint128_t t[5]; + limb r0,r1,r2,r3,r4,c; + limb d0,d1,d2,d4,d419; + + r0 = in[0]; + r1 = in[1]; + r2 = in[2]; + r3 = in[3]; + r4 = in[4]; + + do { + d0 = r0 * 2; + d1 = r1 * 2; + d2 = r2 * 2 * 19; + d419 = r4 * 19; + d4 = d419 * 2; + + t[0] = ((uint128_t) r0) * r0 + ((uint128_t) d4) * r1 + (((uint128_t) d2) * (r3 )); + t[1] = ((uint128_t) d0) * r1 + ((uint128_t) d4) * r2 + (((uint128_t) r3) * (r3 * 19)); + t[2] = ((uint128_t) d0) * r2 + ((uint128_t) r1) * r1 + (((uint128_t) d4) * (r3 )); + t[3] = ((uint128_t) d0) * r3 + ((uint128_t) d1) * r2 + (((uint128_t) r4) * (d419 )); + t[4] = ((uint128_t) d0) * r4 + ((uint128_t) d1) * r3 + (((uint128_t) r2) * (r2 )); + + r0 = (limb)t[0] & 0x7ffffffffffff; c = (limb)(t[0] >> 51); + t[1] += c; r1 = (limb)t[1] & 0x7ffffffffffff; c = (limb)(t[1] >> 51); + t[2] += c; r2 = (limb)t[2] & 0x7ffffffffffff; c = (limb)(t[2] >> 51); + t[3] += c; r3 = (limb)t[3] & 0x7ffffffffffff; c = (limb)(t[3] >> 51); + t[4] += c; r4 = (limb)t[4] & 0x7ffffffffffff; c = (limb)(t[4] >> 51); + r0 += c * 19; c = r0 >> 51; r0 = r0 & 0x7ffffffffffff; + r1 += c; c = r1 >> 51; r1 = r1 & 0x7ffffffffffff; + r2 += c; + } while(--count); + + output[0] = r0; + output[1] = r1; + output[2] = r2; + output[3] = r3; + output[4] = r4; +} + +/* Take a little-endian, 32-byte number and expand it into polynomial form */ +static void +fexpand(limb *output, const u8 *in) { + output[0] = *((const uint64_t *)(in)) & 0x7ffffffffffff; + output[1] = (*((const uint64_t *)(in+6)) >> 3) & 0x7ffffffffffff; + output[2] = (*((const uint64_t *)(in+12)) >> 6) & 0x7ffffffffffff; + output[3] = (*((const uint64_t *)(in+19)) >> 1) & 0x7ffffffffffff; + output[4] = (*((const uint64_t *)(in+24)) >> 12) & 0x7ffffffffffff; +} + +/* Take a fully reduced polynomial form number and contract it into a + * little-endian, 32-byte array + */ +static void +fcontract(u8 *output, const felem input) { + uint128_t t[5]; + + t[0] = input[0]; + t[1] = input[1]; + t[2] = input[2]; + t[3] = input[3]; + t[4] = input[4]; + + t[1] += t[0] >> 51; t[0] &= 0x7ffffffffffff; + t[2] += t[1] >> 51; t[1] &= 0x7ffffffffffff; + t[3] += t[2] >> 51; t[2] &= 0x7ffffffffffff; + t[4] += t[3] >> 51; t[3] &= 0x7ffffffffffff; + t[0] += 19 * (t[4] >> 51); t[4] &= 0x7ffffffffffff; + + t[1] += t[0] >> 51; t[0] &= 0x7ffffffffffff; + t[2] += t[1] >> 51; t[1] &= 0x7ffffffffffff; + t[3] += t[2] >> 51; t[2] &= 0x7ffffffffffff; + t[4] += t[3] >> 51; t[3] &= 0x7ffffffffffff; + t[0] += 19 * (t[4] >> 51); t[4] &= 0x7ffffffffffff; + + /* now t is between 0 and 2^255-1, properly carried. */ + /* case 1: between 0 and 2^255-20. case 2: between 2^255-19 and 2^255-1. */ + + t[0] += 19; + + t[1] += t[0] >> 51; t[0] &= 0x7ffffffffffff; + t[2] += t[1] >> 51; t[1] &= 0x7ffffffffffff; + t[3] += t[2] >> 51; t[2] &= 0x7ffffffffffff; + t[4] += t[3] >> 51; t[3] &= 0x7ffffffffffff; + t[0] += 19 * (t[4] >> 51); t[4] &= 0x7ffffffffffff; + + /* now between 19 and 2^255-1 in both cases, and offset by 19. */ + + t[0] += 0x8000000000000 - 19; + t[1] += 0x8000000000000 - 1; + t[2] += 0x8000000000000 - 1; + t[3] += 0x8000000000000 - 1; + t[4] += 0x8000000000000 - 1; + + /* now between 2^255 and 2^256-20, and offset by 2^255. */ + + t[1] += t[0] >> 51; t[0] &= 0x7ffffffffffff; + t[2] += t[1] >> 51; t[1] &= 0x7ffffffffffff; + t[3] += t[2] >> 51; t[2] &= 0x7ffffffffffff; + t[4] += t[3] >> 51; t[3] &= 0x7ffffffffffff; + t[4] &= 0x7ffffffffffff; + + *((uint64_t *)(output)) = t[0] | (t[1] << 51); + *((uint64_t *)(output+8)) = (t[1] >> 13) | (t[2] << 38); + *((uint64_t *)(output+16)) = (t[2] >> 26) | (t[3] << 25); + *((uint64_t *)(output+24)) = (t[3] >> 39) | (t[4] << 12); +} + +/* Input: Q, Q', Q-Q' + * Output: 2Q, Q+Q' + * + * x2 z3: long form + * x3 z3: long form + * x z: short form, destroyed + * xprime zprime: short form, destroyed + * qmqp: short form, preserved + */ +static void +fmonty(limb *x2, limb *z2, /* output 2Q */ + limb *x3, limb *z3, /* output Q + Q' */ + limb *x, limb *z, /* input Q */ + limb *xprime, limb *zprime, /* input Q' */ + const limb *qmqp /* input Q - Q' */) { + limb origx[5], origxprime[5], zzz[5], xx[5], zz[5], xxprime[5], + zzprime[5], zzzprime[5]; + + memcpy(origx, x, 5 * sizeof(limb)); + fsum(x, z); + fdifference_backwards(z, origx); // does x - z + + memcpy(origxprime, xprime, sizeof(limb) * 5); + fsum(xprime, zprime); + fdifference_backwards(zprime, origxprime); + fmul(xxprime, xprime, z); + fmul(zzprime, x, zprime); + memcpy(origxprime, xxprime, sizeof(limb) * 5); + fsum(xxprime, zzprime); + fdifference_backwards(zzprime, origxprime); + fsquare_times(x3, xxprime, 1); + fsquare_times(zzzprime, zzprime, 1); + fmul(z3, zzzprime, qmqp); + + fsquare_times(xx, x, 1); + fsquare_times(zz, z, 1); + fmul(x2, xx, zz); + fdifference_backwards(zz, xx); // does zz = xx - zz + fscalar_product(zzz, zz, 121665); + fsum(zzz, xx); + fmul(z2, zz, zzz); +} + +// ----------------------------------------------------------------------------- +// Maybe swap the contents of two limb arrays (@a and @b), each @len elements +// long. Perform the swap iff @swap is non-zero. +// +// This function performs the swap without leaking any side-channel +// information. +// ----------------------------------------------------------------------------- +static void +swap_conditional(limb a[5], limb b[5], limb iswap) { + unsigned i; + const limb swap = -iswap; + + for (i = 0; i < 5; ++i) { + const limb x = swap & (a[i] ^ b[i]); + a[i] ^= x; + b[i] ^= x; + } +} + +/* Calculates nQ where Q is the x-coordinate of a point on the curve + * + * resultx/resultz: the x coordinate of the resulting curve point (short form) + * n: a little endian, 32-byte number + * q: a point of the curve (short form) + */ +static void +cmult(limb *resultx, limb *resultz, const u8 *n, const limb *q) { + limb a[5] = {0}, b[5] = {1}, c[5] = {1}, d[5] = {0}; + limb *nqpqx = a, *nqpqz = b, *nqx = c, *nqz = d, *t; + limb e[5] = {0}, f[5] = {1}, g[5] = {0}, h[5] = {1}; + limb *nqpqx2 = e, *nqpqz2 = f, *nqx2 = g, *nqz2 = h; + + unsigned i, j; + + memcpy(nqpqx, q, sizeof(limb) * 5); + + for (i = 0; i < 32; ++i) { + u8 byte = n[31 - i]; + for (j = 0; j < 8; ++j) { + const limb bit = byte >> 7; + + swap_conditional(nqx, nqpqx, bit); + swap_conditional(nqz, nqpqz, bit); + fmonty(nqx2, nqz2, + nqpqx2, nqpqz2, + nqx, nqz, + nqpqx, nqpqz, + q); + swap_conditional(nqx2, nqpqx2, bit); + swap_conditional(nqz2, nqpqz2, bit); + + t = nqx; + nqx = nqx2; + nqx2 = t; + t = nqz; + nqz = nqz2; + nqz2 = t; + t = nqpqx; + nqpqx = nqpqx2; + nqpqx2 = t; + t = nqpqz; + nqpqz = nqpqz2; + nqpqz2 = t; + + byte <<= 1; + } + } + + memcpy(resultx, nqx, sizeof(limb) * 5); + memcpy(resultz, nqz, sizeof(limb) * 5); +} + + +// ----------------------------------------------------------------------------- +// Shamelessly copied from djb's code, tightened a little +// ----------------------------------------------------------------------------- +static void +crecip(felem out, const felem z) { + felem a,t0,b,c; + + /* 2 */ fsquare_times(a, z, 1); // a = 2 + /* 8 */ fsquare_times(t0, a, 2); + /* 9 */ fmul(b, t0, z); // b = 9 + /* 11 */ fmul(a, b, a); // a = 11 + /* 22 */ fsquare_times(t0, a, 1); + /* 2^5 - 2^0 = 31 */ fmul(b, t0, b); + /* 2^10 - 2^5 */ fsquare_times(t0, b, 5); + /* 2^10 - 2^0 */ fmul(b, t0, b); + /* 2^20 - 2^10 */ fsquare_times(t0, b, 10); + /* 2^20 - 2^0 */ fmul(c, t0, b); + /* 2^40 - 2^20 */ fsquare_times(t0, c, 20); + /* 2^40 - 2^0 */ fmul(t0, t0, c); + /* 2^50 - 2^10 */ fsquare_times(t0, t0, 10); + /* 2^50 - 2^0 */ fmul(b, t0, b); + /* 2^100 - 2^50 */ fsquare_times(t0, b, 50); + /* 2^100 - 2^0 */ fmul(c, t0, b); + /* 2^200 - 2^100 */ fsquare_times(t0, c, 100); + /* 2^200 - 2^0 */ fmul(t0, t0, c); + /* 2^250 - 2^50 */ fsquare_times(t0, t0, 50); + /* 2^250 - 2^0 */ fmul(t0, t0, b); + /* 2^255 - 2^5 */ fsquare_times(t0, t0, 5); + /* 2^255 - 21 */ fmul(out, t0, a); +} + +int +curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) { + limb bp[5], x[5], z[5], zmone[5]; + uint8_t e[32]; + int i; + + for (i = 0;i < 32;++i) e[i] = secret[i]; + e[0] &= 248; + e[31] &= 127; + e[31] |= 64; + + fexpand(bp, basepoint); + cmult(x, z, e, bp); + crecip(zmone, z); + fmul(z, x, zmone); + fcontract(mypublic, z); + return 0; +} diff --git a/src/ext/curve25519_donna/curve25519-donna.c b/src/ext/curve25519_donna/curve25519-donna.c new file mode 100644 index 0000000..d4b1b1e --- /dev/null +++ b/src/ext/curve25519_donna/curve25519-donna.c @@ -0,0 +1,724 @@ +/* Copyright 2008, Google Inc. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following disclaimer + * in the documentation and/or other materials provided with the + * distribution. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * + * curve25519-donna: Curve25519 elliptic curve, public key function + * + * http://code.google.com/p/curve25519-donna/ + * + * Adam Langley <agl(a)imperialviolet.org> + * + * Derived from public domain C code by Daniel J. Bernstein <djb(a)cr.yp.to> + * + * More information about curve25519 can be found here + * http://cr.yp.to/ecdh.html + * + * djb's sample implementation of curve25519 is written in a special assembly + * language called qhasm and uses the floating point registers. + * + * This is, almost, a clean room reimplementation from the curve25519 paper. It + * uses many of the tricks described therein. Only the crecip function is taken + * from the sample implementation. + */ + +#include <string.h> +#include <stdint.h> + +typedef uint8_t u8; +typedef int32_t s32; +typedef int64_t limb; + +/* Field element representation: + * + * Field elements are written as an array of signed, 64-bit limbs, least + * significant first. The value of the field element is: + * x[0] + 2^26·x[1] + x^51·x[2] + 2^102·x[3] + ... + * + * i.e. the limbs are 26, 25, 26, 25, ... bits wide. + */ + +/* Sum two numbers: output += in */ +static void fsum(limb *output, const limb *in) { + unsigned i; + for (i = 0; i < 10; i += 2) { + output[0+i] = (output[0+i] + in[0+i]); + output[1+i] = (output[1+i] + in[1+i]); + } +} + +/* Find the difference of two numbers: output = in - output + * (note the order of the arguments!) + */ +static void fdifference(limb *output, const limb *in) { + unsigned i; + for (i = 0; i < 10; ++i) { + output[i] = (in[i] - output[i]); + } +} + +/* Multiply a number by a scalar: output = in * scalar */ +static void fscalar_product(limb *output, const limb *in, const limb scalar) { + unsigned i; + for (i = 0; i < 10; ++i) { + output[i] = in[i] * scalar; + } +} + +/* Multiply two numbers: output = in2 * in + * + * output must be distinct to both inputs. The inputs are reduced coefficient + * form, the output is not. + */ +static void fproduct(limb *output, const limb *in2, const limb *in) { + output[0] = ((limb) ((s32) in2[0])) * ((s32) in[0]); + output[1] = ((limb) ((s32) in2[0])) * ((s32) in[1]) + + ((limb) ((s32) in2[1])) * ((s32) in[0]); + output[2] = 2 * ((limb) ((s32) in2[1])) * ((s32) in[1]) + + ((limb) ((s32) in2[0])) * ((s32) in[2]) + + ((limb) ((s32) in2[2])) * ((s32) in[0]); + output[3] = ((limb) ((s32) in2[1])) * ((s32) in[2]) + + ((limb) ((s32) in2[2])) * ((s32) in[1]) + + ((limb) ((s32) in2[0])) * ((s32) in[3]) + + ((limb) ((s32) in2[3])) * ((s32) in[0]); + output[4] = ((limb) ((s32) in2[2])) * ((s32) in[2]) + + 2 * (((limb) ((s32) in2[1])) * ((s32) in[3]) + + ((limb) ((s32) in2[3])) * ((s32) in[1])) + + ((limb) ((s32) in2[0])) * ((s32) in[4]) + + ((limb) ((s32) in2[4])) * ((s32) in[0]); + output[5] = ((limb) ((s32) in2[2])) * ((s32) in[3]) + + ((limb) ((s32) in2[3])) * ((s32) in[2]) + + ((limb) ((s32) in2[1])) * ((s32) in[4]) + + ((limb) ((s32) in2[4])) * ((s32) in[1]) + + ((limb) ((s32) in2[0])) * ((s32) in[5]) + + ((limb) ((s32) in2[5])) * ((s32) in[0]); + output[6] = 2 * (((limb) ((s32) in2[3])) * ((s32) in[3]) + + ((limb) ((s32) in2[1])) * ((s32) in[5]) + + ((limb) ((s32) in2[5])) * ((s32) in[1])) + + ((limb) ((s32) in2[2])) * ((s32) in[4]) + + ((limb) ((s32) in2[4])) * ((s32) in[2]) + + ((limb) ((s32) in2[0])) * ((s32) in[6]) + + ((limb) ((s32) in2[6])) * ((s32) in[0]); + output[7] = ((limb) ((s32) in2[3])) * ((s32) in[4]) + + ((limb) ((s32) in2[4])) * ((s32) in[3]) + + ((limb) ((s32) in2[2])) * ((s32) in[5]) + + ((limb) ((s32) in2[5])) * ((s32) in[2]) + + ((limb) ((s32) in2[1])) * ((s32) in[6]) + + ((limb) ((s32) in2[6])) * ((s32) in[1]) + + ((limb) ((s32) in2[0])) * ((s32) in[7]) + + ((limb) ((s32) in2[7])) * ((s32) in[0]); + output[8] = ((limb) ((s32) in2[4])) * ((s32) in[4]) + + 2 * (((limb) ((s32) in2[3])) * ((s32) in[5]) + + ((limb) ((s32) in2[5])) * ((s32) in[3]) + + ((limb) ((s32) in2[1])) * ((s32) in[7]) + + ((limb) ((s32) in2[7])) * ((s32) in[1])) + + ((limb) ((s32) in2[2])) * ((s32) in[6]) + + ((limb) ((s32) in2[6])) * ((s32) in[2]) + + ((limb) ((s32) in2[0])) * ((s32) in[8]) + + ((limb) ((s32) in2[8])) * ((s32) in[0]); + output[9] = ((limb) ((s32) in2[4])) * ((s32) in[5]) + + ((limb) ((s32) in2[5])) * ((s32) in[4]) + + ((limb) ((s32) in2[3])) * ((s32) in[6]) + + ((limb) ((s32) in2[6])) * ((s32) in[3]) + + ((limb) ((s32) in2[2])) * ((s32) in[7]) + + ((limb) ((s32) in2[7])) * ((s32) in[2]) + + ((limb) ((s32) in2[1])) * ((s32) in[8]) + + ((limb) ((s32) in2[8])) * ((s32) in[1]) + + ((limb) ((s32) in2[0])) * ((s32) in[9]) + + ((limb) ((s32) in2[9])) * ((s32) in[0]); + output[10] = 2 * (((limb) ((s32) in2[5])) * ((s32) in[5]) + + ((limb) ((s32) in2[3])) * ((s32) in[7]) + + ((limb) ((s32) in2[7])) * ((s32) in[3]) + + ((limb) ((s32) in2[1])) * ((s32) in[9]) + + ((limb) ((s32) in2[9])) * ((s32) in[1])) + + ((limb) ((s32) in2[4])) * ((s32) in[6]) + + ((limb) ((s32) in2[6])) * ((s32) in[4]) + + ((limb) ((s32) in2[2])) * ((s32) in[8]) + + ((limb) ((s32) in2[8])) * ((s32) in[2]); + output[11] = ((limb) ((s32) in2[5])) * ((s32) in[6]) + + ((limb) ((s32) in2[6])) * ((s32) in[5]) + + ((limb) ((s32) in2[4])) * ((s32) in[7]) + + ((limb) ((s32) in2[7])) * ((s32) in[4]) + + ((limb) ((s32) in2[3])) * ((s32) in[8]) + + ((limb) ((s32) in2[8])) * ((s32) in[3]) + + ((limb) ((s32) in2[2])) * ((s32) in[9]) + + ((limb) ((s32) in2[9])) * ((s32) in[2]); + output[12] = ((limb) ((s32) in2[6])) * ((s32) in[6]) + + 2 * (((limb) ((s32) in2[5])) * ((s32) in[7]) + + ((limb) ((s32) in2[7])) * ((s32) in[5]) + + ((limb) ((s32) in2[3])) * ((s32) in[9]) + + ((limb) ((s32) in2[9])) * ((s32) in[3])) + + ((limb) ((s32) in2[4])) * ((s32) in[8]) + + ((limb) ((s32) in2[8])) * ((s32) in[4]); + output[13] = ((limb) ((s32) in2[6])) * ((s32) in[7]) + + ((limb) ((s32) in2[7])) * ((s32) in[6]) + + ((limb) ((s32) in2[5])) * ((s32) in[8]) + + ((limb) ((s32) in2[8])) * ((s32) in[5]) + + ((limb) ((s32) in2[4])) * ((s32) in[9]) + + ((limb) ((s32) in2[9])) * ((s32) in[4]); + output[14] = 2 * (((limb) ((s32) in2[7])) * ((s32) in[7]) + + ((limb) ((s32) in2[5])) * ((s32) in[9]) + + ((limb) ((s32) in2[9])) * ((s32) in[5])) + + ((limb) ((s32) in2[6])) * ((s32) in[8]) + + ((limb) ((s32) in2[8])) * ((s32) in[6]); + output[15] = ((limb) ((s32) in2[7])) * ((s32) in[8]) + + ((limb) ((s32) in2[8])) * ((s32) in[7]) + + ((limb) ((s32) in2[6])) * ((s32) in[9]) + + ((limb) ((s32) in2[9])) * ((s32) in[6]); + output[16] = ((limb) ((s32) in2[8])) * ((s32) in[8]) + + 2 * (((limb) ((s32) in2[7])) * ((s32) in[9]) + + ((limb) ((s32) in2[9])) * ((s32) in[7])); + output[17] = ((limb) ((s32) in2[8])) * ((s32) in[9]) + + ((limb) ((s32) in2[9])) * ((s32) in[8]); + output[18] = 2 * ((limb) ((s32) in2[9])) * ((s32) in[9]); +} + +/* Reduce a long form to a short form by taking the input mod 2^255 - 19. */ +static void freduce_degree(limb *output) { + /* Each of these shifts and adds ends up multiplying the value by 19. */ + output[8] += output[18] << 4; + output[8] += output[18] << 1; + output[8] += output[18]; + output[7] += output[17] << 4; + output[7] += output[17] << 1; + output[7] += output[17]; + output[6] += output[16] << 4; + output[6] += output[16] << 1; + output[6] += output[16]; + output[5] += output[15] << 4; + output[5] += output[15] << 1; + output[5] += output[15]; + output[4] += output[14] << 4; + output[4] += output[14] << 1; + output[4] += output[14]; + output[3] += output[13] << 4; + output[3] += output[13] << 1; + output[3] += output[13]; + output[2] += output[12] << 4; + output[2] += output[12] << 1; + output[2] += output[12]; + output[1] += output[11] << 4; + output[1] += output[11] << 1; + output[1] += output[11]; + output[0] += output[10] << 4; + output[0] += output[10] << 1; + output[0] += output[10]; +} + +#if (-1 & 3) != 3 +#error "This code only works on a two's complement system" +#endif + +/* return v / 2^26, using only shifts and adds. */ +static inline limb +div_by_2_26(const limb v) +{ + /* High word of v; no shift needed*/ + const uint32_t highword = ((uint64_t) v) >> 32; + /* Set to all 1s if v was negative; else set to 0s. */ + const int32_t sign = ((int32_t) highword) >> 31; + /* Set to 0x3ffffff if v was negative; else set to 0. */ + const int32_t roundoff = ((uint32_t) sign) >> 6; + /* Should return v / (1<<26) */ + return (v + roundoff) >> 26; +} + +/* return v / (2^25), using only shifts and adds. */ +static inline limb +div_by_2_25(const limb v) +{ + /* High word of v; no shift needed*/ + const uint32_t highword = ((uint64_t) v) >> 32; + /* Set to all 1s if v was negative; else set to 0s. */ + const int32_t sign = ((int32_t) highword) >> 31; + /* Set to 0x1ffffff if v was negative; else set to 0. */ + const int32_t roundoff = ((uint32_t) sign) >> 7; + /* Should return v / (1<<25) */ + return (v + roundoff) >> 25; +} + +static inline s32 +div_s32_by_2_25(const s32 v) +{ + const s32 roundoff = ((uint32_t)(v >> 31)) >> 7; + return (v + roundoff) >> 25; +} + +/* Reduce all coefficients of the short form input so that |x| < 2^26. + * + * On entry: |output[i]| < 2^62 + */ +static void freduce_coefficients(limb *output) { + unsigned i; + + output[10] = 0; + + for (i = 0; i < 10; i += 2) { + limb over = div_by_2_26(output[i]); + output[i] -= over << 26; + output[i+1] += over; + + over = div_by_2_25(output[i+1]); + output[i+1] -= over << 25; + output[i+2] += over; + } + /* Now |output[10]| < 2 ^ 38 and all other coefficients are reduced. */ + output[0] += output[10] << 4; + output[0] += output[10] << 1; + output[0] += output[10]; + + output[10] = 0; + + /* Now output[1..9] are reduced, and |output[0]| < 2^26 + 19 * 2^38 + * So |over| will be no more than 77825 */ + { + limb over = div_by_2_26(output[0]); + output[0] -= over << 26; + output[1] += over; + } + + /* Now output[0,2..9] are reduced, and |output[1]| < 2^25 + 77825 + * So |over| will be no more than 1. */ + { + /* output[1] fits in 32 bits, so we can use div_s32_by_2_25 here. */ + s32 over32 = div_s32_by_2_25(output[1]); + output[1] -= over32 << 25; + output[2] += over32; + } + + /* Finally, output[0,1,3..9] are reduced, and output[2] is "nearly reduced": + * we have |output[2]| <= 2^26. This is good enough for all of our math, + * but it will require an extra freduce_coefficients before fcontract. */ +} + +/* A helpful wrapper around fproduct: output = in * in2. + * + * output must be distinct to both inputs. The output is reduced degree and + * reduced coefficient. + */ +static void +fmul(limb *output, const limb *in, const limb *in2) { + limb t[19]; + fproduct(t, in, in2); + freduce_degree(t); + freduce_coefficients(t); + memcpy(output, t, sizeof(limb) * 10); +} + +static void fsquare_inner(limb *output, const limb *in) { + output[0] = ((limb) ((s32) in[0])) * ((s32) in[0]); + output[1] = 2 * ((limb) ((s32) in[0])) * ((s32) in[1]); + output[2] = 2 * (((limb) ((s32) in[1])) * ((s32) in[1]) + + ((limb) ((s32) in[0])) * ((s32) in[2])); + output[3] = 2 * (((limb) ((s32) in[1])) * ((s32) in[2]) + + ((limb) ((s32) in[0])) * ((s32) in[3])); + output[4] = ((limb) ((s32) in[2])) * ((s32) in[2]) + + 4 * ((limb) ((s32) in[1])) * ((s32) in[3]) + + 2 * ((limb) ((s32) in[0])) * ((s32) in[4]); + output[5] = 2 * (((limb) ((s32) in[2])) * ((s32) in[3]) + + ((limb) ((s32) in[1])) * ((s32) in[4]) + + ((limb) ((s32) in[0])) * ((s32) in[5])); + output[6] = 2 * (((limb) ((s32) in[3])) * ((s32) in[3]) + + ((limb) ((s32) in[2])) * ((s32) in[4]) + + ((limb) ((s32) in[0])) * ((s32) in[6]) + + 2 * ((limb) ((s32) in[1])) * ((s32) in[5])); + output[7] = 2 * (((limb) ((s32) in[3])) * ((s32) in[4]) + + ((limb) ((s32) in[2])) * ((s32) in[5]) + + ((limb) ((s32) in[1])) * ((s32) in[6]) + + ((limb) ((s32) in[0])) * ((s32) in[7])); + output[8] = ((limb) ((s32) in[4])) * ((s32) in[4]) + + 2 * (((limb) ((s32) in[2])) * ((s32) in[6]) + + ((limb) ((s32) in[0])) * ((s32) in[8]) + + 2 * (((limb) ((s32) in[1])) * ((s32) in[7]) + + ((limb) ((s32) in[3])) * ((s32) in[5]))); + output[9] = 2 * (((limb) ((s32) in[4])) * ((s32) in[5]) + + ((limb) ((s32) in[3])) * ((s32) in[6]) + + ((limb) ((s32) in[2])) * ((s32) in[7]) + + ((limb) ((s32) in[1])) * ((s32) in[8]) + + ((limb) ((s32) in[0])) * ((s32) in[9])); + output[10] = 2 * (((limb) ((s32) in[5])) * ((s32) in[5]) + + ((limb) ((s32) in[4])) * ((s32) in[6]) + + ((limb) ((s32) in[2])) * ((s32) in[8]) + + 2 * (((limb) ((s32) in[3])) * ((s32) in[7]) + + ((limb) ((s32) in[1])) * ((s32) in[9]))); + output[11] = 2 * (((limb) ((s32) in[5])) * ((s32) in[6]) + + ((limb) ((s32) in[4])) * ((s32) in[7]) + + ((limb) ((s32) in[3])) * ((s32) in[8]) + + ((limb) ((s32) in[2])) * ((s32) in[9])); + output[12] = ((limb) ((s32) in[6])) * ((s32) in[6]) + + 2 * (((limb) ((s32) in[4])) * ((s32) in[8]) + + 2 * (((limb) ((s32) in[5])) * ((s32) in[7]) + + ((limb) ((s32) in[3])) * ((s32) in[9]))); + output[13] = 2 * (((limb) ((s32) in[6])) * ((s32) in[7]) + + ((limb) ((s32) in[5])) * ((s32) in[8]) + + ((limb) ((s32) in[4])) * ((s32) in[9])); + output[14] = 2 * (((limb) ((s32) in[7])) * ((s32) in[7]) + + ((limb) ((s32) in[6])) * ((s32) in[8]) + + 2 * ((limb) ((s32) in[5])) * ((s32) in[9])); + output[15] = 2 * (((limb) ((s32) in[7])) * ((s32) in[8]) + + ((limb) ((s32) in[6])) * ((s32) in[9])); + output[16] = ((limb) ((s32) in[8])) * ((s32) in[8]) + + 4 * ((limb) ((s32) in[7])) * ((s32) in[9]); + output[17] = 2 * ((limb) ((s32) in[8])) * ((s32) in[9]); + output[18] = 2 * ((limb) ((s32) in[9])) * ((s32) in[9]); +} + +static void +fsquare(limb *output, const limb *in) { + limb t[19]; + fsquare_inner(t, in); + freduce_degree(t); + freduce_coefficients(t); + memcpy(output, t, sizeof(limb) * 10); +} + +/* Take a little-endian, 32-byte number and expand it into polynomial form */ +static void +fexpand(limb *output, const u8 *input) { +#define F(n,start,shift,mask) \ + output[n] = ((((limb) input[start + 0]) | \ + ((limb) input[start + 1]) << 8 | \ + ((limb) input[start + 2]) << 16 | \ + ((limb) input[start + 3]) << 24) >> shift) & mask; + F(0, 0, 0, 0x3ffffff); + F(1, 3, 2, 0x1ffffff); + F(2, 6, 3, 0x3ffffff); + F(3, 9, 5, 0x1ffffff); + F(4, 12, 6, 0x3ffffff); + F(5, 16, 0, 0x1ffffff); + F(6, 19, 1, 0x3ffffff); + F(7, 22, 3, 0x1ffffff); + F(8, 25, 4, 0x3ffffff); + F(9, 28, 6, 0x1ffffff); +#undef F +} + +#if (-32 >> 1) != -16 +#error "This code only works when >> does sign-extension on negative numbers" +#endif + +/* Take a fully reduced polynomial form number and contract it into a + * little-endian, 32-byte array + */ +static void +fcontract(u8 *output, limb *input) { + int i; + int j; + + for (j = 0; j < 2; ++j) { + for (i = 0; i < 9; ++i) { + if ((i & 1) == 1) { + /* This calculation is a time-invariant way to make input[i] positive + by borrowing from the next-larger limb. + */ + const s32 mask = (s32)(input[i]) >> 31; + const s32 carry = -(((s32)(input[i]) & mask) >> 25); + input[i] = (s32)(input[i]) + (carry << 25); + input[i+1] = (s32)(input[i+1]) - carry; + } else { + const s32 mask = (s32)(input[i]) >> 31; + const s32 carry = -(((s32)(input[i]) & mask) >> 26); + input[i] = (s32)(input[i]) + (carry << 26); + input[i+1] = (s32)(input[i+1]) - carry; + } + } + const s32 mask = (s32)(input[9]) >> 31; + const s32 carry = -(((s32)(input[9]) & mask) >> 25); + input[9] = (s32)(input[9]) + (carry << 25); + input[0] = (s32)(input[0]) - (carry * 19); + } + + /* The first borrow-propagation pass above ended with every limb + except (possibly) input[0] non-negative. + + Since each input limb except input[0] is decreased by at most 1 + by a borrow-propagation pass, the second borrow-propagation pass + could only have wrapped around to decrease input[0] again if the + first pass left input[0] negative *and* input[1] through input[9] + were all zero. In that case, input[1] is now 2^25 - 1, and this + last borrow-propagation step will leave input[1] non-negative. + */ + const s32 mask = (s32)(input[0]) >> 31; + const s32 carry = -(((s32)(input[0]) & mask) >> 26); + input[0] = (s32)(input[0]) + (carry << 26); + input[1] = (s32)(input[1]) - carry; + + /* Both passes through the above loop, plus the last 0-to-1 step, are + necessary: if input[9] is -1 and input[0] through input[8] are 0, + negative values will remain in the array until the end. + */ + + input[1] <<= 2; + input[2] <<= 3; + input[3] <<= 5; + input[4] <<= 6; + input[6] <<= 1; + input[7] <<= 3; + input[8] <<= 4; + input[9] <<= 6; +#define F(i, s) \ + output[s+0] |= input[i] & 0xff; \ + output[s+1] = (input[i] >> 8) & 0xff; \ + output[s+2] = (input[i] >> 16) & 0xff; \ + output[s+3] = (input[i] >> 24) & 0xff; + output[0] = 0; + output[16] = 0; + F(0,0); + F(1,3); + F(2,6); + F(3,9); + F(4,12); + F(5,16); + F(6,19); + F(7,22); + F(8,25); + F(9,28); +#undef F +} + +/* Input: Q, Q', Q-Q' + * Output: 2Q, Q+Q' + * + * x2 z3: long form + * x3 z3: long form + * x z: short form, destroyed + * xprime zprime: short form, destroyed + * qmqp: short form, preserved + */ +static void fmonty(limb *x2, limb *z2, /* output 2Q */ + limb *x3, limb *z3, /* output Q + Q' */ + limb *x, limb *z, /* input Q */ + limb *xprime, limb *zprime, /* input Q' */ + const limb *qmqp /* input Q - Q' */) { + limb origx[10], origxprime[10], zzz[19], xx[19], zz[19], xxprime[19], + zzprime[19], zzzprime[19], xxxprime[19]; + + memcpy(origx, x, 10 * sizeof(limb)); + fsum(x, z); + fdifference(z, origx); // does x - z + + memcpy(origxprime, xprime, sizeof(limb) * 10); + fsum(xprime, zprime); + fdifference(zprime, origxprime); + fproduct(xxprime, xprime, z); + fproduct(zzprime, x, zprime); + freduce_degree(xxprime); + freduce_coefficients(xxprime); + freduce_degree(zzprime); + freduce_coefficients(zzprime); + memcpy(origxprime, xxprime, sizeof(limb) * 10); + fsum(xxprime, zzprime); + fdifference(zzprime, origxprime); + fsquare(xxxprime, xxprime); + fsquare(zzzprime, zzprime); + fproduct(zzprime, zzzprime, qmqp); + freduce_degree(zzprime); + freduce_coefficients(zzprime); + memcpy(x3, xxxprime, sizeof(limb) * 10); + memcpy(z3, zzprime, sizeof(limb) * 10); + + fsquare(xx, x); + fsquare(zz, z); + fproduct(x2, xx, zz); + freduce_degree(x2); + freduce_coefficients(x2); + fdifference(zz, xx); // does zz = xx - zz + memset(zzz + 10, 0, sizeof(limb) * 9); + fscalar_product(zzz, zz, 121665); + /* No need to call freduce_degree here: + fscalar_product doesn't increase the degree of its input. */ + freduce_coefficients(zzz); + fsum(zzz, xx); + fproduct(z2, zz, zzz); + freduce_degree(z2); + freduce_coefficients(z2); +} + +/* Conditionally swap two reduced-form limb arrays if 'iswap' is 1, but leave + * them unchanged if 'iswap' is 0. Runs in data-invariant time to avoid + * side-channel attacks. + * + * NOTE that this function requires that 'iswap' be 1 or 0; other values give + * wrong results. Also, the two limb arrays must be in reduced-coefficient, + * reduced-degree form: the values in a[10..19] or b[10..19] aren't swapped, + * and all all values in a[0..9],b[0..9] must have magnitude less than + * INT32_MAX. + */ +static void +swap_conditional(limb a[19], limb b[19], limb iswap) { + unsigned i; + const s32 swap = -iswap; + + for (i = 0; i < 10; ++i) { + const s32 x = swap & ( ((s32)a[i]) ^ ((s32)b[i]) ); + a[i] = ((s32)a[i]) ^ x; + b[i] = ((s32)b[i]) ^ x; + } +} + +/* Calculates nQ where Q is the x-coordinate of a point on the curve + * + * resultx/resultz: the x coordinate of the resulting curve point (short form) + * n: a little endian, 32-byte number + * q: a point of the curve (short form) + */ +static void +cmult(limb *resultx, limb *resultz, const u8 *n, const limb *q) { + limb a[19] = {0}, b[19] = {1}, c[19] = {1}, d[19] = {0}; + limb *nqpqx = a, *nqpqz = b, *nqx = c, *nqz = d, *t; + limb e[19] = {0}, f[19] = {1}, g[19] = {0}, h[19] = {1}; + limb *nqpqx2 = e, *nqpqz2 = f, *nqx2 = g, *nqz2 = h; + + unsigned i, j; + + memcpy(nqpqx, q, sizeof(limb) * 10); + + for (i = 0; i < 32; ++i) { + u8 byte = n[31 - i]; + for (j = 0; j < 8; ++j) { + const limb bit = byte >> 7; + + swap_conditional(nqx, nqpqx, bit); + swap_conditional(nqz, nqpqz, bit); + fmonty(nqx2, nqz2, + nqpqx2, nqpqz2, + nqx, nqz, + nqpqx, nqpqz, + q); + swap_conditional(nqx2, nqpqx2, bit); + swap_conditional(nqz2, nqpqz2, bit); + + t = nqx; + nqx = nqx2; + nqx2 = t; + t = nqz; + nqz = nqz2; + nqz2 = t; + t = nqpqx; + nqpqx = nqpqx2; + nqpqx2 = t; + t = nqpqz; + nqpqz = nqpqz2; + nqpqz2 = t; + + byte <<= 1; + } + } + + memcpy(resultx, nqx, sizeof(limb) * 10); + memcpy(resultz, nqz, sizeof(limb) * 10); +} + +// ----------------------------------------------------------------------------- +// Shamelessly copied from djb's code +// ----------------------------------------------------------------------------- +static void +crecip(limb *out, const limb *z) { + limb z2[10]; + limb z9[10]; + limb z11[10]; + limb z2_5_0[10]; + limb z2_10_0[10]; + limb z2_20_0[10]; + limb z2_50_0[10]; + limb z2_100_0[10]; + limb t0[10]; + limb t1[10]; + int i; + + /* 2 */ fsquare(z2,z); + /* 4 */ fsquare(t1,z2); + /* 8 */ fsquare(t0,t1); + /* 9 */ fmul(z9,t0,z); + /* 11 */ fmul(z11,z9,z2); + /* 22 */ fsquare(t0,z11); + /* 2^5 - 2^0 = 31 */ fmul(z2_5_0,t0,z9); + + /* 2^6 - 2^1 */ fsquare(t0,z2_5_0); + /* 2^7 - 2^2 */ fsquare(t1,t0); + /* 2^8 - 2^3 */ fsquare(t0,t1); + /* 2^9 - 2^4 */ fsquare(t1,t0); + /* 2^10 - 2^5 */ fsquare(t0,t1); + /* 2^10 - 2^0 */ fmul(z2_10_0,t0,z2_5_0); + + /* 2^11 - 2^1 */ fsquare(t0,z2_10_0); + /* 2^12 - 2^2 */ fsquare(t1,t0); + /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } + /* 2^20 - 2^0 */ fmul(z2_20_0,t1,z2_10_0); + + /* 2^21 - 2^1 */ fsquare(t0,z2_20_0); + /* 2^22 - 2^2 */ fsquare(t1,t0); + /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } + /* 2^40 - 2^0 */ fmul(t0,t1,z2_20_0); + + /* 2^41 - 2^1 */ fsquare(t1,t0); + /* 2^42 - 2^2 */ fsquare(t0,t1); + /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t1,t0); fsquare(t0,t1); } + /* 2^50 - 2^0 */ fmul(z2_50_0,t0,z2_10_0); + + /* 2^51 - 2^1 */ fsquare(t0,z2_50_0); + /* 2^52 - 2^2 */ fsquare(t1,t0); + /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } + /* 2^100 - 2^0 */ fmul(z2_100_0,t1,z2_50_0); + + /* 2^101 - 2^1 */ fsquare(t1,z2_100_0); + /* 2^102 - 2^2 */ fsquare(t0,t1); + /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fsquare(t1,t0); fsquare(t0,t1); } + /* 2^200 - 2^0 */ fmul(t1,t0,z2_100_0); + + /* 2^201 - 2^1 */ fsquare(t0,t1); + /* 2^202 - 2^2 */ fsquare(t1,t0); + /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } + /* 2^250 - 2^0 */ fmul(t0,t1,z2_50_0); + + /* 2^251 - 2^1 */ fsquare(t1,t0); + /* 2^252 - 2^2 */ fsquare(t0,t1); + /* 2^253 - 2^3 */ fsquare(t1,t0); + /* 2^254 - 2^4 */ fsquare(t0,t1); + /* 2^255 - 2^5 */ fsquare(t1,t0); + /* 2^255 - 21 */ fmul(out,t1,z11); +} + +int +curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) { + limb bp[10], x[10], z[11], zmone[10]; + uint8_t e[32]; + int i; + + for (i = 0; i < 32; ++i) e[i] = secret[i]; + e[0] &= 248; + e[31] &= 127; + e[31] |= 64; + + fexpand(bp, basepoint); + cmult(x, z, e, bp); + crecip(zmone, z); + fmul(z, x, zmone); + freduce_coefficients(z); + fcontract(mypublic, z); + return 0; +}

1 0

[tor/master] Add a wrapper around, and test and build support for, curve25519.
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit 89ec584805bfba76609a1191eb6789fc0e24bdae Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Dec 3 15:44:21 2012 -0500 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. --- configure.ac | 99 ++++++++++++++++++++++++++++++++++++++++ src/common/crypto_curve25519.c | 88 +++++++++++++++++++++++++++++++++++ src/common/crypto_curve25519.h | 43 +++++++++++++++++ src/common/include.am | 20 ++++++++- src/test/test_crypto.c | 82 +++++++++++++++++++++++++++++++++ 5 files changed, 331 insertions(+), 1 deletions(-) diff --git a/configure.ac b/configure.ac index 9963a97..9272834 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 0000000..1985e8a --- /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 extra_strong + * 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 skey and pkey, + * writing CURVE25519_OUTPUT_LEN bytes of output into output. */ +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 0000000..3e093be --- /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 0fdc720..f986ba6 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 28e2937..8aadd97 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 };

1 0