Implements the details of building circuits (by chosing paths, constructing/sending create/extend cells, and so on). More...

#include "or.h"
#include "bridges.h"
#include "channel.h"
#include "circpathbias.h"
#include "circuitbuild.h"
#include "circuitlist.h"
#include "circuitstats.h"
#include "circuituse.h"
#include "command.h"
#include "config.h"
#include "confparse.h"
#include "connection.h"
#include "connection_edge.h"
#include "connection_or.h"
#include "control.h"
#include "crypto_rand.h"
#include "directory.h"
#include "entrynodes.h"
#include "hs_ntor.h"
#include "main.h"
#include "microdesc.h"
#include "networkstatus.h"
#include "nodelist.h"
#include "onion.h"
#include "onion_tap.h"
#include "onion_fast.h"
#include "policies.h"
#include "relay.h"
#include "relay_crypto.h"
#include "rendcommon.h"
#include "rephist.h"
#include "router.h"
#include "routerlist.h"
#include "routerparse.h"
#include "routerset.h"
#include "transports.h"

Include dependency graph for circuitbuild.c:

Macros
#define	CIRCUITBUILD_PRIVATE

#define	CIRCUITBUILD_PRIVATE

#define	MAX_CIRCID_ATTEMPTS 64

#define	MAX_SANE_RESTRICTED_NODES 20

Functions
STATIC int	onion_append_hop (crypt_path_t *head_ptr, extend_info_t choice)

STATIC circid_t	get_unique_circ_id_by_chan (channel_t *chan)

char *	circuit_list_path (origin_circuit_t *circ, int verbose)

char *	circuit_list_path_for_controller (origin_circuit_t *circ)

void	circuit_log_path (int severity, unsigned int domain, origin_circuit_t *circ)

origin_circuit_t *	origin_circuit_init (uint8_t purpose, int flags)

origin_circuit_t *	circuit_establish_circuit (uint8_t purpose, extend_info_t *exit_ei, int flags)

circuit_guard_state_t *	origin_circuit_get_guard_state (origin_circuit_t *circ)

int	circuit_handle_first_hop (origin_circuit_t *circ)

void	circuit_n_chan_done (channel_t *chan, int status, int close_origin_circuits)

int	inform_testing_reachability (void)

int	circuit_timeout_want_to_count_circ (const origin_circuit_t *circ)

int	circuit_send_next_onion_skin (origin_circuit_t *circ)

void	circuit_note_clock_jumped (int64_t seconds_elapsed, bool was_idle)

int	circuit_extend (cell_t cell, circuit_t circ)

int	circuit_init_cpath_crypto (crypt_path_t cpath, const char key_data, size_t key_data_len, int reverse, int is_hs_v3)

int	circuit_finish_handshake (origin_circuit_t circ, const created_cell_t reply)

int	circuit_truncated (origin_circuit_t circ, crypt_path_t layer, int reason)

int	onionskin_answer (or_circuit_t circ, const created_cell_t created_cell, const char keys, size_t keys_len, const uint8_t rend_circ_nonce)

int	route_len_for_purpose (uint8_t purpose, extend_info_t *exit_ei)

STATIC int	new_route_len (uint8_t purpose, extend_info_t exit_ei, smartlist_t nodes)

	MOCK_IMPL (int, circuit_all_predicted_ports_handled,(time_t now, int need_uptime, int need_capacity))

STATIC int	onion_pick_cpath_exit (origin_circuit_t circ, extend_info_t exit_ei, int is_hs_v3_rp_circuit)

int	circuit_append_new_exit (origin_circuit_t circ, extend_info_t exit_ei)

int	circuit_extend_to_new_exit (origin_circuit_t circ, extend_info_t exit_ei)

	MOCK_IMPL (STATIC int, count_acceptable_nodes,(smartlist_t *nodes))

void	onion_append_to_cpath (crypt_path_t *head_ptr, crypt_path_t new_hop)

const node_t *	choose_good_entry_server (uint8_t purpose, cpath_build_state_t state, circuit_guard_state_t *guard_state_out)

STATIC int	onion_extend_cpath (origin_circuit_t *circ)

extend_info_t *	extend_info_new (const char nickname, const char rsa_id_digest, const ed25519_public_key_t ed_id, crypto_pk_t onion_key, const curve25519_public_key_t ntor_key, const tor_addr_t addr, uint16_t port)

