With widespread acceptance of the Internet as a public medium for communication and information retrieval, there has been rising concern that the personal privacy of users can be eroded by malicious persons monitoring the network. A technical solution to maintaining privacy is to provide anonymity. There have been a number of protocols proposed for anonymous network communication. We show there exist attacks based on passive traffic monitoring that degrade the anonymity of all existing protocols. We use this result to place an upper bound on how long existing protocols, including Crowds, Onion Routing, Mix-nets, and DC-Net, can maintain anonymity in the face of the attacks described. This provides an analytical measure by we can compare the efficacy of all protocols. Our analytical bounds are supported by tighter results from simulations, and we made empirical measurements of our assumptions. We found that mix-based protocols offer the best tradeoff of performance and security, and we provide a deeper evaluation of the success of timing attacks on mix-based protocols. In our most recent work, we have found that attackers can passively monitor network traffic to detect signatures of users and webservers that persist over days or weeks. VPNs created by ssh tunnels or secure wireless connections (e.g., WEP) as implemented are not sufficient to block these signatures. We designed an attack and evaluated it with real Internet measurements: allowed a training period, we found an attacker could guess which exact web site (in the training set) was visited by a user through an encrypted link almost 40% of the time; 70% of the time the correct answer was in the attackerâ€™s top five guesses. (A random guess had less than 1% chance of success.) Our early evidence indicates the attack has a very low false positive rate for sites that are not in the training set. We show how this attack can be thwarted by network and system defenses.