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

[Nick Mathewson]

Here is (I hope) the correct version of this proposal, reformatted.
Filename: 295-relay-crypto-with-atl.txt
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
   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.