1 /* Copyright (c) 2001 Matej Pfajfar.
2 * Copyright (c) 2001-2004, Roger Dingledine.
3 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4 * Copyright (c) 2007-2017, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
9 * \brief Functions to queue create cells, wrap the various onionskin types,
10 * and parse and create the CREATE cell and its allies.
12 * This module has a few functions, all related to the CREATE/CREATED
13 * handshake that we use on links in order to create a circuit, and the
14 * related EXTEND/EXTENDED handshake that we use over circuits in order to
15 * extend them an additional hop.
17 * In this module, we provide a set of abstractions to create a uniform
18 * interface over the three circuit extension handshakes that Tor has used
19 * over the years (TAP, CREATE_FAST, and ntor). These handshakes are
20 * implemented in onion_tap.c, onion_fast.c, and onion_ntor.c respectively.
22 * All[*] of these handshakes follow a similar pattern: a client, knowing
23 * some key from the relay it wants to extend through, generates the
24 * first part of a handshake. A relay receives that handshake, and sends
25 * a reply. Once the client handles the reply, it knows that it is
26 * talking to the right relay, and it shares some freshly negotiated key
27 * material with that relay.
29 * We sometimes call the client's part of the handshake an "onionskin".
30 * We do this because historically, Onion Routing used a multi-layer
31 * structure called an "onion" to construct circuits. Each layer of the
32 * onion contained key material chosen by the client, the identity of
33 * the next relay in the circuit, and a smaller onion, encrypted with
34 * the key of the next relay. When we changed Tor to use a telescoping
35 * circuit extension design, it corresponded to sending each layer of the
36 * onion separately -- as a series of onionskins.
38 * Clients invoke these functions when creating or extending a circuit,
39 * from circuitbuild.c.
41 * Relays invoke these functions when they receive a CREATE or EXTEND
42 * cell in command.c or relay.c, in order to queue the pending request.
43 * They also invoke them from cpuworker.c, which handles dispatching
44 * onionskin requests to different worker threads.
48 * This module also handles:
50 * <li> Queueing incoming onionskins on the relay side before passing
51 * them to worker threads.
52 * <li>Expiring onionskins on the relay side if they have waited for
54 * <li>Packaging private keys on the server side in order to pass
55 * them to worker threads.
56 * <li>Encoding and decoding CREATE, CREATED, CREATE2, and CREATED2 cells.
57 * <li>Encoding and decodign EXTEND, EXTENDED, EXTEND2, and EXTENDED2
61 * [*] The CREATE_FAST handshake is weaker than described here; see
62 * onion_fast.c for more information.
66 #include "circuitbuild.h"
67 #include "circuitlist.h"
69 #include "cpuworker.h"
70 #include "networkstatus.h"
72 #include "onion_fast.h"
73 #include "onion_ntor.h"
74 #include "onion_tap.h"
80 #include "ed25519_cert.h"
82 /** Type for a linked list of circuits that are waiting for a free CPU worker
83 * to process a waiting onion handshake. */
84 typedef struct onion_queue_t
{
85 TOR_TAILQ_ENTRY(onion_queue_t
) next
;
87 uint16_t handshake_type
;
88 create_cell_t
*onionskin
;
92 /** 5 seconds on the onion queue til we just send back a destroy */
93 #define ONIONQUEUE_WAIT_CUTOFF 5
95 /** Array of queues of circuits waiting for CPU workers. An element is NULL
96 * if that queue is empty.*/
97 static TOR_TAILQ_HEAD(onion_queue_head_t
, onion_queue_t
)
98 ol_list
[MAX_ONION_HANDSHAKE_TYPE
+1] =
99 { TOR_TAILQ_HEAD_INITIALIZER(ol_list
[0]), /* tap */
100 TOR_TAILQ_HEAD_INITIALIZER(ol_list
[1]), /* fast */
101 TOR_TAILQ_HEAD_INITIALIZER(ol_list
[2]), /* ntor */
104 /** Number of entries of each type currently in each element of ol_list[]. */
105 static int ol_entries
[MAX_ONION_HANDSHAKE_TYPE
+1];
107 static int num_ntors_per_tap(void);
108 static void onion_queue_entry_remove(onion_queue_t
*victim
);
110 /* XXXX Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN.
112 * (By which I think I meant, "make sure that no
113 * X_ONIONSKIN_CHALLENGE/REPLY_LEN is greater than
114 * MAX_ONIONSKIN_CHALLENGE/REPLY_LEN." Also, make sure that we can pass
115 * over-large values via EXTEND2/EXTENDED2, for future-compatibility.*/
117 /** Return true iff we have room to queue another onionskin of type
120 have_room_for_onionskin(uint16_t type
)
122 const or_options_t
*options
= get_options();
124 uint64_t tap_usec
, ntor_usec
;
125 uint64_t ntor_during_tap_usec
, tap_during_ntor_usec
;
127 /* If we've got fewer than 50 entries, we always have room for one more. */
128 if (ol_entries
[type
] < 50)
130 num_cpus
= get_num_cpus(options
);
131 /* Compute how many microseconds we'd expect to need to clear all
132 * onionskins in various combinations of the queues. */
134 /* How long would it take to process all the TAP cells in the queue? */
135 tap_usec
= estimated_usec_for_onionskins(
136 ol_entries
[ONION_HANDSHAKE_TYPE_TAP
],
137 ONION_HANDSHAKE_TYPE_TAP
) / num_cpus
;
139 /* How long would it take to process all the NTor cells in the queue? */
140 ntor_usec
= estimated_usec_for_onionskins(
141 ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
],
142 ONION_HANDSHAKE_TYPE_NTOR
) / num_cpus
;
144 /* How long would it take to process the tap cells that we expect to
145 * process while draining the ntor queue? */
146 tap_during_ntor_usec
= estimated_usec_for_onionskins(
147 MIN(ol_entries
[ONION_HANDSHAKE_TYPE_TAP
],
148 ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
] / num_ntors_per_tap()),
149 ONION_HANDSHAKE_TYPE_TAP
) / num_cpus
;
151 /* How long would it take to process the ntor cells that we expect to
152 * process while draining the tap queue? */
153 ntor_during_tap_usec
= estimated_usec_for_onionskins(
154 MIN(ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
],
155 ol_entries
[ONION_HANDSHAKE_TYPE_TAP
] * num_ntors_per_tap()),
156 ONION_HANDSHAKE_TYPE_NTOR
) / num_cpus
;
158 /* See whether that exceeds MaxOnionQueueDelay. If so, we can't queue
160 if (type
== ONION_HANDSHAKE_TYPE_NTOR
&&
161 (ntor_usec
+ tap_during_ntor_usec
) / 1000 >
162 (uint64_t)options
->MaxOnionQueueDelay
)
165 if (type
== ONION_HANDSHAKE_TYPE_TAP
&&
166 (tap_usec
+ ntor_during_tap_usec
) / 1000 >
167 (uint64_t)options
->MaxOnionQueueDelay
)
170 /* If we support the ntor handshake, then don't let TAP handshakes use
171 * more than 2/3 of the space on the queue. */
172 if (type
== ONION_HANDSHAKE_TYPE_TAP
&&
173 tap_usec
/ 1000 > (uint64_t)options
->MaxOnionQueueDelay
* 2 / 3)
179 /** Add <b>circ</b> to the end of ol_list and return 0, except
180 * if ol_list is too long, in which case do nothing and return -1.
183 onion_pending_add(or_circuit_t
*circ
, create_cell_t
*onionskin
)
186 time_t now
= time(NULL
);
188 if (onionskin
->handshake_type
> MAX_ONION_HANDSHAKE_TYPE
) {
190 * We should have rejected this far before this point */
191 log_warn(LD_BUG
, "Handshake %d out of range! Dropping.",
192 onionskin
->handshake_type
);
197 tmp
= tor_malloc_zero(sizeof(onion_queue_t
));
199 tmp
->handshake_type
= onionskin
->handshake_type
;
200 tmp
->onionskin
= onionskin
;
201 tmp
->when_added
= now
;
203 if (!have_room_for_onionskin(onionskin
->handshake_type
)) {
204 #define WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL (60)
205 static ratelim_t last_warned
=
206 RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL
);
208 if (onionskin
->handshake_type
== ONION_HANDSHAKE_TYPE_NTOR
&&
209 (m
= rate_limit_log(&last_warned
, approx_time()))) {
211 "Your computer is too slow to handle this many circuit "
212 "creation requests! Please consider using the "
213 "MaxAdvertisedBandwidth config option or choosing a more "
214 "restricted exit policy.%s",m
);
221 ++ol_entries
[onionskin
->handshake_type
];
222 log_info(LD_OR
, "New create (%s). Queues now ntor=%d and tap=%d.",
223 onionskin
->handshake_type
== ONION_HANDSHAKE_TYPE_NTOR
? "ntor" : "tap",
224 ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
],
225 ol_entries
[ONION_HANDSHAKE_TYPE_TAP
]);
227 circ
->onionqueue_entry
= tmp
;
228 TOR_TAILQ_INSERT_TAIL(&ol_list
[onionskin
->handshake_type
], tmp
, next
);
230 /* cull elderly requests. */
232 onion_queue_t
*head
= TOR_TAILQ_FIRST(&ol_list
[onionskin
->handshake_type
]);
233 if (now
- head
->when_added
< (time_t)ONIONQUEUE_WAIT_CUTOFF
)
237 circ
->onionqueue_entry
= NULL
;
238 onion_queue_entry_remove(head
);
240 "Circuit create request is too old; canceling due to overload.");
241 if (! TO_CIRCUIT(circ
)->marked_for_close
) {
242 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_RESOURCELIMIT
);
248 /** Return a fairness parameter, to prefer processing NTOR style
249 * handshakes but still slowly drain the TAP queue so we don't starve
252 num_ntors_per_tap(void)
254 #define DEFAULT_NUM_NTORS_PER_TAP 10
255 #define MIN_NUM_NTORS_PER_TAP 1
256 #define MAX_NUM_NTORS_PER_TAP 100000
258 return networkstatus_get_param(NULL
, "NumNTorsPerTAP",
259 DEFAULT_NUM_NTORS_PER_TAP
,
260 MIN_NUM_NTORS_PER_TAP
,
261 MAX_NUM_NTORS_PER_TAP
);
264 /** Choose which onion queue we'll pull from next. If one is empty choose
265 * the other; if they both have elements, load balance across them but
268 decide_next_handshake_type(void)
270 /* The number of times we've chosen ntor lately when both were available. */
271 static int recently_chosen_ntors
= 0;
273 if (!ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
])
274 return ONION_HANDSHAKE_TYPE_TAP
; /* no ntors? try tap */
276 if (!ol_entries
[ONION_HANDSHAKE_TYPE_TAP
]) {
278 /* Nick wants us to prioritize new tap requests when there aren't
279 * any in the queue and we've processed k ntor cells since the last
280 * tap cell. This strategy is maybe a good idea, since it starves tap
281 * less in the case where tap is rare, or maybe a poor idea, since it
282 * makes the new tap cell unfairly jump in front of ntor cells that
283 * got here first. In any case this edge case will only become relevant
284 * once tap is rare. We should reevaluate whether we like this decision
285 * once tap gets more rare. */
286 if (ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
] &&
287 recently_chosen_ntors
<= num_ntors_per_tap())
288 ++recently_chosen_ntors
;
290 return ONION_HANDSHAKE_TYPE_NTOR
; /* no taps? try ntor */
293 /* They both have something queued. Pick ntor if we haven't done that
294 * too much lately. */
295 if (++recently_chosen_ntors
<= num_ntors_per_tap()) {
296 return ONION_HANDSHAKE_TYPE_NTOR
;
299 /* Else, it's time to let tap have its turn. */
300 recently_chosen_ntors
= 0;
301 return ONION_HANDSHAKE_TYPE_TAP
;
304 /** Remove the highest priority item from ol_list[] and return it, or
305 * return NULL if the lists are empty.
308 onion_next_task(create_cell_t
**onionskin_out
)
311 uint16_t handshake_to_choose
= decide_next_handshake_type();
312 onion_queue_t
*head
= TOR_TAILQ_FIRST(&ol_list
[handshake_to_choose
]);
315 return NULL
; /* no onions pending, we're done */
317 tor_assert(head
->circ
);
318 tor_assert(head
->handshake_type
<= MAX_ONION_HANDSHAKE_TYPE
);
319 // tor_assert(head->circ->p_chan); /* make sure it's still valid */
320 /* XXX I only commented out the above line to make the unit tests
321 * more manageable. That's probably not good long-term. -RD */
324 --ol_entries
[head
->handshake_type
];
325 log_info(LD_OR
, "Processing create (%s). Queues now ntor=%d and tap=%d.",
326 head
->handshake_type
== ONION_HANDSHAKE_TYPE_NTOR
? "ntor" : "tap",
327 ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
],
328 ol_entries
[ONION_HANDSHAKE_TYPE_TAP
]);
330 *onionskin_out
= head
->onionskin
;
331 head
->onionskin
= NULL
; /* prevent free. */
332 circ
->onionqueue_entry
= NULL
;
333 onion_queue_entry_remove(head
);
337 /** Return the number of <b>handshake_type</b>-style create requests pending.
340 onion_num_pending(uint16_t handshake_type
)
342 return ol_entries
[handshake_type
];
345 /** Go through ol_list, find the onion_queue_t element which points to
346 * circ, remove and free that element. Leave circ itself alone.
349 onion_pending_remove(or_circuit_t
*circ
)
351 onion_queue_t
*victim
;
356 victim
= circ
->onionqueue_entry
;
358 onion_queue_entry_remove(victim
);
360 cpuworker_cancel_circ_handshake(circ
);
363 /** Remove a queue entry <b>victim</b> from the queue, unlinking it from
364 * its circuit and freeing it and any structures it owns.*/
366 onion_queue_entry_remove(onion_queue_t
*victim
)
368 if (victim
->handshake_type
> MAX_ONION_HANDSHAKE_TYPE
) {
370 * We should have rejected this far before this point */
371 log_warn(LD_BUG
, "Handshake %d out of range! Dropping.",
372 victim
->handshake_type
);
378 TOR_TAILQ_REMOVE(&ol_list
[victim
->handshake_type
], victim
, next
);
381 victim
->circ
->onionqueue_entry
= NULL
;
383 if (victim
->onionskin
)
384 --ol_entries
[victim
->handshake_type
];
386 tor_free(victim
->onionskin
);
390 /** Remove all circuits from the pending list. Called from tor_free_all. */
392 clear_pending_onions(void)
394 onion_queue_t
*victim
, *next
;
396 for (i
=0; i
<=MAX_ONION_HANDSHAKE_TYPE
; i
++) {
397 for (victim
= TOR_TAILQ_FIRST(&ol_list
[i
]); victim
; victim
= next
) {
398 next
= TOR_TAILQ_NEXT(victim
,next
);
399 onion_queue_entry_remove(victim
);
401 tor_assert(TOR_TAILQ_EMPTY(&ol_list
[i
]));
403 memset(ol_entries
, 0, sizeof(ol_entries
));
406 /* ============================================================ */
408 /** Return a new server_onion_keys_t object with all of the keys
409 * and other info we might need to do onion handshakes. (We make a copy of
410 * our keys for each cpuworker to avoid race conditions with the main thread,
411 * and to avoid locking) */
412 server_onion_keys_t
*
413 server_onion_keys_new(void)
415 server_onion_keys_t
*keys
= tor_malloc_zero(sizeof(server_onion_keys_t
));
416 memcpy(keys
->my_identity
, router_get_my_id_digest(), DIGEST_LEN
);
417 dup_onion_keys(&keys
->onion_key
, &keys
->last_onion_key
);
418 keys
->curve25519_key_map
= construct_ntor_key_map();
419 keys
->junk_keypair
= tor_malloc_zero(sizeof(curve25519_keypair_t
));
420 curve25519_keypair_generate(keys
->junk_keypair
, 0);
424 /** Release all storage held in <b>keys</b>. */
426 server_onion_keys_free(server_onion_keys_t
*keys
)
431 crypto_pk_free(keys
->onion_key
);
432 crypto_pk_free(keys
->last_onion_key
);
433 ntor_key_map_free(keys
->curve25519_key_map
);
434 tor_free(keys
->junk_keypair
);
435 memwipe(keys
, 0, sizeof(server_onion_keys_t
));
439 /** Release whatever storage is held in <b>state</b>, depending on its
440 * type, and clear its pointer. */
442 onion_handshake_state_release(onion_handshake_state_t
*state
)
444 switch (state
->tag
) {
445 case ONION_HANDSHAKE_TYPE_TAP
:
446 crypto_dh_free(state
->u
.tap
);
449 case ONION_HANDSHAKE_TYPE_FAST
:
450 fast_handshake_state_free(state
->u
.fast
);
451 state
->u
.fast
= NULL
;
453 case ONION_HANDSHAKE_TYPE_NTOR
:
454 ntor_handshake_state_free(state
->u
.ntor
);
455 state
->u
.ntor
= NULL
;
459 * This state should not even exist. */
460 log_warn(LD_BUG
, "called with unknown handshake state type %d",
462 tor_fragile_assert();
467 /** Perform the first step of a circuit-creation handshake of type <b>type</b>
468 * (one of ONION_HANDSHAKE_TYPE_*): generate the initial "onion skin" in
469 * <b>onion_skin_out</b>, and store any state information in <b>state_out</b>.
470 * Return -1 on failure, and the length of the onionskin on acceptance.
473 onion_skin_create(int type
,
474 const extend_info_t
*node
,
475 onion_handshake_state_t
*state_out
,
476 uint8_t *onion_skin_out
)
481 case ONION_HANDSHAKE_TYPE_TAP
:
482 if (!node
->onion_key
)
485 if (onion_skin_TAP_create(node
->onion_key
,
487 (char*)onion_skin_out
) < 0)
490 r
= TAP_ONIONSKIN_CHALLENGE_LEN
;
492 case ONION_HANDSHAKE_TYPE_FAST
:
493 if (fast_onionskin_create(&state_out
->u
.fast
, onion_skin_out
) < 0)
498 case ONION_HANDSHAKE_TYPE_NTOR
:
499 if (!extend_info_supports_ntor(node
))
501 if (onion_skin_ntor_create((const uint8_t*)node
->identity_digest
,
502 &node
->curve25519_onion_key
,
507 r
= NTOR_ONIONSKIN_LEN
;
511 * We should never try to create an impossible handshake type. */
512 log_warn(LD_BUG
, "called with unknown handshake state type %d", type
);
513 tor_fragile_assert();
519 state_out
->tag
= (uint16_t) type
;
524 /** Perform the second (server-side) step of a circuit-creation handshake of
525 * type <b>type</b>, responding to the client request in <b>onion_skin</b>
526 * using the keys in <b>keys</b>. On success, write our response into
527 * <b>reply_out</b>, generate <b>keys_out_len</b> bytes worth of key material
528 * in <b>keys_out_len</b>, a hidden service nonce to <b>rend_nonce_out</b>,
529 * and return the length of the reply. On failure, return -1.
532 onion_skin_server_handshake(int type
,
533 const uint8_t *onion_skin
, size_t onionskin_len
,
534 const server_onion_keys_t
*keys
,
536 uint8_t *keys_out
, size_t keys_out_len
,
537 uint8_t *rend_nonce_out
)
542 case ONION_HANDSHAKE_TYPE_TAP
:
543 if (onionskin_len
!= TAP_ONIONSKIN_CHALLENGE_LEN
)
545 if (onion_skin_TAP_server_handshake((const char*)onion_skin
,
546 keys
->onion_key
, keys
->last_onion_key
,
548 (char*)keys_out
, keys_out_len
)<0)
550 r
= TAP_ONIONSKIN_REPLY_LEN
;
551 memcpy(rend_nonce_out
, reply_out
+DH_KEY_LEN
, DIGEST_LEN
);
553 case ONION_HANDSHAKE_TYPE_FAST
:
554 if (onionskin_len
!= CREATE_FAST_LEN
)
556 if (fast_server_handshake(onion_skin
, reply_out
, keys_out
, keys_out_len
)<0)
558 r
= CREATED_FAST_LEN
;
559 memcpy(rend_nonce_out
, reply_out
+DIGEST_LEN
, DIGEST_LEN
);
561 case ONION_HANDSHAKE_TYPE_NTOR
:
562 if (onionskin_len
< NTOR_ONIONSKIN_LEN
)
565 size_t keys_tmp_len
= keys_out_len
+ DIGEST_LEN
;
566 uint8_t *keys_tmp
= tor_malloc(keys_out_len
+ DIGEST_LEN
);
568 if (onion_skin_ntor_server_handshake(
569 onion_skin
, keys
->curve25519_key_map
,
572 reply_out
, keys_tmp
, keys_tmp_len
)<0) {
576 memcpy(keys_out
, keys_tmp
, keys_out_len
);
577 memcpy(rend_nonce_out
, keys_tmp
+keys_out_len
, DIGEST_LEN
);
578 memwipe(keys_tmp
, 0, keys_tmp_len
);
585 * We should have rejected this far before this point */
586 log_warn(LD_BUG
, "called with unknown handshake state type %d", type
);
587 tor_fragile_assert();
595 /** Perform the final (client-side) step of a circuit-creation handshake of
596 * type <b>type</b>, using our state in <b>handshake_state</b> and the
597 * server's response in <b>reply</b>. On success, generate <b>keys_out_len</b>
598 * bytes worth of key material in <b>keys_out_len</b>, set
599 * <b>rend_authenticator_out</b> to the "KH" field that can be used to
600 * establish introduction points at this hop, and return 0. On failure,
601 * return -1, and set *msg_out to an error message if this is worth
602 * complaining to the user about. */
604 onion_skin_client_handshake(int type
,
605 const onion_handshake_state_t
*handshake_state
,
606 const uint8_t *reply
, size_t reply_len
,
607 uint8_t *keys_out
, size_t keys_out_len
,
608 uint8_t *rend_authenticator_out
,
609 const char **msg_out
)
611 if (handshake_state
->tag
!= type
)
615 case ONION_HANDSHAKE_TYPE_TAP
:
616 if (reply_len
!= TAP_ONIONSKIN_REPLY_LEN
) {
618 *msg_out
= "TAP reply was not of the correct length.";
621 if (onion_skin_TAP_client_handshake(handshake_state
->u
.tap
,
623 (char *)keys_out
, keys_out_len
,
627 memcpy(rend_authenticator_out
, reply
+DH_KEY_LEN
, DIGEST_LEN
);
630 case ONION_HANDSHAKE_TYPE_FAST
:
631 if (reply_len
!= CREATED_FAST_LEN
) {
633 *msg_out
= "TAP reply was not of the correct length.";
636 if (fast_client_handshake(handshake_state
->u
.fast
, reply
,
637 keys_out
, keys_out_len
, msg_out
) < 0)
640 memcpy(rend_authenticator_out
, reply
+DIGEST_LEN
, DIGEST_LEN
);
642 case ONION_HANDSHAKE_TYPE_NTOR
:
643 if (reply_len
< NTOR_REPLY_LEN
) {
645 *msg_out
= "ntor reply was not of the correct length.";
649 size_t keys_tmp_len
= keys_out_len
+ DIGEST_LEN
;
650 uint8_t *keys_tmp
= tor_malloc(keys_tmp_len
);
651 if (onion_skin_ntor_client_handshake(handshake_state
->u
.ntor
,
653 keys_tmp
, keys_tmp_len
, msg_out
) < 0) {
657 memcpy(keys_out
, keys_tmp
, keys_out_len
);
658 memcpy(rend_authenticator_out
, keys_tmp
+ keys_out_len
, DIGEST_LEN
);
659 memwipe(keys_tmp
, 0, keys_tmp_len
);
664 log_warn(LD_BUG
, "called with unknown handshake state type %d", type
);
665 tor_fragile_assert();
670 /** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. If
671 * <b>unknown_ok</b> is true, allow cells with handshake types we don't
674 check_create_cell(const create_cell_t
*cell
, int unknown_ok
)
676 switch (cell
->cell_type
) {
678 if (cell
->handshake_type
!= ONION_HANDSHAKE_TYPE_TAP
&&
679 cell
->handshake_type
!= ONION_HANDSHAKE_TYPE_NTOR
)
682 case CELL_CREATE_FAST
:
683 if (cell
->handshake_type
!= ONION_HANDSHAKE_TYPE_FAST
)
692 switch (cell
->handshake_type
) {
693 case ONION_HANDSHAKE_TYPE_TAP
:
694 if (cell
->handshake_len
!= TAP_ONIONSKIN_CHALLENGE_LEN
)
697 case ONION_HANDSHAKE_TYPE_FAST
:
698 if (cell
->handshake_len
!= CREATE_FAST_LEN
)
701 case ONION_HANDSHAKE_TYPE_NTOR
:
702 if (cell
->handshake_len
!= NTOR_ONIONSKIN_LEN
)
713 /** Write the various parameters into the create cell. Separate from
714 * create_cell_parse() to make unit testing easier.
717 create_cell_init(create_cell_t
*cell_out
, uint8_t cell_type
,
718 uint16_t handshake_type
, uint16_t handshake_len
,
719 const uint8_t *onionskin
)
721 memset(cell_out
, 0, sizeof(*cell_out
));
723 cell_out
->cell_type
= cell_type
;
724 cell_out
->handshake_type
= handshake_type
;
725 cell_out
->handshake_len
= handshake_len
;
726 memcpy(cell_out
->onionskin
, onionskin
, handshake_len
);
729 /** Helper: parse the CREATE2 payload at <b>p</b>, which could be up to
730 * <b>p_len</b> bytes long, and use it to fill the fields of
731 * <b>cell_out</b>. Return 0 on success and -1 on failure.
733 * Note that part of the body of an EXTEND2 cell is a CREATE2 payload, so
734 * this function is also used for parsing those.
737 parse_create2_payload(create_cell_t
*cell_out
, const uint8_t *p
, size_t p_len
)
739 uint16_t handshake_type
, handshake_len
;
744 handshake_type
= ntohs(get_uint16(p
));
745 handshake_len
= ntohs(get_uint16(p
+2));
747 if (handshake_len
> CELL_PAYLOAD_SIZE
- 4 || handshake_len
> p_len
- 4)
749 if (handshake_type
== ONION_HANDSHAKE_TYPE_FAST
)
752 create_cell_init(cell_out
, CELL_CREATE2
, handshake_type
, handshake_len
,
757 /** Magic string which, in a CREATE or EXTEND cell, indicates that a seeming
758 * TAP payload is really an ntor payload. We'd do away with this if every
759 * relay supported EXTEND2, but we want to be able to extend from A to B with
760 * ntor even when A doesn't understand EXTEND2 and so can't generate a
763 #define NTOR_CREATE_MAGIC "ntorNTORntorNTOR"
765 /** Parse a CREATE, CREATE_FAST, or CREATE2 cell from <b>cell_in</b> into
766 * <b>cell_out</b>. Return 0 on success, -1 on failure. (We reject some
767 * syntactically valid CREATE2 cells that we can't generate or react to.) */
769 create_cell_parse(create_cell_t
*cell_out
, const cell_t
*cell_in
)
771 switch (cell_in
->command
) {
773 if (tor_memeq(cell_in
->payload
, NTOR_CREATE_MAGIC
, 16)) {
774 create_cell_init(cell_out
, CELL_CREATE
, ONION_HANDSHAKE_TYPE_NTOR
,
775 NTOR_ONIONSKIN_LEN
, cell_in
->payload
+16);
777 create_cell_init(cell_out
, CELL_CREATE
, ONION_HANDSHAKE_TYPE_TAP
,
778 TAP_ONIONSKIN_CHALLENGE_LEN
, cell_in
->payload
);
781 case CELL_CREATE_FAST
:
782 create_cell_init(cell_out
, CELL_CREATE_FAST
, ONION_HANDSHAKE_TYPE_FAST
,
783 CREATE_FAST_LEN
, cell_in
->payload
);
786 if (parse_create2_payload(cell_out
, cell_in
->payload
,
787 CELL_PAYLOAD_SIZE
) < 0)
794 return check_create_cell(cell_out
, 0);
797 /** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
799 check_created_cell(const created_cell_t
*cell
)
801 switch (cell
->cell_type
) {
803 if (cell
->handshake_len
!= TAP_ONIONSKIN_REPLY_LEN
&&
804 cell
->handshake_len
!= NTOR_REPLY_LEN
)
807 case CELL_CREATED_FAST
:
808 if (cell
->handshake_len
!= CREATED_FAST_LEN
)
812 if (cell
->handshake_len
> RELAY_PAYLOAD_SIZE
-2)
820 /** Parse a CREATED, CREATED_FAST, or CREATED2 cell from <b>cell_in</b> into
821 * <b>cell_out</b>. Return 0 on success, -1 on failure. */
823 created_cell_parse(created_cell_t
*cell_out
, const cell_t
*cell_in
)
825 memset(cell_out
, 0, sizeof(*cell_out
));
827 switch (cell_in
->command
) {
829 cell_out
->cell_type
= CELL_CREATED
;
830 cell_out
->handshake_len
= TAP_ONIONSKIN_REPLY_LEN
;
831 memcpy(cell_out
->reply
, cell_in
->payload
, TAP_ONIONSKIN_REPLY_LEN
);
833 case CELL_CREATED_FAST
:
834 cell_out
->cell_type
= CELL_CREATED_FAST
;
835 cell_out
->handshake_len
= CREATED_FAST_LEN
;
836 memcpy(cell_out
->reply
, cell_in
->payload
, CREATED_FAST_LEN
);
840 const uint8_t *p
= cell_in
->payload
;
841 cell_out
->cell_type
= CELL_CREATED2
;
842 cell_out
->handshake_len
= ntohs(get_uint16(p
));
843 if (cell_out
->handshake_len
> CELL_PAYLOAD_SIZE
- 2)
845 memcpy(cell_out
->reply
, p
+2, cell_out
->handshake_len
);
850 return check_created_cell(cell_out
);
853 /** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
855 check_extend_cell(const extend_cell_t
*cell
)
857 if (tor_digest_is_zero((const char*)cell
->node_id
))
859 /* We don't currently allow EXTEND2 cells without an IPv4 address */
860 if (tor_addr_family(&cell
->orport_ipv4
.addr
) == AF_UNSPEC
)
862 if (cell
->create_cell
.cell_type
== CELL_CREATE
) {
863 if (cell
->cell_type
!= RELAY_COMMAND_EXTEND
)
865 } else if (cell
->create_cell
.cell_type
== CELL_CREATE2
) {
866 if (cell
->cell_type
!= RELAY_COMMAND_EXTEND2
&&
867 cell
->cell_type
!= RELAY_COMMAND_EXTEND
)
870 /* In particular, no CREATE_FAST cells are allowed */
873 if (cell
->create_cell
.handshake_type
== ONION_HANDSHAKE_TYPE_FAST
)
876 return check_create_cell(&cell
->create_cell
, 1);
880 extend_cell_from_extend1_cell_body(extend_cell_t
*cell_out
,
881 const extend1_cell_body_t
*cell
)
883 tor_assert(cell_out
);
885 memset(cell_out
, 0, sizeof(*cell_out
));
886 tor_addr_make_unspec(&cell_out
->orport_ipv4
.addr
);
887 tor_addr_make_unspec(&cell_out
->orport_ipv6
.addr
);
889 cell_out
->cell_type
= RELAY_COMMAND_EXTEND
;
890 tor_addr_from_ipv4h(&cell_out
->orport_ipv4
.addr
, cell
->ipv4addr
);
891 cell_out
->orport_ipv4
.port
= cell
->port
;
892 if (tor_memeq(cell
->onionskin
, NTOR_CREATE_MAGIC
, 16)) {
893 cell_out
->create_cell
.cell_type
= CELL_CREATE2
;
894 cell_out
->create_cell
.handshake_type
= ONION_HANDSHAKE_TYPE_NTOR
;
895 cell_out
->create_cell
.handshake_len
= NTOR_ONIONSKIN_LEN
;
896 memcpy(cell_out
->create_cell
.onionskin
, cell
->onionskin
+ 16,
899 cell_out
->create_cell
.cell_type
= CELL_CREATE
;
900 cell_out
->create_cell
.handshake_type
= ONION_HANDSHAKE_TYPE_TAP
;
901 cell_out
->create_cell
.handshake_len
= TAP_ONIONSKIN_CHALLENGE_LEN
;
902 memcpy(cell_out
->create_cell
.onionskin
, cell
->onionskin
,
903 TAP_ONIONSKIN_CHALLENGE_LEN
);
905 memcpy(cell_out
->node_id
, cell
->identity
, DIGEST_LEN
);
910 create_cell_from_create2_cell_body(create_cell_t
*cell_out
,
911 const create2_cell_body_t
*cell
)
913 tor_assert(cell_out
);
915 memset(cell_out
, 0, sizeof(create_cell_t
));
916 if (BUG(cell
->handshake_len
> sizeof(cell_out
->onionskin
))) {
917 /* This should be impossible because there just isn't enough room in the
918 * input cell to make the handshake_len this large and provide a
919 * handshake_data to match. */
923 cell_out
->cell_type
= CELL_CREATE2
;
924 cell_out
->handshake_type
= cell
->handshake_type
;
925 cell_out
->handshake_len
= cell
->handshake_len
;
926 memcpy(cell_out
->onionskin
,
927 create2_cell_body_getconstarray_handshake_data(cell
),
928 cell
->handshake_len
);
933 extend_cell_from_extend2_cell_body(extend_cell_t
*cell_out
,
934 const extend2_cell_body_t
*cell
)
936 tor_assert(cell_out
);
938 int found_ipv4
= 0, found_ipv6
= 0, found_rsa_id
= 0, found_ed_id
= 0;
939 memset(cell_out
, 0, sizeof(*cell_out
));
940 tor_addr_make_unspec(&cell_out
->orport_ipv4
.addr
);
941 tor_addr_make_unspec(&cell_out
->orport_ipv6
.addr
);
942 cell_out
->cell_type
= RELAY_COMMAND_EXTEND2
;
945 for (i
= 0; i
< cell
->n_spec
; ++i
) {
946 const link_specifier_t
*ls
= extend2_cell_body_getconst_ls(cell
, i
);
947 switch (ls
->ls_type
) {
952 tor_addr_from_ipv4h(&cell_out
->orport_ipv4
.addr
, ls
->un_ipv4_addr
);
953 cell_out
->orport_ipv4
.port
= ls
->un_ipv4_port
;
959 tor_addr_from_ipv6_bytes(&cell_out
->orport_ipv6
.addr
,
960 (const char *)ls
->un_ipv6_addr
);
961 cell_out
->orport_ipv6
.port
= ls
->un_ipv6_port
;
967 memcpy(cell_out
->node_id
, ls
->un_legacy_id
, 20);
973 memcpy(cell_out
->ed_pubkey
.pubkey
, ls
->un_ed25519_id
, 32);
976 /* Ignore this, whatever it is. */
981 if (!found_rsa_id
|| !found_ipv4
) /* These are mandatory */
984 return create_cell_from_create2_cell_body(&cell_out
->create_cell
,
988 /** Parse an EXTEND or EXTEND2 cell (according to <b>command</b>) from the
989 * <b>payload_length</b> bytes of <b>payload</b> into <b>cell_out</b>. Return
990 * 0 on success, -1 on failure. */
992 extend_cell_parse(extend_cell_t
*cell_out
, const uint8_t command
,
993 const uint8_t *payload
, size_t payload_length
)
996 tor_assert(cell_out
);
999 if (payload_length
> RELAY_PAYLOAD_SIZE
)
1003 case RELAY_COMMAND_EXTEND
:
1005 extend1_cell_body_t
*cell
= NULL
;
1006 if (extend1_cell_body_parse(&cell
, payload
, payload_length
)<0 ||
1009 extend1_cell_body_free(cell
);
1012 int r
= extend_cell_from_extend1_cell_body(cell_out
, cell
);
1013 extend1_cell_body_free(cell
);
1018 case RELAY_COMMAND_EXTEND2
:
1020 extend2_cell_body_t
*cell
= NULL
;
1021 if (extend2_cell_body_parse(&cell
, payload
, payload_length
) < 0 ||
1024 extend2_cell_body_free(cell
);
1027 int r
= extend_cell_from_extend2_cell_body(cell_out
, cell
);
1028 extend2_cell_body_free(cell
);
1037 return check_extend_cell(cell_out
);
1040 /** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
1042 check_extended_cell(const extended_cell_t
*cell
)
1045 if (cell
->created_cell
.cell_type
== CELL_CREATED
) {
1046 if (cell
->cell_type
!= RELAY_COMMAND_EXTENDED
)
1048 } else if (cell
->created_cell
.cell_type
== CELL_CREATED2
) {
1049 if (cell
->cell_type
!= RELAY_COMMAND_EXTENDED2
)
1055 return check_created_cell(&cell
->created_cell
);
1058 /** Parse an EXTENDED or EXTENDED2 cell (according to <b>command</b>) from the
1059 * <b>payload_length</b> bytes of <b>payload</b> into <b>cell_out</b>. Return
1060 * 0 on success, -1 on failure. */
1062 extended_cell_parse(extended_cell_t
*cell_out
,
1063 const uint8_t command
, const uint8_t *payload
,
1066 tor_assert(cell_out
);
1067 tor_assert(payload
);
1069 memset(cell_out
, 0, sizeof(*cell_out
));
1070 if (payload_len
> RELAY_PAYLOAD_SIZE
)
1074 case RELAY_COMMAND_EXTENDED
:
1075 if (payload_len
!= TAP_ONIONSKIN_REPLY_LEN
)
1077 cell_out
->cell_type
= RELAY_COMMAND_EXTENDED
;
1078 cell_out
->created_cell
.cell_type
= CELL_CREATED
;
1079 cell_out
->created_cell
.handshake_len
= TAP_ONIONSKIN_REPLY_LEN
;
1080 memcpy(cell_out
->created_cell
.reply
, payload
, TAP_ONIONSKIN_REPLY_LEN
);
1082 case RELAY_COMMAND_EXTENDED2
:
1084 cell_out
->cell_type
= RELAY_COMMAND_EXTENDED2
;
1085 cell_out
->created_cell
.cell_type
= CELL_CREATED2
;
1086 cell_out
->created_cell
.handshake_len
= ntohs(get_uint16(payload
));
1087 if (cell_out
->created_cell
.handshake_len
> RELAY_PAYLOAD_SIZE
- 2 ||
1088 cell_out
->created_cell
.handshake_len
> payload_len
- 2)
1090 memcpy(cell_out
->created_cell
.reply
, payload
+2,
1091 cell_out
->created_cell
.handshake_len
);
1098 return check_extended_cell(cell_out
);
1101 /** Fill <b>cell_out</b> with a correctly formatted version of the
1102 * CREATE{,_FAST,2} cell in <b>cell_in</b>. Return 0 on success, -1 on
1103 * failure. This is a cell we didn't originate if <b>relayed</b> is true. */
1105 create_cell_format_impl(cell_t
*cell_out
, const create_cell_t
*cell_in
,
1110 if (check_create_cell(cell_in
, relayed
) < 0)
1113 memset(cell_out
->payload
, 0, sizeof(cell_out
->payload
));
1114 cell_out
->command
= cell_in
->cell_type
;
1116 p
= cell_out
->payload
;
1117 space
= sizeof(cell_out
->payload
);
1119 switch (cell_in
->cell_type
) {
1121 if (cell_in
->handshake_type
== ONION_HANDSHAKE_TYPE_NTOR
) {
1122 memcpy(p
, NTOR_CREATE_MAGIC
, 16);
1127 case CELL_CREATE_FAST
:
1128 tor_assert(cell_in
->handshake_len
<= space
);
1129 memcpy(p
, cell_in
->onionskin
, cell_in
->handshake_len
);
1132 tor_assert(cell_in
->handshake_len
<= sizeof(cell_out
->payload
)-4);
1133 set_uint16(cell_out
->payload
, htons(cell_in
->handshake_type
));
1134 set_uint16(cell_out
->payload
+2, htons(cell_in
->handshake_len
));
1135 memcpy(cell_out
->payload
+ 4, cell_in
->onionskin
, cell_in
->handshake_len
);
1145 create_cell_format(cell_t
*cell_out
, const create_cell_t
*cell_in
)
1147 return create_cell_format_impl(cell_out
, cell_in
, 0);
1151 create_cell_format_relayed(cell_t
*cell_out
, const create_cell_t
*cell_in
)
1153 return create_cell_format_impl(cell_out
, cell_in
, 1);
1156 /** Fill <b>cell_out</b> with a correctly formatted version of the
1157 * CREATED{,_FAST,2} cell in <b>cell_in</b>. Return 0 on success, -1 on
1160 created_cell_format(cell_t
*cell_out
, const created_cell_t
*cell_in
)
1162 if (check_created_cell(cell_in
) < 0)
1165 memset(cell_out
->payload
, 0, sizeof(cell_out
->payload
));
1166 cell_out
->command
= cell_in
->cell_type
;
1168 switch (cell_in
->cell_type
) {
1170 case CELL_CREATED_FAST
:
1171 tor_assert(cell_in
->handshake_len
<= sizeof(cell_out
->payload
));
1172 memcpy(cell_out
->payload
, cell_in
->reply
, cell_in
->handshake_len
);
1175 tor_assert(cell_in
->handshake_len
<= sizeof(cell_out
->payload
)-2);
1176 set_uint16(cell_out
->payload
, htons(cell_in
->handshake_len
));
1177 memcpy(cell_out
->payload
+ 2, cell_in
->reply
, cell_in
->handshake_len
);
1185 /** Return true iff we are configured (by torrc or by the networkstatus
1186 * parameters) to use Ed25519 identities in our Extend2 cells. */
1188 should_include_ed25519_id_extend_cells(const networkstatus_t
*ns
,
1189 const or_options_t
*options
)
1191 if (options
->ExtendByEd25519ID
!= -1)
1192 return options
->ExtendByEd25519ID
; /* The user has an opinion. */
1194 return (int) networkstatus_get_param(ns
, "ExtendByEd25519ID",
1200 /** Format the EXTEND{,2} cell in <b>cell_in</b>, storing its relay payload in
1201 * <b>payload_out</b>, the number of bytes used in *<b>len_out</b>, and the
1202 * relay command in *<b>command_out</b>. The <b>payload_out</b> must have
1203 * RELAY_PAYLOAD_SIZE bytes available. Return 0 on success, -1 on failure. */
1205 extend_cell_format(uint8_t *command_out
, uint16_t *len_out
,
1206 uint8_t *payload_out
, const extend_cell_t
*cell_in
)
1209 if (check_extend_cell(cell_in
) < 0)
1214 memset(p
, 0, RELAY_PAYLOAD_SIZE
);
1216 switch (cell_in
->cell_type
) {
1217 case RELAY_COMMAND_EXTEND
:
1219 *command_out
= RELAY_COMMAND_EXTEND
;
1220 *len_out
= 6 + TAP_ONIONSKIN_CHALLENGE_LEN
+ DIGEST_LEN
;
1221 set_uint32(p
, tor_addr_to_ipv4n(&cell_in
->orport_ipv4
.addr
));
1222 set_uint16(p
+4, htons(cell_in
->orport_ipv4
.port
));
1223 if (cell_in
->create_cell
.handshake_type
== ONION_HANDSHAKE_TYPE_NTOR
) {
1224 memcpy(p
+6, NTOR_CREATE_MAGIC
, 16);
1225 memcpy(p
+22, cell_in
->create_cell
.onionskin
, NTOR_ONIONSKIN_LEN
);
1227 memcpy(p
+6, cell_in
->create_cell
.onionskin
,
1228 TAP_ONIONSKIN_CHALLENGE_LEN
);
1230 memcpy(p
+6+TAP_ONIONSKIN_CHALLENGE_LEN
, cell_in
->node_id
, DIGEST_LEN
);
1233 case RELAY_COMMAND_EXTEND2
:
1235 uint8_t n_specifiers
= 2;
1236 *command_out
= RELAY_COMMAND_EXTEND2
;
1237 extend2_cell_body_t
*cell
= extend2_cell_body_new();
1238 link_specifier_t
*ls
;
1240 /* IPv4 specifier first. */
1241 ls
= link_specifier_new();
1242 extend2_cell_body_add_ls(cell
, ls
);
1243 ls
->ls_type
= LS_IPV4
;
1245 ls
->un_ipv4_addr
= tor_addr_to_ipv4h(&cell_in
->orport_ipv4
.addr
);
1246 ls
->un_ipv4_port
= cell_in
->orport_ipv4
.port
;
1250 ls
= link_specifier_new();
1251 extend2_cell_body_add_ls(cell
, ls
);
1252 ls
->ls_type
= LS_LEGACY_ID
;
1253 ls
->ls_len
= DIGEST_LEN
;
1254 memcpy(ls
->un_legacy_id
, cell_in
->node_id
, DIGEST_LEN
);
1256 if (should_include_ed25519_id_extend_cells(NULL
, get_options()) &&
1257 !ed25519_public_key_is_zero(&cell_in
->ed_pubkey
)) {
1258 /* Then, maybe, the ed25519 id! */
1260 ls
= link_specifier_new();
1261 extend2_cell_body_add_ls(cell
, ls
);
1262 ls
->ls_type
= LS_ED25519_ID
;
1264 memcpy(ls
->un_ed25519_id
, cell_in
->ed_pubkey
.pubkey
, 32);
1266 cell
->n_spec
= n_specifiers
;
1268 /* Now, the handshake */
1269 cell
->create2
= create2_cell_body_new();
1270 cell
->create2
->handshake_type
= cell_in
->create_cell
.handshake_type
;
1271 cell
->create2
->handshake_len
= cell_in
->create_cell
.handshake_len
;
1272 create2_cell_body_setlen_handshake_data(cell
->create2
,
1273 cell_in
->create_cell
.handshake_len
);
1274 memcpy(create2_cell_body_getarray_handshake_data(cell
->create2
),
1275 cell_in
->create_cell
.onionskin
,
1276 cell_in
->create_cell
.handshake_len
);
1278 ssize_t len_encoded
= extend2_cell_body_encode(
1279 payload_out
, RELAY_PAYLOAD_SIZE
,
1281 extend2_cell_body_free(cell
);
1282 if (len_encoded
< 0 || len_encoded
> UINT16_MAX
)
1284 *len_out
= (uint16_t) len_encoded
;
1294 /** Format the EXTENDED{,2} cell in <b>cell_in</b>, storing its relay payload
1295 * in <b>payload_out</b>, the number of bytes used in *<b>len_out</b>, and the
1296 * relay command in *<b>command_out</b>. The <b>payload_out</b> must have
1297 * RELAY_PAYLOAD_SIZE bytes available. Return 0 on success, -1 on failure. */
1299 extended_cell_format(uint8_t *command_out
, uint16_t *len_out
,
1300 uint8_t *payload_out
, const extended_cell_t
*cell_in
)
1303 if (check_extended_cell(cell_in
) < 0)
1307 memset(p
, 0, RELAY_PAYLOAD_SIZE
);
1309 switch (cell_in
->cell_type
) {
1310 case RELAY_COMMAND_EXTENDED
:
1312 *command_out
= RELAY_COMMAND_EXTENDED
;
1313 *len_out
= TAP_ONIONSKIN_REPLY_LEN
;
1314 memcpy(payload_out
, cell_in
->created_cell
.reply
,
1315 TAP_ONIONSKIN_REPLY_LEN
);
1318 case RELAY_COMMAND_EXTENDED2
:
1320 *command_out
= RELAY_COMMAND_EXTENDED2
;
1321 *len_out
= 2 + cell_in
->created_cell
.handshake_len
;
1322 set_uint16(payload_out
, htons(cell_in
->created_cell
.handshake_len
));
1323 if (2+cell_in
->created_cell
.handshake_len
> RELAY_PAYLOAD_SIZE
)
1325 memcpy(payload_out
+2, cell_in
->created_cell
.reply
,
1326 cell_in
->created_cell
.handshake_len
);