Signal messenger is a popular server-mediated end-to-end encrypted messaging application, and its underlying encryption protocol provides many attractive properties such as authentication, post-compromise security and deniability. Signal additionally provides two extensions, Sealed Sender and Private Groups, to conceal metadata about who communicates with whom, and which parties communicate in groups, from potentially compromised Signal servers. We describe a novel attack for group conversations in Signal and show through theoretical analysis and simulation that groups of communicating entities may be linked through recipient metadata alone, defeating the Sealed Sender and Private Groups mechanisms. We show that an earlier defense proposed for a similar attack on Sealed Sender pairs is not effective against our attack. We then discuss a “server-agnostic” mitigation that can be implemented by users alone, illustrating a tradeoff between communication overhead and defense efficacy.

Website Fingerprinting (WF) attacks on the Tor anonymity network identify websites accessed via Tor by recognizing the traffic patterns -- sequences of packet directions and timing -- associated with accessing a particular site. Previous work has shown that modern WF attacks can function when trained and tested against consistent high or low settings of the Tor "security slider,'' which impacts the traffic pattern produced by a download. In this work we show that training and testing against traces with a mixture of settings can improve the performance of WF attacks in some cases. Thus research seeking to evaluate WF defenses should consider both scenarios to ensure the most consistent evaluations.

While anonymity networks like Tor aim to protect the privacy of their users, they are vulnerable to traffic analysis attacks such as Website Fingerprinting (WF) and Flow Correlation (FC). Recent implementations of WF and FC attacks, such as Tik-Tok and DeepCoFFEA, have shown that the attacks can be effectively carried out, threatening user privacy. Consequently, there is a need for effective traffic analysis defense. There are a variety of existing defenses, but most are either ineffective, incur high latency and bandwidth overhead, or require additional infrastructure. As a result, we aim to design a traffic analysis defense that is efficient and highly resistant to both WF and FC attacks. We propose DeTorrent, which uses competing neural networks to generate and evaluate traffic analysis defenses that insert 'dummy' traffic into real traffic flows. DeTorrent operates with moderate overhead and without delaying traffic. In a closed-world WF setting, it reduces an attacker's accuracy by 61.5%, a reduction 10.5% better than the next-best padding-only defense. Against the state-of-the-art FC attacker, DeTorrent reduces the true positive rate for a .00001 false positive rate to about .12, which is less than half that of the next-best defense. We also demonstrate DeTorrent's practicality by deploying it alongside the Tor network and find that it maintains its performance when applied to live traffic.

In this paper, we present Laserbeak, a new state-of-the-art website fingerprinting attack for Tor that achieves nearly 96% accuracy against FRONT-defended traffic by combining two innovations: 1) multi-channel traffic representations and 2) advanced techniques adapted from state-of-the-art computer vision models. Our work is the first to explore a range of different ways to represent traffic data for a classifier. We find a multi-channel input format that provides richer contextual information, enabling the model to learn robust representations even in the presence of heavy traffic obfuscation. We are also the first to examine how recent advances in transformer models can take advantage of these representations. Our novel model architecture utilizing multi-headed attention layers enhances the capture of both local and global patterns. By combining these innovations, Laserbeak demonstrates absolute performance improvements of up to 36.2% (e.g., from 27.6% to 63.8%) compared with prior attacks against defended traffic. Experiments highlight Laserbeak’s capabilities in multiple scenarios, including a large open-world dataset where it achieves over 80% recall at 99% precision on traffic obfuscated with padding defenses. These advances reduce the remaining anonymity in Tor against fingerprinting threats, underscoring the need for stronger defenses.

Recent website fingerprinting attacks have been shown to achieve very high performance against traffic through Tor. These attacks allow an adversary to deduce the website a Tor user has visited by simply eavesdropping on the encrypted communication. This has consequently motivated the development of many defense strategies that obfuscate traffic through the addition of dummy packets and/or delays. The efficacy and practicality of many of these recent proposals have yet to be scrutinized in detail. In this study, we re-evaluate nine recent defense proposals that claim to provide adequate security with low-overheads using the latest Deep Learning-based attacks. Furthermore, we assess the feasibility of implementing these defenses within the current confines of Tor. To this end, we additionally provide the first on-network implementation of the DynaFlow defense to better assess its real-world utility.

