[tor-dev] is the consensus document unpredictable / unique?

Tue Jun 28 02:43:24 UTC 2016

> On 28 Jun 2016, at 06:16, Razvan Dragomirescu <razvan.dragomirescu at veri.fi> wrote:
> 
> 2. How would a Directory Authority be able to tweak its vote to generate multiple valid consensus documents? I'm not familiar with the voting process (just read about it a bit at http://jordan-wright.com/blog/2015/05/14/how-tor-works-part-three-the-consensus/ ) . Can a rogue DA pretend that it has knowledge of additional relays that the other DAs don't know about and tweak their fingerprints to try to match a precomputed hash? Do the DAs simply merge all relay lists with no other checks?

The consensus generation algorithm is deterministic, based on the content of the (up to) 9 votes. A majority of directory authorities need to vote for a relay to have it included in the consensus.

> Is there any legitimate situation where a single DA would know about a given relay?

Perhaps it's the only reachable directory authority from that relay. But, in that case, the other authorities would see that relay in a vote, and ask each other authority for a copy of its descriptor. If they don't get the descriptor, they won't vote for the relay.

> Or am I missing some random data that the DA includes in its vote that could be used for this?

Yes. Not random data, but an authority can freely choose to vote for (or not vote for) certain attributes, like relay flags, or other values. Sometimes, changing a vote in this way will change the resulting consensus. If 4/9 authorities vote for an attribute, the final authority gets to choose whether it goes in or not.

There are 7000 relays in the consensus.
https://consensus-health.torproject.org/

Each relay can be included or excluded from the consensus (the Running flag).
Each relay can have zero or more of the following 6 flags: Fast Exit Guard HSDir Stable V2Dir.
(For simplicity, I'm ignoring the Valid and BadExit flags.)

By my quick count, 12 flags could be manipulated this way out of the first 50 relay entries.
Extrapolating, 12 * 7000 / 50 = 1680 flags in the entire consensus which depend on a single authority's vote.
Therefore, each authority could affect 1680 / 9 = 186 consensus flags on average.

This gives each authority the ability to produce 2 ^ 186 possible consensus outcomes.

But it gets worse - there are 5 bandwidth authorities.
Each bandwidth authority can choose an arbitrary value as the measured bandwidth of a relay, and the median value is included in the consensus.
There are 6900 measured relays in the consensus.
https://collector.torproject.org/recent/relay-descriptors/
On average, this means that a bandwidth authority can choose from a range of bandwidth values for 1 in 5 relays, or 1380 relays.

Bandwidths in the consensus are reported to 3 significant figures. Let's assume an authority can arbitrarily choose the final one of those figures.

This gives each bandwidth authority the ability to produce 10 ^ 1380 possible consensus outcomes, which must be multiplied by the 2 ^ 186 possibilities above.

Therefore, the number of possible consensus outcomes that can be produced by one malicious authority exceeds the number of possible hash outputs, for almost all current cryptographically secure hashes. While an authority could in theory generate a consensus with any hash, this is bounded by available processor time to hash consensuses.

Here's an efficient algorithm for producing consensus hashes:
* hash most of the consensus, up to the last point where you can make a bandwidth change, or a few flag changes
* store the state of the hash
* use the state to quickly compute the hash of each consensus variant
* if you haven't found a hash that does what you want, try changing something slightly further back, and repeat

The reason that this isn't secure for hidden service descriptor assignments to hidden service directories is that there are only ~5000 possible hidden service directories. So you only need to be able to generate ~5000 hashes to get the descriptor you want on your hidden service directory.

It might work with your scheme, if you use a large enough hash, that takes long enough to calculate, and you use all the bits of the hash, and you check the dates you're signing, and you rate-limit signing. But that means a lot of moving pieces which can go wrong. And it likely means some attacks you haven't thought of.

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com
PGP 968F094B
ricochet:ekmygaiu4rzgsk6n

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 842 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160628/9836f778/attachment.sig>