[tor-dev] Proposal: Tor with collective signatures
tom at ritter.vg
Mon May 2 19:50:42 UTC 2016
On 30 April 2016 at 09:56, Nicolas Gailly <nicolas.gailly at epfl.ch> wrote:
> 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.
Yup, DAs are longterm and available servers.
Now it's my understanding that the parent nodes were needed to
communicate to the children, and this was a part of the optimized
protocol you had developed. If a parent goes offline, permanently, one
needs to update the tree and reorganize it. This won't cause a change
to signature _verification_ but will cause a change to signature
_generation_ - nodes will need to be told 'your new parent is X', and
they need to be told that outside the normal tree-based communication.
So - doable, and doesn't affect clients, but does require some
>>> 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
>>> 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
>>> mechanism ensuring that another leader takes over if the prior one
>> 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
> Here both approaches will return valid signature as long as the CoSi
> system has been given a valid consensus document.
For my point of view - a consensus should never not-be-signed because
it's suspicious. CoSi nodes aren't the determination of what's
suspicious. That's some other process entirely separate to this.
I see it as more simple: I get a request to sign document A
(identified by some hash). Am I already signing it, or signed it in
the past? If so, ignore it. If not, sign it. I would need support for
running many instances of the multi-step signing protocol at the same
>>> A related issue for discussion is whether it could be problematic if
>>> are two or more distinct collective signatures for a given directory
>>> consensus, and whether it is a problem if distinct subsets of 5 DAs
>>> (perhaps accidentally) produce multiple slightly different, though
>>> valid and
>>> legitimately-signed, consensus documents at about the same time. In
>>> words, does Tor directory consensus “need” strong consistency with a
>>> 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
> The question is related to what was discussed during the Tor dev meeting
> about the Tor Transparency idea
> There's been some concerns regarding having different signatures for the
> same content
> 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;);
Hmmmmm. I *think* I understand this concern. AIUI the issue is
Consensus A and B - which differ only by Authority N who signed B but
not A due to network timing or clock skew. Both valid consensuses.
It seems to me we would want to log them both. We want to track all
signatures made by a DA key. But perhaps I haven't thought closely
enough about this.
>>> 4.2 Benefits
>>> Technically, it is quite easy to implement witness cosigning if the
>>> 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
>>> painful and inefficient. Worse, every client would need to check all
>>> 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
> as witnesses, the Tor clients won't need any additional keys as they
> would already be included in the source code.
Ah okay, so it is just one signature verification? That's great if so.
>> 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
>>> 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
>> 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*
> -> No: Could you elaborate then please ? :)
Yes. Hardly an easy attack, but if Alice has set her threshold to N+20
signers from the normal N, I can feed a client consensus documents
with N+19 and N+20 witnesses and if the first doesn't stick and the
second does - I've a good idea it's Alice (or someone else who has set
their threshold to N+20).
Teor's comments about Fallback Dirs are better than ones I could write. =)
More information about the tor-dev