hs_ntor_ref.py 18 KB

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