commit d0d586fb4dc658429c9ee358808514786a980c0b Author: Isis Lovecruft <isis@torproject.org> 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