How much anonymity does network latency leak?

Low-latency anonymity systems such as Tor, AN.ON, Crowds, and Anonymizer.com aim to provide anonymous connections that are both untraceable by local adversaries who control only a few machines and have low enough delay to support anonymous use of network services like Web browsing and remote login. One consequence of these goals is that these services leak some information about the network latency between the sender and one or more nodes in the system. We present two attacks on low-latency anonymity schemes using this information. The first attack allows a pair of colluding Web sites to predict, based on local timing information and with no additional resources, whether two connections from the same Tor exit node are using the same circuit with high confidence. The second attack requires more resources but allows a malicious Web site to gain several bits of information about a client each time he visits the site. We evaluate both attacks against two low-latency anonymity protocolsthe Tor network and the MultiProxy proxy aggregator serviceand conclude that both are highly vulnerable to these attacks.