Hi,
A few of us discussed this proposal in the #tor-dev IRC earlier this week.
There are still a few things in the proposal that we found confusing.
(Some of these things are our mistakes in tor-spec, which were copied
to the proposal. We’re working on fixing them in tor-spec.)
Once the proposal has been revised, we would like to:
* try condensing the proposal into an algorithm in pseudocode
* estimate how it will perform compared to Tor’s current relay crypto
* write a tor-spec patch based on the proposal
Here’s a summary of our feedback:
Changing the Proposal Structure
We’re confused by 3.1 and 3.2, which seem to be duplicate sections using
different notation.
We think the following structure would help us understand the proposal
better:
* 3.1. Describe key derivation for a single hop circuit, like tor-spec
section 5.2.2 at:
https://github.com/torproject/torspec/blob/master/tor-spec.txt#L1210
* 3.2. Describe encryption and decryption for a single-hop circuit, like
tor-spec sections 0.3 and 0.4 at:
https://github.com/torproject/torspec/blob/master/tor-spec.txt#L77
https://github.com/torproject/torspec/blob/master/tor-spec.txt#L124
* 3.3. Describe encryption and decryption for multi-hop circuits, based on
the latest tor-spec section 5.5 at:
https://github.com/torproject/torspec/pull/27/files#diff-390fa89f5c74e769e6e5bef55fc1918bR1366
Making Re-Keying and Tweaking more Explicit
Tor’s current cell crypto keeps the AES-CTR counters synchronized and
incrementing, while this proposal sems to derive them from the cell
contents.
In this proposal, we had trouble working out:
* when the AES is re-keyed vs tweaked
* when the GHASH is re-keyed vs updated
So we wondered if the proposed scheme is not IND-CPA. i.e., if the client
repeats a plaintext cell, it will produce identical ciphertext cells,
because the AES-CTR nonce is based solely on the message and keys.
We think the new structure will be clearer, because the re-keying should
all be in section 3.1, and the tweaks/updates should be in section 3.2.
Generalising to Different Numbers of Hops
The proposal assumes that all circuits are 3-hop circuits, but Tor typically
builds 1, 3, 4, and 5-hop circuits. Also, Tor currently generates the same
number of keys for each hop. There’s no way it can just generate kf_M, kf_E,
kb_M, and kb_E for the final hop, because sometimes the final hop changes.
(Due to circuit cannibalisation, or failed intro extension.)
Please generalise the proposal so that:
* all references to “3-hop circuit” are changed to "N-hop circuit".
* all references to kf_1,2,3, kb_1,2,3, k_fM, k_fE, k_bM and k_bE;
are changed to kf_N, kb_N, kfM_N, kfE_N, kbM_N and kbE_N.
Do we really need 6 keys per hop?
It’s ok if we do, let’s make sure there are no redundant keys.
Explaining which Hops do Integrity Checks
Are kfM_N, kfE_N, kbM_N and kbE_N only used for the innermost encryption and
decryption? (That is, when N is the client’s target hop, or the cell is sent
from hop N to the client.)
If so, please explain that the integrity checks only apply to the lowest
layer, and how this is secure.
If we can do the integrity checks for each layer, perhaps we should, because
then we are protecting against tagging attacks on some nodes, even when the
exit doesn’t support the protocol.
For example, in a standard 3-hop circuit:
C = G = M - E
Where:
= means end-to-end integrity checks
- means no integrity checks
If C and M support the proposed protocol, can they protect against tagging
between G and E, even if G and E don’t support the proposed protocol?
(Perhaps this could be a good example for the proposal?)
Protecting Onion Services
When onion services communicate with clients, we want to make sure that
they aren’t vulnerable to tagging attacks.
For example, in a standard onion service rendezvous, two circuits are
spliced at the rendezvous point R:
C = G = M1 = R ~ M2 ~ M3 ~ G ~ S
Where:
= means end-to-end integrity checks between C and R
~ means end-to-end integrity checks between S and R
- means no integrity checks
We think that the cells from C to S are protected from tagging, if the
C to R and S to R circuits are protected from tagging, because tagging
requires two unprotected nodes, one to add the tag, and one to remove it.
(Also, like the scenario above with the exit circuit, if some of the hops
support the protocol, then any hops closer to the client or service can’t
add or remove tags.)
If onion services are protected, let’s explain that in the proposal.
Minor Stylistic Comments
We’re not used to the notation that you’re using, so it’s hard for us
to follow some sections.
In particular:
* Using the notation X||Y to represent a tuple of arguments to an
operation is confusing, because || usually means concatenation.
(e.g., H(K||X) should probably be H(K, X) because GHASH doesn't do a
simple concatentation of K and X)
* The capitalization of "K" vs “k” is inconsistent, so it’s hard to
tell if keys are the same or different.
Here are some of our notes for our future reference:
Impact on Relay Performance
We would like to estimate how the proposed encryption will perform,
compared to Tor’s current relay crypto.
We think the proposed scheme could be faster, because:
* If we can throw out SHA1, we're saving a lot in practice: SHA1 is
expensive compared to AES_CTR on current cpus
* We should figure this out with the assumption that we do/don't have
aesni and/or carryless-multiply
* If we have a no-carry multiply (*CLMUL*), fast ghash is easy
* If not, it's a bit of a dark art to get it without timing sidechannels
It looks like we trade 1 SHA1 for N+1 GHASHes, where N is the number of
hops. (GHASH is much faster than SHA1, we think more than 3x.)
Here are some other minor corrections or questions, inline on the proposal:
> On 5 Jul 2018, at 06:42, Nick Mathewson <nickm@xxxxxxxxxxxxxx> wrote:
>
> 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
Duplicate word "the the”.
Also the N should probably be S_0.
> 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
Some circuits are not 3 hops, see above.
Entry nodes can be bridges or guards or a random node (when UseEntryGuards
is 0). So let’s say “entry”, not “guard".
> 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)
should be S_0 = D_k3(S ^ T) ^ T and CTR_k1(S_0)?
> 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
End nodes can be exits or directories or intro or rend nodes.
This is an existing problem in tor-spec, see:
https://trac.torproject.org/projects/tor/ticket/26885
> 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.
Some circuits are not 3 hops, see above.
> 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.
During our review, we noticed that the decryption order in tor-spec is
wrong, so we fixed it:
https://trac.torproject.org/projects/tor/ticket/26860
It looks like this proposal has the correct order, but we think it will be
clearer if it is re-structured. (See above.)
> 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.
Some circuits are not 3 hops, see above.
> 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,
We think we might need these keys for each node, not just the exit.
(See above.)
> 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
Let’s use the same construction as tor-spec to derive the keys, but
generate more data when we need more keys.
> 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.
This paragraph is copied from tor-spec.txt.
I think we can drop it from the proposal, and reference tor-spec instead.
> 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,
This sentence is copied from tor-spec.txt.
It’s confusing by itself.
The corresponding section in tor-spec.txt contains some errors.
And it’s also hard to read.
We opened a ticket for this issue:
https://trac.torproject.org/projects/tor/ticket/26859
And then we fixed it in this ticket, because the modified the same sections:
https://trac.torproject.org/projects/tor/ticket/26860
We’d like to see the proposal revised so it matches the new tor-spec structure:
* forward encryption at the client
* forward decryption at ORs
* backward encryption at the end (exit)
* backward decryption at the client
> 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)
Is T’ the previous T (tweak) held over as a piece of state?
Because the "running digest” doesn’t seem to be the internal state of
a digest algorithm.
> Note that in counter mode, decrypt (D) and encrypt (E) are the same
> operation.
This paragraph is copied from tor-spec.txt.
In this context, it’s incorrect.
> 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.
This paragraph is copied from tor-spec.txt.
I think we can drop it from the proposal, and reference tor-spec instead.
> 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.
We revised this paragraph in tor-spec, see below.
Maybe the proposal can just reference tor-spec, rather than copying
this text?
> 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.
2 bytes, P=2^-16
This error seems to be copied from tor-spec.txt section 6.1.
For a fix, see:
https://trac.torproject.org/projects/tor/ticket/26860
> 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.
We have open proposals and tickets on padding, so I suggest that we use
this wording:
"The remainder of the payload is padded with padding bytes.
See tor-spec Section 3 for details."
For those who are interested, here's the list of upcoming changes:
Clarify/determine specification for padding
https://trac.torproject.org/projects/tor/ticket/26228
prop289: Implement authenticated SENDME
https://trac.torproject.org/projects/tor/ticket/26288
In particular:
prop289: Leave unused random bytes in relay cell payload
https://trac.torproject.org/projects/tor/ticket/26846
prop289: randomize the unused part of relay payloads
https://trac.torproject.org/projects/tor/ticket/26871
> 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).
Tor’s current digest is in the cell header. But this proposal moves
the integrity check from the header to end of the cell.
Is there any reason why we can’t put S in the cell header?
If we did, we’d need a specification like the existing tor-spec
digest:
“The nonce S is generated based on the content of the entire cell,
with the nonce field filled with NUL bytes.”
We should decide if it’s better to:
* have non-data fields at the start and end of the cell, or
* fill a field with NUL bytes, calculate the nonce, then replace
the NUL bytes with the nonce.
> 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.
Mixed version networks will be easier to implement if we derive keys
pairwise with each node based on the handshake.
(See above.)
We should probably say something like:
"Both the client and the node need to support the new protocol in this
proposal, otherwise we fall back to the old one."
> 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.
“encrypted padding bytes", see above.
> 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.
We think every hop should authenticate, at least in the transition
period. (See above.)
T
--
teor
Please reply @torproject.org
New subkeys 1 July 2018
PGP C855 6CED 5D90 A0C5 29F6 4D43 450C BA7F 968F 094B
Attachment:
signature.asc
Description: Message signed with OpenPGP
_______________________________________________ tor-dev mailing list tor-dev@xxxxxxxxxxxxxxxxxxxx https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev