Privacy and Anonymity

This page gives an overview of privacy and anonymity research in the Security Group at Microsoft Research, UK. We study the technical aspects of these topics.

Privacy-friendly metering for smart grids

(by George Danezis, Markulf Kohlweiss, Cedric Fournet and Alfredo Rial (MSRC Intern))

Privacy & Smart metering deployment

Many smart grid proposals threaten users' privacy by disclosing fine-grained consumption data to utilities. We have designed protocols that allow for precise billing of consumption while not revealing any consumption information to third parties.

Our protocols combines a signed tariff policy from the utility with signed readings output by a tamper-resistant meter, to compute a total fee. They use zero-knowledge proofs to ensure that the fee is correct without disclosing any consumption data. A wide variety of practical tariff policies can be applied and easily changed. Tariff structures currently proposed for smart-meters are particularly simple and efficient.

Prototypes shows our schemes are generally practical in terms of both communication and computational cost. They can be integrated in a smart metering system in various ways, through local home servers, smart devices and on-line services.

Our protocols are generic enough to be used in other settings such as pay-as-you-drive car insurance, electronic traffic pricing and on-line services billing.

More resources:

Anonymity at access networks and secure NLA

(Tuomas Aura, Michael Roe, George Danezis)

New communications technology often has implications for the privacy users. One such question is whether mobile computer users can move around anonymously. We looked at the issue of location privacy from the point of view of casual observers at the access link. Network chatter, in particular failed attempts to connect to services that are not available on the current link, reveals a lot of information about the user identity and affiliations. The chatter originates from all layers of the protocol stack and from so many different applications that there is no simple way to prevent it. We suggest the following policy: computers should discover or connect to services automatically only when they can identify the network and know that the service is available on that network. This work was done jointly with Janne Lindqvist from Helsinki University of Technology and Anish Mohammed from RHUL.

Tuomas Aura, Janne Lindqvist, Michael Roe, Anish Mohammed, Chattering laptops. In proceedings of Privacy Enhancing Technologies Symposium (PETS 2008), LNCS 5134, July 2008, Springer.

In order to be completely reliable, the same-network policy requires a secure mechanism for recognizing networks. For this reason, we developed a secure network location awareness (NLA) protocol, which also works as a general security mechanism for NLA in networks that are currently unauthenticated. It is based on public-key authentication of DHCP servers and increases the security of the current Windows Vista NLA. When a mobile computer connects to a network for the first time, it learns the public key (self-signed certificate) of the DHCP server, which is used as the NLA network fingerprint for recognizing and authenticating the same network later. The DHCP server may present a certificate chain instead to bind multiple DHCP servers into one logical network. This also improves the usability of NLA because, unlike in the current Vista implementation, multiple IP segments can be recognized as a single network without causing security problems. This project was in cooperation with Steven Murdoch from University of Cambridge. We implemented a prototype of the authentication protocol, which could potentially be transferred to the Windows DHCP client and server.

Tuomas Aura, Michael Roe, Steven J. Murdoch, Securing network location awareness with authenticated DHCP. In proceedings of IEEE SecureComm 2007, September 2007.

Another situation where mobile computers leak information is when they discover 802.11 wireless access points, especially when they actively probe the APs to speed up the discovery or to find APs that have disabled the SSID broadcast. These probes advertise the list of previously visited networks and represent a privacy risk: a local eavesdropper can observe them and infer attributes of the client based on its previous associations. We propose an access-point discovery protocol that supports fast discovery and hidden networks, while also preserving privacy. Our solution is incrementally deployable: it is efficient, actually reducing the reassociation time compared to traditional hidden APs, requires only small modifications to current clients and access points, interoperates with current networks, and does not change the user experience. We proved the security and privacy properties of our protocol, and provided efficiency measurements based on a prototype implementation.

Janne Lindqvist, Tuomas Aura, Michael Roe. Privacy-Preserving 802.11 Access-Point Discovery. Submitted for publication.

Location privacy

(George Danezis)

George has looked at two other aspects of location privacy. The first is a mechanism for implementing pay-as-you-drive insurance policies without leaking any location information to the insurance company. This is done via a mixture of auditing ciphertexts, secure hardware and careful security engineering. Secondly we have worked on re-identification of anonymized location traces. We show that traces at the granularity of GSM cells can be re-identified in a matter of hours, given good past profiles of movement of an individual. Both works are in collaboration with the COSIC group at KU Leuven.

B. Preneel, C. Troncoso, G. Danezis, and E. Kosta. PriPAYD: Privacy Friendly Pay-As-You-Drive Insurance. In Workshop on Privacy in the Electronic Society 2007, ACM, 9 pages, 2007.

