commit c46ff3ec79420a6d94207cbe0d4e4d08208ccc4c Author: Nick Mathewson nickm@torproject.org Date: Sat Dec 8 00:52:44 2012 -0500

Add reference implementation for ntor, plus compatibility test

Before I started coding ntor in C, I did another one in Python. Turns out, they interoperate just fine. --- src/or/onion_ntor.c | 18 +-- src/or/onion_ntor.h | 19 +++ src/test/include.am | 13 ++ src/test/ntor_ref.py | 387 +++++++++++++++++++++++++++++++++++++++++++++++ src/test/test_ntor_cl.c | 166 ++++++++++++++++++++ 5 files changed, 587 insertions(+), 16 deletions(-)

diff --git a/src/or/onion_ntor.c b/src/or/onion_ntor.c index 3f4faf3..8eab55a 100644 --- a/src/or/onion_ntor.c +++ b/src/or/onion_ntor.c @@ -3,26 +3,12 @@

#include "orconfig.h"

-#include "onion_ntor.h" #include "crypto.h" +#define ONION_NTOR_PRIVATE +#include "onion_ntor.h" #include "torlog.h" #include "util.h"

-/** Storage held by a client while waiting for an ntor reply from a server. */ -struct ntor_handshake_state_t { - /** Identity digest of the router we're talking to. */ - uint8_t router_id[DIGEST_LEN]; - /** Onion key of the router we're talking to. */ - curve25519_public_key_t pubkey_B; - - /** - * Short-lived keypair for use with this handshake. - * @{ */ - curve25519_secret_key_t seckey_x; - curve25519_public_key_t pubkey_X; - /** @} */ -}; - /** Free storage held in an ntor handshake state. */ void ntor_handshake_state_free(ntor_handshake_state_t *state) diff --git a/src/or/onion_ntor.h b/src/or/onion_ntor.h index a5cceb9..61ff5c0 100644 --- a/src/or/onion_ntor.h +++ b/src/or/onion_ntor.h @@ -38,6 +38,25 @@ int onion_skin_ntor_client_handshake( const uint8_t *handshake_reply, uint8_t *key_out, size_t key_out_len); + +#ifdef ONION_NTOR_PRIVATE + +/** Storage held by a client while waiting for an ntor reply from a server. */ +struct ntor_handshake_state_t { + /** Identity digest of the router we're talking to. */ + uint8_t router_id[DIGEST_LEN]; + /** Onion key of the router we're talking to. */ + curve25519_public_key_t pubkey_B; + + /** + * Short-lived keypair for use with this handshake. + * @{ */ + curve25519_secret_key_t seckey_x; + curve25519_public_key_t pubkey_X; + /** @} */ +}; +#endif + #endif

#endif diff --git a/src/test/include.am b/src/test/include.am index e4f2897..f625ab7 100644 --- a/src/test/include.am +++ b/src/test/include.am @@ -53,3 +53,16 @@ src_test_bench_LDADD = src/or/libtor.a src/common/libor.a \ noinst_HEADERS+= \ src/test/test.h

