commit 0bc1241494a118d5319207a9f4683b993d389e77 Author: Nick Mathewson nickm@torproject.org Date: Fri May 17 11:03:16 2019 -0400
Make sure that we send at least some random data in RELAY_DATA cells
Proposal 289 prevents SENDME-flooding by requiring the other side to authenticate the data it has received. But this data won't actually be random if they are downloading a known resource. "No problem", we said, "let's fell the empty parts of our cells with some randomness!" and we did that in #26871.
Unfortunately, if the relay data payloads are all completely full, there won't be any empty parts for us to randomize.
Therefore, we now pick random "randomness windows" between CIRCWINDOW_INCREMENT/2 and CIRCWINDOW_INCREMENT. We remember whether we have sent a cell containing at least 16 bytes of randomness in that window. If we haven't, then when the window is exhausted, we send one. (This window approach is designed to lower the number of rng checks we have to do. The number 16 is pulled out of a hat to change the attacker's guessing difficulty to "impossible".)
Implements 28646. --- changes/ticket26846 | 6 +++ scripts/maint/practracker/exceptions.txt | 2 +- src/core/or/circuit_st.h | 11 +++++ src/core/or/circuitlist.c | 1 + src/core/or/circuitlist.h | 2 +- src/core/or/relay.c | 76 +++++++++++++++++++++++++++++--- src/core/or/relay.h | 1 + 7 files changed, 90 insertions(+), 9 deletions(-)
diff --git a/changes/ticket26846 b/changes/ticket26846 new file mode 100644 index 000000000..a18e23179 --- /dev/null +++ b/changes/ticket26846 @@ -0,0 +1,6 @@ + o Minor features (authenticated SENDME): + - Ensure that there is enough randomness on every circuit + to prevent an attacker from successfully predicting what SENDME cells + they will need to send: at a random interval, if we have not send + randomness already, leave some extra space at the end of a cell that + we can fill with random bytes. Closes ticket 26846. diff --git a/scripts/maint/practracker/exceptions.txt b/scripts/maint/practracker/exceptions.txt index 712e59dc5..3a32e97be 100644 --- a/scripts/maint/practracker/exceptions.txt +++ b/scripts/maint/practracker/exceptions.txt @@ -120,7 +120,7 @@ problem function-size /src/core/or/connection_or.c:connection_or_compute_authent problem file-size /src/core/or/policies.c 3249 problem function-size /src/core/or/policies.c:policy_summarize() 107 problem function-size /src/core/or/protover.c:protover_all_supported() 117 -problem file-size /src/core/or/relay.c 3173 +problem file-size /src/core/or/relay.c 3250 problem function-size /src/core/or/relay.c:circuit_receive_relay_cell() 127 problem function-size /src/core/or/relay.c:relay_send_command_from_edge_() 116 problem function-size /src/core/or/relay.c:connection_ap_process_end_not_open() 194 diff --git a/src/core/or/circuit_st.h b/src/core/or/circuit_st.h index 499bf93d6..3c7b93161 100644 --- a/src/core/or/circuit_st.h +++ b/src/core/or/circuit_st.h @@ -92,6 +92,10 @@ struct circuit_t { /** True iff this circuit has received a DESTROY cell in either direction */ unsigned int received_destroy : 1;
+ /** True iff we have sent a sufficiently random data cell since last + * we reset send_randomness_after_n_cells. */ + unsigned int have_sent_sufficiently_random_cell : 1; + uint8_t state; /**< Current status of this circuit. */ uint8_t purpose; /**< Why are we creating this circuit? */
@@ -104,6 +108,13 @@ struct circuit_t { * circuit-level sendme cells to indicate that we're willing to accept * more. */ int deliver_window; + /** + * How many cells do we have until we need to send one that contains + * sufficient randomness? Used to ensure that authenticated SENDME cells + * will reflect some unpredictable information. + **/ + uint16_t send_randomness_after_n_cells; + /** FIFO containing the digest of the cells that are just before a SENDME is * sent by the client. It is done at the last cell before our package_window * goes down to 0 which is when we expect a SENDME. diff --git a/src/core/or/circuitlist.c b/src/core/or/circuitlist.c index 72952a8a5..ebbe7f082 100644 --- a/src/core/or/circuitlist.c +++ b/src/core/or/circuitlist.c @@ -993,6 +993,7 @@ init_circuit_base(circuit_t *circ)
circ->package_window = circuit_initial_package_window(); circ->deliver_window = CIRCWINDOW_START; + circuit_reset_sendme_randomness(circ); cell_queue_init(&circ->n_chan_cells);
smartlist_add(circuit_get_global_list(), circ); diff --git a/src/core/or/circuitlist.h b/src/core/or/circuitlist.h index 6f5fce487..80c1f7ac4 100644 --- a/src/core/or/circuitlist.h +++ b/src/core/or/circuitlist.h @@ -218,7 +218,7 @@ void circuit_mark_all_dirty_circs_as_unusable(void); void circuit_synchronize_written_or_bandwidth(const circuit_t *c, circuit_channel_direction_t dir); MOCK_DECL(void, circuit_mark_for_close_, (circuit_t *circ, int reason, - int line, const char *file)); + int line, const char *cfile)); int circuit_get_cpath_len(origin_circuit_t *circ); int circuit_get_cpath_opened_len(const origin_circuit_t *); void circuit_clear_cpath(origin_circuit_t *circ); diff --git a/src/core/or/relay.c b/src/core/or/relay.c index 7a121780a..c48147dff 100644 --- a/src/core/or/relay.c +++ b/src/core/or/relay.c @@ -533,6 +533,10 @@ relay_command_to_string(uint8_t command) } }
+/** When padding a cell with randomness, leave this many zeros after the + * payload. */ +#define CELL_PADDING_GAP 4 + /** Return the offset where the padding should start. The <b>data_len</b> is * the relay payload length expected to be put in the cell. It can not be * bigger than RELAY_PAYLOAD_SIZE else this function assert(). @@ -556,7 +560,7 @@ get_pad_cell_offset(size_t data_len)
/* If the offset is larger than the cell payload size, we return an offset * of zero indicating that no padding needs to be added. */ - size_t offset = RELAY_HEADER_SIZE + data_len + 4; + size_t offset = RELAY_HEADER_SIZE + data_len + CELL_PADDING_GAP; if (offset >= CELL_PAYLOAD_SIZE) { return 0; } @@ -2028,26 +2032,81 @@ uint64_t stats_n_data_cells_received = 0; uint64_t stats_n_data_bytes_received = 0;
/** + * Called when initializing a circuit, or when we have reached the end of the + * window in which we need to send some randomness so that incoming sendme + * cells will be unpredictable. Resets the flags and picks a new window. + */ +void +circuit_reset_sendme_randomness(circuit_t *circ) +{ + circ->have_sent_sufficiently_random_cell = 0; + circ->send_randomness_after_n_cells = CIRCWINDOW_INCREMENT / 2 + + crypto_fast_rng_get_uint(get_thread_fast_rng(), CIRCWINDOW_INCREMENT / 2); +} + +/** + * Any relay data payload containing fewer than this many real bytes is + * considered to have enough randomness to. + **/ +#define RELAY_PAYLOAD_LENGTH_FOR_RANDOM_SENDMES \ + (RELAY_PAYLOAD_SIZE - CELL_PADDING_GAP - 16) + +/** * Helper. Return the number of bytes that should be put into a cell from a * given edge connection on which <b>n_available</b> bytes are available. */ static size_t connection_edge_get_inbuf_bytes_to_package(size_t n_available, - int package_partial) + int package_partial, + circuit_t *on_circuit) { if (!n_available) return 0;
- size_t length = RELAY_PAYLOAD_SIZE; + /* Do we need to force this payload to have space for randomness? */ + const bool force_random_bytes = + (on_circuit->send_randomness_after_n_cells == 0) && + (! on_circuit->have_sent_sufficiently_random_cell);
- if (n_available < length) { /* not a full payload available */ + /* At most how much would we like to send in this cell? */ + size_t target_length; + if (force_random_bytes) { + target_length = RELAY_PAYLOAD_LENGTH_FOR_RANDOM_SENDMES; + } else { + target_length = RELAY_PAYLOAD_SIZE; + } + + /* Decide how many bytes we will actually put into this cell. */ + size_t package_length; + if (n_available >= target_length) { /* A full payload is available. */ + package_length = target_length; + } else { /* not a full payload available */ if (package_partial) - length = n_available; /* just take whatever's available now */ + package_length = n_available; /* just take whatever's available now */ else return 0; /* nothing to do until we have a full payload */ }
- return length; + /* If we reach this point, we will be definitely sending the cell. */ + tor_assert_nonfatal(package_length > 0); + + if (package_length <= RELAY_PAYLOAD_LENGTH_FOR_RANDOM_SENDMES) { + /* This cell will have enough randomness in the padding to make a future + * sendme cell unpredictable. */ + on_circuit->have_sent_sufficiently_random_cell = 1; + } + + if (on_circuit->send_randomness_after_n_cells == 0) { + /* Either this cell, or some previous cell, had enough padding to + * ensure sendme unpredictability. */ + tor_assert_nonfatal(on_circuit->have_sent_sufficiently_random_cell); + /* Pick a new interval in which we need to send randomness. */ + circuit_reset_sendme_randomness(on_circuit); + } + + --on_circuit->send_randomness_after_n_cells; + + return package_length; }
/** If <b>conn</b> has an entire relay payload of bytes on its inbuf (or @@ -2123,10 +2182,13 @@ connection_edge_package_raw_inbuf(edge_connection_t *conn, int package_partial, }
length = connection_edge_get_inbuf_bytes_to_package(bytes_to_process, - package_partial); + package_partial, circ); if (!length) return 0;
+ /* If we reach this point, we will definitely be packaging bytes into + * a cell. */ + stats_n_data_bytes_packaged += length; stats_n_data_cells_packaged += 1;
diff --git a/src/core/or/relay.h b/src/core/or/relay.h index 97d5d6d0f..0fc308f7d 100644 --- a/src/core/or/relay.h +++ b/src/core/or/relay.h @@ -42,6 +42,7 @@ int connection_edge_package_raw_inbuf(edge_connection_t *conn, int package_partial, int *max_cells); void connection_edge_consider_sending_sendme(edge_connection_t *conn); +void circuit_reset_sendme_randomness(circuit_t *circ);
extern uint64_t stats_n_data_cells_packaged; extern uint64_t stats_n_data_bytes_packaged;