commit 8edd7803d98c6ecbf286275aa38cd48125e1521a Author: Nick Mathewson nickm@torproject.org Date: Fri Mar 1 11:58:25 2019 -0500
New version of Proposal 295 from Tomer Ashur, Orr Dunkelman, and Atul Luykx --- proposals/000-index.txt | 4 +- proposals/295-relay-crypto-with-adl.txt | 402 ++++++++++++++++++++++++++++++++ proposals/295-relay-crypto-with-atl.txt | 263 --------------------- 3 files changed, 404 insertions(+), 265 deletions(-)
diff --git a/proposals/000-index.txt b/proposals/000-index.txt index 8b01392..7cc5806 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 [CLOSED] 294 TLS 1.3 Migration [DRAFT] -295 Using ADL-GCM for relay cryptography (solving the crypto-tagging attack) [OPEN] +295 Using ADL for relay cryptography (solving the crypto-tagging attack) [OPEN] 296 Have Directory Authorities expose raw bandwidth list files [OPEN] 297 Relaxing the protover-based shutdown rules [CLOSED] 298 Putting family lines in canonical form [CLOSED] @@ -250,7 +250,7 @@ Proposals by status: 285 Directory documents should be standardized as UTF-8 287 Reduce circuit lifetime without overloading the network 289 Authenticating sendme cells to mitigate bandwidth attacks - 295 Using ADL-GCM for relay cryptography (solving the crypto-tagging attack) + 295 Using ADL for relay cryptography (solving the crypto-tagging attack) 296 Have Directory Authorities expose raw bandwidth list files 299 Preferring IPv4 or IPv6 based on IP Version Failure Count ACCEPTED: diff --git a/proposals/295-relay-crypto-with-adl.txt b/proposals/295-relay-crypto-with-adl.txt new file mode 100644 index 0000000..f88f3cf --- /dev/null +++ b/proposals/295-relay-crypto-with-adl.txt @@ -0,0 +1,402 @@ +Filename: 295-relay-crypto-with-adl.txt +Title: Using ADL for relay cryptography (solving the crypto-tagging attack) +Author: Tomer Ashur, Orr Dunkelman, Atul Luykx +Created: 22 Feb 2018 +Last-Modified: 1 March 2019 +Status: Open + + +0. Context + + Although Crypto Tagging Attacks were identified already in the + original Tor design, it was not before the rise of the + Procyonidae in 2012 that their severity was fully realized. In + Proposal 202 (Two 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) Mathewson puts forward a concrete + approach which uses the tweakable wide-block cipher AEZ. + + This proposal suggests an alternative approach to Proposal 261 + using the notion of Release (of) Unverified Plaintext (RUP) + security. It describes an improved algorithm for circuit + encryption based on CTR-mode which is already used in Tor, and an + additional component for hashing. + + Incidentally, and similar to Proposal 261, this proposal employs + the ENCODE-then-ENCIPHER approach thus it improves Tor's E2E + integrity by using (sufficient) redundancy. + + 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 . + + For authentication between the OP and the edge node we use + the PIV scheme: https://eprint.iacr.org/2013/835 + +2. Preliminaries + +2.1 Motivation + + For motivation, see proposal 202. + +2.2. Notation + + Symbol Meaning + ------ ------- + M Plaintext + C_I Ciphertext + CTR Counter Mode + N_I A de/encryption nonce (to be used in CTR-mode) + T_I A tweak (to be used to de/encrypt the nonce) + T'_I A running digest + ^ XOR + || Concatenation + (This is more readable than a single | but must be adapted + before integrating the proposal into tor-spec.txt) + +2.3. Security parameters + + HASH_LEN -- The length of the hash function's output, in bytes. + + PAYLOAD_LEN -- The longest allowable cell payload, in bytes. (509) + + DIG_KEY_LEN -- The key length used to digest messages (e.g., + using GHASH). Since GHASH is only defined for 128-bit keys, we + recommend DIG_KEY_LEN = 128. + + ENC_KEY_LEN -- The key length used for encryption (e.g., AES). We + recommend ENC_KEY_LEN = 128. + +2.4. Key derivation (replaces Section 5.2.2) + + For newer KDF needs, Tor uses the key derivation function HKDF + from RFC5869, instantiated with SHA256. The generated key + material is: + + K = K_1 | K_2 | K_3 | ... + + where, if H(x,t) denotes HMAC_SHA256 with value x and key t, + and m_expand denotes an arbitrarily chosen value, + and INT8(i) is an octet with the value "i", then + K_1 = H(m_expand | INT8(1) , KEY_SEED ) + and K_(i+1) = H(K_i | m_expand | INT8(i+1) , KEY_SEED ), + in RFC5869's vocabulary, this is HKDF-SHA256 with info == + m_expand, salt == t_key, and IKM == secret_input. + + When used in the ntor handshake a string of key material is + generated and is used in the following way: + + Length Purpose Notation + ------ ------- -------- + HASH_LEN forward digest IV DF * + HASH_LEN backward digest IV DB * + ENC_KEY_LEN encryption key Kf + ENC_KEY_LEN decryption key Kb + DIG_KEY_LEN forward digest key Khf + DIG_KEY_LEN backward digest key Khb + ENC_KEY_LEN forward tweak key Ktf + ENC_KEY_LEN backward tweak key Ktb + DIGEST_LEN nonce to use in the * + hidden service protocol + + * I am not sure that we need these any longer. + + Excess bytes from K are discarded. + +2.6. Ciphers + + For hashing(*) we use GHASH with a DIG_KEY_LEN-bit key. We write + this as Digest(K,M) where K is the key and M the message to be + hashed. + + We use AES with an ENC_KEY_LEN-bit key. For AES encryption + (resp., decryption) we write E(K,X) (resp., D(K,X)) where K is an + ENC_KEY_LEN-bit key and X the block to be encrypted (resp., + decrypted). + + For a stream cipher, unless otherwise specified, we use + ENC_KEY_LEN-bit AES in counter mode, with a nonce that is + generated as explained below. We write this as Encrypt(K,N,X) + (resp., Decrypt(K,N,X)) where K is the key, N the nonce, and X + the message to be encrypted (resp., decrypted). + + (*) The terms hash and digest are used interchangeably. + +3. Routing relay cells + +3.1. Forward Direction + + The forward direction is the direction that CREATE/CREATE2 cells + are sent. + +3.1.1. Routing from the Origin + + Let n denote the integer representing the destination node. For + I = 1...n+1, T'_{I} is initialized to the 128-bit string consisting + entirely of '0's. When an OP sends a relay cell, they prepare the + cell as follows: + + The OP prepares the authentication part of the message: + + C_{n+1} = M + T_{n+1} = Digest(Khf_n,T'_{n+1}||C_{n+1}) + N_{n+1} = T_{n+1} ^ E(Ktf_n,T_{n+1} ^ 0) + T'_{n+1} = T_{n+1} + + Then, the OP prepares the multi-layered encryption: + + For I=n...1: + C_I = Encrypt(Kf_I,N_{I+1},C_{I+1}) + T_I = Digest(Khf_I,T'_I||C_I) + N_I = T_I ^ E(Ktf_I,T_I ^ N_{I+1}) + T'_I = T_I + + The OP sends C_1 and N_1 to node 1. + +3.1.2. Relaying Forward at Onion Routers + + When a forward relay cell is received by OR I, it decrypts the + payload with the stream cipher, as follows: + + 'Forward' relay cell: + + T_I = Digest(Khf_I,T'_I||C_I) + N_{I+1} = T_I ^ D(Ktf_I,T_I ^ N_I) + C_{I+1} = Decrypt(Kf_I,N_{I+1},C_I) + T'_I = T_I + + The OR then decides whether it recognizes the relay cell as + described below. If the OR recognizes the cell, it processes the + contents of the relay cell. Otherwise, it passes C_{I+1}||N_{I+1} + along the circuit if the circuit continues. + + For more information, see section 4 below. + +3.2. Backward Direction + + The backward direction is the opposite direction from + CREATE/CREATE2 cells. + +3.2.1. Relaying Backward at Onion Routers + + When a backward relay cell is received by OR I, it encrypts the + payload with the stream cipher, as follows: + + 'Backward' relay cell: + + T_I = Digest(Khb_I,T'_I||C_{I+1}) + N_I = T_I ^ E(Ktb_I,T_I ^ N_{I+1}) + C_I = Encrypt(Kb_I,N_I,C_{I+1}) + T'_I = T_I + + with C_{n+1} = M and N_{n+1}=0. Once encrypted, the node passes + C_I and N_I along the circuit towards the OP. + +3.2.2. Routing to the Origin + + When a relay cell arrives at an OP, the OP decrypts the payload + with the stream cipher as follows: + + OP receives relay cell from node 1: + + For I=1...n, where n is the end node on the circuit: + C_{I+1} = Decrypt(Kb_I,N_I,C_I) + T_I = Digest(Khb_I,T'_I||C_{I+1}) + N_{I+1} = T_I ^ D(Ktb_I,T_I ^ N_I) + T'_I = T_I + + If the payload is recognized (see Section 4.1), + then: + + The sending node is I. Stop, process the + payload and authenticate. + +4. Application connections and stream management + +4.1. Relay cells + + Within a circuit, the OP and the end 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 as a simple indication that the + cell is still encrypted. It is an optimization to avoid + calculating expensive digests for every cell. 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^-16. + + If the cell is recognized, the node moves to verifying the + authenticity of the message as follows(*): + + forward direction (executed by the end node): + + T_{n+1} = Digest(Khf_n,T'_{n+1}||C_{n+1}) + Tag = T_{n+1} ^ D(Ktf_n,T_{n+1} ^ N_{n+1}) + T'_{n+1} = T_{n+1} + + The message is authenticated (i.e., M = C_{n+1}) if + and only if Tag = 0 + + backward direction (executed by the OP): + + The message is authenticated (i.e., C_{n+1} = M) if + and only if N_{n+1} = 0 + + + The old Digest field is removed since sufficient information for + authentication is now included in the nonce part of the payload. + + (*) we should consider dropping the 'recognized' field + altogether and always try to authenticate. Note that this is + an optimization question and the crypto works just as well + either way. + + 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 padding bytes. + +4.2. Appending the encrypted nonce and dealing with version-homogenic + and version-heterogenic circuits + + When a cell is prepared to be routed from the origin (see Section + 3.1.1) the encrypted nonce N 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 + combined with other sources to generate the layer's + nonce. Otherwise, if the node only supports the old protocol, n + is still appended to the encrypted cell (so that following nodes + can still recover their nonce), but a synchronized nonce (as per + the old protocol) is used in CTR-mode. + + 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.1. 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 padding bytes or encrypted data. + +5. Security + +5.1. Resistance to crypto-tagging attacks + + A crypto-tagging attack involves a circuit with two colluding + nodes and at least one honest node between them. The attack works + when one node makes a change to the cell (tagging) in a way that + can be undone by the other colluding party. In between, the + tagged cell is processed by honest nodes which do not detect the + change. The attack is possible due to the malleability property + of CTR-mode: a change to a ciphertext bit effects only the + respective plaintext bit in a predicatble way. This proposal + frustrates the crypto-tagging attack by linking the nonce to the + encrypted message such that any change to the ciphertext results + in a random nonce and hence, random plaintext. + + Let us consider the following 3-hop scenario: the entry and end + nodes are malicious and colluding and the middle node is honest. + +5.1.1. forward direction + + Suppose that node I tags the ciphertext part of the message + (C'_{I+1} != C_{I+1}) then forwards it to the next node (I+1). As + per Section 3.1.2. Node I+1 digests C'_{I+1} to generate T_{I+1} + and N_{I+2}. Since C'_{I+2} is different than it should be, so + are the resulting T_{I+1} and N_{I+2}. Hence, decrypting C'_{I+2} + using these values results in a random string for C_{I+2}. Since + C_{I+2} is now just a random string, it is decrypted into a + random string and cannot be 'recognized' nor + authenticated. Furthermore, since C'_{I+1} is different than what + it should be, T'_{I+1} (i.e., the running digest of the middle + node) is now out of sync with that of the OP, which means that + all future cells sent through this node will decrypt into garbage + (random strings). + + Likewise, suppose that instead of tagging the ciphertext, Node I + node tags the encrypted nonce N'_{I+1} != N_{I+1}. Now, when Node + I+1 digests the payload the tweak T_{I+1} is find, but using it + to decrypt N'_{I+1} again results in a random nonce for + N_{I+2}. This random nonce is used to decrypt C_{I+1} into a + random C'_{I+2} which is not recognized by the end node. Since + C_{I+2} is now a random string, the running digest of the end + node is now out of sync, which prevents the end node from + decrypting further cells. + +5.1.2. Backward direction + + In the backward direction the tagging is done by Node I+2 + untagging by the Node I. Suppose first that Node I+2 tags the + ciphertext C_{I+2} and sends it to Node I+1. As per Section + 3.2.1, Node I+1 first digests C_{I+2} and uses the resulting + T_{I+1} to generate a nonce N_{I+1}. From this it is clear that + any change introduced by Node I+2 influences the entire payload + and cannot be removed by Node I. + + Unlike in Section 5.1.1., the cell is blindly delivered by Node I + to the OP which decrypts it. However, since the payload leaving + the end node was modified, the message cannot be authenticated by + the OP which can be trusted to tear down the circuit. + + Suppose now that tagging is done by Node I+2 to the nonce part of + the payload, i.e., N_{I+2}. Since this value is encrypted by Node + I+1 to generate its own nonce N_{I+1}, again, a random nonce is + used which affects the entire keystream of CTR-mode. The cell + again cannot be authenticated by the OP and the circuit is torn + down. + + We note that the end node can modify the plain message before + ever encrypting it and this cannot be discovered by the Tor + protocol. This vulnerability is outside the scope of this + proposal and users should always use TLS to make sure that their + application data is encrypted before it enters the Tor network. + +5.2. End-to-end authentication + + Similar to the old protocol, this proposal only offers end-to-end + authentication rather than per-hop authentication. However, + unlike the old protocol, the ADL-construction is non-malleable + and hence, once a non-authentic message was processed by an + honest node supporting the new protocol, it is effectively + destroyed for all nodes further down the circuit. This is because + the nonce used to de/encrypt all messages is linked to (a digest + of) the payload data. + + As a result, while honest nodes cannot detect non-authentic + messages, such nodes still destroy the message thus invalidating + its authentication tag when it is checked by edge nodes. As a + result, security against crypto-tagging attacks is ensured as + long as an honest node supporting the new protocol processes the + message between two dishonest ones. + +5.3 The Running Digest + + Unlike the old protocol, the running digest is now computed as + the output of a GHASH call instead of a hash function call + (SHA256). Since GHASH does not provide the same type of security + guarantees as SHA256, it is worth discussing why security is not + lost from computing the running digest differently. + + The running digets is used to ensure that if the same payload is + encrypted twice, then the resulting ciphertext does not remain + the same. Therefore, all that is needed is that the digest should + repeat with low probability. GHASH is a universal hash function, + hence it gives such a guarantee assuming its key is chosen + uniformly at random. diff --git a/proposals/295-relay-crypto-with-atl.txt b/proposals/295-relay-crypto-with-atl.txt deleted file mode 100644 index d2a24db..0000000 --- a/proposals/295-relay-crypto-with-atl.txt +++ /dev/null @@ -1,263 +0,0 @@ -Filename: 295-relay-crypto-with-atl.txt -Title: Using ADL-GCM for relay cryptography (solving the crypto-tagging attack) -Author: Tomer Ashur, Orr Dunkelman, Atul Lyukx -Created: 09 Apr 2018 -Status: Open - -0. Context - - Although Crypto Tagging Attacks were identified already in the - original Tor design, it was not before the rise of the Procyonidae in - 2012 that their severity was fully realized. In Proposal 202 (Two - 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) Mathewson puts forward a concrete approach which uses - the tweakable wide-block cipher AEZ. - -1. Motivation - - For motivations, see proposal 202. - -2. Summary and preliminaries - - This proposal suggests an alternative approach to Proposal 261 using - the notion of Release (of) Unverified Plaintexts (RUP-security). It - 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. - - 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 - - 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., - - CTR(N) = E(N)||E(N+1)||...||E(N+l) = z_1||z_2||...||Z_{n+1} = Z - - 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 - 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.