ntor_ref.py 12 KB

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