commit b652790f6082a15d45665fef88d3ee244a224a64 Author: Mike Perry mikeperry-git@torproject.org Date: Fri Sep 4 17:36:43 2015 -0700
Add out-of-band hmac proposal draft. --- proposals/xxx-oob-hashmac.txt | 272 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 272 insertions(+)
diff --git a/proposals/xxx-oob-hashmac.txt b/proposals/xxx-oob-hashmac.txt new file mode 100644 index 0000000..9027abd --- /dev/null +++ b/proposals/xxx-oob-hashmac.txt @@ -0,0 +1,272 @@ +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