To Signal or Not to Signal? Layering Traffic Analysis Resistance on Secure Instant Messaging

Transport layer data leaks metadata unintentionally$\unicode{x2013}$such as who communicates with whom. While tools for strong transport layer privacy exist, they have adoption obstacles, including performance overheads incompatible with mobile devices. We posit that by changing the objective of metadata privacy for $\textit{all traffic}$, we can open up a new design space for pragmatic approaches to transport layer privacy. As a first step in this direction, we propose the $\textit{hybrid model}$, a system model that allows one to practically combine, and formally reason about network traffic with different privacy guarantees ($\textit{regular}$ and $\textit{deniable}$) in one joint system. Using techniques from information flow control we present a principled approach to construct a formal model and prove that deniable traffic achieves transport layer privacy against strong adversaries$\unicode{x2013}$this constitutes the first bridging of information flow control and anonymous communication to our knowledge. Additionally, we show that existing state-of-the-art protocols can be extended to support transport layer privacy, by designing a novel protocol for $\textit{deniable instant messaging}$ (DenIM), which is a variant of the Signal protocol. As an instantiation of the hybrid model, we implement and evaluate a proof-of-concept instant messaging system running both DenIM and regular Signal. We empirically show that the hybrid model can maintain low-latency for regular Signal traffic without breaking existing features, while at the same time supporting deniable Signal traffic.