One of the rare delights of living and working as a security and privacy researcher in the UK is the bi-yearly schedule of surveillance legislation. Despite being often defeated, like the Phoenix, they only spring back to life at the slightest opportunity. This time round is no different: the PM has announced that secret all party negotiations reached consensus on an emergency bill enabling data retention (after it was deemed illiberal at a European level). It is meant to complete its journey through parliament this week, making an analysis all the more pressing.

First of all, it is important to appreciate that the bill fills the gap left by the traffic data retention directive’s (Directive 2006/24/EC) demise, when it was ruled invalid by the Court of Justice of the European Union. In theory, it should enable the same regime of data retention to continue without addressing in the slightest the civil liberties concerns that lead to the demise of the directive. There is however a problem: traffic data retention makes sense if it is widely implemented. There is no point in services in the UK retaining data, if US services or German services do not — the “bad guys” or anyone who values their privacy, would simply move their operations there.

Partly to deal with the possible lack of data retention abroad, the bill has provisions for the extraterritorial application of some powers, to force retention of interception of traffic. Which means that if you have some presence in the UK you may be asked nicely to retain data or provide wiretaps to UK law-enforcement or spooks. In fact even if you do not you may be asked anyways, and in extremis a public notice may be sufficient to force you to retain certain types of data. It is absolutely not clear to me what this means for foreign providers or technology companies.

The bill gives wide powers to the secretary of state to ask operators to retain any “relevant communications” data he/she wishes — where “relevant” points to the types of data mentioned in the Data Retention Directive (2009). They may impose specific conditions, and also decide to compensate operators for their trouble. One key limitation is that the retention period should not exceed 12 months.

For a blast from the past, a quick reminder of how “communications data” is defined in RIPA — which this bill piggy-backs on:

(4) In this Chapter “communications data” means any of the following—

(a) any traffic data comprised in or attached to a communication (whether by the sender or otherwise) for the purposes of any postal service or telecommunication system by means of which it is being or may be transmitted;

(b) any information which includes none of the contents of a communication (apart from any information falling within paragraph (a)) and is about the use made by any person—

(i) of any postal service or telecommunications service; or

(ii) in connection with the provision to or use by any person of any telecommunications service, of any part of a telecommunication system;

(c) any information not falling within paragraph (a) or (b) that is held or obtained, in relation to persons to whom he provides the service, by a person providing a postal service or telecommunications service.

Back in 2000 this definition was just about sane. At the time you could have email (content = body, comms = headers, in relation = subscriber information) or web requests to public resources, or IRC or usenet — none of which had much data on users. Today, what exactly is meant by category (c) “held or obtained, in relation to persons to whom he provides the service” is rather all encompassing. I am told this means “subscriber information”, ie. the credit card that pays for the email account. But, why not other data that is not explicitly the content of communications? What about your full facebook profile? It is after all the equivalent of “subscriber data”? Why not your OK Cupid profile, with the answers to all questions about your kinky preferences? They are input into a form like other subscriber data, and there is no question OK Cupid does provide a communication service. What is the limit? By perpetuating the fiction that contents of communications are protected by warrant, all other items are now susceptible game for access as communications data.

An interesting detail is that the bill somewhat changes the definition of a telecommunication service to include any service facilitating messaging (communications), or involved in the in “creation, management, or storage of communications transmitted, or that may be transmitted”. I assume this includes relays like Tor, but also cloud storage services that may contain emails, webmail, facebook chat, on-line game chat and the like. Interestingly it also includes all their infrastructure providers, transit providers, storage providers, etc. If a notice comes their way, they will have to help intercept.

I have a rather enlightening chat with Yvo Desmedt after the Cambridge Security Protocol‘s Workshop, who was kind enough to give me an overview and insight into the group key agreement protocols of the ’90s. As part of an on-going conversation on secure chat, I am trying to understand the genealogy, and requirement, for key group agreements to be “contributory” — namely ensure all participants contribute to the final group key, even under malice. It seems that there is also a preference for symmetric schemes, where all participants perform the same operations.

