Re: [tor-dev] Proposal: Tor with collective signatures

On 25 April 2016 at 07:32, Nicolas Gailly nicolas.gailly@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