Analyzing and Protecting Communication Metadata

Most communication systems (e.g., e-mails, instant messengers, VPNs) use encryption to prevent third parties from learning sensitive information. However, encrypted communications protect the contents but often leak metadata: the amount of data sent and the time it was sent, the way the data should be decrypted, the identity of the sender and the recipient. These metadata are a pervasive threat to privacy: They enable a variety of attacks that range from recovering plaintext contents from encrypted communications to inferring communicating parties. Our goal in this thesis is two-fold: First, to raise awareness about this problem by demonstrating attacks that threaten user privacy; and second, to propose novel solutions that reduce the metadata leakage and maintain acceptable usability and costs. To achieve the first goal, we present the first work that performs an in-depth analysis of the communications of wearable devices under the lens of traffic analysis. We demonstrate that the metadata of Bluetooth communications of wearable devices (smartwatches, fitness trackers, and blood-pressure monitors) leak sensitive information to a passive observer, despite the use of encryption. By design, these devices handle fine-grained and long-term, personal, medical and lifestyle-related data from their users. Our work highlights the need to rethink how sensitive data is exchanged in this setting. More generally, we confirm that metadata can pose a threat to user privacy, even in settings where traffic-analysis attacks are perhaps not an immediate threat. For the second goal, we begin by presenting a theoretical contribution that concerns ciphertext formats: Padmé, a padding function designed to reduce the metadata leakage of files and messages through their length. Padmé efficiently hides the size of objects even when they have very different sizes. Padmé is a part of PURBs, a ciphertext format that does not leak metadata, except for a small amount about the size. Then, we design systems that enable communicating while reducing metadata leakage: Anonymous Communication Networks (ACNs). ACNs protect against some metadata leakage (e.g., who is communicating and when). Traffic-analysis resistant ACNs have not seen widespread adoption yet, possibly due to their technical shortcomings. We focus on two aspects that remain unsolved: small-scale traffic-agnostic communication that achieves low latency, and large-scale asynchronous messaging that handles millions of users. We present PriFi, an ACN that provides provable traffic-analysis resistance and low-latency in the context of a local-area network. The protocol hides the source and recipient of a message by ensuring that the communication patterns of all participants are equal, even in the presence of active attacks. PriFi ensures low-latency and traffic-agnostic communication for a small set of users. We then present Rubato, an ACN for anonymous messaging that handles millions of users. Other large-scale ACNs have an important limitation: A sender and a recipient need to be online at the same time to resist intersection attacks. As participants are uncoordinated, they need to be online and to send cover traffic at all times, which is infeasible for many users. Rubato is a circuit-based mixnet that enables its users to be asynchronous; they can participate in the network according to their own schedule. Unlike previous ACNs, this enables users to participate using their mobile devices