Yvo’s classic Eurocrypt paper [BD94] is the basis of GOTR [LVH13], which manages to complicate it considerably. The original paper had a O(N) broadcasts cost, and was “peer-to-peer”, meaning that everyone just does the same thing. However it did not consider an active adversary, and was also not “contributory” meaning that an insider (active) adversary could force the key to anything they liked. Interestingly, Yvo points me to [BD96], which he thinks is superior to [BD94]. This paper really illustrates that there is no magic to group key agreement: a master key for the group is determined and then propagated using a key-sharing graph. This reduces the cost from O(N) broadcasts to just O(N) point to point messages — which to me seems optimal.

Now, the idea that schemes must be “contributory” (ie. no participant is special in determining the key — no one can force the key to be some specific value) emerged sometime in the late ’90s. The first reference I found to this property is [BW98], where the authors look at the round complexity of key agreement. However they state that “If the group key is generated and distributed by a central trusted party, then it is not necessary to discuss the communication complexity“. Then, they just launch into those schemes with no justification as to the reason centralized distribution may be a problem …

Katz and Young [KY03] also state that “(we exclude here centralized protocols in which a designated group manager is assumed; such asymmetric, non-contributory schemes place an unfairly high burden on one participant who is a single point of failure and who must also be trusted to properly generate keys)“. So it seems that the security issue contributory schemes try to mitigate is a flawed RNG. However this is a marginal threat — if the RNG is bad, than it may be likely the adversary can also corrupt other aspects of the platform to extract keys. In any case the flawed RNG threat can be dealt with by including some entropy from other participants assuming that they do not act in an adaptive malicious manner (if they do they can just leak the key to the adversary). I find it strange that KY03 argue that a single participant must not be burdened, when this results in proposed protocols that burden all participants to a great extent instead.

Around 2000 a number of works spring up that attempt to extend key agreement to dynamic membership setting, including [STW00] and [KPT00]. It is not at all clear to me whether those are in fact superior to running the key exchange multiple times, or even having a central party distributing keys.

Finally, Goldberg and others [GUGC09] propose extensions to OTR for a multi-user setting. These focus on deniability and signatures (and call a generic key exchange protocol) and a shared authentic transcript. This is a fine property, however I am a bit surprised the protocols are (a) so complex to establish ephemeral signatures and (b) so simple if they are to establish transcript consistency. My understanding is that they rely on the channel to offer consistent ordering, and then simply cryptographically ensure it was not tampered by an adversary — however I only read the paper obliquely.

Conclusion: It seems that a lot of the literature on group key exchange is based on the premise that the protocols need to be symmetric and contributory. Yet, I fail to see any justification beyond the fact that centralized schemes are simple and efficient, and no one could possibly write an academic paper about them. All schemes I have seem rely on the honest channel offering ordering, and being reliable. If that is not the case some of them detect it and hard fail (for example the integrity checks fail, with no hint that it is due to missing messages). This means that they assume some ordering happens on the outside of the crypto, which is dubious without some leader election. Few works have dealt with how you determine the group, which would either go the admin way or the voting way (can of worms).


[BD94] Mike Burmester, Yvo Desmedt: A Secure and Efficient Conference Key Distribution System (Extended Abstract). EUROCRYPT 1994: 275-286

[LVH13] Hong Liu, Eugene Y. Vasserman, Nicholas Hopper: Improved group off-the-record messaging. WPES 2013: 249-254

[BD96] Mike Burmester, Yvo Desmedt: Efficient and Secure Conference-Key Distribution. Security Protocols Workshop 1996: 119-129

[GUGC09] Ian Goldberg, Berkant Ustaoglu, Matthew Van Gundy, Hao Chen: Multi-party off-the-record messaging. ACM Conference on Computer and Communications Security 2009: 358-368

[KY03] Katz, Jonathan, and Moti Yung. “Scalable protocols for authenticated group key exchange.” Advances in cryptology-CRYPTO 2003. Springer Berlin Heidelberg, 2003. 110-125.

[BW98] Becker, Klaus, and Uta Wille. “Communication complexity of group key distribution.” Proceedings of the 5th ACM conference on Computer and communications security. ACM, 1998.

[STW00] Steiner, Michael, Gene Tsudik, and Michael Waidner. “Key agreement in dynamic peer groups.” Parallel and Distributed Systems, IEEE Transactions on 11.8 (2000): 769-780.

