Onion Routing Encryption

Question

I'm curious how, in onion routing, the relay nodes identify which node to forward the message to? From my understanding the message must travel a specific path based on the keys the user has. I don't understand how the nodes understand how to relay the message both in the request path and in the response path. Explanations I've seen at my level seem to abstract this part away.

My guess is that information pertaining to the nodes adjacent to a relay node is understandable despite the encryption? For example, assuming 3 relay nodes, in the request relay node 2 receives M' = E2(E3(M)), can find M'' = E3(M), and there is some information readable to the node in M'' to tell it that it must go to node 3?

In other words, the initial encryption when the message is sent off looks more like H1||E1(H2||E2(H3||E3(M))), where each H_N is readable by node N and contains information about the next node.

But I assume this isn't correct because it only makes sense when the sender (client) can add all the headers, I don't know how it would work in the response.

Answer 1

Your assumption is correct. When a client sends a request to an onion service, it first makes a connection to the first relay in the circuit, then sends a payload to this first relay. The first relay uses its key to decrypt the payload, then this reveals the next 'layer' of the onion, which includes a header, and a payload to be sent to the second relay, whereby included in the header is the IP address of the second relay. The first relay then opens a connection to the second relay, and sends this payload to the second relay. This process continues (typically through three relays), with each relay stripping off another layer of the onion, and forwarding the payload to the next relay, until the payload containing the request reaches the onion service.

Your question pertains to how the process works in reverse, when the response is sent back from the onion service to the client. This is possible due to the fact that all of the connections that were opened in the process above (when the request is sent from the client to the onion service) remain open, so that the response can be sent back from the onion service to the client. This is explained briefly at https://en.wikipedia.org/wiki/Onion_routing#Onion_creation_and_transmission (see where it reads 'When the final recipient of the data sends data back, the intermediary nodes maintain the same link back to the originator, with data again layered, but in reverse such that the final node this time adds the first layer of encryption...'), and in more detail in the landmark paper, Tor: The Second-Generation Onion Router (see section 4.2).