[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 s7r):

 > Replying to [comment:35 s7r]:
 > 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).

 Of course, 1.8 GB memory for replay cache is unacceptable. But the way I
 thought of it it was never meant to hold 28 million elements. It should
 hold the same number of elements like it does now, but instead keep one
 more value in memory (`ALLOW_RESET_CACHE`) and choose a number for how
 many times we are willing to allow. When it stats, it starts with  value 1
 and after rand(16384, 16384*2) it gets cleared and reset, and number
 incremented to +1 = 2. When we hit the max. number of ALLOW_RESET_CACHE,
 we rotate the introduction point. So maybe I'm missing something but the
 memory requirement should not be much bigger as opposite to what we have
 now since we need to only keep in memory two things more: how many times
 we already reset the cache and for  how many times are we willing to reset
 it. Again, this is if course not perfect but I think it's better.

 Also, I don't think having the lifetime of introduction points as long as
 possible (based on time) like Guards have is a good idea, because simply
 introduction points are nothing like the Guards. While the Guard is
 (theoretically) know ONLY to the client (the Tor daemon running the onion
 service in this case), the introduction point is known to every client
 trying to connect to the onion service. From my point of view here we
 should assume that every client (visitor) of an onion service is a
 potential attacker. Even the ones that use authentication, are still under
 this threat (what if a genuine client gets squeezed with the door to
 handle the onion auth credentials, etc). So the longer you hold a
 connection to an introduction point the more time you give to an attacker
 to pull a guard discovery attack.

 Introduction points vs vanguards:
 - guard (first hop, layer 1 guard - not know to the onion service visitor)
 - 2nd hop (layer 2 guard - not known to the onion service visitor)
 - 3nd hop (layer 3 guard - not know to the onion service visitor and even
 for these we thought about making the 3rd hop always random because it's
 just before the rendezvous point which is selected by the client
 [potential attacker]. Even if in vanguards we decided 3rd hop static but
 for shortest period of time this node is still at least theoretically not
 directly known to the onion service visitor).

 IMO introduction points don't share the same property as the Guards and
 keeping them static only based on time for longer period of time while
 open the door for easier attacks. In vanguards I believe we already keep
 the circuit path to the introduction point static for some time, but not
 the introduction point itself.

 It's worth to keep the nodes we use static (like Guard, maybe even layer 2
 and 3 guards) because they are theoretically not known by the remote
 connecting client and we don't want to face a Sybil attack to choose a
 hostile node under these positions so that they become from theoretically
 not known to known. But introduction points are directly known and
 advertised in the descriptor.

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