End-to-end flow correlation attacks are among the oldest known attacks on low-latency anonymity networks, and are treated as a core primitive for traffic analysis of Tor. However, despite recent work showing that individual flows can be correlated with high accuracy, the impact of even these state-of-the-art attacks is questionable due to a central drawback: their pairwise nature, requiring comparison between N2pairs of flows to deanonymize N users. This results in a combinatorial explosion in computational requirements and an asymptotically declining base rate, leading to either high numbers of false positives or vanishingly small rates of successful correlation. In this paper, we introduce a novel flow correlation attack, DeepCoFFEA, that combines two ideas to overcome these drawbacks. First, DeepCoFFEA uses deep learning to train a pair of feature embedding networks that respectively map Tor and exit flows into a single low-dimensional space where correlated flows are similar; pairs of embedded flows can be compared at lower cost than pairs of full traces. Second, DeepCoFFEA uses amplification, dividing flows into short windows and using voting across these windows to significantly reduce false positives; the same embedding networks can be used with an increasing number of windows to independently lower the false positive rate. We conduct a comprehensive experimental analysis showing that DeepCoFFEA significantly outperforms state-of-the-art flow correlation attacks on Tor, e.g. 93% true positive rate versus at most 13% when tuned for high precision, with two orders of magnitude speedup over prior work. We also consider the effects of several potential countermeasures on DeepCoFFEA, finding that existing lightweight defenses are not sufficient to secure anonymity networks from this threat.

Abstract Website Fingerprinting (WF) attacks are used by local passive attackers to determine the destination of encrypted internet traffic by comparing the sequences of packets sent to and received by the user to a previously recorded data set. As a result, WF attacks are of particular concern to privacy-enhancing technologies such as Tor. In response, a variety of WF defenses have been developed, though they tend to incur high bandwidth and latency overhead or require additional infrastructure, thus making them difficult to implement in practice. Some lighter-weight defenses have been presented as well; still, they attain only moderate effectiveness against recently published WF attacks. In this paper, we aim to present a realistic and novel defense, RegulaTor, which takes advantage of common patterns in web browsing traffic to reduce both defense overhead and the accuracy of current WF attacks. In the closed-world setting, RegulaTor reduces the accuracy of the state-of-the-art attack, Tik-Tok, against comparable defenses from 66% to 25.4%. To achieve this performance, it requires 6.6% latency overhead and a bandwidth overhead 39.3% less than the leading moderate-overhead defense. In the open-world setting, RegulaTor limits a precision-tuned Tik-Tok attack to an F 1-score of. 135, compared to .625 for the best comparable defense.

Abstract We introduce Generative Adversarial Networks for Data-Limited Fingerprinting (GANDaLF), a new deep-learning-based technique to perform Website Fingerprinting (WF) on Tor traffic. In contrast to most earlier work on deep-learning for WF, GANDaLF is intended to work with few training samples, and achieves this goal through the use of a Generative Adversarial Network to generate a large set of “fake” data that helps to train a deep neural network in distinguishing between classes of actual training data. We evaluate GANDaLF in low-data scenarios including as few as 10 training instances per site, and in multiple settings, including fingerprinting of website index pages and fingerprinting of non-index pages within a site. GANDaLF achieves closed-world accuracy of 87% with just 20 instances per site (and 100 sites) in standard WF settings. In particular, GANDaLF can outperform Var-CNN and Triplet Fingerprinting (TF) across all settings in subpage fingerprinting. For example, GANDaLF outperforms TF by a 29% margin and Var-CNN by 38% for training sets using 20 instances per site.

Abstract Recent advances in Deep Neural Network (DNN) architectures have received a great deal of attention due to their ability to outperform state-of-the-art machine learning techniques across a wide range of application, as well as automating the feature engineering process. In this paper, we broadly study the applicability of deep learning to website fingerprinting. First, we show that unsupervised DNNs can generate lowdimensional informative features that improve the performance of state-of-the-art website fingerprinting attacks. Second, when used as classifiers, we show that they can exceed performance of existing attacks across a range of application scenarios, including fingerprinting Tor website traces, fingerprinting search engine queries over Tor, defeating fingerprinting defenses, and fingerprinting TLS-encrypted websites. Finally, we investigate which site-level features of a website influence its fingerprintability by DNNs.

