/* Copyright 2001 Matej Pfajfar, 2001-2004 Roger Dingledine. */ /* See LICENSE for licensing information */ /* $Id$ */ /** * \file circuitbuild.c * \brief The actual details of building circuits. **/ #include "or.h" extern or_options_t options; /* command-line and config-file options */ /********* START VARIABLES **********/ /** A global list of all circuits at this hop. */ extern circuit_t *global_circuitlist; /********* END VARIABLES ************/ static int circuit_deliver_create_cell(circuit_t *circ, char *payload); static cpath_build_state_t * onion_new_cpath_build_state(uint8_t purpose, const char *exit_digest); static int onion_extend_cpath(crypt_path_t **head_ptr, cpath_build_state_t *state, routerinfo_t **router_out); static int decide_circ_id_type(char *local_nick, char *remote_nick); static int count_acceptable_routers(smartlist_t *routers); /** Iterate over values of circ_id, starting from conn-\>next_circ_id, * and with the high bit specified by circ_id_type (see * decide_circ_id_type()), until we get a circ_id that is not in use * by any other circuit on that conn. * * Return it, or 0 if can't get a unique circ_id. */ static uint16_t get_unique_circ_id_by_conn(connection_t *conn, int circ_id_type) { uint16_t test_circ_id; int attempts=0; uint16_t high_bit; tor_assert(conn && conn->type == CONN_TYPE_OR); high_bit = (circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0; do { /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a * circID such that (high_bit|test_circ_id) is not already used. */ test_circ_id = conn->next_circ_id++; if (test_circ_id == 0 || test_circ_id >= 1<<15) { test_circ_id = 1; conn->next_circ_id = 2; } if(++attempts > 1<<15) { /* Make sure we don't loop forever if all circ_id's are used. This * matters because it's an external DoS vulnerability. */ log_fn(LOG_WARN,"No unused circ IDs. Failing."); return 0; } test_circ_id |= high_bit; } while(circuit_get_by_circ_id_conn(test_circ_id, conn)); return test_circ_id; } /** Log, at severity severity, the nicknames of each router in * circ's cpath. Also log the length of the cpath, and the intended * exit point. */ void circuit_log_path(int severity, circuit_t *circ) { char buf[1024]; char *s = buf; struct crypt_path_t *hop; char *states[] = {"closed", "waiting for keys", "open"}; routerinfo_t *router; tor_assert(CIRCUIT_IS_ORIGIN(circ) && circ->cpath); snprintf(s, sizeof(buf)-1, "circ (length %d, exit %s): ", circ->build_state->desired_path_len, circ->build_state->chosen_exit_name); hop=circ->cpath; do { s = buf + strlen(buf); router = router_get_by_digest(hop->identity_digest); if(router) { snprintf(s, sizeof(buf) - (s - buf), "%s(%s) ", router->nickname, states[hop->state]); } else { if(circ->purpose == CIRCUIT_PURPOSE_C_REND_JOINED) { snprintf(s, sizeof(buf) - (s - buf), "(rendjoin hop)"); } else { snprintf(s, sizeof(buf) - (s - buf), "UNKNOWN "); } } hop=hop->next; } while(hop!=circ->cpath); log_fn(severity,"%s",buf); } /** Tell the rep(utation)hist(ory) module about the status of the links * in circ. Hops that have become OPEN are marked as successfully * extended; the _first_ hop that isn't open (if any) is marked as * unable to extend. */ void circuit_rep_hist_note_result(circuit_t *circ) { struct crypt_path_t *hop; char *prev_digest = NULL; routerinfo_t *router; hop = circ->cpath; if(!hop) { /* XXX * if !hop, then we're not the beginning of this circuit. * for now, just forget about it. later, we should remember when * extends-through-us failed, too. */ return; } if (server_mode()) { prev_digest = router_get_my_routerinfo()->identity_digest; } do { router = router_get_by_digest(hop->identity_digest); if (router) { if (prev_digest) { if (hop->state == CPATH_STATE_OPEN) rep_hist_note_extend_succeeded(prev_digest, router->identity_digest); else { rep_hist_note_extend_failed(prev_digest, router->identity_digest); break; } } prev_digest = router->identity_digest; } else { prev_digest = NULL; } hop=hop->next; } while (hop!=circ->cpath); } /** A helper function for circuit_dump_by_conn() below. Log a bunch * of information about circuit circ. */ static void circuit_dump_details(int severity, circuit_t *circ, int poll_index, char *type, int this_circid, int other_circid) { struct crypt_path_t *hop; log(severity,"Conn %d has %s circuit: circID %d (other side %d), state %d (%s), born %d", poll_index, type, this_circid, other_circid, circ->state, circuit_state_to_string[circ->state], (int)circ->timestamp_created); if(CIRCUIT_IS_ORIGIN(circ)) { /* circ starts at this node */ if(circ->state == CIRCUIT_STATE_BUILDING) log(severity,"Building: desired len %d, planned exit node %s.", circ->build_state->desired_path_len, circ->build_state->chosen_exit_name); for(hop=circ->cpath;hop->next != circ->cpath; hop=hop->next) log(severity,"hop: state %d, addr 0x%.8x, port %d", hop->state, (unsigned int)hop->addr, (int)hop->port); } } /** Log, at severity severity, information about each circuit * that is connected to conn. */ void circuit_dump_by_conn(connection_t *conn, int severity) { circuit_t *circ; connection_t *tmpconn; for(circ=global_circuitlist;circ;circ = circ->next) { if(circ->p_conn == conn) circuit_dump_details(severity, circ, conn->poll_index, "App-ward", circ->p_circ_id, circ->n_circ_id); for(tmpconn=circ->p_streams; tmpconn; tmpconn=tmpconn->next_stream) { if(tmpconn == conn) { circuit_dump_details(severity, circ, conn->poll_index, "App-ward", circ->p_circ_id, circ->n_circ_id); } } if(circ->n_conn == conn) circuit_dump_details(severity, circ, conn->poll_index, "Exit-ward", circ->n_circ_id, circ->p_circ_id); for(tmpconn=circ->n_streams; tmpconn; tmpconn=tmpconn->next_stream) { if(tmpconn == conn) { circuit_dump_details(severity, circ, conn->poll_index, "Exit-ward", circ->n_circ_id, circ->p_circ_id); } } } } /** Build a new circuit for purpose. If exit_digest * is defined, then use that as your exit router, else choose a suitable * exit node. * * Also launch a connection to the first OR in the chosen path, if * it's not open already. */ circuit_t *circuit_establish_circuit(uint8_t purpose, const char *exit_digest) { routerinfo_t *firsthop; connection_t *n_conn; circuit_t *circ; circ = circuit_new(0, NULL); /* sets circ->p_circ_id and circ->p_conn */ circ->state = CIRCUIT_STATE_OR_WAIT; circ->build_state = onion_new_cpath_build_state(purpose, exit_digest); circ->purpose = purpose; if (! circ->build_state) { log_fn(LOG_INFO,"Generating cpath failed."); circuit_mark_for_close(circ); return NULL; } onion_extend_cpath(&circ->cpath, circ->build_state, &firsthop); if(!CIRCUIT_IS_ORIGIN(circ)) { log_fn(LOG_INFO,"Generating first cpath hop failed."); circuit_mark_for_close(circ); return NULL; } /* now see if we're already connected to the first OR in 'route' */ log_fn(LOG_DEBUG,"Looking for firsthop '%s:%u'", firsthop->address,firsthop->or_port); /* imprint the circuit with its future n_conn->id */ memcpy(circ->n_conn_id_digest, firsthop->identity_digest, DIGEST_LEN); n_conn = connection_get_by_identity_digest(firsthop->identity_digest, CONN_TYPE_OR); if(!n_conn || n_conn->state != OR_CONN_STATE_OPEN) { /* not currently connected */ circ->n_addr = firsthop->addr; circ->n_port = firsthop->or_port; if(!n_conn) { /* launch the connection */ n_conn = connection_or_connect(firsthop->addr, firsthop->or_port, firsthop->identity_digest); if(!n_conn) { /* connect failed, forget the whole thing */ log_fn(LOG_INFO,"connect to firsthop failed. Closing."); circuit_mark_for_close(circ); return NULL; } } log_fn(LOG_DEBUG,"connecting in progress (or finished). Good."); /* return success. The onion/circuit/etc will be taken care of automatically * (may already have been) whenever n_conn reaches OR_CONN_STATE_OPEN. */ return circ; } else { /* it (or a twin) is already open. use it. */ circ->n_addr = n_conn->addr; circ->n_port = n_conn->port; circ->n_conn = n_conn; log_fn(LOG_DEBUG,"Conn open. Delivering first onion skin."); if(circuit_send_next_onion_skin(circ) < 0) { log_fn(LOG_INFO,"circuit_send_next_onion_skin failed."); circuit_mark_for_close(circ); return NULL; } } return circ; } /** Find circuits that are waiting on or_conn to become open, * if any, and get them to send their create cells forward. */ void circuit_n_conn_done(connection_t *or_conn, int success) { circuit_t *circ; log_fn(LOG_DEBUG,"or_conn to %s, success=%d", or_conn->nickname, success); for(circ=global_circuitlist;circ;circ = circ->next) { if (circ->marked_for_close) continue; if(!circ->n_conn && circ->n_addr == or_conn->addr && circ->n_port == or_conn->port && !memcmp(or_conn->identity_digest, circ->n_conn_id_digest, DIGEST_LEN)) { tor_assert(circ->state == CIRCUIT_STATE_OR_WAIT); if(!success) { /* or_conn failed; close circ */ log_fn(LOG_INFO,"or_conn failed. Closing circ."); circuit_mark_for_close(circ); continue; } log_fn(LOG_DEBUG,"Found circ %d, sending create cell.", circ->n_circ_id); circ->n_conn = or_conn; memcpy(circ->n_conn_id_digest, or_conn->identity_digest, DIGEST_LEN); if(CIRCUIT_IS_ORIGIN(circ)) { if(circuit_send_next_onion_skin(circ) < 0) { log_fn(LOG_INFO,"send_next_onion_skin failed; circuit marked for closing."); circuit_mark_for_close(circ); continue; /* XXX could this be bad, eg if next_onion_skin failed because conn died? */ } } else { /* pull the create cell out of circ->onionskin, and send it */ if(circuit_deliver_create_cell(circ, circ->onionskin) < 0) { circuit_mark_for_close(circ); continue; } } } } } static int circuit_deliver_create_cell(circuit_t *circ, char *payload) { int circ_id_type; cell_t cell; tor_assert(circ && circ->n_conn && circ->n_conn->type == CONN_TYPE_OR); tor_assert(payload); /* XXXX008 How can we keep a good upgrade path here? We should * compare keys, not nicknames...but older servers will compare nicknames. * Should we check server version from the most recent directory? Hm. */ circ_id_type = decide_circ_id_type(options.Nickname, circ->n_conn->nickname); circ->n_circ_id = get_unique_circ_id_by_conn(circ->n_conn, circ_id_type); if(!circ->n_circ_id) { log_fn(LOG_WARN,"failed to get unique circID."); return -1; } log_fn(LOG_DEBUG,"Chosen circID %u.",circ->n_circ_id); memset(&cell, 0, sizeof(cell_t)); cell.command = CELL_CREATE; cell.circ_id = circ->n_circ_id; memcpy(cell.payload, payload, ONIONSKIN_CHALLENGE_LEN); connection_or_write_cell_to_buf(&cell, circ->n_conn); return 0; } extern int has_completed_circuit; /** This is the backbone function for building circuits. * * If circ's first hop is closed, then we need to build a create * cell and send it forward. * * Otherwise, we need to build a relay extend cell and send it * forward. * * Return -1 if we want to tear down circ, else return 0. */ int circuit_send_next_onion_skin(circuit_t *circ) { crypt_path_t *hop; routerinfo_t *router; int r; char payload[2+4+DIGEST_LEN+ONIONSKIN_CHALLENGE_LEN]; char *onionskin; int payload_len; tor_assert(circ && CIRCUIT_IS_ORIGIN(circ)); if(circ->cpath->state == CPATH_STATE_CLOSED) { log_fn(LOG_DEBUG,"First skin; sending create cell."); router = router_get_by_digest(circ->n_conn->identity_digest); if (!router) { log_fn(LOG_WARN,"Couldn't find routerinfo for %s", circ->n_conn->nickname); return -1; } if(onion_skin_create(router->onion_pkey, &(circ->cpath->handshake_state), payload) < 0) { log_fn(LOG_WARN,"onion_skin_create (first hop) failed."); return -1; } if(circuit_deliver_create_cell(circ, payload) < 0) return -1; circ->cpath->state = CPATH_STATE_AWAITING_KEYS; circ->state = CIRCUIT_STATE_BUILDING; log_fn(LOG_DEBUG,"first skin; finished sending create cell."); } else { tor_assert(circ->cpath->state == CPATH_STATE_OPEN); tor_assert(circ->state == CIRCUIT_STATE_BUILDING); log_fn(LOG_DEBUG,"starting to send subsequent skin."); r = onion_extend_cpath(&circ->cpath, circ->build_state, &router); if (r==1) { /* done building the circuit. whew. */ circ->state = CIRCUIT_STATE_OPEN; log_fn(LOG_INFO,"circuit built!"); circuit_reset_failure_count(); if(!has_completed_circuit) { has_completed_circuit=1; log_fn(LOG_NOTICE,"Tor has successfully opened a circuit. Looks like it's working."); } circuit_rep_hist_note_result(circ); circuit_has_opened(circ); /* do other actions as necessary */ return 0; } else if (r<0) { log_fn(LOG_INFO,"Unable to extend circuit path."); return -1; } hop = circ->cpath->prev; *(uint32_t*)payload = htonl(hop->addr); *(uint16_t*)(payload+4) = htons(hop->port); if (strncmp(router->platform, "Tor 0.0.7", 9)) { /* Before 0.0.8, we didn't support the long payload format. */ memcpy(payload+2+4, hop->identity_digest, DIGEST_LEN); onionskin = payload+2+4+DIGEST_LEN; payload_len = 2+4+DIGEST_LEN+ONIONSKIN_CHALLENGE_LEN; } else { onionskin = payload+2+4; payload_len = 2+4+ONIONSKIN_CHALLENGE_LEN; } if(onion_skin_create(router->onion_pkey, &(hop->handshake_state), onionskin) < 0) { log_fn(LOG_WARN,"onion_skin_create failed."); return -1; } log_fn(LOG_DEBUG,"Sending extend relay cell."); /* send it to hop->prev, because it will transfer * it to a create cell and then send to hop */ if(connection_edge_send_command(NULL, circ, RELAY_COMMAND_EXTEND, payload, payload_len, hop->prev) < 0) return 0; /* circuit is closed */ hop->state = CPATH_STATE_AWAITING_KEYS; } return 0; } /** Take the 'extend' cell, pull out addr/port plus the onion skin. Make * sure we're connected to the next hop, and pass it the onion skin in * a create cell. */ int circuit_extend(cell_t *cell, circuit_t *circ) { connection_t *n_conn; relay_header_t rh; int old_format; char *onionskin; char *id_digest=NULL; if(circ->n_conn) { log_fn(LOG_WARN,"n_conn already set. Bug/attack. Closing."); return -1; } relay_header_unpack(&rh, cell->payload); if (rh.length == 4+2+ONIONSKIN_CHALLENGE_LEN) { /* Once this format is no longer supported, nobody will use * connection_*_get_by_addr_port. */ old_format = 1; } else if (rh.length == 4+2+DIGEST_LEN+ONIONSKIN_CHALLENGE_LEN) { old_format = 0; } else { log_fn(LOG_WARN, "Wrong length on extend cell. Closing circuit."); return -1; } circ->n_addr = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE)); circ->n_port = ntohs(get_uint16(cell->payload+RELAY_HEADER_SIZE+4)); if (old_format) { n_conn = connection_twin_get_by_addr_port(circ->n_addr,circ->n_port); onionskin = cell->payload+RELAY_HEADER_SIZE+4+2; } else { id_digest = cell->payload+RELAY_HEADER_SIZE+4+2; n_conn = connection_get_by_identity_digest(id_digest, CONN_TYPE_OR); onionskin = cell->payload+RELAY_HEADER_SIZE+4+2+DIGEST_LEN; } if(!n_conn) { /* we should try to open a connection */ /* Note that this will close circuits where the onion has the same * router twice in a row in the path. I think that's ok. */ routerinfo_t *router; struct in_addr in; in.s_addr = htonl(circ->n_addr); log_fn(LOG_INFO,"Next router (%s:%d) not connected. Connecting.", inet_ntoa(in), circ->n_port); if (old_format) { router = router_get_by_addr_port(circ->n_addr, circ->n_port); if(!router) { log_fn(LOG_INFO,"Next hop is an unknown router. Closing."); return -1; } id_digest = router->identity_digest; } else { /* new format */ router = router_get_by_digest(id_digest); #if 0 if(router) { /* addr/port might be different */ circ->n_addr = router->addr; circ->n_port = router->or_port; } #endif } tor_assert(id_digest); memcpy(circ->onionskin, onionskin, ONIONSKIN_CHALLENGE_LEN); circ->state = CIRCUIT_STATE_OR_WAIT; /* imprint the circuit with its future n_conn->id */ memcpy(circ->n_conn_id_digest, id_digest, DIGEST_LEN); n_conn = connection_or_connect(circ->n_addr, circ->n_port, id_digest); if(!n_conn) { log_fn(LOG_INFO,"Launching n_conn failed. Closing."); return -1; } log_fn(LOG_DEBUG,"connecting in progress (or finished). Good."); /* return success. The onion/circuit/etc will be taken care of automatically * (may already have been) whenever n_conn reaches OR_CONN_STATE_OPEN. */ return 0; } circ->n_addr = n_conn->addr; /* these are different if we found a twin instead */ circ->n_port = n_conn->port; circ->n_conn = n_conn; memcpy(circ->n_conn_id_digest, n_conn->identity_digest, DIGEST_LEN); log_fn(LOG_DEBUG,"n_conn is %s:%u",n_conn->address,n_conn->port); if(circuit_deliver_create_cell(circ, onionskin) < 0) return -1; return 0; } /** Initialize cpath-\>{f|b}_{crypto|digest} from the key material in * key_data. key_data must contain CPATH_KEY_MATERIAL bytes, which are * used as follows: * - 20 to initialize f_digest * - 20 to initialize b_digest * - 16 to key f_crypto * - 16 to key b_crypto * * (If 'reverse' is true, then f_XX and b_XX are swapped.) */ int circuit_init_cpath_crypto(crypt_path_t *cpath, char *key_data, int reverse) { crypto_digest_env_t *tmp_digest; crypto_cipher_env_t *tmp_crypto; tor_assert(cpath && key_data); tor_assert(!(cpath->f_crypto || cpath->b_crypto || cpath->f_digest || cpath->b_digest)); log_fn(LOG_DEBUG,"hop init digest forward 0x%.8x, backward 0x%.8x.", (unsigned int)*(uint32_t*)key_data, (unsigned int)*(uint32_t*)(key_data+20)); cpath->f_digest = crypto_new_digest_env(); crypto_digest_add_bytes(cpath->f_digest, key_data, DIGEST_LEN); cpath->b_digest = crypto_new_digest_env(); crypto_digest_add_bytes(cpath->b_digest, key_data+DIGEST_LEN, DIGEST_LEN); log_fn(LOG_DEBUG,"hop init cipher forward 0x%.8x, backward 0x%.8x.", (unsigned int)*(uint32_t*)(key_data+40), (unsigned int)*(uint32_t*)(key_data+40+16)); if (!(cpath->f_crypto = crypto_create_init_cipher(key_data+(2*DIGEST_LEN),1))) { log(LOG_WARN,"forward cipher initialization failed."); return -1; } if (!(cpath->b_crypto = crypto_create_init_cipher(key_data+(2*DIGEST_LEN)+CIPHER_KEY_LEN,0))) { log(LOG_WARN,"backward cipher initialization failed."); return -1; } if (reverse) { tmp_digest = cpath->f_digest; cpath->f_digest = cpath->b_digest; cpath->b_digest = tmp_digest; tmp_crypto = cpath->f_crypto; cpath->f_crypto = cpath->b_crypto; cpath->b_crypto = tmp_crypto; } return 0; } /** A created or extended cell came back to us on the circuit, * and it included reply (the second DH key, plus KH). * * Calculate the appropriate keys and digests, make sure KH is * correct, and initialize this hop of the cpath. * * Return -1 if we want to mark circ for close, else return 0. */ int circuit_finish_handshake(circuit_t *circ, char *reply) { unsigned char keys[CPATH_KEY_MATERIAL_LEN]; crypt_path_t *hop; tor_assert(CIRCUIT_IS_ORIGIN(circ)); if(circ->cpath->state == CPATH_STATE_AWAITING_KEYS) hop = circ->cpath; else { for(hop=circ->cpath->next; hop != circ->cpath && hop->state == CPATH_STATE_OPEN; hop=hop->next) ; if(hop == circ->cpath) { /* got an extended when we're all done? */ log_fn(LOG_WARN,"got extended when circ already built? Closing."); return -1; } } tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS); if(onion_skin_client_handshake(hop->handshake_state, reply, keys, DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) { log_fn(LOG_WARN,"onion_skin_client_handshake failed."); return -1; } crypto_dh_free(hop->handshake_state); /* don't need it anymore */ hop->handshake_state = NULL; /* Remember hash of g^xy */ memcpy(hop->handshake_digest, reply+DH_KEY_LEN, DIGEST_LEN); if (circuit_init_cpath_crypto(hop, keys, 0)<0) { return -1; } hop->state = CPATH_STATE_OPEN; log_fn(LOG_INFO,"finished"); circuit_log_path(LOG_INFO,circ); return 0; } /** We received a relay truncated cell on circ. * * Since we don't ask for truncates currently, getting a truncated * means that a connection broke or an extend failed. For now, * just give up: for circ to close, and return 0. */ int circuit_truncated(circuit_t *circ, crypt_path_t *layer) { crypt_path_t *victim; connection_t *stream; tor_assert(circ && CIRCUIT_IS_ORIGIN(circ)); tor_assert(layer); /* XXX Since we don't ask for truncates currently, getting a truncated * means that a connection broke or an extend failed. For now, * just give up. */ circuit_mark_for_close(circ); return 0; while(layer->next != circ->cpath) { /* we need to clear out layer->next */ victim = layer->next; log_fn(LOG_DEBUG, "Killing a layer of the cpath."); for(stream = circ->p_streams; stream; stream=stream->next_stream) { if(stream->cpath_layer == victim) { log_fn(LOG_INFO, "Marking stream %d for close.", stream->stream_id); /* no need to send 'end' relay cells, * because the other side's already dead */ stream->has_sent_end = 1; connection_mark_for_close(stream); } } layer->next = victim->next; circuit_free_cpath_node(victim); } log_fn(LOG_INFO, "finished"); return 0; } /** 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. */ static 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; } /** 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; } /** Choose a length for a circuit of purpose purpose. * Default length is 3 + the number of endpoints that would give something * away. If the routerlist routers 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 purpose 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(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 * purpose and exit_nickname (if specified), and * return it. */ static cpath_build_state_t * onion_new_cpath_build_state(uint8_t purpose, const char *exit_digest) { 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_digest) { /* the circuit-builder pre-requested one */ memcpy(info->chosen_exit_digest, exit_digest, DIGEST_LEN); exit = router_get_by_digest(exit_digest); if (exit) { info->chosen_exit_name = tor_strdup(exit->nickname); } else { info->chosen_exit_name = tor_malloc(HEX_DIGEST_LEN+1); base16_encode(info->chosen_exit_name, HEX_DIGEST_LEN+1, exit_digest, DIGEST_LEN); } log_fn(LOG_INFO,"Using requested exit node '%s'", info->chosen_exit_name); } 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; } memcpy(info->chosen_exit_digest, exit->identity_digest, DIGEST_LEN); info->chosen_exit_name = tor_strdup(exit->nickname); } return info; } /** Return the number of routers in routers 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;inickname); if(r->is_running == 0) { log_fn(LOG_DEBUG,"Nope, the directory says %d is not running.",i); goto next_i_loop; } if(clique_mode()) { conn = connection_get_by_identity_digest(r->identity_digest, CONN_TYPE_OR); 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;jonion_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 sl 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 new_hop to the end of the doubly-linked-list head_ptr. * * 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 head_ptr, * based on state. Add the hop info to head_ptr, and return a * pointer to the chosen router in router_out. */ static 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_name); choice = router_get_by_digest(state->chosen_exit_digest); 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_name); 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_digest(state->chosen_exit_digest)); 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_digest(state->chosen_exit_digest)); 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_digest(state->chosen_exit_digest)); 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_digest(cpath->identity_digest); 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_name); 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; memcpy(hop->identity_digest, choice->identity_digest, DIGEST_LEN); 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; } /* Local Variables: mode:c indent-tabs-mode:nil c-basic-offset:2 End: */