Hi,
Here's a new version of the proposal with some minor fixes discussed with teor last time.
0.4: - changed *included* to *appended* - 3.2: end of paragraph, a valid consensus document contains a majority of CoSi signatures. - Acknowledgments include teor and Tom Ritter.
As always, critics / feedbacks / thoughts are more than welcome :)
Thanks !
Nicolas
Ps: Our team and I are going to be at PETS this year, so if you don't have time now to
read the whole thing, but you are still willing to know about CoSi and how it could improve
Tor security, I/we will be happy to talk with some of you there also.
<----------------------------------->
Filename: tor_cosi.txt Title: Tor Cosi Author: Nicolas GAILLY, DeDiS lab, EPFL Created: 09.03.2016 Status: draft Version: 0.4
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 appended to the consensus document so clients don't have to request it from another party. A CoSi signature is appended to the consensus document in the same way DAs signatures are.
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. Using this mechanism, a consensus document is then served only if a majority of CoSi signatures are valid (5/9).
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 appended to 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 appended 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. Acknowledgments
This proposal has received some valuable feedback from Bryan Ford, Linus Gasser, Ismail Khoffi, Philipp Jovanovic, and Ludovic Barman, Tim Wilson-Brown and Tom Ritter.
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-r... [5] https://en.wikipedia.org/wiki/K-ary_tree