[tor-dev] Proposal: Authenticating sendme cells to mitigate bandwidth attacks

[teor]

Hi,

Comments inline:

> On 13 Feb 2018, at 12:26, Roger Dingledine <arma at mit.edu> wrote:
> 
> Filename: xxx-authenticated-sendmes.txt
> Title: Authenticating sendme cells to mitigate bandwidth attacks
> Author: Rob Jansen, Roger Dingledine
> Created: 2016-12-01
> Status: open
> 
> …
> 
> 2.7 Long >3-hop Circuits
> 
>   The adversary could use a circuit longer than three hops to cause more
>   bandwidth usage across the network. Let's use an 8 hop circuit as an
>   example.

You should use 7 hops as an example, because 8 hops doesn't work on the
network due to RELAY_EARLY limits.

And you should define what you mean by "hop".
(Is it 1-based? Are you counting links, or relays? Does the client count?)

>   Adversary:
>   16 transfers to create the circuit
>   2 to begin the two exit connections
>   2 to send the two GET requests
>   ---
>   20
> 
>   Network:
>   128 transfers to create the circuit
>   62 to begin the two exit connections (assumes two for the exit TCP connect)
>   32 to send the two GET requests to the website
>   15000 for requested data (until the stream and circuit windows close)
>   ---
>   15222
> 
>   The adversary could also target a specific relay, and use it multiple
>   times as part of the long circuit, e.g., as hop 1, 4, and 7.
> 
>   Target:
>   54 transfers to create the circuit
>   22 to begin the two exit connections (assumes two for the exit TCP connect)
>   12 to send the two GET requests to the website
>   5000 for requested data (until the stream and circuit windows close)
>   ---
>   5088
> 
> …
> 
>   How shall we version the sendme payload so we can change the format of
>   it later? Right now sendme payloads are empty. Here's a simple design:
>   we use five bytes in the payload, where the first byte indicates the
>   sendme payload version (0 in the original design, and 1 once we've
>   implemented this proposal), and the rest of the payload is formatted
>   based on the payload version number: in this case, it's simply the
>   four bytes of digest.
> 
>   Is there a better way to version the payload, e.g. a way that is
>   already standard in other parts of the design, so we aren't adding
>   a new paint color to keep track of on the bike shed?

This is pretty much the standard way that we version other payloads.

IP addresses in NETINFO cells have custom versioning, because IPv4
used to be mandatory. But almost everything else uses the zero byte at the
start of an empty payload as the first version.

> …
> 
> 3.3. Making sure there are enough unpredictable bytes in the circuit
> 
>   So far, the design as described fails to a very simple attacker:
>   the client fetches a file whose contents it already knows, and it
>   uses that knowledge to calculate the correct digests and fake its
>   sendmes just like in the original attack.
> 
>   The fix is that the exit relay needs to be able to add some randomness
>   into its cells. It can add this randomness, in a way that's completely
>   orthogonal to the rest of this design, simply by choosing one relay
>   cell every so often and not using the entire relay cell payload for
>   actual data (i.e. using a Length field of less than 498), and putting
>   some random bytes in the remainder of the payload.

This will break implementations that assume the payload is always full,
until the final cell. Let's check that Tor doesn't make this assumption.

>   How many random bytes should the exit relay use, and how often should
>   it use them? There is a tradeoff between security when under attack,
>   and efficiency when not under attack. We think 1 byte of randomness
>   every 1000 cells is a good starting plan

Should the rate be a consensus parameter as well?

> , and we can always improve
>   it later without needing to change any of the rest of this design.

I suggest that the 1 byte of randomness goes somewhere in the first few
cells of the 1000. That way, clients that only request small amounts of data
(like chutney) break early.

>   (Note that the spec currently says "The remainder of the payload
>   is padded with NUL bytes." We think "is" doesn't mean MUST, so we
>   should just be sure to update that part of the spec to reflect our
>   new plans here.)

Tor doesn't check the padding.

> 4. Deployment Plan
> 
>   In phase one, both sides begin remembering their expected digests,
>   and they learn how to parse sendme payloads. When they receive a
>   sendme with payload version 1, they verify its digest and tear down
>   the circuit if it's wrong. But they continue to send and accept
>   payload version 0 sendmes.
> 
>   In phase two, we flip a switch in the consensus, and everybody starts
>   sending payload version 1 sendmes. Payload version 0 sendmes are
>   still accepted.
> 
>   In phase three, we flip a different switch in the consensus, and
>   everybody starts refusing payload version 0 sendmes.
> 
>   (It has to be two separate switches, not one unified one, because
>   otherwise we'd have a race where relays learn about the update before
>   clients know to start the new behavior.)
> 
>   We'll want to do a bunch of testing in chutney before flipping the
>   switches in the real network: I've long suspected we still have bugs
>   in our sendme timing, and this proposal might expose some of them.

I suggest we do testing on private test networks as well.
Chutney isn't very good at supplying latency.

>   Alas, this deployment plan leaves a pretty large window until relays
>   are protected from attack. It's not all bad news though, since we
>   could flip the switches earlier than intended if we encounter a
>   network-wide attack.
> 
> …

T