[tor-dev] Proposal: Tor with collective signatures
Nicolas Gailly
nicolas.gailly at epfl.ch
Mon Apr 25 12:32:50 UTC 2016
Hi all,
Since the first post, I've received some comments off-list and
consequently added more sections to the proposal. Particularly, it adds
a detailed description of the messages that needs to be passed down
between the witnesses, paragraphs to answer some questions, and a link
to the official paper.
I hope it gets clearer and answer most of your questions :)
Please, feel free to ask questions on/off list, I'd be happy to discuss
about it anytime ;) (irc: nikkolasg)
Thanks,
Nicolas
version 0.2:
- 3.2.1 Setup : explicitly using Fallback directory mirrors as witnesses
- 3.2.2 Operation: what does a witness that refuse to sign do
- 3.2.3 added incremental deployment section
- 3.3 : added evolution of the CoSi set of witnesses section
- 3.1 added signature description
- 5 Specifications:
5.1: Protocol
5.2: Format
------------------------------------------------------------------------------------------
Filename: tor_cosi.txt
Title: Tor Cosi
Author: Nicolas GAILLY, DeDiS lab, EPFL
Created: 09.03.2016
Status: draft
Version: 0.2
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 any user or relay is free to adjust this value to
its own
need. In order to verify the signature, they need to have the
individuals
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 plausible 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
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 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 official paper
[0].
3.1 Simplified Architecture
The designated leader arranges all the witnesses in a tree. The public
keys of each participants are aggregated to form an aggregate public
key. The
tree is only there for performance reasons and can be reconfigured
at any
point in time without affecting security (the latest experiments
showed that
we could run up to 8000 nodes with a 2 second delay for generating a
signature). Once the tree is constructed, its "certificate"
represents the
aggregate public key and all its individual public keys of each
witnesses.
At the end of a signature round, the client will be able to verify the
CoSi signature (which uses Schnorr signatures) using the aggregate
public key.
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.2.2 Operations).
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 Setup
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 the D.A. and
a subset
of the Fallback Directory Mirrors [2], namely the set of relays that
are (a)
deemed stable enough by the same criteria as used for selecting Fallback
Directory Mirrors, (b) are running a recent enough version of the
Tor relay
software to support the CoSi witness server role, and (c) have not
opted out
of playing this CoSi witness role. That way the deployment cost is
drastically reduced as software will already have the keys to verify
a CoSi
signature.
Another criteria for the tree construction includes 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.
3.2.2 Operations
Once the tree is setup and each one knows about it (have the
certificate),
then the signature process happens for each consensus document. 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.
If a witness does not want to sign, it 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.
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.
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?
3.2.3 Integration
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.
For incremental deployment purposes, it's reasonable to think that those
Fallback Directory mirrors servers probably would not deply CoSi
support all
at the same time. Moreover, this set of witnesses might be a subset
of the
Fallback Directoy mirrors and some of them would not want to be
cosigners.
The hard-coded list of mirrors into the Tor client might need to be
annotated
with a “cosigner flag" for each such mirror, allowing some bootstrap
relays to
be cosigners and others not. The witness group is then simply the
subset of
fallback directory mirrors with the cosigner flag set.
3.3 Evolution of the CoSi set of witnesses
One obvious solution for the evolution of the CoSi set of winesses lies
into the version-ing mechanism of Tor. A particular Tor client
version would
be associated with a particular cosigning group which consists of
the D.A. and
the Fallback Directory Mirrors whose keys are embedded into the
source code of
this Tor version with this "cosigner flag" set. 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.
3.4 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 restore connectivity between the children of the
failed node and the rest of the tree. Since the DA reach consensus every
hour [1], with the help of the gossiping network, the availability
problem
is not 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 refers 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. Please note that
while the current implementation only uses ed25519, it is completely
possible to use
any other elliptic curve implementations.
+ 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
6. Compatibility
7. Implementation
Implementation in Go is open source at:
https://github.com/dedis/cothority
8. Performance
9. Acknowledgements
This proposals 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
-------------- next part --------------
Filename: tor_cosi.txt
Title: Tor Cosi
Author: Nicolas GAILLY, DeDiS lab, EPFL
Created: 09.03.2016
Status: draft
Version: 0.2
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 any user or relay is free to adjust this value to its own
need. In order to verify the signature, they need to have the individuals
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 plausible 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 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 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 official paper
[0].
3.1 Simplified Architecture
The designated leader arranges all the witnesses in a tree. The public
keys of each participants are aggregated to form an aggregate public key. The
tree is only there for performance reasons and can be reconfigured at any
point in time without affecting security (the latest experiments showed that
we could run up to 8000 nodes with a 2 second delay for generating a
signature). Once the tree is constructed, its "certificate" represents the
aggregate public key and all its individual public keys of each witnesses.
At the end of a signature round, the client will be able to verify the
CoSi signature (which uses Schnorr signatures) using the aggregate public key.
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.2.2 Operations).
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 Setup
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 the D.A. and a subset
of the Fallback Directory Mirrors [2], namely the set of relays that are (a)
deemed stable enough by the same criteria as used for selecting Fallback
Directory Mirrors, (b) are running a recent enough version of the Tor relay
software to support the CoSi witness server role, and (c) have not opted out
of playing this CoSi witness role. That way the deployment cost is
drastically reduced as software will already have the keys to verify a CoSi
signature.
Another criteria for the tree construction includes 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.
3.2.2 Operations
Once the tree is setup and each one knows about it (have the certificate),
then the signature process happens for each consensus document. 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.
If a witness does not want to sign, it 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.
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.
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?
3.2.3 Integration
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.
For incremental deployment purposes, it's reasonable to think that those
Fallback Directory mirrors servers probably would not deply CoSi support all
at the same time. Moreover, this set of witnesses might be a subset of the
Fallback Directoy mirrors and some of them would not want to be cosigners.
The hard-coded list of mirrors into the Tor client might need to be annotated
with a “cosigner flag" for each such mirror, allowing some bootstrap relays to
be cosigners and others not. The witness group is then simply the subset of
fallback directory mirrors with the cosigner flag set.
3.3 Evolution of the CoSi set of witnesses
One obvious solution for the evolution of the CoSi set of winesses lies
into the version-ing mechanism of Tor. A particular Tor client version would
be associated with a particular cosigning group which consists of the D.A. and
the Fallback Directory Mirrors whose keys are embedded into the source code of
this Tor version with this "cosigner flag" set. 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.
3.4 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 restore connectivity between the children of the
failed node and the rest of the tree. Since the DA reach consensus every
hour [1], with the help of the gossiping network, the availability problem
is not 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 refers 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. Please note that
while the current implementation only uses ed25519, it is completely possible to use
any other elliptic curve implementations.
+ 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
6. Compatibility
7. Implementation
Implementation in Go is open source at:
https://github.com/dedis/cothority
8. Performance
9. Acknowledgements
This proposals 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
-------------- 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/20160425/4874ace4/attachment-0001.sig>
More information about the tor-dev
mailing list