commit c46ff3ec79420a6d94207cbe0d4e4d08208ccc4c
Author: Nick Mathewson <nickm(a)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;
+ }
+}
+
