commit dc3683f929a747876cfb66fa1b91edff68dfc27d Author: Nick Mathewson nickm@torproject.org Date: Tue Aug 6 13:58:28 2019 -0400

update to latest version as of 11 July --- proposals/295-relay-crypto-with-adl.txt | 103 ++++++++++++++------------------ 1 file changed, 44 insertions(+), 59 deletions(-)

diff --git a/proposals/295-relay-crypto-with-adl.txt b/proposals/295-relay-crypto-with-adl.txt index f88f3cf..cfb58a2 100644 --- a/proposals/295-relay-crypto-with-adl.txt +++ b/proposals/295-relay-crypto-with-adl.txt @@ -2,7 +2,7 @@ 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 +Last-Modified: 10 July 2019 Status: Open

@@ -54,7 +54,8 @@ Status: Open 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 + Tf'_I A running digest (forward direction) + Tb'_I A running digest (backward direction) ^ XOR || Concatenation (This is more readable than a single | but must be adapted @@ -71,7 +72,7 @@ Status: Open recommend DIG_KEY_LEN = 128.

ENC_KEY_LEN -- The key length used for encryption (e.g., AES). We - recommend ENC_KEY_LEN = 128. + recommend ENC_KEY_LEN = 256.

2.4. Key derivation (replaces Section 5.2.2)

@@ -94,8 +95,8 @@ Status: Open

Length Purpose Notation ------ ------- -------- - HASH_LEN forward digest IV DF * - HASH_LEN backward digest IV DB * + 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 @@ -105,7 +106,7 @@ Status: Open DIGEST_LEN nonce to use in the * hidden service protocol

- * I am not sure that we need these any longer. + * I am not sure that we need this any longer.

Excess bytes from K are discarded.

@@ -130,6 +131,10 @@ Status: Open

3. Routing relay cells

+ Let n denote the integer representing the destination node. For + I = 1...n, we set Tf'_{I} = DF_I and Tb'_{I} = DB_I + where DF_I and DB_I are generated according to Section 2.4. + 3.1. Forward Direction

The forward direction is the direction that CREATE/CREATE2 cells @@ -137,25 +142,22 @@ Status: Open

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 + 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}) + T_{n+1} = Digest(Khf_n,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) + T_I = Digest(Khf_I,Tf'_I||C_I) N_I = T_I ^ E(Ktf_I,T_I ^ N_{I+1}) - T'_I = T_I + Tf'_I = T_I

The OP sends C_1 and N_1 to node 1.

@@ -166,10 +168,10 @@ Status: Open

'Forward' relay cell:

- T_I = Digest(Khf_I,T'_I||C_I) + T_I = Digest(Khf_I,Tf'_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 + Tf'_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 @@ -190,10 +192,10 @@ Status: Open

'Backward' relay cell:

- T_I = Digest(Khb_I,T'_I||C_{I+1}) + T_I = Digest(Khb_I,Tb'_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 + Tb'_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. @@ -207,9 +209,9 @@ Status: Open

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}) + T_I = Digest(Khb_I,Tb'_I||C_{I+1}) N_{I+1} = T_I ^ D(Ktb_I,T_I ^ N_I) - T'_I = T_I + Tb'_I = T_I

If the payload is recognized (see Section 4.1), then: @@ -229,46 +231,30 @@ Status: Open 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] + Data [PAYLOAD_LEN-21 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. + The old Digest field is removed since sufficient information for + authentication is now included in the nonce part of the payload.

- If the cell is recognized, the node moves to verifying the - authenticity of the message as follows(*): + The old 'Recognized' field is removed and the node always tries to + authenticate the message as follows:

forward direction (executed by the end node):

- T_{n+1} = Digest(Khf_n,T'_{n+1}||C_{n+1}) + T_{n+1} = Digest(Khf_n,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 + The message is recognized and 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. + The message is recognized and authenticated + (i.e., C_{n+1} = M) if and only if N_{n+1} = 0.

- (*) 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 @@ -319,31 +305,30 @@ Status: Open 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} + and N_{I+2}. Since C'_{I+2} is different from what it should be, so + are the resulting T_{I+1} and N_{I+2}. Hence, decrypting C'_{I+1} 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). + random string and cannot be authenticated. Furthermore, since + C'_{I+1} is different than what it should be, Tf'_{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 + tags the encrypted nonce N'_{I+1} != N_{I+1}. Now, when Node + I+1 digests the payload the tweak T_{I+1} is fine, 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 + random C'_{I+2} which cannot be authenticated by the end node. Since + C_{I+2} is a random string, the running digest of the end node is + now out of sync with that of OP, 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 + untagging by 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