Ian Martiny (University of Colorado Boulder), Gabriel Kaptchuk (Boston University), Adam Aviv (The George Washington University), Dan Roche (U.S. Naval Avademy), Eric Wustrow (University of Colorado Boulder)

The Signal messaging service recently deployed a emph{sealed sender} feature that provides sender anonymity by cryptographically hiding a message's sender from the service provider. We demonstrate, both theoretically and empirically, that this one-sided anonymity is broken when two parties send multiple messages back and forth; that is, the promise of sealed sender does not emph{compose} over a conversation of messages. Our attack is in the family of Statistical Disclosure Attacks (SDAs), and is made particularly effective by emph{delivery receipts} that inform the sender that a message has been successfully delivered, which are enabled by default on Signal. We show using theoretical and simulation-based models that Signal could link sealed sender users in as few as 5 messages.

Our attack goes beyond tracking users via network-level identifiers by working at the application layer of Signal. This make our attacks particularly effective against users that employ Tor or VPNs as anonymity protections, who would otherwise be secure against network tracing. We present a range of practical mitigation strategies that could be employed to prevent such attacks, and we prove our protocols secure using a new simulation-based security definition for one-sided anonymity over any sequence of messages. The simplest provably-secure solution uses many of the same mechanisms already employed by the (flawed) sealed-sender protocol used by Signal, which means it could be deployed with relatively small overhead costs; we estimate that the extra cryptographic cost of running our most sophisticated solution in a system with millions of users would be less than $40 per month.

View More Papers

SpecTaint: Speculative Taint Analysis for Discovering Spectre Gadgets

Zhenxiao Qi (UC Riverside), Qian Feng (Baidu USA), Yueqiang Cheng (NIO Security Research), Mengjia Yan (MIT), Peng Li (ByteDance), Heng Yin (UC Riverside), Tao Wei (Ant Group)

Read More

Empirical Scanning Analysis of Censys and Shodan

Christopher Bennett, AbdelRahman Abdou, and Paul C. van Oorschot (School of Computer Science, Carleton University, Canada)

Read More

Raising Trust in the Food Supply Chain

Alexander Krumpholz, Marthie Grobler, Raj Gaire, Claire Mason, Shanae Burns (CSIRO Data61)

Read More

To Err.Is Human: Characterizing the Threat of Unintended URLs...

Beliz Kaleli (Boston University), Brian Kondracki (Stony Brook University), Manuel Egele (Boston University), Nick Nikiforakis (Stony Brook University), Gianluca Stringhini (Boston University)

Read More