[tor-dev] Tor with collective signatures
Nicolas Gailly
nicolas.gailly at epfl.ch
Thu May 26 13:22:21 UTC 2016
Hi all,
Finally, after a while, here's a revised version of the proposal :)
This version should clarify some of the previously discussed issues on
the thread:
+ the selection of the witnesses,
+ the evolution of the set of witnesses,
+ more details about exceptions
+ some basic bandwidth computations,
+ small tweaks
Eager to hear your comments as always :)
Thanks,
Nicolas
PS: If you want to jump in directly, here's my rough CHANGES.md:
- 3.2.1
+ Changed to Witness selection
+ Incremental deployment paragraph
- 3.2.2
+ Operations added One DA = One Leader
+ Added Tree generation and tree passing
+ Strength / weakness leader selection
- 3.3 Removed Fallback directory mirrors + flag
+ different signature for backward compatibility
- 3.4 Handling failure of witnesses
+ handling failure during round also
- 3.5 Refusing to sign
- 5.2 Tree format
- 5.3 Bandwidth section
- 4.1 Changed cons
- 6 Moved Integration to Compatibility
<------------ BEGIN ------------>
Title: Tor Cosi
Author: Nicolas GAILLY, DeDiS lab, EPFL
Created: 09.03.2016
Status: draft
Version: 0.3
0. Introduction
This document describes how to provide and use a decentralized witness
cosigning mechanism in order to gain proactive transparency and public
accountability for the Tor consensus documents. Directory
Authorities (DA)
send their document to this set of witnesses and embed the signature
within the document. Tor relays and clients can choose to refuse a
consensus document if it has not been accepted and signed by a threshold
of witnesses.
1. Overview
A weakness of the current DA system is that if any 5 of the 9 DAs’
keys are stolen or coerced they could be used to sign fake directories
that the attacker might use secretly in another part of the world to
compromise Tor clients in the attacker’s domain. We propose to address
this class of attacks by incorporating decentralized witness cosigning
(CoSi) into the directory signing process, which ensures that any
consensus document must be not only signed by appropriate DAs, but also
publicly witnessed, signed and logged by a larger group of servers
acting
as witnesses, before clients will accept the directory.
A Tor relay or client expects to receive an additional "CoSi"
signature alongside the consensus document. They verify if the signature
is correct and whether a sufficient number of witnesses attested
that the
consensus document is valid or not. The Tor project would fix such a
threshold in the default configuration but users and relay operators are
free to adjust this value to their own preferences. In order to verify
the signature, they need to have the individual public keys of all the
witnesses beforehand. This "CoSi certificate" can be embedded in the
software in the same way certificate pinning does.
2. Motivation
Tor's DAs are comprised of 9 servers (and one extra for the bridges):
four of them are in the US and 5 of them are in the EU. Attacking these
central and vital points of the Tor network is clearly within the
reach of
state level adversaries if they were to collaborate. Recent stories
about
surveillance show that such a collaboration is already happening.
For example, let's imagine a situation where a state-level attacker
secretly coerces and/or steals the private keys of 5 of the 9 DAs, takes
them back to the Republic of Tyrannia where they control the ISPs
and the
country’s Internet connectivity to the rest of the world. The government
embeds those keys in their “Great Firewall” type devices, and uses
them to
secretly MITM attack targeted Tor users within Tyrannia by giving them
correctly-signed but completely false views of the Tor directory in
which
all of the available relays are run by the Tyrannian authorities. Since
this attack does not attack the consensus documents that the legitimate
DAs are regularly broadcasting to the rest of the world, neither the Tor
project nor anyone else outside of Tyrannia will have the opportunity to
see or promptly become aware of the fake consensus documents, and
not many
people even inside Tyrannia might have the opportunity to detect the
attack if it is carefully targeted against the small number of suspected
activists and journalists the government does not like.
The main goal of CoSi applied in Tor should be to ensure consensus
document transparency: that is, ensure the property that any consensus
document that any Tor client anywhere will accept has been observed and
logged by a significant number of parties throughout the world, so that
any misuse of a quorum of 5 DA keys anywhere will be quickly detectable
(soon, if not necessarily during the signing process itself).
3. Design
The first part of the section will talk more about the architecture of
a "CoSi" system and the second part will go into more detail about how
such a system can be integrated in Tor. For more details, please
refer to
the main CoSi research paper [0].
3.1 Simplified Architecture
First, the list of witness's public keys constitute the "CoSi
certificate" that can be used to verify a signature; it contains the
list
of individual public keys and the aggregate key. Then the leader forms
the tree out of the list of witnesses and run the CoSi protocol. The
tree
is only there for performance reasons and can be reconfigured at any
point
in time without affecting security. The leader then includes the CoSi
signature (which uses Schnorr signatures) in the consensus document.
Clients can then verify the consensus document using the aggregate
public
key of the "CoSi certificate".
A CoSi signature have two components:
- Schnorr signature
- Exceptions: bitmap of length equal to the size of the witness
group used by absent witnesses or refusing-to-sign witnesses (see
3.5).
Besides contributing to the signing, each witness can and should
perform any readily feasible syntactic and semantic correctness
checks on
the leader’s proposed statements before signing off on them. They
can/should probably publish logs of the statements they witness or
simply
make available a public mirror of everything that its tree roster
has been
asked to sign.
3.2 CoSi in Tor
3.2.1 Witness selection
CoSi relies on a list of decentralized cosigning witnesses, an
optional role to be supported by a future version of the standard Tor
relay software. The set of witness servers will initially be
defined as a
list of the DAs and a list of servers that satisfy some specific
criteria.
Those criteria are similar as the ones used for the selection of the
Fallback Directory Mirrors [2]. Specifically, the set of relays
that are:
* Opting to be a CoSi witness (and to generate an ed25519 key),
* Having stable keys, IP addresses, and ports, ideally for the life of
the release, nominally the next 2 years,
* having demonstrated good uptime, calculated as a decaying weighted
average,
* not having more than one witness with the same IP, family, or
operator (contact info).
One way to form an initial witness list is to contact first the Fallback
Directory Mirrors to see if they accept to endorse this new role and
then
if not enough operators agree on this, we can start searching for others
operators. Of course, managing such an organization takes time and
one can
expect the first list of witness to be ready only after a few months.
For deployment, one general strategy is to start with low threshold t,
i.e. t = 1-10% of N, where N is the number of witnesses in the CoSi
certificate. Once the witness set is operating, depending on the
evolution of the set (how many servers failed ? what is the frequency of
their failure ? etc), we can slowly and conservatively increase the
security parameters N and t. The maximum value of N would have to be
decided in further discussion. The threshold can be adapted using the
statistics gathered from the previous iterations. If 80% of the
witnesses
were consistently and continually available and the threshold is
only 20%,
then it makes sense to higher up this security parameter.
3.2.2 Operations
Each time a DA, acting in its role as CoSi leader, initiates a
collective signing round, the leader forms a communication tree. One
criteria that can be played with except the branching factor is the
latency between witnesses. One can collect information about the
communication latencies between the witnesses and construct a
shortest-path spanning tree using this data in order to reduce the
global
latency of the system.
Once the tree is setup then the signature process happens for each
consensus document. The leader starts by generating the tree out of the
witnesses. The tree can be generated out of a fixed branching factor and
is basically represented as an array of indices out of CoSi certificate.
The leader then sends down the tree to the its children and starts the
multi-step CoSi round.
The CoSi protocol produces a collective signature in response to the
initiation of the protocol by a leader. This signature is then included
in the consensus document so clients don't have to request it from
another
party.
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. This approach is not the most
efficient but likely to be the simplest, and we do not expect the small
inefficiency caused by the redundant collective signing to be a
problem in
practice. 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. This approach would eliminate redundant collective signing
operations in the common case at the cost of perhaps unnecessary
complexity.
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?
As far as our understanding of Tor goes, there does not seem to be any
particularly strong consistency requirements between the different DAs’
perspectives. Therefore, the simplest approach would be that all DAs
independently act as leaders to produce different collective
signatures on
the same consensus documents. This approach does not require any
synchronization between DAs and enable directly each DA to service the
CoSi-signed consensus document to the Tor network. Later it may be worth
exploring automated leader-election mechanisms and/or stronger
consensus-consistency mechanisms, but there does not seems to have a
need
for such a complexity right now.
3.3 Evolution of the CoSi set of witnesses
One obvious solution for the evolution of the CoSi set of witness lies
into the version-ing mechanism of Tor. A particular Tor client version
would be associated with a particular cosigning group whose keys are
embedded into the source code of this Tor version. A client will
have the
latest CoSi set keys when and only when its Tor client would be
upgraded -
just like the list of directory authorities.
Using this mechanism, a leader still have to produce valid CoSi
signature for each version used by the clients that are supported. For
example, if the policy is that witness sets change at most once per
year,
and Tor clients are supposed to be supported up to 2 years old, then a
leader has to provide up to 2 different CoSi signatures, one for each of
the two recent witness lists. The duration of support for a Tor version
has to be the same as the availability time we expect from relay
operators
that are selected to be witness.
The strength of this mechanism is its simplicity. One the other hand,
if the witness set in fact proves to evolve too quickly, the DAs may
have
to juggle multiple witness sets in order to retain compatibility with
older Tor clients.
3.4 Failure of witnesses
A simple design to handle the case where one or more witnesses are
down is to leverage the already existing measurements from the Tor
network. For example, if a witness relay does not have the "Running"
flag
[4], then the leader excludes it from the tree before starting a new
round. When the witness relay gets back online, it will have to wait
some
time before being included again in any further CoSi round. The
"Running"
flag seems a good starting point as a suggestion because the CoSi system
can then recover quickly from failed nodes, but other possibilities such
as the "Stable" flag or a simple timeout might be worth exploring
too. The leader launching a round on subset of the initial witness list
will have to toggles the bit on the bitmap of the final CoSi
signature on
the indexes of the absent witnesses. The indexes are referenced by the
CoSi certificates.
If a witness is to fail during a CoSi round, a simple mechanism is to
make the parent of the failed witness announce the failure to the
leader.
The leader will then restart a round with a new tree that does not
contains the failed witness. The leader also have to toggle the bit
corresponding to the failed witness in the exception bitmap.
3.5 Refusing to sign
If a witness does not want to sign, it should raises an administrative
alarm in its public log or contact a DA. The witness should also toggles
the bit at its index in the bitmap. Its index is determined as the index
in the list of witnesses from the CoSi certificate. The client will then
see a "1" bit in the bitmap, and will subtract the corresponding public
key of the witness from the aggregate public key. That way, the
client is
still able to verify the signature and it knows about which witnesses
refused to sign off. 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.
3.6 Optional: Break-the-glass Emergency Directory Adjustments
In case of emergency, the delay caused by having to coordinate among 5
DAs in order to make anything happen (i.e. excluding a set of malicious
nodes) can be problematic.
This section proposes a mechanism in which the CoSi witnesses can
accept and witness not just “full consensus” documents (signed by 5
DAs),
but can also accept “emergency adjustments”, which are
highly-constrained
deltas (diffs) to an existing full consensus document signed by a
smaller
threshold of DAs, e.g., 2 or even just 1. For example, the CoSi witness
cosigning rules might require that an emergency directory-adjustment
must:
- be a diff against a “fresh”, recent full consensus document (perhaps
*the* most recent one),
- can make no modifications to the full consensus other than some
pre-defined operations such as decreasing bandwidth weights assigned
to relays,
- cannot affect the directory-wide total bandwidth weight by more than
X% (e.g., 1% or .1%).
These suggestions are just a few imaginable rules to get the idea
across; the “right” rules would of course need much more
discussion. This
way, if one or two DAs discovers or even strongly suspects an attack of
some kind, they can take emergency countermeasures against the
attack and
be able to roll them out to clients quickly without having to get a
full 5
DAs out of bed - but because the delta-consensus is still
witness-cosigned
automatically by (perhaps) all the DAs and a number of additional
trusted
relays, we get the strong accountability provision that the use of
such a
“break-the-glass” emergency provision will immediately become known
to the
other DAs as soon as they do get out of bed.
Such a break-the-glass emergency adjustment mechanism could be
designed, if desired, so that ordinary clients and relays cannot
immediately tell the difference between a directory consensus
produced via
the normal threshold of 5 DAs and one that was produced as a delta
via the
emergency adjustment mechanism. Only the witness cosigners would
necessarily need to know which collectively-signed directories were
authorized via the full consensus procedure or via a break-the-glass
adjustment. So if it’s important to keep it secret from the general
public the precise reason for a particular directory update, that can be
accommodated. Only the more-trusted group of witness cosigners (and
obviously all the DAs themselves) would necessarily know the precise
origin and administrative justification of a given directory update.
With
even fancier crypto, even the witnesses would not necessarily need to
know, but that’s beyond the scope of this proposal and its desirability
may be questionable at any rate.
4. Security implications
4.1 Cons
Since the structure is a tree, if any node fails, there must be some
failover mechanisms to reconstruct a tree without the failed node.
Since
the DA reach consensus every hour [1], and following the design in 3.4,
the availability problem should not be an issue.
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. The key technical
contribution of our research is a distributed protocol that makes large,
decentralized witness cosigning groups practical. This decentralized
approach enables the security of the whole system to scale with the
number
of witnesses.
Not only does this system dramatically increase the cost of
successfully deploying an attack on the DA (the attacker would have to
corrupt a large majority of the witnesses), 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.
4.3 Differences between CoSi and Certificate Transparency
Prior transparency mechanisms have two weaknesses. First they do not
significantly increase the number of secret keys an attacker must
control
to compromise any client device, and client devices cannot even
retroactively detect such compromise unless they can actively
communicate
with multiple well-known Internet servers. For example, even with
Certificate Transparency, an attacker can forge an Extended Validation
(EV) certificate for Chrome after compromising or coercing only three
parties: one Certificate Authority (CA) and two log servers. Since many
CAs and log servers are in US jurisdiction, such an attack is clearly
within reach of the US government. If such an attack does occur,
Certificate Transparency cannot detect it unless the victim device has a
chance to communicate or gossip the fake certificate with other
parties on
the Internet – after it has already accepted and started using the fake
digital certificate. In the case of Tor Transparency, the attack is
harder
because the attacker would have to compromise the three parties plus a
majority of Directory Authorities but facing a state-level adversary the
threat is still plausible. One way to increase the difficulty of the
attack is to make sure the logs servers are scattered in different
places
of the world.
Second, the attacker can still evade transparency by controlling the
client’s Internet access paths. For example, a compromised Internet
service provider (ISP) or corporate Internet gateway can defeat
retroactive transparency mechanisms by persistently blocking a victim
device’s access to transparency servers elsewhere on the Internet.
Even if
the user’s device is mobile, a state intelligence service such as
China’s
“Great Firewall” could defeat retroactive transparency mechanisms by
persistently blocking connections from a targeted victim’s devices to
external transparency servers, in the same way that China already blocks
connections to many websites and Tor relays.
Using CoSi requires the clients to have the list of public keys of all
the witnesses embedded in the software, like certificate pinning. In
order
to reduce the size of this CoSi certificate, we embed the aggregated
public key of all the witnesses and a hash representing the root of a
Merkle tree containing the public key of all the witnesses. Using the
certificate this way provides an universally-verifiable commitment
to all
the witnesses’ public keys, without the certificate actually containing
them all.
5. Specifications
5.1 Protocol
We will describe quickly the protocol here; for a more detailed
explanation, please refer to the academic paper [0]. The setup is as
described in 3.2.1. The protocol in itself consists of four phases:
- Announcement: The leader broadcast down the consensus document to its
children, which in turn also broadcast to their children,etc.
- Commitment: When the leaves of the CoSi tree get the consensus
document,generate its random value v(i) and the corresponding
commitment V(i) and sends V(i) up to its parent. If a leaf refuses to
sign this consensus document, it does not create any commitment. Each
intermediate node aggregate all the commitments of their children, add
their own commitment (or nothing if it refuses to sign) and send the
result up in the tree. The root gets the aggregated commitment V
of all
signing witnesses.
- Challenge: The root then compute the challenge c = H( m || V ), with
m being the consensus document and H being a collision resistant
hash function that returns a scalar, and distribute the challenge down
the tree like in the Announcement phase.
- Response: Starting from the leaves, each witnesses compute its
response
r(i) = v(i) - c * x(i), where x(i) is the long term private key of the
witness. If the witness refuses to sign, it simply set the n-th bit of
the bitmap to "1", where n is the index of the witness in the "CoSi
certificate" (the list of all individual public keys). Each
intermediate
nodes in the tree aggregate the responses and the bitmap of all its
children, aggregate with its own response/bitmap and send that up
in the
tree. At the end of the protocol, the root gets the aggregated
response
r.
The signature is the tuple (c,r) and must be included in the consensus
document. If no exceptions occurred (i.e. the bitmap contains all "0"s),
the signature can be verified using the aggregate public key of all
witnesses using standard Schnorr verification algorithm [3]. If an
exception occurs, the client needs to lookup the indexes where the
bitmap
contains "1"s. The client then lookup the corresponding public keys
(from
the list of public keys of witnesses) and subtract each of them from the
aggregate public key. The client can then use this reduced public key to
verify the signature as usual.
5.2 Format
+ The "CoSi certificate" is a list of all witnesse's ed25519 public
keys and the aggregate public key of all individual public keys.
+ A CoSi tree is a list of indexes out of the CoSi certificate. It
seems reasonable to pick the indexes as 16-bits unsigned integers. In
order to make this representation maximally space efficient, the tree
needs to be a complete K-ary tree [5].
+ A CoSi signature contains:
- the challenge c, an ed25519 scalar
- the response r, an ed25519 scalar
- the bitmap of exceptions, whose length is equal to the number of
witnesses.
+ The messages sent during the four following phases are as follow:
- Announcement: consensus document
- Commitment: an ed25519 curve point
- Challenge: an ed25519 scalar
- Response: an ed25519 scalar and the exception bitmap
5.3 Bandwidth
Let's compute the cumulative bandwidth required by a witness to
participate in a CoSi round with a tree having a branching factor BF.
- tree: N * 2 bytes
- Announcement: consensus = 1,500 KB * (BF+1)
- Commitment: ed25519 point 32 * (BF+1) bytes
- Challenge: ed25519 scalar 32 * (BF+1) bytes
- Response: (ed25519 scalar + bitmap N bits) * (BF+1) bytes
The announcement phase clearly dominates so we can approximate the
bandwidth required for one round: 1.5 * (BF+1) MB. Since the consensus
document is generated every hour, then we 1.5*(BF+1) / 3600 MB/sec.
For BF = 5, the bandwidth is equal to 2 KB/sec. The bandwidth
requirement are that low such that there is no additional bandwidth
requirement on the witness selection criteria.
6. Compatibility
First of all, integrating CoSi would *not* immediately affect the
fundamental structure or function of the current DAs: there could
still be
9 of them, of which any 5 can authorize the release of a new consensus
document, as they do now. Secondly, CoSi would not necessarily change
anything about how the 9 DAs decide on how to compute these directory
consensus documents; e.g., it would not prevent the DAs from working
together to block the inclusion of (or assignment of
bandwidth-weight to)
relays that might be perceived by the DAs as doing bad things. Finally,
full backward compatibility with old Tor clients and relay software
may be
maintained by treating the new CoSi-generated collective signature
as just
an additional signature that gets attached to and distributed with
consensus documents. It may be treated as a special “10th virtual
DA” that
does not help authorize decisions but just publicly witnesses the output
of the regular 9 DAs. Old client and relay software can simply ignore
that new collective signature, whereas new software might look for
it and
over time gradually increase the threshold number of witnesses it
expects
to see.
7. Implementation
Implementation in Go is open source at:
https://github.com/dedis/cothority
8. Performance
9. Acknowledgements
This proposal has received some valuable feedback from Bryan Ford,
Linus Gasser, Ismail Khoffi, Philipp Jovanovic, and Ludovic Barman.
A. References
[0] http://arxiv.org/pdf/1503.08768v3.pdf
[1] https://collector.torproject.org
[2]
https://trac.torproject.org/projects/tor/wiki/doc/FallbackDirectoryMirrors
[3] https://en.wikipedia.org/wiki/Schnorr_signature
[4]
https://tor.stackexchange.com/questions/423/what-are-good-explanations-for-relay-flags
[5] https://en.wikipedia.org/wiki/K-ary_tree
-------------- next part --------------
Filename: tor_cosi.txt
Title: Tor Cosi
Author: Nicolas GAILLY, DeDiS lab, EPFL
Created: 09.03.2016
Status: draft
Version: 0.3
0. Introduction
This document describes how to provide and use a decentralized witness
cosigning mechanism in order to gain proactive transparency and public
accountability for the Tor consensus documents. Directory Authorities (DA)
send their document to this set of witnesses and embed the signature
within the document. Tor relays and clients can choose to refuse a
consensus document if it has not been accepted and signed by a threshold
of witnesses.
1. Overview
A weakness of the current DA system is that if any 5 of the 9 DAs’
keys are stolen or coerced they could be used to sign fake directories
that the attacker might use secretly in another part of the world to
compromise Tor clients in the attacker’s domain. We propose to address
this class of attacks by incorporating decentralized witness cosigning
(CoSi) into the directory signing process, which ensures that any
consensus document must be not only signed by appropriate DAs, but also
publicly witnessed, signed and logged by a larger group of servers acting
as witnesses, before clients will accept the directory.
A Tor relay or client expects to receive an additional "CoSi"
signature alongside the consensus document. They verify if the signature
is correct and whether a sufficient number of witnesses attested that the
consensus document is valid or not. The Tor project would fix such a
threshold in the default configuration but users and relay operators are
free to adjust this value to their own preferences. In order to verify
the signature, they need to have the individual public keys of all the
witnesses beforehand. This "CoSi certificate" can be embedded in the
software in the same way certificate pinning does.
2. Motivation
Tor's DAs are comprised of 9 servers (and one extra for the bridges):
four of them are in the US and 5 of them are in the EU. Attacking these
central and vital points of the Tor network is clearly within the reach of
state level adversaries if they were to collaborate. Recent stories about
surveillance show that such a collaboration is already happening.
For example, let's imagine a situation where a state-level attacker
secretly coerces and/or steals the private keys of 5 of the 9 DAs, takes
them back to the Republic of Tyrannia where they control the ISPs and the
country’s Internet connectivity to the rest of the world. The government
embeds those keys in their “Great Firewall” type devices, and uses them to
secretly MITM attack targeted Tor users within Tyrannia by giving them
correctly-signed but completely false views of the Tor directory in which
all of the available relays are run by the Tyrannian authorities. Since
this attack does not attack the consensus documents that the legitimate
DAs are regularly broadcasting to the rest of the world, neither the Tor
project nor anyone else outside of Tyrannia will have the opportunity to
see or promptly become aware of the fake consensus documents, and not many
people even inside Tyrannia might have the opportunity to detect the
attack if it is carefully targeted against the small number of suspected
activists and journalists the government does not like.
The main goal of CoSi applied in Tor should be to ensure consensus
document transparency: that is, ensure the property that any consensus
document that any Tor client anywhere will accept has been observed and
logged by a significant number of parties throughout the world, so that
any misuse of a quorum of 5 DA keys anywhere will be quickly detectable
(soon, if not necessarily during the signing process itself).
3. Design
The first part of the section will talk more about the architecture of
a "CoSi" system and the second part will go into more detail about how
such a system can be integrated in Tor. For more details, please refer to
the main CoSi research paper [0].
3.1 Simplified Architecture
First, the list of witness's public keys constitute the "CoSi
certificate" that can be used to verify a signature; it contains the list
of individual public keys and the aggregate key. Then the leader forms
the tree out of the list of witnesses and run the CoSi protocol. The tree
is only there for performance reasons and can be reconfigured at any point
in time without affecting security. The leader then includes the CoSi
signature (which uses Schnorr signatures) in the consensus document.
Clients can then verify the consensus document using the aggregate public
key of the "CoSi certificate".
A CoSi signature have two components:
- Schnorr signature
- Exceptions: bitmap of length equal to the size of the witness
group used by absent witnesses or refusing-to-sign witnesses (see
3.5).
Besides contributing to the signing, each witness can and should
perform any readily feasible syntactic and semantic correctness checks on
the leader’s proposed statements before signing off on them. They
can/should probably publish logs of the statements they witness or simply
make available a public mirror of everything that its tree roster has been
asked to sign.
3.2 CoSi in Tor
3.2.1 Witness selection
CoSi relies on a list of decentralized cosigning witnesses, an
optional role to be supported by a future version of the standard Tor
relay software. The set of witness servers will initially be defined as a
list of the DAs and a list of servers that satisfy some specific criteria.
Those criteria are similar as the ones used for the selection of the
Fallback Directory Mirrors [2]. Specifically, the set of relays that are:
* Opting to be a CoSi witness (and to generate an ed25519 key),
* Having stable keys, IP addresses, and ports, ideally for the life of
the release, nominally the next 2 years,
* having demonstrated good uptime, calculated as a decaying weighted
average,
* not having more than one witness with the same IP, family, or
operator (contact info).
One way to form an initial witness list is to contact first the Fallback
Directory Mirrors to see if they accept to endorse this new role and then
if not enough operators agree on this, we can start searching for others
operators. Of course, managing such an organization takes time and one can
expect the first list of witness to be ready only after a few months.
For deployment, one general strategy is to start with low threshold t,
i.e. t = 1-10% of N, where N is the number of witnesses in the CoSi
certificate. Once the witness set is operating, depending on the
evolution of the set (how many servers failed ? what is the frequency of
their failure ? etc), we can slowly and conservatively increase the
security parameters N and t. The maximum value of N would have to be
decided in further discussion. The threshold can be adapted using the
statistics gathered from the previous iterations. If 80% of the witnesses
were consistently and continually available and the threshold is only 20%,
then it makes sense to higher up this security parameter.
3.2.2 Operations
Each time a DA, acting in its role as CoSi leader, initiates a
collective signing round, the leader forms a communication tree. One
criteria that can be played with except the branching factor is the
latency between witnesses. One can collect information about the
communication latencies between the witnesses and construct a
shortest-path spanning tree using this data in order to reduce the global
latency of the system.
Once the tree is setup then the signature process happens for each
consensus document. The leader starts by generating the tree out of the
witnesses. The tree can be generated out of a fixed branching factor and
is basically represented as an array of indices out of CoSi certificate.
The leader then sends down the tree to the its children and starts the
multi-step CoSi round.
The CoSi protocol produces a collective signature in response to the
initiation of the protocol by a leader. This signature is then included
in the consensus document so clients don't have to request it from another
party.
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. This approach is not the most
efficient but likely to be the simplest, and we do not expect the small
inefficiency caused by the redundant collective signing to be a problem in
practice. 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. This approach would eliminate redundant collective signing
operations in the common case at the cost of perhaps unnecessary
complexity.
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?
As far as our understanding of Tor goes, there does not seem to be any
particularly strong consistency requirements between the different DAs’
perspectives. Therefore, the simplest approach would be that all DAs
independently act as leaders to produce different collective signatures on
the same consensus documents. This approach does not require any
synchronization between DAs and enable directly each DA to service the
CoSi-signed consensus document to the Tor network. Later it may be worth
exploring automated leader-election mechanisms and/or stronger
consensus-consistency mechanisms, but there does not seems to have a need
for such a complexity right now.
3.3 Evolution of the CoSi set of witnesses
One obvious solution for the evolution of the CoSi set of witness lies
into the version-ing mechanism of Tor. A particular Tor client version
would be associated with a particular cosigning group whose keys are
embedded into the source code of this Tor version. A client will have the
latest CoSi set keys when and only when its Tor client would be upgraded -
just like the list of directory authorities.
Using this mechanism, a leader still have to produce valid CoSi
signature for each version used by the clients that are supported. For
example, if the policy is that witness sets change at most once per year,
and Tor clients are supposed to be supported up to 5 years old, then a
leader has to provide up to 5 different CoSi signatures, one for each of
the five recent witness lists. The duration of support for a Tor version
has to be the same as the availability time we expect from relay operators
that are selected to be witness.
The strength of this mechanism is its simplicity. One the other hand,
if the witness set in fact proves to evolve too quickly, the DAs may have
to juggle multiple witness sets in order to retain compatibility with
older Tor clients.
3.4 Failure of witnesses
A simple design to handle the case where one or more witnesses are
down is to leverage the already existing measurements from the Tor
network. For example, if a witness relay does not have the "Running" flag
[4], then the leader excludes it from the tree before starting a new
round. When the witness relay gets back online, it will have to wait some
time before being included again in any further CoSi round. The "Running"
flag seems a good starting point as a suggestion because the CoSi system
can then recover quickly from failed nodes, but other possibilities such
as the "Stable" flag or a simple timeout might be worth exploring
too. The leader launching a round on subset of the initial witness list
will have to toggles the bit on the bitmap of the final CoSi signature on
the indexes of the absent witnesses. The indexes are referenced by the
CoSi certificates.
If a witness is to fail during a CoSi round, a simple mechanism is to
make the parent of the failed witness announce the failure to the leader.
The leader will then restart a round with a new tree that does not
contains the failed witness. The leader also have to toggle the bit
corresponding to the failed witness in the exception bitmap.
3.5 Refusing to sign
If a witness does not want to sign, it should raises an administrative
alarm in its public log or contact a DA. The witness should also toggles
the bit at its index in the bitmap. Its index is determined as the index
in the list of witnesses from the CoSi certificate. The client will then
see a "1" bit in the bitmap, and will subtract the corresponding public
key of the witness from the aggregate public key. That way, the client is
still able to verify the signature and it knows about which witnesses
refused to sign off. 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.
3.6 Optional: Break-the-glass Emergency Directory Adjustments
In case of emergency, the delay caused by having to coordinate among 5
DAs in order to make anything happen (i.e. excluding a set of malicious
nodes) can be problematic.
This section proposes a mechanism in which the CoSi witnesses can
accept and witness not just “full consensus” documents (signed by 5 DAs),
but can also accept “emergency adjustments”, which are highly-constrained
deltas (diffs) to an existing full consensus document signed by a smaller
threshold of DAs, e.g., 2 or even just 1. For example, the CoSi witness
cosigning rules might require that an emergency directory-adjustment must:
- be a diff against a “fresh”, recent full consensus document (perhaps
*the* most recent one),
- can make no modifications to the full consensus other than some
pre-defined operations such as decreasing bandwidth weights assigned
to relays,
- cannot affect the directory-wide total bandwidth weight by more than
X% (e.g., 1% or .1%).
These suggestions are just a few imaginable rules to get the idea
across; the “right” rules would of course need much more discussion. This
way, if one or two DAs discovers or even strongly suspects an attack of
some kind, they can take emergency countermeasures against the attack and
be able to roll them out to clients quickly without having to get a full 5
DAs out of bed - but because the delta-consensus is still witness-cosigned
automatically by (perhaps) all the DAs and a number of additional trusted
relays, we get the strong accountability provision that the use of such a
“break-the-glass” emergency provision will immediately become known to the
other DAs as soon as they do get out of bed.
Such a break-the-glass emergency adjustment mechanism could be
designed, if desired, so that ordinary clients and relays cannot
immediately tell the difference between a directory consensus produced via
the normal threshold of 5 DAs and one that was produced as a delta via the
emergency adjustment mechanism. Only the witness cosigners would
necessarily need to know which collectively-signed directories were
authorized via the full consensus procedure or via a break-the-glass
adjustment. So if it’s important to keep it secret from the general
public the precise reason for a particular directory update, that can be
accommodated. Only the more-trusted group of witness cosigners (and
obviously all the DAs themselves) would necessarily know the precise
origin and administrative justification of a given directory update. With
even fancier crypto, even the witnesses would not necessarily need to
know, but that’s beyond the scope of this proposal and its desirability
may be questionable at any rate.
4. Security implications
4.1 Cons
Since the structure is a tree, if any node fails, there must be some
failover mechanisms to reconstruct a tree without the failed node. Since
the DA reach consensus every hour [1], and following the design in 3.4,
the availability problem should not be an issue.
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. The key technical
contribution of our research is a distributed protocol that makes large,
decentralized witness cosigning groups practical. This decentralized
approach enables the security of the whole system to scale with the number
of witnesses.
Not only does this system dramatically increase the cost of
successfully deploying an attack on the DA (the attacker would have to
corrupt a large majority of the witnesses), 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.
4.3 Differences between CoSi and Certificate Transparency
Prior transparency mechanisms have two weaknesses. First they do not
significantly increase the number of secret keys an attacker must control
to compromise any client device, and client devices cannot even
retroactively detect such compromise unless they can actively communicate
with multiple well-known Internet servers. For example, even with
Certificate Transparency, an attacker can forge an Extended Validation
(EV) certificate for Chrome after compromising or coercing only three
parties: one Certificate Authority (CA) and two log servers. Since many
CAs and log servers are in US jurisdiction, such an attack is clearly
within reach of the US government. If such an attack does occur,
Certificate Transparency cannot detect it unless the victim device has a
chance to communicate or gossip the fake certificate with other parties on
the Internet – after it has already accepted and started using the fake
digital certificate. In the case of Tor Transparency, the attack is harder
because the attacker would have to compromise the three parties plus a
majority of Directory Authorities but facing a state-level adversary the
threat is still plausible. One way to increase the difficulty of the
attack is to make sure the logs servers are scattered in different places
of the world.
Second, the attacker can still evade transparency by controlling the
client’s Internet access paths. For example, a compromised Internet
service provider (ISP) or corporate Internet gateway can defeat
retroactive transparency mechanisms by persistently blocking a victim
device’s access to transparency servers elsewhere on the Internet. Even if
the user’s device is mobile, a state intelligence service such as China’s
“Great Firewall” could defeat retroactive transparency mechanisms by
persistently blocking connections from a targeted victim’s devices to
external transparency servers, in the same way that China already blocks
connections to many websites and Tor relays.
Using CoSi requires the clients to have the list of public keys of all
the witnesses embedded in the software, like certificate pinning. In order
to reduce the size of this CoSi certificate, we embed the aggregated
public key of all the witnesses and a hash representing the root of a
Merkle tree containing the public key of all the witnesses. Using the
certificate this way provides an universally-verifiable commitment to all
the witnesses’ public keys, without the certificate actually containing
them all.
5. Specifications
5.1 Protocol
We will describe quickly the protocol here; for a more detailed
explanation, please refer to the academic paper [0]. The setup is as
described in 3.2.1. The protocol in itself consists of four phases:
- Announcement: The leader broadcast down the consensus document to its
children, which in turn also broadcast to their children,etc.
- Commitment: When the leaves of the CoSi tree get the consensus
document,generate its random value v(i) and the corresponding
commitment V(i) and sends V(i) up to its parent. If a leaf refuses to
sign this consensus document, it does not create any commitment. Each
intermediate node aggregate all the commitments of their children, add
their own commitment (or nothing if it refuses to sign) and send the
result up in the tree. The root gets the aggregated commitment V of all
signing witnesses.
- Challenge: The root then compute the challenge c = H( m || V ), with
m being the consensus document and H being a collision resistant
hash function that returns a scalar, and distribute the challenge down
the tree like in the Announcement phase.
- Response: Starting from the leaves, each witnesses compute its response
r(i) = v(i) - c * x(i), where x(i) is the long term private key of the
witness. If the witness refuses to sign, it simply set the n-th bit of
the bitmap to "1", where n is the index of the witness in the "CoSi
certificate" (the list of all individual public keys). Each intermediate
nodes in the tree aggregate the responses and the bitmap of all its
children, aggregate with its own response/bitmap and send that up in the
tree. At the end of the protocol, the root gets the aggregated response
r.
The signature is the tuple (c,r) and must be included in the consensus
document. If no exceptions occurred (i.e. the bitmap contains all "0"s),
the signature can be verified using the aggregate public key of all
witnesses using standard Schnorr verification algorithm [3]. If an
exception occurs, the client needs to lookup the indexes where the bitmap
contains "1"s. The client then lookup the corresponding public keys (from
the list of public keys of witnesses) and subtract each of them from the
aggregate public key. The client can then use this reduced public key to
verify the signature as usual.
5.2 Format
+ The "CoSi certificate" is a list of all witnesse's ed25519 public
keys and the aggregate public key of all individual public keys.
+ A CoSi tree is a list of indexes out of the CoSi certificate. It
seems reasonable to pick the indexes as 16-bits unsigned integers. In
order to make this representation maximally space efficient, the tree
needs to be a complete K-ary tree [5].
+ A CoSi signature contains:
- the challenge c, an ed25519 scalar
- the response r, an ed25519 scalar
- the bitmap of exceptions, whose length is equal to the number of
witnesses.
+ The messages sent during the four following phases are as follow:
- Announcement: consensus document
- Commitment: an ed25519 curve point
- Challenge: an ed25519 scalar
- Response: an ed25519 scalar and the exception bitmap
5.3 Bandwidth
Let's compute the cumulative bandwidth required by a witness to
participate in a CoSi round with a tree having a branching factor BF.
- tree: N * 2 bytes
- Announcement: consensus = 1,500 KB * (BF+1)
- Commitment: ed25519 point 32 * (BF+1) bytes
- Challenge: ed25519 scalar 32 * (BF+1) bytes
- Response: (ed25519 scalar + bitmap N bits) * (BF+1) bytes
The announcement phase clearly dominates so we can approximate the
bandwidth required for one round: 1.5 * (BF+1) MB. Since the consensus
document is generated every hour, then we 1.5*(BF+1) / 3600 MB/sec.
For BF = 5, the bandwidth is equal to 2 KB/sec. The bandwidth
requirement are that low such that there is no additional bandwidth
requirement on the witness selection criteria.
6. Compatibility
First of all, integrating CoSi would *not* immediately affect the
fundamental structure or function of the current DAs: there could still be
9 of them, of which any 5 can authorize the release of a new consensus
document, as they do now. Secondly, CoSi would not necessarily change
anything about how the 9 DAs decide on how to compute these directory
consensus documents; e.g., it would not prevent the DAs from working
together to block the inclusion of (or assignment of bandwidth-weight to)
relays that might be perceived by the DAs as doing bad things. Finally,
full backward compatibility with old Tor clients and relay software may be
maintained by treating the new CoSi-generated collective signature as just
an additional signature that gets attached to and distributed with
consensus documents. It may be treated as a special “10th virtual DA” that
does not help authorize decisions but just publicly witnesses the output
of the regular 9 DAs. Old client and relay software can simply ignore
that new collective signature, whereas new software might look for it and
over time gradually increase the threshold number of witnesses it expects
to see.
7. Implementation
Implementation in Go is open source at:
https://github.com/dedis/cothority
8. Performance
9. Acknowledgements
This proposal has received some valuable feedback from Bryan Ford,
Linus Gasser, Ismail Khoffi, Philipp Jovanovic, and Ludovic Barman.
A. References
[0] http://arxiv.org/pdf/1503.08768v3.pdf
[1] https://collector.torproject.org
[2] https://trac.torproject.org/projects/tor/wiki/doc/FallbackDirectoryMirrors
[3] https://en.wikipedia.org/wiki/Schnorr_signature
[4] https://tor.stackexchange.com/questions/423/what-are-good-explanations-for-relay-flags
[5] https://en.wikipedia.org/wiki/K-ary_tree
-------------- 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/20160526/7b728dc9/attachment-0001.sig>
More information about the tor-dev
mailing list