+if CURVE25519_ENABLED +noinst_PROGRAMS+= src/test/test-ntor-cl +src_test_test_ntor_cl_SOURCES = src/test/test_ntor_cl.c +src_test_test_ntor_cl_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ +src_test_test_ntor_cl_LDADD = src/or/libtor.a src/common/libor.a \ + src/common/libor-crypto.a $(LIBDONNA) \ + @TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ \ + @TOR_OPENSSL_LIBS@ @TOR_LIB_WS32@ @TOR_LIB_GDI@ +src_test_test_ntor_cl_AM_CPPFLAGS = \ + -I"$(top_srcdir)/src/or" + +endif + diff --git a/src/test/ntor_ref.py b/src/test/ntor_ref.py new file mode 100644 index 0000000..6133be1 --- /dev/null +++ b/src/test/ntor_ref.py @@ -0,0 +1,387 @@ +# Copyright 2012 The Tor Project, Inc +# See LICENSE for licensing information + +""" +ntor_ref.py + + +This module is a reference implementation for the "ntor" protocol +s proposed by Goldberg, Stebila, and Ustaoglu and as instantiated in +Tor Proposal 216. + +It's meant to be used to validate Tor's ntor implementation. It +requirs the curve25519 python module from the curve25519-donna +package. + + *** DO NOT USE THIS IN PRODUCTION. *** + +commands: + + gen_kdf_vectors: Print out some test vectors for the RFC5869 KDF. + timing: Print a little timing information about this implementation's + handshake. + self-test: Try handshaking with ourself; make sure we can. + test-tor: Handshake with tor's ntor implementation via the program + src/test/test-ntor-cl; make sure we can. + +""" + +import binascii +import curve25519 +import hashlib +import hmac +import subprocess + +# ********************************************************************** +# Helpers and constants + +def HMAC(key,msg): + "Return the HMAC-SHA256 of 'msg' using the key 'key'." + H = hmac.new(key, "", hashlib.sha256) + H.update(msg) + return H.digest() + +def H(msg,tweak): + """Return the hash of 'msg' using tweak 'tweak'. (In this version of ntor, + the tweaked hash is just HMAC with the tweak as the key.)""" + return HMAC(key=tweak, + msg=msg) + +def keyid(k): + """Return the 32-byte key ID of a public key 'k'. (Since we're + using curve25519, we let k be its own keyid.) + """ + return k.serialize() + +NODE_ID_LENGTH = 20 +KEYID_LENGTH = 32 +G_LENGTH = 32 +H_LENGTH = 32 + +PROTOID = b"ntor-curve25519-sha256-1" +M_EXPAND = PROTOID + ":key_expand" +T_MAC = PROTOID + ":mac" +T_KEY = PROTOID + ":key_extract" +T_VERIFY = PROTOID + ":verify" + +def H_mac(msg): return H(msg, tweak=T_MAC) +def H_verify(msg): return H(msg, tweak=T_VERIFY) + +class PrivateKey(curve25519.keys.Private): + """As curve25519.keys.Private, but doesn't regenerate its public key + every time you ask for it. + """ + def __init__(self): + curve25519.keys.Private.__init__(self) + self._memo_public = None + + def get_public(self): + if self._memo_public is None: + self._memo_public = curve25519.keys.Private.get_public(self) + + return self._memo_public + +# ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + +def kdf_rfc5869(key, salt, info, n): + + prk = HMAC(key=salt, msg=key) + + out = b"" + last = b"" + i = 1 + while len(out) < n: + m = last + info + chr(i) + last = h = HMAC(key=prk, msg=m) + out += h + i = i + 1 + return out[:n] + +def kdf_ntor(key, n): + return kdf_rfc5869(key, T_KEY, M_EXPAND, n) + +# ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + +def client_part1(node_id, pubkey_B): + """Initial handshake, client side. + + From the specification: + + <<To send a create cell, the client generates a keypair x,X = + KEYGEN(), and sends a CREATE cell with contents: + + NODEID: ID -- ID_LENGTH bytes + KEYID: KEYID(B) -- H_LENGTH bytes + CLIENT_PK: X -- G_LENGTH bytes + >> + + Takes node_id -- a digest of the server's identity key, + pubkey_B -- a public key for the server. + Returns a tuple of (client secret key x, client->server message)""" + + assert len(node_id) == NODE_ID_LENGTH + + key_id = keyid(pubkey_B) + seckey_x = PrivateKey() + pubkey_X = seckey_x.get_public().serialize() + + message = node_id + key_id + pubkey_X + + assert len(message) == NODE_ID_LENGTH + H_LENGTH + H_LENGTH + return seckey_x , message + +def hash_nil(x): + """Identity function: if we don't pass a hash function that does nothing, + the curve25519 python lib will try to sha256 it for us.""" + return x + +def bad_result(r): + """Helper: given a result of multiplying a public key by a private key, + return True iff one of the inputs was broken""" + assert len(r) == 32 + return r == '\x00'*32 + +def server(seckey_b, my_node_id, message, keyBytes=72): + """Handshake step 2, server side. + + From the spec: + + << + The server generates a keypair of y,Y = KEYGEN(), and computes + + secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID + KEY_SEED = H(secret_input, t_key) + verify = H(secret_input, t_verify) + auth_input = verify | ID | B | Y | X | PROTOID | "Server" + + The server sends a CREATED cell containing: + + SERVER_PK: Y -- G_LENGTH bytes + AUTH: H(auth_input, t_mac) -- H_LENGTH byets + >> + + Takes seckey_b -- the server's secret key + my_node_id -- the servers's public key digest, + message -- a message from a client + keybytes -- amount of key material to generate + + Returns a tuple of (key material, sever->client reply), or None on + error. + """ + + assert len(message) == NODE_ID_LENGTH + H_LENGTH + H_LENGTH + + if my_node_id != message[:NODE_ID_LENGTH]: + return None + + badness = (keyid(seckey_b.get_public()) != + message[NODE_ID_LENGTH:NODE_ID_LENGTH+H_LENGTH]) + + pubkey_X = curve25519.keys.Public(message[NODE_ID_LENGTH+H_LENGTH:]) + seckey_y = PrivateKey() + pubkey_Y = seckey_y.get_public() + pubkey_B = seckey_b.get_public() + xy = seckey_y.get_shared_key(pubkey_X, hash_nil) + xb = seckey_b.get_shared_key(pubkey_X, hash_nil) + + # secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID + secret_input = (xy + xb + my_node_id + + pubkey_B.serialize() + + pubkey_X.serialize() + + pubkey_Y.serialize() + + PROTOID) + + verify = H_verify(secret_input) + + # auth_input = verify | ID | B | Y | X | PROTOID | "Server" + auth_input = (verify + + my_node_id + + pubkey_B.serialize() + + pubkey_Y.serialize() + + pubkey_X.serialize() + + PROTOID + + "Server") + + msg = pubkey_Y.serialize() + H_mac(auth_input) + + badness += bad_result(xb) + badness += bad_result(xy) + + if badness: + return None + + keys = kdf_ntor(secret_input, keyBytes) + + return keys, msg + +def client_part2(seckey_x, msg, node_id, pubkey_B, keyBytes=72): + """Handshake step 3: client side again. + + From the spec: + + << + The client then checks Y is in G^* [see NOTE below], and computes + + secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID + KEY_SEED = H(secret_input, t_key) + verify = H(secret_input, t_verify) + auth_input = verify | ID | B | Y | X | PROTOID | "Server" + + The client verifies that AUTH == H(auth_input, t_mac). + >> + + Takes seckey_x -- the secret key we generated in step 1. + msg -- the message from the server. + node_id -- the node_id we used in step 1. + server_key -- the same public key we used in step 1. + keyBytes -- the number of bytes we want to generate + Returns key material, or None on error + + """ + assert len(msg) == G_LENGTH + H_LENGTH + + pubkey_Y = curve25519.keys.Public(msg[:G_LENGTH]) + their_auth = msg[G_LENGTH:] + + pubkey_X = seckey_x.get_public() + + yx = seckey_x.get_shared_key(pubkey_Y, hash_nil) + bx = seckey_x.get_shared_key(pubkey_B, hash_nil) + + + # secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID + secret_input = (yx + bx + node_id + + pubkey_B.serialize() + + pubkey_X.serialize() + + pubkey_Y.serialize() + PROTOID) + + verify = H_verify(secret_input) + + # auth_input = verify | ID | B | Y | X | PROTOID | "Server" + auth_input = (verify + node_id + + pubkey_B.serialize() + + pubkey_Y.serialize() + + pubkey_X.serialize() + PROTOID + + "Server") + + my_auth = H_mac(auth_input) + + badness = my_auth != their_auth + badness = bad_result(yx) + bad_result(bx) + + if badness: + return None + + return kdf_ntor(secret_input, keyBytes) + +# ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + +def demo(node_id="iToldYouAboutStairs.", server_key=PrivateKey()): + """ + Try to handshake with ourself. + """ + x, create = client_part1(node_id, server_key.get_public()) + skeys, created = server(server_key, node_id, create) + ckeys = client_part2(x, created, node_id, server_key.get_public()) + assert len(skeys) == 72 + assert len(ckeys) == 72 + assert skeys == ckeys + +# ====================================================================== +def timing(): + """ + Use Python's timeit module to see how fast this nonsense is + """ + import timeit + t = timeit.Timer(stmt="ntor_ref.demo(N,SK)", + setup="import ntor_ref,curve25519;N='ABCD'*5;SK=ntor_ref.PrivateKey()") + print t.timeit(number=1000) + +# ====================================================================== + +def kdf_vectors(): + """ + Generate some vectors to check our KDF. + """ + import binascii + def kdf_vec(inp): + k = kdf(inp, T_KEY, M_EXPAND, 100) + print repr(inp), "\n""+ binascii.b2a_hex(k)+ """ + kdf_vec("") + kdf_vec("Tor") + kdf_vec("AN ALARMING ITEM TO FIND ON YOUR CREDIT-RATING STATEMENT") + +# ====================================================================== + + +def test_tor(): + """ + Call the test-ntor-cl command-line program to make sure we can + interoperate with Tor's ntor program + """ + enhex=binascii.b2a_hex + dehex=lambda s: binascii.a2b_hex(s.strip()) + + PROG = "./src/test/test-ntor-cl" + def tor_client1(node_id, pubkey_B): + " returns (msg, state) " + p = subprocess.Popen([PROG, "client1", enhex(node_id), + enhex(pubkey_B.serialize())], + stdout=subprocess.PIPE) + return map(dehex, p.stdout.readlines()) + def tor_server1(seckey_b, node_id, msg, n): + " returns (msg, keys) " + p = subprocess.Popen([PROG, "server1", enhex(seckey_b.serialize()), + enhex(node_id), enhex(msg), str(n)], + stdout=subprocess.PIPE) + return map(dehex, p.stdout.readlines()) + def tor_client2(state, msg, n): + " returns (keys,) " + p = subprocess.Popen([PROG, "client2", enhex(state), + enhex(msg), str(n)], + stdout=subprocess.PIPE) + return map(dehex, p.stdout.readlines()) + + + node_id = "thisisatornodeid$#%^" + seckey_b = PrivateKey() + pubkey_B = seckey_b.get_public() + + # Do a pure-Tor handshake + c2s_msg, c_state = tor_client1(node_id, pubkey_B) + s2c_msg, s_keys = tor_server1(seckey_b, node_id, c2s_msg, 90) + c_keys, = tor_client2(c_state, s2c_msg, 90) + assert c_keys == s_keys + assert len(c_keys) == 90 + + # Try a mixed handshake with Tor as the client + c2s_msg, c_state = tor_client1(node_id, pubkey_B) + s_keys, s2c_msg = server(seckey_b, node_id, c2s_msg, 90) + c_keys, = tor_client2(c_state, s2c_msg, 90) + assert c_keys == s_keys + assert len(c_keys) == 90 + + # Now do a mixed handshake with Tor as the server + c_x, c2s_msg = client_part1(node_id, pubkey_B) + s2c_msg, s_keys = tor_server1(seckey_b, node_id, c2s_msg, 90) + c_keys = client_part2(c_x, s2c_msg, node_id, pubkey_B, 90) + assert c_keys == s_keys + assert len(c_keys) == 90 + + print "We just interoperated." + +# ====================================================================== + +if __name__ == '__main__': + import sys + if sys.argv[1] == 'gen_kdf_vectors': + kdf_vectors() + elif sys.argv[1] == 'timing': + timing() + elif sys.argv[1] == 'self-test': + demo() + elif sys.argv[1] == 'test-tor': + test_tor() + + else: + print __doc__ diff --git a/src/test/test_ntor_cl.c b/src/test/test_ntor_cl.c new file mode 100644 index 0000000..6e6bd21 --- /dev/null +++ b/src/test/test_ntor_cl.c @@ -0,0 +1,166 @@ +/* Copyright (c) 2012, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +#include "orconfig.h" +#include <stdio.h> +#include <stdlib.h> + +#define ONION_NTOR_PRIVATE +#include "or.h" +#include "util.h" +#include "compat.h" +#include "crypto.h" +#include "crypto_curve25519.h" +#include "onion_ntor.h" + +#ifndef CURVE25519_ENABLED +#error "This isn't going to work without curve25519." +#endif + +#define N_ARGS(n) STMT_BEGIN { \ + if (argc < (n)) { \ + fprintf(stderr, "%s needs %d arguments.\n",argv[1],n); \ + return 1; \ + } \ + } STMT_END +#define BASE16(idx, var, n) STMT_BEGIN { \ + const char *s = argv[(idx)]; \ + if (base16_decode((char*)var, n, s, strlen(s)) < 0 ) { \ + fprintf(stderr, "couldn't decode argument %d (%s)\n",idx,s); \ + return 1; \ + } \ + } STMT_END +#define INT(idx, var) STMT_BEGIN { \ + var = atoi(argv[(idx)]); \ + if (var <= 0) { \ + fprintf(stderr, "bad integer argument %d (%s)\n",idx,argv[(idx)]); \ + } \ + } STMT_END + +static int +client1(int argc, char **argv) +{ + /* client1 nodeID B -> msg state */ + curve25519_public_key_t B; + uint8_t node_id[DIGEST_LEN]; + ntor_handshake_state_t *state; + uint8_t msg[NTOR_ONIONSKIN_LEN]; + + char buf[1024]; + + memset(&state, 0, sizeof(state)); + + N_ARGS(4); + BASE16(2, node_id, DIGEST_LEN); + BASE16(3, B.public_key, CURVE25519_PUBKEY_LEN); + + if (onion_skin_ntor_create(node_id, &B, &state, msg)<0) { + fprintf(stderr, "handshake failed"); + return 2; + } + + base16_encode(buf, sizeof(buf), (const char*)msg, sizeof(msg)); + printf("%s\n", buf); + base16_encode(buf, sizeof(buf), (void*)state, sizeof(*state)); + printf("%s\n", buf); + ntor_handshake_state_free(state); + return 0; +} + +static int +server1(int argc, char **argv) +{ + uint8_t msg_in[NTOR_ONIONSKIN_LEN]; + curve25519_keypair_t kp; + di_digest256_map_t *keymap=NULL; + uint8_t node_id[DIGEST_LEN]; + int keybytes; + + uint8_t msg_out[NTOR_REPLY_LEN]; + uint8_t *keys; + char *hexkeys; + + char buf[256]; + + /* server1: b nodeID msg N -> msg keys */ + N_ARGS(6); + BASE16(2, kp.seckey.secret_key, CURVE25519_SECKEY_LEN); + BASE16(3, node_id, DIGEST_LEN); + BASE16(4, msg_in, NTOR_ONIONSKIN_LEN); + INT(5, keybytes); + + curve25519_public_key_generate(&kp.pubkey, &kp.seckey); + dimap_add_entry(&keymap, kp.pubkey.public_key, &kp); + + keys = tor_malloc(keybytes); + hexkeys = tor_malloc(keybytes*2+1); + if (onion_skin_ntor_server_handshake( + msg_in, keymap, NULL, node_id, msg_out, keys, + (size_t)keybytes)<0) { + fprintf(stderr, "handshake failed"); + return 2; + } + + base16_encode(buf, sizeof(buf), (const char*)msg_out, sizeof(msg_out)); + printf("%s\n", buf); + base16_encode(hexkeys, keybytes*2+1, (const char*)keys, keybytes); + printf("%s\n", hexkeys); + + tor_free(keys); + tor_free(hexkeys); + return 0; +} + +static int +client2(int argc, char **argv) +{ + struct ntor_handshake_state_t state; + uint8_t msg[NTOR_REPLY_LEN]; + int keybytes; + uint8_t *keys; + char *hexkeys; + + N_ARGS(5); + BASE16(2, (&state), sizeof(state)); + BASE16(3, msg, sizeof(msg)); + INT(4, keybytes); + + keys = tor_malloc(keybytes); + hexkeys = tor_malloc(keybytes*2+1); + if (onion_skin_ntor_client_handshake(&state, msg, keys, keybytes)<0) { + fprintf(stderr, "handshake failed"); + return 2; + } + + base16_encode(hexkeys, keybytes*2+1, (const char*)keys, keybytes); + printf("%s\n", hexkeys); + + tor_free(keys); + tor_free(hexkeys); + + return 0; +} + +int +main(int argc, char **argv) +{ + /* + client1: nodeID B -> msg state + server1: b nodeID msg N -> msg keys + client2: state msg N -> keys + */ + if (argc < 2) { + fprintf(stderr, "I need arguments. Read source for more info.\n"); + return 1; + } else if (!strcmp(argv[1], "client1")) { + return client1(argc, argv); + } else if (!strcmp(argv[1], "server1")) { + return server1(argc, argv); + } else if (!strcmp(argv[1], "client2")) { + return client2(argc, argv); + } else { + fprintf(stderr, "What's a %s?\n", argv[1]); + return 1; + } +} +