Experimentation tools facilitate exploration of Tor performance and security research problems and allow researchers to safely and privately conduct Tor experiments without risking harm to real Tor users. However, researchers using these tools configure them to generate network traffic based on simplifying assumptions and outdated measurements and without understanding the efficacy of their configuration choices. In this work, we design a novel technique for dynamically learning Tor network traffic models using hidden Markov modeling and privacy-preserving measurement techniques. We conduct a safe but detailed measurement study of Tor using 17 relays (~2% of Tor bandwidth) over the course of 6 months, measuring general statistics and models that can be used to generate a sequence of streams and packets. We show how our measurement results and traffic models can be used to generate traffic flows in private Tor networks and how our models are more realistic than standard and alternative network traffic generation~methods.

Tor provides low-latency anonymous and uncensored network access against a local or network adversary. Due to the design choice to minimize traffic overhead (and increase the pool of potential users) Tor allows some information about the client's connections to leak. Attacks using (features extracted from) this information to infer the website a user visits are called Website Fingerprinting (WF) attacks. We develop a methodology and tools to measure the amount of leaked information about a website. We apply this tool to a comprehensive set of features extracted from a large set of websites and WF defense mechanisms, allowing us to make more fine-grained observations about WF attacks and defenses.

Existing End-to-End secure messaging applications trust a single service provider to deliver messages in a consistent order to a consistent group of conversation members. We propose a protocol that removes this single point of failure by using multiple service providers, enforcing conversation integrity as long as one service provider out of N behave honestly. However, this approach could potentially increase the number of entities that learn the metadata for a conversation. In this work we discuss the challenges and provide a protocol that limits the metadata leakage to that of existing messaging applications while still providing strong conversation integrity.

Abstract We describe SYM-GOTR, a protocol for secure Group Off-The-Record (GOTR) messaging. In contrast to previous work, SYM-GOTR is the first protocol to offer confidential, authenticated, and repudiable conversations among a dynamic group with the additional properties of message unlinkability and the guarantee that all users see the same conversation, while providing efficient use of network and CPU resources. SYM-GOTR achieves these properties through the use of a novel optimistic consistency check protocol that either determines that all users agree on a transcript with constant-size messages or identifies at least one user that has not followed the protocol. We provide an implementation of SYM-GOTR as a Java library along with a plugin for the Jitsi instant messaging client. We analyze the performance of SYM-GOTR in a real world deployment scenario and discuss the challenges of providing a usable implementation without compromising the security of the conversation.

Abstract We present PeerFlow, a system to securely load balance client traffic in Tor. Security in Tor requires that no adversary handle too much traffic. However, Tor relays are run by volunteers who cannot be trusted to report the relay bandwidths, which Tor clients use for load balancing. We show that existing methods to determine the bandwidths of Tor relays allow an adversary with little bandwidth to attack large amounts of client traffic. These methods include Tor’s current bandwidth-scanning system, TorFlow, and the peer-measurement system EigenSpeed. We present an improved design called PeerFlow that uses a peer-measurement process both to limit an adversary’s ability to increase his measured bandwidth and to improve accuracy. We show our system to be secure, fast, and efficient. We implement PeerFlow in Tor and demonstrate its speed and accuracy in large-scale network simulations.

Abstract Search engine queries contain a great deal of private and potentially compromising information about users. One technique to prevent search engines from identifying the source of a query, and Internet service providers (ISPs) from identifying the contents of queries is to query the search engine over an anonymous network such as Tor. In this paper, we study the extent to which Website Fingerprinting can be extended to fingerprint individual queries or keywords to web applications, a task we call Keyword Fingerprinting (KF). We show that by augmenting traffic analysis using a two-stage approach with new task-specific feature sets, a passive network adversary can in many cases defeat the use of Tor to protect search engine queries. We explore three popular search engines, Google, Bing, and Duckduckgo, and several machine learning techniques with various experimental scenarios. Our experimental results show that KF can identify Google queries containing one of 300 targeted keywords with recall of 80% and precision of 91%, while identifying the specific monitored keyword among 300 search keywords with accuracy 48%. We also further investigate the factors that contribute to keyword fingerprintability to understand how search engines and users might protect against KF.

We consider the problem of estimating the latency of a feasible but unused Autonomous System-level path on the Internet. This problem arises in evaluating the overhead incurred by censorship and surveillance circumvention schemes that alter the Internet routing infrastructure, and the cost of attacks against such schemes. Since these paths are not advertised by the current routing infrastructure, they cannot be directly measured by end hosts, leading researchers to estimate the costs indirectly. Using traceroute measurements of observed Internet paths, we measure the accuracy of the two methods used in the literature to date, finding that these methods have poor accuracy and correlation, explaining as low as 3% of the variation in observed AS path latencies, and at most 42%. We also describe an improved method that can balance accuracy and path coverage. At the high end our estimator can explain up to 83% of variation in observed AS path latencies, while still being able to achieve 56% when maximizing the number of paths able to be estimated.

