KATHOLIEKE UNIVERSITEIT LEUVEN FACULTEITINGENIEURSWETENSCHAPPEN DEPARTEMENTELEKTROTECHNIEK–ESAT KasteelparkArenberg10,3001Leuven-Heverlee Anonymity and Privacy in Electronic Services Promotors: Proefschriftvoorgedragentot Prof.Dr.ir.BartPreneel hetbehalenvanhetdoctoraat Prof.Dr.ir.JoosVandewalle indeingenieurswetenschappen door Claudia DIAZ December2005 KATHOLIEKE UNIVERSITEIT LEUVEN FACULTEITINGENIEURSWETENSCHAPPEN DEPARTEMENTELEKTROTECHNIEK–ESAT KasteelparkArenberg10,3001Leuven-Heverlee Anonymity and Privacy in Electronic Services Jury: Proefschriftvoorgedragentot Prof.Dr.ir.GuidoDeRoeck,voorzitter hetbehalenvanhetdoctoraat Prof.Dr.ir.BartPreneel,promotor indeingenieurswetenschappen Prof.Dr.ir.JoosVandewalle,promotor door Prof.Dr.ir.BartDeDecker Prof.Dr.ir.GeertDeconinck Claudia DIAZ Dr.DoganKesdogan(RWTHAachenUniversity) Prof.Dr.ir.PatrickWambacq U.D.C.681.3*D46 December2005 (cid:13)c Katholieke Universiteit Leuven – Faculteit Ingenieurswetenschappen Arenbergkasteel, B-3001 Heverlee (Belgium) Allerechtenvoorbehouden. Nietsuitdezeuitgavemagvermenigvuldigden/of openbaar gemaakt worden door middel van druk, fotocopie, microfilm, elektron- isch of op welke andere wijze ook zonder voorafgaande schriftelijke toestemming van de uitgever. Allrightsreserved. Nopartofthepublicationmaybereproducedinanyform by print, photoprint, microfilm or any other means without written permission from the publisher. D/2005/7515/99 ISBN 90-5682-671-9 Al abuelo Acknowledgements No man is an island, entire of itself... – John Donne This thesis would not have been possible without the help and support of many people I would like to acknowledge here. First, I want to thank Prof. Bart Preneel for giving me the opportunity to do this Ph.D., guiding my research and finding the money to fund me; and Prof. Joos Vandewalle for offering me the opportunity to work in his research group. I am also very grateful to Prof. Bart De Decker and Prof. Geert Deconinck for their reviews and suggestions to improve this dissertation. I want to thank Prof. Patrick Wambacq and Dr. Dogan Kesdogan for serving as jury members and Prof. Guido De Roeck for chairing the jury. Iwouldalsoliketothankallmyco-authors,andinparticularJorisClaessens, Andrei Serjantov, Len Sassaman and Evelyne Dewitte. Their collaboration has been essential in many of the research results presented here. Special thanks to Stefaan Seys for translating the abstract of this dissertation from English to Dutch. I would like to take this opportunity to also thank George Danezis, Roger Dingledine, Andreas Pfitzmann, Paul Syverson, Ben Laurie, Joss Wright and the other regular PET attendees for the fruitful and motivating discussions on anonymity research. A big thanks goes to my (current and past) COSIC colleagues. I am very lucky to work with people who are always willing to help out when you need it. They have also been great company at work, for dinner, over a coffee or a beer. ThisincludesinparticularDannyDeCock,KlausKursawe,SvetlaNikova, Jasper Scholten and Berna O¨rs. P´ela No¨e, Marleen Somers and Elvira Wouters deserve a big thank you for their patience and valuable help with all sorts of administrative issues. I also want to thank my family and friends back in Spain for making it so v easy to disconnect from the Ph.D. during holidays. And the last and biggest thank you goes to my partner Diego Juiz for his patience, understanding and encouragement over the time it has taken me to complete this Ph.D. Finally, I would like to mention my two cats, Ambar and Borges, who have amused my writing days. Claudia D´ıaz Gent, December 2005 Abstract Thisthesispresentsinformationtheoreticanonymitymetricsandvariousanalysis of anonymous communication nodes. Our contributions are a step towards the understandingofanonymitypropertiesandthedevelopmentofrobustanonymous communications. Anonymouscommunicationsareanessentialbuildingblockfor privacy-enhanced applications, as the data available at the communication layer may leak critical private information. Oneofthemaincontributionsofourworkisthedegree of anonymity,aprac- tical information theoretic anonymity metric. Entropy-based anonymity metrics can be applied to measure the degree of anonymity provided by an anonymous service to its users. In particular, these metrics can be applied to systems which leak probabilistic relationships between the anonymous subjects and their trans- actions. We present a taxonomy of the two main building blocks used to imple- ment anonymous communication networks, which are anonymous communica- tion nodes (called mixes) and cover traffic policies (called dummy traffic). We propose a model for describing anonymous communication nodes which extends designpossibilitiesandfacilitatestheanalysisofanonymityproperties. Weiden- tify the parameters which must be taken into account in the design and analysis of mix-based anonymous communication networks. Inordertoshowthepracticalapplicationsofinformationtheoreticanonymity metrics, we have applied the metrics to evaluate the anonymity properties of various nodes for anonymous communication which have been proposed in the literature. We analyze the anonymity provided by these nodes when subject to passive and active attacks, while considering scenarios with and without cover traffic techniques. We have analyzed two working implementations of anonymous email in real traffic conditions. The tools used for the analysis are information theoretic met- rics and our model for anonymous communication nodes. We show that anony- mous email traffic patterns are hard to predict and no assumptions on them should be made. We find that the two studied designs offer very different trade- vii offs for anonymity and performance. All in all, we believe that information theoretic metrics are a useful tool to characterize anonymity properties. Our work is one step towards a better understanding of anonymity and our results can be used for the design of robust anonymity technologies.