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

[tor/master] Complete all DOCDOC entries from the ntor branch
by nickm＠torproject.org 03 Jan '13

03 Jan '13

commit 94cb7bd24d2ffda9038c267b3ee0837dd64ec903 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Dec 25 22:38:20 2012 -0500 Complete all DOCDOC entries from the ntor branch --- src/or/circuitbuild.c | 8 ++++---- src/or/cpuworker.c | 21 ++++++++++++++++++--- src/or/onion.c | 5 ++--- src/or/onion_fast.c | 5 +++-- src/or/router.c | 36 ++++++++++++++++++------------------ 5 files changed, 45 insertions(+), 30 deletions(-) diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 9300b04..552167f 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -490,10 +490,10 @@ circuit_n_chan_done(channel_t *chan, int status) /** Find a new circid that isn't currently in use on the circ->n_chan * for the outgoing - * circuit circ, and deliver a cell of type cell_type - * (either CELL_CREATE or CELL_CREATE_FAST) with payload payload - * to this circuit. DOCDOC new arguments - * Return -1 if we failed to find a suitable circid, else return 0. + * circuit circ, and deliver the cell create_cell to this + * circuit. If relayed is true, this is a create cell somebody + * gave us via an EXTEND cell, so we shouldn't worry if we don't understand + * it. Return -1 if we failed to find a suitable circid, else return 0. */ static int circuit_deliver_create_cell(circuit_t *circ, const create_cell_t *create_cell, diff --git a/src/or/cpuworker.c b/src/or/cpuworker.c index 1ac8cd5..3f8fc94 100644 --- a/src/or/cpuworker.c +++ b/src/or/cpuworker.c @@ -84,29 +84,44 @@ tag_unpack(const uint8_t *tag, uint64_t *chan_id, circid_t *circ_id) *circ_id = get_uint16(tag+8); } -/** DOCDOC */ +/** Magic numbers to make sure our cpuworker_requests don't grow any + * mis-framing bugs. */ #define CPUWORKER_REQUEST_MAGIC 0xda4afeed #define CPUWORKER_REPLY_MAGIC 0x5eedf00d -/**DOCDOC*/ +/** A request sent to a cpuworker. */ typedef struct cpuworker_request_t { + /** Magic number; must be CPUWORKER_REQUEST_MAGIC. */ uint32_t magic; /** Opaque tag to identify the job */ uint8_t tag[TAG_LEN]; + /** Task code. Must be one of CPUWORKER_TASK_* */ uint8_t task; + /** A create cell for the cpuworker to process. */ create_cell_t create_cell; + /* Turn the above into a tagged union if needed. */ } cpuworker_request_t; -/**DOCDOC*/ +/** A reply sent by a cpuworker. */ typedef struct cpuworker_reply_t { + /** Magic number; must be CPUWORKER_REPLY_MAGIC. */ uint32_t magic; + /** Opaque tag to identify the job; matches the request's tag.*/ uint8_t tag[TAG_LEN]; + /** True iff we got a successful request. */ uint8_t success; + /** Output of processing a create cell + * + * @{ + */ + /** The created cell to send back. */ created_cell_t created_cell; + /** The keys to use on this circuit. */ uint8_t keys[CPATH_KEY_MATERIAL_LEN]; + /** Input to use for authenticating introduce1 cells. */ uint8_t rend_auth_material[DIGEST_LEN]; } cpuworker_reply_t; diff --git a/src/or/onion.c b/src/or/onion.c index 56bc9a3..fc3e621 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -304,9 +304,8 @@ onion_skin_create(int type, * type type, responding to the client request in onion_skin * using the keys in keys. On success, write our response into * reply_out, generate keys_out_len bytes worth of key material - * in keys_out_len, and return the length of the reply. On failure, - * return -1. - * DOCDOC rend_nonce_out + * in keys_out_len, a hidden service nonce to rend_nonce_out, + * and return the length of the reply. On failure, return -1. */ int onion_skin_server_handshake(int type, diff --git a/src/or/onion_fast.c b/src/or/onion_fast.c index f33b048..eb9eceb 100644 --- a/src/or/onion_fast.c +++ b/src/or/onion_fast.c @@ -12,7 +12,7 @@ #include "or.h" #include "onion_fast.h" -/**DOCDOC*/ +/** Release all state held in victim. */ void fast_handshake_state_free(fast_handshake_state_t *victim) { @@ -22,7 +22,8 @@ fast_handshake_state_free(fast_handshake_state_t *victim) tor_free(victim); } -/** DOCDOC */ +/** Create the state needed to perform a CREATE_FAST hasnshake. Return 0 + * on success, -1 on failure. */ int fast_onionskin_create(fast_handshake_state_t **handshake_state_out, uint8_t *handshake_out) diff --git a/src/or/router.c b/src/or/router.c index a97db85..961fd48 100644 --- a/src/or/router.c +++ b/src/or/router.c @@ -56,8 +56,10 @@ static crypto_pk_t *onionkey=NULL; * generated by clients that have an older version of our descriptor. */ static crypto_pk_t *lastonionkey=NULL; #ifdef CURVE25519_ENABLED -/**DOCDOC*/ +/** Current private ntor secret key: used to perform the ntor handshake. */ static curve25519_keypair_t curve25519_onion_key; +/** Previous private ntor secret key: used to perform the ntor handshake + * with clients that have an older version of our descriptor. */ static curve25519_keypair_t last_curve25519_onion_key; #endif /** Private server "identity key": used to sign directory info and TLS @@ -105,20 +107,6 @@ set_onion_key(crypto_pk_t *k) mark_my_descriptor_dirty("set onion key"); } -#if 0 -/**DOCDOC*/ -static void -set_curve25519_onion_key(const curve25519_keypair_t *kp) -{ - if (tor_memeq(&curve25519_onion_key, kp, sizeof(curve25519_keypair_t))) - return; - - tor_mutex_acquire(key_lock); - memcpy(&curve25519_onion_key, kp, sizeof(curve25519_keypair_t)); - tor_mutex_release(key_lock); -} -#endif - /** Return the current onion key. Requires that the onion key has been * loaded or generated. */ crypto_pk_t * @@ -147,12 +135,15 @@ dup_onion_keys(crypto_pk_t **key, crypto_pk_t **last) } #ifdef CURVE25519_ENABLED -/**DOCDOC only in main thread*/ +/** Return the current secret onion key for the ntor handshake. Must only + * be called from the main thread. */ static const curve25519_keypair_t * get_current_curve25519_keypair(void) { return &curve25519_onion_key; } +/** Return a map from KEYID (the key itself) to keypairs for use in the ntor + * handshake. Must only be called from the main thread. */ di_digest256_map_t * construct_ntor_key_map(void) { @@ -173,6 +164,8 @@ construct_ntor_key_map(void) return m; } +/** Helper used to deallocate a di_digest256_map_t returned by + * construct_ntor_key_map. */ static void ntor_key_map_free_helper(void *arg) { @@ -180,9 +173,12 @@ ntor_key_map_free_helper(void *arg) memwipe(k, 0, sizeof(*k)); tor_free(k); } +/** Release all storage from a keymap returned by construct_ntor_key_map. */ void ntor_key_map_free(di_digest256_map_t *map) { + if (!map) + return; dimap_free(map, ntor_key_map_free_helper); } #endif @@ -453,7 +449,11 @@ init_key_from_file(const char *fname, int generate, int severity) } #ifdef CURVE25519_ENABLED -/** DOCDOC */ +/** Load a curve25519 keypair from the file fname, writing it into + * keys_out. If the file isn't found and generate is true, + * create a new keypair and write it into the file. If there are errors, log + * them at level severity. Generate files using tag in their + * ASCII wrapper. */ static int init_curve25519_keypair_from_file(curve25519_keypair_t *keys_out, const char *fname, @@ -1599,7 +1599,7 @@ router_digest_is_me(const char *digest) tor_memeq(server_identitykey_digest, digest, DIGEST_LEN)); } -/** DOCDOC */ +/** Return my identity digest. */ const uint8_t * router_get_my_id_digest(void) {

1 0

[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