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.

5 files changed, 587 insertions, 16 deletions

diff --git a/src/or/onion_ntor.c b/src/or/onion_ntor.c
index 3f4faf3fa..8eab55acf 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 a5cceb94d..61ff5c0ad 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 e4f2897cd..f625ab7f7 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 000000000..6133be139
--- /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 000000000..6e6bd2139
--- /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;
+  }
+}
+