[tor-dev] HSDir hash ring modification

[Nick Mathewson]

On Fri, Aug 23, 2013 at 9:31 AM, Kang <td66bshwu at gmail.com> wrote:
> Hello.
> I was reading about hidden services and a thought occurred to me
> regarding the hash ring used in choosing and determining the HSDirs
> for a hidden service.
> As far as I can tell the hash ring is more or less static since a
> relay's position is determined by their identity key, which doesn't
> change.
> I'm also under the impression that the hash ring is only used for
> calculation of HSDirs of hidden services.
>
> I don't have a particular method in mind, but it seems to me that you
> could use the "time-period" value that is used in calculation of the
> service's descriptor-id to shuffle the ring.
> This would cause the ring to be different for each hidden service, and
> also make its order change periodically.
> I imagine in particular it would make onion address enumeration
> attacks more difficult, since an attacker wouldn't just be able to
> "cast a net" over the ring for all services.
>
> Can anybody see any problems or false assumptions with this?

So right now, the HSDir ring is built as a function of node IDs.  A
hidden service's position within that ring changes depending on a
function of the hidden service's ID (immutable) and time-period
(predictable).  The issue we'd like to solve is that if you know a
hidden service's ID, you can predict where it will be stored in the
ring at any given time in the future, and try to arrange to have
servers with identities close to that point.

So for example, suppose that Mallory want to DOS a hidden service with
ID "jellyandcrumpets.onion" next Thursday, right before the big
crumpet festival.

The descriptor IDs that this hidden service will generate on Thursday
are going to be:   (coding simplified)
 H1 =  H( jellyandcrumpets | H(Aug 29 2013, replica1) )
 H2 =  H( jellyandcrumpets | H(Aug 29 2013, replica2) )

And so all that Mallory needs to do is try to make sure that, by
Thursday, Mallory occupies the points in the HSDir ring right after H1
and right after H2.  Mallory does this by generating identity keys
until finding several that are right after H1, and several that are
right after H2.  Mallory then must run nodes with those identity keys
until they get the HSDir flag.  At that point, Mallory can refuse to
answer requests for the jellyandcrumpets service.

That's how it is now.



As I understand it, your proposed fix is to have the time-period also
used in sorting the nodes into the HSDir. So on Thursday, instead of
ordering the nodes in the HSDir ring by their public keys PK, we would
instead order the nodes in the ring by H(Aug 29 2013, PK).

But Mallory can still succeed.  All he must do is to choose public
keys such that H(Aug 29 2013, PK) is right after H1 or H2, and he can
succeed just as well at censoring jellyandcrumpets.onion service for
that day.



The real problem here is that time is predictable.  Not to put too
fine a point on it: we know what day it's going to be next Thursday
well in advance. :)

So long as the the <hidden service, hsdir> mapping depends only on
things things that Mallory can control (like the public keys of his
servers) and things  that Mallory can predict far enough in advance to
get the HSDir flag (like the hidden service's identity and the date of
the attack), then these attacks will remain feasible.

If we want to keep Mallory from knowing which PKs to run long enough
in advance to do a low-cost HSDir-based censorship attack, we can take
two approaches:
   * We make it higher-cost to have a server running with a given PK
and the HSDir flag on a chosen day.  We've already done this with
changes to the directory authorities in 0.2.4.10-alpha, in response to
the attack technique in the "Trawling for Tor Hidden Services" paper.
   * Have the mapping depend on some temporary value that the attacker
cannot know very far in advance.


The most obvious way to have such an unpredictable value is to have
the authorities decide on one for each time period a short time before
each time period begins.  But it turns out that collaboratively
generating random value is tricky, if you want to resist attacks where
one authority can influence the random value to give the results they
want.  Section 4 of http://freehaven.net/doc/casc-rep/casc-rep.pdf
discusses some difficulties and a possible workaround, but that
paper's pretty old, and I bet somebody's come up with a better answer
by now.

cheers,
-- 
Nick