What's a little leakage between friends?
This addresses a security vulnerability in metadata-private messaging systems, but the solution is incremental as it relies on assumptions about user behavior.
The paper tackles the problem of metadata leakage in messaging systems by introducing a compromised friend attack, where an adversary can infer a user's other ongoing conversations by compromising a friend, and proposes a private answering machine primitive to prevent it, though a secure and efficient construction requires assumptions about bounding the maximum number of friends.
This paper introduces a new attack on recent messaging systems that protect communication metadata. The main observation is that if an adversary manages to compromise a user's friend, it can use this compromised friend to learn information about the user's other ongoing conversations. Specifically, the adversary learns whether a user is sending other messages or not, which opens the door to existing intersection and disclosure attacks. To formalize this compromised friend attack, we present an abstract scenario called the exclusive call center problem that captures the attack's root cause, and demonstrates that it is independent of the particular design or implementation of existing metadata-private messaging systems. We then introduce a new primitive called a private answering machine that can prevent the attack. Unfortunately, building a secure and efficient instance of this primitive under only computational hardness assumptions does not appear possible. Instead, we give a construction under the assumption that users can place a bound on their maximum number of friends and are okay leaking this information.