[tor-dev] Draft proposal: Tor Consensus Transparency

Sun Jul 6 16:06:56 UTC 2014

(Disclaimer, I don't know the details of how consensus documents work. Some assumptions I made might be wrong.)

In section 2 Motivation, you mention a partition attack. I think the rest of the document neglects the topic of *actually protecting against this*, instead focusing only on running the log. I want to emphasise that CT logs are only an enabler, not a guarantor, of the security property. The monitors are the important thing, that actually detect attacks. (Someone needs to be watching, otherwise all security measures are useless.)

With X509, domain owners have the rightful control on what certificates say, but CAs can issue certs on their behalf. CT monitors protect against this, by getting data from logs and checking that the certificates for each domain have all been issued with the permission of the owner.

With the tor consensus document model, it's more vague exactly what the monitors should check for. To protect against a partition attack, you might do something like "monitors should check that the diff between consensus documents is small, within a small time period". But the precise parameters will need to be adjusted and justified, and this is important for robust detection of the attack.

Also, are there any other threats you want to protect against?

>  A log monitor verifies that the contents of the log is consistent
>  with the rules of the Tor network, notably that all entries are
>  properly formed and signed Tor consensus documents.

Don't Tor clients do this already? CT gives us the ability to detect things that a single client cannot already detect, such as a partition attack on the overall network, so we should focus on that.

X

On 05/07/14 01:05, Linus Nordberg wrote:
> Hi Tor devs,
> 
> It's surprisingly hard to work on Tor during the Tor developer
> meetings! My apologies for not publishing this text until now, despite
> my repeated ranting about the subject the last few days.
> 
> Well, here it is, in an early draft version. Thank you all who've
> listened patiently and given valuable feedback. I welcome more feedback
> from the list. Thanks in advance.
> 
> --8<---------------cut here---------------start------------->8---
> Filename: xxx-tor-consensus-transparency.txt
> Title: Tor Consensus Transparency
> Author: Linus Nordberg
> Created: 2014-06-28
> Status: Draft
> 
> 0. Introduction
> 
>    WARNING!!! EARLY DRAFT -- MISSING IMPORTANT BITS AND PIECES!
> 
>    This document describes how to provide and use public, append-only,
>    untrusted logs containing Tor consensus documents, much like what
>    Certificate Transparency [RFC6962] does for X.509 certificates. Tor
>    relays and clients can then refuse using a consensus not present in
>    logs of their choosing.
> 
>    WARNING!!! EARLY DRAFT -- MISSING IMPORTANT BITS AND PIECES!
> 
> 1. Overview
> 
>    Using a public, append-only, untrusted log like the history tree
>    described in [CrosbyWallach], Tor clients and relays verify that
>    consensus documents are present in one or more logs before using
>    them.
> 
>    Consensus-users, i.e. Tor clients and relays, expect to receive one
>    or more "proof of inclusions" with new consensus documents. A proof
>    of inclusion is a hash sum representing the tree head of a log,
>    signed by the logs private key, and an audit path listing the nodes
>    in the tree needed to recreate the tree head. Consensus-users are
>    configured to use one or more logs by listing a log address and a
>    public key for each log. This is used to verify that a given
>    consensus document is present in a given log.
> 
>    Anyone can submit a properly formatted and signed consensus
>    document to a log and get a signed proof of inclusion in
>    return. Directory authorities should do this and include the proofs
>    when serving consensus documents. Directory caches and
>    consensus-users receiving a consensus not including a proof of
>    inclusion submit the document and use the proof they receive in
>    return.
> 
>    Auditing log behaviour and monitoring the contents of logs is
>    performed in cooperation between the Tor network and external
>    services. Directory caches act as log auditors with help from Tor
>    clients gossiping about what they see. Directory authorities are
>    good candidates for monitoring log content since they know what
>    documents they have issued. Anybody can run both an auditor and a
>    monitor though, which is an important property of the proposed
>    system.
> 
>    Summary of proposed changes to Tor:
> 
>    - Directory authorities start submitting newly created consensuses
>      to at least one public log.
> 
>    - Tor clients and relays receiving a consensus not accompanied by a
>      proof of inclusion start submitting that to at least one public
>      log.
> 
>    - Consensus-users start rejecting consensuses accompanied by an
>      invalid proof of inclusion.
> 
>    - A new cell type LOG_GOSSIP is defined, for clients and relays to
>      exchange information about tree heads seen and their validity.
> 
>    - Consensus-users send LOG_GOSSIP cells with seen tree heads to
>      relays.
> 
>    - Relays validate tree heads received in LOG_GOSSIP cells (section
>      3.2.2) and send results to consensus-users in LOG_GOSSIP cells.
> 
> 2. Motivation
> 
>    Popping five boxes or factoring five RSA keys should not be ruled
>    out as a possible attack against a subset of the Tor network. An
>    attacker controlling a majority of the directory authorities
>    signing keys can, using man-in-the-middle or man-on-the-side
>    attacks, serve consensus documents listing relays under their
>    control. If mounted on a small subset of the network, the chance of
>    detection is probably low. This proposal increases the cost for
>    such an attack by raising the chances of it to be detected.
> 
>    The complexity of the proposed solution is motivated by the value
>    of the decentralisation given. Anybody can run their own log and
>    use it. Anybody can audit any existing logs and verify their
>    correct behaviour. This empowers people outside the group of Tor
>    directory authority operators and the people who trust them on a
>    personal basis.
> 
> 3. Design
> 
>    Communication with logs is done over http(s) similar to what
>    [RFC6962] defines. This proposal does not use [[the TLS data
>    structures]] but instead structures based on [[FIXME]]. Parameters
>    for POSTs and all responses are encoded as name/value pairs in JSON
>    objects [RFC4627].
> 
>    Definitions:
> 
>    - Log id: The SHA-256 hash of the log's public key, to be treated
>      as an opaque byte string identifying the log.
> 
> 3.1 Consensus submission
> 
>    Logs accept consensus submissions from anyone as long as the
>    consensus is signed by a majority of the Tor directory authorities
>    of the Tor network that the log is logging.
> 
>    [[TODO: Move most of this to "specification" section?]]
> 
>    Consensus documents are POST:ed to well-known URL
> 
>      https://<log server>/tct/v1/add
> 
>    Input:
> 
>      consensus: A consensus status document as defined in [dir-spec]
>        section 3.4.1.
> 
>    Output:
> 
>      id: The log id, base64 encoded.
> 
>      tree_size: The size of the tree, in entries, in decimal.
> 
>      timestamp: The timestamp, in decimal.
> 
>      sha256_root_hash: The Merkle Tree Hash of a tree including the
>        submitted entry, in base64.
> 
>      tree_head_signature: A TreeHeadSignature ([RFC6962] section 3.5)
>        for the above data.
> 
>      audit_path: An array of base64-encoded Merkle tree nodes proving
>        the inclusion of the submitted entry in the tree denoted by
>        sha256_root_hash (see [RFC6962] section 2.1.1).
> 
>    The output is what we call a proof of inclusion.
> 
>    The tree_head_signature is signed with the private key of the log.
> 
> 3.2 Consensus verification
> 
> 3.2.1 Log entry membership
> 
>    Calculate a tree head from the hash of the received consensus and
>    the audit path in proof. Verify that it's identical to the tree
>    head in the proof. This can easily be done by consensus-users for
>    each received consensus.
> 
>    We now know that the consensus is part of a tree which the log
>    claims to be The Tree. Whether this tree is the same tree that
>    everybody else see is unknown at this point.
> 
> 3.2.2 Append-only property of the log
> 
>    Ask the log for a consistency proof between the received tree head
>    and a previously known good tree head. The known good head can be
>    the empty tree. [[TODO add text about how to deal with received
>    heads that are older than the last known good tree.]] Communication
>    with logs is done over http(s) [[as described in [RFC6962] section
>    4 -- TODO specify protocol and encoding]].
> 
>    [[description of consistency verification goes here]]
> 
>    Tor relays may do this for tree heads received in LOG_GOSSIP cells
>    and communicate results in the same cells. [[TODO: Do this
>    synchronously or asynchronously?]] Relays cache results to minimise
>    the need for communication with log servers and calculations.
> 
>    We now know that the received tree is a superset of the known good
>    tree.
> 
> 3.3 Log auditing
> 
>    A log auditor verifies that the log presents the same view to all
>    its clients and its append-only property, i.e. that no entries once
>    accepted by the log are ever changed or removed. [[TODO describe
>    the Tor networks role in auditing a bit more than what's mentioned
>    in 3.2.2]]
> 
> 3.4 Log monitoring
> 
>    A log monitor verifies that the contents of the log is consistent
>    with the rules of the Tor network, notably that all entries are
>    properly formed and signed Tor consensus documents. Note that there
>    can be more than one valid consensus documents for a given point in
>    time. One reason for this is that the number of signatures can
>    differ due to consensus voting timing details. [[Are there more?]]
> 
>    [[TODO expand on monitoring strategies -- even if this is not part
>    of proposed extensions to the Tor network it's good for
>    understanding]]
> 
> 3.5 Consensus-user behaviour
> 
>    Keep an on-disk cache of consensus documents. Mark them as being in
>    on of three states:
> 
>    LOG_STATE_UNKNOWN -- don't know whether it's present in enough logs
>                         or not
>    LOG_STATE_LOGGED -- have seen good proof(s) of inclusion
>    LOG_STATE_LOGGED_GOOD -- confident about the tree head representing
>                             a good tree
> 
>    Newly arrived consensus documents start in LOG_STATE_UNKNOWN or
>    LOG_STATE_LOGGED depending on whether they are accompanied by
>    enough proofs or not. There are two possible state transitions:
> 
>    - LOG_STATE_UNKNOWN --> LOG_STATE_LOGGED: Seen enough proofs of
>      inclusion verifying correctly according to section 3.2.1. The
>      number of good proofs needed is a policy setting in the
>      configuration of the consensus-user.
> 
>    - LOG_STATE_LOGGED --> LOG_STATE_LOGGED_GOOD: Seen enough gossiping
>      to know that the tree head in the proof belongs to a known log.
> 
>    Consensuses in state LOG_STATE_UNKNOWN are not used but are instead
>    submitted to one or more logs. This may take the consensus to
>    LOG_STATE_LOGGED.
> 
>    Consensuses in state LOG_STATE_LOGGED are used despite not being
>    fully verified with regard to logging. LOG_GOSSIP cells with the
>    tree heads from received proofs are being sent to relays for
>    further verified. Clients send to all relays that they have a
>    circuit to to. Relays send to three random relays that they have a
>    circuit to.
> 
> 3.6 Relay behaviour when acting as an auditor
> 
>    TODO
> 
> 3.7 Notable differences from Certificate Transparency
> 
>    - The data logged is "strictly time-stamped", i.e. ordered.
> 
>    - Much shorter lifetime of logged data -- a day rather than a
>      year. Is the effects of this difference of importance only for
>      "one-shot attacks"?
> 
>    - Directory authorities have consensus about what they're
>      signing -- there are no "web sites knowing better".
> 
>    - Submitters are not in the same hurry as CA:s and can wait minutes
>      rather than seconds for a proof of inclusion.
> 
> 4. Security implications
> 
>   TODO
> 
> 5. Specification
> 
>   TODO
> 
> ? Compatibility
> ? Implementation
> ? Performance and scalability notes
> 
> A. Open issues
> 
>    - handle all consensus flavours (i.e. microdescriptor consensuses)
>    - don't use "consensus verification" since that's misleading
>    - maybe add hash function agility, i.e. don't fixate SHA-256 (but see
>      CT discussion about why not and TODO summarize it here)
>    - add a blurb about the values of publishing logs as Tor hidden services
>    - should relays gossip amongst each others too?
>    - discuss compromise of log keys
>    - add 'version' and 'extensions' fields to the submission response?
>    - maybe log votes as well
> 
> B. Acknowledgements
> 
>    This proposal leans heavily on [RFC6962]. Some definitions are
>    copied verbatim from that document. Valuable feedback has been
>    received from Ben Laurie and Karsten Loesing.
> 
> C. References
> 
>    [CrosbyWallach] http://static.usenix.org/event/sec09/tech/full_papers/crosby.pdf
>    [dir-spec] https://gitweb.torproject.org/torspec.git/blob/HEAD:/dir-spec.txt
>    [RFC4627] https://tools.ietf.org/html/rfc4627
>    [RFC6962] https://tools.ietf.org/html/rfc6962
> --8<---------------cut here---------------end--------------->8---
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
> 

-- 
GPG: 4096R/1318EFAC5FBBDBCE
git://github.com/infinity0/pubkeys.git

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 880 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20140706/9fbb395d/attachment.sig>