extend_info_t *	extend_info_from_node (const node_t *node, int for_direct_connect)

void	extend_info_free_ (extend_info_t *info)

extend_info_t *	extend_info_dup (extend_info_t *info)

const node_t *	build_state_get_exit_node (cpath_build_state_t *state)

const uint8_t *	build_state_get_exit_rsa_id (cpath_build_state_t *state)

const char *	build_state_get_exit_nickname (cpath_build_state_t *state)

int	extend_info_addr_is_allowed (const tor_addr_t *addr)

int	extend_info_supports_tap (const extend_info_t *ei)

int	extend_info_supports_ntor (const extend_info_t *ei)

int	circuit_can_use_tap (const origin_circuit_t *circ)

int	circuit_has_usable_onion_key (const origin_circuit_t *circ)

int	extend_info_has_preferred_onion_key (const extend_info_t *ei)

void	circuit_upgrade_circuits_from_guard_wait (void)

Detailed Description

Implements the details of building circuits (by chosing paths, constructing/sending create/extend cells, and so on).

On the client side, this module handles launching circuits. Circuit launches are srtarted from circuit_establish_circuit(), called from circuit_launch_by_extend_info()). To choose the path the circuit will take, onion_extend_cpath() calls into a maze of node selection functions.

Once the circuit is ready to be launched, the first hop is treated as a special case with circuit_handle_first_hop(), since it might need to open a channel. As the channel opens, and later as CREATED and RELAY_EXTENDED cells arrive, the client will invoke circuit_send_next_onion_skin() to send CREATE or RELAY_EXTEND cells.

On the server side, this module also handles the logic of responding to RELAY_EXTEND requests, using circuit_extend().

Function Documentation

◆ build_state_get_exit_nickname()

const char* build_state_get_exit_nickname ( cpath_build_state_t * state )

Return the nickname for the chosen exit router in state. If there is no chosen exit, or if we don't know the routerinfo_t for the chosen exit, return NULL.

◆ build_state_get_exit_node()

const node_t* build_state_get_exit_node ( cpath_build_state_t * state )

Return the node_t for the chosen exit router in state. If there is no chosen exit, or if we don't know the node_t for the chosen exit, return NULL.

◆ build_state_get_exit_rsa_id()

const uint8_t* build_state_get_exit_rsa_id ( cpath_build_state_t * state )

Return the RSA ID digest for the chosen exit router in state. If there is no chosen exit, return NULL.

Here is the caller graph for this function:

◆ choose_good_entry_server()

const node_t* choose_good_entry_server	(	uint8_t	purpose,
		cpath_build_state_t *	state,
		circuit_guard_state_t **	guard_state_out
	)

Pick a good entry server for the circuit to be built according to state. Don't reuse a chosen exit (if any), don't use this router (if we're an OR), and respect firewall settings; if we're configured to use entry guards, return one.

Set *guard_state_out to information about the guard that we're selecting, which we'll use later to remember whether the guard worked or not.

◆ circuit_append_new_exit()

int circuit_append_new_exit	(	origin_circuit_t *	circ,
		extend_info_t *	exit_ei
	)

Give circ a new exit destination to exit, and add a hop to the cpath reflecting this. Don't send the next extend cell – the caller will do this if it wants to.

◆ circuit_establish_circuit()

origin_circuit_t* circuit_establish_circuit	(	uint8_t	purpose,
		extend_info_t *	exit_ei,
		int	flags
	)

Build a new circuit for purpose. If exit 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.

Here is the call graph for this function:

◆ circuit_extend()

int circuit_extend	(	cell_t *	cell,
		circuit_t *	circ
	)

Take the 'extend' cell, pull out addr/port plus the onion skin and identity digest for the next hop. If we're already connected, pass the onion skin to the next hop using a create cell; otherwise launch a new OR connection, and circ will notice when the connection succeeds or fails.

Return -1 if we want to warn and tear down the circuit, else return 0.

◆ circuit_extend_to_new_exit()

int circuit_extend_to_new_exit	(	origin_circuit_t *	circ,
		extend_info_t *	exit_ei
	)

Take an open circ, and add a new hop at the end, based on info. Set its state back to CIRCUIT_STATE_BUILDING, and then send the next extend cell to begin connecting to that hop.

◆ circuit_finish_handshake()

int circuit_finish_handshake	(	origin_circuit_t *	circ,
		const created_cell_t *	reply
	)

A "created" cell reply came back to us on circuit circ. (The body of reply varies depending on what sort of handshake this is.)

Calculate the appropriate keys and digests, make sure KH is correct, and initialize this hop of the cpath.

Return - reason if we want to mark circ for close, else return 0.

◆ circuit_handle_first_hop()

int circuit_handle_first_hop ( origin_circuit_t * circ )

Start establishing the first hop of our circuit. Figure out what OR we should connect to, and if necessary start the connection to it. If we're already connected, then send the 'create' cell. Return 0 for ok, -reason if circ should be marked-for-close.

◆ circuit_init_cpath_crypto()

int circuit_init_cpath_crypto	(	crypt_path_t *	cpath,
		const char *	key_data,
		size_t	key_data_len,
		int	reverse,
		int	is_hs_v3
	)

Initialize cpath->{f|b}_{crypto|digest} from the key material in key_data.

If is_hs_v3 is set, this cpath will be used for next gen hidden service circuits and key_data must be at least HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN bytes in length.

If is_hs_v3 is not set, key_data must contain CPATH_KEY_MATERIAL_LEN 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.)

