[tor-dev] Defending against guard discovery attacks by pinning middle nodes

[Mike Perry]

A. Johnson:
> > It seems to me that we want to defend against (at least) two
> > different attacks here:
> > 
> > Sybil attack:
> ...
> > Coercion attack:
> 
> Yes, I also am currently thinking about the problem in this way.
> 
> >  Unfortunately, it doesn't really make sense to add two '5 day
> >  guards' in a circuit, since a Sybil adversary has equal chances to
> >  pop at the guard nearest to the HS.
> 
> Yup.
> 
> > * While more hops are useless for Sybil attacks, they actually help
> > against coercion attacks. Unfortunately, they only add 5 days per
> > extra hop to the time to deanonymization.
> 
> And yes again. In this model, an ultra-mega-secret HS should use a
> long chain of guards. Of course, at some point, it is easier to do a
> congestion attack to identify the first guard being used by the HS.
> That is still a win, though, in that such an attack takes more
> technical skill and effort.

I think this brings up another good point about hidden services that the
"you must use a single guard forever" model causes us to ignore.

Imagine if we had k-Conflux routing, where you could pick 1-k guards,
and send packets to a single exit or RP.

Under this model, congestion attacks would be more difficult, because
you have to also do the combinatorics to choke out the Choose(N, k)
combinations of k of N total guards. If you only choked a subset, conflux
would rebalance to the remaining free paths (assuming good, responsive
flow control).

> > * It seems that coercion attacks are noisy. At least in this case,
> > relays got seized (why?) and people got notified that something was
> > going on. It would be nice if we could make coercion attacks even
> > more noisy, so that adversaries can't do them without tipping off
> > the whole network.
> 
> I’m not optimistic about this. Surveillance is no good if the target
> is aware of it, and so it can be expected to be difficult to detect.
> 
> > * The more I think about this problem, the more I realize that our
> > solutions are quite hacky. Maybe guards are not the right layer to
> > fix this problem, and we should try to fix the guard discovery
> > problem in circuit establishment as Mike has been suggesting?
> > Unfortunately, the virtual circuits idea seems hard to analyze and
> > do securely.
> 
> What do you mean by "the guard discovery problem in circuit
> establishment”? Do you mean using some level of traffic padding to
> make it difficult to determine when your relay is directly observing
> an HS guard? This seems straightforward to do just by making every
> relay see the same type and number of cells in every non-terminal
> position in the circuit during circuit creation (some will have no
> effect, detectable only by the last relay). I do worry about how the
> cell RTTs could still leak your relative circuit position. Ignoring
> that, maybe you can make it so that the adversary either (i) has to
> start surveillance on an observed hop and hope that it is a relatively
> static guard close to the HS or (ii) has to wait until some relay is
> observed *multiple* times from the malicious relays to be sure that it
> is in some layer of guards for the targeted HS.

I think padding and other defenses against introducing active side
channels are fine longer-term plans, but I think what George means is
that we should re-design HS path selection specifically for this guard
discovery threat, taking it as a given that the adversary is able to use
*some* side channel to determine that it is in the path and knows its
position.

While I find passive timing attacks skeptical at scale, I am not so
crazy as to believe that it is impossible to *actively* encode a
reliable side channel in a traffic pattern that you control (which is
used in the HS guard discovery research). Conflux may also make these
types of side channels more difficult to construct, but I suspect that
just means you have to send more data as an attacker. Since you can send
a bunch of data at the HS for most application layer protocols (HTTP
POST comes to mind), this is probably not a huge barrier.


After reading your back-of-the-envelope calculations on node rotation
and guard lifetime for multi-tiered guards in your parent reply, I think
that it stands to reason that some topology like this is best (with
Conflux):

HS -> Guard_1 -> Guard_2 -> Guard_3 -> RP

The idea would be that Guard_3 would rotate on the order of hours,
Guard_2 would come from a set that is rotated on the order of days
(based on the expected duration for the adversary to become Guard_3), and
Guard_1 would rotate on the order of months (based on the expected
duration for the adversary to become Guard_2).

Based on your math in your parent reply, this now does strike me as
superior to what I actually proposed with "virtual circuits", since if
the whole virtual circuit had a lifetime of hours, you'd still have only
days before the adversary ended up in the Guard_2 position.

I would prefer if we had closed-form or code-based versions of this
calculation, though, so we could play with set sizes and lifespans for
the 3 hops. We also want to play with questions like "How many circuits
should we use at a time?" and "How big should the set of middle nodes we
choose from be?" Making all of that parameterized will help us tune it.
Heck, the surface might even be plottable or traversable with gradient
descent.


-- 
Mike Perry
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20141110/722752c4/attachment.sig>