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---
(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
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!
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.
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.
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/addInput:
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.
- Security implications
TODO
- 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@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Ximin Luo infinity0@torproject.org wrote Sun, 06 Jul 2014 17:06:56 +0100:
| (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.)
Good point. What do you think about this?
Note that while the proposed solution gives some protection against using a false consensus, in addition to high chance of detection, this is not the primary goal but more of a nice side effect.
| 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.
Operators of directory authorities can look for consensuses they don't recognise. This was my immediate thought but obviously misses out on the benefits of decentralisation of consensus verification.
Others could indeed "check the diff". I will add text addressing that after having looked at what is being done in the field of diffing consensuses as part of one of the GSoC projects.
More ideas for things to look for?
| Also, are there any other threats you want to protect against?
No.
| > 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.
This validates the functionality of the log more than anything else. Maybe this should move to "Log auditing".
-
Linus Nordberg -
Linus Nordberg -
Ximin Luo