Replace proposal 295 with the right version :/

2 files changed, 230 insertions, 243 deletions

diff --git a/proposals/000-index.txt b/proposals/000-index.txt
index d9c7e93..6b3295f 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 [OPEN]
 294  TLS 1.3 Migration [DRAFT]
-295  Using the ATL construction for relay cryptography (solving the crypto-tagging attack) [OPEN]
+295  Using ADL-GCM for relay cryptography (solving the crypto-tagging attack) [OPEN]
 
 
 Proposals by status:
@@ -245,7 +245,7 @@ Proposals by status:
    287  Reduce circuit lifetime without overloading the network
    289  Authenticating sendme cells to mitigate bandwidth attacks
    293  Other ways for relays to know when to publish [for 0.3.5]
-   295  Using the ATL construction for relay cryptography (solving the crypto-tagging attack)
+   295  Using ADL-GCM for relay cryptography (solving the crypto-tagging attack)
  ACCEPTED:
    188  Bridge Guards and other anti-enumeration defenses
    249  Allow CREATE cells with >505 bytes of handshake data
diff --git a/proposals/295-relay-crypto-with-atl.txt b/proposals/295-relay-crypto-with-atl.txt
index 74e31b1..73eb98b 100644
--- a/proposals/295-relay-crypto-with-atl.txt
+++ b/proposals/295-relay-crypto-with-atl.txt
@@ -1,10 +1,9 @@
 Filename: 295-relay-crypto-with-atl.txt
-Title: Using the ATL construction for relay cryptography (solving the crypto-tagging attack)
+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
@@ -13,8 +12,8 @@ Status: Open
    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) Nick put forward a concrete approach which uses the
-   tweakable wide-block cipher AEZ.
+   cryptography) Mathewson puts forward a concrete approach which uses
+   the tweakable wide-block cipher AEZ.
 
 1. Motivation
 
@@ -27,250 +26,238 @@ Status: Open
    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. If a solution that is
-   based solely on components that already exist in Tor is desirable,
-   SHA-1 can be used for hashing (however, this is highly discouraged as
-   SHA-1 is broken!).
+   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
+   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.,
 
-      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 .
+       CTR(N) = E(N)||E(N+1)||...||E(N+l) = z_1||z_2||...||Z_{n+1} = Z
 