Return 0 if init was successful, else -1 if it failed.

◆ circuit_list_path()

char* circuit_list_path	(	origin_circuit_t *	circ,
		int	verbose
	)

If verbose is false, allocate and return a comma-separated list of the currently built elements of circ. If verbose is true, also list information about link status in a more verbose format using spaces.

Here is the caller graph for this function:

◆ circuit_list_path_for_controller()

char* circuit_list_path_for_controller ( origin_circuit_t * circ )

Allocate and return a comma-separated list of the currently built elements of circ, giving each as a verbose nickname.

◆ circuit_log_path()

void circuit_log_path	(	int	severity,
		unsigned int	domain,
		origin_circuit_t *	circ
	)

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.

Here is the call graph for this function:

◆ circuit_n_chan_done()

void circuit_n_chan_done	(	channel_t *	chan,
		int	status,
		int	close_origin_circuits
	)

Find any circuits that are waiting on or_conn to become open and get them to send their create cells forward.

Status is 1 if connect succeeded, or 0 if connect failed.

Close_origin_circuits is 1 if we should close all the origin circuits through this channel, or 0 otherwise. (This happens when we want to retry an older guard.)

◆ circuit_note_clock_jumped()

void circuit_note_clock_jumped	(	int64_t	seconds_elapsed,
		bool	was_idle
	)

Our clock just jumped by seconds_elapsed. If was_idle is true, then the monotonic time matches; otherwise it doesn't. Assume something has also gone wrong with our network: notify the user, and abandon all not-yet-used circuits.

Here is the call graph for this function:

◆ circuit_send_next_onion_skin()

int circuit_send_next_onion_skin ( origin_circuit_t * circ )

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, if circ's cpath still has any non-open hops, we need to build a relay extend cell and send it forward to the next non-open hop.

If all hops on the cpath are open, we're done building the circuit and we should do housekeeping for the newly opened circuit.

Return -reason if we want to tear down circ, else return 0.

◆ circuit_timeout_want_to_count_circ()

int circuit_timeout_want_to_count_circ ( const origin_circuit_t * circ )

Return true if circ is the type of circuit we want to count timeouts from.

In particular, we want to consider any circuit that plans to build at least 3 hops (but maybe more), but has 3 or fewer hops built so far.

We still want to consider circuits before 3 hops, because we need to decide if we should convert them to a measurement circuit in circuit_build_times_handle_completed_hop(), rather than letting slow circuits get killed right away.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ circuit_truncated()

int circuit_truncated	(	origin_circuit_t *	circ,
		crypt_path_t *	layer,
		int	reason
	)

We received a relay truncated cell on circ.

Since we don't send truncates currently, getting a truncated means that a connection broke or an extend failed. For now, just give up: force circ to close, and return 0.

◆ circuit_upgrade_circuits_from_guard_wait()

void circuit_upgrade_circuits_from_guard_wait ( void )

