commit 09220cc5b7da9aae30549f0d58cd9de0d9db447d Author: Nick Mathewson nickm@torproject.org Date: Wed Jul 4 16:41:58 2018 -0400

Replace proposal 295 with the right version :/ --- proposals/000-index.txt | 4 +- proposals/295-relay-crypto-with-atl.txt | 469 ++++++++++++++++---------------- 2 files changed, 230 insertions(+), 243 deletions(-)

diff --git a/proposals/000-index.txt b/proposals/000-index.txt index d9c7e93..6b3295f 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -215,7 +215,7 @@ Proposals by number: 292 Mesh-based vanguards [ACCEPTED] 293 Other ways for relays to know when to publish [OPEN] 294 TLS 1.3 Migration [DRAFT] -295 Using the ATL construction for relay cryptography (solving the crypto-tagging attack) [OPEN] +295 Using ADL-GCM for relay cryptography (solving the crypto-tagging attack) [OPEN]

Proposals by status: @@ -245,7 +245,7 @@ Proposals by status: 287 Reduce circuit lifetime without overloading the network 289 Authenticating sendme cells to mitigate bandwidth attacks 293 Other ways for relays to know when to publish [for 0.3.5] - 295 Using the ATL construction for relay cryptography (solving the crypto-tagging attack) + 295 Using ADL-GCM for relay cryptography (solving the crypto-tagging attack) ACCEPTED: 188 Bridge Guards and other anti-enumeration defenses 249 Allow CREATE cells with >505 bytes of handshake data diff --git a/proposals/295-relay-crypto-with-atl.txt b/proposals/295-relay-crypto-with-atl.txt index 74e31b1..73eb98b 100644 --- a/proposals/295-relay-crypto-with-atl.txt +++ b/proposals/295-relay-crypto-with-atl.txt @@ -1,10 +1,9 @@ Filename: 295-relay-crypto-with-atl.txt -Title: Using the ATL construction for relay cryptography (solving the crypto-tagging attack) +Title: Using ADL-GCM for relay cryptography (solving the crypto-tagging attack) Author: Tomer Ashur Created: 09 Apr 2018 Status: Open

- 0. Context

Although Crypto Tagging Attacks were identified already in the @@ -13,8 +12,8 @@ Status: Open improved relay encryption protocols for Tor cells) Nick Mathewson discussed two approaches to stymie tagging attacks and generally improve Tor's cryptography. In Proposal 261 (AEZ for relay - cryptography) Nick put forward a concrete approach which uses the - tweakable wide-block cipher AEZ. + cryptography) Mathewson puts forward a concrete approach which uses + the tweakable wide-block cipher AEZ.

1. Motivation

@@ -27,250 +26,238 @@ Status: Open describes an improved algorithm for circuit encryption based on CTR-mode which is already used in Tor, and an additional component for hashing. When this additional component is GHash, a GCM-based - solution can be used from the OpenSSL library. If a solution that is - based solely on components that already exist in Tor is desirable, - SHA-1 can be used for hashing (however, this is highly discouraged as - SHA-1 is broken!). + solution can be used from the OpenSSL library.

Incidentally, and similar to Proposal 261, this proposal employs the ENCODE-then-ENCIPHER approach thus it improves Tor's E2E integrity by using (sufficiently enough) redundancy.

- For more information about the scheme and a security proof for its - RUP-security see + For more information about the scheme and a security proof for its + RUP-security see + + Tomer Ashur, Orr Dunkelman, Atul Luykx: Boosting Authenticated + Encryption Robustness with Minimal Modifications. CRYPTO (3) + 2017: 3-33 available online at https://eprint.iacr.org/2017/239 . + +2.1. Cryptographic algorithms + + As an encryption primitive we use AES. We denote one call to the + primitive by E(·), e.g., + + Z = E_k(X) + + where k is a K-bit key, X is the input to AES and Z is the output. We + omit k where it is irrelevant or is clear from context. While we + propose to set K=256 to ensure long-term post-quantum resistance, we + stress that the solution also works for other key lengths. + + To encrypt, we use AES is counter mode and a nonce N to produce a + random bit stream, e.g.,

- Tomer Ashur, Orr Dunkelman, Atul Luykx: Boosting Authenticated - Encryption Robustness with Minimal Modifications. CRYPTO (3) 2017: - 3-33 available online at https://eprint.iacr.org/2017/239 . + CTR(N) = E(N)||E(N+1)||...||E(N+l) = z_1||z_2||...||Z_{n+1} = Z

