src/test/ntor_ref.py

   1 # Copyright 2012-2013, The Tor Project, Inc
   2 # See LICENSE for licensing information
   3
   4 """
   5 ntor_ref.py
   6
   7
   8 This module is a reference implementation for the "ntor" protocol
   9 s proposed by Goldberg, Stebila, and Ustaoglu and as instantiated in
  10 Tor Proposal 216.
  11
  12 It's meant to be used to validate Tor's ntor implementation.  It
  13 requirs the curve25519 python module from the curve25519-donna
  14 package.
  15
  16                 *** DO NOT USE THIS IN PRODUCTION. ***
  17
  18 commands:
  19
  20    gen_kdf_vectors: Print out some test vectors for the RFC5869 KDF.
  21    timing: Print a little timing information about this implementation's
  22       handshake.
  23    self-test: Try handshaking with ourself; make sure we can.
  24    test-tor: Handshake with tor's ntor implementation via the program
  25       src/test/test-ntor-cl; make sure we can.
  26
  27 """
  28
  29 import binascii
  30 import curve25519
  31 import hashlib
  32 import hmac
  33 import subprocess
  34
  35 # **********************************************************************
  36 # Helpers and constants
  37
  38 def HMAC(key,msg):
  39     "Return the HMAC-SHA256 of 'msg' using the key 'key'."
  40     H = hmac.new(key, "", hashlib.sha256)
  41     H.update(msg)
  42     return H.digest()
  43
  44 def H(msg,tweak):
  45     """Return the hash of 'msg' using tweak 'tweak'.  (In this version of ntor,
  46        the tweaked hash is just HMAC with the tweak as the key.)"""
  47     return HMAC(key=tweak,
  48                 msg=msg)
  49
  50 def keyid(k):
  51     """Return the 32-byte key ID of a public key 'k'. (Since we're
  52        using curve25519, we let k be its own keyid.)
  53     """
  54     return k.serialize()
  55
  56 NODE_ID_LENGTH = 20
  57 KEYID_LENGTH = 32
  58 G_LENGTH = 32
  59 H_LENGTH = 32
  60
  61 PROTOID = b"ntor-curve25519-sha256-1"
  62 M_EXPAND = PROTOID + ":key_expand"
  63 T_MAC    = PROTOID + ":mac"
  64 T_KEY    = PROTOID + ":key_extract"
  65 T_VERIFY = PROTOID + ":verify"
  66
  67 def H_mac(msg): return H(msg, tweak=T_MAC)
  68 def H_verify(msg): return H(msg, tweak=T_VERIFY)
  69
  70 class PrivateKey(curve25519.keys.Private):
  71     """As curve25519.keys.Private, but doesn't regenerate its public key
  72        every time you ask for it.
  73     """
  74     def __init__(self):
  75         curve25519.keys.Private.__init__(self)
  76         self._memo_public = None
  77
  78     def get_public(self):
  79         if self._memo_public is None:
  80             self._memo_public = curve25519.keys.Private.get_public(self)
  81
  82         return self._memo_public
  83
  84 # ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  85
  86 def kdf_rfc5869(key, salt, info, n):
  87
  88     prk = HMAC(key=salt, msg=key)
  89
  90     out = b""
  91     last = b""
  92     i = 1
  93     while len(out) < n:
  94         m = last + info + chr(i)
  95         last = h = HMAC(key=prk, msg=m)
  96         out += h
  97         i = i + 1
  98     return out[:n]
  99
 100 def kdf_ntor(key, n):
 101     return kdf_rfc5869(key, T_KEY, M_EXPAND, n)
 102
 103 # ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 104
 105 def client_part1(node_id, pubkey_B):
 106     """Initial handshake, client side.
 107
 108        From the specification:
 109
 110          <<To send a create cell, the client generates a keypair x,X =
 111            KEYGEN(), and sends a CREATE cell with contents:
 112
 113            NODEID:     ID             -- ID_LENGTH bytes
 114            KEYID:      KEYID(B)       -- H_LENGTH bytes
 115            CLIENT_PK:  X              -- G_LENGTH bytes
 116          >>
 117
 118        Takes node_id -- a digest of the server's identity key,
 119              pubkey_B -- a public key for the server.
 120        Returns a tuple of (client secret key x, client->server message)"""
 121
 122     assert len(node_id) == NODE_ID_LENGTH
 123
 124     key_id = keyid(pubkey_B)
 125     seckey_x = PrivateKey()
 126     pubkey_X = seckey_x.get_public().serialize()
 127
 128     message = node_id + key_id + pubkey_X
 129
 130     assert len(message) == NODE_ID_LENGTH + H_LENGTH + H_LENGTH
 131     return seckey_x , message
 132
 133 def hash_nil(x):
 134     """Identity function: if we don't pass a hash function that does nothing,
 135        the curve25519 python lib will try to sha256 it for us."""
 136     return x
 137
 138 def bad_result(r):
 139     """Helper: given a result of multiplying a public key by a private key,
 140        return True iff one of the inputs was broken"""
 141     assert len(r) == 32
 142     return r == '\x00'*32
 143
 144 def server(seckey_b, my_node_id, message, keyBytes=72):
 145     """Handshake step 2, server side.
 146
 147        From the spec:
 148
 149        <<
 150          The server generates a keypair of y,Y = KEYGEN(), and computes
 151
 152            secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID
 153            KEY_SEED = H(secret_input, t_key)
 154            verify = H(secret_input, t_verify)
 155            auth_input = verify | ID | B | Y | X | PROTOID | "Server"
 156
 157          The server sends a CREATED cell containing:
 158
 159            SERVER_PK:  Y                     -- G_LENGTH bytes
 160            AUTH:       H(auth_input, t_mac)  -- H_LENGTH byets
 161         >>
 162
 163        Takes seckey_b -- the server's secret key
 164              my_node_id -- the servers's public key digest,
 165              message -- a message from a client
 166              keybytes -- amount of key material to generate
 167
 168        Returns a tuple of (key material, sever->client reply), or None on
 169        error.
 170     """
 171
 172     assert len(message) == NODE_ID_LENGTH + H_LENGTH + H_LENGTH
 173
 174     if my_node_id != message[:NODE_ID_LENGTH]:
 175         return None
 176
 177     badness = (keyid(seckey_b.get_public()) !=
 178                message[NODE_ID_LENGTH:NODE_ID_LENGTH+H_LENGTH])
 179
 180     pubkey_X = curve25519.keys.Public(message[NODE_ID_LENGTH+H_LENGTH:])
 181     seckey_y = PrivateKey()
 182     pubkey_Y = seckey_y.get_public()
 183     pubkey_B = seckey_b.get_public()
 184     xy = seckey_y.get_shared_key(pubkey_X, hash_nil)
 185     xb = seckey_b.get_shared_key(pubkey_X, hash_nil)
 186
 187     # secret_input = EXP(X,y) | EXP(X,b) | ID | B | X | Y | PROTOID
 188     secret_input = (xy + xb + my_node_id +
 189                     pubkey_B.serialize() +
 190                     pubkey_X.serialize() +
 191                     pubkey_Y.serialize() +
 192                     PROTOID)
 193
 194     verify = H_verify(secret_input)
 195
 196     # auth_input = verify | ID | B | Y | X | PROTOID | "Server"
 197     auth_input = (verify +
 198                   my_node_id +
 199                   pubkey_B.serialize() +
 200                   pubkey_Y.serialize() +
 201                   pubkey_X.serialize() +
 202                   PROTOID +
 203                   "Server")
 204
 205     msg = pubkey_Y.serialize() + H_mac(auth_input)
 206
 207     badness += bad_result(xb)
 208     badness += bad_result(xy)
 209
 210     if badness:
 211         return None
 212
 213     keys = kdf_ntor(secret_input, keyBytes)
 214
 215     return keys, msg
 216
 217 def client_part2(seckey_x, msg, node_id, pubkey_B, keyBytes=72):
 218     """Handshake step 3: client side again.
 219
 220        From the spec:
 221
 222        <<
 223          The client then checks Y is in G^* [see NOTE below], and computes
 224
 225          secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID
 226          KEY_SEED = H(secret_input, t_key)
 227          verify = H(secret_input, t_verify)
 228          auth_input = verify | ID | B | Y | X | PROTOID | "Server"
 229
 230          The client verifies that AUTH == H(auth_input, t_mac).
 231        >>
 232
 233        Takes seckey_x -- the secret key we generated in step 1.
 234              msg -- the message from the server.
 235              node_id -- the node_id we used in step 1.
 236              server_key -- the same public key we used in step 1.
 237              keyBytes -- the number of bytes we want to generate
 238        Returns key material, or None on error
 239
 240     """
 241     assert len(msg) == G_LENGTH + H_LENGTH
 242
 243     pubkey_Y = curve25519.keys.Public(msg[:G_LENGTH])
 244     their_auth = msg[G_LENGTH:]
 245
 246     pubkey_X = seckey_x.get_public()
 247
 248     yx = seckey_x.get_shared_key(pubkey_Y, hash_nil)
 249     bx = seckey_x.get_shared_key(pubkey_B, hash_nil)
 250
 251
 252     # secret_input = EXP(Y,x) | EXP(B,x) | ID | B | X | Y | PROTOID
 253     secret_input = (yx + bx + node_id +
 254                     pubkey_B.serialize() +
 255                     pubkey_X.serialize() +
 256                     pubkey_Y.serialize() + PROTOID)
 257
 258     verify = H_verify(secret_input)
 259
 260     # auth_input = verify | ID | B | Y | X | PROTOID | "Server"
 261     auth_input = (verify + node_id +
 262                   pubkey_B.serialize() +
 263                   pubkey_Y.serialize() +
 264                   pubkey_X.serialize() + PROTOID +
 265                   "Server")
 266
 267     my_auth = H_mac(auth_input)
 268
 269     badness = my_auth != their_auth
 270     badness = bad_result(yx) + bad_result(bx)
 271
 272     if badness:
 273         return None
 274
 275     return kdf_ntor(secret_input, keyBytes)
 276
 277 # ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 278
 279 def demo(node_id="iToldYouAboutStairs.", server_key=PrivateKey()):
 280     """
 281        Try to handshake with ourself.
 282     """
 283     x, create = client_part1(node_id, server_key.get_public())
 284     skeys, created = server(server_key, node_id, create)
 285     ckeys = client_part2(x, created, node_id, server_key.get_public())
 286     assert len(skeys) == 72
 287     assert len(ckeys) == 72
 288     assert skeys == ckeys
 289
 290 # ======================================================================
 291 def timing():
 292     """
 293        Use Python's timeit module to see how fast this nonsense is
 294     """
 295     import timeit
 296     t = timeit.Timer(stmt="ntor_ref.demo(N,SK)",
 297        setup="import ntor_ref,curve25519;N='ABCD'*5;SK=ntor_ref.PrivateKey()")
 298     print t.timeit(number=1000)
 299
 300 # ======================================================================
 301
 302 def kdf_vectors():
 303     """
 304        Generate some vectors to check our KDF.
 305     """
 306     import binascii
 307     def kdf_vec(inp):
 308         k = kdf(inp, T_KEY, M_EXPAND, 100)
 309         print repr(inp), "\n\""+ binascii.b2a_hex(k)+ "\""
 310     kdf_vec("")
 311     kdf_vec("Tor")
 312     kdf_vec("AN ALARMING ITEM TO FIND ON YOUR CREDIT-RATING STATEMENT")
 313
 314 # ======================================================================
 315
 316
 317 def test_tor():
 318     """
 319        Call the test-ntor-cl command-line program to make sure we can
 320        interoperate with Tor's ntor program
 321     """
 322     enhex=binascii.b2a_hex
 323     dehex=lambda s: binascii.a2b_hex(s.strip())
 324
 325     PROG = "./src/test/test-ntor-cl"
 326     def tor_client1(node_id, pubkey_B):
 327         " returns (msg, state) "
 328         p = subprocess.Popen([PROG, "client1", enhex(node_id),
 329                               enhex(pubkey_B.serialize())],
 330                              stdout=subprocess.PIPE)
 331         return map(dehex, p.stdout.readlines())
 332     def tor_server1(seckey_b, node_id, msg, n):
 333         " returns (msg, keys) "
 334         p = subprocess.Popen([PROG, "server1", enhex(seckey_b.serialize()),
 335                               enhex(node_id), enhex(msg), str(n)],
 336                              stdout=subprocess.PIPE)
 337         return map(dehex, p.stdout.readlines())
 338     def tor_client2(state, msg, n):
 339         " returns (keys,) "
 340         p = subprocess.Popen([PROG, "client2", enhex(state),
 341                               enhex(msg), str(n)],
 342                              stdout=subprocess.PIPE)
 343         return map(dehex, p.stdout.readlines())
 344
 345
 346     node_id = "thisisatornodeid$#%^"
 347     seckey_b = PrivateKey()
 348     pubkey_B = seckey_b.get_public()
 349
 350     # Do a pure-Tor handshake
 351     c2s_msg, c_state = tor_client1(node_id, pubkey_B)
 352     s2c_msg, s_keys = tor_server1(seckey_b, node_id, c2s_msg, 90)
 353     c_keys, = tor_client2(c_state, s2c_msg, 90)
 354     assert c_keys == s_keys
 355     assert len(c_keys) == 90
 356
 357     # Try a mixed handshake with Tor as the client
 358     c2s_msg, c_state = tor_client1(node_id, pubkey_B)
 359     s_keys, s2c_msg = server(seckey_b, node_id, c2s_msg, 90)
 360     c_keys, = tor_client2(c_state, s2c_msg, 90)
 361     assert c_keys == s_keys
 362     assert len(c_keys) == 90
 363
 364     # Now do a mixed handshake with Tor as the server
 365     c_x, c2s_msg = client_part1(node_id, pubkey_B)
 366     s2c_msg, s_keys = tor_server1(seckey_b, node_id, c2s_msg, 90)
 367     c_keys = client_part2(c_x, s2c_msg, node_id, pubkey_B, 90)
 368     assert c_keys == s_keys
 369     assert len(c_keys) == 90
 370
 371     print "We just interoperated."
 372
 373 # ======================================================================
 374
 375 if __name__ == '__main__':
 376     import sys
 377     if sys.argv[1] == 'gen_kdf_vectors':
 378         kdf_vectors()
 379     elif sys.argv[1] == 'timing':
 380         timing()
 381     elif sys.argv[1] == 'self-test':
 382         demo()
 383     elif sys.argv[1] == 'test-tor':
 384         test_tor()
 385
 386     else:
 387         print __doc__