[tor-dev] Proposal: Tor with collective signatures

[Tom Ritter]

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
engineering.

>>>     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?
> 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.

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
time.

>>>     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.
> 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/2016WinterDevMeeting/Notes/ConsensusTransparency).
>
> 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
>>> 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.
> 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.

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
>> 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 ? :)


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. =)

-tom