[tor-dev] Proposal: Tor with collective signatures

[Nicolas Gailly]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160430/b87631c5/attachment.sig>