src/test/hs_ntor_ref.py

   1 #!/usr/bin/python
   2 # Copyright 2017-2019, The Tor Project, Inc
   3 # See LICENSE for licensing information
   4
   5 """
   6 hs_ntor_ref.py
   7
   8 This module is a reference implementation of the modified ntor protocol
   9 proposed for Tor hidden services in proposal 224 (Next Generation Hidden
  10 Services) in section [NTOR-WITH-EXTRA-DATA].
  11
  12 The modified ntor protocol is a single-round protocol, with three steps in total:
  13
  14     1: Client generates keys and sends them to service via INTRODUCE cell
  15
  16     2: Service computes key material based on client's keys, and sends its own
  17        keys to client via RENDEZVOUS cell
  18
  19     3: Client computes key material as well.
  20
  21 It's meant to be used to validate Tor's HS ntor implementation by conducting
  22 various integration tests. Specifically it conducts the following three tests:
  23
  24 - Tests our Python implementation by running the whole protocol in Python and
  25   making sure that results are consistent.
  26
  27 - Tests little-t-tor ntor implementation. We use this Python code to instrument
  28   little-t-tor and carry out the handshake by using little-t-tor code. The
  29   small C wrapper at src/test/test-hs-ntor-cl is used for this Python module to
  30   interface with little-t-tor.
  31
  32 - Cross-tests Python and little-t-tor implementation by running half of the
  33   protocol in Python code and the other in little-t-tor. This is actually two
  34   tests so that all parts of the protocol are run both by little-t-tor and
  35   Python.
  36
  37 It requires the curve25519 python module from the curve25519-donna package.
  38
  39 The whole logic and concept for this test suite was taken from ntor_ref.py.
  40
  41                 *** DO NOT USE THIS IN PRODUCTION. ***
  42 """
  43
  44 # Future imports for Python 2.7, mandatory in 3.0
  45 from __future__ import division
  46 from __future__ import print_function
  47 from __future__ import unicode_literals
  48
  49 import struct
  50 import os, sys
  51 import binascii
  52 import subprocess
  53
  54 try:
  55     import curve25519
  56     curve25519mod = curve25519.keys
  57 except ImportError:
  58     curve25519 = None
  59     import slownacl_curve25519
  60     curve25519mod = slownacl_curve25519
  61
  62 import hashlib
  63 try:
  64     import sha3
  65 except ImportError:
  66     # In python 3.6, the sha3 functions are in hashlib whether we
  67     # import sha3 or not.
  68     sha3 = None
  69
  70 try:
  71     # Pull the sha3 functions in.
  72     from hashlib import sha3_256, shake_256
  73     def shake_squeeze(obj, n):
  74         return obj.digest(n)
  75 except ImportError:
  76     if hasattr(sha3, "SHA3256"):
  77         # If this happens, then we have the old "sha3" module which
  78         # hashlib and pysha3 superseded.
  79         sha3_256 = sha3.SHA3256
  80         shake_256 = sha3.SHAKE256
  81         def shake_squeeze(obj, n):
  82             return obj.squeeze(n)
  83     else:
  84         # error code 77 tells automake to skip this test
  85         sys.exit(77)
  86
  87 # Import Nick's ntor reference implementation in Python
  88 # We are gonna use a few of its utilities.
  89 from ntor_ref import hash_nil
  90 from ntor_ref import PrivateKey
  91
  92 # String constants used in this protocol
  93 PROTOID = b"tor-hs-ntor-curve25519-sha3-256-1"
  94 T_HSENC    = PROTOID + b":hs_key_extract"
  95 T_HSVERIFY = PROTOID + b":hs_verify"
  96 T_HSMAC    = PROTOID + b":hs_mac"
  97 M_HSEXPAND = PROTOID + b":hs_key_expand"
  98
  99 INTRO_SECRET_LEN = 161
 100 REND_SECRET_LEN = 225
 101 AUTH_INPUT_LEN = 199
 102
 103 # Implements MAC(k,m) = H(htonll(len(k)) | k | m)
 104 def mac(k,m):
 105     def htonll(num):
 106         return struct.pack('!q', num)
 107
 108     s = sha3_256()
 109     s.update(htonll(len(k)))
 110     s.update(k)
 111     s.update(m)
 112     return s.digest()
 113
 114 ######################################################################
 115
 116 # Functions that implement the modified HS ntor protocol
 117
 118 """As client compute key material for INTRODUCE cell as follows:
 119
 120   intro_secret_hs_input = EXP(B,x) | AUTH_KEY | X | B | PROTOID
 121   info = m_hsexpand | subcredential
 122   hs_keys = KDF(intro_secret_hs_input | t_hsenc | info, S_KEY_LEN+MAC_LEN)
 123   ENC_KEY = hs_keys[0:S_KEY_LEN]
 124   MAC_KEY = hs_keys[S_KEY_LEN:S_KEY_LEN+MAC_KEY_LEN]
 125 """
 126 def intro2_ntor_client(intro_auth_pubkey_str, intro_enc_pubkey,
 127                        client_ephemeral_enc_pubkey, client_ephemeral_enc_privkey, subcredential):
 128
 129     dh_result = client_ephemeral_enc_privkey.get_shared_key(intro_enc_pubkey, hash_nil)
 130     secret =  dh_result + intro_auth_pubkey_str + client_ephemeral_enc_pubkey.serialize() + intro_enc_pubkey.serialize() + PROTOID
 131     assert(len(secret) == INTRO_SECRET_LEN)
 132     info = M_HSEXPAND + subcredential
 133
 134     kdf = shake_256()
 135     kdf.update(secret + T_HSENC + info)
 136     key_material = shake_squeeze(kdf, 64*8)
 137
 138     enc_key = key_material[0:32]
 139     mac_key = key_material[32:64]
 140
 141     return enc_key, mac_key
 142
 143 """Wrapper over intro2_ntor_client()"""
 144 def client_part1(intro_auth_pubkey_str, intro_enc_pubkey,
 145                  client_ephemeral_enc_pubkey, client_ephemeral_enc_privkey, subcredential):
 146     enc_key, mac_key = intro2_ntor_client(intro_auth_pubkey_str, intro_enc_pubkey, client_ephemeral_enc_pubkey, client_ephemeral_enc_privkey, subcredential)
 147     assert(enc_key)
 148     assert(mac_key)
 149
 150     return enc_key, mac_key
 151
 152 """As service compute key material for INTRODUCE cell as follows:
 153
 154   intro_secret_hs_input = EXP(X,b) | AUTH_KEY | X | B | PROTOID
 155   info = m_hsexpand | subcredential
 156   hs_keys = KDF(intro_secret_hs_input | t_hsenc | info, S_KEY_LEN+MAC_LEN)
 157   HS_DEC_KEY = hs_keys[0:S_KEY_LEN]
 158   HS_MAC_KEY = hs_keys[S_KEY_LEN:S_KEY_LEN+MAC_KEY_LEN]
 159 """
 160 def intro2_ntor_service(intro_auth_pubkey_str, client_enc_pubkey, service_enc_privkey, service_enc_pubkey, subcredential):
 161     dh_result = service_enc_privkey.get_shared_key(client_enc_pubkey, hash_nil)
 162     secret = dh_result + intro_auth_pubkey_str + client_enc_pubkey.serialize() + service_enc_pubkey.serialize() + PROTOID
 163     assert(len(secret) == INTRO_SECRET_LEN)
 164     info = M_HSEXPAND + subcredential
 165
 166     kdf = shake_256()
 167     kdf.update(secret + T_HSENC + info)
 168     key_material = shake_squeeze(kdf, 64*8)
 169
 170     enc_key = key_material[0:32]
 171     mac_key = key_material[32:64]
 172
 173     return enc_key, mac_key
 174
 175 """As service compute key material for INTRODUCE and REDNEZVOUS cells.
 176
 177   Use intro2_ntor_service() to calculate the INTRODUCE key material, and use
 178   the following computations to do the RENDEZVOUS ones:
 179
 180       rend_secret_hs_input = EXP(X,y) | EXP(X,b) | AUTH_KEY | B | X | Y | PROTOID
 181       NTOR_KEY_SEED = MAC(rend_secret_hs_input, t_hsenc)
 182       verify = MAC(rend_secret_hs_input, t_hsverify)
 183       auth_input = verify | AUTH_KEY | B | Y | X | PROTOID | "Server"
 184       AUTH_INPUT_MAC = MAC(auth_input, t_hsmac)
 185 """
 186 def service_part1(intro_auth_pubkey_str, client_enc_pubkey, intro_enc_privkey, intro_enc_pubkey, subcredential):
 187     intro_enc_key, intro_mac_key = intro2_ntor_service(intro_auth_pubkey_str, client_enc_pubkey, intro_enc_privkey, intro_enc_pubkey, subcredential)
 188     assert(intro_enc_key)
 189     assert(intro_mac_key)
 190
 191     service_ephemeral_privkey = PrivateKey()
 192     service_ephemeral_pubkey = service_ephemeral_privkey.get_public()
 193
 194     dh_result1 = service_ephemeral_privkey.get_shared_key(client_enc_pubkey, hash_nil)
 195     dh_result2 = intro_enc_privkey.get_shared_key(client_enc_pubkey, hash_nil)
 196     rend_secret_hs_input = dh_result1 + dh_result2 + intro_auth_pubkey_str + intro_enc_pubkey.serialize() + client_enc_pubkey.serialize() + service_ephemeral_pubkey.serialize() + PROTOID
 197     assert(len(rend_secret_hs_input) == REND_SECRET_LEN)
 198
 199     ntor_key_seed = mac(rend_secret_hs_input, T_HSENC)
 200     verify = mac(rend_secret_hs_input, T_HSVERIFY)
 201     auth_input = verify + intro_auth_pubkey_str + intro_enc_pubkey.serialize() + service_ephemeral_pubkey.serialize() + client_enc_pubkey.serialize() + PROTOID + b"Server"
 202     assert(len(auth_input) == AUTH_INPUT_LEN)
 203     auth_input_mac = mac(auth_input, T_HSMAC)
 204
 205     assert(ntor_key_seed)
 206     assert(auth_input_mac)
 207     assert(service_ephemeral_pubkey)
 208
 209     return intro_enc_key, intro_mac_key, ntor_key_seed, auth_input_mac, service_ephemeral_pubkey
 210
 211 """As client compute key material for rendezvous cells as follows:
 212
 213   rend_secret_hs_input = EXP(Y,x) | EXP(B,x) | AUTH_KEY | B | X | Y | PROTOID
 214   NTOR_KEY_SEED = MAC(ntor_secret_input, t_hsenc)
 215   verify = MAC(ntor_secret_input, t_hsverify)
 216   auth_input = verify | AUTH_KEY | B | Y | X | PROTOID | "Server"
 217   AUTH_INPUT_MAC = MAC(auth_input, t_hsmac)
 218 """
 219 def client_part2(intro_auth_pubkey_str, client_ephemeral_enc_pubkey, client_ephemeral_enc_privkey,
 220                  intro_enc_pubkey, service_ephemeral_rend_pubkey):
 221     dh_result1 = client_ephemeral_enc_privkey.get_shared_key(service_ephemeral_rend_pubkey, hash_nil)
 222     dh_result2 = client_ephemeral_enc_privkey.get_shared_key(intro_enc_pubkey, hash_nil)
 223     rend_secret_hs_input = dh_result1 + dh_result2 + intro_auth_pubkey_str + intro_enc_pubkey.serialize() + client_ephemeral_enc_pubkey.serialize() + service_ephemeral_rend_pubkey.serialize() + PROTOID
 224     assert(len(rend_secret_hs_input) == REND_SECRET_LEN)
 225
 226     ntor_key_seed = mac(rend_secret_hs_input, T_HSENC)
 227     verify = mac(rend_secret_hs_input, T_HSVERIFY)
 228     auth_input = verify + intro_auth_pubkey_str + intro_enc_pubkey.serialize() + service_ephemeral_rend_pubkey.serialize() + client_ephemeral_enc_pubkey.serialize() + PROTOID + b"Server"
 229     assert(len(auth_input) == AUTH_INPUT_LEN)
 230     auth_input_mac = mac(auth_input, T_HSMAC)
 231
 232     assert(ntor_key_seed)
 233     assert(auth_input_mac)
 234
 235     return ntor_key_seed, auth_input_mac
 236
 237 #################################################################################
 238
 239 """
 240 Utilities for communicating with the little-t-tor ntor wrapper to conduct the
 241 integration tests
 242 """
 243
 244 PROG = "./src/test/test-hs-ntor-cl"
 245 if sys.version_info[0] >= 3:
 246     enhex=lambda s: binascii.b2a_hex(s).decode("ascii")
 247 else:
 248     enhex=lambda s: binascii.b2a_hex(s)
 249 dehex=lambda s: binascii.a2b_hex(s.strip())
 250
 251 def tor_client1(intro_auth_pubkey_str, intro_enc_pubkey,
 252                 client_ephemeral_enc_privkey, subcredential):
 253     p = subprocess.Popen([PROG, "client1",
 254                           enhex(intro_auth_pubkey_str),
 255                           enhex(intro_enc_pubkey.serialize()),
 256                           enhex(client_ephemeral_enc_privkey.serialize()),
 257                           enhex(subcredential)],
 258                          stdout=subprocess.PIPE)
 259     return map(dehex, p.stdout.readlines())
 260
 261 def tor_server1(intro_auth_pubkey_str, intro_enc_privkey,
 262                 client_ephemeral_enc_pubkey, subcredential):
 263     p = subprocess.Popen([PROG, "server1",
 264                           enhex(intro_auth_pubkey_str),
 265                           enhex(intro_enc_privkey.serialize()),
 266                           enhex(client_ephemeral_enc_pubkey.serialize()),
 267                           enhex(subcredential)],
 268                          stdout=subprocess.PIPE)
 269     return map(dehex, p.stdout.readlines())
 270
 271 def tor_client2(intro_auth_pubkey_str, client_ephemeral_enc_privkey,
 272                 intro_enc_pubkey, service_ephemeral_rend_pubkey, subcredential):
 273     p = subprocess.Popen([PROG, "client2",
 274                           enhex(intro_auth_pubkey_str),
 275                           enhex(client_ephemeral_enc_privkey.serialize()),
 276                           enhex(intro_enc_pubkey.serialize()),
 277                           enhex(service_ephemeral_rend_pubkey.serialize()),
 278                           enhex(subcredential)],
 279                          stdout=subprocess.PIPE)
 280     return map(dehex, p.stdout.readlines())
 281
 282 ##################################################################################
 283
 284 # Perform a pure python ntor test
 285 def do_pure_python_ntor_test():
 286     # Initialize all needed key material
 287     client_ephemeral_enc_privkey = PrivateKey()
 288     client_ephemeral_enc_pubkey = client_ephemeral_enc_privkey.get_public()
 289     intro_enc_privkey = PrivateKey()
 290     intro_enc_pubkey = intro_enc_privkey.get_public()
 291     intro_auth_pubkey_str = os.urandom(32)
 292     subcredential = os.urandom(32)
 293
 294     client_enc_key, client_mac_key = client_part1(intro_auth_pubkey_str, intro_enc_pubkey, client_ephemeral_enc_pubkey, client_ephemeral_enc_privkey, subcredential)
 295
 296     service_enc_key, service_mac_key, service_ntor_key_seed, service_auth_input_mac, service_ephemeral_pubkey = service_part1(intro_auth_pubkey_str, client_ephemeral_enc_pubkey, intro_enc_privkey, intro_enc_pubkey, subcredential)
 297
 298     assert(client_enc_key == service_enc_key)
 299     assert(client_mac_key == service_mac_key)
 300
 301     client_ntor_key_seed, client_auth_input_mac = client_part2(intro_auth_pubkey_str, client_ephemeral_enc_pubkey, client_ephemeral_enc_privkey,
 302                                                                intro_enc_pubkey, service_ephemeral_pubkey)
 303
 304     assert(client_ntor_key_seed == service_ntor_key_seed)
 305     assert(client_auth_input_mac == service_auth_input_mac)
 306
 307     print("DONE: python dance [%s]" % repr(client_auth_input_mac))
 308
 309 # Perform a pure little-t-tor integration test.
 310 def do_little_t_tor_ntor_test():
 311     # Initialize all needed key material
 312     subcredential = os.urandom(32)
 313     client_ephemeral_enc_privkey = PrivateKey()
 314     client_ephemeral_enc_pubkey = client_ephemeral_enc_privkey.get_public()
 315     intro_enc_privkey = PrivateKey()
 316     intro_enc_pubkey = intro_enc_privkey.get_public() # service-side enc key
 317     intro_auth_pubkey_str = os.urandom(32)
 318
 319     client_enc_key, client_mac_key = tor_client1(intro_auth_pubkey_str, intro_enc_pubkey,
 320                                                  client_ephemeral_enc_privkey, subcredential)
 321     assert(client_enc_key)
 322     assert(client_mac_key)
 323
 324     service_enc_key, service_mac_key, service_ntor_auth_mac, service_ntor_key_seed, service_eph_pubkey = tor_server1(intro_auth_pubkey_str,
 325                                                                                                                      intro_enc_privkey,
 326                                                                                                                      client_ephemeral_enc_pubkey,
 327                                                                                                                      subcredential)
 328     assert(service_enc_key)
 329     assert(service_mac_key)
 330     assert(service_ntor_auth_mac)
 331     assert(service_ntor_key_seed)
 332
 333     assert(client_enc_key == service_enc_key)
 334     assert(client_mac_key == service_mac_key)
 335
 336     # Turn from bytes to key
 337     service_eph_pubkey = curve25519mod.Public(service_eph_pubkey)
 338
 339     client_ntor_auth_mac, client_ntor_key_seed  = tor_client2(intro_auth_pubkey_str, client_ephemeral_enc_privkey,
 340                                                               intro_enc_pubkey, service_eph_pubkey, subcredential)
 341     assert(client_ntor_auth_mac)
 342     assert(client_ntor_key_seed)
 343
 344     assert(client_ntor_key_seed == service_ntor_key_seed)
 345     assert(client_ntor_auth_mac == service_ntor_auth_mac)
 346
 347     print("DONE: tor dance [%s]" % repr(client_ntor_auth_mac))
 348
 349 """
 350 Do mixed test as follows:
 351     1. C -> S (python mode)
 352     2. C <- S (tor mode)
 353     3. Client computes keys (python mode)
 354 """
 355 def do_first_mixed_test():
 356     subcredential = os.urandom(32)
 357
 358     client_ephemeral_enc_privkey = PrivateKey()
 359     client_ephemeral_enc_pubkey = client_ephemeral_enc_privkey.get_public()
 360     intro_enc_privkey = PrivateKey()
 361     intro_enc_pubkey = intro_enc_privkey.get_public() # service-side enc key
 362
 363     intro_auth_pubkey_str = os.urandom(32)
 364
 365     # Let's do mixed
 366     client_enc_key, client_mac_key = client_part1(intro_auth_pubkey_str, intro_enc_pubkey,
 367                                                   client_ephemeral_enc_pubkey, client_ephemeral_enc_privkey,
 368                                                   subcredential)
 369
 370     service_enc_key, service_mac_key, service_ntor_auth_mac, service_ntor_key_seed, service_eph_pubkey = tor_server1(intro_auth_pubkey_str,
 371                                                                                                                      intro_enc_privkey,
 372                                                                                                                      client_ephemeral_enc_pubkey,
 373                                                                                                                      subcredential)
 374     assert(service_enc_key)
 375     assert(service_mac_key)
 376     assert(service_ntor_auth_mac)
 377     assert(service_ntor_key_seed)
 378     assert(service_eph_pubkey)
 379
 380     assert(client_enc_key == service_enc_key)
 381     assert(client_mac_key == service_mac_key)
 382
 383     # Turn from bytes to key
 384     service_eph_pubkey = curve25519mod.Public(service_eph_pubkey)
 385
 386     client_ntor_key_seed, client_auth_input_mac = client_part2(intro_auth_pubkey_str, client_ephemeral_enc_pubkey, client_ephemeral_enc_privkey,
 387                                                                intro_enc_pubkey, service_eph_pubkey)
 388
 389     assert(client_auth_input_mac == service_ntor_auth_mac)
 390     assert(client_ntor_key_seed == service_ntor_key_seed)
 391
 392     print("DONE: 1st mixed dance [%s]" % repr(client_auth_input_mac))
 393
 394 """
 395 Do mixed test as follows:
 396     1. C -> S (tor mode)
 397     2. C <- S (python mode)
 398     3. Client computes keys (tor mode)
 399 """
 400 def do_second_mixed_test():
 401     subcredential = os.urandom(32)
 402
 403     client_ephemeral_enc_privkey = PrivateKey()
 404     client_ephemeral_enc_pubkey = client_ephemeral_enc_privkey.get_public()
 405     intro_enc_privkey = PrivateKey()
 406     intro_enc_pubkey = intro_enc_privkey.get_public() # service-side enc key
 407
 408     intro_auth_pubkey_str = os.urandom(32)
 409
 410     # Let's do mixed
 411     client_enc_key, client_mac_key = tor_client1(intro_auth_pubkey_str, intro_enc_pubkey,
 412                                                  client_ephemeral_enc_privkey, subcredential)
 413     assert(client_enc_key)
 414     assert(client_mac_key)
 415
 416     service_enc_key, service_mac_key, service_ntor_key_seed, service_ntor_auth_mac, service_ephemeral_pubkey = service_part1(intro_auth_pubkey_str, client_ephemeral_enc_pubkey, intro_enc_privkey, intro_enc_pubkey, subcredential)
 417
 418     client_ntor_auth_mac, client_ntor_key_seed  = tor_client2(intro_auth_pubkey_str, client_ephemeral_enc_privkey,
 419                                                               intro_enc_pubkey, service_ephemeral_pubkey, subcredential)
 420     assert(client_ntor_auth_mac)
 421     assert(client_ntor_key_seed)
 422
 423     assert(client_ntor_key_seed == service_ntor_key_seed)
 424     assert(client_ntor_auth_mac == service_ntor_auth_mac)
 425
 426     print("DONE: 2nd mixed dance [%s]" % repr(client_ntor_auth_mac))
 427
 428 def do_mixed_tests():
 429     do_first_mixed_test()
 430     do_second_mixed_test()
 431
 432 if __name__ == '__main__':
 433     do_pure_python_ntor_test()
 434     do_little_t_tor_ntor_test()
 435     do_mixed_tests()