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

[Tim Wilson-Brown - teor]

Hi Razvan,

> On 26 Jun 2016, at 07:52, Razvan Dragomirescu <razvan.dragomirescu at veri.fi> wrote:
> 
> I couldn't find a detailed description of the Tor consensus, so I'm checking that my understanding of it is correct. Basically, would it be correct to assume that the consensus document (or a hash thereof) for a date in the future is an unpredictable value that will also be unique to all nodes inquiring about it at that time?

The future values of consensuses can be influenced by each of the 9 directory authorities, individually. A malicious authority has ~5 minutes between receiving other authorities' votes and creating its own to calculate a vote that creates a consensus hash that achieves a desired outcome.

While it can't control the exact consensus hash, it can choose between many possible hashes, only limited by the available computing time. And it can farm out these computations to other computers.

A shared random commit-and-reveal scheme, like the one in proposal 250, gives each authority a single choice: to reveal, or not reveal. This means that a malicious authority can only choose between two different output hashes, rather than choosing between many millions of possible hashes.

This is why OnionNS switched from using a hash of the consensus, to the shared random value in the consensus.

> On 26 Jun 2016, at 08:18, Tom van der Woerdt <info at tvdw.eu> wrote:
> 
> The consensus has signatures from all directory operators on it, and computing those ahead of time requires a lot of private keys. Because they also all contain the date, they're all unique. So yea, they're both unique and unpredictable.

The signed part of the consensus is the (hash of) everything up until the first signature.
So while the consensus eventually contains up to 9 signatures, and some legacy signatures, it's not created or initially distributed between authorities that way.

There's a few reasons you shouldn't rely on the hash of the signatures:
* while the consensus is produced by up to 9 authority signatures, each signature is only produced by 1 authority;
* a client only needs 5 of the 9 signatures to use a consensus, so it's not guaranteed to have them all;
* signatures are distributed encoded, in PKCS1-padded format that ignores additional whitespace  (and various other extraneous characters), so a malicious authority can control (some bits in) the hash of its own signature;
* PKCS1.5-padding allows arbitrary pseudorandom inputs as part of the padding, so a malicious authority can try multiple values for this pseudorandom input until it gets a has that it wants;

A malicious authority also has ~5 minutes between receiving other authorities' signatures and creating its own to calculate a signature that creates a consensus + signatures hash that achieves a desired outcome.

This doesn't necessarily mean that your scheme will be insecure, but it would need to be constructed very carefully to avoid giving one malicious authority the ability to break it. And you might want to get some cryptographers to review it.

(I can imagine an attack where a service creates many keys in advance with random values as the consensus hash, and a malicious authority then tries to vote or sign to match the consensus hash to one of the random values used to create one of the keys.)

On the other hand, you could wait until there's a shared random value in the tor consensus, and use it. This may be ready a lot sooner than the entire next-generation hidden service protocol (proposal 224). It could be released in 0.2.9, and it could be running on enough authorities some time in 2017.

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/20160627/85bc99df/attachment.sig>