[KPT00] Kim, Yongdae, Adrian Perrig, and Gene Tsudik. “Simple and fault-tolerant key agreement for dynamic collaborative groups.” Proceedings of the 7th ACM conference on Computer and communications security. ACM, 2000.

I read today a brief missive about the Russian government’s intent to replace US sourced CPUs, the heart of a modern computer, with domestically produced ones. This is presumably a move to protect their critical infrastructure from hardware back doors, that are difficult to detect or eliminate. This is a good opportunity to share my thoughts on what is at stake in the current debate about the NSA’s and GCHQ’s pervasive surveillance infrastructure, including historic attempts to prevent the development and widespread use of security and cryptology technologies, and their current active compromise of international communications and end-users.

A lot has been written about the right to privacy of American citizens, and to some extent now British subjects. In my opinion, this important domestic issue lies on the insignificant end of the global impact of the Snowden revelations. It is also the only issue that may be resolved through better oversight and stronger privacy guarantees in national laws (with the caveats relating to the “liberal fallacy“).

What is truly at stake is whether a small number of technologically-advanced countries, including the US and the UK, but also others with a domestic technology industry, should be in a position to absolutely dominate the “cyber-space” of smaller nations. About 20 years ago, this may have been a minor concern as few things were critically dependent on IP or mobile networks. Today, most social and economic interactions are mediated through such technologies, or could economically benefit from being so, if only due to “security and privacy concerns”.

Read the rest of this entry »

London Crypto Festival

19 December 2013

I had the opportunity to speak as part of a panel at the London Crypto Festival on November 30th 2013. My main point was that we have not one, but many ways to protect privacy in on-line services. Therefore consumers and citizens should demand from their service and software providers strong protections for their privacy, and come to expect them. The examples I used are from what I know best, namely smart metering privacy for which we have proposed in the past very credible protocols for privacy friendly billing and statistics.

My Crypto Party Presentation can be found here.

I was very honored to be invited to Asiacrypt 2013 to present some of our work on privacy-friendly computations. It was an opportunity to consolidate a presentation that includes an overview of privacy-friendly billing and aggregation for smart metering. The slides of the presentation are available in Powerpoint 2012 format (and an older ppt format).

The key references providing more technical details on smart-metering privacy are:

The latest revelations about the NSA attacking some of the largest US cloud providers’ communications, are also accompanied by Cambridge Member of Parliament, Julian Huppert, call to revise the oversight of UK intelligence agencies. Similar calls were made in the US about better oversight of their security agencies. Julian concludes in this Guardian “Comment is Free” piece that:

“Who can read this, and how do we want to protect this? We need to agree the rules now, before we completely lose control.”

While better oversight is in itself a good thing, the over-reliance on “oversight” or privacy regulation, such as data protection regimes, is a typical example of what I call the “liberal fallacy”. The liberal fallacy is the belief that privacy is a complex social technical issue, and as a result it needs to be addressed first and foremost by better regulation, since it cannot be addressed by technical means alone.

The argument is extremely appealing for a number of reasons, and when put so reasonably I would be surprised if most privacy and security professionals, as well as policy makers and civil society advocates would not agree with it. After all, privacy in indeed both complex, and not merely a technical property. Privacy is not an absolute right, and regulation can “balance” the rights of the individual against the collective needs to revoke this right in certain circumstances. In a liberal democracy both the state and companies operate within the rule of the law, therefore proper regulation seems a light weight mechanism to solve the privacy problem.

The problem is that the “better regulation and oversight” argument is just non-sense in the context of the NSA and GCHQ spying allegations. The reason for thi, is that the national regulations do not affect the willingness, legality or ability of other states to conduct mass surveillance operations. Better German privacy legislation would not have protected the German head of state’s telephone conversation against US agencies. Similarly, better UK oversight of GCHQ will not extend any protections the US afford to US persons only to the UK population. For any national legislation offering you strong privacy guarantees and good oversight, there are about 205 other jurisdictions in which spying on you is not only legal, but highly ethical, patriotic, in the national interest, and rather well funded by tax payers.

