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-2016, 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.
14 #include "circuitlist.h"
16 #include "cpuworker.h"
17 #include "networkstatus.h"
19 #include "onion_fast.h"
20 #include "onion_ntor.h"
21 #include "onion_tap.h"
26 /** Type for a linked list of circuits that are waiting for a free CPU worker
27 * to process a waiting onion handshake. */
28 typedef struct onion_queue_t
{
29 TOR_TAILQ_ENTRY(onion_queue_t
) next
;
31 uint16_t handshake_type
;
32 create_cell_t
*onionskin
;
36 /** 5 seconds on the onion queue til we just send back a destroy */
37 #define ONIONQUEUE_WAIT_CUTOFF 5
39 /** Array of queues of circuits waiting for CPU workers. An element is NULL
40 * if that queue is empty.*/
41 static TOR_TAILQ_HEAD(onion_queue_head_t
, onion_queue_t
)
42 ol_list
[MAX_ONION_HANDSHAKE_TYPE
+1] =
43 { TOR_TAILQ_HEAD_INITIALIZER(ol_list
[0]), /* tap */
44 TOR_TAILQ_HEAD_INITIALIZER(ol_list
[1]), /* fast */
45 TOR_TAILQ_HEAD_INITIALIZER(ol_list
[2]), /* ntor */
48 /** Number of entries of each type currently in each element of ol_list[]. */
49 static int ol_entries
[MAX_ONION_HANDSHAKE_TYPE
+1];
51 static int num_ntors_per_tap(void);
52 static void onion_queue_entry_remove(onion_queue_t
*victim
);
54 /* XXXX Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN.
56 * (By which I think I meant, "make sure that no
57 * X_ONIONSKIN_CHALLENGE/REPLY_LEN is greater than
58 * MAX_ONIONSKIN_CHALLENGE/REPLY_LEN." Also, make sure that we can pass
59 * over-large values via EXTEND2/EXTENDED2, for future-compatibility.*/
61 /** Return true iff we have room to queue another onionskin of type
64 have_room_for_onionskin(uint16_t type
)
66 const or_options_t
*options
= get_options();
68 uint64_t tap_usec
, ntor_usec
;
69 uint64_t ntor_during_tap_usec
, tap_during_ntor_usec
;
71 /* If we've got fewer than 50 entries, we always have room for one more. */
72 if (ol_entries
[type
] < 50)
74 num_cpus
= get_num_cpus(options
);
75 /* Compute how many microseconds we'd expect to need to clear all
76 * onionskins in various combinations of the queues. */
78 /* How long would it take to process all the TAP cells in the queue? */
79 tap_usec
= estimated_usec_for_onionskins(
80 ol_entries
[ONION_HANDSHAKE_TYPE_TAP
],
81 ONION_HANDSHAKE_TYPE_TAP
) / num_cpus
;
83 /* How long would it take to process all the NTor cells in the queue? */
84 ntor_usec
= estimated_usec_for_onionskins(
85 ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
],
86 ONION_HANDSHAKE_TYPE_NTOR
) / num_cpus
;
88 /* How long would it take to process the tap cells that we expect to
89 * process while draining the ntor queue? */
90 tap_during_ntor_usec
= estimated_usec_for_onionskins(
91 MIN(ol_entries
[ONION_HANDSHAKE_TYPE_TAP
],
92 ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
] / num_ntors_per_tap()),
93 ONION_HANDSHAKE_TYPE_TAP
) / num_cpus
;
95 /* How long would it take to process the ntor cells that we expect to
96 * process while draining the tap queue? */
97 ntor_during_tap_usec
= estimated_usec_for_onionskins(
98 MIN(ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
],
99 ol_entries
[ONION_HANDSHAKE_TYPE_TAP
] * num_ntors_per_tap()),
100 ONION_HANDSHAKE_TYPE_NTOR
) / num_cpus
;
102 /* See whether that exceeds MaxOnionQueueDelay. If so, we can't queue
104 if (type
== ONION_HANDSHAKE_TYPE_NTOR
&&
105 (ntor_usec
+ tap_during_ntor_usec
) / 1000 >
106 (uint64_t)options
->MaxOnionQueueDelay
)
109 if (type
== ONION_HANDSHAKE_TYPE_TAP
&&
110 (tap_usec
+ ntor_during_tap_usec
) / 1000 >
111 (uint64_t)options
->MaxOnionQueueDelay
)
114 /* If we support the ntor handshake, then don't let TAP handshakes use
115 * more than 2/3 of the space on the queue. */
116 if (type
== ONION_HANDSHAKE_TYPE_TAP
&&
117 tap_usec
/ 1000 > (uint64_t)options
->MaxOnionQueueDelay
* 2 / 3)
123 /** Add <b>circ</b> to the end of ol_list and return 0, except
124 * if ol_list is too long, in which case do nothing and return -1.
127 onion_pending_add(or_circuit_t
*circ
, create_cell_t
*onionskin
)
130 time_t now
= time(NULL
);
132 if (onionskin
->handshake_type
> MAX_ONION_HANDSHAKE_TYPE
) {
133 log_warn(LD_BUG
, "Handshake %d out of range! Dropping.",
134 onionskin
->handshake_type
);
138 tmp
= tor_malloc_zero(sizeof(onion_queue_t
));
140 tmp
->handshake_type
= onionskin
->handshake_type
;
141 tmp
->onionskin
= onionskin
;
142 tmp
->when_added
= now
;
144 if (!have_room_for_onionskin(onionskin
->handshake_type
)) {
145 #define WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL (60)
146 static ratelim_t last_warned
=
147 RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL
);
149 if (onionskin
->handshake_type
== ONION_HANDSHAKE_TYPE_NTOR
&&
150 (m
= rate_limit_log(&last_warned
, approx_time()))) {
152 "Your computer is too slow to handle this many circuit "
153 "creation requests! Please consider using the "
154 "MaxAdvertisedBandwidth config option or choosing a more "
155 "restricted exit policy.%s",m
);
162 ++ol_entries
[onionskin
->handshake_type
];
163 log_info(LD_OR
, "New create (%s). Queues now ntor=%d and tap=%d.",
164 onionskin
->handshake_type
== ONION_HANDSHAKE_TYPE_NTOR
? "ntor" : "tap",
165 ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
],
166 ol_entries
[ONION_HANDSHAKE_TYPE_TAP
]);
168 circ
->onionqueue_entry
= tmp
;
169 TOR_TAILQ_INSERT_TAIL(&ol_list
[onionskin
->handshake_type
], tmp
, next
);
171 /* cull elderly requests. */
173 onion_queue_t
*head
= TOR_TAILQ_FIRST(&ol_list
[onionskin
->handshake_type
]);
174 if (now
- head
->when_added
< (time_t)ONIONQUEUE_WAIT_CUTOFF
)
178 circ
->onionqueue_entry
= NULL
;
179 onion_queue_entry_remove(head
);
181 "Circuit create request is too old; canceling due to overload.");
182 circuit_mark_for_close(TO_CIRCUIT(circ
), END_CIRC_REASON_RESOURCELIMIT
);
187 /** Return a fairness parameter, to prefer processing NTOR style
188 * handshakes but still slowly drain the TAP queue so we don't starve
191 num_ntors_per_tap(void)
193 #define DEFAULT_NUM_NTORS_PER_TAP 10
194 #define MIN_NUM_NTORS_PER_TAP 1
195 #define MAX_NUM_NTORS_PER_TAP 100000
197 return networkstatus_get_param(NULL
, "NumNTorsPerTAP",
198 DEFAULT_NUM_NTORS_PER_TAP
,
199 MIN_NUM_NTORS_PER_TAP
,
200 MAX_NUM_NTORS_PER_TAP
);
203 /** Choose which onion queue we'll pull from next. If one is empty choose
204 * the other; if they both have elements, load balance across them but
207 decide_next_handshake_type(void)
209 /* The number of times we've chosen ntor lately when both were available. */
210 static int recently_chosen_ntors
= 0;
212 if (!ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
])
213 return ONION_HANDSHAKE_TYPE_TAP
; /* no ntors? try tap */
215 if (!ol_entries
[ONION_HANDSHAKE_TYPE_TAP
]) {
217 /* Nick wants us to prioritize new tap requests when there aren't
218 * any in the queue and we've processed k ntor cells since the last
219 * tap cell. This strategy is maybe a good idea, since it starves tap
220 * less in the case where tap is rare, or maybe a poor idea, since it
221 * makes the new tap cell unfairly jump in front of ntor cells that
222 * got here first. In any case this edge case will only become relevant
223 * once tap is rare. We should reevaluate whether we like this decision
224 * once tap gets more rare. */
225 if (ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
] &&
226 recently_chosen_ntors
<= num_ntors_per_tap())
227 ++recently_chosen_ntors
;
229 return ONION_HANDSHAKE_TYPE_NTOR
; /* no taps? try ntor */
232 /* They both have something queued. Pick ntor if we haven't done that
233 * too much lately. */
234 if (++recently_chosen_ntors
<= num_ntors_per_tap()) {
235 return ONION_HANDSHAKE_TYPE_NTOR
;
238 /* Else, it's time to let tap have its turn. */
239 recently_chosen_ntors
= 0;
240 return ONION_HANDSHAKE_TYPE_TAP
;
243 /** Remove the highest priority item from ol_list[] and return it, or
244 * return NULL if the lists are empty.
247 onion_next_task(create_cell_t
**onionskin_out
)
250 uint16_t handshake_to_choose
= decide_next_handshake_type();
251 onion_queue_t
*head
= TOR_TAILQ_FIRST(&ol_list
[handshake_to_choose
]);
254 return NULL
; /* no onions pending, we're done */
256 tor_assert(head
->circ
);
257 tor_assert(head
->handshake_type
<= MAX_ONION_HANDSHAKE_TYPE
);
258 // tor_assert(head->circ->p_chan); /* make sure it's still valid */
259 /* XXX I only commented out the above line to make the unit tests
260 * more manageable. That's probably not good long-term. -RD */
263 --ol_entries
[head
->handshake_type
];
264 log_info(LD_OR
, "Processing create (%s). Queues now ntor=%d and tap=%d.",
265 head
->handshake_type
== ONION_HANDSHAKE_TYPE_NTOR
? "ntor" : "tap",
266 ol_entries
[ONION_HANDSHAKE_TYPE_NTOR
],
267 ol_entries
[ONION_HANDSHAKE_TYPE_TAP
]);
269 *onionskin_out
= head
->onionskin
;
270 head
->onionskin
= NULL
; /* prevent free. */
271 circ
->onionqueue_entry
= NULL
;
272 onion_queue_entry_remove(head
);
276 /** Return the number of <b>handshake_type</b>-style create requests pending.
279 onion_num_pending(uint16_t handshake_type
)
281 return ol_entries
[handshake_type
];
284 /** Go through ol_list, find the onion_queue_t element which points to
285 * circ, remove and free that element. Leave circ itself alone.
288 onion_pending_remove(or_circuit_t
*circ
)
290 onion_queue_t
*victim
;
295 victim
= circ
->onionqueue_entry
;
297 onion_queue_entry_remove(victim
);
299 cpuworker_cancel_circ_handshake(circ
);
302 /** Remove a queue entry <b>victim</b> from the queue, unlinking it from
303 * its circuit and freeing it and any structures it owns.*/
305 onion_queue_entry_remove(onion_queue_t
*victim
)
307 if (victim
->handshake_type
> MAX_ONION_HANDSHAKE_TYPE
) {
308 log_warn(LD_BUG
, "Handshake %d out of range! Dropping.",
309 victim
->handshake_type
);
314 TOR_TAILQ_REMOVE(&ol_list
[victim
->handshake_type
], victim
, next
);
317 victim
->circ
->onionqueue_entry
= NULL
;
319 if (victim
->onionskin
)
320 --ol_entries
[victim
->handshake_type
];
322 tor_free(victim
->onionskin
);
326 /** Remove all circuits from the pending list. Called from tor_free_all. */
328 clear_pending_onions(void)
330 onion_queue_t
*victim
, *next
;
332 for (i
=0; i
<=MAX_ONION_HANDSHAKE_TYPE
; i
++) {
333 for (victim
= TOR_TAILQ_FIRST(&ol_list
[i
]); victim
; victim
= next
) {
334 next
= TOR_TAILQ_NEXT(victim
,next
);
335 onion_queue_entry_remove(victim
);
337 tor_assert(TOR_TAILQ_EMPTY(&ol_list
[i
]));
339 memset(ol_entries
, 0, sizeof(ol_entries
));
342 /* ============================================================ */
344 /** Return a new server_onion_keys_t object with all of the keys
345 * and other info we might need to do onion handshakes. (We make a copy of
346 * our keys for each cpuworker to avoid race conditions with the main thread,
347 * and to avoid locking) */
348 server_onion_keys_t
*
349 server_onion_keys_new(void)
351 server_onion_keys_t
*keys
= tor_malloc_zero(sizeof(server_onion_keys_t
));
352 memcpy(keys
->my_identity
, router_get_my_id_digest(), DIGEST_LEN
);
353 dup_onion_keys(&keys
->onion_key
, &keys
->last_onion_key
);
354 keys
->curve25519_key_map
= construct_ntor_key_map();
355 keys
->junk_keypair
= tor_malloc_zero(sizeof(curve25519_keypair_t
));
356 curve25519_keypair_generate(keys
->junk_keypair
, 0);
360 /** Release all storage held in <b>keys</b>. */
362 server_onion_keys_free(server_onion_keys_t
*keys
)
367 crypto_pk_free(keys
->onion_key
);
368 crypto_pk_free(keys
->last_onion_key
);
369 ntor_key_map_free(keys
->curve25519_key_map
);
370 tor_free(keys
->junk_keypair
);
371 memwipe(keys
, 0, sizeof(server_onion_keys_t
));
375 /** Release whatever storage is held in <b>state</b>, depending on its
376 * type, and clear its pointer. */
378 onion_handshake_state_release(onion_handshake_state_t
*state
)
380 switch (state
->tag
) {
381 case ONION_HANDSHAKE_TYPE_TAP
:
382 crypto_dh_free(state
->u
.tap
);
385 case ONION_HANDSHAKE_TYPE_FAST
:
386 fast_handshake_state_free(state
->u
.fast
);
387 state
->u
.fast
= NULL
;
389 case ONION_HANDSHAKE_TYPE_NTOR
:
390 ntor_handshake_state_free(state
->u
.ntor
);
391 state
->u
.ntor
= NULL
;
394 log_warn(LD_BUG
, "called with unknown handshake state type %d",
396 tor_fragile_assert();
400 /** Perform the first step of a circuit-creation handshake of type <b>type</b>
401 * (one of ONION_HANDSHAKE_TYPE_*): generate the initial "onion skin" in
402 * <b>onion_skin_out</b>, and store any state information in <b>state_out</b>.
403 * Return -1 on failure, and the length of the onionskin on acceptance.
406 onion_skin_create(int type
,
407 const extend_info_t
*node
,
408 onion_handshake_state_t
*state_out
,
409 uint8_t *onion_skin_out
)
414 case ONION_HANDSHAKE_TYPE_TAP
:
415 if (!node
->onion_key
)
418 if (onion_skin_TAP_create(node
->onion_key
,
420 (char*)onion_skin_out
) < 0)
423 r
= TAP_ONIONSKIN_CHALLENGE_LEN
;
425 case ONION_HANDSHAKE_TYPE_FAST
:
426 if (fast_onionskin_create(&state_out
->u
.fast
, onion_skin_out
) < 0)
431 case ONION_HANDSHAKE_TYPE_NTOR
:
432 if (tor_mem_is_zero((const char*)node
->curve25519_onion_key
.public_key
,
433 CURVE25519_PUBKEY_LEN
))
435 if (onion_skin_ntor_create((const uint8_t*)node
->identity_digest
,
436 &node
->curve25519_onion_key
,
441 r
= NTOR_ONIONSKIN_LEN
;
444 log_warn(LD_BUG
, "called with unknown handshake state type %d", type
);
445 tor_fragile_assert();
450 state_out
->tag
= (uint16_t) type
;
455 /** Perform the second (server-side) step of a circuit-creation handshake of
456 * type <b>type</b>, responding to the client request in <b>onion_skin</b>
457 * using the keys in <b>keys</b>. On success, write our response into
458 * <b>reply_out</b>, generate <b>keys_out_len</b> bytes worth of key material
459 * in <b>keys_out_len</b>, a hidden service nonce to <b>rend_nonce_out</b>,
460 * and return the length of the reply. On failure, return -1.
463 onion_skin_server_handshake(int type
,
464 const uint8_t *onion_skin
, size_t onionskin_len
,
465 const server_onion_keys_t
*keys
,
467 uint8_t *keys_out
, size_t keys_out_len
,
468 uint8_t *rend_nonce_out
)
473 case ONION_HANDSHAKE_TYPE_TAP
:
474 if (onionskin_len
!= TAP_ONIONSKIN_CHALLENGE_LEN
)
476 if (onion_skin_TAP_server_handshake((const char*)onion_skin
,
477 keys
->onion_key
, keys
->last_onion_key
,
479 (char*)keys_out
, keys_out_len
)<0)
481 r
= TAP_ONIONSKIN_REPLY_LEN
;
482 memcpy(rend_nonce_out
, reply_out
+DH_KEY_LEN
, DIGEST_LEN
);
484 case ONION_HANDSHAKE_TYPE_FAST
:
485 if (onionskin_len
!= CREATE_FAST_LEN
)
487 if (fast_server_handshake(onion_skin
, reply_out
, keys_out
, keys_out_len
)<0)
489 r
= CREATED_FAST_LEN
;
490 memcpy(rend_nonce_out
, reply_out
+DIGEST_LEN
, DIGEST_LEN
);
492 case ONION_HANDSHAKE_TYPE_NTOR
:
493 if (onionskin_len
< NTOR_ONIONSKIN_LEN
)
496 size_t keys_tmp_len
= keys_out_len
+ DIGEST_LEN
;
497 uint8_t *keys_tmp
= tor_malloc(keys_out_len
+ DIGEST_LEN
);
499 if (onion_skin_ntor_server_handshake(
500 onion_skin
, keys
->curve25519_key_map
,
503 reply_out
, keys_tmp
, keys_tmp_len
)<0) {
507 memcpy(keys_out
, keys_tmp
, keys_out_len
);
508 memcpy(rend_nonce_out
, keys_tmp
+keys_out_len
, DIGEST_LEN
);
509 memwipe(keys_tmp
, 0, keys_tmp_len
);
515 log_warn(LD_BUG
, "called with unknown handshake state type %d", type
);
516 tor_fragile_assert();
523 /** Perform the final (client-side) step of a circuit-creation handshake of
524 * type <b>type</b>, using our state in <b>handshake_state</b> and the
525 * server's response in <b>reply</b>. On success, generate <b>keys_out_len</b>
526 * bytes worth of key material in <b>keys_out_len</b>, set
527 * <b>rend_authenticator_out</b> to the "KH" field that can be used to
528 * establish introduction points at this hop, and return 0. On failure,
529 * return -1, and set *msg_out to an error message if this is worth
530 * complaining to the user about. */
532 onion_skin_client_handshake(int type
,
533 const onion_handshake_state_t
*handshake_state
,
534 const uint8_t *reply
, size_t reply_len
,
535 uint8_t *keys_out
, size_t keys_out_len
,
536 uint8_t *rend_authenticator_out
,
537 const char **msg_out
)
539 if (handshake_state
->tag
!= type
)
543 case ONION_HANDSHAKE_TYPE_TAP
:
544 if (reply_len
!= TAP_ONIONSKIN_REPLY_LEN
) {
546 *msg_out
= "TAP reply was not of the correct length.";
549 if (onion_skin_TAP_client_handshake(handshake_state
->u
.tap
,
551 (char *)keys_out
, keys_out_len
,
555 memcpy(rend_authenticator_out
, reply
+DH_KEY_LEN
, DIGEST_LEN
);
558 case ONION_HANDSHAKE_TYPE_FAST
:
559 if (reply_len
!= CREATED_FAST_LEN
) {
561 *msg_out
= "TAP reply was not of the correct length.";
564 if (fast_client_handshake(handshake_state
->u
.fast
, reply
,
565 keys_out
, keys_out_len
, msg_out
) < 0)
568 memcpy(rend_authenticator_out
, reply
+DIGEST_LEN
, DIGEST_LEN
);
570 case ONION_HANDSHAKE_TYPE_NTOR
:
571 if (reply_len
< NTOR_REPLY_LEN
) {
573 *msg_out
= "ntor reply was not of the correct length.";
577 size_t keys_tmp_len
= keys_out_len
+ DIGEST_LEN
;
578 uint8_t *keys_tmp
= tor_malloc(keys_tmp_len
);
579 if (onion_skin_ntor_client_handshake(handshake_state
->u
.ntor
,
581 keys_tmp
, keys_tmp_len
, msg_out
) < 0) {
585 memcpy(keys_out
, keys_tmp
, keys_out_len
);
586 memcpy(rend_authenticator_out
, keys_tmp
+ keys_out_len
, DIGEST_LEN
);
587 memwipe(keys_tmp
, 0, keys_tmp_len
);
592 log_warn(LD_BUG
, "called with unknown handshake state type %d", type
);
593 tor_fragile_assert();
598 /** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. If
599 * <b>unknown_ok</b> is true, allow cells with handshake types we don't
602 check_create_cell(const create_cell_t
*cell
, int unknown_ok
)
604 switch (cell
->cell_type
) {
606 if (cell
->handshake_type
!= ONION_HANDSHAKE_TYPE_TAP
&&
607 cell
->handshake_type
!= ONION_HANDSHAKE_TYPE_NTOR
)
610 case CELL_CREATE_FAST
:
611 if (cell
->handshake_type
!= ONION_HANDSHAKE_TYPE_FAST
)
620 switch (cell
->handshake_type
) {
621 case ONION_HANDSHAKE_TYPE_TAP
:
622 if (cell
->handshake_len
!= TAP_ONIONSKIN_CHALLENGE_LEN
)
625 case ONION_HANDSHAKE_TYPE_FAST
:
626 if (cell
->handshake_len
!= CREATE_FAST_LEN
)
629 case ONION_HANDSHAKE_TYPE_NTOR
:
630 if (cell
->handshake_len
!= NTOR_ONIONSKIN_LEN
)
641 /** Write the various parameters into the create cell. Separate from
642 * create_cell_parse() to make unit testing easier.
645 create_cell_init(create_cell_t
*cell_out
, uint8_t cell_type
,
646 uint16_t handshake_type
, uint16_t handshake_len
,
647 const uint8_t *onionskin
)
649 memset(cell_out
, 0, sizeof(*cell_out
));
651 cell_out
->cell_type
= cell_type
;
652 cell_out
->handshake_type
= handshake_type
;
653 cell_out
->handshake_len
= handshake_len
;
654 memcpy(cell_out
->onionskin
, onionskin
, handshake_len
);
657 /** Helper: parse the CREATE2 payload at <b>p</b>, which could be up to
658 * <b>p_len</b> bytes long, and use it to fill the fields of
659 * <b>cell_out</b>. Return 0 on success and -1 on failure.
661 * Note that part of the body of an EXTEND2 cell is a CREATE2 payload, so
662 * this function is also used for parsing those.
665 parse_create2_payload(create_cell_t
*cell_out
, const uint8_t *p
, size_t p_len
)
667 uint16_t handshake_type
, handshake_len
;
672 handshake_type
= ntohs(get_uint16(p
));
673 handshake_len
= ntohs(get_uint16(p
+2));
675 if (handshake_len
> CELL_PAYLOAD_SIZE
- 4 || handshake_len
> p_len
- 4)
677 if (handshake_type
== ONION_HANDSHAKE_TYPE_FAST
)
680 create_cell_init(cell_out
, CELL_CREATE2
, handshake_type
, handshake_len
,
685 /** Magic string which, in a CREATE or EXTEND cell, indicates that a seeming
686 * TAP payload is really an ntor payload. We'd do away with this if every
687 * relay supported EXTEND2, but we want to be able to extend from A to B with
688 * ntor even when A doesn't understand EXTEND2 and so can't generate a
691 #define NTOR_CREATE_MAGIC "ntorNTORntorNTOR"
693 /** Parse a CREATE, CREATE_FAST, or CREATE2 cell from <b>cell_in</b> into
694 * <b>cell_out</b>. Return 0 on success, -1 on failure. (We reject some
695 * syntactically valid CREATE2 cells that we can't generate or react to.) */
697 create_cell_parse(create_cell_t
*cell_out
, const cell_t
*cell_in
)
699 switch (cell_in
->command
) {
701 if (tor_memeq(cell_in
->payload
, NTOR_CREATE_MAGIC
, 16)) {
702 create_cell_init(cell_out
, CELL_CREATE
, ONION_HANDSHAKE_TYPE_NTOR
,
703 NTOR_ONIONSKIN_LEN
, cell_in
->payload
+16);
705 create_cell_init(cell_out
, CELL_CREATE
, ONION_HANDSHAKE_TYPE_TAP
,
706 TAP_ONIONSKIN_CHALLENGE_LEN
, cell_in
->payload
);
709 case CELL_CREATE_FAST
:
710 create_cell_init(cell_out
, CELL_CREATE_FAST
, ONION_HANDSHAKE_TYPE_FAST
,
711 CREATE_FAST_LEN
, cell_in
->payload
);
714 if (parse_create2_payload(cell_out
, cell_in
->payload
,
715 CELL_PAYLOAD_SIZE
) < 0)
722 return check_create_cell(cell_out
, 0);
725 /** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
727 check_created_cell(const created_cell_t
*cell
)
729 switch (cell
->cell_type
) {
731 if (cell
->handshake_len
!= TAP_ONIONSKIN_REPLY_LEN
&&
732 cell
->handshake_len
!= NTOR_REPLY_LEN
)
735 case CELL_CREATED_FAST
:
736 if (cell
->handshake_len
!= CREATED_FAST_LEN
)
740 if (cell
->handshake_len
> RELAY_PAYLOAD_SIZE
-2)
748 /** Parse a CREATED, CREATED_FAST, or CREATED2 cell from <b>cell_in</b> into
749 * <b>cell_out</b>. Return 0 on success, -1 on failure. */
751 created_cell_parse(created_cell_t
*cell_out
, const cell_t
*cell_in
)
753 memset(cell_out
, 0, sizeof(*cell_out
));
755 switch (cell_in
->command
) {
757 cell_out
->cell_type
= CELL_CREATED
;
758 cell_out
->handshake_len
= TAP_ONIONSKIN_REPLY_LEN
;
759 memcpy(cell_out
->reply
, cell_in
->payload
, TAP_ONIONSKIN_REPLY_LEN
);
761 case CELL_CREATED_FAST
:
762 cell_out
->cell_type
= CELL_CREATED_FAST
;
763 cell_out
->handshake_len
= CREATED_FAST_LEN
;
764 memcpy(cell_out
->reply
, cell_in
->payload
, CREATED_FAST_LEN
);
768 const uint8_t *p
= cell_in
->payload
;
769 cell_out
->cell_type
= CELL_CREATED2
;
770 cell_out
->handshake_len
= ntohs(get_uint16(p
));
771 if (cell_out
->handshake_len
> CELL_PAYLOAD_SIZE
- 2)
773 memcpy(cell_out
->reply
, p
+2, cell_out
->handshake_len
);
778 return check_created_cell(cell_out
);
781 /** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
783 check_extend_cell(const extend_cell_t
*cell
)
785 if (tor_digest_is_zero((const char*)cell
->node_id
))
787 /* We don't currently allow EXTEND2 cells without an IPv4 address */
788 if (tor_addr_family(&cell
->orport_ipv4
.addr
) == AF_UNSPEC
)
790 if (cell
->create_cell
.cell_type
== CELL_CREATE
) {
791 if (cell
->cell_type
!= RELAY_COMMAND_EXTEND
)
793 } else if (cell
->create_cell
.cell_type
== CELL_CREATE2
) {
794 if (cell
->cell_type
!= RELAY_COMMAND_EXTEND2
&&
795 cell
->cell_type
!= RELAY_COMMAND_EXTEND
)
798 /* In particular, no CREATE_FAST cells are allowed */
801 if (cell
->create_cell
.handshake_type
== ONION_HANDSHAKE_TYPE_FAST
)
804 return check_create_cell(&cell
->create_cell
, 1);
807 /** Protocol constants for specifier types in EXTEND2
810 #define SPECTYPE_IPV4 0
811 #define SPECTYPE_IPV6 1
812 #define SPECTYPE_LEGACY_ID 2
815 /** Parse an EXTEND or EXTEND2 cell (according to <b>command</b>) from the
816 * <b>payload_length</b> bytes of <b>payload</b> into <b>cell_out</b>. Return
817 * 0 on success, -1 on failure. */
819 extend_cell_parse(extend_cell_t
*cell_out
, const uint8_t command
,
820 const uint8_t *payload
, size_t payload_length
)
824 memset(cell_out
, 0, sizeof(*cell_out
));
825 if (payload_length
> RELAY_PAYLOAD_SIZE
)
827 eop
= payload
+ payload_length
;
830 case RELAY_COMMAND_EXTEND
:
832 if (payload_length
!= 6 + TAP_ONIONSKIN_CHALLENGE_LEN
+ DIGEST_LEN
)
835 cell_out
->cell_type
= RELAY_COMMAND_EXTEND
;
836 tor_addr_from_ipv4n(&cell_out
->orport_ipv4
.addr
, get_uint32(payload
));
837 cell_out
->orport_ipv4
.port
= ntohs(get_uint16(payload
+4));
838 tor_addr_make_unspec(&cell_out
->orport_ipv6
.addr
);
839 if (tor_memeq(payload
+ 6, NTOR_CREATE_MAGIC
, 16)) {
840 cell_out
->create_cell
.cell_type
= CELL_CREATE2
;
841 cell_out
->create_cell
.handshake_type
= ONION_HANDSHAKE_TYPE_NTOR
;
842 cell_out
->create_cell
.handshake_len
= NTOR_ONIONSKIN_LEN
;
843 memcpy(cell_out
->create_cell
.onionskin
, payload
+ 22,
846 cell_out
->create_cell
.cell_type
= CELL_CREATE
;
847 cell_out
->create_cell
.handshake_type
= ONION_HANDSHAKE_TYPE_TAP
;
848 cell_out
->create_cell
.handshake_len
= TAP_ONIONSKIN_CHALLENGE_LEN
;
849 memcpy(cell_out
->create_cell
.onionskin
, payload
+ 6,
850 TAP_ONIONSKIN_CHALLENGE_LEN
);
852 memcpy(cell_out
->node_id
, payload
+ 6 + TAP_ONIONSKIN_CHALLENGE_LEN
,
856 case RELAY_COMMAND_EXTEND2
:
858 uint8_t n_specs
, spectype
, speclen
;
860 int found_ipv4
= 0, found_ipv6
= 0, found_id
= 0;
861 tor_addr_make_unspec(&cell_out
->orport_ipv4
.addr
);
862 tor_addr_make_unspec(&cell_out
->orport_ipv6
.addr
);
864 if (payload_length
== 0)
867 cell_out
->cell_type
= RELAY_COMMAND_EXTEND2
;
868 n_specs
= *payload
++;
869 /* Parse the specifiers. We'll only take the first IPv4 and first IPv6
870 * address, and the node ID, and ignore everything else */
871 for (i
= 0; i
< n_specs
; ++i
) {
872 if (eop
- payload
< 2)
874 spectype
= payload
[0];
875 speclen
= payload
[1];
877 if (eop
- payload
< speclen
)
884 tor_addr_from_ipv4n(&cell_out
->orport_ipv4
.addr
,
885 get_uint32(payload
));
886 cell_out
->orport_ipv4
.port
= ntohs(get_uint16(payload
+4));
894 tor_addr_from_ipv6_bytes(&cell_out
->orport_ipv6
.addr
,
895 (const char*)payload
);
896 cell_out
->orport_ipv6
.port
= ntohs(get_uint16(payload
+16));
900 case SPECTYPE_LEGACY_ID
:
905 memcpy(cell_out
->node_id
, payload
, 20);
911 if (!found_id
|| !found_ipv4
)
913 if (parse_create2_payload(&cell_out
->create_cell
,payload
,eop
-payload
)<0)
921 return check_extend_cell(cell_out
);
924 /** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
926 check_extended_cell(const extended_cell_t
*cell
)
928 if (cell
->created_cell
.cell_type
== CELL_CREATED
) {
929 if (cell
->cell_type
!= RELAY_COMMAND_EXTENDED
)
931 } else if (cell
->created_cell
.cell_type
== CELL_CREATED2
) {
932 if (cell
->cell_type
!= RELAY_COMMAND_EXTENDED2
)
938 return check_created_cell(&cell
->created_cell
);
941 /** Parse an EXTENDED or EXTENDED2 cell (according to <b>command</b>) from the
942 * <b>payload_length</b> bytes of <b>payload</b> into <b>cell_out</b>. Return
943 * 0 on success, -1 on failure. */
945 extended_cell_parse(extended_cell_t
*cell_out
,
946 const uint8_t command
, const uint8_t *payload
,
949 memset(cell_out
, 0, sizeof(*cell_out
));
950 if (payload_len
> RELAY_PAYLOAD_SIZE
)
954 case RELAY_COMMAND_EXTENDED
:
955 if (payload_len
!= TAP_ONIONSKIN_REPLY_LEN
)
957 cell_out
->cell_type
= RELAY_COMMAND_EXTENDED
;
958 cell_out
->created_cell
.cell_type
= CELL_CREATED
;
959 cell_out
->created_cell
.handshake_len
= TAP_ONIONSKIN_REPLY_LEN
;
960 memcpy(cell_out
->created_cell
.reply
, payload
, TAP_ONIONSKIN_REPLY_LEN
);
962 case RELAY_COMMAND_EXTENDED2
:
964 cell_out
->cell_type
= RELAY_COMMAND_EXTENDED2
;
965 cell_out
->created_cell
.cell_type
= CELL_CREATED2
;
966 cell_out
->created_cell
.handshake_len
= ntohs(get_uint16(payload
));
967 if (cell_out
->created_cell
.handshake_len
> RELAY_PAYLOAD_SIZE
- 2 ||
968 cell_out
->created_cell
.handshake_len
> payload_len
- 2)
970 memcpy(cell_out
->created_cell
.reply
, payload
+2,
971 cell_out
->created_cell
.handshake_len
);
978 return check_extended_cell(cell_out
);
981 /** Fill <b>cell_out</b> with a correctly formatted version of the
982 * CREATE{,_FAST,2} cell in <b>cell_in</b>. Return 0 on success, -1 on
983 * failure. This is a cell we didn't originate if <b>relayed</b> is true. */
985 create_cell_format_impl(cell_t
*cell_out
, const create_cell_t
*cell_in
,
990 if (check_create_cell(cell_in
, relayed
) < 0)
993 memset(cell_out
->payload
, 0, sizeof(cell_out
->payload
));
994 cell_out
->command
= cell_in
->cell_type
;
996 p
= cell_out
->payload
;
997 space
= sizeof(cell_out
->payload
);
999 switch (cell_in
->cell_type
) {
1001 if (cell_in
->handshake_type
== ONION_HANDSHAKE_TYPE_NTOR
) {
1002 memcpy(p
, NTOR_CREATE_MAGIC
, 16);
1007 case CELL_CREATE_FAST
:
1008 tor_assert(cell_in
->handshake_len
<= space
);
1009 memcpy(p
, cell_in
->onionskin
, cell_in
->handshake_len
);
1012 tor_assert(cell_in
->handshake_len
<= sizeof(cell_out
->payload
)-4);
1013 set_uint16(cell_out
->payload
, htons(cell_in
->handshake_type
));
1014 set_uint16(cell_out
->payload
+2, htons(cell_in
->handshake_len
));
1015 memcpy(cell_out
->payload
+ 4, cell_in
->onionskin
, cell_in
->handshake_len
);
1025 create_cell_format(cell_t
*cell_out
, const create_cell_t
*cell_in
)
1027 return create_cell_format_impl(cell_out
, cell_in
, 0);
1031 create_cell_format_relayed(cell_t
*cell_out
, const create_cell_t
*cell_in
)
1033 return create_cell_format_impl(cell_out
, cell_in
, 1);
1036 /** Fill <b>cell_out</b> with a correctly formatted version of the
1037 * CREATED{,_FAST,2} cell in <b>cell_in</b>. Return 0 on success, -1 on
1040 created_cell_format(cell_t
*cell_out
, const created_cell_t
*cell_in
)
1042 if (check_created_cell(cell_in
) < 0)
1045 memset(cell_out
->payload
, 0, sizeof(cell_out
->payload
));
1046 cell_out
->command
= cell_in
->cell_type
;
1048 switch (cell_in
->cell_type
) {
1050 case CELL_CREATED_FAST
:
1051 tor_assert(cell_in
->handshake_len
<= sizeof(cell_out
->payload
));
1052 memcpy(cell_out
->payload
, cell_in
->reply
, cell_in
->handshake_len
);
1055 tor_assert(cell_in
->handshake_len
<= sizeof(cell_out
->payload
)-2);
1056 set_uint16(cell_out
->payload
, htons(cell_in
->handshake_len
));
1057 memcpy(cell_out
->payload
+ 2, cell_in
->reply
, cell_in
->handshake_len
);
1065 /** Format the EXTEND{,2} cell in <b>cell_in</b>, storing its relay payload in
1066 * <b>payload_out</b>, the number of bytes used in *<b>len_out</b>, and the
1067 * relay command in *<b>command_out</b>. The <b>payload_out</b> must have
1068 * RELAY_PAYLOAD_SIZE bytes available. Return 0 on success, -1 on failure. */
1070 extend_cell_format(uint8_t *command_out
, uint16_t *len_out
,
1071 uint8_t *payload_out
, const extend_cell_t
*cell_in
)
1074 if (check_extend_cell(cell_in
) < 0)
1078 eop
= payload_out
+ RELAY_PAYLOAD_SIZE
;
1080 memset(p
, 0, RELAY_PAYLOAD_SIZE
);
1082 switch (cell_in
->cell_type
) {
1083 case RELAY_COMMAND_EXTEND
:
1085 *command_out
= RELAY_COMMAND_EXTEND
;
1086 *len_out
= 6 + TAP_ONIONSKIN_CHALLENGE_LEN
+ DIGEST_LEN
;
1087 set_uint32(p
, tor_addr_to_ipv4n(&cell_in
->orport_ipv4
.addr
));
1088 set_uint16(p
+4, ntohs(cell_in
->orport_ipv4
.port
));
1089 if (cell_in
->create_cell
.handshake_type
== ONION_HANDSHAKE_TYPE_NTOR
) {
1090 memcpy(p
+6, NTOR_CREATE_MAGIC
, 16);
1091 memcpy(p
+22, cell_in
->create_cell
.onionskin
, NTOR_ONIONSKIN_LEN
);
1093 memcpy(p
+6, cell_in
->create_cell
.onionskin
,
1094 TAP_ONIONSKIN_CHALLENGE_LEN
);
1096 memcpy(p
+6+TAP_ONIONSKIN_CHALLENGE_LEN
, cell_in
->node_id
, DIGEST_LEN
);
1099 case RELAY_COMMAND_EXTEND2
:
1102 *command_out
= RELAY_COMMAND_EXTEND2
;
1104 *p
++ = n
; /* 2 identifiers */
1105 *p
++ = SPECTYPE_IPV4
; /* First is IPV4. */
1106 *p
++ = 6; /* It's 6 bytes long. */
1107 set_uint32(p
, tor_addr_to_ipv4n(&cell_in
->orport_ipv4
.addr
));
1108 set_uint16(p
+4, htons(cell_in
->orport_ipv4
.port
));
1110 *p
++ = SPECTYPE_LEGACY_ID
; /* Next is an identity digest. */
1111 *p
++ = 20; /* It's 20 bytes long */
1112 memcpy(p
, cell_in
->node_id
, DIGEST_LEN
);
1115 /* Now we can send the handshake */
1116 set_uint16(p
, htons(cell_in
->create_cell
.handshake_type
));
1117 set_uint16(p
+2, htons(cell_in
->create_cell
.handshake_len
));
1120 if (cell_in
->create_cell
.handshake_len
> eop
- p
)
1123 memcpy(p
, cell_in
->create_cell
.onionskin
,
1124 cell_in
->create_cell
.handshake_len
);
1126 p
+= cell_in
->create_cell
.handshake_len
;
1127 *len_out
= p
- payload_out
;
1137 /** Format the EXTENDED{,2} cell in <b>cell_in</b>, storing its relay payload
1138 * in <b>payload_out</b>, the number of bytes used in *<b>len_out</b>, and the
1139 * relay command in *<b>command_out</b>. The <b>payload_out</b> must have
1140 * RELAY_PAYLOAD_SIZE bytes available. Return 0 on success, -1 on failure. */
1142 extended_cell_format(uint8_t *command_out
, uint16_t *len_out
,
1143 uint8_t *payload_out
, const extended_cell_t
*cell_in
)
1146 if (check_extended_cell(cell_in
) < 0)
1150 memset(p
, 0, RELAY_PAYLOAD_SIZE
);
1152 switch (cell_in
->cell_type
) {
1153 case RELAY_COMMAND_EXTENDED
:
1155 *command_out
= RELAY_COMMAND_EXTENDED
;
1156 *len_out
= TAP_ONIONSKIN_REPLY_LEN
;
1157 memcpy(payload_out
, cell_in
->created_cell
.reply
,
1158 TAP_ONIONSKIN_REPLY_LEN
);
1161 case RELAY_COMMAND_EXTENDED2
:
1163 *command_out
= RELAY_COMMAND_EXTENDED2
;
1164 *len_out
= 2 + cell_in
->created_cell
.handshake_len
;
1165 set_uint16(payload_out
, htons(cell_in
->created_cell
.handshake_len
));
1166 if (2+cell_in
->created_cell
.handshake_len
> RELAY_PAYLOAD_SIZE
)
1168 memcpy(payload_out
+2, cell_in
->created_cell
.reply
,
1169 cell_in
->created_cell
.handshake_len
);