onion.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448
  1. /* Copyright (c) 2001 Matej Pfajfar.
  2. * Copyright (c) 2001-2004, Roger Dingledine.
  3. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
  4. * Copyright (c) 2007-2012, The Tor Project, Inc. */
  5. /* See LICENSE for licensing information */
  6. /**
  7. * \file onion.c
  8. * \brief Functions to queue create cells, and handle onionskin
  9. * parsing and creation.
  10. **/
  11. #include "or.h"
  12. #include "circuitlist.h"
  13. #include "config.h"
  14. #include "onion.h"
  15. #include "rephist.h"
  16. /** Type for a linked list of circuits that are waiting for a free CPU worker
  17. * to process a waiting onion handshake. */
  18. typedef struct onion_queue_t {
  19. or_circuit_t *circ;
  20. char *onionskin;
  21. time_t when_added;
  22. struct onion_queue_t *next;
  23. } onion_queue_t;
  24. /** 5 seconds on the onion queue til we just send back a destroy */
  25. #define ONIONQUEUE_WAIT_CUTOFF 5
  26. /** First and last elements in the linked list of circuits waiting for CPU
  27. * workers, or NULL if the list is empty.
  28. * @{ */
  29. static onion_queue_t *ol_list=NULL;
  30. static onion_queue_t *ol_tail=NULL;
  31. /**@}*/
  32. /** Length of ol_list */
  33. static int ol_length=0;
  34. /** Add <b>circ</b> to the end of ol_list and return 0, except
  35. * if ol_list is too long, in which case do nothing and return -1.
  36. */
  37. int
  38. onion_pending_add(or_circuit_t *circ, char *onionskin)
  39. {
  40. onion_queue_t *tmp;
  41. time_t now = time(NULL);
  42. tmp = tor_malloc_zero(sizeof(onion_queue_t));
  43. tmp->circ = circ;
  44. tmp->onionskin = onionskin;
  45. tmp->when_added = now;
  46. if (!ol_tail) {
  47. tor_assert(!ol_list);
  48. tor_assert(!ol_length);
  49. ol_list = tmp;
  50. ol_tail = tmp;
  51. ol_length++;
  52. return 0;
  53. }
  54. tor_assert(ol_list);
  55. tor_assert(!ol_tail->next);
  56. if (ol_length >= get_options()->MaxOnionsPending) {
  57. #define WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL (60)
  58. static ratelim_t last_warned =
  59. RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL);
  60. char *m;
  61. if ((m = rate_limit_log(&last_warned, approx_time()))) {
  62. log_warn(LD_GENERAL,
  63. "Your computer is too slow to handle this many circuit "
  64. "creation requests! Please consider using the "
  65. "MaxAdvertisedBandwidth config option or choosing a more "
  66. "restricted exit policy.%s",m);
  67. tor_free(m);
  68. }
  69. tor_free(tmp);
  70. return -1;
  71. }
  72. ol_length++;
  73. ol_tail->next = tmp;
  74. ol_tail = tmp;
  75. while ((int)(now - ol_list->when_added) >= ONIONQUEUE_WAIT_CUTOFF) {
  76. /* cull elderly requests. */
  77. circ = ol_list->circ;
  78. onion_pending_remove(ol_list->circ);
  79. log_info(LD_CIRC,
  80. "Circuit create request is too old; canceling due to overload.");
  81. circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_RESOURCELIMIT);
  82. }
  83. return 0;
  84. }
  85. /** Remove the first item from ol_list and return it, or return
  86. * NULL if the list is empty.
  87. */
  88. or_circuit_t *
  89. onion_next_task(char **onionskin_out)
  90. {
  91. or_circuit_t *circ;
  92. if (!ol_list)
  93. return NULL; /* no onions pending, we're done */
  94. tor_assert(ol_list->circ);
  95. tor_assert(ol_list->circ->p_chan); /* make sure it's still valid */
  96. tor_assert(ol_length > 0);
  97. circ = ol_list->circ;
  98. *onionskin_out = ol_list->onionskin;
  99. ol_list->onionskin = NULL; /* prevent free. */
  100. onion_pending_remove(ol_list->circ);
  101. return circ;
  102. }
  103. /** Go through ol_list, find the onion_queue_t element which points to
  104. * circ, remove and free that element. Leave circ itself alone.
  105. */
  106. void
  107. onion_pending_remove(or_circuit_t *circ)
  108. {
  109. onion_queue_t *tmpo, *victim;
  110. if (!ol_list)
  111. return; /* nothing here. */
  112. /* first check to see if it's the first entry */
  113. tmpo = ol_list;
  114. if (tmpo->circ == circ) {
  115. /* it's the first one. remove it from the list. */
  116. ol_list = tmpo->next;
  117. if (!ol_list)
  118. ol_tail = NULL;
  119. ol_length--;
  120. victim = tmpo;
  121. } else { /* we need to hunt through the rest of the list */
  122. for ( ;tmpo->next && tmpo->next->circ != circ; tmpo=tmpo->next) ;
  123. if (!tmpo->next) {
  124. log_debug(LD_GENERAL,
  125. "circ (p_circ_id %d) not in list, probably at cpuworker.",
  126. circ->p_circ_id);
  127. return;
  128. }
  129. /* now we know tmpo->next->circ == circ */
  130. victim = tmpo->next;
  131. tmpo->next = victim->next;
  132. if (ol_tail == victim)
  133. ol_tail = tmpo;
  134. ol_length--;
  135. }
  136. /* now victim points to the element that needs to be removed */
  137. tor_free(victim->onionskin);
  138. tor_free(victim);
  139. }
  140. /*----------------------------------------------------------------------*/
  141. /** Given a router's 128 byte public key,
  142. * stores the following in onion_skin_out:
  143. * - [42 bytes] OAEP padding
  144. * - [16 bytes] Symmetric key for encrypting blob past RSA
  145. * - [70 bytes] g^x part 1 (inside the RSA)
  146. * - [58 bytes] g^x part 2 (symmetrically encrypted)
  147. *
  148. * Stores the DH private key into handshake_state_out for later completion
  149. * of the handshake.
  150. *
  151. * The meeting point/cookies and auth are zeroed out for now.
  152. */
  153. int
  154. onion_skin_create(crypto_pk_t *dest_router_key,
  155. crypto_dh_t **handshake_state_out,
  156. char *onion_skin_out) /* ONIONSKIN_CHALLENGE_LEN bytes */
  157. {
  158. char challenge[DH_KEY_LEN];
  159. crypto_dh_t *dh = NULL;
  160. int dhbytes, pkbytes;
  161. tor_assert(dest_router_key);
  162. tor_assert(handshake_state_out);
  163. tor_assert(onion_skin_out);
  164. *handshake_state_out = NULL;
  165. memset(onion_skin_out, 0, ONIONSKIN_CHALLENGE_LEN);
  166. if (!(dh = crypto_dh_new(DH_TYPE_CIRCUIT)))
  167. goto err;
  168. dhbytes = crypto_dh_get_bytes(dh);
  169. pkbytes = (int) crypto_pk_keysize(dest_router_key);
  170. tor_assert(dhbytes == 128);
  171. tor_assert(pkbytes == 128);
  172. if (crypto_dh_get_public(dh, challenge, dhbytes))
  173. goto err;
  174. note_crypto_pk_op(ENC_ONIONSKIN);
  175. /* set meeting point, meeting cookie, etc here. Leave zero for now. */
  176. if (crypto_pk_public_hybrid_encrypt(dest_router_key, onion_skin_out,
  177. ONIONSKIN_CHALLENGE_LEN,
  178. challenge, DH_KEY_LEN,
  179. PK_PKCS1_OAEP_PADDING, 1)<0)
  180. goto err;
  181. memset(challenge, 0, sizeof(challenge));
  182. *handshake_state_out = dh;
  183. return 0;
  184. err:
  185. memset(challenge, 0, sizeof(challenge));
  186. if (dh) crypto_dh_free(dh);
  187. return -1;
  188. }
  189. /** Given an encrypted DH public key as generated by onion_skin_create,
  190. * and the private key for this onion router, generate the reply (128-byte
  191. * DH plus the first 20 bytes of shared key material), and store the
  192. * next key_out_len bytes of key material in key_out.
  193. */
  194. int
  195. onion_skin_server_handshake(const char *onion_skin, /*ONIONSKIN_CHALLENGE_LEN*/
  196. crypto_pk_t *private_key,
  197. crypto_pk_t *prev_private_key,
  198. char *handshake_reply_out, /*ONIONSKIN_REPLY_LEN*/
  199. char *key_out,
  200. size_t key_out_len)
  201. {
  202. char challenge[ONIONSKIN_CHALLENGE_LEN];
  203. crypto_dh_t *dh = NULL;
  204. ssize_t len;
  205. char *key_material=NULL;
  206. size_t key_material_len=0;
  207. int i;
  208. crypto_pk_t *k;
  209. len = -1;
  210. for (i=0;i<2;++i) {
  211. k = i==0?private_key:prev_private_key;
  212. if (!k)
  213. break;
  214. note_crypto_pk_op(DEC_ONIONSKIN);
  215. len = crypto_pk_private_hybrid_decrypt(k, challenge,
  216. ONIONSKIN_CHALLENGE_LEN,
  217. onion_skin, ONIONSKIN_CHALLENGE_LEN,
  218. PK_PKCS1_OAEP_PADDING,0);
  219. if (len>0)
  220. break;
  221. }
  222. if (len<0) {
  223. log_info(LD_PROTOCOL,
  224. "Couldn't decrypt onionskin: client may be using old onion key");
  225. goto err;
  226. } else if (len != DH_KEY_LEN) {
  227. log_warn(LD_PROTOCOL, "Unexpected onionskin length after decryption: %ld",
  228. (long)len);
  229. goto err;
  230. }
  231. dh = crypto_dh_new(DH_TYPE_CIRCUIT);
  232. if (!dh) {
  233. log_warn(LD_BUG, "Couldn't allocate DH key");
  234. goto err;
  235. }
  236. if (crypto_dh_get_public(dh, handshake_reply_out, DH_KEY_LEN)) {
  237. log_info(LD_GENERAL, "crypto_dh_get_public failed.");
  238. goto err;
  239. }
  240. key_material_len = DIGEST_LEN+key_out_len;
  241. key_material = tor_malloc(key_material_len);
  242. len = crypto_dh_compute_secret(LOG_PROTOCOL_WARN, dh, challenge,
  243. DH_KEY_LEN, key_material,
  244. key_material_len);
  245. if (len < 0) {
  246. log_info(LD_GENERAL, "crypto_dh_compute_secret failed.");
  247. goto err;
  248. }
  249. /* send back H(K|0) as proof that we learned K. */
  250. memcpy(handshake_reply_out+DH_KEY_LEN, key_material, DIGEST_LEN);
  251. /* use the rest of the key material for our shared keys, digests, etc */
  252. memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
  253. memset(challenge, 0, sizeof(challenge));
  254. memset(key_material, 0, key_material_len);
  255. tor_free(key_material);
  256. crypto_dh_free(dh);
  257. return 0;
  258. err:
  259. memset(challenge, 0, sizeof(challenge));
  260. if (key_material) {
  261. memset(key_material, 0, key_material_len);
  262. tor_free(key_material);
  263. }
  264. if (dh) crypto_dh_free(dh);
  265. return -1;
  266. }
  267. /** Finish the client side of the DH handshake.
  268. * Given the 128 byte DH reply + 20 byte hash as generated by
  269. * onion_skin_server_handshake and the handshake state generated by
  270. * onion_skin_create, verify H(K) with the first 20 bytes of shared
  271. * key material, then generate key_out_len more bytes of shared key
  272. * material and store them in key_out.
  273. *
  274. * After the invocation, call crypto_dh_free on handshake_state.
  275. */
  276. int
  277. onion_skin_client_handshake(crypto_dh_t *handshake_state,
  278. const char *handshake_reply, /* ONIONSKIN_REPLY_LEN bytes */
  279. char *key_out,
  280. size_t key_out_len)
  281. {
  282. ssize_t len;
  283. char *key_material=NULL;
  284. size_t key_material_len;
  285. tor_assert(crypto_dh_get_bytes(handshake_state) == DH_KEY_LEN);
  286. key_material_len = DIGEST_LEN + key_out_len;
  287. key_material = tor_malloc(key_material_len);
  288. len = crypto_dh_compute_secret(LOG_PROTOCOL_WARN, handshake_state,
  289. handshake_reply, DH_KEY_LEN, key_material,
  290. key_material_len);
  291. if (len < 0)
  292. goto err;
  293. if (tor_memneq(key_material, handshake_reply+DH_KEY_LEN, DIGEST_LEN)) {
  294. /* H(K) does *not* match. Something fishy. */
  295. log_warn(LD_PROTOCOL,"Digest DOES NOT MATCH on onion handshake. "
  296. "Bug or attack.");
  297. goto err;
  298. }
  299. /* use the rest of the key material for our shared keys, digests, etc */
  300. memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
  301. memset(key_material, 0, key_material_len);
  302. tor_free(key_material);
  303. return 0;
  304. err:
  305. memset(key_material, 0, key_material_len);
  306. tor_free(key_material);
  307. return -1;
  308. }
  309. /** Implement the server side of the CREATE_FAST abbreviated handshake. The
  310. * client has provided DIGEST_LEN key bytes in <b>key_in</b> ("x"). We
  311. * generate a reply of DIGEST_LEN*2 bytes in <b>key_out</b>, consisting of a
  312. * new random "y", followed by H(x|y) to check for correctness. We set
  313. * <b>key_out_len</b> bytes of key material in <b>key_out</b>.
  314. * Return 0 on success, &lt;0 on failure.
  315. **/
  316. int
  317. fast_server_handshake(const uint8_t *key_in, /* DIGEST_LEN bytes */
  318. uint8_t *handshake_reply_out, /* DIGEST_LEN*2 bytes */
  319. uint8_t *key_out,
  320. size_t key_out_len)
  321. {
  322. char tmp[DIGEST_LEN+DIGEST_LEN];
  323. char *out = NULL;
  324. size_t out_len;
  325. int r = -1;
  326. if (crypto_rand((char*)handshake_reply_out, DIGEST_LEN)<0)
  327. return -1;
  328. memcpy(tmp, key_in, DIGEST_LEN);
  329. memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
  330. out_len = key_out_len+DIGEST_LEN;
  331. out = tor_malloc(out_len);
  332. if (crypto_expand_key_material(tmp, sizeof(tmp), out, out_len)) {
  333. goto done;
  334. }
  335. memcpy(handshake_reply_out+DIGEST_LEN, out, DIGEST_LEN);
  336. memcpy(key_out, out+DIGEST_LEN, key_out_len);
  337. r = 0;
  338. done:
  339. memset(tmp, 0, sizeof(tmp));
  340. memset(out, 0, out_len);
  341. tor_free(out);
  342. return r;
  343. }
  344. /** Implement the second half of the client side of the CREATE_FAST handshake.
  345. * We sent the server <b>handshake_state</b> ("x") already, and the server
  346. * told us <b>handshake_reply_out</b> (y|H(x|y)). Make sure that the hash is
  347. * correct, and generate key material in <b>key_out</b>. Return 0 on success,
  348. * true on failure.
  349. *
  350. * NOTE: The "CREATE_FAST" handshake path is distinguishable from regular
  351. * "onionskin" handshakes, and is not secure if an adversary can see or modify
  352. * the messages. Therefore, it should only be used by clients, and only as
  353. * the first hop of a circuit (since the first hop is already authenticated
  354. * and protected by TLS).
  355. */
  356. int
  357. fast_client_handshake(const uint8_t *handshake_state,/*DIGEST_LEN bytes*/
  358. const uint8_t *handshake_reply_out,/*DIGEST_LEN*2 bytes*/
  359. uint8_t *key_out,
  360. size_t key_out_len)
  361. {
  362. char tmp[DIGEST_LEN+DIGEST_LEN];
  363. char *out;
  364. size_t out_len;
  365. int r = -1;
  366. memcpy(tmp, handshake_state, DIGEST_LEN);
  367. memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
  368. out_len = key_out_len+DIGEST_LEN;
  369. out = tor_malloc(out_len);
  370. if (crypto_expand_key_material(tmp, sizeof(tmp), out, out_len)) {
  371. goto done;
  372. }
  373. if (tor_memneq(out, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) {
  374. /* H(K) does *not* match. Something fishy. */
  375. log_warn(LD_PROTOCOL,"Digest DOES NOT MATCH on fast handshake. "
  376. "Bug or attack.");
  377. goto done;
  378. }
  379. memcpy(key_out, out+DIGEST_LEN, key_out_len);
  380. r = 0;
  381. done:
  382. memset(tmp, 0, sizeof(tmp));
  383. memset(out, 0, out_len);
  384. tor_free(out);
  385. return r;
  386. }
  387. /** Remove all circuits from the pending list. Called from tor_free_all. */
  388. void
  389. clear_pending_onions(void)
  390. {
  391. while (ol_list) {
  392. onion_queue_t *victim = ol_list;
  393. ol_list = victim->next;
  394. tor_free(victim->onionskin);
  395. tor_free(victim);
  396. }
  397. ol_list = ol_tail = NULL;
  398. ol_length = 0;
  399. }