National legislation works best in the context of territorial matters, where proximity and ability to harm is related to physical distance and location, and an army ensures territorial integrity. The internet is not like that: a US, Russian or Chinese router is as close to your UK web-site or switch as one in the UK. Benefiting from strong protections by UK entities, does nothing to protect you from other dangers that are just as close. It is shocking that US agencies were targeting cloud providers, but now we know they were not doing so only using their legal authority, but also just intercepting their communications. Even given perfect US oversight, better regulation will not prevent other countries doing the same — only better encryption systems can do that.

I am quite delighted that Julian Huppert does also mention that that placing back doors into security products makes everyone less safe, in line with the statement many UK security researchers made earlier this year. Yet, the focus on regulation is misplaced: against nation state level threats, sadly, only better security and privacy technologies can provide a credible defense for privacy.

Moving to UCL …

31 October 2013

After a good few years at Microsoft Research, I am now moving to University College London to take a position on Security and Privacy Engineering, at the Computer Science Department.

I am joining a fantastic team of researchers: Angela Sasse heads the group and is doing pioneering work on human aspects of security; Jens Groth is an expert on cryptography, and zero knowledge; Nicolas Courtois is a leading cryptanalyst, and has hit the news many times in the past by demonstrating vulnerabilities in deployed systems. Alongside myself, Emiliano De Cristofaro, who works on applied cryptography and privacy, and David Pym, who has a dual interest in formal methods and economics of security, are also joining the group.

One of my first non-research tasks at UCL is to teach the  Computer Security 1 course, which is a broad introduction to the basics of computer security. As a matter of principle, namely that the highest levels of quality of protection are achieved when computer security is discussed in public, I consider that the class to be a public event and open to anyone who would like to attend (subject to space restrictions). So if you are based in London, and would like access, just let me know.

I was sent yesterday articles about the new round of policy proposals related to Internet surveillance and traffic data monitoring (bbc, guardian). What is depressing, but also really revealing, is how similar both the sought powers, as well as the arguments for those powers are to previous attempts, just a few years ago.

In their essence the powers seek to extend the ability of law enforcement agencies to have access to all Internet traffic data, a power that they largely already have when it come to conventional telecommunications, or email services. What are traffic data? Everything that you have not typed as a message: the identity and time of your facebook chats, your facebook likes, the log of the visits to all web-pages, the clicks on on-line polls, the location data your phone sends to access on-line location services, the times and places you were in the same chat room with your friends, your on-line friends, etc. Basically you can think of blanket traffic data retention and access as having a policeman following you around 24h a day / 7 days a week, and making notes about where you have been, what you have looked at, who you are talking to, what you are doing, where you are sleeping (and with whom), everything you bought, every political and trade union meeting you went to, … — but not actually hearning any of the conversation or seeing what you wrote. Traffic data provide an X-ray of your whole life, and the policy suggests they should be available to law enforcement and the intelligence services without any judicial oversight (only political review or police oversight).

As has been discussed many times before recording all this information is very expensive, unlikely to ever be totally comprehensive, technically nearly infeasible, and prone to over-collection and abuse. In fact a focus on “more data” detracts attention from careful on-the-ground case work, and turns policing into a computer game you cannot win. A lot of data is already sitting on databases, and can be accessed by police — in fact police are under-equipped, under trained and under resourced to make use of those investigative resources, let alone more raw data. The focus on ubiquitous surveillance also increases concerns about privacy, and the ideas that everything communicated can be used against a person puts a brake on the adoption of information technologies like computational clouds.

On that basis the conservative and libdem opposition has in the past argued against those measures. They are now in government so one would think that this debate in not necessary. Yet, the internet surveillance plans are back on the table! What is going on here?

This time around, I personally think, that the campaign against those measures should also seek to dislodge those in the permanent and non-elected institutions of the state, that keep bringing back on the table this policy. I find it very hard to believe that these near carbon copy proposal naturally “re-emerge” despite the prolonged public debaes against them. It is much more likely that the policy is simply repackaged and presented anew to every new minister by career civil servants, under permanent pressures from the agencies.

