Proposal 162: Publish the consensus in multiple flavors

[Nick Mathewson]

On Fri, Jun 12, 2009 at 11:10:09PM -0400, Roger Dingledine wrote:
> On Fri, May 15, 2009 at 01:05:41PM -0400, Nick Mathewson wrote:
> > Filename: 162-consensus-flavors.txt
> > Title: Publish the consensus in multiple flavors
> 
> Looks good. We should do it.
> 
> >    Our past approach to cases like this has been to shovel all of
> >    the data into the consensus document.  But this is rather poor
> >    for bandwidth.  Adding a single SHA256 hash to a consensus for
> >    each router increases the compressed consensus size by 47%.  In
> >    comparison, replacing a single SHA1 hash with a SHA256 hash for
> >    each listed router increases the consensus size by only 18%.
> 
> SHA256's are still huge. It's a real shame there aren't accepted hash
> functions that use only 20 bytes.

I think we're going to have to live with this, unless we want to be
crypto-weirdos and say that our hash function is the first 20 bytes of
SHA256 or something else horribly under-analyzed like that.

> >    In addition to the consensus currently served at
> >    /tor/status-vote/(current|next)/consensus.z ,
> 
> Are we expecting to make this url deprecated at some point? I guess not
> until 0.2.1.x is obsolete, which is a long time from now.
> 
> In the mean time, do we really want to force caches to mirror the
> old-school consensus URL, and also the "ns" consensus flavor URL, even
> though they'll always be the same document? Seems to me that we could
> start out with only one consensus flavor, the "microdesc" one.

My plan was to have the "ns" URL be synonymous with the old URL, so
that once the authorities are serving at the ns URL, caches can start
fetching it.  They don't need to download the document more than
once.  The old URL will only need to be an alias for the "ns" URL.

> >     The algname part of a signature describes what algorithm was
> >     used to hash the identity and signing keys, and to compute the
> >     signature.  The algorithm "sha256" MUST be recognized;
> >     signatures with unrecognized algorithms MUST be ignored.
> >     (See below).
> 
> I'm still curious about Sebastian's question here. I guess the
> plan is to use sha256 sigs for now, and if

"when" ;)

>                                             we decide we don't like
> that hash function, we a) make up a new consensus flavor that hashes
> microdescriptors with whirlpool++, b) get all the authorities to upgrade
> to a consensus method that agrees to build that flavor and list the
> new flavor in the consensus-index file, hashed by whirlpool++ as well
> as sha256, and c) teach clients to fetch the new flavor and make sure
> the ... make sure the what? Is there anything in the consensus itself
> that shows what digest the authority used when signing? It seems like we
> want to make sure the "Signature*" lines from the consensus-index get
> used in the appropriate consensus flavor too.

You mean, we should have new consensus document types include
extensible signature lines of the format currently specified for the
consensus-index?  I think that's a good idea.  We can't trivially do
it for the existing networkstatus format without a bit of intense
hacking, though, since existing clients will freak out if they fetch a
consensus with directory signatures they can't verify.

The right place to specify this is probably when introducing a new
consensus flavor: I'll amend 158 to say that we use this format.

> More generally, at some point we should specify our upgrade path plan,
> so we're less likely to learn later that it has holes.

Indeed we should.  That's what I'm hoping the current
xxx-what-uses-sha1.txt document turns into.

> Also, in that case, caches that haven't upgraded can still be tricked
> by an authority into fetching a colliding consensus flavor document,
> since they'd only be checking the sha256. That's not so bad since clients
> should be able to check the hashes themselves. In theory it's a DoS worry,
> since an attacker could make it hard to find a copy with the right valid
> hashes and signatures; but in practice I don't see an authority actually
> being able to pull off that attack without somebody noticing and fixing
> it out of band. And we're only vulnerable to an authority doing it,
> right (assuming honest but not-upgraded relays, and nobody mitm'ing the
> connection from relay to authority)?

So the attack would run like this:
  - Mallory (the hostile authority) guesses what a future consensus
    will be.  This is hard unless there is way less information in
    everyone else's vote than we might have thought.  Note that the
    each consensus includes a vote-digest line from every voter, so
    that unless Mallory can guess all other authorities' votes
    exactly, he's going to have trouble here.

    (Mallory can make more than one guess, but unless he guesses
    the actual consensus, he loses.  He can influence the consensus by
    voting on it, but his influence is not unlimited.)

  - Mallory figures out an alternate consensus that he wants the
    authorities to publish instead.

  - Mallory generates a hash collision between the future consensus
    and the desired target consensus.  He can modify the future
    consensus most easily through introducing stuff in the contact
    line of his vote, and through 

    (Note that this step is going to be computationally expensive, and
    it's got to happen on a tight schedule: the longer Mallory spends
    generating a collision, the likelier it is that no vote he can
    make will make the consensus confirm to his expectations.)

  - The authorities vote.  Mallory now has a signed document
    purporting to be a consensus that shares the SHA256 of the actual
    consensus.  Any caches and clients that look only at the SHA256 of
    the document will believe it to be properly signed.

I think this attack probably wouldn't work so well in practice because
of the difficulty of guessing a consensus in time, but please check my
reasoning.

The part of this that worries me is that Mallory could set the
fresh-until time indefinitely far in the future, so that if the attack
ever _did_ work, the affected clients would stay compromised
indefinitely, or until they upgraded.

We could mitigate that part of this attack by imposing a maximum on
the freshness of any descriptor, I guess.

Alternatively, if we are really worried here, we could have each
authority include a random nonce in its vote so that there is no way
to predict what the vote-digest fields of a consensus will be in
advance.  This is a cheap fix, and it would cut the attack window
down to the voting delay time, so Mallory would need to find a hash
collision in about 5 minutes.

> >     The consensus index is made available at
> >        /tor/status-vote/(current|next)/consensus-index.z.
> 
> You should be aware that due to a bug in the current code, that url is
> valid already:
> 128.31.0.34:9031/tor/status-vote/current/consensus-index
> 
> Not a huge problem though, I think.

Not a huge problem, so long as we don't have caches try to fetch it
until all the authorities are upgraded.

yrs,
-- 
Nick