On Fri, Aug 23, 2013 at 9:31 AM, Kang td66bshwu@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,