Better Anonymous Communications George Danezis University of Cambridge Computer Laboratory Queens’ College January 2004 This dissertation is submitted for the degree of Doctor of Philosophy Declaration This dissertation is the result of my own work and includes nothing which is the outcome of work done in collaboration except where speciflcally indi- cated in the text and summarised in section 1.3. This dissertation does not exceed the regulation length of 600001 words, including tables and footnotes. 1using detex thesis.tex | wc Acknowledgements \No man is an island, entire of itself; every man is a piece of the continent, a part of the main." Meditation 17, Devotions Upon Emergent Occasions | John Donne I am deeply indebted to my supervisor and teacher Ross Anderson, for al- lowing me to join his research group, and helping me at key points during the last three years. I hope this document shows that his trust in me was justifled. I am also grateful to Robin Walker, my director of studies, for his support during the last six years and for giving me the opportunity to study in Cambridge. These years of research would have been considerably less productive without the local scientiflc community, my colleagues in the computer secu- rity group of the Computer Laboratory, but also my colleagues from around the world. I would like to specially thank my co-authors, Richard Clayton, Markus Kuhn, Andrei Serjantov, Roger Dingledine, Nick Mathewson and Len Sassaman. This research would not have been possible without my parents. At every stage of my academic life they acted as role models, provided moral and flnancial support. The special value they attach to education has marked me for life. Iamgratefultocafes,socialcentresandautonomouszonesaroundEurope for having me as a guest; it is fltting that some ideas developed in this thesis were flrst conceived there. Similarly I am indebted to my friends, house- mates and companions, that have shared with me everything, at times when none of us had much. Without them, all this would be meaningless. This research was partly supported by the Cambridge University Euro- pean Union Trust, Queens’ College, and The Cambridge-MIT Institute. Better Anonymous Communications George Danezis Summary This thesis contributes to the fleld of anonymous communications over widely deployed communication networks. It describes novel schemes to protect anonymity; it also presents powerful new attacks and new ways of analysing and understanding anonymity properties. We present Mixminion, a new generation anonymous remailer, and exam- ine its security against all known passive and active cryptographic attacks. We use the secure anonymous replies it provides, to describe a pseudonym server, as an example of the anonymous protocols that mixminion can sup- port. The security of mix systems is then assessed against a compulsion threat model, in which an adversary can request the decryption of material from honest nodes. A new construction, the fs-mix, is presented that makes tracing messages by such an adversary extremely expensive. Moving beyond the static security of anonymous communication proto- cols, we deflne a metric based on information theory that can be used to measure anonymity. The analysis of the pool mix serves as an example of its use. We then create a framework within which we compare the tra–c analy- sis resistance provided by difierent mix network topologies. A new topology, based on expander graphs, proves to be e–cient and secure. The rgb-mix is also presented; this implements a strategy to detect (cid:176)ooding attacks against honest mix nodes and neutralise them by the use of cover tra–c. Finally a set of generic attacks are studied. Statistical disclosure attacks model the whole anonymous system as a black box, and are able to uncover the relationships between long-term correspondents. Stream attacks trace streams of data travelling through anonymizing networks, and uncover the communicating parties very quickly. They both use statistical methods to drastically reduce the anonymity of users. Other minor attacks are described against peer discovery and route reconstruction in anonymous networks, as well as the na˜‡ve use of anonymous replies. 6 Contents 1 Introduction 13 1.1 Scope and purpose . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2 Schedule of work . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Work done in collaboration . . . . . . . . . . . . . . . . . . . . 18 2 Deflning anonymity 19 2.1 Anonymity as a security property . . . . . . . . . . . . . . . . 19 2.1.1 Traditional threat model . . . . . . . . . . . . . . . . . 21 2.1.2 Compulsion threat model . . . . . . . . . . . . . . . . 22 2.1.3 Assessing real-world capabilities . . . . . . . . . . . . . 23 2.2 Technical deflnitions and measures . . . . . . . . . . . . . . . 24 2.3 An information theoretic deflnition . . . . . . . . . . . . . . . 26 2.3.1 Application: the pool mix . . . . . . . . . . . . . . . . 27 2.3.2 Application: composing mixes . . . . . . . . . . . . . . 31 2.3.3 A framework for analysing mix networks . . . . . . . . 32 2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3 Primitives and building blocks 37 3.1 Symmetric cryptographic primitives . . . . . . . . . . . . . . . 37 3.1.1 Hash functions . . . . . . . . . . . . . . . . . . . . . . 38 3.1.2 Pseudo-random functions: stream ciphers . . . . . . . . 39 3.1.3 Random permutations: block ciphers . . . . . . . . . . 39 3.2 Cryptographic constructions . . . . . . . . . . . . . . . . . . . 40 3.2.1 Block cipher modes . . . . . . . . . . . . . . . . . . . . 40 3.2.2 Large block ciphers: BEAR . . . . . . . . . . . . . . . 41 3.2.3 Message authentication codes for integrity . . . . . . . 43 7 8 CONTENTS 3.3 Asymmetric cryptographic primitives . . . . . . . . . . . . . . 44 3.3.1 Di–e-Hellman exchange . . . . . . . . . . . . . . . . . 44 3.3.2 The El Gamal encryption system . . . . . . . . . . . . 45 3.3.3 The Rivest-Shamir-Adelman crypto-system . . . . . . . 46 3.3.4 Strengthening the primitives . . . . . . . . . . . . . . . 47 3.4 Plausible deniability . . . . . . . . . . . . . . . . . . . . . . . 48 3.4.1 Deniable encryption . . . . . . . . . . . . . . . . . . . 48 3.5 Forward security . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4 Related work 53 4.1 Trusted and semi-trusted relays . . . . . . . . . . . . . . . . . 54 4.1.1 anon.penet.fi . . . . . . . . . . . . . . . . . . . . . . 54 4.1.2 Anonymizer & SafeWeb . . . . . . . . . . . . . . . . . 55 4.1.3 Type I \Cypherpunk" remailers . . . . . . . . . . . . . 57 4.1.4 Crowds . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.1.5 Nym servers . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Mix systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.2.1 Chaum’s original mix . . . . . . . . . . . . . . . . . . . 60 4.2.2 ISDN mixes, Real Time mixes and Web mixes . . . . . 63 4.2.3 Babel and Mixmaster . . . . . . . . . . . . . . . . . . . 66 4.2.4 Stop-and-go mixes . . . . . . . . . . . . . . . . . . . . 68 4.2.5 Onion routing . . . . . . . . . . . . . . . . . . . . . . . 69 4.2.6 Peer-to-peer mix networks . . . . . . . . . . . . . . . . 71 4.2.7 Attacks against the ‘young’ Tarzan . . . . . . . . . . . 72 4.2.8 Robust & veriflable mix constructions . . . . . . . . . . 76 4.2.9 Mix building blocks, attacks and analysis . . . . . . . . 79 4.3 Other systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5 Mixminion 85 5.1 Models and requirements . . . . . . . . . . . . . . . . . . . . . 86 5.1.1 The system view . . . . . . . . . . . . . . . . . . . . . 87 5.1.2 Requirements . . . . . . . . . . . . . . . . . . . . . . . 88 CONTENTS 9 5.1.3 Orthogonal issues . . . . . . . . . . . . . . . . . . . . . 91 5.2 The anatomy of the Mixminion format . . . . . . . . . . . . . 93 5.2.1 The sub-header structure . . . . . . . . . . . . . . . . . 94 5.2.2 The header structure . . . . . . . . . . . . . . . . . . . 95 5.2.3 The whole packet . . . . . . . . . . . . . . . . . . . . . 96 5.2.4 Decoding messages . . . . . . . . . . . . . . . . . . . . 98 5.3 Security analysis of Mixminion . . . . . . . . . . . . . . . . . . 102 5.3.1 Bitwise unlinkability . . . . . . . . . . . . . . . . . . . 102 5.3.2 Route position and length leakage . . . . . . . . . . . . 102 5.3.3 Tagging attacks . . . . . . . . . . . . . . . . . . . . . . 103 5.4 Protocols with reply blocks . . . . . . . . . . . . . . . . . . . . 106 5.4.1 Protocol notation . . . . . . . . . . . . . . . . . . . . . 107 5.4.2 The Who Am I? attack . . . . . . . . . . . . . . . . . 108 5.4.3 Nym servers . . . . . . . . . . . . . . . . . . . . . . . . 110 5.5 Beyond Mixminion . . . . . . . . . . . . . . . . . . . . . . . . 113 5.5.1 Lowering the overheads of Mixminion . . . . . . . . . . 113 5.5.2 Simplifying the swap operation . . . . . . . . . . . . . 114 5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 6 Forward secure mixing 117 6.1 How to trace a mixed message . . . . . . . . . . . . . . . . . . 118 6.2 Deflning forward anonymity . . . . . . . . . . . . . . . . . . . 120 6.3 The fs-mix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.3.1 The cost of an fs-mix . . . . . . . . . . . . . . . . . . . 122 6.4 Security analysis . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.4.1 Protection against compulsion . . . . . . . . . . . . . . 123 6.4.2 Tra–c analysis . . . . . . . . . . . . . . . . . . . . . . 124 6.4.3 Robustness . . . . . . . . . . . . . . . . . . . . . . . . 125 6.5 Additional features . . . . . . . . . . . . . . . . . . . . . . . . 126 6.6 Other forward security mechanisms . . . . . . . . . . . . . . . 127 6.6.1 Forward secure link encryption . . . . . . . . . . . . . 127 6.6.2 Tamper-proof secure hardware . . . . . . . . . . . . . . 128 6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 10 CONTENTS 7 Sparse mix networks 129 7.1 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 7.2 Mix networks and expander graphs . . . . . . . . . . . . . . . 131 7.3 The anonymity of expander topologies . . . . . . . . . . . . . 133 7.3.1 Protection against intersection attacks . . . . . . . . . 135 7.3.2 Subverted nodes . . . . . . . . . . . . . . . . . . . . . . 138 7.4 Comparing topologies . . . . . . . . . . . . . . . . . . . . . . . 139 7.4.1 Mix cascades . . . . . . . . . . . . . . . . . . . . . . . 140 7.4.2 Mix networks . . . . . . . . . . . . . . . . . . . . . . . 140 7.5 An example network . . . . . . . . . . . . . . . . . . . . . . . 142 7.5.1 Selecting a good topology . . . . . . . . . . . . . . . . 142 7.5.2 Mixing speed . . . . . . . . . . . . . . . . . . . . . . . 143 7.5.3 Resisting intersection and tra–c analysis attacks . . . . 143 7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 8 Red-green-black mixes 147 8.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 8.2 Design principles, assumptions and constraints . . . . . . . . . 149 8.3 Red-green-black mixes . . . . . . . . . . . . . . . . . . . . . . 150 8.4 The security of rgb-mixes . . . . . . . . . . . . . . . . . . . . . 152 8.5 A cautionary note . . . . . . . . . . . . . . . . . . . . . . . . . 155 8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 9 Statistical disclosure attacks 157 9.1 The disclosure attack revisited . . . . . . . . . . . . . . . . . . 158 9.2 The statistical disclosure attack . . . . . . . . . . . . . . . . . 159 9.2.1 Applicability and e–ciency . . . . . . . . . . . . . . . . 160 9.3 Statistical attacks against a pool mix . . . . . . . . . . . . . . 162 9.3.1 Approximating the model . . . . . . . . . . . . . . . . 163 9.3.2 Estimating ~v . . . . . . . . . . . . . . . . . . . . . . . 165 9.4 Evaluation of the attack . . . . . . . . . . . . . . . . . . . . . 167 9.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169