Hang With Your Buddies to Resist Intersection Attacks

David Isaac Wolinsky, Ewa Syta, and Bryan Ford
Yale University

20th ACM Conference on Computer and Communications Security (CCS)
November 4-8, 2013, Berlin, Germany


Some anonymity schemes, such as DC-nets and MIX cascades, can guarantee anonymity even against traffic analysis – provided messages are independent and unlinkable. Users in practice often desire pseudonymity – sending messages intentionally linkable to each other but not to the sender – but pseudonymity in dynamic networks exposes users to intersection attacks. We present Buddies, the first systematic attempt to offer intersection attack resistant pseudonyms in practical anonymity systems. Buddies groups users dynamically into buddy sets, controlling message transmission to make buddies within a set behaviorally indistinguishable to a traffic-monitoring adversary. Intersection attack resistance does not come “for free,” of course, and Buddies offers users control over the inevitable tradeoffs between anonymity, latency, and the useful lifetime of a pseudonym. Using trace-based simulations and a working prototype, we find that Buddies can guarantee non-trivial anonymity set sizes in realistic chat/microblogging scenarios, for both short-lived and long-lived pseudonyms.

Paper: PDF

This material is based upon work supported by the Defense Advanced Research Agency (DARPA) and SPAWAR Systems Center Pacific, Contract No. N66001-11-C-4018. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Defense Advanced Research Agency (DARPA) and SPAWAR Systems Center Pacific.