Something I have been meaning to write up for a long time but never got around to:
I assume the reader knows the basics of asymmetric cryptography, for sake of brevity and simplicity lets us consider RSA, even though thats not the onion encryption in Tor uses. I assume the reader is familiar with the mathematics behind RSA, and the basic proofs that decrypting the encrypted number results in the original number, so familiarity with modular arithmetic, modular exponentiation etc is assumed...
I assume the reader knows the basic concept of onion routing: the sender of a packet chooses an arbitrary path through routing nodes, whose public keys are known, and first encrypts the packet for the exit node's public key, then encrypts that for the next-to-last nodes public key, and so on in a backwards fashion to finally encrypt the onion packet for the first routing node's public key. At each layer a bit of metadata is encrypted along so the routing nodes know only the next node to send their decryption to. So the N-layer encrypted packet is sent to the first routing node, which decrypts the first layer, splits the metadata from the N-1-times encrypted packet, and sends the latter to the next node mentioned in the metadata.
From the perspective of an ISP or 3 letter agency monitoring the traffic of a specific intermediate routing node, they see encrypted packets arrive, and encrypted packets leaving.
Let me first state the obvious, but which I will NOT rely on:
If the eavesdropper were to possess the capability to break RSA, they could trivially decrypt the packet and associate the incoming packets to the outgoing packets. (let us ignore that if they could break RSA, they could just decrypt the whole layered onion of the packet at once...).
To transliterate to math:
EavesDropperAbleToBreakRSA => EavesDropperAbleToTrackPackets
given "A => B" and "not A" one is unable to prove "not B", although it is tempting to jump to that conclusion. B can be true while A is false, it would just mean that the eavesdropper could track packets in an alternative manner, but how?
Lets go back to our hypothetical naive RSA implementation of Tor:
Is it really necessary to break RSA to match incoming and outgoing packets of an intermediate node?
Of course not: imagine first for simplicity that the node only received 2 incoming packets, and 2 outgoing packets.
This means the eavesdropper sees 2 incoming k+1 times encrypted packets, and 2 k-times encrypted packets, which happen to be the decryption of the incomming packets. Why break RSA if the outgoing packets ARE the decryptions? One merely needs to re-encrypt the outgoing packets with the proper metadata, given the routing node's public key, and one should end up with identically one of the 2 incoming packets, so consolidating ISP powers, or other attackers able to monitor network traffic on a sufficient number of nodes can simply track packets in the onion network. Effectively the k+1-times encrypted packet is an RSA signature of the k-times encrypted packet!!!
Suppose a random route is 5 hops long and that there are 30 routing nodes (not realistic but insightful as we will see).
Suppose only the entry node packet and the exit node packet are logged, but not the intermediate traffic. How computationally expensive would it be to guess and verify the route?
that would be 30 times 29 times 28 times 27 times 26 combinations. Each combination would consist of 5 encryptions/signature checks. Very feasible to brute force.
The reason this is insightful is that a dominant eavesdropped missing observability on a small number of links can brute force these without having to break RSA, and still verifiably confirm the actual route. It would only need to consider public keys of nodes on which observability it lacks. So this becomes expensive much quicker for entities that have less eavesdropping infrastructure, than for dominant eavesdroppers.
A security researcher who understands this potential ploy in onion routing networks will have a hard time proving the exploit in practice, because the researcher lacks the eavesdropping powers that ISP's and 3 letter agencies possess.