On 04/29/2016 05:13 PM, Tom Ritter wrote:
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.
First of all, you have to remember that the Tree layout is not important regarding the signature generation, but is merely here as an optimization. It enables us to restart CoSi with a new Tree layout with a better Leader. Secondly, in the context of Tor + CoSi, the leader would be selected as one of the D.A. (in RR fashion or fixed, see below). From my limited point of view, the D.A.s are considered to be longterm and highly available servers.
One issue for discussion is who should initiate CoSi protocol rounds and at what times. For example, each of the 9 DAs (or whatever subsetis 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?
Sure. But "ignore a request" would mean that every witnesses refuse to sign? In that case, the leader must have a way to determine if the signature has not been issued because the consensus document is already in the process of being signed or because the consensus document looks suspicious. Here both approaches will return valid signature as long as the CoSi system has been given a valid consensus document.
A related issue for discussion is whether it could be problematic ifthere 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.
The question is related to what was discussed during the Tor dev meeting about the Tor Transparency idea (https://lists.torproject.org/pipermail/tor-dev/2014-July/007092.html). There's been some concerns regarding having different signatures for the same content (https://trac.torproject.org/projects/tor/wiki/org/meetings/2016WinterDevMeet...).
In any case, the specifics rules for signing (see the above paragraph.) should be tailored to the Tor needs and should be discussed more in-depth with Tor experts (I'm not one;);
3.4 Optional: Break-the-glass Emergency Directory Adjustments I love me some fancy crypto, but I question the need for this feature at all, let alone more complex versions of it.
Tim Wilson-Brown:
This looks like a "golden key" from a distance, and, if there's a bug in the implementation, it could well become one.
I'd want to make sure we really needed this feature before implementing it.
One issue I've been told during the Tor dev is the *reactivity* of D.A. operators when a (or multiple) relay are detected as being malicious. This feature is a proposition to alleviate the need to have at least 5 D.A. ready to sign. I've also been told that Roger was interested in the idea at but it would be great if some D.A. operators could say more about this indeed.
About the "golden key" perspective, the rules determine exactly what this emergency process can do, and these rules will be publicly enforced by every witnesses. Moreover, this emergency process will still be publicly logged so any attack against a few D.A.s that uses this emergency process can easily be detected. But I agree these rules are delicate and as written in the proposal, they need much more discussion (offlist
4.2 Benefits
Technically, it is quite easy to implement witness cosigning if thegroup 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.
It was a comparison regarding other multi-signature approaches ;) A CoSi signature can be verified in "one-shot" against the aggregate public key of all witnesses. Moreover, using the Fallback Directory mirrors https://trac.torproject.org/projects/tor/wiki/doc/FallbackDirectoryMirrors) as witnesses, the Tor clients won't need any additional keys as they would already be included in the source code.
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.
Exactly.
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.
I'm afraid I don't see what you mean here. Are you talking about the "locally set" threshold of witnesses that must have participated in the CoSi signature in order to be considered valid ? -> Yes: If an attacker has successfully fingerprinted a Tor client by knowing its "threshold", that means the attacker already has corrupted the *majority of the D.A.s* (because the consensus document still need to be signed as usual by a majority of D.A.s), AND at least *threshold* witnesses. -> No: Could you elaborate then please ? :)
But since the client needs the public keys, it will download each of them via some unspecified mechanism?
The second version of the proposal emphasizes more on this subject. Specifically, the CoSi set of witnesses could be defined as a subset of the Fallback directory mirrors (https://trac.torproject.org/projects/tor/wiki/doc/FallbackDirectoryMirrors), so that way a Tor client can already verify CoSi signatures using the embedded keys.
==== 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.
That's why we started emphasizing on using the Fallback Directory mirrors because they already have been selected using some specific criterias that the Tor people already chose. If a *very old* Tor client get back online, and *if* the Fallback Directory mirrors list is a new disjoint set from the *very old* set, the new CoSi witnesses list also has changed radically. Thus, there's a high probability that the CoSi signature will be considered invalid, that does not mean the client can't use Tor (it could be a flag in the torrc "AcceptInvalidCosiSig"); but the client will see this warning and that he should definitely update to a more recent version for a better security. See section 3.2.3 for more on this.
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
We already designed last year a prototype using CoSi with CT. We'd be happy to talk more with you about that, so let's keep in touch :)
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
I'm always happy to answer any more concerns / feedback you might have :)
Thanks a lot,
Nicolas