src/test/ntor_ref.py

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