diff options
Diffstat (limited to 'src/or/onion.c')
| -rw-r--r-- | src/or/onion.c | 524 |
1 files changed, 2 insertions, 522 deletions
diff --git a/src/or/onion.c b/src/or/onion.c index adaab58c4..8cf007354 100644 --- a/src/or/onion.c +++ b/src/or/onion.c @@ -4,42 +4,14 @@ /** * \file onion.c - * \brief Functions to handle onion parsing/creation and handle cpaths. + * \brief Functions to queue create cells, and handle onionskin + * parsing and creation. **/ #include "or.h" -/* prototypes for smartlist operations from routerlist.h - * They're here to prevent precedence issues with the .h files - */ -void router_add_running_routers_to_smartlist(smartlist_t *sl); -void add_nickname_list_to_smartlist(smartlist_t *sl, char *list); - extern or_options_t options; /**< command-line and config-file options */ -static int count_acceptable_routers(smartlist_t *routers); - -/** Decide whether the first bit of the circuit ID will be - * 0 or 1, to avoid conflicts where each side randomly chooses - * the same circuit ID. - * - * Return CIRC_ID_TYPE_LOWER if local_nick is NULL, or if - * local_nick is lexographically smaller than remote_nick. - * Else return CIRC_ID_TYPE_HIGHER. - */ -int decide_circ_id_type(char *local_nick, char *remote_nick) { - int result; - - tor_assert(remote_nick); - if(!local_nick) - return CIRC_ID_TYPE_LOWER; - result = strcasecmp(local_nick, remote_nick); - tor_assert(result); - if(result < 0) - return CIRC_ID_TYPE_LOWER; - return CIRC_ID_TYPE_HIGHER; -} - struct onion_queue_t { circuit_t *circ; struct onion_queue_t *next; @@ -140,498 +112,6 @@ void onion_pending_remove(circuit_t *circ) { free(victim); } -/** Given a response payload and keys, initialize, then send a created - * cell back. - */ -int onionskin_answer(circuit_t *circ, unsigned char *payload, unsigned char *keys) { - cell_t cell; - crypt_path_t *tmp_cpath; - - tmp_cpath = tor_malloc_zero(sizeof(crypt_path_t)); - - memset(&cell, 0, sizeof(cell_t)); - cell.command = CELL_CREATED; - cell.circ_id = circ->p_circ_id; - - circ->state = CIRCUIT_STATE_OPEN; - - log_fn(LOG_DEBUG,"Entering."); - - memcpy(cell.payload, payload, ONIONSKIN_REPLY_LEN); - - log_fn(LOG_INFO,"init digest forward 0x%.8x, backward 0x%.8x.", - (unsigned int)*(uint32_t*)(keys), (unsigned int)*(uint32_t*)(keys+20)); - if (circuit_init_cpath_crypto(tmp_cpath, keys, 0)<0) { - log_fn(LOG_WARN,"Circuit initialization failed"); - tor_free(tmp_cpath); - return -1; - } - circ->n_digest = tmp_cpath->f_digest; - circ->n_crypto = tmp_cpath->f_crypto; - circ->p_digest = tmp_cpath->b_digest; - circ->p_crypto = tmp_cpath->b_crypto; - tor_free(tmp_cpath); - - memcpy(circ->handshake_digest, cell.payload+DH_KEY_LEN, DIGEST_LEN); - - connection_or_write_cell_to_buf(&cell, circ->p_conn); - log_fn(LOG_DEBUG,"Finished sending 'created' cell."); - - return 0; -} - -extern int has_fetched_directory; /**< from main.c */ - -/** Choose a length for a circuit of purpose <b>purpose</b>. - * Default length is 3 + the number of endpoints that would give something - * away. If the routerlist <b>routers</b> doesn't have enough routers - * to handle the desired path length, return as large a path length as - * is feasible, except if it's less than 2, in which case return -1. - */ -static int new_route_len(double cw, uint8_t purpose, smartlist_t *routers) { - int num_acceptable_routers; - int routelen; - - tor_assert((cw >= 0) && (cw < 1) && routers); /* valid parameters */ - -#ifdef TOR_PERF - routelen = 2; -#else - if(purpose == CIRCUIT_PURPOSE_C_GENERAL) - routelen = 3; - else if(purpose == CIRCUIT_PURPOSE_C_INTRODUCING) - routelen = 4; - else if(purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND) - routelen = 3; - else if(purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO) - routelen = 3; - else if(purpose == CIRCUIT_PURPOSE_S_CONNECT_REND) - routelen = 4; - else { - log_fn(LOG_WARN,"Unhandled purpose %d", purpose); - return -1; - } -#endif -#if 0 - for(routelen = 3; ; routelen++) { /* 3, increment until coinflip says we're done */ - if (crypto_pseudo_rand_int(255) >= cw*255) /* don't extend */ - break; - } -#endif - log_fn(LOG_DEBUG,"Chosen route length %d (%d routers available).",routelen, - smartlist_len(routers)); - - num_acceptable_routers = count_acceptable_routers(routers); - - if(num_acceptable_routers < 2) { - log_fn(LOG_INFO,"Not enough acceptable routers (%d). Discarding this circuit.", - num_acceptable_routers); - return -1; - } - - if(num_acceptable_routers < routelen) { - log_fn(LOG_INFO,"Not enough routers: cutting routelen from %d to %d.", - routelen, num_acceptable_routers); - routelen = num_acceptable_routers; - } - - return routelen; -} - -/** Return a pointer to a suitable router to be the exit node for the - * general-purpose circuit we're about to build. - * - * Look through the connection array, and choose a router that maximizes - * the number of pending streams that can exit from this router. - * - * Return NULL if we can't find any suitable routers. - */ -static routerinfo_t *choose_good_exit_server_general(routerlist_t *dir) -{ - int *n_supported; - int i, j; - int n_pending_connections = 0; - connection_t **carray; - int n_connections; - int best_support = -1; - int n_best_support=0; - smartlist_t *sl, *preferredexits, *excludedexits; - routerinfo_t *router; - - get_connection_array(&carray, &n_connections); - - /* Count how many connections are waiting for a circuit to be built. - * We use this for log messages now, but in the future we may depend on it. - */ - for (i = 0; i < n_connections; ++i) { - if (carray[i]->type == CONN_TYPE_AP && - carray[i]->state == AP_CONN_STATE_CIRCUIT_WAIT && - !carray[i]->marked_for_close && - !circuit_stream_is_being_handled(carray[i])) - ++n_pending_connections; - } - log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending", - n_pending_connections); - /* Now we count, for each of the routers in the directory, how many - * of the pending connections could possibly exit from that - * router (n_supported[i]). (We can't be sure about cases where we - * don't know the IP address of the pending connection.) - */ - n_supported = tor_malloc(sizeof(int)*smartlist_len(dir->routers)); - for (i = 0; i < smartlist_len(dir->routers); ++i) { /* iterate over routers */ - router = smartlist_get(dir->routers, i); - if(router_is_me(router)) { - n_supported[i] = -1; - log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname); - /* XXX there's probably a reverse predecessor attack here, but - * it's slow. should we take this out? -RD - */ - continue; - } - if(!router->is_running) { - n_supported[i] = -1; - log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- directory says it's not running.", - router->nickname, i); - continue; /* skip routers that are known to be down */ - } - if(router_exit_policy_rejects_all(router)) { - n_supported[i] = -1; - log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.", - router->nickname, i); - continue; /* skip routers that reject all */ - } - n_supported[i] = 0; - for (j = 0; j < n_connections; ++j) { /* iterate over connections */ - if (carray[j]->type != CONN_TYPE_AP || - carray[j]->state != AP_CONN_STATE_CIRCUIT_WAIT || - carray[j]->marked_for_close || - circuit_stream_is_being_handled(carray[j])) - continue; /* Skip everything but APs in CIRCUIT_WAIT */ - switch (connection_ap_can_use_exit(carray[j], router)) - { - case ADDR_POLICY_REJECTED: - log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.", - router->nickname, i); - break; /* would be rejected; try next connection */ - case ADDR_POLICY_ACCEPTED: - case ADDR_POLICY_UNKNOWN: - ++n_supported[i]; - log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.", - router->nickname, i, n_supported[i]); - } - } /* End looping over connections. */ - if (n_supported[i] > best_support) { - /* If this router is better than previous ones, remember its index - * and goodness, and start counting how many routers are this good. */ - best_support = n_supported[i]; n_best_support=1; - log_fn(LOG_DEBUG,"%s is new best supported option so far.", - router->nickname); - } else if (n_supported[i] == best_support) { - /* If this router is _as good_ as the best one, just increment the - * count of equally good routers.*/ - ++n_best_support; - } - } - log_fn(LOG_INFO, "Found %d servers that might support %d/%d pending connections.", - n_best_support, best_support, n_pending_connections); - - preferredexits = smartlist_create(); - add_nickname_list_to_smartlist(preferredexits,options.ExitNodes); - - excludedexits = smartlist_create(); - add_nickname_list_to_smartlist(excludedexits,options.ExcludeNodes); - - sl = smartlist_create(); - - /* If any routers definitely support any pending connections, choose one - * at random. */ - if (best_support > 0) { - for (i = 0; i < smartlist_len(dir->routers); i++) - if (n_supported[i] == best_support) - smartlist_add(sl, smartlist_get(dir->routers, i)); - - smartlist_subtract(sl,excludedexits); - if (smartlist_overlap(sl,preferredexits)) - smartlist_intersect(sl,preferredexits); - router = smartlist_choose(sl); - } else { - /* Either there are no pending connections, or no routers even seem to - * possibly support any of them. Choose a router at random. */ - if (best_support == -1) { - log(LOG_WARN, "All routers are down or middleman -- choosing a doomed exit at random."); - } - for(i = 0; i < smartlist_len(dir->routers); i++) - if(n_supported[i] != -1) - smartlist_add(sl, smartlist_get(dir->routers, i)); - - smartlist_subtract(sl,excludedexits); - if (smartlist_overlap(sl,preferredexits)) - smartlist_intersect(sl,preferredexits); - router = smartlist_choose(sl); - } - - smartlist_free(preferredexits); - smartlist_free(excludedexits); - smartlist_free(sl); - tor_free(n_supported); - if(router) { - log_fn(LOG_INFO, "Chose exit server '%s'", router->nickname); - return router; - } - log_fn(LOG_WARN, "No exit routers seem to be running; can't choose an exit."); - return NULL; -} - -/** Return a pointer to a suitable router to be the exit node for the - * circuit of purpose <b>purpose</b> that we're about to build (or NULL - * if no router is suitable). - * - * For general-purpose circuits, pass it off to - * choose_good_exit_server_general() - * - * For client-side rendezvous circuits, choose a random node, weighted - * toward the preferences in 'options'. - */ -static routerinfo_t *choose_good_exit_server(uint8_t purpose, routerlist_t *dir) -{ - routerinfo_t *r; - switch(purpose) { - case CIRCUIT_PURPOSE_C_GENERAL: - return choose_good_exit_server_general(dir); - case CIRCUIT_PURPOSE_C_ESTABLISH_REND: - r = router_choose_random_node(dir, options.RendNodes, options.RendExcludeNodes, NULL); - return r; - default: - log_fn(LOG_WARN,"unhandled purpose %d", purpose); - tor_assert(0); - } - return NULL; /* never reached */ -} - -/** Allocate a cpath_build_state_t, populate it based on - * <b>purpose</b> and <b>exit_nickname</b> (if specified), and - * return it. - */ -cpath_build_state_t *onion_new_cpath_build_state(uint8_t purpose, - const char *exit_nickname) { - routerlist_t *rl; - int r; - cpath_build_state_t *info; - routerinfo_t *exit; - - router_get_routerlist(&rl); - r = new_route_len(options.PathlenCoinWeight, purpose, rl->routers); - if (r < 0) - return NULL; - info = tor_malloc_zero(sizeof(cpath_build_state_t)); - info->desired_path_len = r; - if(exit_nickname) { /* the circuit-builder pre-requested one */ - log_fn(LOG_INFO,"Using requested exit node '%s'", exit_nickname); - info->chosen_exit = tor_strdup(exit_nickname); - } else { /* we have to decide one */ - exit = choose_good_exit_server(purpose, rl); - if(!exit) { - log_fn(LOG_WARN,"failed to choose an exit server"); - tor_free(info); - return NULL; - } - info->chosen_exit = tor_strdup(exit->nickname); - } - return info; -} - -/** Return the number of routers in <b>routers</b> that are currently up - * and available for building circuits through. Count sets of twins only - * once. - */ -static int count_acceptable_routers(smartlist_t *routers) { - int i, j, n; - int num=0; - connection_t *conn; - routerinfo_t *r, *r2; - - n = smartlist_len(routers); - for(i=0;i<n;i++) { - r = smartlist_get(routers, i); - log_fn(LOG_DEBUG,"Contemplating whether router %d (%s) is a new option...", - i, r->nickname); - if(r->is_running == 0) { - log_fn(LOG_DEBUG,"Nope, the directory says %d is not running.",i); - goto next_i_loop; - } - if(options.ORPort) { - conn = connection_exact_get_by_addr_port(r->addr, r->or_port); - if(!conn || conn->type != CONN_TYPE_OR || conn->state != OR_CONN_STATE_OPEN) { - log_fn(LOG_DEBUG,"Nope, %d is not connected.",i); - goto next_i_loop; - } - } - for(j=0;j<i;j++) { - r2 = smartlist_get(routers, j); - if(!crypto_pk_cmp_keys(r->onion_pkey, r2->onion_pkey)) { - /* these guys are twins. so we've already counted him. */ - log_fn(LOG_DEBUG,"Nope, %d is a twin of %d.",i,j); - goto next_i_loop; - } - } - num++; - log_fn(LOG_DEBUG,"I like %d. num_acceptable_routers now %d.",i, num); - next_i_loop: - ; /* C requires an explicit statement after the label */ - } - - return num; -} - -/** Go through smartlist <b>sl</b> of routers, and remove all elements that - * have the same onion key as twin. - */ -static void remove_twins_from_smartlist(smartlist_t *sl, routerinfo_t *twin) { - int i; - routerinfo_t *r; - - if(twin == NULL) - return; - - for(i=0; i < smartlist_len(sl); i++) { - r = smartlist_get(sl,i); - if (!crypto_pk_cmp_keys(r->onion_pkey, twin->onion_pkey)) { - smartlist_del(sl,i--); - } - } -} - -/** Add <b>new_hop</b> to the end of the doubly-linked-list <b>head_ptr</b>. - * - * This function is used to extend cpath by another hop. - */ -void onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop) -{ - if (*head_ptr) { - new_hop->next = (*head_ptr); - new_hop->prev = (*head_ptr)->prev; - (*head_ptr)->prev->next = new_hop; - (*head_ptr)->prev = new_hop; - } else { - *head_ptr = new_hop; - new_hop->prev = new_hop->next = new_hop; - } -} - -/** Choose a suitable next hop in the cpath <b>head_ptr</b>, - * based on <b>state</b>. Add the hop info to head_ptr, and return a - * pointer to the chosen router in <b>router_out</b>. - */ -int onion_extend_cpath(crypt_path_t **head_ptr, cpath_build_state_t - *state, routerinfo_t **router_out) -{ - int cur_len; - crypt_path_t *cpath, *hop; - routerinfo_t *r; - routerinfo_t *choice; - int i; - smartlist_t *sl, *excludednodes; - - tor_assert(head_ptr); - tor_assert(router_out); - - if (!*head_ptr) { - cur_len = 0; - } else { - cur_len = 1; - for (cpath = *head_ptr; cpath->next != *head_ptr; cpath = cpath->next) { - ++cur_len; - } - } - if (cur_len >= state->desired_path_len) { - log_fn(LOG_DEBUG, "Path is complete: %d steps long", - state->desired_path_len); - return 1; - } - log_fn(LOG_DEBUG, "Path is %d long; we want %d", cur_len, - state->desired_path_len); - - excludednodes = smartlist_create(); - add_nickname_list_to_smartlist(excludednodes,options.ExcludeNodes); - - if(cur_len == state->desired_path_len - 1) { /* Picking last node */ - log_fn(LOG_DEBUG, "Contemplating last hop: choice already made: %s", - state->chosen_exit); - choice = router_get_by_nickname(state->chosen_exit); - smartlist_free(excludednodes); - if(!choice) { - log_fn(LOG_WARN,"Our chosen exit %s is no longer in the directory? Discarding this circuit.", - state->chosen_exit); - return -1; - } - } else if(cur_len == 0) { /* picking first node */ - /* try the nodes in EntryNodes first */ - sl = smartlist_create(); - add_nickname_list_to_smartlist(sl,options.EntryNodes); - /* XXX one day, consider picking chosen_exit knowing what's in EntryNodes */ - remove_twins_from_smartlist(sl,router_get_by_nickname(state->chosen_exit)); - remove_twins_from_smartlist(sl,router_get_my_routerinfo()); - smartlist_subtract(sl,excludednodes); - choice = smartlist_choose(sl); - smartlist_free(sl); - if(!choice) { - sl = smartlist_create(); - router_add_running_routers_to_smartlist(sl); - remove_twins_from_smartlist(sl,router_get_by_nickname(state->chosen_exit)); - remove_twins_from_smartlist(sl,router_get_my_routerinfo()); - smartlist_subtract(sl,excludednodes); - choice = smartlist_choose(sl); - smartlist_free(sl); - } - smartlist_free(excludednodes); - if(!choice) { - log_fn(LOG_WARN,"No acceptable routers while picking entry node. Discarding this circuit."); - return -1; - } - } else { - log_fn(LOG_DEBUG, "Contemplating intermediate hop: random choice."); - sl = smartlist_create(); - router_add_running_routers_to_smartlist(sl); - remove_twins_from_smartlist(sl,router_get_by_nickname(state->chosen_exit)); - remove_twins_from_smartlist(sl,router_get_my_routerinfo()); - for (i = 0, cpath = *head_ptr; i < cur_len; ++i, cpath=cpath->next) { - r = router_get_by_addr_port(cpath->addr, cpath->port); - tor_assert(r); - remove_twins_from_smartlist(sl,r); - } - smartlist_subtract(sl,excludednodes); - choice = smartlist_choose(sl); - smartlist_free(sl); - smartlist_free(excludednodes); - if(!choice) { - log_fn(LOG_WARN,"No acceptable routers while picking intermediate node. Discarding this circuit."); - return -1; - } - } - - log_fn(LOG_DEBUG,"Chose router %s for hop %d (exit is %s)", - choice->nickname, cur_len, state->chosen_exit); - - hop = tor_malloc_zero(sizeof(crypt_path_t)); - - /* link hop into the cpath, at the end. */ - onion_append_to_cpath(head_ptr, hop); - - hop->state = CPATH_STATE_CLOSED; - - hop->port = choice->or_port; - hop->addr = choice->addr; - - hop->package_window = CIRCWINDOW_START; - hop->deliver_window = CIRCWINDOW_START; - - log_fn(LOG_DEBUG, "Extended circuit path with %s for hop %d", - choice->nickname, cur_len); - - *router_out = choice; - return 0; -} - /*----------------------------------------------------------------------*/ /** Given a router's 128 byte public key, |