[tor-dev] Proposal: Tor with collective signatures

[Tom Ritter]

On 25 April 2016 at 07:32, Nicolas Gailly <nicolas.gailly at epfl.ch> wrote:
> They can / should
> probably
>     publish logs of the statements they witness or simply make available
> a public
>     mirror of everything that its tree roster has been asked to sign.

This mirror can be 'unprotected' in the sense that you just stick the
documents into a directory listed on the web. Any further protection
(mirroring, append-only log) is unnecessary because the security of
the scheme relies on a multitude of weakly-protected witnesses - not
the security of an individual witness.


> The mechanism is similar for
>     witnesses that went offline. The parent of an offline witness will
> set the bit
>     in the bitmap of the failed witness.

You mention this in Cons as well - it seems like the parents in the
tree need to be more carefully selected than the leaf nodes or the
tree can degrade heavily over time as they leave.


>     One issue for discussion is who should initiate CoSi protocol rounds and
>     at what times.  For example, each of the 9 DAs (or whatever subset
> is online)
>     could independently initiate CoSi rounds on each directory consensus
> event,
>     producing up to nine separate, redundant collective signatures on each
>     directory consensus.  Alternatively, the common case might be for
> one of the 9
>     DAs to be the CoSi initiator at a given time, with a round-robin
> leader-change
>     mechanism ensuring that another leader takes over if the prior one
> becomes
>     unavailable.

Can't CoSi nodes ignore a request to initiate on a consensus document
they're already in the process of signing?


>     A related issue for discussion is whether it could be problematic if
> there
>     are two or more distinct collective signatures for a given directory
>     consensus, and whether it is a problem if distinct subsets of 5 DAs
> might
>     (perhaps accidentally) produce multiple slightly different, though
> valid and
>     legitimately-signed, consensus documents at about the same time.  In
> other
>     words, does Tor directory consensus “need” strong consistency with a
> single
>     serialized timeline, as Byzantine consensus protocols are intended
> to provide
>     - or is weak consistency with occasional cases of multiple concurrent
>     consensus documents and/or collective signatures acceptable?

Such a situation should be a primary use case of CoSi. If an attacker
submits a fraudulent consensus for signing it _should_ be signed and
logged - that's the primary motivation. Having that signing process
fail cause there's already a document in progress would be a poor
design.


> 3.4 Optional: Break-the-glass Emergency Directory Adjustments
> ...
> With even fancier crypto, even the witnesses would not
> necessarily need
>     to know, but that’s beyond the scope of this proposal and its
> desirability may
>     be questionable at any rate.

I love me some fancy crypto, but I question the need for this feature
at all, let alone more complex versions of it.


> 4.2 Benefits
>
>     Technically, it is quite easy to implement witness cosigning if the
> group
>     of witnesses is small. If we want the group of witnesses to be
> large, however
>     – and we do, to ensure that compromising transparency would require
> not just a
>     few but hundreds or even thousands of witnesses to be colluding
> maliciously –
>     then gathering hundreds or thousands of individual signatures could
> become
>     painful and inefficient. Worse, every client would need to check all
> these
>     signatures individually.

That seems like a very painful cost to pay - I would expect this would
significantly hurt the performance of Tor in constrained spaces:
mobile phones, IOT devices. I had hoped signature checking was a
one-shot, not for each individual key.


> The key technical contribution of our
> research is a
>     distributed protocol that makes large, decentralized witness
> cosigning groups
>     practical. This decentralized approach enables the security of the whole
>     system to scale with the number of witnesses.

Additionally, you (or maybe not you, but your protocol) results in a
_single_ signature, not N signatures. So there's a size benefit
compared to a standard 'N of M' scheme where each element is it's own
signature.

>     Not only does this system dramatically increase the cost of successfully
>     deploying an attack on the DA (the attacker would have to corrupt a
> large
>     majority of the witnesses), it also decreases the incentive to
> launch such an
>     attack because the threshold of witnesses that are required to sign the
>     document for the signature to be accepted can be locally set on each
> client.

This does; however, give a pretty straightforward fingerprinting attack.


>     Using CoSi requires the clients to have the list of public keys of
> all the
>     witnesses embedded in the software, like certificate pinning. In
> order to
>     reduce the size of this CoSi certificate, we embed the aggregated
> public key
>     of all the witnesses and a hash representing the root of a Merkle tree
>     containing the public key of all the witnesses. Using the
> certificate this way
>     provides an universally-verifiable commitment to all the witnesses’
> public
>     keys, without the certificate actually containing them all.

But since the client needs the public keys, it will download each of
them via some unspecified mechanism?


==== General Comments

My biggest comment/concern about this is determining the set of
signers, how you update that set, and how you handle the long-tail of
users with old sets of signers. You mention this in 3.3 - that signers
can be baked into a particular version of Tor. 0.2.4.23 was released
in Aug, 2014 and the 0.2.4 branch has ~1500 relays in the network. As
you ay - you can go with a smaller number of handpicked ones to
increase reliability or a larger number of less reliable ones, with
the latter being preferable.

Where do the signers come from? Presumably we'd make up some criteria
and say 'these relays are signers' and then fix them as signers and
update that list every major version or something... but what's
turnover for relays on a 3-year timespan? I think suggesting a
criteria for choosing signers and performing the turnover analysis
will be very important to see if this approach is feasible.


Aside from that - for folks who don't know I'm working on Certificate
Transparency Gossip, which some people see as a 'competitor' to CoSi
in the CT space. I agree CoSi reduces the need for Gossip in CT; but I
would be happy to see CoSi developed and deployed for CT logs.  I just
don't think it will be for many of the trusted logs (e.g. Google's)
for operational reasons - and I want to ensure the correct behavior of
these logs in as privacy-preserving way as I can. So I keep working on
that.  Gossip for Tor would be radically different from Gossip in the
web ecosystem (to the point where it may not work). CoSi may be a
better fit.

-tom