-2.1 An instructive 1-node circuit
+   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
-   encrypting its value in such a way that any change to the ciphertext
-   or the tag (e.g., through a tagging attack) would randomize the nonce
-   and result in a random value as the output of CTR-mode.
-
-	The basic crypto components of the proposal are:
-		* a block cipher E(·)
-		* A universal hash function, H(·);
-
-   Using the block cipher E(·) and a non-repeating nonce N, one can
-   construct the CTR mode-of-operation:
-
-		CTR(N) = E(N)||E(N+1)||...||E(N+l)
-
-  For simplicity, let us for now consider normal encryption using
-  CTR-mode (This is akin to building a circuit with a single node. In
-  the sequel we will see what happens when this idea is used in a 3-node
-  circuit):
-
-		* Input: a nonce N, a message M = (m_0,...,m_l)
-		1. (z_0,...,z_l) = CTR(N)
-		2. (c_0,...,c_l) = (z_0 ^ m_0, ... z_l ^ m_l)
-
-   The client sends C = (c_0,...,c_l) to the receiver which repeats Step
-   (1) to generate the random stream Z = (z_0,...,z_l) and recovers the
-   message through M = C ^ Z. A protocol using this scheme is vulnerable
-   to the crypto tagging attack due to the malleability of
-   CTR-mode. Indeed, since Z depends only on N rather than on the
-   message M itself, a change to a ciphertext bit affects the respective
-   plaintext bit and nothing else.
-
-   Our solution is based on the idea that linking N and C makes it
-   impossible to change C without affecting N (and hence Z) in such a
-   way that it is impossible to recover M. This can be done by extending
-   the protocol in the following way:
-
-		3. X = H(C)
-		4. S = X ^ E(N ^ X)
-
-   Now, instead of sending C, the client sends C||S to the receiver. To
-   decrypt, the receiver first repeats Step (3) to obtain X, then
-   inverts Step (4) to obtain N: N = D(S ^ X) ^ X (where D(·) is the
-   inverse function of E(·)).  Then, having obtained N, the receiver
-   continues to decrypt C as before. If the receiver already knows N
-   (e.g., in the case of a synchronized nonce), they can authenticate C
-   by comparing N = D(S ^ X) ^ X to the nonce they expect.
-
-   Let us consider what happens when a change is made to C. Let C' be a
-   variant of C with one or more bits flipped. Since H(·) is a universal
-   hash function, X' = H(C' ≠ C) is random. Trying to execute D(S ^ X')
-   ^ X' would result in a random N' ≠ N which in turn would result in a
-   random Z' (and hence a random M'). Similarly for a change in S.
-
-2.2 Extending to a 3-node Tor circuit
-
-   The Tor protocol uses layered encryption to encapsulate the
-  message. Generally speaking, this can be written as:
-
-	* input: synchronized nonces (N^0, N^1, N^2), a message M = (m_0,...,m_l)
-	1. (z^2_0,...,z^2_l) = CTR(N^2)
-	2. (c^2_0,...,c^2_l) = (z^2_0 ^ m_0, ... z^2_l ^ m_l)
-	3. (z^1_0,...,z^1_l) = CTR(N^1)
-	4. (c^1_0,...,c^1_l) = (z^1_0 ^ c^2_0, ... z^1_l ^ c^2_l)
-	5. (z^0_0,...,z^0_l) = CTR(N^0)
-	6. (c^0_0,...,c^0_l) = (z^0_0 ^ c^1_0, ... z^0_l ^ c^0_l)
-
-   The crypto-tagging stems from the fact that a change to C affects M
-   directly since all z^j_i depend only on N^j rather than on C^j.
-
-   An extension of the 1-layer solution presented in Section 2.1 would
-   look like this:
-
-	* Input: a nonce N, a message M = (m_0,...,m_l)
-	1.  (z^2_0,...,z^2_l) = CTR(N)
-	2.  (c^2_0,...,c^2_l) = (z^2_0 ^ m_0, ... z^2_l ^ m_l)
-	3.  X^2 = H(C^2)
-	4.  S^2 = X^2 ^ E(N^2 ^ X^2)
-
-	5.  (z^1_0,...,z^1_l) = CTR(S^2)
-	6.  (c^1_0,...,c^1_l) = (z^1_0 ^ c^2_0, ... z^1_l ^ c^2_l)
-	7.  X^1 = H(C^1)
-	8.  S^1 = X^1 ^ E(S^2 ^ X^1)
-
-	9.  (z^0_0,...,z^0_l) = CTR(S^1)
-	10. (c^0_0,...,c^0_l) = (z^0_0 ^ c^1_0, ... z^1_l ^ c^0_l)
-	11. X^0 = H(C^0)
-	12. S^0 = X^0 ^ E(S^1 ^ X^0)
-
-   The client sends the message C^0||S^0 = ((c^0_0,...,c^0_l)||S^0) to
-   the guard. To decrypt, the guard repeats Step (11) and inverts Step
-   (12) to obtain S^1 which it uses to generate Z^0 and decrypt C^0 into
-   C^1. The guard then forwards C^1||S^1 to the middle node which
-   repeats this process and forwards C^2||S^2 to the exit. The exit
-   removes the final encryption layer and processes the cell as in the
-   old protocol.
-
-   Let us now consider what happens when the crypto tagging attack is
-   applied to this protocol. Without loss of generality, after inverting
-   Step (11) the guard tags either C^1 or S^1 and forwards C'^1||S'^1 to
-   the middle node. The middle node, unaware of the change follows the
-   protocol to decrypt C'^1||S'^1 which results in a random string as
-   per the explanation above. Since both CircID and CMD are not part of
-   the payload, the middle node can still forward the random string
-   (unaware of this fact) to the exit node. Upon receiving the random
-   string, the exit node decrypts it, sees that the 'Rec' field is not
-   all-zero and acts accordingly.
-
-
-3. Design considerations
-
-3.1 Choice of primitives
-
-   We stress that the proposed protocol is primitive agnostic.
-
-   Noting that Tor currently uses AES_CTR we tried to design a solution
-   that requires only minimal changes. Most importantly, the encryption
-   is still performed using CTR-mode, and can be instantiated using
-   AES_CTR (however, the solution works just as well with any other
-   block cipher).
-
-   The hashing of the ciphertext requires a universal hash function. The
-   GCM mode of operation uses CTR+GHash and is available from the
-   OpenSSL crypto library which is already used within Tor. Any
-   available universal hash function can be used instead of GHash if the
-   latter introduces an unacceptable latency.
-
-   The nonce-encryption step uses a tweakable block cipher. In the
-   example above we used the XEX trick to transform a "regular" block
-   cipher into a tweakable block cipher which allows reusing whatever
-   underlying primitive is used in CTR-mode. A tweakable block cipher
-   can be used directly (with X as the tweak) if one is available but
-   this is not required.
-
-3.2 Security requirements
-
-   In Proposal 202, Nick Mathewson outlined the security requirements
-   for any solution. We copy them here verbatim and discuss how each of
-   them is addressed in the proposed solution:
-
-      * " ... we'd like any attacker who controls a node on the circuit
-        not to have a good way to learn any other nodes, even if he/she
-        controls those nodes" - By construction, once processed by an
-        honest node the cell's payload is completely destroyed, thus
-        unlinking any relation between what is seen by nodes further
-        down the circuit and the original message. An adversary
-        controlling the exit node can still see that the circuit turned
-        into junk (borrowing the professional jargon of Proposal 202);
-        this seems unavoidable (if any of the other proposals somehow
-        solved this, we would like to know so we can see if it can
-        somehow be adapted here.
-
-     * "no relay should be able to alter a cell between an honest sender
-       and an honest recipient in a way that they cannot detect" - Any
-       alternation of a cell between a sender and a recipient will be
-       decrypted to junk and never delivered to the recipient. (**)
-
-     * "Relay cells should be secret: nobody but the sender and
-       recipient of a relay cell should be able to learn what it says."
-       - since the protocol is an extension of the existing one,
-       whatever secrecy was present before remains so.
-
-     * "... Circuits should resist transparent, recoverable tagging
-       attacks... " - that's the whole point. Once a change was injected
-       and passed to an adjacent honest node, no node further down the
-       circuit can recover the relay cell.
-
-    * "... The above properties should apply to sequences of cells
-      too... " - this one is more tricky. To the best of my
-      understanding this property is currently ensured through the
-      'Digest' field in the payload. Keeping this field, our solution
-      can provide the same functionality as before. However,
-      re-arranging the 'Rec' and 'Digest' fields in a way similar to
-      Proposal 261 would reduce the overhead but would require
-      developing a different solution. It seems possible though. (*)
-
-   In addition to supporting these security requirements, this proposal
-   improves Tor's E2E authentication by replacing the broken SHA-1 with
-   an ENCODE-then-ENCIPHER authentication. By introducing redundancy to
-   the cell (either through the 'Rec' and 'Digest' fields or otherwise)
-   the exit node can verify that the cell was not altered en route. This
-   is similar to what is done in Proposal 261 but without the trouble of
-   using a tweakable wide-block cipher.
-
-	(*) a possible solution would be to digest X as part of H(C) but
-	this requires further discussion.
-
-	(**) my understanding is that a single circuit can be used for
-	more than one TCP stream. If this is not the case, then the
-	recipient receives a random string and can identify that this is
-	not a valid message.
-
-
-3.3 Feature requirements
-
-
-   In addition to security requirements, Proposal 202 also discusses
-   some feature requirements. We discuss two of them here as the others
-   seems to be trivially supported (although this needs to be verified
-   by someone who understands Tor better than me).
-
-
-    * "Any new approach should be able to coexist on a circuit with the
-      old approach" - following the IRC discussion, we had an internal
-      discussion and we think that the proposed solution works even if
-      only the middle node supports the new protocol. This involves
-      encrypting the nonce only for the middle nonce. We came up with
-      two ways to achieve this, both have their pro's and con's and
-      should be discussed once we agree on the general idea.
-
-      Since the Crypto tagging attack requires a collusion between a
-      corrupted guard and a corrupted exit, it does not make sense to
-      discuss what happens when one of them runs the new protocol.
-
-    * "Cell length needs to be constant as cells move through the
-      network." - The solution was designed to allow for a fixed cell
-      size. this should be discussed though.
-
-4. Specifications
-	TBD
-
-5. Compatibility
-	See Section 3.3
-
-6. Implementation
-	TBD
-
-7. Performance and scalability notes
-	TBD
+   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.