1 /* Copyright (c) 2019-2020, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
6 * \brief Code that is related to SENDME cells both in terms of
7 * creating/parsing cells and handling the content.
10 #define SENDME_PRIVATE
12 #include "core/or/or.h"
14 #include "app/config/config.h"
15 #include "core/crypto/relay_crypto.h"
16 #include "core/mainloop/connection.h"
17 #include "core/or/cell_st.h"
18 #include "core/or/crypt_path.h"
19 #include "core/or/circuitlist.h"
20 #include "core/or/circuituse.h"
21 #include "core/or/or_circuit_st.h"
22 #include "core/or/relay.h"
23 #include "core/or/sendme.h"
24 #include "feature/nodelist/networkstatus.h"
25 #include "lib/ctime/di_ops.h"
26 #include "trunnel/sendme_cell.h"
28 /* Return the minimum version given by the consensus (if any) that should be
29 * used when emitting a SENDME cell. */
31 get_emit_min_version(void)
33 return networkstatus_get_param(NULL
, "sendme_emit_min_version",
34 SENDME_EMIT_MIN_VERSION_DEFAULT
,
35 SENDME_EMIT_MIN_VERSION_MIN
,
36 SENDME_EMIT_MIN_VERSION_MAX
);
39 /* Return the minimum version given by the consensus (if any) that should be
40 * accepted when receiving a SENDME cell. */
42 get_accept_min_version(void)
44 return networkstatus_get_param(NULL
, "sendme_accept_min_version",
45 SENDME_ACCEPT_MIN_VERSION_DEFAULT
,
46 SENDME_ACCEPT_MIN_VERSION_MIN
,
47 SENDME_ACCEPT_MIN_VERSION_MAX
);
50 /* Pop the first cell digset on the given circuit from the SENDME last digests
51 * list. NULL is returned if the list is uninitialized or empty.
53 * The caller gets ownership of the returned digest thus is responsible for
54 * freeing the memory. */
56 pop_first_cell_digest(const circuit_t
*circ
)
62 if (circ
->sendme_last_digests
== NULL
||
63 smartlist_len(circ
->sendme_last_digests
) == 0) {
67 /* More cell digest than the SENDME window is never suppose to happen. The
68 * cell should have been rejected before reaching this point due to its
69 * package_window down to 0 leading to a circuit close. Scream loudly but
70 * still pop the element so we don't memory leak. */
71 tor_assert_nonfatal(smartlist_len(circ
->sendme_last_digests
) <=
72 CIRCWINDOW_START_MAX
/ CIRCWINDOW_INCREMENT
);
74 circ_digest
= smartlist_get(circ
->sendme_last_digests
, 0);
75 smartlist_del_keeporder(circ
->sendme_last_digests
, 0);
79 /* Return true iff the given cell digest matches the first digest in the
80 * circuit sendme list. */
82 v1_digest_matches(const uint8_t *circ_digest
, const uint8_t *cell_digest
)
84 tor_assert(circ_digest
);
85 tor_assert(cell_digest
);
87 /* Compare the digest with the one in the SENDME. This cell is invalid
88 * without a perfect match. */
89 if (tor_memneq(circ_digest
, cell_digest
, TRUNNEL_SENDME_V1_DIGEST_LEN
)) {
90 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
91 "SENDME v1 cell digest do not match.");
95 /* Digests matches! */
99 /* Return true iff the given decoded SENDME version 1 cell is valid and
100 * matches the expected digest on the circuit.
102 * Validation is done by comparing the digest in the cell from the previous
103 * cell we saw which tells us that the other side has in fact seen that cell.
104 * See proposal 289 for more details. */
106 cell_v1_is_valid(const sendme_cell_t
*cell
, const uint8_t *circ_digest
)
109 tor_assert(circ_digest
);
111 const uint8_t *cell_digest
= sendme_cell_getconstarray_data_v1_digest(cell
);
112 return v1_digest_matches(circ_digest
, cell_digest
);
115 /* Return true iff the given cell version can be handled or if the minimum
116 * accepted version from the consensus is known to us. */
118 cell_version_can_be_handled(uint8_t cell_version
)
120 int accept_version
= get_accept_min_version();
122 /* We will first check if the consensus minimum accepted version can be
123 * handled by us and if not, regardless of the cell version we got, we can't
125 if (accept_version
> SENDME_MAX_SUPPORTED_VERSION
) {
126 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
127 "Unable to accept SENDME version %u (from consensus). "
128 "We only support <= %u. Probably your tor is too old?",
129 accept_version
, SENDME_MAX_SUPPORTED_VERSION
);
133 /* Then, is this version below the accepted version from the consensus? If
134 * yes, we must not handle it. */
135 if (cell_version
< accept_version
) {
136 log_info(LD_PROTOCOL
, "Unacceptable SENDME version %u. Only "
137 "accepting %u (from consensus). Closing circuit.",
138 cell_version
, accept_version
);
142 /* Is this cell version supported by us? */
143 if (cell_version
> SENDME_MAX_SUPPORTED_VERSION
) {
144 log_info(LD_PROTOCOL
, "SENDME cell version %u is not supported by us. "
145 "We only support <= %u",
146 cell_version
, SENDME_MAX_SUPPORTED_VERSION
);
155 /* Return true iff the encoded SENDME cell in cell_payload of length
156 * cell_payload_len is valid. For each version:
159 * 1: Authenticated with last cell digest.
161 * This is the main critical function to make sure we can continue to
162 * send/recv cells on a circuit. If the SENDME is invalid, the circuit should
163 * be marked for close by the caller. */
165 sendme_is_valid(const circuit_t
*circ
, const uint8_t *cell_payload
,
166 size_t cell_payload_len
)
168 uint8_t cell_version
;
169 uint8_t *circ_digest
= NULL
;
170 sendme_cell_t
*cell
= NULL
;
173 tor_assert(cell_payload
);
175 /* An empty payload means version 0 so skip trunnel parsing. We won't be
176 * able to parse a 0 length buffer into a valid SENDME cell. */
177 if (cell_payload_len
== 0) {
180 /* First we'll decode the cell so we can get the version. */
181 if (sendme_cell_parse(&cell
, cell_payload
, cell_payload_len
) < 0) {
182 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
183 "Unparseable SENDME cell received. Closing circuit.");
186 cell_version
= sendme_cell_get_version(cell
);
189 /* Validate that we can handle this cell version. */
190 if (!cell_version_can_be_handled(cell_version
)) {
194 /* Pop the first element that was added (FIFO). We do that regardless of the
195 * version so we don't accumulate on the circuit if v0 is used by the other
197 circ_digest
= pop_first_cell_digest(circ
);
198 if (circ_digest
== NULL
) {
199 /* We shouldn't have received a SENDME if we have no digests. Log at
200 * protocol warning because it can be tricked by sending many SENDMEs
201 * without prior data cell. */
202 log_fn(LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
203 "We received a SENDME but we have no cell digests to match. "
208 /* Validate depending on the version now. */
209 switch (cell_version
) {
211 if (!cell_v1_is_valid(cell
, circ_digest
)) {
216 /* Version 0, there is no work to be done on the payload so it is
217 * necessarily valid if we pass the version validation. */
220 log_warn(LD_PROTOCOL
, "Unknown SENDME cell version %d received.",
222 tor_assert_nonfatal_unreached();
227 sendme_cell_free(cell
);
228 tor_free(circ_digest
);
231 sendme_cell_free(cell
);
232 tor_free(circ_digest
);
236 /* Build and encode a version 1 SENDME cell into payload, which must be at
237 * least of RELAY_PAYLOAD_SIZE bytes, using the digest for the cell data.
239 * Return the size in bytes of the encoded cell in payload. A negative value
240 * is returned on encoding failure. */
242 build_cell_payload_v1(const uint8_t *cell_digest
, uint8_t *payload
)
245 sendme_cell_t
*cell
= NULL
;
247 tor_assert(cell_digest
);
250 cell
= sendme_cell_new();
252 /* Building a payload for version 1. */
253 sendme_cell_set_version(cell
, 0x01);
254 /* Set the data length field for v1. */
255 sendme_cell_set_data_len(cell
, TRUNNEL_SENDME_V1_DIGEST_LEN
);
257 /* Copy the digest into the data payload. */
258 memcpy(sendme_cell_getarray_data_v1_digest(cell
), cell_digest
,
259 sendme_cell_get_data_len(cell
));
261 /* Finally, encode the cell into the payload. */
262 len
= sendme_cell_encode(payload
, RELAY_PAYLOAD_SIZE
, cell
);
264 sendme_cell_free(cell
);
268 /* Send a circuit-level SENDME on the given circuit using the layer_hint if
269 * not NULL. The digest is only used for version 1.
271 * Return 0 on success else a negative value and the circuit will be closed
272 * because we failed to send the cell on it. */
274 send_circuit_level_sendme(circuit_t
*circ
, crypt_path_t
*layer_hint
,
275 const uint8_t *cell_digest
)
277 uint8_t emit_version
;
278 uint8_t payload
[RELAY_PAYLOAD_SIZE
];
282 tor_assert(cell_digest
);
284 emit_version
= get_emit_min_version();
285 switch (emit_version
) {
287 payload_len
= build_cell_payload_v1(cell_digest
, payload
);
288 if (BUG(payload_len
< 0)) {
289 /* Unable to encode the cell, abort. We can recover from this by closing
290 * the circuit but in theory it should never happen. */
293 log_debug(LD_PROTOCOL
, "Emitting SENDME version 1 cell.");
298 /* Unknown version, fallback to version 0 meaning no payload. */
300 log_debug(LD_PROTOCOL
, "Emitting SENDME version 0 cell. "
301 "Consensus emit version is %d", emit_version
);
305 if (relay_send_command_from_edge(0, circ
, RELAY_COMMAND_SENDME
,
306 (char *) payload
, payload_len
,
309 "SENDME relay_send_command_from_edge failed. Circuit's closed.");
310 return -1; /* the circuit's closed, don't continue */
315 /* Record the cell digest only if the next cell is expected to be a SENDME. */
317 record_cell_digest_on_circ(circuit_t
*circ
, const uint8_t *sendme_digest
)
320 tor_assert(sendme_digest
);
322 /* Add the digest to the last seen list in the circuit. */
323 if (circ
->sendme_last_digests
== NULL
) {
324 circ
->sendme_last_digests
= smartlist_new();
326 smartlist_add(circ
->sendme_last_digests
,
327 tor_memdup(sendme_digest
, DIGEST_LEN
));
334 /** Return true iff the next cell for the given cell window is expected to be
337 * We are able to know that because the package or deliver window value minus
338 * one cell (the possible SENDME cell) should be a multiple of the increment
341 circuit_sendme_cell_is_next(int window
)
343 /* At the start of the window, no SENDME will be expected. */
344 if (window
== CIRCWINDOW_START
) {
348 /* Are we at the limit of the increment and if not, we don't expect next
351 * We test against the window minus 1 because when we are looking if the
352 * next cell is a SENDME, the window (either package or deliver) hasn't been
353 * decremented just yet so when this is called, we are currently processing
354 * the "window - 1" cell.
356 * This function is used when recording a cell digest and this is done quite
357 * low in the stack when decrypting or encrypting a cell. The window is only
358 * updated once the cell is actually put in the outbuf. */
359 if (((window
- 1) % CIRCWINDOW_INCREMENT
) != 0) {
363 /* Next cell is expected to be a SENDME. */
367 /** Called when we've just received a relay data cell, when we've just
368 * finished flushing all bytes to stream <b>conn</b>, or when we've flushed
369 * *some* bytes to the stream <b>conn</b>.
371 * If conn->outbuf is not too full, and our deliver window is low, send back a
372 * suitable number of stream-level sendme cells.
375 sendme_connection_edge_consider_sending(edge_connection_t
*conn
)
379 int log_domain
= TO_CONN(conn
)->type
== CONN_TYPE_AP
? LD_APP
: LD_EXIT
;
381 /* Don't send it if we still have data to deliver. */
382 if (connection_outbuf_too_full(TO_CONN(conn
))) {
386 if (circuit_get_by_edge_conn(conn
) == NULL
) {
387 /* This can legitimately happen if the destroy has already arrived and
388 * torn down the circuit. */
389 log_info(log_domain
, "No circuit associated with edge connection. "
390 "Skipping sending SENDME.");
394 while (conn
->deliver_window
<=
395 (STREAMWINDOW_START
- STREAMWINDOW_INCREMENT
)) {
396 log_debug(log_domain
, "Outbuf %" TOR_PRIuSZ
", queuing stream SENDME.",
397 buf_datalen(TO_CONN(conn
)->outbuf
));
398 conn
->deliver_window
+= STREAMWINDOW_INCREMENT
;
399 if (connection_edge_send_command(conn
, RELAY_COMMAND_SENDME
,
401 log_debug(LD_CIRC
, "connection_edge_send_command failed while sending "
402 "a SENDME. Circuit probably closed, skipping.");
403 goto end
; /* The circuit's closed, don't continue */
411 /** Check if the deliver_window for circuit <b>circ</b> (at hop
412 * <b>layer_hint</b> if it's defined) is low enough that we should
413 * send a circuit-level sendme back down the circuit. If so, send
414 * enough sendmes that the window would be overfull if we sent any
418 sendme_circuit_consider_sending(circuit_t
*circ
, crypt_path_t
*layer_hint
)
420 bool sent_one_sendme
= false;
421 const uint8_t *digest
;
423 while ((layer_hint
? layer_hint
->deliver_window
: circ
->deliver_window
) <=
424 CIRCWINDOW_START
- CIRCWINDOW_INCREMENT
) {
425 log_debug(LD_CIRC
,"Queuing circuit sendme.");
427 layer_hint
->deliver_window
+= CIRCWINDOW_INCREMENT
;
428 digest
= cpath_get_sendme_digest(layer_hint
);
430 circ
->deliver_window
+= CIRCWINDOW_INCREMENT
;
431 digest
= relay_crypto_get_sendme_digest(&TO_OR_CIRCUIT(circ
)->crypto
);
433 if (send_circuit_level_sendme(circ
, layer_hint
, digest
) < 0) {
434 return; /* The circuit's closed, don't continue */
436 /* Current implementation is not suppose to send multiple SENDME at once
437 * because this means we would use the same relay crypto digest for each
438 * SENDME leading to a mismatch on the other side and the circuit to
439 * collapse. Scream loudly if it ever happens so we can address it. */
440 tor_assert_nonfatal(!sent_one_sendme
);
441 sent_one_sendme
= true;
445 /* Process a circuit-level SENDME cell that we just received. The layer_hint,
446 * if not NULL, is the Exit hop of the connection which means that we are a
447 * client. In that case, circ must be an origin circuit. The cell_body_len is
448 * the length of the SENDME cell payload (excluding the header). The
449 * cell_payload is the payload.
451 * Return 0 on success (the SENDME is valid and the package window has
452 * been updated properly).
454 * On error, a negative value is returned, which indicates that the
455 * circuit must be closed using the value as the reason for it. */
457 sendme_process_circuit_level(crypt_path_t
*layer_hint
,
458 circuit_t
*circ
, const uint8_t *cell_payload
,
459 uint16_t cell_payload_len
)
462 tor_assert(cell_payload
);
464 /* Validate the SENDME cell. Depending on the version, different validation
465 * can be done. An invalid SENDME requires us to close the circuit. */
466 if (!sendme_is_valid(circ
, cell_payload
, cell_payload_len
)) {
467 return -END_CIRC_REASON_TORPROTOCOL
;
470 /* If we are the origin of the circuit, we are the Client so we use the
471 * layer hint (the Exit hop) for the package window tracking. */
472 if (CIRCUIT_IS_ORIGIN(circ
)) {
473 /* If we are the origin of the circuit, it is impossible to not have a
474 * cpath. Just in case, bug on it and close the circuit. */
475 if (BUG(layer_hint
== NULL
)) {
476 return -END_CIRC_REASON_TORPROTOCOL
;
478 if ((layer_hint
->package_window
+ CIRCWINDOW_INCREMENT
) >
479 CIRCWINDOW_START_MAX
) {
480 static struct ratelim_t exit_warn_ratelim
= RATELIM_INIT(600);
481 log_fn_ratelim(&exit_warn_ratelim
, LOG_WARN
, LD_PROTOCOL
,
482 "Unexpected sendme cell from exit relay. "
484 return -END_CIRC_REASON_TORPROTOCOL
;
486 layer_hint
->package_window
+= CIRCWINDOW_INCREMENT
;
487 log_debug(LD_APP
, "circ-level sendme at origin, packagewindow %d.",
488 layer_hint
->package_window
);
490 /* We count circuit-level sendme's as valid delivered data because they
491 * are rate limited. */
492 circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ
), cell_payload_len
);
494 /* We aren't the origin of this circuit so we are the Exit and thus we
495 * track the package window with the circuit object. */
496 if ((circ
->package_window
+ CIRCWINDOW_INCREMENT
) >
497 CIRCWINDOW_START_MAX
) {
498 static struct ratelim_t client_warn_ratelim
= RATELIM_INIT(600);
499 log_fn_ratelim(&client_warn_ratelim
, LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
500 "Unexpected sendme cell from client. "
501 "Closing circ (window %d).", circ
->package_window
);
502 return -END_CIRC_REASON_TORPROTOCOL
;
504 circ
->package_window
+= CIRCWINDOW_INCREMENT
;
505 log_debug(LD_EXIT
, "circ-level sendme at non-origin, packagewindow %d.",
506 circ
->package_window
);
512 /* Process a stream-level SENDME cell that we just received. The conn is the
513 * edge connection (stream) that the circuit circ is associated with. The
514 * cell_body_len is the length of the payload (excluding the header).
516 * Return 0 on success (the SENDME is valid and the package window has
517 * been updated properly).
519 * On error, a negative value is returned, which indicates that the
520 * circuit must be closed using the value as the reason for it. */
522 sendme_process_stream_level(edge_connection_t
*conn
, circuit_t
*circ
,
523 uint16_t cell_body_len
)
528 /* Don't allow the other endpoint to request more than our maximum (i.e.
529 * initial) stream SENDME window worth of data. Well-behaved stock clients
530 * will not request more than this max (as per the check in the while loop
531 * of sendme_connection_edge_consider_sending()). */
532 if ((conn
->package_window
+ STREAMWINDOW_INCREMENT
) >
533 STREAMWINDOW_START_MAX
) {
534 static struct ratelim_t stream_warn_ratelim
= RATELIM_INIT(600);
535 log_fn_ratelim(&stream_warn_ratelim
, LOG_PROTOCOL_WARN
, LD_PROTOCOL
,
536 "Unexpected stream sendme cell. Closing circ (window %d).",
537 conn
->package_window
);
538 return -END_CIRC_REASON_TORPROTOCOL
;
540 /* At this point, the stream sendme is valid */
541 conn
->package_window
+= STREAMWINDOW_INCREMENT
;
543 /* We count circuit-level sendme's as valid delivered data because they are
545 if (CIRCUIT_IS_ORIGIN(circ
)) {
546 circuit_read_valid_data(TO_ORIGIN_CIRCUIT(circ
), cell_body_len
);
549 log_debug(CIRCUIT_IS_ORIGIN(circ
) ? LD_APP
: LD_EXIT
,
550 "stream-level sendme, package_window now %d.",
551 conn
->package_window
);
555 /* Called when a relay DATA cell is received on the given circuit. If
556 * layer_hint is NULL, this means we are the Exit end point else we are the
557 * Client. Update the deliver window and return its new value. */
559 sendme_circuit_data_received(circuit_t
*circ
, crypt_path_t
*layer_hint
)
561 int deliver_window
, domain
;
563 if (CIRCUIT_IS_ORIGIN(circ
)) {
564 tor_assert(layer_hint
);
565 --layer_hint
->deliver_window
;
566 deliver_window
= layer_hint
->deliver_window
;
569 tor_assert(!layer_hint
);
570 --circ
->deliver_window
;
571 deliver_window
= circ
->deliver_window
;
575 log_debug(domain
, "Circuit deliver_window now %d.", deliver_window
);
576 return deliver_window
;
579 /* Called when a relay DATA cell is received for the given edge connection
580 * conn. Update the deliver window and return its new value. */
582 sendme_stream_data_received(edge_connection_t
*conn
)
585 return --conn
->deliver_window
;
588 /* Called when a relay DATA cell is packaged on the given circuit. If
589 * layer_hint is NULL, this means we are the Exit end point else we are the
590 * Client. Update the package window and return its new value. */
592 sendme_note_circuit_data_packaged(circuit_t
*circ
, crypt_path_t
*layer_hint
)
594 int package_window
, domain
;
598 if (CIRCUIT_IS_ORIGIN(circ
)) {
600 tor_assert(layer_hint
);
601 --layer_hint
->package_window
;
602 package_window
= layer_hint
->package_window
;
606 tor_assert(!layer_hint
);
607 --circ
->package_window
;
608 package_window
= circ
->package_window
;
612 log_debug(domain
, "Circuit package_window now %d.", package_window
);
613 return package_window
;
616 /* Called when a relay DATA cell is packaged for the given edge connection
617 * conn. Update the package window and return its new value. */
619 sendme_note_stream_data_packaged(edge_connection_t
*conn
)
623 --conn
->package_window
;
624 log_debug(LD_APP
, "Stream package_window now %d.", conn
->package_window
);
625 return conn
->package_window
;
628 /* Record the cell digest into the circuit sendme digest list depending on
629 * which edge we are. The digest is recorded only if we expect the next cell
630 * that we will receive is a SENDME so we can match the digest. */
632 sendme_record_cell_digest_on_circ(circuit_t
*circ
, crypt_path_t
*cpath
)
635 uint8_t *sendme_digest
;
639 package_window
= circ
->package_window
;
641 package_window
= cpath
->package_window
;
644 /* Is this the last cell before a SENDME? The idea is that if the
645 * package_window reaches a multiple of the increment, after this cell, we
646 * should expect a SENDME. */
647 if (!circuit_sendme_cell_is_next(package_window
)) {
651 /* Getting the digest is expensive so we only do it once we are certain to
652 * record it on the circuit. */
654 sendme_digest
= cpath_get_sendme_digest(cpath
);
657 relay_crypto_get_sendme_digest(&TO_OR_CIRCUIT(circ
)->crypto
);
660 record_cell_digest_on_circ(circ
, sendme_digest
);
663 /* Called once we decrypted a cell and recognized it. Record the cell digest
664 * as the next sendme digest only if the next cell we'll send on the circuit
665 * is expected to be a SENDME. */
667 sendme_record_received_cell_digest(circuit_t
*circ
, crypt_path_t
*cpath
)
671 /* Only record if the next cell is expected to be a SENDME. */
672 if (!circuit_sendme_cell_is_next(cpath
? cpath
->deliver_window
:
673 circ
->deliver_window
)) {
678 /* Record incoming digest. */
679 cpath_sendme_record_cell_digest(cpath
, false);
681 /* Record forward digest. */
682 relay_crypto_record_sendme_digest(&TO_OR_CIRCUIT(circ
)->crypto
, true);
686 /* Called once we encrypted a cell. Record the cell digest as the next sendme
687 * digest only if the next cell we expect to receive is a SENDME so we can
688 * match the digests. */
690 sendme_record_sending_cell_digest(circuit_t
*circ
, crypt_path_t
*cpath
)
694 /* Only record if the next cell is expected to be a SENDME. */
695 if (!circuit_sendme_cell_is_next(cpath
? cpath
->package_window
:
696 circ
->package_window
)) {
701 /* Record the forward digest. */
702 cpath_sendme_record_cell_digest(cpath
, true);
704 /* Record the incoming digest. */
705 relay_crypto_record_sendme_digest(&TO_OR_CIRCUIT(circ
)->crypto
, false);