[tor-dev] Proposal 295: Using the ATL construction for relay cryptography (solving the crypto-tagging attack)

Wed Jul 4 18:16:09 UTC 2018

Oh no!  I uploaded the wrong version of this.  I'll replace it once I
reformat the new one, but in the meantime, I'm attaching (what I hope
is) the latest version from Tomer.
-------------- next part --------------
Filename: ???
Title: Using ADL-GCM for relay cryptography (solving the crypto-tagging attack)
Author: Tomer Ashur
Created: 09 Apr 2018
Status: TBD

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. 