[tor-dev] [Draft Proposal] Scalable Hidden Services

[Matthew Finkel]

On Wed, Oct 30, 2013 at 08:11:16AM +0000, Matthew Finkel wrote:
> On Mon, Oct 28, 2013 at 08:49:46PM +0000, George Kadianakis wrote:
...
> > It seems to me that an IP+Client adversary is always able to find the
> > number and status of HS-nodes. The proposed ways to fix this is to add
> > measures like random-circuit-disconnects and connecting to IPs
> > multiple times from a single HS-node. Both of these solutions seems
> > easy to get wrong and hard to prove secure. We should think more about
> > them!
... 
> 
> The more I think about this problem the more I convince myself we need
> another layer of abstraction between the client and the IP, perhaps
> proxy the INTRODUCE1 cell via the HSDir that is responible for the HS's
> descriptor and the client never need know the IPs. This requires a lot
> more thought (more than I can give it right now, at least).

To solidify this description, the idea is to take George's Intermediate
descriptor and encrypt everything using the symmetric key except the
Intro Point details. These would need to be encrypted with a key that
was exchanged with the HSDirs. Then, when a client requests a descriptor
from an HSDir, it receives everything it needs to send the INTRODUCE1
cell except it will not know the introduction points. It will be at this
point where the client sends the INTRODUCE1 payload encapsulated in
another cell (along with the hidden service's address so the HSDir knows
where to connect) to the HSDir. The HSDir then establishes a connection
with one of the introduction points and forwards the INTRODUCE1 payload
to the hidden service.

I want to like this tweak, but I don't think we gain enough from it,
alas. The main improvement is that a client will never know the
introduction points for a hidden service, therefore it will never be
able to estimate the size of the hidden service solely from its
descriptor, assuming the intro point section is padded to a prespecified
length or is sent to the HSDir separately. However, this is only a
slight hinderance for a Client+IP and will not prevent the information
leakage described by George, over time.

Assuming the HSDirs for a hidden service are sufficiently unpredictable
prior to the period, the main improvement this provides is the ability
to scale with respect to IPs without significant leakage to a Client+IP,
but this does nothing to prevent any correlation attacks that may exist.
But, again, over time with the one-hidden-service-per-intro-point a
client will still be able to recognize a hidden service failure even if
it may not know the size of a hidden service. Furthermore, this all
strictly depends on the randomness by which HSDirs become responsible
for a hidden service's descriptor.

Can this idea be improved to make it worthwhile and safer? What othere
modifications can we make to the rend protocol to improve the
"hiddenness" of an HS (without needing to go as far as the valet design)
while also improving usability/speed?