[tor-dev] Proposal: Tor with collective signatures

Sun May 1 05:30:11 UTC 2016

> On 1 May 2016, at 00:56, Nicolas Gailly <nicolas.gailly at epfl.ch> wrote:
> 
>>> 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.

Tor doesn't actually hard-code any keys in its source code.
It only includes hashed key fingerprints for authorities and fallback directories.

When Tor bootstraps:
1. Tor contacts a fallback directory, it compares the fingerprint of the public key the fallback directory sends to the hard-coded fingerprint,
2. Tor downloads a consensus, and downloads the authority keys required to validate the signatures on that consensus,
3. once Tor has validated the consensus, it uses the relays in the consensus.

In order to obtain the fallback directory mirror keys, you would have to add another step:
2b. Tor downloads the descriptors of each of the fallback directory mirrors

Descriptors are about 1.5KB on average, and connecting to several different fallbacks to download these descriptors could add significantly to bootstrap time.

It's worth noting that there's a cryptographic issue with using microdescriptors, which is that microdescriptors aren't signed by the private keys of each relay. Instead, they're authenticated by being included in a valid consensus. But the consensus that we have hasn't been validated.

So this means that CoSi needs to download the full descriptors, which are significantly larger than microdescriptors.

It's worth documenting this in the proposal, as it would be very easy to implement an insecure variant of CoSi that used microdescriptors.

It's also worth noting that the requirement is that Tor download a majority of authority keys, not all of them.
It's important that we also specify the number of fallback keys that need to be downloaded for the CoSi scheme.

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

As I describe above, the proposal needs to specify the fallback key download mechanism, and justify that it is secure.

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

This persistence of old tor relay versions is why we asked that fallback directory mirrors be up for the next 2 years.

However, it's worth noting that older versions of Tor were excluded from the network due to Heartbleed (April 2014).
It's possible that, in future, old tor relay versions may stay on the network for longer than 2 years.

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

I'm not convinced that the set of fallback directory mirrors is necessarily suited for CoSi.

Fallback directory mirror selection uses the following criteria:
* relay operators opting-in to be a fallback directory mirror,
* being on the same key, addresses, and ports, ideally for the life of the release, nominally the next 2 years,
* having good uptime, calculated as a decaying weighted average,
* having the Guard, Running, and V2Dir flags almost all the time, calculated as a decaying weighted average,
* having at least 3MB/s bandwidth, (one hundred times the expected additional load on a fallback directory),
* being able to serve the consensus within 15 seconds,
* not having more than one fallback with the same IP, family, or operator (contact info).
After these criteria are applied, we choose the 100 fallback candidates with the highest bandwidth.

Some of these criteria just don't seem that relevant to CoSi.

Others, like the stability criteria, are directly relevant - because they tell you how many fallbacks we expect to be up at any one time (95% when the 0.2.8 list was created). We expect the number of fallbacks that are up to decrease over time, but, since this is the first release with fallbacks, we don't know how rapidly their numbers will fall.

The fallback list has been selected so that even if only a small number of fallbacks are up, they can handle the extra load. Even if they are all down, tor will still bootstrap from the authorities, with only a few seconds' delay.

A reliable, practical design like this is a crucial part of the CoSi proposal. It determines how many witnesses should be required out of the total number, and what criteria should be used to select the list of witnesses.

It's also worth considering how much effort it would take to contact relay operators about CoSi.
I only asked operators about becoming a fallback directory mirror, and not any other potential uses of the list of fallback directories.
It took me several weeks just to send out these emails, and collate responses.

Operators will likely want to know about the version of Tor they'll need to run, and any additional bandwidth or CPU requirements. Knowing the additional bandwidth and CPU load would be useful as part of the proposal. If the fallbacks have to serve each others' descriptors in order for clients to obtain the fallback keys, this extra bandwidth needs to be accounted for.

If a descriptor is 1.5KB, and you need to download 100 of them, that's an extra 1.5MB at bootstrap time.
Microdescriptor consensuses are 1.3MB.
So that would mean increasing the additional bandwidth requirements for fallback directory mirrors from 20KB/s to 50KB/s.
This excludes the bandwidth costs of the CoSi scheme itself, which are hopefully much, much smaller.

(These are uncompressed figures, compression might also be a factor, but it doesn't seem to differ that much between microdescriptor consensuses and descriptors, it's about 45% for both.)

Please feel free to use this email or these ideas in any updates to the proposal.

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com
PGP 968F094B
ricochet:ekmygaiu4rzgsk6n

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 842 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20160501/f2a1811f/attachment-0001.sig>