onion.c 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566
  1. /* Copyright 2001,2002,2003 Roger Dingledine, Matej Pfajfar. */
  2. /* See LICENSE for licensing information */
  3. /* $Id$ */
  4. #include "or.h"
  5. extern or_options_t options; /* command-line and config-file options */
  6. static int count_acceptable_routers(routerinfo_t **rarray, int rarray_len);
  7. int decide_aci_type(char *local_nick, char *remote_nick) {
  8. int result;
  9. assert(remote_nick);
  10. if(!local_nick)
  11. return ACI_TYPE_LOWER;
  12. result = strcmp(local_nick, remote_nick);
  13. assert(result);
  14. if(result < 0)
  15. return ACI_TYPE_LOWER;
  16. return ACI_TYPE_HIGHER;
  17. }
  18. struct onion_queue_t {
  19. circuit_t *circ;
  20. struct onion_queue_t *next;
  21. };
  22. /* global (within this file) variables used by the next few functions */
  23. static struct onion_queue_t *ol_list=NULL;
  24. static struct onion_queue_t *ol_tail=NULL;
  25. static int ol_length=0;
  26. int onion_pending_add(circuit_t *circ) {
  27. struct onion_queue_t *tmp;
  28. tmp = tor_malloc(sizeof(struct onion_queue_t));
  29. memset(tmp, 0, sizeof(struct onion_queue_t));
  30. tmp->circ = circ;
  31. if(!ol_tail) {
  32. assert(!ol_list);
  33. assert(!ol_length);
  34. ol_list = tmp;
  35. ol_tail = tmp;
  36. ol_length++;
  37. return 0;
  38. }
  39. assert(ol_list);
  40. assert(!ol_tail->next);
  41. if(ol_length >= options.MaxOnionsPending) {
  42. log_fn(LOG_WARN,"Already have %d onions queued. Closing.", ol_length);
  43. free(tmp);
  44. return -1;
  45. }
  46. ol_length++;
  47. ol_tail->next = tmp;
  48. ol_tail = tmp;
  49. return 0;
  50. }
  51. circuit_t *onion_next_task(void) {
  52. circuit_t *circ;
  53. if(!ol_list)
  54. return NULL; /* no onions pending, we're done */
  55. assert(ol_list->circ);
  56. if(!ol_list->circ->p_conn) {
  57. log_fn(LOG_INFO,"ol_list->circ->p_conn null, must have died?");
  58. onion_pending_remove(ol_list->circ);
  59. return onion_next_task(); /* recurse: how about the next one? */
  60. }
  61. assert(ol_length > 0);
  62. circ = ol_list->circ;
  63. onion_pending_remove(ol_list->circ);
  64. return circ;
  65. }
  66. /* go through ol_list, find the onion_queue_t element which points to
  67. * circ, remove and free that element. leave circ itself alone.
  68. */
  69. void onion_pending_remove(circuit_t *circ) {
  70. struct onion_queue_t *tmpo, *victim;
  71. if(!ol_list)
  72. return; /* nothing here. */
  73. /* first check to see if it's the first entry */
  74. tmpo = ol_list;
  75. if(tmpo->circ == circ) {
  76. /* it's the first one. remove it from the list. */
  77. ol_list = tmpo->next;
  78. if(!ol_list)
  79. ol_tail = NULL;
  80. ol_length--;
  81. victim = tmpo;
  82. } else { /* we need to hunt through the rest of the list */
  83. for( ;tmpo->next && tmpo->next->circ != circ; tmpo=tmpo->next) ;
  84. if(!tmpo->next) {
  85. log_fn(LOG_DEBUG,"circ (p_aci %d) not in list, probably at cpuworker.",circ->p_aci);
  86. return;
  87. }
  88. /* now we know tmpo->next->circ == circ */
  89. victim = tmpo->next;
  90. tmpo->next = victim->next;
  91. if(ol_tail == victim)
  92. ol_tail = tmpo;
  93. ol_length--;
  94. }
  95. /* now victim points to the element that needs to be removed */
  96. free(victim);
  97. }
  98. /* given a response payload and keys, initialize, then send a created cell back */
  99. int onionskin_answer(circuit_t *circ, unsigned char *payload, unsigned char *keys) {
  100. unsigned char iv[16];
  101. cell_t cell;
  102. memset(iv, 0, 16);
  103. memset(&cell, 0, sizeof(cell_t));
  104. cell.command = CELL_CREATED;
  105. cell.aci = circ->p_aci;
  106. cell.length = DH_KEY_LEN;
  107. circ->state = CIRCUIT_STATE_OPEN;
  108. log_fn(LOG_DEBUG,"Entering.");
  109. memcpy(cell.payload, payload, DH_KEY_LEN);
  110. log_fn(LOG_DEBUG,"init cipher forward %d, backward %d.", *(int*)keys, *(int*)(keys+16));
  111. if (!(circ->n_crypto =
  112. crypto_create_init_cipher(CIRCUIT_CIPHER,keys,iv,0))) {
  113. log_fn(LOG_WARN,"Cipher initialization failed (n).");
  114. return -1;
  115. }
  116. if (!(circ->p_crypto =
  117. crypto_create_init_cipher(CIRCUIT_CIPHER,keys+16,iv,1))) {
  118. log_fn(LOG_WARN,"Cipher initialization failed (p).");
  119. return -1;
  120. }
  121. connection_or_write_cell_to_buf(&cell, circ->p_conn);
  122. log_fn(LOG_DEBUG,"Finished sending 'created' cell.");
  123. return 0;
  124. }
  125. /* uses a weighted coin with weight cw to choose a route length */
  126. static int chooselen(double cw) {
  127. int len = 2;
  128. uint8_t coin;
  129. if ((cw < 0) || (cw >= 1)) /* invalid parameter */
  130. return -1;
  131. while(1)
  132. {
  133. if (CRYPTO_PSEUDO_RAND_INT(coin))
  134. return -1;
  135. if (coin > cw*255) /* don't extend */
  136. break;
  137. else
  138. len++;
  139. }
  140. return len;
  141. }
  142. /* returns an array of pointers to routent that define a new route through the OR network
  143. * int cw is the coin weight to use when choosing the route
  144. * order of routers is from last to first
  145. */
  146. static unsigned int *new_route(double cw, routerinfo_t **rarray, int rarray_len, int *routelen) {
  147. int i;
  148. int num_acceptable_routers;
  149. unsigned int *route;
  150. unsigned int oldchoice, choice;
  151. assert((cw >= 0) && (cw < 1) && (rarray) && (routelen) ); /* valid parameters */
  152. *routelen = chooselen(cw);
  153. if (*routelen == -1) {
  154. log_fn(LOG_WARN,"Choosing route length failed.");
  155. return NULL;
  156. }
  157. log_fn(LOG_DEBUG,"Chosen route length %d (%d routers available).",*routelen, rarray_len);
  158. num_acceptable_routers = count_acceptable_routers(rarray, rarray_len);
  159. if(num_acceptable_routers < 2) {
  160. log_fn(LOG_INFO,"Not enough acceptable routers. Failing.");
  161. return NULL;
  162. }
  163. if(num_acceptable_routers < *routelen) {
  164. log_fn(LOG_INFO,"Not enough routers: cutting routelen from %d to %d.",*routelen, num_acceptable_routers);
  165. *routelen = num_acceptable_routers;
  166. }
  167. if(*routelen < 1) {
  168. log_fn(LOG_WARN,"Didn't find any acceptable routers. Failing.");
  169. return NULL;
  170. }
  171. /* allocate memory for the new route */
  172. route = (unsigned int *)tor_malloc(*routelen * sizeof(unsigned int));
  173. oldchoice = rarray_len;
  174. for(i=0;i<*routelen;i++) {
  175. // log_fn(LOG_DEBUG,"Choosing hop %u.",i);
  176. if (CRYPTO_PSEUDO_RAND_INT(choice)) {
  177. free(route);
  178. return NULL;
  179. }
  180. choice = choice % rarray_len;
  181. log_fn(LOG_DEBUG,"Contemplating router %u.",choice);
  182. if(choice == oldchoice ||
  183. (oldchoice < rarray_len && !crypto_pk_cmp_keys(rarray[choice]->onion_pkey, rarray[oldchoice]->onion_pkey)) ||
  184. (options.OnionRouter && !connection_twin_get_by_addr_port(rarray[choice]->addr, rarray[choice]->or_port))) {
  185. /* Same router as last choice, or router twin,
  186. * or no routers with that key are connected to us.
  187. * Try again. */
  188. log_fn(LOG_DEBUG,"Picked a router %d that won't work as next hop.",choice);
  189. i--;
  190. continue;
  191. }
  192. log_fn(LOG_DEBUG,"Chosen router %u for hop %u.",choice,i);
  193. oldchoice = choice;
  194. route[i] = choice;
  195. }
  196. return route;
  197. }
  198. static int count_acceptable_routers(routerinfo_t **rarray, int rarray_len) {
  199. int i, j;
  200. int num=0;
  201. connection_t *conn;
  202. for(i=0;i<rarray_len;i++) {
  203. log_fn(LOG_DEBUG,"Contemplating whether router %d is a new option...",i);
  204. if(options.OnionRouter) {
  205. conn = connection_exact_get_by_addr_port(rarray[i]->addr, rarray[i]->or_port);
  206. if(!conn || conn->type != CONN_TYPE_OR || conn->state != OR_CONN_STATE_OPEN) {
  207. log_fn(LOG_DEBUG,"Nope, %d is not connected.",i);
  208. goto next_i_loop;
  209. }
  210. }
  211. for(j=0;j<i;j++) {
  212. if(!crypto_pk_cmp_keys(rarray[i]->onion_pkey, rarray[j]->onion_pkey)) {
  213. /* these guys are twins. so we've already counted him. */
  214. log_fn(LOG_DEBUG,"Nope, %d is a twin of %d.",i,j);
  215. goto next_i_loop;
  216. }
  217. }
  218. num++;
  219. log_fn(LOG_DEBUG,"I like %d. num_acceptable_routers now %d.",i, num);
  220. next_i_loop:
  221. ; /* our compiler may need an explicit statement after the label */
  222. }
  223. return num;
  224. }
  225. crypt_path_t *onion_generate_cpath(routerinfo_t **firsthop) {
  226. int routelen; /* length of the route */
  227. unsigned int *route; /* hops in the route as an array of indexes into rarray */
  228. crypt_path_t *cpath=NULL;
  229. directory_t *dir;
  230. routerinfo_t **rarray;
  231. int rarray_len;
  232. int i;
  233. crypt_path_t *hop;
  234. routerinfo_t *router;
  235. struct in_addr netaddr;
  236. router_get_directory(&dir);
  237. rarray = dir->routers;
  238. rarray_len = dir->n_routers;
  239. /* choose a route */
  240. route = new_route(options.CoinWeight, rarray, rarray_len, &routelen);
  241. if (!route) {
  242. log_fn(LOG_INFO,"Error choosing a route through the OR network.");
  243. return NULL;
  244. }
  245. log_fn(LOG_DEBUG,"Chosen a route of length %u: ",routelen);
  246. *firsthop = rarray[route[routelen-1]];
  247. assert(*firsthop); /* should always be defined */
  248. for(i=0; i<routelen; i++) {
  249. netaddr.s_addr = htonl((rarray[route[i]])->addr);
  250. log_fn(LOG_DEBUG,"%u : %s:%u, %u/%u",routelen-i,
  251. inet_ntoa(netaddr),
  252. (rarray[route[i]])->or_port,
  253. (int) (rarray[route[i]])->onion_pkey,
  254. crypto_pk_keysize((rarray[route[i]])->onion_pkey));
  255. }
  256. /* create the cpath layer by layer, starting at the last hop */
  257. for (i=0;i<routelen;i++) {
  258. router = rarray[route[i]];
  259. /* build up the crypt_path */
  260. hop = (crypt_path_t *)tor_malloc(sizeof(crypt_path_t));
  261. memset(hop, 0, sizeof(crypt_path_t));
  262. /* link hop into the cpath, at the front */
  263. hop->next = cpath;
  264. hop->prev = NULL;
  265. hop->state = CPATH_STATE_CLOSED;
  266. if(cpath) {
  267. cpath->prev = hop;
  268. }
  269. cpath = hop;
  270. hop->port = rarray[route[i]]->or_port;
  271. hop->addr = rarray[route[i]]->addr;
  272. hop->package_window = CIRCWINDOW_START;
  273. hop->deliver_window = CIRCWINDOW_START;
  274. log_fn(LOG_DEBUG,"Building hop %u of crypt path.",i+1);
  275. }
  276. /* now link cpath->prev to the end of cpath */
  277. for(hop=cpath; hop->next; hop=hop->next) ;
  278. hop->next = cpath;
  279. cpath->prev = hop;
  280. free(route);
  281. return cpath;
  282. }
  283. /*----------------------------------------------------------------------*/
  284. /* Given a router's public key, generates a 144-byte encrypted DH pubkey,
  285. * and stores it into onion_skin out. Stores the DH private key into
  286. * handshake_state_out for later completion of the handshake.
  287. *
  288. * The encrypted pubkey is formed as follows:
  289. * 16 bytes of symmetric key
  290. * 128 bytes of g^x for DH.
  291. * The first 128 bytes are RSA-encrypted with the server's public key,
  292. * and the last 16 are encrypted with the symmetric key.
  293. */
  294. int
  295. onion_skin_create(crypto_pk_env_t *dest_router_key,
  296. crypto_dh_env_t **handshake_state_out,
  297. char *onion_skin_out) /* Must be DH_ONIONSKIN_LEN bytes long */
  298. {
  299. char iv[16];
  300. char *pubkey = NULL;
  301. crypto_dh_env_t *dh = NULL;
  302. crypto_cipher_env_t *cipher = NULL;
  303. int dhbytes, pkbytes;
  304. *handshake_state_out = NULL;
  305. memset(onion_skin_out, 0, DH_ONIONSKIN_LEN);
  306. memset(iv, 0, 16);
  307. if (!(dh = crypto_dh_new()))
  308. goto err;
  309. dhbytes = crypto_dh_get_bytes(dh);
  310. pkbytes = crypto_pk_keysize(dest_router_key);
  311. assert(dhbytes+16 == DH_ONIONSKIN_LEN);
  312. pubkey = (char *)tor_malloc(dhbytes+16);
  313. if (crypto_rand(16, pubkey))
  314. goto err;
  315. /* XXXX You can't just run around RSA-encrypting any bitstream: if it's
  316. * greater than the RSA key, then OpenSSL will happily encrypt,
  317. * and later decrypt to the wrong value. So we set the first bit
  318. * of 'pubkey' to 0. This means that our symmetric key is really only
  319. * 127 bits long, but since it shouldn't be necessary to encrypt
  320. * DH public keys values in the first place, we should be fine.
  321. */
  322. pubkey[0] &= 0x7f;
  323. if (crypto_dh_get_public(dh, pubkey+16, dhbytes))
  324. goto err;
  325. #ifdef DEBUG_ONION_SKINS
  326. #define PA(a,n) \
  327. { int _i; for (_i = 0; _i<n; ++_i) printf("%02x ",((int)(a)[_i])&0xFF); }
  328. printf("Client: client g^x:");
  329. PA(pubkey+16,3);
  330. printf("...");
  331. PA(pubkey+141,3);
  332. puts("");
  333. printf("Client: client symkey:");
  334. PA(pubkey+0,16);
  335. puts("");
  336. #endif
  337. cipher = crypto_create_init_cipher(ONION_CIPHER, pubkey, iv, 1);
  338. if (!cipher)
  339. goto err;
  340. if (crypto_pk_public_encrypt(dest_router_key, pubkey, pkbytes,
  341. onion_skin_out, RSA_NO_PADDING)==-1)
  342. goto err;
  343. if (crypto_cipher_encrypt(cipher, pubkey+pkbytes, dhbytes+16-pkbytes,
  344. onion_skin_out+pkbytes))
  345. goto err;
  346. free(pubkey);
  347. crypto_free_cipher_env(cipher);
  348. *handshake_state_out = dh;
  349. return 0;
  350. err:
  351. tor_free(pubkey);
  352. if (dh) crypto_dh_free(dh);
  353. if (cipher) crypto_free_cipher_env(cipher);
  354. return -1;
  355. }
  356. /* Given an encrypted DH public key as generated by onion_skin_create,
  357. * and the private key for this onion router, generate the 128-byte DH
  358. * reply, and key_out_len bytes of key material, stored in key_out.
  359. */
  360. int
  361. onion_skin_server_handshake(char *onion_skin, /* DH_ONIONSKIN_LEN bytes long */
  362. crypto_pk_env_t *private_key,
  363. char *handshake_reply_out, /* DH_KEY_LEN bytes long */
  364. char *key_out,
  365. int key_out_len)
  366. {
  367. char buf[DH_ONIONSKIN_LEN];
  368. char iv[16];
  369. crypto_dh_env_t *dh = NULL;
  370. crypto_cipher_env_t *cipher = NULL;
  371. int pkbytes;
  372. int len;
  373. memset(iv, 0, 16);
  374. pkbytes = crypto_pk_keysize(private_key);
  375. if (crypto_pk_private_decrypt(private_key,
  376. onion_skin, pkbytes,
  377. buf, RSA_NO_PADDING) == -1)
  378. goto err;
  379. #ifdef DEBUG_ONION_SKINS
  380. printf("Server: client symkey:");
  381. PA(buf+0,16);
  382. puts("");
  383. #endif
  384. cipher = crypto_create_init_cipher(ONION_CIPHER, buf, iv, 0);
  385. if (crypto_cipher_decrypt(cipher, onion_skin+pkbytes, DH_ONIONSKIN_LEN-pkbytes,
  386. buf+pkbytes))
  387. goto err;
  388. #ifdef DEBUG_ONION_SKINS
  389. printf("Server: client g^x:");
  390. PA(buf+16,3);
  391. printf("...");
  392. PA(buf+141,3);
  393. puts("");
  394. #endif
  395. dh = crypto_dh_new();
  396. if (crypto_dh_get_public(dh, handshake_reply_out, DH_KEY_LEN))
  397. goto err;
  398. #ifdef DEBUG_ONION_SKINS
  399. printf("Server: server g^y:");
  400. PA(handshake_reply_out+0,3);
  401. printf("...");
  402. PA(handshake_reply_out+125,3);
  403. puts("");
  404. #endif
  405. len = crypto_dh_compute_secret(dh, buf+16, DH_KEY_LEN, key_out, key_out_len);
  406. if (len < 0)
  407. goto err;
  408. #ifdef DEBUG_ONION_SKINS
  409. printf("Server: key material:");
  410. PA(buf, DH_KEY_LEN);
  411. puts("");
  412. printf("Server: keys out:");
  413. PA(key_out, key_out_len);
  414. puts("");
  415. #endif
  416. crypto_free_cipher_env(cipher);
  417. crypto_dh_free(dh);
  418. return 0;
  419. err:
  420. if (cipher) crypto_free_cipher_env(cipher);
  421. if (dh) crypto_dh_free(dh);
  422. return -1;
  423. }
  424. /* Finish the client side of the DH handshake.
  425. * Given the 128 byte DH reply as generated by onion_skin_server_handshake
  426. * and the handshake state generated by onion_skin_create, generate
  427. * key_out_len bytes of shared key material and store them in key_out.
  428. *
  429. * After the invocation, call crypto_dh_free on handshake_state.
  430. */
  431. int
  432. onion_skin_client_handshake(crypto_dh_env_t *handshake_state,
  433. char *handshake_reply,/* Must be DH_KEY_LEN bytes long*/
  434. char *key_out,
  435. int key_out_len)
  436. {
  437. int len;
  438. assert(crypto_dh_get_bytes(handshake_state) == DH_KEY_LEN);
  439. #ifdef DEBUG_ONION_SKINS
  440. printf("Client: server g^y:");
  441. PA(handshake_reply+0,3);
  442. printf("...");
  443. PA(handshake_reply+125,3);
  444. puts("");
  445. #endif
  446. len = crypto_dh_compute_secret(handshake_state, handshake_reply, DH_KEY_LEN,
  447. key_out, key_out_len);
  448. if (len < 0)
  449. return -1;
  450. #ifdef DEBUG_ONION_SKINS
  451. printf("Client: keys out:");
  452. PA(key_out, key_out_len);
  453. puts("");
  454. #endif
  455. return 0;
  456. }
  457. /*
  458. Local Variables:
  459. mode:c
  460. indent-tabs-mode:nil
  461. c-basic-offset:2
  462. End:
  463. */