What prevents CircID collision from happening?

Question

When a Tor OP wants to extend a circuit, it sends a relay extend cell to the last node on it. This node then sends CREATE cell to the desired destination node, choosing a new CircID (used to identify the circuit uniquely) not already used between the node sending the CREATE cell and the destination node.

What will happen in the hypothetic case when, say, 2 different circuits with different middle nodes share the same exit node, and the two middle nodes choose the same, colliding CircID when sending CREATE cell to the common exit node?

Following the spec, this should be a possible scenario, because each of the middle nodes doesn't use the randomly generated CircID already to this exit node. The collision happens only on the exit node and there is no way for the two middle nodes to know about it.

How strong is the entropy behind CircID generation and is it the only defence measure against CircID collision?

Answer 1

There's a misunderstanding here. CREATE cells are sent just from immediate neighbours in a circuit, during circuit construction. So a client will send a CREATE cell to the entry node, where the collision prevention protocol will work. Then the client sends an EXTEND cell, which instructs the entry node to send a (fresh) CREATE cell to the destined middle node. The same happens again when extending the circuit to the exit node. The CircID is not actually the same across the entire circuit, rather it is used to uniquely identify a circuit on a given connection between two tor nodes.

Answer 2

You do not need unique circuit IDs for all neighboring connections for one onion node. You have encrypted TLS sessions between neighboring nodes. Now some circuits get multiplexed into one session and so you need the circuit IDs to differentiate.