Herbivore: A Scalable and Efficient Protocol for Anonymous Communication - PDF

Please download to get full document.

View again

of 17
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report



Views: 14 | Pages: 17

Extension: PDF | Download: 0

Related documents
Herbivore: A Scalable and Efficient Protocol for Anonymous Communication Sharad Goel, Mark Robson, Milo Polte, and Emin Gün Sirer Cornell University, Ithaca NY 14850, USA Abstract. Anonymity is increasingly
Herbivore: A Scalable and Efficient Protocol for Anonymous Communication Sharad Goel, Mark Robson, Milo Polte, and Emin Gün Sirer Cornell University, Ithaca NY 14850, USA Abstract. Anonymity is increasingly important for networked applications amidst concerns over censorship and privacy. In this paper, we describe Herbivore, a peer-to-peer, scalable, tamper-resilient communication system that provides provable anonymity and privacy. Building on dining cryptographer networks, Herbivore scales by partitioning the network into anonymizing cliques. Adversaries able to monitor all network traffic cannot deduce the identity of a sender or receiver beyond an anonymizing clique. In addition to strong anonymity, Herbivore simultaneously provides high efficiency and scalability, distinguishing it from other anonymous communication protocols. Performance measurements from a prototype implementation show that the system can achieve high bandwidths and low latencies when deployed over the Internet. 1 Introduction Even though strong anonymity and privacy guarantees are critical for many applications, current Internet networking protocols provide no support for masking the identity of communication endpoints. An adversary that monitors Internet routers can determine which IP addresses have contacted which services. Tracking software installed at the ISPs can map IP addresses back to individuals. While encryption protocols, such as SSL, make it computationally difficult for attackers to decipher what was sent, they cannot hide who sent it. The situation is particularly problematic when governments and large corporations monitor online activity, track user behavior or censor communications. In this paper, we describe a peer-to-peer, tamper-resistant, scalable anonymous communication protocol, called Herbivore. Herbivore has three critical properties: (1) it hides the identity of communication endpoints, even from attackers with unrestricted wiretapping capabilities, (2) it scales well with large numbers of users, and (3) it is efficient in terms of bandwidth and latency. Herbivore is structured as an overlay network on top of an untrusted substrate, like the Internet. It provides strong anonymity by building on the information theoretic guarantees of dining cryptographer networks (DC-nets) [2]. Specifically, Herbivore guarantees sender and receiver anonymity; that is, it is computationally intractable for observers that monitor all network traffic, as well as participate in the protocol, to deduce the origin or destination of a message beyond an anonymizing clique. Herbivore s scalability stems from a divide-and-conquer approach that partitions the network into anonymizing cliques. Herbivore uses a decentralized, peer-to-peer approach to organize the global network securely into smaller cliques in which anonymous communication can occur efficiently. Actual measurements from a prototype deployed over the Internet demonstrate that the system can achieve high bandwidths and low latencies in practice. Overall, the Herbivore system provides a provably anonymous communication channel that can scale to large numbers of participants and run efficiently over existing networks. Herbivore enables participants to contact legacy services on the Internet through proxy nodes, though in this mode of usage, it guarantees only the anonymity of the endpoint that is part of the Herbivore network. The rest of this paper describes the design of Herbivore, examines its behavior analytically and presents measurements from a prototype implementation. Section 2 describes previous work on anonymous communication protocols. Section 3 provides the necessary background on DC-nets. Section 4 describes the 2 operation of Herbivore, including the local and global network topology algorithms. Section 5 addresses potential attacks on the network. In Section 6 we describe the structure of representative applications built on top of Herbivore. Section 7 presents results from our prototype implementation. Finally, Section 8 summarizes our contributions. 2 Related Work Three critical properties for anonymous communication protocols are strong anonymity, scalability, and efficiency. By strong anonymity, we mean a system s ability to protect the participants identities from an adversary that is both capable of unlimited wiretapping (unlimited passive attacks), and compromising a significant fraction of participating nodes (active attacks). By scalability, we mean the ability of the system to accommodate large numbers of participants and to decouple its performance from the number of total nodes. By efficiency, we are referring to the effective anonymous bandwidth of the system, that is, the number of bits sent per anonymous bit transferred, as well as its latency. Previous work on anonymous communication protocols can achieve any two, but not all three of these critical properties. Past work can be grouped into three categories: source-rewriting systems, broadcast protocols, and DC-nets. Source-rewriting systems Source-rewriting systems provide anonymity via packet reshuffling. Mixes [1] work by removing the timing correlation between arriving packets and outgoing packets. A mix is a forwarder node that queues incoming packets for a period of time 0 t T such that, when finally sent, the packets appear as if they may have originated from any one of the nodes that contacted that mix in the last T seconds. Mixes work best when arranged in series, and need a constant amount of traffic to retain anonymity while avoiding long packet delays. Tarzan [7] uses a decentralized, peer-to-peer approach to construct such a series of mixes, called tunnels. Neither system is immune to statistical analysis, and their latency is proportional to the degree of anonymity they provide. In other source-rewriting protocols, including Onion Routing [19], Crowds [14], and Hordes [17], messages are sent through the network via random paths that deter packet traces. Each node that forwards the message rewrites the source field of the packet with its own id. Consequently, attackers with limited wiretapping abilities cannot easily track packets back to their originators. In order to make it difficult to track a packet s propagation through the network, the packets are encrypted and potentially reordered at each node, though the systems differ on how these operations are performed. In Onion Routing, the sender picks a full path through the network and encrypts the packets in layers. Each node along the path reorders the packets, strips off a layer of encryption and forwards them. In Crowds, the paths are determined locally and on-the-fly by the forwarders instead of a priori by the senders, and encryption is done via pair-wise key exchange and symmetric encryption between forwarders. In both of these systems, returned packets follow the reverse route from the sender. Hordes improves upon these two source-rewriting systems by replacing the return path with a low latency multicast operation. Source rewriting is also used in peer-to-peer content distribution networks such as Freenet [3] and the Freedom Network [8] to obfuscate the identity of request originators. While these systems are efficient and scale well, they do not provide strong anonymity guarantees. A passive adversary can perform traffic analysis to trace the packet through the intermediary nodes to a sender and receiver. Further, source-rewriting incurs high latencies, as the round-trip times grow linearly with the number of anonymizing forwarders traversed. Broadcast protocols Broadcast protocols, such as P 5 [16], provide sender and receiver anonymity by transmitting encrypted packets at a constant rate to all participants. When a node has no data packets to send, it sends noise, which is then propagated throughout the network in the same manner as data packets. This approach provides strong anonymity, as a passive eavesdropper cannot tell which packets contain data and which packets are noise. Alone, a constant bit rate broadcast protocol would scale poorly with increasing network sizes. P 5 scales by partitioning the network into anonymizing broadcast groups. 3 With this protocol, a node can send messages at a rate of 1/S with low packet loss and log S/S with high packet loss, where S is the number of nodes in its anonymizing broadcast group. P 5 achieves anonymity and scalability, but at a cost of efficiency. It can waste bandwidth and place large loads on the underlying network, since accommodating high peak data bandwidths with this approach requires that the network constantly run at the highest possible load. Overall, the constant bit rate limitation is not well-suited for bursty data traffic, and efficiency is elusive under a scheme whose anonymity depends on propagating noise. DC-Nets Introduced in 1988 [2], DC-nets are an elegant mechanism for strongly anonymous communication. Since they provide the basis of Herbivore, we describe their operation in detail in the next section. 3 DC-nets Background In this section, we informally describe the operation of DC-nets, and highlight the areas where Herbivore makes contributions related to their basic operation. A formal specification of DC-nets can be found in Appendix A. DC-nets propagate a bit of information in the following way: Suppose there are two participants, Alice and Bob, one of whom (Bob) wants to communicate a one-bit message to Charlie. Alice and Bob first toss a coin in secret. Alice reports the truthful result of the coin toss to Charlie. Bob, on the other hand, reports the true result of the coin toss only if he wants to transmit a 0. If he wants to transmit a 1, Bob lies about the coin toss. Charlie deciphers the message by taking the XOR of the values sent by Alice and Bob. If they both report 0 or 1, they are both telling the truth and the one-bit message is a zero; otherwise, one of them is lying, and the one-bit message is a one. Since Charlie does not know if it was Alice or Bob who lied about the coin toss, he can never determine who sent the message. This security guarantee is strong and information-theoretic: No amount of computational power can help Charlie determine that it was Bob who sent the message. Turning this basic idea for one bit transmission into a general scheme for communication between arbitrary numbers of hosts requires some modifications, originally outlined in [2]. First, for all participants to be able to send and receive messages, the nodes have to be arranged in a connected key graph; that is, Charlie needs to have shared secret keys with Alice and Bob. In addition to this key graph, the nodes need to communicate with each other through a physical transmission network. Previous work considered deploying DC-nets in a variety of topologies [11, 5]. Here, we prove that a star topology is optimal for the communication requirements of DC-nets, and use it as part of the Herbivore intra-clique topology. Second, a protocol is necessary to ensure that only one node sends a message at a time. If multiple nodes try to simultaneously transmit in a DC-net, the network will in effect transmit the XOR of the messages, leading to collisions and corrupted messages. Previous work on DC-nets devoted additional bandwidth to reservations, thereby reducing the likelihood of such collisions. These reservation schemes targeted a low packet collision rate, and derived the amount of bandwidth to devote to reservations from this rate and the birthday paradox. Depending on the essentially arbitrary choices of packet size and collision rate, this reservation scheme can be quite inefficient and entail large space overheads. Here, we relate the bandwidth to be used for the reservation phase to the choice of the packet size and network load, and systematically derive an equation for the size of the reservation block. Third, self-organization typically requires some signaling among the participants, and in an anonymous network, this signaling may have to be done anonymously. This can be inefficient if nodes simply reserve a slot and then transmit their message, as transmissions in traditional DC-nets require bandwidth proportional to the number of participants. Here, we present a scheme for probabilistic, anonymous and unanimous agreement in a DC-net that requires each node send a constant, and in practice modest, number of bits independent of clique size. Herbivore uses this signaling mechanism to control the local topology of each anonymizing clique. 4 The preceding modifications turn the core idea for one-bit transmission from two hosts into a general idea for sending anonymous packets between N participants. While this approach provides anonymity, it is vulnerable to a range of denial-of-service attacks and does not scale well with increasing numbers of participants. A malicious node can trivially disrupt the network by sending messages without a reservation. Worse, the anonymity guarantees provided by DC-nets make it difficult to locate such disruptive participants. Past work [20] has developed techniques for identifying and cleaving such malicious nodes out of a DC-net. It relies on setting up traps, that is, random data sent for the express purpose of catching a malicious disrupter, and can not only detect disruption but also identify the disrupters. In a model where there is a single, global DC-net, the ability to specifically identify such malicious nodes and drop them from the network is critical, as they can render the entire network unusable. However, the ability to cleave out disrupters comes at a price: The network protocol is considerably more complex as it needs to make sure that the trap mechanism itself is not abused by malicious nodes to cleave out legitimate participants, and a substantial (O(N)) amount of the anonymous bandwidth is dedicated to traps. Further, the anonymous bandwidth of a DC-net is limited by the slowest participant. Overall, DC-nets elegantly provide strong anonymity, but suffer from efficiency and scalability problems. 4 Protocol Herbivore simultaneously provides scalability, efficiency and strong anonymity. There are two components to the Herbivore system. At the lowest level, a round protocol governs how bits are sent among the participating nodes. This protocol achieves strong anonymity by building on DC-nets at the wire level. It extends the basic DC-net scheme in several ways to utilize the network efficiently, detect tampering and facilitate long-lived transactions. The round protocol provides efficient and anonymous communication; however, its performance is inversely proportional to the number of simultaneously active sessions, and malicious nodes can affect all participants. To scale well in the face of planetary scale networks and malicious participants, Herbivore employs a global topology control algorithm to divide the network into smaller anonymizing cliques. Herbivore guarantees that each clique will have at least k nodes, where k is a predetermined constant that describes the degree of anonymity offered by the system. New cliques are created automatically when existing cliques grow too large to communicate efficiently. When the number of nodes in a clique falls below k, the nodes in that clique are redistributed throughout the network. A secure entry control protocol deters attempts by malicious nodes to subvert the global topology control algorithm. In the next two sections, we describe the operation of the system from the top down. We first treat the round protocol as a black box, and describe how Herbivore s global topology control algorithm organizes a large network into a collection of small cliques. These cliques enable the algorithm to scale and to contain malicious nodes. We then describe the round protocol used within a clique for anonymous data transmission in detail, and describe how the system achieves efficiency. 4.1 Global Topology Control The global topology of the Herbivore network is determined by an entry control protocol, which assigns newly arriving nodes into cliques, and by a clique maintenance protocol, which rearranges existing nodes when the number of participants within a clique is too many or too few. Entry Control Protocol A node joins the Herbivore network by contacting any one of the participants and following the entry control protocol. This protocol serves three purposes. First, it deters attacks targeted at compromising the anonymity of specific nodes. If nodes could select which clique to join, conspiring attackers could take over all but one member of a selected clique, and consequently trace all 5 transactions emanating from that clique to the remaining node. Second, it ensures that cliques are of approximately equal size by randomizing the point of entry for newly arriving nodes. Finally, through a challenge-based protocol, it limits the rate at which nodes can join the network, curbing the impact of malicious nodes who attempt to launch denial of service attacks by rapidly joining the network in several locations. The entry control protocol operates by assigning physical nodes uniformly distributed identifiers in a virtual space, and subsequently grouping them into cliques of size k or more. A simple and intuitively appealing scheme for entry control Fig. 1. The global topology of Herbivore is structured as a ring, with each clique assigned a unique key. While communication in Herbivore is primarily done at the clique level, nodes can leverage this global backbone to communicate with other cliques would be to group nodes together by the hash of their IP addresses. Indeed, many peer-to-peer systems use the hash of an IP address and a small salt (between zero and eight bits) to map the physical participants onto a virtual ring [15, 18, 21, 10, 9]. Some others allow the nodes to directly pick their location [13]. All such systems are vulnerable to attack by an adversary which owns a large number of IP addresses, and can thus pick a particular IP address whose hash happens to map to a point of interest in the overlay network. The salt makes these systems even less secure, as it enables malicious nodes to pick their salt value to match the desired location, in addition to their IP address. For instance, attackers with a class-a IP address and an 8-bit salt have bits at their disposal to pick their point of entry into the network. These schemes are unsuitable for use in Herbivore, as the freedom to judiciously select the point of entry would enable an attacker to crowd out all but one legitimate node in a targeted clique, exposing the transmissions of the remaining node. We call such an attack a topology attack. Herbivore s secure random entry protocol is designed to prohibit topology attacks. The entry protocol takes the decision on which clique to join out of the hands of the joining node. Each node and each clique in Herbivore have a unique node key and clique key, respectively. Let f and g be one-way functions. To enter the network, a node first generates a public/private key pair K public /K private. It then randomly generates vectors until it finds a y K public such that the lower m k bits of f(k public ) equal those of f(y). The value g(k public, y) forms the node key for the entering node, which then joins the clique whose key is closest numerically to its node key. Any available method can be used for locating this clique; however, distributed hash tables are a natural choice as they provide a decentralized, peer-to-peer way of locating close objects given a key. In Herbivore, we use the off-the-shelf Chord protocol [18, 9]. Having located the closest clique, the node first presents the pair (K public, y). Each node computes f(k public ) and f(y), confirms that that the lower m k bits match, and checks that the key g(k public, y) corresponds to its clique. If (K public, y) has been previously presented by another member of the clique, then the node is denied admission this preve
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks