[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [tor-dev] Tor with collective signatures



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-relay-flags
    [5] https://en.wikipedia.org/wiki/K-ary_tree


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-relay-flags
    [5] https://en.wikipedia.org/wiki/K-ary_tree

Attachment: signature.asc
Description: OpenPGP digital signature

_______________________________________________
tor-dev mailing list
tor-dev@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev