Opened 6 years ago

Closed 4 years ago

#9273 closed project (implemented)

Brainstorm tradeoffs from moving to 2 (or even 1) guards

Reported by: arma Owned by:
Priority: High Milestone: Tor: 0.2.6.x-final
Component: Core Tor/Tor Version:
Severity: Keywords: tor-client, design, analysis, needs-proposal, 026-triaged-1
Cc: mikeperry Actual Points:
Parent ID: #11480 Points:
Reviewer: Sponsor:

Description

There are now many conflicting issues to consider when changing the default number of guards. I'd like to write a proposal suggesting we move to 2 (or even 1), but I don't think I'm ready to write the analysis section yet.

Here's a start:

Pro 1: Reduces chance of using an adversary's guard. This argues for 1, but 2 would still be a lot better. See Tariq's WPES 2012 paper for details.

Pro 2: Reduces impact from guard fingerprinting: if the adversary learns that you have the following n guards, and later sees an anonymous user with the same guards, how likely is it to be you? Said another way, a trio of guards produces a cubic, whereas a duo of guards produces a quadratic. Somebody should do the math to sort out the chance of having all possible trios of guards, followed by the expected uniqueness of a trio. I expect moving to 2 gives the majority of the benefit here.

Con 1: Increases the variance of performance. The more guards you have, the closer to average performance you'll be. Whereas if you have just one guard, your performance will be impacted a lot by that choice. It would seem that we need to raise the bar on getting the Guard flag if we move people to having just one guard.

Con 2: Moving to 1 guard will rule out a Conflux-style design. But 2 guards would still work fine.

What did I miss?

Child Tickets

Change History (9)

comment:1 Changed 6 years ago by nickm

Keywords: tor-client design analysis added
Priority: normalmajor

comment:2 Changed 6 years ago by hsn

I expect ppl to hand picking guard in case of one guard. Why have slower relay picked by random while you can get fastest nearest server.

comment:3 Changed 6 years ago by mikeperry

Cc: mikeperry added

FTR: I am in favor of both Conflux and reduced guards. Also note that Conflux will naturally compensate for the performance downsides of reduced guards. 2 seems a good choice for this reason.

I also did some back-of-the-envelope math for guard fingerprinting when we were discussing directory guards being separate or shared in https://trac.torproject.org/projects/tor/ticket/6526#comment:8. Basically, if we have 9 bits of guard entropy, that is equivalent to 512 uniform guard choices, and then you can use combinatorics from there. For two guards, https://www.wolframalpha.com/input/?i=512+choose+2 = 130,816 combinations, or about 17 bits of identifying entropy, versus 3 guards at 512 choose 3 = 22 million/25 bits. You could also compute the Shannon entropy directly the long way, but I think it should be the same.

Of course, my mental model of Paul Syverson just said "But that entropy metric doesn't reflect the fact that users will be more likely to have popular fast guards than unpopular slow guards, and this becomes even more pronounced with two guards rather than three. Tracking users with popular fast guards is harder than tracking users who get unlucky and pick one or more unpopular slow guards because the anonymity sets are larger for the fast guard users."

Usually when Paul gets inside my head like this, I just start thinking about something that would jeopardize his security clearance and he goes away. But in this case, I think he's right. It would be an even larger improvement than pure entropy metrics indicate.

comment:4 Changed 6 years ago by nickm

Keywords: needs-proposal added

I think that when Paul and Mike and Roger all agree, it's probably a good idea to move this way in 0.2.5.

This needs a proposal.

So, here are some tradeoffs to consider:

  • We need to make sure that the probability of choosing any given guard has a lower bound. If there are some guards that people pick with very small probability, that guard's users are going to stand out!
  • In practice, no guard's uptime is going to be 100%. So in reality, even in a 1-guard scenario people will have a primary guard, and a fallback guard that they use whenever that guard's down, and a fallback fallback guard, and so on. This means that fingerprinting based on complex guard sets will still be possible in the long term.
  • One idea we floated a while ago was deterministic guard grouping. Under this idea, you could still have k guards out of N possible guard nodes, but instead of there being N-choose-k possible groups of three to choose, there would only be N/k possible choices.
    • The guards would be put into groups by the authorities as part of the voting algorithm. These groups would probably want to be persistent somehow.
    • The advantages of this approach are:
      • You'd still get the reliability boost of multiple guards.
      • You'd avoid the "Fallback guard" problem noted above.
      • The fingerprinting opportunity would be limited, even more so than in the case where every user picks a node at random.
    • Intuitively, you might think that an attacker would want to manipulate the group-assignment process to get there to be groups full of completely attacker-controlled nodes. But I think that the rational behavior for the attacker would be to try to spread their nodes out among as many groups as possible.
      • It seems hard to prevent an attacker from manipulating a group assignment process, especially if groups are persistent over time and the attacker can take down old nodes and bring them back up with new identity/location.
      • So we should probably try to design a solid group assignment process, but we probably want to do our analysis here under the assumption that the attacker can manipulate the node selection process, and limit our worst-case scenario there.
    • On superficial analysis, I still like this "guard group" idea.
  • Probably we will need equations to analyze specific proposals here.

comment:5 Changed 5 years ago by nickm

Milestone: Tor: 0.2.5.x-finalTor: 0.2.6.x-final

comment:6 Changed 5 years ago by lunar

comment:7 Changed 5 years ago by nickm

Keywords: 026 added
Parent ID: #11480

comment:8 Changed 5 years ago by nickm

Keywords: 026-triaged-1 added; 026 removed

comment:9 Changed 4 years ago by nickm

Resolution: implemented
Status: newclosed

This has been done for a bit.

Note: See TracTickets for help on using tickets.