[tor-bugs] #26294 [Core Tor/Tor]: attacker can force intro point rotation by ddos

[Tor Bug Tracker & Wiki]

#26294: attacker can force intro point rotation by ddos
------------------------------+--------------------
     Reporter:  arma          |      Owner:  (none)
         Type:  defect        |     Status:  new
     Priority:  Medium        |  Milestone:
    Component:  Core Tor/Tor  |    Version:
     Severity:  Normal        |   Keywords:
Actual Points:                |  Parent ID:
       Points:                |   Reviewer:
      Sponsor:                |
------------------------------+--------------------
 Currently, an onion service's intro points each expire (intentionally
 rotate) after receiving rand(16384, 16384*2) intro requests.

 Imagine an attacker who generates many introduction attempts. Since each
 intro attempt can take its own path to the target intro point, the
 bottleneck will be the introduction circuit itself. Let's say that intro
 circuit can sustain 500KBytes/s of traffic. That's 1000 intro requests per
 second coming in -- so after 24ish seconds (rand(16,32)), that intro point
 will expire: the onion service will pick a new one and start publishing
 new onion descriptors.

 If the intro circuit can handle 1MByte/s, then rotation will happen after
 12ish seconds.

 With three intro circuits, each receiving intro requests at a different
 rate, we could end up changing our descriptor even more often than this.
 There are at least four impacts from this attack:

 (1) Onion services spend energy and bandwidth generating new intro
 circuits, and publishing new descriptors to list them.

 (2) Clients might get the last onion descriptor, not the next one, and so
 they'll attempt to introduce to a circuit that's no longer listening.

 (3) The intro points themselves get a surprise 16k-32k incoming circuits,
 probably plus a lot more after that because the attacker wouldn't know
 when to stop. Not only that, but for v2 onion services these circuits use
 the slower TAP as the circuit handshake at the intro point.

 (4) The HSDirs get a new descriptor every few seconds, which aside from
 the bandwidth and circuit load, tells them that the onion service is under
 attack like this.

 Intro points that can handle several megabytes of traffic per second will
 keep up and push the intro requests back to the onion service, thus
 hastening the rotation. Intro points that *can't* handle that traffic will
 become congested and no fun to use for others during the period of the
 attack.

 The reason we rotate after 16k-32k requests is because the intro point
 keeps a replay cache, to avoid ever responding to a given intro request
 more than once.

 One direction would be to work on bumping up the size of the replay cache,
 or designing a different data structure like a bloom filter so we can
 scale the replay cache better. I think we could succeed there. The
 benefits would be to (1) and (2) and (4) above, i.e. onion services won't
 spend so much time making new descriptors, and clients will be more likely
 to use an onion descriptor that's still accurate. The drawback would be to
 (3), where the hotspots last longer, that is, the poor intro point feels
 the damage for a longer period of time.

 Taking a step back, I think there are two directions we can go here.
 Option one, we can try to scale to handle the load. We would focus on load
 balancing better, like reacting to an attack by choosing super fast intro
 points, and either choosing fast middle nodes too, or some fancier
 approach like having multiple circuits to your intro point. Option two, we
 recognize that this volume of introduction requests represents a problem
 in itself, and try to introduce defenses at the intro point level. Here we
 focus on proof of work schemes or other ways to slow down the flow, or we
 improve the protocol to pass along hints about how to sort the intro
 requests by priority.

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/26294>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online