[tor-dev] Proposal: Tor with collective signatures

Nicolas Gailly nicolas.gailly at epfl.ch
Thu Apr 14 12:40:14 UTC 2016


Hi Tor devs,

I'm part of the DeDiS team at EPFL and we are working on Cothority,
which is a generic framework for Collective Authority. We worked on a
proposal to apply Collective Signatures (CoSi) to D.A. consensus
document in the Tor ecosystem. While not adding too much complexity to
the Tor ecosystem, we believe it can bring more transparency,
accountability and security regarding the consensus documents. There is
also a section regarding the emergency procedure that D.A.s operators
are under when a relay is detected as malicious, and how CoSi could help
in this process.

I hope you will find it interesting and welcome all the feedbacks /
opinions you can have!

Thanks in advance,

Nicolas

<-------- tor_cosi.txt --------------->
Filename: tor_cosi.txt
Title: Tor CoSi
Author: Nicolas GAILLY
Created: 09.03.2016
Status: draft

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

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

4.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 the hash of a Merkle tree containing all the
    individual public keys. This Merkle tree is needed in case some
nodes are
    failing, so the verification of the signature can still be executed
without
    any change by the client. These issues are covered later in the
“Handling
    Exceptions” part. In a nutshell, a signature round broadcasts the
message down
    the tree, and to each participant. At the end of a signature round,
the client
    have a simple Schnorr signature to verify.

    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.

    An important point is that each signature is chained with the last
one, so
    each witness also knows the full set of witnesses that accepted the last
    signature and whether the leader is acting malicious or not.

4.2 CoSi in Tor
   4.2.1 Setup
       The CoSi system can be constructed using independent, diverse and
    decentralized witnesses. In the context of Tor, one could imagine to
include
    the DA themselves (one could be the leader), and some of the best
relays in
    term of availability and reputation. Due to the decentralized nature of
    CoSi, this system can also includes external organizations that are
    favorable and trusted by Tor (e.g. EFF). 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. One important property is that the
    system is under a closed membership policy. The certificate of the
    CoSi system will have to be embedded in the Tor code in a similar
way as for
    certificate pinning.

    One obvious way to do it is to setup the set of witnesses as being
the DAs
    and the set of (future) “backup directory servers” as their public
keys will
    already be hard-coded into the Tor client software. That way the
deployment
    cost is drastically reduced as software will already have the keys
to verify a
    CoSi signature.

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

    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?

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

4.3 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

6. Compatibility

7. Implementation

    Implementation in Go is open source at:
    https://github.com/dedis/cothority

8. Performance

9. Acknowledgments

    This proposals has received some valuable feedback from Bryan Ford,
Linus
    Gasser, Ismail Khoffi, Philipp Jovanovic, and Ludovic Barman.

A. References

    [1] https://collector.torproject.org
<-------------- END ----------------------->

-------------- next part --------------
Filename: tor_cosi.txt
Title: Tor Cosi
Author: Nicolas GAILLY, DeDiS lab, EPFL
Created: 09.03.2016
Status: draft

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

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

4.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 the hash of a Merkle tree containing all the
    individual public keys. This Merkle tree is needed in case some nodes are
    failing, so the verification of the signature can still be executed without
    any change by the client. These issues are covered later in the “Handling
    Exceptions” part. In a nutshell, a signature round broadcasts the message down
    the tree, and to each participant. At the end of a signature round, the client
    have a simple Schnorr signature to verify. 

    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. 

    An important point is that each signature is chained with the last one, so
    each witness also knows the full set of witnesses that accepted the last
    signature and whether the leader is acting malicious or not.

4.2 CoSi in Tor
    
4.2.1 Setup 
    
    The CoSi system can be constructed using independent, diverse and
    decentralized witnesses. In the context of Tor, one could imagine to include
    the DA themselves (one could be the leader), and some of the best relays in
    term of availability and reputation. Due to the decentralized nature of
    CoSi, this system can also includes external organizations that are
    favorable and trusted by Tor (e.g. EFF). 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. One important property is that the
    system is under a closed membership policy. The certificate of the
    CoSi system will have to be embedded in the Tor code in a similar way as for
    certificate pinning.

    One obvious way to do it is to setup the set of witnesses as being the DAs
    and the set of (future) “backup directory servers” as their public keys will
    already be hard-coded into the Tor client software. That way the deployment
    cost is drastically reduced as software will already have the keys to verify a
    CoSi signature.

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

    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?

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

4.3 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

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

    [1] https://collector.torproject.org
-------------- 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/20160414/bb5cf365/attachment-0001.sig>


More information about the tor-dev mailing list