[tor-dev] Proposal 295: Using the ATL construction for relay cryptography (solving the crypto-tagging attack)
Nick Mathewson
nickm at torproject.org
Tue Jul 3 21:41:25 UTC 2018
Hi, all!
I've got the privilege to relay the following proposal from Tomer
Ashur: it reflects a whole lot of work. I didn't make any changes,
other than wrapping the lines: please let me know if corrupted
anything.
Filename: 295-relay-crypto-with-atl.txt
Title: Using the ATL construction 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) Nick put 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. 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!).
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 An instructive 1-node circuit
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
More information about the tor-dev
mailing list