Filename: 251-netflow-padding.txt
Title: Padding for netflow record resolution reduction
Authors: Mike Perry
Created: 20 August 2015
Status: Closed
Implemented-In: 0.3.1.1-alpha
NOTE: Please look at section 2 of padding-spec.txt now, not this document.
0. Motivation
It is common practice by many ISPs to record data about the activity of
endpoints that use their uplink, if nothing else for billing purposes, but
sometimes also for monitoring for attacks and general failure.
Unfortunately, Tor node operators typically have no control over the data
recorded and retained by their ISP. They are often not even informed about
their ISP's retention policy, or the associated data sharing policy of those
records (which tends to be "give them to whoever asks" in practice[1]).
It is also likely that defenses for this problem will prove useful against
proposed data retention plans in the EU and elsewhere, since these schemes
will likely rely on the same technology.
0.1. Background
At the ISP level, this data typically takes the form of Netflow, jFlow,
Netstream, or IPFIX flow records. These records are emitted by gateway
routers in a raw form and then exported (often over plaintext) to a
"collector" that either records them verbatim, or reduces their granularity
further[2].
Netflow records and the associated data collection and retention tools are
very configurable, and have many modes of operation, especially when
configured to handle high throughput. However, at ISP scale, per-flow records
are very likely to be employed, since they are the default, and also provide
very high resolution in terms of endpoint activity, second only to full packet
and/or header capture.
Per-flow records record the endpoint connection 5-tuple, as well as the
total number of bytes sent and received by that 5-tuple during a particular
time period. They can store additional fields as well, but it is primarily
timing and bytecount information that concern us.
When configured to provide per-flow data, routers emit these raw flow
records periodically for all active connections passing through them
based on two parameters: the "active flow timeout" and the "inactive
flow timeout".
The "active flow timeout" causes the router to emit a new record
periodically for every active TCP session that continuously sends data. The
default active flow timeout for most routers is 30 minutes, meaning that a
new record is created for every TCP session at least every 30 minutes, no
matter what. This value can be configured to be from 1 minute to 60 minutes
on major routers.
The "inactive flow timeout" is used by routers to create a new record if a
TCP session is inactive for some number of seconds. It allows routers to
avoid the need to track a large number of idle connections in memory, and
instead emit a separate record only when there is activity. This value
ranges from 10 seconds to 600 seconds on common routers. It appears as
though no routers support a value lower than 10 seconds.
0.2. Default timeout values of major routers
For reference, here are default values and ranges (in parenthesis when
known) for common routers, along with citations to their manuals.
Some routers speak other collection protocols than Netflow, and in the
case of Juniper, use different timeouts for these protocols. Where this
is known to happen, it has been noted.
Inactive Timeout Active Timeout
Cisco IOS[3] 15s (10-600s) 30min (1-60min)
Cisco Catalyst[4] 5min 32min
Juniper (jFlow)[5] 15s (10-600s) 30min (1-60min)
Juniper (Netflow)[6,7] 60s (10-600s) 30min (1-30min)
H3C (Netstream)[8] 60s (60-600s) 30min (1-60min)
Fortinet[9] 15s 30min
MicroTik[10] 15s 30min
nProbe[14] 30s 120s
Alcatel-Lucent[15] 15s (10-600s) 30min (1-600min)
1. Proposal Overview
The combination of the active and inactive netflow record timeouts allow us
to devise a low-cost padding defense that causes what would otherwise be
split records to "collapse" at the router even before they are exported to
the collector for storage. So long as a connection transmits data before the
"inactive flow timeout" expires, then the router will continue to count the
total bytes on that flow before finally emitting a record at the "active
flow timeout".
This means that for a minimal amount of padding that prevents the "inactive
flow timeout" from expiring, it is possible to reduce the resolution of raw
per-flow netflow data to the total amount of bytes send and received in a 30
minute window. This is a vast reduction in resolution for HTTP, IRC, XMPP,
SSH, and other intermittent interactive traffic, especially when all
user traffic in that time period is multiplexed over a single connection
(as it is with Tor).
2. Implementation
Tor clients currently maintain one TLS connection to their Guard node to
carry actual application traffic, and make up to 3 additional connections to
other nodes to retrieve directory information.
We propose to pad only the client's connection to the Guard node, and not
any other connection. We propose to treat Bridge node connections to the Tor
network as client connections, and pad them, but otherwise not pad between
normal relays.
Both clients and Guards will maintain a timer for all application (ie:
non-directory) TLS connections. Every time a non-padding packet is sent or
received by either end, that endpoint will sample a timeout value from
between 1.5 seconds and 9.5 seconds. If the connection becomes active for
any reason before this timer expires, the timer is reset to a new random
value between 1.5 and 9.5 seconds. If the connection remains inactive until
the timer expires, a single CELL_PADDING cell will be sent on that connection.
In this way, the connection will only be padded in the event that it is
idle, and will always transmit a packet before the minimum 10 second inactive
timeout.
2.1. Tunable parameters
We propose that the defense be controlled by the following consensus
parameters:
* nf_ito_low
- The low end of the range to send padding when inactive, in ms.
- Default: 1500
* nf_ito_high
- The high end of the range to send padding, in ms.
- Default: 9500
* nf_pad_relays
- If set to 1, we also pad inactive relay-to-relay connections
- Default: 0
* conn_timeout_low
- The low end of the range to decide when we should close an idle
connection (not counting padding).
- Default: 900 seconds after last circuit closes
* conn_timeout_high
- The high end of the range to decide when we should close an idle
connection.
- Default: 1800 seconds after last circuit close
If nf_ito_low == nf_ito_high == 0, padding will be disabled.
2.2. Maximum overhead bounds
With the default parameters, we expect a padded connection to send one
padding cell every 5.5 seconds (see Appendix A for the statistical analysis
of expected padding packet rate on an idle link). This averages to 103 bytes
per second full duplex (~52 bytes/sec in each direction), assuming a 512 byte
cell and 55 bytes of TLS+TCP+IP headers. For a connection that remains idle
for a full 30 minutes of inactivity, this is about 92KB of overhead in each
direction.
With 2.5M completely idle clients connected simultaneously, 52 bytes per
second still amounts to only 130MB/second in each direction network-wide,
which is roughly the current amount of Tor directory traffic[11]. Of course,
our 2.5M daily users will neither be connected simultaneously, nor entirely
idle, so we expect the actual overhead to be much lower than this.
2.3. Measuring actual overhead
To measure the actual padding overhead in practice, we propose to export
the following statistics in extra-info descriptors for the previous (fixed,
non-rolling) 24 hour period:
* Total cells read (padding and non-padding)
* Total cells written (padding and non-padding)
* Total CELL_PADDING cells read
* Total CELL_PADDING cells written
* Total RELAY_COMMAND_DROP cells read
* Total RELAY_COMMAND_DROP cells written
These values will be rounded to 100 cells each, and no values are reported if
the relay has read or written less than 10000 cells in the previous period.
RELAY_COMMAND_DROP cells are circuit-level padding not used by this defense,
but we may as well start recording statistics about them now, too, to aid in
the development of future defenses.
2.4. Load balancing considerations
Eventually, we will likely want to update the consensus weights to properly
load balance the selection of Guard nodes that must carry this overhead.
We propose that we use the extra-info documents to get a more accurate value
for the total average Guard and Guard+Exit node overhead of this defense in
practice, and then use that value to fractionally reduce the consensus
selection weights for Guard nodes and Guard+Exit nodes, to reflect their
reduced capacity relative to middle nodes.
3. Threat model and adversarial considerations
This defense does not assume fully adversarial behavior on the part of the
upstream network administrator, as that administrator typically has no
specific interest in trying to deanonymize Tor, but only in monitoring their
own network for signs of overusage, attack, or failure.
Therefore, in a manner closer to the "honest but curious" threat model, we
assume that the netflow collector will be using standard equipment not
specifically tuned to capturing Tor traffic. We want to reduce the resolution
of logs that are collected incidentally, so that if they happen to fall into
the wrong hands, we can be more certain will not be useful.
We feel that this assumption is a fair one because correlation attacks (and
statistical attacks in general) will tend to accumulate false positives very
quickly if the adversary loses resolution at any observation points. It is
especially unlikely for the the attacker to benefit from only a few
high-resolution collection points while the remainder of the Tor network
is only subject to connection-level/per-flow netflow data retention, or even
less data retention than that.
Nonetheless, it is still worthwhile to consider what the adversary is capable
of, especially in light of looming data retention regulation.
Because no major router appears to have the ability to set the inactive
flow timeout below 10 seconds, it would seem as though the adversary is left
with three main options: reduce the active record timeout to the minimum (1
minute), begin logging full packet and/or header data, or develop a custom
solution.
It is an open question to what degree these approaches would help the
adversary, especially if only some of its observation points implemented
these changes.
3.1 What about sampled data?
At scale, it is known that some Internet backbone routers at AS boundaries
and exchanges perform sampled packet header collection and/or produce
netflow records based on a subset of the packets that pass through their
infrastructure.
The effects of this against Tor were studied before against the (much
smaller) Tor network as it was in 2007[12]. At sampling rate of 1 out of
every 2000 packets, the attack did not achieve high accuracy until over
100MB of data were transmitted, even when correlating only 500 flows in
a closed-world lab setting.
We suspect that this type of attack is unlikely to be effective at scale on
the Tor network today, but we make no claims that this defense will make any
impact upon sampled correlation, primarily because the amount of padding
that this defense introduces is comparatively low relative to the amount of
transmitted traffic that sampled correlation attacks require to attain
any accuracy.
3.2. What about long-term statistical disclosure?
This defense similarly does not claim to defeat long-term correlation
attacks involving many observations over large amounts of time.
However, we do believe it will significantly increase the amount of traffic
and the number of independent observations required to attain the same
accuracy if the adversary uses default per-flow netflow records.
3.3. What about prior information/confirmation?
In truth, the most dangerous aspect of these netflow logs is not actually
correlation at all, but confirmation.
If the adversary has prior information about the location of a target, and/or
when and how that target is expected to be using Tor, then the effectiveness
of this defense will be very situation-dependent (on factors such as the
number of other tor users in the area at that time, etc).
In any case, the odds that there is other concurrent activity (to
create a false positive) within a single 30 minute record are much higher
than the odds that there is concurrent activity that aligns with a
subset of a series of smaller, more frequent inactive timeout records.
4. Synergistic effects with future padding and other changes
Because this defense only sends padding when the OR connection is completely
idle, it should still operate optimally when combined with other forms of
padding (such as padding for website traffic fingerprinting and hidden service
circuit fingerprinting). If those future defenses choose to send padding for
any reason at any layer of Tor, then this defense automatically will not.
In addition to interoperating optimally with any future padding defenses,
simple changes to the Tor network usage can serve to further reduce the
usefulness of any data retention, as well as reduce the overhead from this
defense.
For example, if all directory traffic were also tunneled through the main
Guard node instead of independent directory guards, then the adversary
would lose additional resolution in terms of the ability to differentiate
directory traffic from normal usage, especially when it is occurs within
the same netflow record. As written and specified, the defense will pad
such tunneled directory traffic optimally.
Similarly, if bridge guards[13] are implemented such that bridges use their
own guard node to route all of their connecting client traffic through, then
users who run bridges will also benefit from blending their own client traffic
with the concurrent traffic of their connected clients, the sum total of
which will also be optimally padded such that it only transmits padding when
the connection to the bridge's guard is completely idle.
Appendix A: Padding Cell Timeout Distribution Statistics
It turns out that because the padding is bidirectional, and because both
endpoints are maintaining timers, this creates the situation where the time
before sending a padding packet in either direction is actually
min(client_timeout, server_timeout).
If client_timeout and server_timeout are uniformly sampled, then the
distribution of min(client_timeout,server_timeout) is no longer uniform, and
the resulting average timeout (Exp[min(X,X)]) is much lower than the
midpoint of the timeout range.
To compensate for this, instead of sampling each endpoint timeout uniformly,
we instead sample it from max(X,X), where X is uniformly distributed.
If X is a random variable uniform from 0..R-1 (where R=high-low), then the
random variable Y = max(X,X) has Prob(Y == i) = (2.0*i + 1)/(R*R).
Then, when both sides apply timeouts sampled from Y, the resulting
bidirectional padding packet rate is now a third random variable:
Z = min(Y,Y).
The distribution of Z is slightly bell-shaped, but mostly flat around the
mean. It also turns out that Exp[Z] ~= Exp[X]. Here's a table of average
values for each random variable:
R Exp[X] Exp[Z] Exp[min(X,X)] Exp[Y=max(X,X)]
2000 999.5 1066 666.2 1332.8
3000 1499.5 1599.5 999.5 1999.5
5000 2499.5 2666 1666.2 3332.8
6000 2999.5 3199.5 1999.5 3999.5
7000 3499.5 3732.8 2332.8 4666.2
8000 3999.5 4266.2 2666.2 5332.8
10000 4999.5 5328 3332.8 6666.2
15000 7499.5 7995 4999.5 9999.5
20000 9900.5 10661 6666.2 13332.8
In this way, we maintain the property that the midpoint of the timeout range
is the expected mean time before a padding packet is sent in either
direction.
1. https://lists.torproject.org/pipermail/tor-relays/2015-August/007575.html
2. https://en.wikipedia.org/wiki/NetFlow
3. http://www.cisco.com/en/US/docs/ios/12_3t/netflow/command/reference/nfl_a1gt_ps5207_TSD_Products_Command_Reference_Chapter.html#wp1185203
4. http://www.cisco.com/c/en/us/support/docs/switches/catalyst-6500-series-switches/70974-netflow-catalyst6500.html#opconf
5. https://www.juniper.net/techpubs/software/erx/junose60/swconfig-routing-vol1/html/ip-jflow-stats-config4.html#560916
6. http://www.jnpr.net/techpubs/en_US/junos15.1/topics/reference/configuration-statement/flow-active-timeout-edit-forwarding-options-po.html
7. http://www.jnpr.net/techpubs/en_US/junos15.1/topics/reference/configuration-statement/flow-active-timeout-edit-forwarding-options-po.html
8. http://www.h3c.com/portal/Technical_Support___Documents/Technical_Documents/Switches/H3C_S9500_Series_Switches/Command/Command/H3C_S9500_CM-Release1648%5Bv1.24%5D-System_Volume/200901/624854_1285_0.htm#_Toc217704193
9. http://docs-legacy.fortinet.com/fgt/handbook/cli52_html/FortiOS%205.2%20CLI/config_system.23.046.html
10. http://wiki.mikrotik.com/wiki/Manual:IP/Traffic_Flow
11. https://metrics.torproject.org/dirbytes.html
12. http://freehaven.net/anonbib/cache/murdoch-pet2007.pdf
13. https://gitweb.torproject.org/torspec.git/tree/proposals/188-bridge-guards.txt
14. http://www.ntop.org/wp-content/uploads/2013/03/nProbe_UserGuide.pdf
15. http://infodoc.alcatel-lucent.com/html/0_add-h-f/93-0073-10-01/7750_SR_OS_Router_Configuration_Guide/Cflowd-CLI.html