Abstract Social media websites are blocked in many regimes where Internet censorship is applied. In this paper, we introduce Mailet, an unobservable transport proxy which enables the users to access social websites by email applications. Without assuming the Mailet servers are trustworthy, Mailet can support the services requiring privileges without having the complete credential. Particularly, the credential is split and distributed in two Mailet servers, and neither of them can recover the credential alone. To recover the credential in a TLS record message, we propose a highly efficient Galois/ Counter Mode(GCM) based secure computation, which can enable the two servers to conceal their separate credential copies in the computation. We implemented a prototype for Twitter.com to demonstrate the usability and security of Mailet.

We present a brief summary of The 14th Workshop on Privacy in the Electronic Society, held on October 12th, 2015, in conjunction with the 22nd ACM Conference on Computer and Communications Security in Denver, Colorado, USA. The goal of this workshop is to discuss the problems of privacy in the global interconnected societies and possible solutions to them. The workshop program includes 11 full papers and 3 short papers out of 32 total submissions. Specific areas that are covered in the program include, but are not limited to: web and social network privacy, mobile and location privacy, communications privacy, and privacy-preserving data analysis.

Vuze is a popular file‐sharing client. When looking for content, Vuze selects from its list of neighbours, a set of 20 nodes to be contacted; the selection is performed such that the neighbours closest to the content in terms of Vuze ID are contacted first. To improve efficiency of its searches, Vuze implements a network coordinate system: from the set of 20 to‐be‐contacted nodes, queries are sent to the closest nodes in terms of network distance, which is calculated by the difference in network coordinates. However, network coordinate systems are inherently insecure and a malicious peer can lie about its coordinate to appear closest to every peer in the network. This allows the malicious peer to bias next‐hop choices for victim peers such that queries will be sent to the attacker, thus hijacking every search query. In our experiments, almost 20% of the search queries are hijacked; the cost of performing this attack is minimal – less than $112/month.

In response to increasingly sophisticated methods of blocking access to censorship circumvention schemes such as Tor, recently proposed systems such as Skypemorph, FreeWave, and CensorSpoofer have used voice and video conferencing protocols as "cover channels" to hide proxy connections. We demonstrate that even with perfect emulation of the cover channel, these systems can be vulnerable to attacks that detect or disrupt the covert communications while having no effect on legitimate cover traffic. Our attacks stem from differences in the channel requirements for the cover protocols, which are peer-to-peer and loss tolerant, and the covert traffic, which is client-proxy and loss intolerant. These differences represent significant limitations and suggest that such protocols are a poor choice of cover channel for general censorship circumvention schemes.

Both academic research and historical incidents have shown that unstable BGP speakers can have extreme, undesirable impacts on network performance and reliability. Large amounts of time and energy have been invested in improving router stability. In this paper, we show how an adversary in control of a BGP speaker in a transit AS can cause a victim router in an arbitrary location on the Internet to become unstable. Through experimentation with both hardware and software routers, we examine the behavior of routers under abnormal conditions and come to three conclusions. First, that unexpected but perfectly legal BGP messages can place routers into those states with troubling ease. Second, that an adversary can implement attacks using these messages to disrupt the function of victim routers in arbitrary locations in the network. And third, modern best practices do not blunt the force of these attacks sufficiently. These conclusions lead us to recommend more rigorous testing of BGP implementations, focusing as much on protocol correctness as on software correctness.

Abstract The Kad network, an implementation of the Kademlia DHT protocol, supports the popular eDonkey peer‐to‐peer file sharing network and has over 1 million concurrent nodes. We describe several attacks that exploit critical design weaknesses in Kad to allow an attacker with modest resources to cause a significant fraction of all searches to fail. We measure the cost and effectiveness of these attacks against a set of 16 000 nodes connected to the operational Kad network. Using our large‐scale simulator, DVN, we successfully scaled up to a 200 000 node experiment. We also measure the cost of previously proposed, generic DHT attacks against the Kad network and find that our attacks are much more cost effective. Finally, we introduce and evaluate simple mechanisms to significantly increase the cost of these attacks. Copyright © 2010 John Wiley & Sons, Ltd.

