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

LaKSA: A Probabilistic Proof-of-Stake Protocol

Daniel Reijsbergen (Singapore University of Technology and Design), Pawel Szalachowski (Singapore University of Technology and Design), Junming Ke (University of Tartu), Zengpeng Li (Singapore University of Technology and Design), Jianying Zhou (Singapore University of Technology and Design)

Read More

PGFUZZ: Policy-Guided Fuzzing for Robotic Vehicles

Hyungsub Kim (Purdue University), Muslum Ozgur Ozmen (Purdue University), Antonio Bianchi (Purdue University), Z. Berkay Celik (Purdue University), Dongyan Xu (Purdue University)

Read More

KUBO: Precise and Scalable Detection of User-triggerable Undefined Behavior...

Changming Liu (Northeastern University), Yaohui Chen (Facebook Inc.), Long Lu (Northeastern University)

Read More

(Short) Fooling Perception via Location: A Case of Region-of-Interest...

Kanglan Tang, Junjie Shen, and Qi Alfred Chen (UC Irvine)

Read More