[tor-dev] Hidden Service Scaling

[Paul Syverson]

On Wed, Oct 09, 2013 at 03:02:47PM +0100, Christopher Baines wrote:
> On 09/10/13 11:41, Paul Syverson wrote:
> >>>> These two changes combined should help with the two goals. Reliability
> >>>> is improved by having multiple OP's providing the service, and having
> >>>> all of these accessible from the introduction points. Scalability is
> >>>> also improved, as you are not limited to one OP (as described above,
> >>>> currently you can also have +1 but only one will receive most of the
> >>>> traffic, and fail over is slow).
> >>>  
> >>> Do you see any disadvantages to this design?
> >>
> >> So, care needs to be taken around the interaction between the hidden
> >> service instances, and the introduction points. If each instance just
> >> makes one circuit, then this reveals the number of instances.
> > 
> > You said something similar in response to Nick, specifically you said
> > 
> >    I believe that to mask the state and possibly number of instances,
> >    you would have to at least have some of the introduction points
> >    connecting to multiple instances.
> > 
> > I didn't understand why you said this in either place. Someone would
> > have to know they had a complete list of introduction points to
> > know the number of instances, but that would depend on how HS descriptors
> > are created, stored, and distributed. From whom is this being hidden?
> > You didn't state the adversary. Is it HS directory servers, intro point
> > operators, potential clients of a hidden service?  I don't see why
> > any of these necessarily learns the state or number of instances
> > simply because each intro point is chosen by a single instance
> > (ignoring coincidental collisions if these choices are not coordinated).
> 
> To clarify, I was interpreting the goal as only the service operator
> should know the number of instances. In particular, the adversary here
> is the introduction point. If hidden service instances only ever create
> one circuit to each introduction point, each introduction point knows
> the number of instances of every service it is an introduction point
> for, as this is the same as the number of circuits for that service.
> 

I'm missing something. Suppose there is a hidden service with ten
instances, each of which runs its own introduction point. How do any
of these ten introduction points know the number of instances because
they each see a single circuit from the hidden service?

> > Also, in your response to Nick you said that not having instances share
> > intro points in some way would place an upper bound on the number of
> > instances. True, but if the number of available intro points >> likely
> > number of instances, this is a nonissue. 
> 
> I don't really follow your reasoning.

If there are a thousand possible introduction points for a given HS,
if each instance runs say two intro points, then that bounds the
number of instances at 500 (ignoring that the intro points for different
instances overlap q.v. below).

> 
> > And come to think of it,
> > not true: if the instances are sometimes choosing the same intro points
> > then this does not bound the number of instances possible (ignoring
> > the number of HSes or instances for which a single intro point can
> > serve as intro point at one time).
> 
> Ok, but I was assuming the current behaviour of Tor, which I believe
> prevents instances using some of the same introduction points.

Why? If two different instances of the same HS operated completely
independently (just for the sake of argument, I'm assuming there are
good reasons this wouldn't happen in reality) then they wouldn't even
know they were colliding on intro points. And neither would the intro
points.

> 
> > Also, above you said "If each instance just makes one circuit". Did
> > you mean if there is a single intro point per instance? 
> 
> No, as you could have one instance that makes say 3 circuits to just one
> introduction point. This can help, as it can hide the number of
> instances from the introduction point.

Off the top of my head, I'm guessing this would be a bad idea since
the multiple circuits with the same source and destination will create
more observation opportunities for either compromised Tor nodes or
underlying ASes routers, etc. I don't have a specific attack in mind,
but this seems a greater threat to locating a hidden service than
would be revealing the number of instances to an intro point (which
I still don't understand your argument that this gets revealed anyway).

> 
> > Hard to say specifically without exploring more, but in general I
> > would be more worried about what is revealed because circuits are
> > built to common intro points by different instances and the intro
> > points can recognize and manage these, e.g., dropping redundant ones
> > than I would be because the number of intro points puts an upper
> > bound on instances.
> 
> I don't quite understand the last part, but regarding introduction
> points handling more that one circuit for the same service. I think that
> having this helps possibly hide information (like the number of
> instances). This does depend on also allowing one instance to use
> multiple circuits, otherwise, some information would be given away.
> 

I think our miscommunication above is just reiterated here. Hopefully
something I have said will spark you to recognize the confusion (and
indicate to you which one of us is having it) and you can tell me.

> I might try creating a wiki page on the Tor wiki to collect all of the
> information in this thread, as it might be a nice reference for discussion.
> 

Sure. I tend to do things more via email, but a chacun son gout.
Note that I'm swamped for at least the next week so sorry if I
don't respond any time soon.

aloha,
Paul