Ad hoc low-power wireless networks are an exciting research direction in sensing and pervasive computing. Prior security work in this area has focused primarily on denial of communication at the routing or medium access control levels. This paper explores resource depletion attacks at the routing protocol layer, which permanently disable networks by quickly draining nodes' battery power. These "Vampire” attacks are not specific to any specific protocol, but rather rely on the properties of many popular classes of routing protocols. We find that all examined protocols are susceptible to Vampire attacks, which are devastating, difficult to detect, and are easy to carry out using as few as one malicious insider sending only protocol-compliant messages. In the worst case, a single Vampire can increase network-wide energy usage by a factor of O(N), where N in the number of network nodes. We discuss methods to mitigate these types of attacks, including a new proof-of-concept protocol that provably bounds the damage caused by Vampires during the packet forwarding phase.

A network coordinate system [7, 14, 15] assigns virtual coordinates (network positions) to every node in the network. These coordinates are assigned so that the coordinate distance between two nodes reflects the real network distance between those two nodes. This allows any peer in the sytem to accurately estimate the network distance between any pair of nodes, without having the pair of nodes contact each other. Network coordinate systems' ability to predict the network latency between arbitrary pairs of nodes can be used in many applications: finding the closest node to download content from in a content distribution network or route to in a peer-to-peer system [18], reducing inter-ISP communication [5, 13], reducing the amount of state stored in routers [1], performing byzantine leader elections [6], and detecting Sybil attackers [3, 8].

Many graphs in general, and social graphs in particular, are directed by nature. However, applications built on top of social networks, including Sybil defenses, information routing and dissemination, and anonymous communication require mutual relationships which produce undirected graphs. When undirected graphs are used as testing tools for these applications to bring insight on their usability and potential deployment, directed graphs are converted into undirected graphs by omitting edge directions or by augmenting graphs. Unfortunately, it is unclear how altering these graphs affects the quality of their mixing time. Motivated by the lack of prior work on this problem, we investigate mathematical tools for measuring the mixing time of directed social graphs and its associated error bounds. We use these tools to measure the mixing time of several benchmarking directed graphs and their undirected counterparts. We then measure how this difference impacts two applications built on top of social networks: a Sybil defense mechanism and an anonymous communication system.

Decoy Routing is a new approach to Internet censorship circumvention that was recently and independently proposed at FOCI'11, USENIX Security'11 and CCS'11. Decoy routing aims to hamper nation-state level Internet censorship by having routers, rather than end hosts, relay traffic to blocked destinations. We analyze the security of these schemes against a routing capable adversary, a censoring authority that is willing to make routing decisions in response to decoy routing systems.

Social network-based Sybil defenses exploit the algorithmic properties of social graphs to infer the extent to which an arbitrary node in such a graph should be trusted. However, these systems do not consider the different amounts of trust represented by different graphs, and different levels of trust between nodes, though trust is being a crucial requirement in these systems. For instance, co-authors in an academic collaboration graph are trusted in a different manner than social friends. Furthermore, some social friends are more trusted than others. However, previous designs for social network-based Sybil defenses have not considered the inherent trust properties of the graphs they use. In this paper we introduce several designs to tune the performance of Sybil defenses by accounting for differential trust in social graphs and modeling these trust values by biasing random walks performed on these graphs. Surprisingly, we find that the cost function, the required length of random walks to accept all honest nodes with overwhelming probability, is much greater in graphs with high trust values, such as co-author graphs, than in graphs with low trust values such as online social networks. We show that this behavior is due to the community structure in high-trust graphs, requiring longer walk to traverse multiple communities. Furthermore, we show that our proposed designs to account for trust, while increase the cost function of graphs with low trust value, decrease the advantage of attacker.

A network coordinate system assigns Euclidean “virtual” coordinates to every node in a network to allow easy estimation of network latency between pairs of nodes that have never contacted each other. These systems have been implemented in a variety of applications, most notably the popular Vuze BitTorrent client. Zage and Nita-Rotaru (at CCS 2007) and independently, Kaafar et al. (at SIGCOMM 2007), demonstrated that several widely-cited network coordinate systems are prone to simple attacks, and proposed mechanisms to defeat these attacks using outlier detection to filter out adversarial inputs. Kaafar et al. goes a step further and requires that a fraction of the network is trusted. More recently, Sherr et al. (at USENIX ATC 2009) proposed Veracity, a distributed reputation system to secure network coordinate systems. We describe a new attack on network coordinate systems, Frog-Boiling, that defeats all of these defenses. Thus, even a system with trusted entities is still vulnerable to attacks. Moreover, having witnesses vouch for your coordinates as in Veracity does not prevent our attack. Finally, we demonstrate empirically that the Frog-Boiling attack is more disruptive than the previously known attacks: systems that attempt to reject “bad” inputs by statistical means or reputation cannot be used to secure a network coordinate system.

