[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-commits] [torspec/master] Give Mike's OOB HMAC proposal a number and fix the filename.
commit d0d586fb4dc658429c9ee358808514786a980c0b
Author: Isis Lovecruft <isis@xxxxxxxxxxxxxx>
Date: Wed Sep 9 21:14:43 2015 +0000
Give Mike's OOB HMAC proposal a number and fix the filename.
---
proposals/000-index.txt | 2 +
proposals/253-oob-hmac.txt | 272 +++++++++++++++++++++++++++++++++++++++++
proposals/xxx-oob-hashmac.txt | 272 -----------------------------------------
3 files changed, 274 insertions(+), 272 deletions(-)
diff --git a/proposals/000-index.txt b/proposals/000-index.txt
index 7ef953f..96d3436 100644
--- a/proposals/000-index.txt
+++ b/proposals/000-index.txt
@@ -173,6 +173,7 @@ Proposals by number:
250 Random Number Generation During Tor Voting [DRAFT]
251 Padding for netflow record resolution reduction [DRAFT]
252 Single Onion Services [DRAFT]
+253 Out of Band Circuit HMACs [DRAFT]
Proposals by status:
@@ -200,6 +201,7 @@ Proposals by status:
250 Random Number Generation During Tor Voting
251 Padding for netflow record resolution reduction
252 Single Onion Services
+ 253 Out of Band Circuit HMACs
NEEDS-REVISION:
190 Bridge Client Authorization Based on a Shared Secret
OPEN:
diff --git a/proposals/253-oob-hmac.txt b/proposals/253-oob-hmac.txt
new file mode 100644
index 0000000..7171e91
--- /dev/null
+++ b/proposals/253-oob-hmac.txt
@@ -0,0 +1,272 @@
+Filename: 253-oob-hmac.txt
+Title: Out of Band Circuit HMACs
+Authors: Mike Perry
+Created: 01 September 2015
+Status: Draft
+
+
+0. Motivation
+
+
+It is currently possible for Guard nodes (and MITM adversaries that
+steal their identity keys) to perform a "tagging" attack to influence
+circuit construction and resulting relay usage[1].
+
+Because Tor uses AES as a stream cipher, malicious or intercepted Guard
+nodes can simply XOR a unique identifier into the circuit cipherstream
+during circuit setup and usage. If this identifier is not removed by a
+colluding exit (either by performing another XOR, or making use of known
+plaintext regions of a cell to directly extract a complete side-channel
+value), then the circuit will fail. In this way, malicious or
+intercepted Guard nodes can ensure that all client traffic is directed
+only to colluding exit nodes, who can observe the destinations and
+deanonymize users.
+
+Most code paths in the Tor relay source code will emit loud warnings for
+the most obvious instances circuit failure caused by this attack.
+However, it is very difficult to ensure that all such error conditions
+are properly covered such that warnings will be emitted.
+
+This proposal aims to provide a mechanism to ensure that tagging and
+related malleability attacks are cryptographically detectable when they
+happen.
+
+
+1. Overview
+
+Since Tor Relays are already storing a running hash of all data
+transmitted on their circuits (via the or_circuit_t::n_digest and
+or_circuit_t::p_digest properties), it is possible to compute an
+out-of-band HMAC on circuit data, and verify that it is as expected.
+
+This proposal first defines an OOB_HMAC primitive that can be included
+standalone in a new relay cell command type, and additionally in other
+cell types.
+
+Use of the standalone relay cell command serves to ensure that circuits
+that are successfully built and used were not manipulated at a previous
+point.
+
+By altering the RELAY_COMMAND_TRUNCATED and CELL_DESTROY cells to also
+include the OOB_HMAC information, it is similarly possible to detect
+alteration of circuit contents that cause failures before the point of
+usage.
+
+
+2. The OOB_HMAC primitive
+
+The OOB_HMAC primitive uses the existing rolling hashes present in
+or_circuit_t to provide a Tor OP (aka client) with the hash history of
+the traffic that a given relay has seen it so far.
+
+Note that to avoid storing an additional 64 bytes of SHA256 digest for
+every circuit at every relay, we use SHA1 for the hash logs, since the
+circuits are already storing SHA1 hashes. It's not immediately clear how
+to upgrade the existing SHA1 digests to SHA256 with the current circuit
+protocol, either, since matching hash algorithms are essential to the
+'recognized' relay cell forwarding behavior. The version field exists
+primarily for this reason, should the rolling circuit hashes ever
+upgrade to SHA256.
+
+The OOB_HMAC primitive is specified in Trunnel as follows:
+
+ struct oob_hmac_body {
+ /* Version of this section. Must be 1 */
+ u8 version;
+
+ /* SHA1 hash of all client-originating data on this circuit
+ (obtained from or_circuit_t::n_digest). */
+ u8 client_hash_log[20];
+ /* Number of cells processed in this hash, mod 2^32. Used
+ to spot-check hash position */
+ u32 client_cell_count;
+
+ /* SHA1 hash of all server-originating data on this circuit
+ (obtained from or_circuit_t::p_digest). */
+ u8 server_hash_log[20];
+ /* Number of cells processed in this hash, mod 2^32. Used
+ to spot-check hash position.
+ XXX: Technically the server-side is not needed. */
+ u32 server_cell_count;
+
+ /* HMAC-SHA-256 of the entire cell contents up to this point,
+ using or_circuit_t::p_crypto as the hmac key.
+ XXX: Should we use a KDF here instead of p_crypto directly? */
+ u8 cell_hmac_256[32];
+ };
+
+
+3. Usage of OOB_HMAC
+
+The OOB_HMAC body will be included in three places:
+
+ 1. In a new relay cell command RELAY_COMMAND_HMAC_SEND, which is sent in
+ response to a client-originating RELAY_COMMAND_HMAC_GET on stream 0.
+ 2. In CELL_DESTROY, immediately after the error code
+ 3. In RELAY_COMMAND_TRUNCATED, immediately after the CELL_DESTROY
+ contents
+
+3.1. RELAY_COMMAND_HMAC_GET/SEND relay commands
+
+Clients should use leaky-pipe topology to send RELAY_COMMAND_HMAC_GET to
+the second-to-last node (typically the middle node) in the circuit at
+three points during circuit construction and usage:
+
+ 1. Immediately after the last RELAY_EARLY cell is sent
+ 2. Upon any stream detachment, timeout, or failure.
+ 3. Upon any OP-initiated circuit teardown (including timed-out partially
+ built circuits).
+
+We use RELAY_EARLY as the point at which to send these cells to avoid
+leaking the path length to the middle hop.
+
+3.2. Alteration of CELL_DESTROY and RELAY_COMMAND_TRUNCATED
+
+In order to provide an HMAC even when a circuit is torn down before use
+due to failure, the behavior for generating and handling CELL_DESTROY
+and RELAY_COMMAND_TRUNCATED should be modified as follows:
+
+Whenever an OR sends a CELL_DESTROY for a circuit towards the OP, if
+that circuit was already properly established, the OR should include the
+contents of oob_hmac_body immediately after the reason field. The HMAC
+must cover the error code from CELL_DESTROY.
+
+Upon receipt of a CELL_DESTROY, and in any other case where an OR would
+generate a RELAY_COMMAND_TRUNCATED due to error, a conformant relay
+would include the CELL_DESTROY oob_hmac_body, as well as its own
+locally created oob_hmac_body. The locally created oob_hmac_body must
+cover the entire payload contents of RELAY_COMMAND_TRUNCATED, including
+the error code and the CELL_DESTROY oob_hmac_body.
+
+Here is a new Trunnel specification for RELAY_COMMAND_TRUNCATED:
+
+ struct relay_command_truncated {
+ /* Error code */
+ u8 error_code;
+
+ /* Number of oob_hmacs. Must be 0, 1, or 2 */
+ u8 num_hmac;
+
+ /* If there are 2 hmacs, the first one is from the CELL_DESTROY,
+ and the second one is from the truncating relay. If num_hmac
+ is 0, then this came from a relay without support for
+ oob_hmac. */
+ struct oob_hmac_body[num_hmac];
+ };
+
+The usage of a strong HMAC to cover the entire CELL_DESTROY contents
+also allows an OP to properly authenticate the reason a remote node
+needed to close a circuit, without relying on the previous hop to be
+honest about it.
+
+
+4. Ensuring proper ordering with respect to hashes
+
+4.1. RELAY_COMMAND_HMAC_GET/SEND
+
+The in-order delivery guarantee of circuits will mean that the incoming
+hashes will match upon receipt of the RELAY_COMMAND_HMAC_SEND cell, but
+any outgoing traffic the OP sent since RELAY_COMMAND_HMAC_GET will
+not have been seen by the responding OR.
+
+Therefore, immediately upon sending a RELAY_COMMAND_HMAC_GET, the OP
+must record and store its current outgoing hash state for that circuit,
+until the RELAY_COMMAND_HMAC_SEND arrives, and use that stored hash
+value for comparison against the oob_hmac_body's client_hash_log field.
+
+The server_hash_log should be checked against the corresponding
+crypt_path_t entry in origin_circuit_t for the relay that the command
+was sent to.
+
+4.2. RELAY_COMMAND_TRUNCATED
+
+Since RELAY_COMMAND_TRUNCATED may be sent in response to any error
+condition generated by a cell in either direction, the OP must check
+that its local cell counts match those present in the oob_hmac_body for
+that hop.
+
+If the counts do not match, the OP may generate a RELAY_COMMAND_HMAC_GET
+to the hop that sent RELAY_COMMAND_TRUNCATED, prior to tearing down the
+circuit.
+
+4.3. CELL_DESTROY
+
+If the cell counts of the destroy cell's oob_hmac_body do not match what
+the client sent for that hop, unfortunately that hash must be discarded.
+Otherwise, it may be checked against values held from before processing
+the RELAY_COMMAND_TRUNCATED envelope.
+
+
+5. Security concerns and mitigations
+
+5.1. Silent circuit failure attacks
+
+The primary way to game this oob-hmac is to omit or block cells
+containing HMACs from reaching the OP, or otherwise tear down circuits
+before responses arrive with proof of tampering.
+
+If a large fraction of circuits somehow fail without any
+RELAY_COMMAND_TRUNCATED oob_hmac_body payloads present, and without any
+responses to RELAY_COMMAND_HMAC_GET requests, the user should be alerted
+of this fact as well.
+
+This rate of silent circuit failure should be kept as an additional,
+separate per-Guard Path Bias statistic, and the user should be warned if
+this failure rate exceeds some (low) threshold for circuits containing
+relays that should have supported this proposal.
+
+5.2. Malicious/colluding middle nodes
+
+If the adversary is prevented from causing silent circuit failure
+without the client being able to notice and react, their next available
+vector is to ensure that circuits are only built to middle nodes that
+are malicious and colluding with them (or that do not support this
+proposal), so that they may lie about the proper hash values that they
+see (or omit them).
+
+Right now, the current path bias code also does not count circuit
+failures to the middle hop as circuit attempts. This was done to reduce
+the effect of ambient circuit failure on the path bias accounting (since
+an average ambient circuit failure of X per-hop causes the total circuit
+failure middle+exit circuits to be 2X). Unfortunately, not counting
+middle hop failure allows the adversary to only allow circuits to
+colluding middle hops to complete, so that they may lie about their hash
+logs. All failed circuits to non-colluding middle nodes could be torn
+down before RELAY_COMMAND_TRUNCATED is sent.
+
+For this reason, the per-Guard Path Bias counts should be augmented to
+additionally track middle-node-only failure as a separate statistic as
+well, and the user should be warned if middle-node failure drops below a
+similar threshold as the current end-to-end failure.
+
+5.3. Side channel issues, mitigations, and limitations
+
+Unfortunately, leaking information about circuit usage to the middle
+node prevents us from sending RELAY_COMMAND_HMAC_GET cells at more
+optimal points in circuit usage (such as immediately upon open,
+immediately after stream usage, etc).
+
+As such, we are limited to waiting until RELAY_EARLY cells stop being
+sent. It is debatable if we should send hashes periodically (perhaps
+with windowing information updates?) instead.
+
+
+6. Alternatives
+
+A handful of alternatives to this proposal have already been discussed,
+but have been dismissed for various reasons. Per-hop cell HMACs were
+ruled out because they will leak the total path length, as well as the
+current hop's position in the circuit.
+
+Wide-block ciphers have been discussed, which would provide the property
+that attempts to alter a cell at a previous hop would render it
+completely corrupted upon its final destination, thus preventing
+untagging and recovery, even by a colluding malicious peer.
+
+Unfortunately, performance analysis of modern provably secure versions
+of wide-block ciphers has shown them to be at least 10X slower than
+AES-NI[2].
+
+
+1. https://lists.torproject.org/pipermail/tor-dev/2012-March/003347.html
+2. http://archives.seul.org/tor/dev/Mar-2015/msg00137.html
diff --git a/proposals/xxx-oob-hashmac.txt b/proposals/xxx-oob-hashmac.txt
deleted file mode 100644
index 9027abd..0000000
--- a/proposals/xxx-oob-hashmac.txt
+++ /dev/null
@@ -1,272 +0,0 @@
-Filename: xxx-oob-hmac.txt
-Title: Out of Band Circuit HMACs
-Authors: Mike Perry
-Created: 01 September 2015
-Status: Draft
-
-
-0. Motivation
-
-
-It is currently possible for Guard nodes (and MITM adversaries that
-steal their identity keys) to perform a "tagging" attack to influence
-circuit construction and resulting relay usage[1].
-
-Because Tor uses AES as a stream cipher, malicious or intercepted Guard
-nodes can simply XOR a unique identifier into the circuit cipherstream
-during circuit setup and usage. If this identifier is not removed by a
-colluding exit (either by performing another XOR, or making use of known
-plaintext regions of a cell to directly extract a complete side-channel
-value), then the circuit will fail. In this way, malicious or
-intercepted Guard nodes can ensure that all client traffic is directed
-only to colluding exit nodes, who can observe the destinations and
-deanonymize users.
-
-Most code paths in the Tor relay source code will emit loud warnings for
-the most obvious instances circuit failure caused by this attack.
-However, it is very difficult to ensure that all such error conditions
-are properly covered such that warnings will be emitted.
-
-This proposal aims to provide a mechanism to ensure that tagging and
-related malleability attacks are cryptographically detectable when they
-happen.
-
-
-1. Overview
-
-Since Tor Relays are already storing a running hash of all data
-transmitted on their circuits (via the or_circuit_t::n_digest and
-or_circuit_t::p_digest properties), it is possible to compute an
-out-of-band HMAC on circuit data, and verify that it is as expected.
-
-This proposal first defines an OOB_HMAC primitive that can be included
-standalone in a new relay cell command type, and additionally in other
-cell types.
-
-Use of the standalone relay cell command serves to ensure that circuits
-that are successfully built and used were not manipulated at a previous
-point.
-
-By altering the RELAY_COMMAND_TRUNCATED and CELL_DESTROY cells to also
-include the OOB_HMAC information, it is similarly possible to detect
-alteration of circuit contents that cause failures before the point of
-usage.
-
-
-2. The OOB_HMAC primitive
-
-The OOB_HMAC primitive uses the existing rolling hashes present in
-or_circuit_t to provide a Tor OP (aka client) with the hash history of
-the traffic that a given relay has seen it so far.
-
-Note that to avoid storing an additional 64 bytes of SHA256 digest for
-every circuit at every relay, we use SHA1 for the hash logs, since the
-circuits are already storing SHA1 hashes. It's not immediately clear how
-to upgrade the existing SHA1 digests to SHA256 with the current circuit
-protocol, either, since matching hash algorithms are essential to the
-'recognized' relay cell forwarding behavior. The version field exists
-primarily for this reason, should the rolling circuit hashes ever
-upgrade to SHA256.
-
-The OOB_HMAC primitive is specified in Trunnel as follows:
-
- struct oob_hmac_body {
- /* Version of this section. Must be 1 */
- u8 version;
-
- /* SHA1 hash of all client-originating data on this circuit
- (obtained from or_circuit_t::n_digest). */
- u8 client_hash_log[20];
- /* Number of cells processed in this hash, mod 2^32. Used
- to spot-check hash position */
- u32 client_cell_count;
-
- /* SHA1 hash of all server-originating data on this circuit
- (obtained from or_circuit_t::p_digest). */
- u8 server_hash_log[20];
- /* Number of cells processed in this hash, mod 2^32. Used
- to spot-check hash position.
- XXX: Technically the server-side is not needed. */
- u32 server_cell_count;
-
- /* HMAC-SHA-256 of the entire cell contents up to this point,
- using or_circuit_t::p_crypto as the hmac key.
- XXX: Should we use a KDF here instead of p_crypto directly? */
- u8 cell_hmac_256[32];
- };
-
-
-3. Usage of OOB_HMAC
-
-The OOB_HMAC body will be included in three places:
-
- 1. In a new relay cell command RELAY_COMMAND_HMAC_SEND, which is sent in
- response to a client-originating RELAY_COMMAND_HMAC_GET on stream 0.
- 2. In CELL_DESTROY, immediately after the error code
- 3. In RELAY_COMMAND_TRUNCATED, immediately after the CELL_DESTROY
- contents
-
-3.1. RELAY_COMMAND_HMAC_GET/SEND relay commands
-
-Clients should use leaky-pipe topology to send RELAY_COMMAND_HMAC_GET to
-the second-to-last node (typically the middle node) in the circuit at
-three points during circuit construction and usage:
-
- 1. Immediately after the last RELAY_EARLY cell is sent
- 2. Upon any stream detachment, timeout, or failure.
- 3. Upon any OP-initiated circuit teardown (including timed-out partially
- built circuits).
-
-We use RELAY_EARLY as the point at which to send these cells to avoid
-leaking the path length to the middle hop.
-
-3.2. Alteration of CELL_DESTROY and RELAY_COMMAND_TRUNCATED
-
-In order to provide an HMAC even when a circuit is torn down before use
-due to failure, the behavior for generating and handling CELL_DESTROY
-and RELAY_COMMAND_TRUNCATED should be modified as follows:
-
-Whenever an OR sends a CELL_DESTROY for a circuit towards the OP, if
-that circuit was already properly established, the OR should include the
-contents of oob_hmac_body immediately after the reason field. The HMAC
-must cover the error code from CELL_DESTROY.
-
-Upon receipt of a CELL_DESTROY, and in any other case where an OR would
-generate a RELAY_COMMAND_TRUNCATED due to error, a conformant relay
-would include the CELL_DESTROY oob_hmac_body, as well as its own
-locally created oob_hmac_body. The locally created oob_hmac_body must
-cover the entire payload contents of RELAY_COMMAND_TRUNCATED, including
-the error code and the CELL_DESTROY oob_hmac_body.
-
-Here is a new Trunnel specification for RELAY_COMMAND_TRUNCATED:
-
- struct relay_command_truncated {
- /* Error code */
- u8 error_code;
-
- /* Number of oob_hmacs. Must be 0, 1, or 2 */
- u8 num_hmac;
-
- /* If there are 2 hmacs, the first one is from the CELL_DESTROY,
- and the second one is from the truncating relay. If num_hmac
- is 0, then this came from a relay without support for
- oob_hmac. */
- struct oob_hmac_body[num_hmac];
- };
-
-The usage of a strong HMAC to cover the entire CELL_DESTROY contents
-also allows an OP to properly authenticate the reason a remote node
-needed to close a circuit, without relying on the previous hop to be
-honest about it.
-
-
-4. Ensuring proper ordering with respect to hashes
-
-4.1. RELAY_COMMAND_HMAC_GET/SEND
-
-The in-order delivery guarantee of circuits will mean that the incoming
-hashes will match upon receipt of the RELAY_COMMAND_HMAC_SEND cell, but
-any outgoing traffic the OP sent since RELAY_COMMAND_HMAC_GET will
-not have been seen by the responding OR.
-
-Therefore, immediately upon sending a RELAY_COMMAND_HMAC_GET, the OP
-must record and store its current outgoing hash state for that circuit,
-until the RELAY_COMMAND_HMAC_SEND arrives, and use that stored hash
-value for comparison against the oob_hmac_body's client_hash_log field.
-
-The server_hash_log should be checked against the corresponding
-crypt_path_t entry in origin_circuit_t for the relay that the command
-was sent to.
-
-4.2. RELAY_COMMAND_TRUNCATED
-
-Since RELAY_COMMAND_TRUNCATED may be sent in response to any error
-condition generated by a cell in either direction, the OP must check
-that its local cell counts match those present in the oob_hmac_body for
-that hop.
-
-If the counts do not match, the OP may generate a RELAY_COMMAND_HMAC_GET
-to the hop that sent RELAY_COMMAND_TRUNCATED, prior to tearing down the
-circuit.
-
-4.3. CELL_DESTROY
-
-If the cell counts of the destroy cell's oob_hmac_body do not match what
-the client sent for that hop, unfortunately that hash must be discarded.
-Otherwise, it may be checked against values held from before processing
-the RELAY_COMMAND_TRUNCATED envelope.
-
-
-5. Security concerns and mitigations
-
-5.1. Silent circuit failure attacks
-
-The primary way to game this oob-hmac is to omit or block cells
-containing HMACs from reaching the OP, or otherwise tear down circuits
-before responses arrive with proof of tampering.
-
-If a large fraction of circuits somehow fail without any
-RELAY_COMMAND_TRUNCATED oob_hmac_body payloads present, and without any
-responses to RELAY_COMMAND_HMAC_GET requests, the user should be alerted
-of this fact as well.
-
-This rate of silent circuit failure should be kept as an additional,
-separate per-Guard Path Bias statistic, and the user should be warned if
-this failure rate exceeds some (low) threshold for circuits containing
-relays that should have supported this proposal.
-
-5.2. Malicious/colluding middle nodes
-
-If the adversary is prevented from causing silent circuit failure
-without the client being able to notice and react, their next available
-vector is to ensure that circuits are only built to middle nodes that
-are malicious and colluding with them (or that do not support this
-proposal), so that they may lie about the proper hash values that they
-see (or omit them).
-
-Right now, the current path bias code also does not count circuit
-failures to the middle hop as circuit attempts. This was done to reduce
-the effect of ambient circuit failure on the path bias accounting (since
-an average ambient circuit failure of X per-hop causes the total circuit
-failure middle+exit circuits to be 2X). Unfortunately, not counting
-middle hop failure allows the adversary to only allow circuits to
-colluding middle hops to complete, so that they may lie about their hash
-logs. All failed circuits to non-colluding middle nodes could be torn
-down before RELAY_COMMAND_TRUNCATED is sent.
-
-For this reason, the per-Guard Path Bias counts should be augmented to
-additionally track middle-node-only failure as a separate statistic as
-well, and the user should be warned if middle-node failure drops below a
-similar threshold as the current end-to-end failure.
-
-5.3. Side channel issues, mitigations, and limitations
-
-Unfortunately, leaking information about circuit usage to the middle
-node prevents us from sending RELAY_COMMAND_HMAC_GET cells at more
-optimal points in circuit usage (such as immediately upon open,
-immediately after stream usage, etc).
-
-As such, we are limited to waiting until RELAY_EARLY cells stop being
-sent. It is debatable if we should send hashes periodically (perhaps
-with windowing information updates?) instead.
-
-
-6. Alternatives
-
-A handful of alternatives to this proposal have already been discussed,
-but have been dismissed for various reasons. Per-hop cell HMACs were
-ruled out because they will leak the total path length, as well as the
-current hop's position in the circuit.
-
-Wide-block ciphers have been discussed, which would provide the property
-that attempts to alter a cell at a previous hop would render it
-completely corrupted upon its final destination, thus preventing
-untagging and recovery, even by a colluding malicious peer.
-
-Unfortunately, performance analysis of modern provably secure versions
-of wide-block ciphers has shown them to be at least 10X slower than
-AES-NI[2].
-
-
-1. https://lists.torproject.org/pipermail/tor-dev/2012-March/003347.html
-2. http://archives.seul.org/tor/dev/Mar-2015/msg00137.html
_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits