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

Rosita: Towards Automatic Elimination of Power-Analysis Leakage in Ciphers

Madura A. Shelton (University of Adelaide), Niels Samwel (Radboud University), Lejla Batina (Radboud University), Francesco Regazzoni (University of Amsterdam and...

Read More

Shadow Attacks: Hiding and Replacing Content in Signed PDFs

Christian Mainka (Ruhr University Bochum), Vladislav Mladenov (Ruhr University Bochum), Simon Rohlmann (Ruhr University Bochum)

Read More

Time-Based CAN Intrusion Detection Benchmark

Deborah Blevins (University of Kentucky), Pablo Moriano, Robert Bridges, Miki Verma, Michael Iannacone, and Samuel Hollifield (Oak Ridge National Laboratory)

Read More

Who's Hosting the Block Party? Studying Third-Party Blockage of...

Marius Steffens (CISPA Helmholtz Center for Information Security), Marius Musch (TU Braunschweig), Martin Johns (TU Braunschweig), Ben Stock (CISPA Helmholtz...

Read More