-2.1 An instructive 1-node circuit + and XOR Z with the message M to produce the ciphertext C, e.g., + + C = Z ^ M + + For authentication, we use the universal hash function GHASH and a + key k, e.g., + + T = H(K||X) = H_k(X) + + where K is a 256-bit key, X an arbitrary length string, and T a + unique authentication tag for X. While we propose to set K=256 to + ensure long-term post-quantum resistance, we stress that the solution + works for any universal hash function as well as for keys of length + K!=256. + +3. The proposed solution + +3.1 An overview of the proposed solution

Noting that in CTR-mode the nonce is essential for the encryption/decryption operations, the proposed solution is based on - encrypting its value in such a way that any change to the ciphertext - or the tag (e.g., through a tagging attack) would randomize the nonce - and result in a random value as the output of CTR-mode. - - The basic crypto components of the proposal are: - * a block cipher E(·) - * A universal hash function, H(·); - - Using the block cipher E(·) and a non-repeating nonce N, one can - construct the CTR mode-of-operation: - - CTR(N) = E(N)||E(N+1)||...||E(N+l) - - For simplicity, let us for now consider normal encryption using - CTR-mode (This is akin to building a circuit with a single node. In - the sequel we will see what happens when this idea is used in a 3-node - circuit): - - * Input: a nonce N, a message M = (m_0,...,m_l) - 1. (z_0,...,z_l) = CTR(N) - 2. (c_0,...,c_l) = (z_0 ^ m_0, ... z_l ^ m_l) - - The client sends C = (c_0,...,c_l) to the receiver which repeats Step - (1) to generate the random stream Z = (z_0,...,z_l) and recovers the - message through M = C ^ Z. A protocol using this scheme is vulnerable - to the crypto tagging attack due to the malleability of - CTR-mode. Indeed, since Z depends only on N rather than on the - message M itself, a change to a ciphertext bit affects the respective - plaintext bit and nothing else. - - Our solution is based on the idea that linking N and C makes it - impossible to change C without affecting N (and hence Z) in such a - way that it is impossible to recover M. This can be done by extending - the protocol in the following way: - - 3. X = H(C) - 4. S = X ^ E(N ^ X) - - Now, instead of sending C, the client sends C||S to the receiver. To - decrypt, the receiver first repeats Step (3) to obtain X, then - inverts Step (4) to obtain N: N = D(S ^ X) ^ X (where D(·) is the - inverse function of E(·)). Then, having obtained N, the receiver - continues to decrypt C as before. If the receiver already knows N - (e.g., in the case of a synchronized nonce), they can authenticate C - by comparing N = D(S ^ X) ^ X to the nonce they expect. - - Let us consider what happens when a change is made to C. Let C' be a - variant of C with one or more bits flipped. Since H(·) is a universal - hash function, X' = H(C' ≠ C) is random. Trying to execute D(S ^ X') - ^ X' would result in a random N' ≠ N which in turn would result in a - random Z' (and hence a random M'). Similarly for a change in S. - -2.2 Extending to a 3-node Tor circuit - - The Tor protocol uses layered encryption to encapsulate the - message. Generally speaking, this can be written as: - - * input: synchronized nonces (N^0, N^1, N^2), a message M = (m_0,...,m_l) - 1. (z^2_0,...,z^2_l) = CTR(N^2) - 2. (c^2_0,...,c^2_l) = (z^2_0 ^ m_0, ... z^2_l ^ m_l) - 3. (z^1_0,...,z^1_l) = CTR(N^1) - 4. (c^1_0,...,c^1_l) = (z^1_0 ^ c^2_0, ... z^1_l ^ c^2_l) - 5. (z^0_0,...,z^0_l) = CTR(N^0) - 6. (c^0_0,...,c^0_l) = (z^0_0 ^ c^1_0, ... z^0_l ^ c^0_l) - - The crypto-tagging stems from the fact that a change to C affects M - directly since all z^j_i depend only on N^j rather than on C^j. - - An extension of the 1-layer solution presented in Section 2.1 would - look like this: - - * Input: a nonce N, a message M = (m_0,...,m_l) - 1. (z^2_0,...,z^2_l) = CTR(N) - 2. (c^2_0,...,c^2_l) = (z^2_0 ^ m_0, ... z^2_l ^ m_l) - 3. X^2 = H(C^2) - 4. S^2 = X^2 ^ E(N^2 ^ X^2) - - 5. (z^1_0,...,z^1_l) = CTR(S^2) - 6. (c^1_0,...,c^1_l) = (z^1_0 ^ c^2_0, ... z^1_l ^ c^2_l) - 7. X^1 = H(C^1) - 8. S^1 = X^1 ^ E(S^2 ^ X^1) - - 9. (z^0_0,...,z^0_l) = CTR(S^1) - 10. (c^0_0,...,c^0_l) = (z^0_0 ^ c^1_0, ... z^1_l ^ c^0_l) - 11. X^0 = H(C^0) - 12. S^0 = X^0 ^ E(S^1 ^ X^0) - - The client sends the message C^0||S^0 = ((c^0_0,...,c^0_l)||S^0) to - the guard. To decrypt, the guard repeats Step (11) and inverts Step - (12) to obtain S^1 which it uses to generate Z^0 and decrypt C^0 into - C^1. The guard then forwards C^1||S^1 to the middle node which - repeats this process and forwards C^2||S^2 to the exit. The exit - removes the final encryption layer and processes the cell as in the - old protocol. - - Let us now consider what happens when the crypto tagging attack is - applied to this protocol. Without loss of generality, after inverting - Step (11) the guard tags either C^1 or S^1 and forwards C'^1||S'^1 to - the middle node. The middle node, unaware of the change follows the - protocol to decrypt C'^1||S'^1 which results in a random string as - per the explanation above. Since both CircID and CMD are not part of - the payload, the middle node can still forward the random string - (unaware of this fact) to the exit node. Upon receiving the random - string, the exit node decrypts it, sees that the 'Rec' field is not - all-zero and acts accordingly. - - -3. Design considerations - -3.1 Choice of primitives - - We stress that the proposed protocol is primitive agnostic. - - Noting that Tor currently uses AES_CTR we tried to design a solution - that requires only minimal changes. Most importantly, the encryption - is still performed using CTR-mode, and can be instantiated using - AES_CTR (however, the solution works just as well with any other - block cipher). - - The hashing of the ciphertext requires a universal hash function. The - GCM mode of operation uses CTR+GHash and is available from the - OpenSSL crypto library which is already used within Tor. Any - available universal hash function can be used instead of GHash if the - latter introduces an unacceptable latency. - - The nonce-encryption step uses a tweakable block cipher. In the - example above we used the XEX trick to transform a "regular" block - cipher into a tweakable block cipher which allows reusing whatever - underlying primitive is used in CTR-mode. A tweakable block cipher - can be used directly (with X as the tweak) if one is available but - this is not required. - -3.2 Security requirements - - In Proposal 202, Nick Mathewson outlined the security requirements - for any solution. We copy them here verbatim and discuss how each of - them is addressed in the proposed solution: - - * " ... we'd like any attacker who controls a node on the circuit - not to have a good way to learn any other nodes, even if he/she - controls those nodes" - By construction, once processed by an - honest node the cell's payload is completely destroyed, thus - unlinking any relation between what is seen by nodes further - down the circuit and the original message. An adversary - controlling the exit node can still see that the circuit turned - into junk (borrowing the professional jargon of Proposal 202); - this seems unavoidable (if any of the other proposals somehow - solved this, we would like to know so we can see if it can - somehow be adapted here. - - * "no relay should be able to alter a cell between an honest sender - and an honest recipient in a way that they cannot detect" - Any - alternation of a cell between a sender and a recipient will be - decrypted to junk and never delivered to the recipient. (**) - - * "Relay cells should be secret: nobody but the sender and - recipient of a relay cell should be able to learn what it says." - - since the protocol is an extension of the existing one, - whatever secrecy was present before remains so. - - * "... Circuits should resist transparent, recoverable tagging - attacks... " - that's the whole point. Once a change was injected - and passed to an adjacent honest node, no node further down the - circuit can recover the relay cell. - - * "... The above properties should apply to sequences of cells - too... " - this one is more tricky. To the best of my - understanding this property is currently ensured through the - 'Digest' field in the payload. Keeping this field, our solution - can provide the same functionality as before. However, - re-arranging the 'Rec' and 'Digest' fields in a way similar to - Proposal 261 would reduce the overhead but would require - developing a different solution. It seems possible though. (*) - - In addition to supporting these security requirements, this proposal - improves Tor's E2E authentication by replacing the broken SHA-1 with - an ENCODE-then-ENCIPHER authentication. By introducing redundancy to - the cell (either through the 'Rec' and 'Digest' fields or otherwise) - the exit node can verify that the cell was not altered en route. This - is similar to what is done in Proposal 261 but without the trouble of - using a tweakable wide-block cipher. - - (*) a possible solution would be to digest X as part of H(C) but - this requires further discussion. - - (**) my understanding is that a single circuit can be used for - more than one TCP stream. If this is not the case, then the - recipient receives a random string and can identify that this is - not a valid message. - - -3.3 Feature requirements - - - In addition to security requirements, Proposal 202 also discusses - some feature requirements. We discuss two of them here as the others - seems to be trivially supported (although this needs to be verified - by someone who understands Tor better than me). - - - * "Any new approach should be able to coexist on a circuit with the - old approach" - following the IRC discussion, we had an internal - discussion and we think that the proposed solution works even if - only the middle node supports the new protocol. This involves - encrypting the nonce only for the middle nonce. We came up with - two ways to achieve this, both have their pro's and con's and - should be discussed once we agree on the general idea. - - Since the Crypto tagging attack requires a collusion between a - corrupted guard and a corrupted exit, it does not make sense to - discuss what happens when one of them runs the new protocol. - - * "Cell length needs to be constant as cells move through the - network." - The solution was designed to allow for a fixed cell - size. this should be discussed though. - -4. Specifications - TBD - -5. Compatibility - See Section 3.3 - -6. Implementation - TBD - -7. Performance and scalability notes - TBD + linking the nonce and the transmitted data in such a way that any + change to the data (e.g., through a tagging attack) randomizes the + nonce and results in a random value Z' != Z for CTR(N' != N). + +3.1.1. 'Forward' direction (same direction as CREATE): + + When preparing a message to be sent in the forward direction, the + client is responsible for encrypting all layers. The client starts by + digesting the message to create a synthetic tweak T_0 = H_{k_fM}(M) + and uses this tweak to encrypt an all-zero string to create a + synthetic IV: S_0 = T_0 ^ E_{k_fE}(0 ^ T_0). + + The message and the synthetic IV (i.e., M||S_0) are passed as input + to the first encryption layer which uses S_0 to produce the random + stream Z = CTR_k1(S_0) and the ciphertext C = Z ^ M. Then, a tweak T + = H_k2(C) is generated by digesting the ciphertext of this + layer. Finally, S_0 is encrypted using AES and the tweak T to produce + an encrypted nonce S = T ^ E_k3(N ^ T) which is appended to the the + ciphertext and is used as the nonce for the next encryption layer. + + After encrypting 3 times, the client sends C||S to the guard. Whereas + the protocol previously required that the nonce be kept in sync + between each node and the client, this is no longer required as it + can now be recovered from C||S. To decrypt, the node first computes T + = H_k2(C) then uses it to obtain S = D_k3(S ^ T) ^ T. Finally, CTR(S) + is used to decrypt C into M. The once-decrypted nonce is appended to + the data and M||S is sent to the next node which repeats this + process. + + The exit verifies the integrity of the message by digesting it and + using the resulting T to decrypt S_0 into N. If N=0, the message is + authenticated. Otherwise, if the message has been changed by an + adversary, N!=0 and the circuit is destroyed. + +3.1.2 'Back' direction (opposite direction from CREATE): + + When sending back a message from the exit to the client, each node + adds an additional layer of encryption. The exit starts by digesting + the message to create a synthetic tweak T_0 = H_{k_bM}(M) and uses + this tweak to encrypt an all-zero string to create a synthetic IV: + S_0 = T_0 ^ E_{k_bE}(0 ^ T_0). The synthetic IV is then used to + produce the random stream Z = CTR_k1(S_0) and uses that to encrypt + the plaintext through C = Z ^ M. The nonce is appended to the + ciphertext and C||S_0 is sent to the next node. + + Receiving a message from the exit, the middle starts by producing a + tweak T = H_k2(C). The tweak is then used to encrypt the nonce + through S = T ^ E_k3(N ^ T) which is then used to produce the random + stream Z' = CTR_k1(S). Finally, the message is encrypted via C' = Z' + ^ C and the encrypted nonce is appended to C'. The message C'||S is + sent to the next node which repeats this procedure. + + When the message arrives at the client, the client peels each layer + using the nonce that is appended at the end of the message. The + decrypted layer is used to compute the tweak T = H_k2(P), which is + used to decrypt this layer's nonce into the next layer's nonce. + + The client verifies the integrity of the message by digesting it and using + the resulting T to decrypt S_0 into N. If N=0, the message is + authenticated. Otherwise, if the message has been changed by an adversary, + N!=0 and the circuit is destroyed. + +3.2 Circuit management + +3.2.1 Creating circuits + + The general process of creating a circuit remains the same (see + tor-spec.txt), except for step 5 where instead of creating a pair of + keys (kf_1,kb_1) for forward and backward communication, + respectively, 2 triplets of keys (kf_1,kf_2,kf_3) and + (kb_1,kb_2,kb_3) are created for communication in the forward and + backward directions, respectively. Two additional pairs of + "authentication keys" (k_fM,k_fE) and (k_bM,k_bE) are created between + the client and the exit in the forward and backward directions, + respectively. + + note: the keys can be created by running KDF-RFC5869 3 times in each + direction, or by running it once in each direction to create a + master-key and derive the rest as subkeys from this master key + +3.2.2 Routing relay cells + + When an OR receives a RELAY or RELAY_EARLY cell, it checks the cell's + circID and determines whether it has a corresponding circuit along + that connection. If not, the OR drops the cell. + + Otherwise, if the OR is not at the OP edge of the circuit (that is, + either an 'exit node' or a non-edge node), it de/encrypts the payload + with the stream cipher, as follows (the message structure is C||S): + + 'Forward' relay cell (same direction as CREATE) + (input structure is: C||S): + + 1. T = H_{kf_2}(T'||C); digest ciphertext (T' is a running digest + of all previous cells, i.e., last round's T) + + 2. N = T ^ D_{kf_3}(S ^ T); decrypt nonce + + 3. M = CTR_{kf_1}(N) ^ C; decrypt message + (output structure is M||N) + + 'Back' relay cell (opposite direction from CREATE) + (input structure is: M||N): + + 1. T = H_{kb_2}(T'||M); digest ciphertext (T' is a running digest + of all previous cells, i.e., last round's T) + + 2. S = T ^ E_{kb_3}(N ^ T); encrypt nonce + + 3. C = CTR_{kb_1}(S) ^ M; encrypt message + (output structure is C||S) + + Note that in counter mode, decrypt (D) and encrypt (E) are the same + operation. + + The OR then decides whether it recognizes the relay cell, by + inspecting the payload as described in Section 4.1 below. If the OR + recognizes the cell, it processes the contents of the relay cell. + Otherwise, it passes the decrypted relay cell along the circuit if + the circuit continues. If the OR at the end of the circuit + encounters an unrecognized relay cell, an error has occurred: the OR + sends a DESTROY cell to tear down the circuit. + +4. Application connections and stream management + +4.1 Relay cells + + Within a circuit, the OP and the exit node use the contents of RELAY + packets to tunnel end-to-end commands and TCP connections ("Streams") + across circuits. End-to-end commands can be initiated by either + edge; streams are initiated by the OP. + + The payload of each unencrypted RELAY cell consists of: + Relay command [1 byte] + 'Recognized' [2 bytes] + StreamID [2 bytes] + Length [2 bytes] + Data [PAYLOAD_LEN-23 bytes] + + The 'recognized' field is used for a simple indication if the cell + still encrypted or not. When sending cells, the unencrypted + 'recognized' MUST be set to zero. + + When receiving and decrypting cells the 'recognized' will always be + zero if we're the endpoint that the cell is destined for. For cells + that we should relay, the 'recognized' field will usually be nonzero, + but will accidentally be zero with P=2^-32. + + The old Digest field is removed, since sufficient information for + authentication is now included in the all-zero string used to create the + nonce for the first encryption layer. + + The 'Length' field of a relay cell contains the number of bytes in + the relay payload which contain real payload data. The remainder of + the payload is padded with NUL bytes. + +4.2 Appending the encrypted nonce + + When a cell is prepared by the client to be sent in the 'forward' + direction, as explained in Section 3.2.2, the encrypted nonce S is + appended to the encrypted cell (occupying the last 16 bytes of the + cell). If the cell is prepared to be sent to a node supporting the + new protocol, S is used as the nonce for the next round's + encryption. Otherwise, if the next node only supports the old + protocol, S is still appended to the encrypted cell, but a + synchronized nonce (as per the old protocol) is used for encryption. + + When a cell is sent along the circuit in the 'backward' direction, + nodes supporting the new protocol always assume that the last 16 + bytes of the input are the nonce used by the previous node, which + they process as per Section 3.2.2. If the previous node also supports + the new protocol, these cells are indeed the nonce. If the previous + node only supports the old protocol, these bytes are either encrypted + NUL bytes or encrypted data. + +4.3 Authenticating the message + + End-to-end authentication is performed in both directions in the same + way. Once the final layer of encryption is removed, the + message-to-be-authenticated is digested and this digest is used to + decrypt the nonce used in this layer. If the decrypted nonce is + all-zero, the message is authentic. Otherwise, if a change was made + to the ciphertext or the encrypted nonce somewhere along the circuit, + the nonce decrypts into a random value and the circuit is destroyed.