The HSDirs for a hidden service should not be predictable indefinitely into the future (#8244) · Issues · Legacy / Trac · GitLab

The HSDirs for a hidden service should not be predictable indefinitely into the future

When a hidden service chooses what HSDir relays to publish its hidden service descriptor to, it does it in a deterministic way based on day and .onion address. That way clients can do the same calculation to decide what HSDirs to contact when fetching the hidden service descriptor.

But a flaw in this approach is that anybody can predict what six HSDir relays will be responsible for a given hidden service, 22 days from now. There's no reason to have that property, and it makes attacks to temporarily censor a hidden service much more effective since you can e.g. choose the identity keys of your Sybils such that there exists a day in the next 30 days where you'll be running all six of the HSDirs for your target hidden service.

One solution would be for the directory authorities to produce a periodic random string that is unpredictable until they have produced it. Then put that string in the consensus.

The first issue is whether a single authority can play tricks where it waits to vote until it sees the votes from the other authorities, and then chooses its random string to produce the desired consensus random string. This issue is actually really serious, since I bet for any six adversarial HSDirs, there exists a random string that puts them in charge of the target hidden service. See all the contortions we went through in http://freehaven.net/anonbib/#casc-rep about generating a consensus random number; I hope we don't need as many contortions here.

The second issue is how we should handle transitions between epochs. One option is to post two random strings (today's and tomorrow's), and then each hidden service uses both of them. Surely there's a more efficient answer here.

I guess issue number three is how the directory authorities should vote on a thing that doesn't have granularity of one vote period. Do they all just vote the random string that they voted at the beginning of the day, for the whole day? If I'm an authority and I missed the first hour of the day, do I get to add my vote on the second hour (I think the answer has to be no)? What if there weren't enough votes to make a consensus in the first hour? If I come up as an authority and can't get a proper recent consensus, but now it's time to vote, what do I vote?

And lastly, how do we transition? I think hidden services would publish to the old ones and the new ones, until clients that don't know about the new way are obsolete. In the mean time that increases the exposure of the hidden service to an adversary who just wants to get one of the n HSDirs for the hidden service for that period. (Is getting some-but-not-all that bad?)

(This ticket is inspired by rpw's upcoming Oakland paper)