A network latency estimation scheme associates a "position" to every peer in a distributed network such that the latency between any two nodes can be accurately estimated from their positions. Applications for these schemes include efficient overlay construction, compact routing, anonymous route selection, and efficient byzantine agreement. We present a new latency estimation scheme, Treeple. Our scheme is different from existing ones in several aspects: Treeple is provably secure, rather than being able to resist known attacks; positions in Treeple are not Euclidean coordinates and reflect the underlying network topology; finally, positions in Treeple are accurate, stable, and can be assigned to peers not participating in the system.

Tor, a distributed Internet anonymizing system, relies on volunteers who run dedicated relays. Other than altruism, these volunteers have no incentive to run relays, causing a large disparity between the number of users and available relays. We introduce BRAIDS, a set of practical mechanisms that encourages users to run Tor relays, allowing them to earn credits redeemable for improved performance of both interactive and non-interactive Tor traffic. These performance incentives will allow Tor to support increasing resource demands with almost no loss in anonymity: BRAIDS is robust to well-known attacks. Using a simulation of 20,300 Tor nodes, we show that BRAIDS allows relays to achieve 75% lower latency than non-relays for interactive traffic, and 90% higher bandwidth utilization for non-interactive traffic.

Social network-based Sybil defenses exploit the trust exhibited in social graphs to detect Sybil nodes that disrupt an algorithmic property (i.e., the fast mixing) in these graphs. The performance of these defenses depends on the quality of the algorithmic property and assuming a strong trust model in the underlying graph. While it is natural to think of trust value associated with the social graphs, Sybil defenses have used the social graphs without this consideration. In this paper we study paramagnetic designs to tune the performance of Sybil defenses by accounting for trust in social graphs and modeling the trust as modified random walks. Our designs are motivated by the observed relationship between the algorithmic property required for the defenses to perform well and a hypothesized trust value in the underlying graphs.

In this work, we introduce the Coordinated Cross Plane Session Termination, or CXPST, attack, a distributed denial of service attack that attacks the control plane of the Internet. CXPST extends previous work that demonstrates a vulnerability in routers that allows an adversary to disconnect a pair of routers using only data plane traffic. By carefully choosing BGP sessions to terminate, CXPST generates a surge of BGP updates that are seen by nearly all core routers on the Internet. This surge of updates surpasses the computational capacity of affected routers, crippling their ability to make routing decisions

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 protocols—the Tor network and the MultiProxy proxy aggregator service—and conclude that both are highly vulnerable to these attacks.

Modern advanced botnets may employ a decentralized peer-to-peer overlay network to bootstrap and maintain their command and control channels, making them more resilient to traditional mitigation efforts such as server incapacitation. As an alternative strategy, the malware defense community has been trying to identify the bot-infected hosts and enumerate the IP addresses of the participating nodes so that the list can be used by system administrators to identify local infections, block spam emails sent from bots, and configure firewalls to protect local users. Enumerating the infected hosts, however, has presented challenges. One cannot identify infected hosts behind firewalls or NAT devices by employing crawlers, a commonly used enumeration technique where recursive get-peerlist lookup requests are sent newly discovered IP addresses of infected hosts. As many bot-infected machines in homes or offices are behind firewall or NAT devices, these crawler-based enumeration methods would miss a large portions of botnet infections. In this paper, we present the Passive P2P Monitor (PPM), which can enumerate the infected hosts regardless whether or not they are behind a firewall or NAT. As an empirical study, we examined the Storm botnet and enumerated its infected hosts using the PPM. We also improve our PPM design by incorporating a FireWall Checker (FWC) to identify nodes behind a firewall. Our experiment with the peer-to-peer Storm botnet shows that more than 40% of bots that contact the PPM are behind firewall or NAT devices, implying that crawler-based enumeration techniques would miss out a significant portion of the botnet population. Finally, we show that the PPM's coverage is based on a probability-based coverage model that we derived from the empirical observation of the Storm botnet.