Find the circuits that are waiting to find out whether their guards are usable, and if any are ready to become usable, mark them open and try attaching streams as appropriate.

Here is the call graph for this function:

◆ extend_info_addr_is_allowed()

int extend_info_addr_is_allowed ( const tor_addr_t * addr )

Return true iff the given address can be used to extend to.

◆ extend_info_dup()

extend_info_t* extend_info_dup ( extend_info_t * info )

Allocate and return a new extend_info_t with the same contents as info.

◆ extend_info_free_()

void extend_info_free_ ( extend_info_t * info )

Release storage held by an extend_info_t struct.

◆ extend_info_from_node()

extend_info_t* extend_info_from_node	(	const node_t *	node,
		int	for_direct_connect
	)

Allocate and return a new extend_info that can be used to build a circuit to or through the node node. Use the primary address of the node (i.e. its IPv4 address) unless for_direct_connect is true, in which case the preferred address is used instead. May return NULL if there is not enough info about node to extend to it–for example, if the preferred routerinfo_t or microdesc_t is missing, or if for_direct_connect is true and none of the node's addresses is allowed by tor's firewall and IP version config.

Here is the call graph for this function:

◆ extend_info_new()

extend_info_t* extend_info_new	(	const char *	nickname,
		const char *	rsa_id_digest,
		const ed25519_public_key_t *	ed_id,
		crypto_pk_t *	onion_key,
		const curve25519_public_key_t *	ntor_key,
		const tor_addr_t *	addr,
		uint16_t	port
	)

Allocate a new extend_info object based on the various arguments.

◆ get_unique_circ_id_by_chan()

STATIC circid_t get_unique_circ_id_by_chan ( channel_t * chan )

Search for a value for circ_id that we can use on chan for an outbound circuit, 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.

◆ inform_testing_reachability()

int inform_testing_reachability ( void )

We've decided to start our reachability testing. If all is set, log this to the user. Return 1 if we did, or 0 if we chose not to log anything.

◆ MOCK_IMPL() [1/2]

MOCK_IMPL	(	int	,
		circuit_all_predicted_ports_handled	,
		(time_t now, int need_uptime, int need_capacity)
	)

Return 1 if we already have circuits present or on the way for all anticipated ports. Return 0 if we should make more.

If we're returning 0, set need_uptime and need_capacity to indicate any requirements that the unhandled ports have.

◆ MOCK_IMPL() [2/2]

MOCK_IMPL	(	STATIC	int,
		count_acceptable_nodes	,
		(smartlist_t *nodes)
	)

Return the number of routers in routers that are currently up and available for building circuits through.

