We present SlicedPIR, a distributed Private Information Retrieval (PIR) protocol. SlicedPIR efficiently alleviates the server's compute bottleneck by offloading its load across multiple untrusted client machines. In contrast to prior work, SlicedPIR induces only a modest network overhead when the server offloads its work. It achieves those communication savings by exploiting the polynomial encoding of homomorphic encryption schemes typically used in PIR protocols. This encoding lets the server make novel use of the Number Theoretic Transform (NTT) to distribute points on the polynomials as ''slices'' of its data rather than the polynomials themselves. Using NTT allows the clients to process recursive PIR queries on their slices and return a succinct result to the server. The server efficiently verifies the clients' results by leveraging the Schwartz-Zippel lemma, which we adapt to the PIR use case. We show how to integrate SlicedPIR into a private messaging system, where clients write messages to the server's database and then use PIR to secretly query for messages from their friends. We implement a prototype of SlicedPIR and run experiments to show that it scales well with the number of clients and database size. Concretely, SlicedPIR achieves better performance and cuts network usage by over 95% compared to the state-of-the-art.

The celebrated Algorand protocol solves validated byzantine agreement in a scalable manner in the synchronous setting. In this paper, we study the feasibility of similar solutions in the asynchronous setting. Our main result is an asynchronous validated byzantine agreement protocol that we call Asynchronous Algorand. As with Algorand, it terminates in an expected constant number of rounds, and honest parties send an expected O(n polylog n) bits, where n is the number of parties. The protocol is resilient to a fully-asynchronous weak-adaptive adversary that can corrupt a near-optimal number of parties (< (1/3 - ϵ)n) and requires just a verifiable random function (VRF) setup and secure erasures.

Parallel mixing is a common technique for efficiently unlinking messages from their senders' identity. It involves multiple servers arranged in a stratified mix-network (mixnet), each shuffling a fraction of the messages in parallel with others and then relaying them to a subsequent server. By the end of the route through the mixnet's servers, after applying each server's local shuffle, all messages are mixed together, hiding the senders' identities. Unfortunately, parallel mixing is bottlenecked by the busiest server in each mixnet stratum and does not offer a way to ensure load balancing across the servers. Thus, Sybil clients can coordinate to route their messages through one victim server in the middle of the mixnet and subsequent strata, stalling message delivery for everyone and keeping their identities hidden since their messages were already shuffled with those from other clients. This paper presents BalancedMixnet, a new protocol for load balancing clients across the servers in a parallel mix network while ensuring sender anonymity. Our protocol relies on anonymous credentials to ensure clients use a route through the mixnet that is selected uniformly at random and, at the same time, let servers verify that the message is from a valid client and prevent replay attacks. The cost of issuing and validating credentials can be easily amortized across multiple messages from the same client. We implement and evaluate BalancedMixnet, illustrating that the cost of integrating it into a parallel mixnet is modest and provides substantial benefits against Sybil attacks.

This paper presents a new architecture for metadata-private messaging that counters scalability challenges by offloading most computations to the clients. At the core of our design is a distributed private information retrieval (PIR) protocol, where the responder delegates its work to alleviate PIR's computational bottleneck and catches misbehaving delegates by efficiently verifying their results. We introduce DPIR, a messaging system that uses distributed PIR to let a server storing messages delegate the work to the system's clients, such that each client contributes proportional processing to the number of messages it reads. The server removes clients returning invalid results, which DPIR leverages to integrate an incentive mechanism for honest client behavior by conditioning messaging through DPIR on correctly processing PIR requests from other users. The result is a metadata-private messaging system that asymptotically improves scalability over prior work with the same threat model. We show through experiments on a prototype implementation that DPIR concretely improves performance by 3.25× and 4.31× over prior work [3, 5] and that the performance gap grows with the user base~size.