We introduce Torsk, a structured peer-to-peer low-latency anonymity protocol. Torsk is designed as an interoperable replacement for the relay selection and directory service of the popular Tor anonymity network, that decreases the bandwidth cost of relay selection and maintenance from quadratic to quasilinear while introducing no new attacks on the anonymity provided by Tor, and no additional delay to connections made via Tor. The resulting bandwidth savings make a modest-sized Torsk network significantly cheaper to operate, and allows low-bandwidth clients to join the network. Unlike previous proposals for P2P anonymity schemes, Torsk does not require all users to relay traffic for others. Torsk utilizes a combination of two P2P lookup mechanisms with complementary strengths in order to avoid attacks on the confidentiality and integrity of lookups. We show by analysis that previously known attacks on P2P anonymity schemes do not apply to Torsk, and report on experiments conducted with a 336-node wide-area deployment of Torsk, demonstrating its efficiency and feasibility. Categories and Subject Descriptors

We introduce the concept of membership-concealing overlay networks (MCONs), which hide the real-world identities of participants. We argue that while membership concealment is orthogonal to anonymity and censorship resistance, pseudonymous communication and censorship resistance become much easier if done over a membership-concealing network. We formalize the concept of membership concealment, discuss a number of attacks against existing systems and present real-world attack results. We then propose three proof-of-concept MCON designs that resist those attacks: one that is more efficient, another that is more robust to membership churn, and a third that balances efficiency and robustness. We show theoretical and simulation results demonstrating the feasibility and performance of our schemes.

A Distributed Hash Table (DHT) is a structured overlay network service that provides a decentralized lookup for mapping objects to locations. In this paper, we study the lookup performance of locating nodes responsible for replicated information in Kad - one of the largest DHT networks existing currently. Throughout the measurement study, we found that Kad lookups locate only 18% of nodes storing replicated data. This failure leads to limited reliability and an inefficient use of resources during lookups. Ironically, we found that this poor performance is due to the high level of routing table similarity, despite the relatively high churn rate in the network. We propose solutions which either exploit the high routing table similarity or avoid the duplicate returns using multiple target keys.

Steganography is the problem of hiding secret messages in "innocent-lookingrdquo public communication so that the presence of the secret messages cannot be detected. This paper introduces a cryptographic formalization of steganographic security in terms of computational indistinguishability from a channel, an indexed family of probability distributions on cover messages. We use cryptographic and complexity-theoretic proof techniques to show that the existence of one-way functions and the ability to sample from the channel are necessary conditions for secure steganography. We then construct a steganographic protocol, based on rejection sampling from the channel, that is provably secure and has nearly optimal bandwidth under these conditions. This is the first known example of a general provably secure steganographic protocol. We also give the first formalization of "robustrdquo steganography, where an adversary attempts to remove any hidden messages without unduly disrupting the cover channel. We give a necessary condition on the amount of disruption the adversary is allowed in terms of a worst case measure of mutual information. We give a construction that is provably secure and computationally efficient and has nearly optimal bandwidth, assuming repeatable access to the channel distribution.

The Kad network, an implementation of the Kademlia DHT protocol, supports the popular eDonkey peer-to-peer file sharing network and has over 1 million concurrent nodes. We describe several attacks that exploit critical design weaknesses in Kad to allow an attacker with modest resources to cause a significant fraction of all searches to fail. We measure the cost and effectiveness of these attacks against a set of 16,000 nodes connected to the operational Kad network. We also measure the cost of previously proposed, generic DHT attacks against the Kad network and find that our attacks are much more cost effective. Finally, we introduce and evaluate simple mechanisms to significantly increase the cost of these attacks.

A timed-release cryptosystem allows a sender to encrypt a message so that only the intended recipient can read it only after a specified time. We formalize the concept of a secure timed-release public-key cryptosystem and show that, if a third party is relied upon to guarantee decryption after the specified date, this concept is equivalent to identity-based encryption; this explains the observation that all known constructions use identity-based encryption to achieve timed-release security. We then give several provably-secure constructions of timed-release encryption: a generic scheme based on any identity-based encryption scheme, and two more efficient schemes based on the existence of cryptographically admissible bilinear mappings. The first of these is essentially as efficient as the Boneh-Franklin Identity-Based encryption scheme, and is provably secure and authenticated in the random oracle model; the final scheme is not authenticated but is provably secure in the standard model (i.e., without random oracles).

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. This paper reports on three experiments that partially measure the extent to which such leakage can compromise anonymity. First, using a public dataset of pairwise round-trip times (RTTs) between 2000 Internet hosts, we estimate that on average, knowing the network location of host A and the RTT to host B leaks 3.64 bits of information about the network location of B. Second, we describe an attack that 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 17% equal error rate. Finally, we describe an attack that allows a malicious website, with access to a network coordinate system and one corrupted Tor router, to recover roughly 6.8 bits of network location per hour.

An electronic cash system allows users to withdraw coins, represented as bit strings, from a bank or broker, and spend those coins anonymously at participating merchants, so that the broker cannot link spent coins to the user who withdraws them. A variety of schemes with various security properties have been proposed for this purpose, but because strings of bits are inherently copyable, they must all deal with the problem of double-spending. In this paper, we present an electronic cash scheme that introduces a new peer-to-peer system architecture to prevent double-spending without requiring an on-line trusted party or tamper-resistant software or hardware. The scheme is easy to implement, computationally efficient, and provably secure. To demonstrate this, we report on a proof-of-concept implementation for Internet vendors along with a detailed complexity analysis and selected security proofs.

A peer-to-peer (P2P) storage system allows a network of peer computers to increase the availability of their data by replicating it on other peers in the network. In such networks, a central challenge is preventing "freeloaders", or nodes that use disproportionately more storage on other peers than they contribute to the network. While several existing systems claim to solve this problem, we show that all known approaches are vulnerable to various attacks by either a single greedy peer or a small group of peers. To address this problem, we describe a robust distributed system to account for the storage activities of each peer. We analyze the security of this system, prove that it is secure under a much stronger attack model than previous work, and evaluate the efficiency of a prototype implementation.

We introduce covert two-party computation, a stronger notion of security than standard secure two-party computation. Like standard secure two-party computation, covert two-party computation allows Alice and Bob, with secret inputs xA and xB respectively, to compute a function f(xA,xB) without leaking any additional information about their inputs. In addition, covert two-party computation guarantees that even the existence of a computation is hidden from all protocol participants unless the value of the function mandates otherwise. This allows the construction of protocols that return f(xA,xB) only when it equals a certain value of interest (such as "Yes, we are romantically interested in each other") but for which neither party can determine whether the other even ran the protocol whenever f(xA,xB) is not a value of interest. Since existing techniques for secure function evaluation always reveal that both parties participate in the computation, covert computation requires the introduction of new techniques based on provably secure steganography. We introduce security definitions for covert two-party computation and show that this surprising notion can be achieved by a protocol given the Decisional Diffie-Hellman assumption in the "honest but curious" model. Using this protocol as a subroutine, we present another protocol which is fair and secure against malicious adversaries in the Random Oracle Model --- unlike most other protocols against malicious adversaries, this protocol does not rely on zero-knowledge proofs (or similar cut-and-choose techniques), because they inherently reveal that a computation took place. We remark that all our protocols are of comparable efficiency to protocols for standard secure two-party computation.

Informally, a communication protocol is sender k - anonymous if it can guarantee that an adversary, trying to determine the sender of a particular message, can only narrow down its search to a set of k suspects. Receiver k-anonymity places a similar guarantee on the receiver: an adversary, at best, can only narrow down the possible receivers to a set of size k. In this paper we introduce the notions of sender and receiver k-anonymity and consider their applications. We show that there exist simple and efficient protocols which are k-anonymous for both the sender and the receiver in a model where a polynomial time adversary can see all traffic in the network and can control up to a constant fraction of the participants. Our protocol is provably secure, practical, and does not require the existence of trusted third parties. This paper also provides a conceptually simple augmentation to Chaum's DC-Nets that adds robustness against adversaries who attempt to disrupt the protocol through perpetual transmission or selective non-participation.

It has been shown that standard genetic programming using standard subtree crossover is prone to a form of structural convergence which makes it extremely difficult to make changes near the root, occasionally causing runs to become trapped in local maxima. Based on these structural limitations we propose a different tree representation, AppGP, which we hope will avoid this problem in some cases. In this paper, we describe this representation, and compare its performance to the performance of standard GP on a suite of test problems. We find that on all of the test problems, AppGP does no worse than standard GP, and in several it does considerably better, suggesting that the representation warrants further study.