(Note that this function may overcount or undercount, if we have descriptors that are not the type we would prefer to use for some particular router. See bug #25885.)

Here is the call graph for this function:

◆ new_route_len()

STATIC int new_route_len	(	uint8_t	purpose,
		extend_info_t *	exit_ei,
		smartlist_t *	nodes
	)

Choose a length for a circuit of purpose purpose and check if enough routers are available.

If the routerlist nodes doesn't have enough routers to handle the desired path length, return -1.

Here is the call graph for this function:

◆ onion_append_hop()

STATIC int onion_append_hop	(	crypt_path_t **	head_ptr,
		extend_info_t *	choice
	)

Create a new hop, annotate it with information about its corresponding router choice, and append it to the end of the cpath head_ptr.

◆ onion_append_to_cpath()

void onion_append_to_cpath	(	crypt_path_t **	head_ptr,
		crypt_path_t *	new_hop
	)

Add new_hop to the end of the doubly-linked-list head_ptr. This function is used to extend cpath by another hop.

◆ onion_extend_cpath()

STATIC int onion_extend_cpath ( origin_circuit_t * circ )

Choose a suitable next hop in the cpath head_ptr, based on state. Append the hop info to head_ptr.

Return 1 if the path is complete, 0 if we successfully added a hop, and -1 on error.

Here is the call graph for this function:

◆ onion_pick_cpath_exit()

STATIC int onion_pick_cpath_exit	(	origin_circuit_t *	circ,
		extend_info_t *	exit_ei,
		int	is_hs_v3_rp_circuit
	)

Decide a suitable length for circ's cpath, and pick an exit router (or use exit if provided). Store these in the cpath.

If is_hs_v3_rp_circuit is set, then this exit should be suitable to be used as an HS v3 rendezvous point.

Return 0 if ok, -1 if circuit should be closed.

Here is the caller graph for this function:

◆ onionskin_answer()

int onionskin_answer	(	or_circuit_t *	circ,
		const created_cell_t *	created_cell,
		const char *	keys,
		size_t	keys_len,
		const uint8_t *	rend_circ_nonce
	)

Given a response payload and keys, initialize, then send a created cell back.

◆ origin_circuit_get_guard_state()

circuit_guard_state_t* origin_circuit_get_guard_state ( origin_circuit_t * circ )

Return the guard state associated with circ, which may be NULL.

◆ origin_circuit_init()

origin_circuit_t* origin_circuit_init	(	uint8_t	purpose,
		int	flags
	)

Create and return a new origin circuit. Initialize its purpose and build-state based on our arguments. The flags argument is a bitfield of CIRCLAUNCH_* flags.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ route_len_for_purpose()

int route_len_for_purpose	(	uint8_t	purpose,
		extend_info_t *	exit_ei
	)

Helper for new_route_len(). Choose a circuit length for purpose purpose: DEFAULT_ROUTE_LEN (+ 1 if someone else chose the exit). If someone else chose the exit, they could be colluding with the exit, so add a randomly selected node to preserve anonymity.

Here, "exit node" sometimes means an OR acting as an internal endpoint, rather than as a relay to an external endpoint. This means there need to be at least DEFAULT_ROUTE_LEN routers between us and the internal endpoint to preserve the same anonymity properties that we would get when connecting to an external endpoint. These internal endpoints can include:

Connections to a directory of hidden services (CIRCUIT_PURPOSE_C_GENERAL)
A client connecting to an introduction point, which the hidden service picked (CIRCUIT_PURPOSE_C_INTRODUCING, via circuit_get_open_circ_or_launch() which rewrites it from CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT)
A hidden service connecting to a rendezvous point, which the client picked (CIRCUIT_PURPOSE_S_CONNECT_REND, via rend_service_receive_introduction() and rend_service_relaunch_rendezvous)

There are currently two situations where we picked the exit node ourselves, making DEFAULT_ROUTE_LEN a safe circuit length:

We are a hidden service connecting to an introduction point (CIRCUIT_PURPOSE_S_ESTABLISH_INTRO, via rend_service_launch_establish_intro())
We are a router testing its own reachabiity (CIRCUIT_PURPOSE_TESTING, via router_do_reachability_checks())

onion_pick_cpath_exit() bypasses us (by not calling new_route_len()) in the one-hop tunnel case, so we don't need to handle that.

Here is the call graph for this function:

Here is the caller graph for this function:

Macros

Functions

Detailed Description

Function Documentation

◆ build_state_get_exit_nickname()

◆ build_state_get_exit_node()

◆ build_state_get_exit_rsa_id()

◆ choose_good_entry_server()

◆ circuit_append_new_exit()

◆ circuit_establish_circuit()

◆ circuit_extend()

◆ circuit_extend_to_new_exit()

◆ circuit_finish_handshake()

◆ circuit_handle_first_hop()

◆ circuit_init_cpath_crypto()

◆ circuit_list_path()

◆ circuit_list_path_for_controller()

◆ circuit_log_path()

◆ circuit_n_chan_done()

◆ circuit_note_clock_jumped()

◆ circuit_send_next_onion_skin()

◆ circuit_timeout_want_to_count_circ()

◆ circuit_truncated()

◆ circuit_upgrade_circuits_from_guard_wait()

◆ extend_info_addr_is_allowed()

◆ extend_info_dup()

◆ extend_info_free_()

◆ extend_info_from_node()

◆ extend_info_new()

◆ get_unique_circ_id_by_chan()

◆ inform_testing_reachability()

◆ MOCK_IMPL() [1/2]

◆ MOCK_IMPL() [2/2]

◆ new_route_len()

◆ onion_append_hop()

◆ onion_append_to_cpath()

◆ onion_extend_cpath()

◆ onion_pick_cpath_exit()

◆ onionskin_answer()

◆ origin_circuit_get_guard_state()

◆ origin_circuit_init()

◆ route_len_for_purpose()