I find it troubling that there is a non-elected set of institutions of the state that have as a permanent policy agenda to undermine civil liberties, despite consistently losing the public debate when specific powers are considered by Parliament. I would call this political subversion. What is even more troubling is that the architects of such policies are hiding under the cloak of secrecy, making it impossible for those outside government and the security services to really call them to account. I appreciate that operational necessities mean that some aspects of the security services’ work must remain secret. Yet, I cannot see why the branch of the security services that aims to directly affect public policy, through pushing a permanent agenda of ubiquitous surveillance, should enjoy that privilege.

Today Theresa May, our home secretary “insisted only data – times, dates, numbers and addresses – not content would be accessible” and that “ordinary people” had nothing to fear. Requesting such information about the communications between the home office, civil servants, and the members of the security services that advised them about this policy may change her opinion about how sensitive such information is. In fact, she may discover that providing such a map of the policy campaign and network of support, gives the opponents of the policy an undeniable advantage. I am very much looking forward to turning my automated social network analysis tools on their call graphs and email logs, and providing all results and intuitions to journalists.

ACM CCS 2011 just took place this week, so I decided to give a bit more insight into a few processes the program chairs used behind the scenes to manage what is the largest security conference to date. Vitaly Shmatikov (CCS11 Program co-chair) has already given a short introduction this year’s process: we received 429 full papers that we had to review with 54 PC members. While no hard target was set at the start of the process we expected to accept around the 60 papers that are now forming the program of CCS 2011. These are my views and opinions on the process, and they are not automatically shared by anyone else, including Vitaly.

Note: This post describes automated statistics we used to interpret scores of reviews to guide us in assigning more reviews or guiding discussion. All final acceptance decision were taken the old fashioned way through qualitative assesment of the reviews and discussion in the PC.

Read the rest of this entry »

Privacy-friendly Aggregation for the Smart-grid
Klaus Kursawe (Radboud Universiteit Nijmegen) and George Danezis and Markulf Kohlweiss (Microsoft Research)

Privacy in for smart electricity provision seems to be a rising topic, and this year there is a whole session on it at PETS 2011. The first paper (one which I am a coauthor) looks at the problem of gathering aggregate data from groups of smart meters, without allowing any third party to get the the individual measurements. This can be applied as a PET to solve real-world problems such as fraud detection, leakage detection, load estimates, demand response, weather prediction — all of which only require aggregate data (sometimes in real time), not individual measurements.

The key challenge to providing a private aggregation protocols are the specific constraints of smart meters. They are cheap devices, with modest resources, hardly any bandwidth, no ability to communicate, etc. Two specific protocols are presented: the first one allows to compare the sum of meter readings with a reference number (maybe measured from a feeder meter). This protocol allows for fancy proofs of correctness, but it slow in terms of computation and bandwidth (it requires public key operations for each reading). The second protocol is extremely fast and has no communication overhead. In both cases a pragmatic approach to the threat model is followed: we assume that the utilities will be honestly defining groups of meters and facilitating the key management protocol — for the second protocol there is no overhead of public key operations after the initial key setup.

The key highlight from this work is not as much its technical depth (tricks with DC networks and hash function that would not surprise any PETS regular). What is interesting is that the protocols were designed for a real industrial application and now fully integrated on real smart meters and their communication protocols in collaboration with our collaborators at Elster.

Plug-in privacy for Smart Metering billing
Marek Jawurek, Martin Johns, and Florian Kerschbaum (SAP Research)

This second paper looks at the problem of billing for fine-grained time of use tariffs — their energy consumption at different times costs a different rate per unit. This is a very important topic, as correct billing and time of use tariffs are a key driver of fine-grained data collection through smart meters — if we can do billing privately then maybe less personal information may be collected.

Technically the protocols proposed are based on the homomorphic properties of Pedersen commitments: readings are commitments, and you can use multiplication by a constant and addition to compute the bill, and (most importantly) prove that it is correct. The system model is that the meter outputs signed commitments of readings, a privacy component computes the bill and proofs of correctness, and those are sent to the supplier for verification (and printing the bills!).

This is the core of a nice solution for the basic billing case (which is likely to be the common one in smart grids). We have shown in related work that the protocol can be further improved to have zero communication overhead. Since it avoids expensive zero-knowledge proofs it is fast for its proofs and verification. It also provides the basic infrastructure to support further more expressive billing policies and general computations.


Get every new post delivered to your Inbox.