Relay Routing
Overview
Relay routing is the process by which the INCOG Browser constructs and maintains encrypted multi-hop circuits through the relay network. This document specifies the routing protocol in detail, including circuit construction, key exchange, traffic forwarding, circuit teardown, and failure recovery.
Circuit Construction
Terminology
- Circuit: A complete relay path from the client to an exit node, traversing one or more intermediate relay hops
- Cell: The fundamental unit of relay protocol communication — a fixed-size encrypted packet transmitted between adjacent hops
- Stream: A logical connection multiplexed over a circuit, corresponding to a single user-initiated network request
- Relay node: Any participant in the relay network forwarding circuit traffic
Construction Sequence
Client selects entry node E, middle node M, exit node X from relay directory
Client initiates TLS connection to E
Client ←→ E: TLS handshake (authenticates E's identity key)
Client ←→ E: ECDH key exchange → establishes session key K_E
All subsequent communication with E is encrypted with K_E
Client sends EXTEND cell to E (encrypted with K_E)
EXTEND cell contains: M's address + client's ECDH public key for M
E relays EXTEND cell to M
M sends EXTENDED response to E
EXTENDED response contains: M's ECDH public key
E relays EXTENDED response to client
Client derives K_M from ECDH with M's public key
Circuit now has two hops: Client ←→ E ←→ M
Client sends EXTEND2 cell to E (encrypted with K_E)
Inside: EXTEND2 to M (encrypted with K_M)
Inside: X's address + client's ECDH public key for X
M relays EXTEND to X
X sends EXTENDED response to M
Client derives K_X from ECDH with X's public key
Circuit complete: Client ←→ E ←→ M ←→ X
Client opens stream on circuit to target destination
Client sends BEGIN cell (encrypted K_E → K_M → K_X) specifying destination
X decrypts inner layer, opens TCP connection to destination
This construction sequence ensures:
- E knows the client's real IP and M's address (not X's or the destination)
- M knows E and X (neither client nor destination)
- X knows M and the destination (not the client or E)
Key Derivation
Session keys are derived from the ECDH exchange using HKDF with domain separation labels per hop. The key derivation produces:
- A forward encryption key (client → hop direction)
- A backward encryption key (hop → client direction)
- An authentication key for cell integrity verification
Keys are session-scoped and rotated at circuit teardown. Long-term identity keys (used only for directory authentication) are never used directly for traffic encryption.
Traffic Forwarding
Cell Format
All relay protocol traffic is transmitted in fixed-size cells of 514 bytes. Fixed cell sizes prevent packet-size-based traffic analysis by ensuring that all relay cells are indistinguishable in size regardless of payload content.
Cell structure:
[ CircuitID: 4 bytes ]
[ Cell type: 1 byte ]
[ Payload: 509 bytes ]
The CircuitID identifies which circuit a cell belongs to at each hop. CircuitIDs are local to each link — the same circuit has different CircuitIDs on each link, preventing circuit correlation by observers monitoring multiple network links.
Layered Decryption
Traffic forwarded through the circuit has encryption layers removed at each hop:
Client sends to E:
Encrypt(K_E,
Encrypt(K_M,
Encrypt(K_X, payload)))
E decrypts outer layer, sees inner ciphertext, forwards to M
M decrypts middle layer, sees inner ciphertext, forwards to X
X decrypts final layer, sees plaintext payload, sends to destination
Each cell carries an authentication tag under the hop's authentication key. Hops verify the authentication tag for the layer they decrypt, detecting tampering with probability 1 - 2^-128 per cell. Authentication verification failure results in immediate circuit teardown.
Stream Multiplexing
Multiple logical streams (individual network requests) are multiplexed over a single circuit. Stream multiplexing serves two purposes:
- Efficiency: Avoids the overhead of circuit construction for each individual request
- Traffic correlation resistance: Multiple simultaneous streams through a single circuit make per-stream traffic analysis more difficult
Streams are identified by StreamIDs local to each circuit. The circuit layer handles demultiplexing of cells to the appropriate stream at the exit node.
However, stream multiplexing introduces a potential correlation risk: if a single circuit carries streams to multiple destinations, an observer at the exit node can link those streams to a common circuit and thus to a common user. The protocol mitigates this by using separate circuits for sensitive browsing contexts and recommending single-purpose circuit usage for high-privacy scenarios.
Padding and Traffic Analysis Resistance
Cell Padding
All cells are padded to exactly 514 bytes regardless of payload size. Cells carrying less than 509 bytes of payload are padded with random bytes before transmission and the padding is stripped at the recipient.
This uniform cell size prevents traffic analysis based on packet sizes — a powerful attack that can identify specific websites or content types from their characteristic packet size distributions even when content is encrypted.
Inter-Packet Timing
The relay protocol introduces controlled timing jitter between cell transmissions. The jitter is parameterized by the user's sensitivity configuration:
- Low privacy mode: No artificial jitter; minimal latency overhead
- Standard mode: Up to 20ms random jitter per cell
- High privacy mode: Up to 100ms random jitter per cell
- Maximum privacy mode: Exponential-distribution jitter with mean 200ms
Higher jitter budgets more effectively resist timing correlation attacks (where an adversary monitors both network links near the entry and exit nodes and correlates traffic patterns) at the cost of increased latency.
Cover Traffic
At network scale, the relay protocol supports cover traffic: dummy cells injected into the circuit at random intervals to maintain a constant traffic rate regardless of actual user activity. Cover traffic makes it impossible for a traffic observer to infer when a user is actively browsing versus idle based on traffic volume patterns.
Cover traffic is a network-scale privacy property: it is most effective when many users simultaneously generate cover traffic, as this creates a large pool of indistinguishable traffic that any individual user's real traffic is hidden within.
Circuit Lifecycle Management
Circuit Rotation
Circuits are not intended for indefinite reuse. Long-lived circuits accumulate traffic analysis data that could assist correlation attacks. The protocol enforces circuit rotation:
- Circuits are rotated after a configurable maximum duration (default: 10 minutes)
- Circuits are rotated after a configurable maximum traffic volume
- Circuits are always rotated at session boundaries
Circuit rotation involves constructing a new circuit through a different relay path before tearing down the old circuit, ensuring continuity of active streams during the transition.
Stream-to-Circuit Assignment
The client-side circuit management layer maintains a pool of pre-built circuits to avoid the latency of on-demand circuit construction. When a new stream is initiated, it is assigned to an appropriate circuit from the pool based on:
- Circuit freshness (age and traffic volume)
- Destination compatibility (circuits may be specialized by destination type)
- Isolation requirements (certain browsing contexts require dedicated circuits)
Teardown Sequence
Client sends DESTROY cell to entry node
Entry node propagates DESTROY to middle node
Middle node propagates DESTROY to exit node
All nodes close their local circuit state
All open streams on the circuit receive RST
On teardown, all session key material is securely erased. There is no persistent record of the circuit's routing path or traffic content.
Failure Recovery
Relay circuits can fail for several reasons:
- Relay node failure or network outage during circuit lifetime
- Network congestion causing circuit timeout
- Protocol errors detected by authentication verification
Failed circuit is detected (timeout or explicit failure notification)
Open streams are marked for reconnection
New circuit is constructed through alternative relay path
Streams are re-established on new circuit
The reconnection is transparent to the application layer. HTTP/S connections that survive circuit failure are reconnected without disruption to the user's browsing experience.
Exit Policies
Exit Node Policies
Exit nodes declare which traffic they are willing to forward through an exit policy. Exit policies allow node operators to limit the traffic types their nodes process based on operational and legal considerations.
A typical exit policy might specify:
- Permitted destination ports (e.g., 80, 443 for HTTP/S only)
- Denied destination ports (e.g., deny port 25 to prevent email spam routing)
- Denied destination IP ranges (e.g., deny routing to private address ranges)
Exit policies are declared in the relay directory capability announcement and are enforced by the exit node software. The client-side path construction algorithm considers exit policies when selecting exit nodes, ensuring that the selected exit node can handle the intended traffic type.
DNS at the Exit
Exit nodes handle DNS resolution for the destinations they connect to. This is a deliberate design choice: DNS resolution at the exit node prevents the client from making DNS queries that could be correlated with relay traffic timing to identify destinations despite routing obfuscation.
Exit node DNS resolution uses encrypted DNS resolvers to prevent the exit node's upstream DNS queries from exposing destination information to ISP-level observers.