Set reconciliation, where two parties hold fixed-length bit strings and run a protocol to learn the strings they are missing from each other, is a fundamental task in many distributed systems. We present Rateless Invertible Bloom Lookup Tables (Rateless IBLTs), the first set reconciliation protocol, to the best of our knowledge, that achieves low computation cost and near-optimal communication cost across a wide range of scenarios: set differences of one to millions, bit strings of a few bytes to megabytes, and workloads injected by potential adversaries. Rateless IBLT is based on a novel encoder that incrementally encodes the set difference into an infinite stream of coded symbols, resembling rateless error-correcting codes. We compare Rateless IBLT with state-of-the-art set reconciliation schemes and demonstrate significant improvements. Rateless IBLT achieves 3--4× lower communication cost than non-rateless schemes with similar computation cost, and 2--2000× lower computation cost than schemes with similar communication cost. We show the real-world benefits of Rateless IBLT by applying it to synchronize the state of the Ethereum blockchain, and demonstrate 5.6× lower end-to-end completion time and 4.4× lower communication cost compared to the system used in production.

Distributed systems are often designed to recover from downed nodes. Unfortunately, it is challenging to create recovery mechanisms that work in Byzantine networks, where the attacker controls some of the nodes and links. Often times an adversarial node can lie about an honest node being offline, and there is no way to verify this claim or detect the liar.

Yodel is the first system for voice calls that hides metadata (e.g., who is communicating with whom) from a powerful adversary that controls the network and compromises servers. Voice calls require sub-second message latency, but low latency has been difficult to achieve in prior work where processing each message requires an expensive public key operation at each hop in the network. Yodel avoids this expense with the idea of self-healing circuits, reusable paths through a mix network that use only fast symmetric cryptography. Once created, these circuits are resilient to passive and active attacks from global adversaries. Creating and connecting to these circuits without leaking metadata is another challenge that Yodel addresses with the idea of guarded circuit exchange, where each user creates a backup circuit in case an attacker tampers with their traffic. We evaluate Yodel across the internet and it achieves acceptable voice quality with 990 ms of latency for 5 million simulated users.

S.57-63

User convenience and strong security are often at odds, and most security applications need to find some sort of balance between these two (often opposing) goals. The Resource Public Key Infrastructure (RPKI), a security infrastructure built on top of interdomain routing, is not immune to this issue. The RPKI uses the maxLength attribute to reduce the amount of information that must be explicitly recorded in its cryptographic objects. MaxLength also allows operators to easily reconfigure their networks without modifying their RPKI objects. Our network measurements, however, suggest that the maxLength attribute strikes the wrong balance between security and user convenience. We therefore believe that operators should avoid using maxLength. We give operational recommendations and develop software that allow operators to reap many of the benefits of maxLength without its security costs.

Algorand is a new cryptocurrency that confirms transactions with latency on the order of a minute while scaling to many users. Algorand ensures that users never have divergent views of confirmed transactions, even if some of the users are malicious and the network is temporarily partitioned. In contrast, existing cryptocurrencies allow for temporary forks and therefore require a long time, on the order of an hour, to confirm transactions with high confidence.

Private communication over the Internet remains a challenging problem. Even if messages are encrypted, it is hard to deliver them without revealing metadata about which pairs of users are communicating. Scalable anonymity systems, such as Tor, are susceptible to traffic analysis attacks that leak metadata. In contrast, the largest-scale systems with metadata privacy require passing all messages through a small number of providers, requiring a high operational cost for each provider and limiting their deployability in practice.

Extensive standardization and R&D efforts are dedicated to establishing secure interdomain routing. These efforts focus on two mechanisms: origin authentication with RPKI, and path validation with BGPsec. However, while RPKI is finally gaining traction, the adoption of BGPsec seems not even on the horizon due to inherent, possibly insurmountable, obstacles, including the need to replace today's routing infrastructure, the overhead of online cryptography, and meagre benefits in partial deployment. Consequently, secure interdomain routing remains a distant dream. We propose an easily deployable, modest extension to RPKI, called ``path-end validation'', which does not entail replacing/upgrading today's BGP routers nor online cryptographic operations. We show, through rigorous security analyses and extensive simulations on empirically-derived datasets, that path-end validation yields significant security benefits even in very limited partial adoption. We present an open-source, readily deployable prototype implementation of path-end validation.