Yoni De Mulder, George Danezis, Lejla Batina and Bart Preneel. Identification via Location-Profiling in GSM Networks. Workshop on Privacy in the Electronic Society (WPES 2008), Alexandria, Virginia, USA.

Analysis of anonymous communications

(George Danezis)

Anonymous communications require complex distributed systems, with multiple factors such as resilience to churn, latency and bandwidth having to be optimised at the same time as security maintained. The work has focused on (1) refining measures for anonymity (2) analysing the interdependencies between systems’ issues and the anonymity provided (3) designing cryptographic mechanisms to support their operation.

A major contribution has recently been our understanding of how denial-of-service attacks against anonymity systems not only degrades performance and usability, but can also be used to enhance traffic analysis, by forcing retransmissions. We analyse many families of systems, from traditional mix networks to onion routing and peer-to-peer anonymity systems and find them all more vulnerable than previously believed. This is joint work with Nikita Borisov’s group at UIUC.

Nikita Borisov, George Danezis, Prateek Mittal and Parisa Tabriz. Denial of Service or Denial of Security? How Attacks on Reliability can Compromise Anonymity. ACM CCS 2007.

A second key contribution is the analysis of the effect that partial knowledge of the anonymizing network has on anonymity. We show that when users only know a small fraction of relays they are vulnerable to a whole new family of attacks, we call bridging and fingerprinting. This is joint work with Paul Syverson from the Naval Research Lab.

George Danezis and Paul Syverson. Bridging and Fingerprinting: Epistemic Attacks on Route Selection. Privacy Enhancing Technologies Symposium (PETS 2008), Leuven, Belgium.

Recently a number of mechanisms have been proposed to “revoke” anonymity in case of abuse. This is the equivalent for anonymity systems of the role key escrow played for encryption systems. We showed that two of those mechanisms are in fact weak, in that they allow secure anonymous communications despite the escrow mechanisms. This is a result with profound policy implications, as it shows that it is not possible to “wrap” a layer of escrow around any anonymity system, without modifying its internals significantly.

George Danezis and Len Sassaman. How to Bypass Two Anonymity Revocation Schemes. Privacy Enhancing Technologies Symposium (PETS 2008), Leuven, Belgium.

Lately we have been looking at the cryptographic security of anonymous communications. With Ian Goldberg, from the University of Waterloo, we propose a cryptographic way to package anonymous messages that is very compact. It uses elliptic curves for cryptography requiring as few as 224 bytes of headers to route a packet over 5 mixes. We provide proofs of its security in the random oracle model, as well as a full featured reference implementation.

George Danezis and Ian Goldberg. Sphinx: A Compact and Provably Secure Mix Format. Manuscript under review, November 2008.

George has made with others a minor correction to a wide belief that anonymity can only decrease through the operation of a systems. Both the work on escrow and anonymity decrease is joint with the COSIC team at KU Leuven.

C. Diaz, C. Troncoso, and G. Danezis. Does additional information always reduce anonymity?. In Workshop on Privacy in the Electronic Society 2007, ACM, 4 pages, 2007.

Detecting PII in digital documents

(Tuomas Aura, Michael Roe)

Authoring processSometimes, it is necessary to remove author names and other personally identifiable information (PII) from documents before publication. It is, however, difficult to be sure that all the metadata has been removed. We designed a novel defensive tool for detecting names and identifiers in digital documents. By using the detection tool, we learned about where PII may be stored in documents and how it is put there. A key observation is that, contrary to common belief, user and machine identifiers and other metadata are not embedded in documents only by a single piece of software, such as Microsoft Word, but by various tools used at different stages of the document authoring process. We used the tool to detect information leaks in Office 2003 documents and to validate the enhanced document scrubbing features in Office 2007.

Tuomas Aura, Thomas A. Kuhn and Michael Roe. Scanning electronic documents for Personally identifiable information. In proceedings of Workshop on Privacy in the Electronic Society (WPES 2006), October 2006.

Other work privacy and traffic analysis

George published a couple of position papers at the Security Protocols’ Workshop, about doctrinal issues around offensive information warfare, as well as the impossibility of eliminating all covertness and anonymity from communications.

George Danezis. Covert Communications Despite Traffic Data Retention. Cambridge Security Protocols Workshop (SPW 2008). Sidney Sussex College, Cambridge, UK.

Daniel Cvrcek and George Danezis. Fighting the Good Internet War. Cambridge Security Protocols Workshop (SPW 2008). Sidney Sussex College, Cambridge, UK.