Relay cell size moving backward

Question

I have been studying the papers on Tor and Onion Routing for my thesis and I have been trying to figure out how the whole cell size works.

In the OR paper it is made clear that when a cell moves in the forward direction, every time an encryption layer is removed, the size is kept the same with the use of padding. This is not mentioned clearly in the Tor paper, but I believe that it is the same there as well.

How does it work in the opposite direction (backward)? In the OR paper it says that in every node, an encryption layer is added on the cell and the initiator receives a cell with multiple layers of encryption. But, is there a use of padding here as well, in order to maintain the size? And how do it work for the second and third node? Do they remove padding in order to add a layer of encryption?

Thanks!

Answer 1

The current implementation of Tor does not use any padding in its circuit crypto. Different from the original OR paper, Tor later switched to a "telescoping" circuit building approach, with RELAY cells encrypted with a stream cipher, so no cell size change is involved. (This might change in the future but not very near.)

So when you build a circuit, it basically looks like this at the first hop (talking of TAP, in the case of ntor it will be slightly different):

Client ---(PKEnc(handshake, OnionKey1))--> Relay 1
Client <--(response)--- Relay 1

Client and Relay 1 learns SymKey1 from the handshake. When extending to the second hop, you are sending the handshake over the already-built 1-hop circuit.

Client ---(SymEnc(PKEnc(handshake, OnionKey2), SymKey1))--> Relay 1 ---(PKEnc(handshake, OnionKey2))--> Relay 2
Client <--(SymEnc(response, SymKey1))--- Relay 1 <--(response)--- Relay 2

Relay 1 decrypts the handshake using SymKey1 and forwards it to Relay 2. Upon receiving the response from Relay 2, Relay 1 encrypts it using SymKey1 and sends back to Client. Client decrypts the response, learns a SymKey2 shared with Relay 2 and the 2-hop circuit is built. So is the third hop.

Client ---(SymEnc(SymEnc(PKEnc(handshake, OnionKey3), SymKey2), SymKey1))--> Relay 1 ---(SymEnc(PKEnc(handshake, OnionKey3), SymKey2))--> Relay 2 ---(PKEnc(handshake, OnionKey3))--> Relay 3
Client <--(SymEnc(SymEnc(response, SymKey2), SymKey1))--- Relay 1 <--(SymEnc(response, SymKey2))--- Relay 2 <--(response)--- Relay 3

And for application data routed over the circuit:

Client ---(SymEnc(SymEnc(SymEnc(data, SymKey3), SymKey2), SymKey1))--> Relay 1 ---(SymEnc(SymEnc(data, SymKey3), SymKey2))--> Relay 2 ---(SymEnc(data, SymKey3))--> Relay 3 ---(data)--> destination
Client <--(SymEnc(SymEnc(SymEnc(data, SymKey3), SymKey2), SymKey1))--- Relay 1 <--(SymEnc(SymEnc(data, SymKey3), SymKey2))--- Relay 2 <--(SymEnc(data, SymKey3))--- Relay 3 <--(data)--- destination

All SynEnc functions mentioned above are stream ciphers that produces ciphertexts of the same length as plaintexts. Consequently, cell sizes are kept unchanged between hops.