Extensive standardization and R&D efforts are dedicated to establishing secure interdomain routing. These efforts focus on two complementary mechanisms: origin authentication with RPKI, and path validation with BGPsec. However, while RPKI is finally gaining traction, the adoption of BGPsec seems not even on the horizon. This is due to inherent, possibly insurmountable, obstacles, including the need to replace today's routing infrastructure, meagre benefits in partial deployment and online cryptography.

We present practical off-path TCP injection attacks for connections between current, nonbuggy browsers and Web servers. The attacks allow Web-cache poisoning with malicious objects such as spoofed Web pages and scripts; these objects can be cached for a long period of time, exposing any user of that cache to cross-site scripting , cross-site request forgery , and phishing attacks. In contrast to previous TCP injection attacks, we do not require MitM capabilities or malware running on the client machine. Instead, our attacks rely on a weaker assumption, that the user only enters a malicious Web site, but does not download or install any application. Our attacks exploit subtle details of the TCP and HTTP specifications, and features of legitimate (and very common) browser implementations. An empirical evaluation of our techniques with current versions of browsers shows that connections with most popular Web sites are vulnerable. We conclude this work with practical client- and server-end defenses against our attacks.

We present a practical off-path TCP-injection attack for connections between current, non-buggy browsers and web-servers. The attack allows web-cache poisoning with malicious objects; these objects can be cached for long time period, exposing any user of that cache to XSS, CSRF and phishing attacks.

We show that fragmented IPv4 and IPv6 traffic is vulnerable to effective interception and denial-of-service (DoS) attacks by an off-path attacker. Specifically, we demonstrate a weak attacker intercepting more than 80% of the data between peers and causing over 94% loss rate. We show that our attacks are practical through experimental validation on popular industrial and open-source products, with realistic network setups that involve NAT or tunneling and include concurrent legitimate traffic as well as packet losses. The interception attack requires a zombie agent behind the same NAT or tunnel-gateway as the victim destination; the DoS attack only requires a puppet agent, that is, a sandboxed applet or script running in web-browser context. The complexity of our attacks depends on the predictability of the IP Identification (ID) field which is typically implemented as one or multiple counters, as allowed and recommended by the IP specifications. The attacks are much simpler and more efficient for implementations, such as Windows, which use one ID counter for all destinations. Therefore, much of our focus is on presenting effective attacks for implementations, such as Linux, which use per-destination ID counters. We present practical defenses for the attacks presented in this article, the defenses can be deployed on network firewalls without changes to hosts or operating system kernel.

We present LOT, a lightweight plug and play secure tunneling protocol deployed at network gateways. Two communicating gateways, A and B, running LOT would automatically detect each other and establish an efficient tunnel, securing communication between them. LOT tunnels allow A to discard spoofed packets that specify source addresses in B’s network and vice versa. This helps to mitigate many attacks, including DNS poisoning, network scans, and most notably (Distributed) Denial of Service (DoS). LOT tunnels provide several additional defenses against DoS attacks. Specifically, since packets received from LOT-protected networks cannot be spoofed, LOT gateways implement quotas, identifying and blocking packet floods from specific networks. Furthermore, a receiving LOT gateway (e.g., B) can send the quota assigned to each tunnel to the peer gateway (A), which can then enforce near-source quotas, reducing waste and congestion by filtering excessive traffic before it leaves the source network. Similarly, LOT tunnels facilitate near-source filtering, where the sending gateway discards packets based on filtering rules defined by the destination gateway. LOT gateways also implement an intergateway congestion detection mechanism, allowing sending gateways to detect when their packets get dropped before reaching the destination gateway and to perform appropriate near-source filtering to block the congesting traffic; this helps against DoS attacks on the backbone connecting the two gateways. LOT is practical: it is easy to manage (plug and play, requires no coordination between gateways), deployed incrementally at edge gateways (not at hosts and core routers), and has negligible overhead in terms of bandwidth and processing, as we validate experimentally. LOT storage requirements are also modest.