[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:  asn
     Type:  defect                               |         Status:
                                                 |  merge_ready
 Priority:  Medium                               |      Milestone:  Tor:
                                                 |  0.4.2.x-final
Component:  Core Tor/Tor                         |        Version:
 Severity:  Normal                               |     Resolution:
 Keywords:  tor-hs, tor-dos, network-team-       |  Actual Points:  6
  roadmap-august, security, 042-should           |
Parent ID:  #29999                               |         Points:  7
 Reviewer:  dgoulet                              |        Sponsor:
                                                 |  Sponsor27-must
-------------------------------------------------+-------------------------

Comment (by asn):

 Replying to [comment:33 arma]:
 > Replying to [comment:27 asn]:
 > > We actually had not heard that replay caches are there to protect
 against traffic analysis attacks. How does the attack work? I considered
 that identical INTRO2 cells could be used as a signal to the HS guard, but
 since they are end-to-end encrypted the singal should not be visible,
 right?
 >
 > The encryption protects the payload, but not the communications metadata
 (timing and volume).
 >

 Thanks for the explanation. The attacks indeed make sense.

 > I worry about two impacts from replays by the intro point:
 >
 > * Capture an intro2 cell and later play it repeatedly, to create a
 pattern at the onion service's guard, at a time of our choosing. The
 replay cache at the onion service doesn't completely resolve this concern,
 because the intro point gets to send the cells before the onion service
 can realize they're replays. But if Mike succeeds at removing every side
 channel from the world, then the replayed intro2 cells are "legitimate"
 (i.e. expected and correctly formed) cells so without a replay cache there
 is no way to realize that they're not wanted.
 >

 I think this side-channel attack is kinda interesting, and it gives even
 more reason to change the current design since (as s7r mentioned) it's
 currently easy to make onion services rotate their introduction points,
 and hence place the attacker in the right position to carry out this
 attack.

 Also, introduction points will always be in position to carry out this
 attack since they can send arbitrary cells to the end of the circuit (the
 HS). If those cells are not expected, the service will drop them (and
 issue a log warning) but the attack will still be carried out since the
 signal will reach the guard.

 IMO, this attack is a reason to increase the lifetime of the introduction
 points, but not a reason to drop this patch.

 > * Capture an intro2 cell and later play it repeatedly to create a
 pattern at the rendezvous point. This one is directly resolved by a replay
 cache at the onion service side. The impact is a bit subtle/indirect, but
 it would for example allow attacks where later you discover which
 rendezvous point a given introduction attempt used.
 >

 This is indeed an attack that becomes possible if this patch gets merged,
 and creates a tradeoff here that is worth discussing.

 I feel like an adversary that would end up launching this attack is
 dealing with a super advanced (almost artificial) scenario: The adversary
 does not know the identity of the onion, but still they capture INTRO2
 cells and then replay them to learn the rendezvous point. Now let's assume
 that they can instantly pair an introduction with a rendezvous point,
 what's next? Maybe if they later learn the actual identity of the onion
 service, they can learn that a given rendezvous circuit was destined to
 that onion? And what's next? Maybe they can do traffic correlation to
 identify the identity of the onion or of the client? But this ends up
 being a super strong attacker suddenly, and would probably have other ways
 to achieve the same goal.

 Also, the patch of this ticket won't allow the introduction point to
 generate arbitrary signals to the rendezvous point, since the replay cache
 needs to be reset before a replay is possible. And a replay cache can only
 be reset by legitimate (non-replay) traffic. So this attack assumes a
 popular onion service, and the attacker can only replay each cell once, so
 they can only create a signal of one rendezvous circuit per cache reset
 (except if they also replay other intro2 cells, but those will be going to
 other rendezvous points).

 So I can see how this attack can work, but it still seems pretty remote,
 compared to the one that is currently possible (attacker forces HS to use
 an evil intro, and then does the above attack, or collects statistics, or
 whatever), and hence I still feel like the patch in this ticket is
 superior. As always, it's a tradeoff.

 ----

 Replying to [comment:35 s7r]:
 > Which is why I think configuring the replay cache to limit on a "hybrid"
 threshold (time + introductions) as described in comment:11 will not
 interfere with the issues and concerns described above. It's just about
 choosing the right variable min and max values so that introduction points
 are not rotated too fast but also cannot send unlimited replays
 (introductions) during their time-based lifetime. A "hybrid" limitation as
 described will simply enhance the current behavior instead of radically
 changing it.

 Hm. I still don't see how the hybrid construction can help here: IMO the
 future ideal scenario is that introduction points will last for ever
 (kinda like guards) to resist Sybil atacks, and hence adding any rotation
 parameter apart from time will make rotation happen faster which is no
 good.

 In particular, adding 'introductions' as a rotation parameter, opens us up
 to the attack of this ticket, where an adversary can force your intros to
 rotate because of too many introductions. The only reason that the design
 from comment:11 works out (in paper) is because the intro will rotate
 after 28 million introductions which is a huge number and will never
 happen (at least in theory, and if it happens it's bad). The problem with
 that is that a replay cache that holds 28million elements will be around
 1.8 GB of memory (according to my over-the-envelope computations in
 https://github.com/torproject/tor/pull/1163/commits/6ef1ac5eed85d7cf3cafa1797dc1003912d1a63c)
 which doesn't really work out in practice....

 It is the case that we might want to make the replay cache of this patch
 even bigger since it can currently hold 150k-300k elements for a memory
 overhead of 8.4MB to 16.8MB. Do you think we can afford to make them
 bigger? Perhaps double them or triple them or even bigger? An onion
 service should have about 6 of these right now (and it will become 3 when
 we do #22893).

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