295-relay-crypto-with-adl.txt

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: 13 Jan. 2020
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 .

   A recent paper presented a birthday bound distinguisher
   against the ADL scheme, thus showing that the RUP security
   proof is tight: https://eprint.iacr.org/2019/1359 .


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)
   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
          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 = 256.

2.4. Key derivation (replaces Section 5.2.2 in Tor-spec.txt)

   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 authentication digest IV 	AF
   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 if this is still needed.

   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.
   (**) Proposal 308 suggested that using POLYVAL [GLL18]
        would be more efficient here. This proposal will work just the
		same if POLYVAL is used instead of GHASH.

3. Routing relay cells

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

3.1. Forward Direction

   The forward direction is the direction that CREATE/CREATE2 cells
   are sent.

3.1.1. Routing from the origin

   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
                Ta_I = Digest(Khf_n,Ta'_I||C_{n+1})
                N_{n+1} = Ta_I ^ E(Ktf_n,Ta_I ^ 0)
		Ta'_{I} = Ta_I

        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,Tf'_I||C_I)
                        N_I = T_I ^ E(Ktf_I,T_I ^ N_{I+1})
                        Tf'_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,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)
                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
   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,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})
                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.

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,Tb'_I||C_{I+1})
                        N_{I+1} = T_I ^ D(Ktb_I,T_I ^ N_I)
                        Tb'_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]
                StreamID                [2 bytes]
                Length                  [2 bytes]
                Data                    [PAYLOAD_LEN-21 bytes]


   The old Digest field is removed since sufficient information for
   authentication is now included in the nonce part of the payload.

   The old 'Recognized' field is removed and the node always tries to
   authenticate the message as follows.

4.1.1 forward direction (executed by the end node):

				Ta_I = Digest(Khf_n,Ta'_I||C_{n+1})
				Tag = Ta_I ^ D(Ktf_n,Ta_I ^ N_{n+1})

				If Tag = 0:
                  Ta'_I = Ta_I
                  The message is authenticated.
             Otherwise:
                  Ta'_I remains unchanged.
                  The message is not authenticated.


4.1.2 backward direction (executed by the OP):

                The message is recognized and authenticated
				(i.e., C_{n+1} = M) if and only if N_{n+1} = 0.


   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 above) 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, N is
   used 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 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 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
   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 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 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 digest 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.

6. Forward secrecy

   Inspired by the approach of Proposal 308, a small modification
   to this proposal makes it forward secure. The core idea is to
   replace the encryption key KF_n after de/encrypting the cell.
   As an added benefit, this would allow to keep the authentication
   layer stateless (i.e., without keeping a running digest for
   this layer).

   Below we present the required changes to the sections above.

6.1. Routing from the Origin (replacing 3.1.1 above)

   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,C_{n+1})
			N_{n+1} = T_{n+1} ^ E(Ktf_n,T_{n+1} ^ 0)


        Then, the OP prepares the multi-layered encryption:
			For the final layer n:
				(C_n,Kf'_n) = Encrypt(Kf_n,N_{n+1},C_{I+1}||0||0) (*)
				T_n = Digest(Khf_I,Tf'_n||C_n)
				N_n = T_I ^ E(Ktf_n,T_n ^ N_{n+1})
				Tf'_n = T_n
				Kf_n = Kf'_n

				(*) CTR mode is used to generate two additional blocks. This
					256-bit value is denoted K'f_n and is used in subsequent
					steps to replace the encryption key of this layer.
					To achieve forward secrecy it is important that the
					obsolete Kf_n is erased in a non-recoverable way.

                For layer I=(n-1)...1:
                        C_I = Encrypt(Kf_I,N_{I+1},C_{I+1})
                        T_I = Digest(Khf_I,Tf'_I||C_I)
                        N_I = T_I ^ E(Ktf_I,T_I ^ N_{I+1})
                        Tf'_I = T_I

		The OP sends C_1 and N_1 to node 1.

	Alternatively, if we want that all nodes use the same functionality
	OP prepares the cell as follows:

			For layer I=n...1:
				(C_I,K'f_I) = Encrypt(Kf_I,N_{I+1},C_{I+1}||0||0) (*)
				T_I = Digest(Khf_I,Tf'_I||C_I)
				N_I = T_I ^ E(Ktf_I,T_I ^ N_{I+1})
				Tf'_I = T_I
				Kf_I = Kf'_I

				(*) CTR mode is used to generate two additional blocks. This
					256-bit value is denoted K'f_n and is used in subsequent
					steps to replace the encryption key of this layer.
					To achieve forward secrecy it is important that the
					obsolete Kf_n is erased in a non-recoverable way.

		This scheme offers forward secrecy in all levels of the circuit.

6.2. Relaying Forward at Onion Routers (replacing 3.1.2 above)

   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,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||0||0)
                Tf'_I = T_I

   The OR then decides whether it recognizes the relay cell as described below.
   Depending on the choice of scheme from 6.1 the OR uses the last two blocks
   of C_{I+1} to update the encryption key or discards them.

   If the cell is recognized the OR also 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 about recognizing and authenticating relay cells,
   see 5.4.5 below.

6.3. Relaying Backward at Onion Routers (replacing 3.2.1 above)

   When an edge node receives a message M to be routed back to the
   origin, it encrypts it as follows:

		T_n = Digest(Khb_n,Tb'_n||M)
                N_n = T_n ^ E(Ktb_n,T_n ^ 0)
                (C_n,K'b_n) = Encrypt(Kb_n,N_n,M||0||0) (*)
                Tb'_n = T_n
		Kb_n = K'b_n

				(*) CTR mode is used to generate two additional blocks. This
					256-bit value is denoted K'b_n and will be used in
					subsequent steps to replace the encryption key of this layer.
					To achieve forward secrecy it is important that the obsolete
					K'b_n is erased in a non-recoverable way.

    Once encrypted, the edge node sends C_n and N_n along the circuit towards
	the OP. When a backward relay cell is received by OR_I (I<n), it encrypts
	the payload with the stream cipher, as follows:

        'Backward' relay cell:

                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})
                Tb'_I = T_I

   Each node passes C_I and N_I along the circuit towards the OP.

   If forward security is desired for all layers in the circuit, all OR's
   encrypt as follows:
		T_I = Digest(Khb_I,Tb'_I||C_{I+1})
                N_I = T_I ^ E(Ktb_I,T_I ^ 0)
                (C_I,K'b_I) = Encrypt(Kb_n,N_n,M||0||0)
                Tb'_I = T_I
		Kb_I = K'b_I


6.4. Routing to the Origin (replacing 3.2.2 above)

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

				And updates the encryption keys according to the strategy
				chosen for 6.3.

                If the payload is recognized (see Section 4.1),
                then:

                       The sending node is I. Process the payload!


6.5. Recognizing and authenticating a relay cell (replacing 4.1.1 above):

	Authentication in the forward direction is done as follows:

		T_{n+1} = Digest(Khf_n,C_{n+1})
                Tag = T_{n+1} ^ D(Ktf_n,T_{n+1} ^ N_{n+1})

	The message is recognized and authenticated
				(i.e., M = C_{n+1}) if and only if Tag = 0.

	No changes are required to the authentication process when the relay
	cell is sent backwards.