26 September 2014
I am today attending the first Internet Privacy Engineering Network (IPEN), where the issue of translating Data Protection principles into requirements has been raised a number of times. While this exercise needs to be repeated for each given service or application, it reminded me that I had drafted a number of generic Technical Requirements for Processing PII. These need to be reviewed and validated, but I hope they offer at least proof that the problem can be made tractable.
The paper “I Know Why You Went to the Clinic: Risks and Realization of HTTPS Traffic Analysis” is revisiting the vulnerability of HTTPS encryption to traffic analysis.
The authors note that most secure web connections access directly a specific website that is requested by a user (as opposed to the setting where a user is observed using Tor, where the site is not known). There are challenges in doing this: different websites are usually quite distinct, while many sub-pages in the same website may share a common layout that makes them hard to distinguish through encryption. Additional complications are added by cache, cookies, and the use of Flash. However, this setting may be easier than the Tor case, in that the adversary could realistically enumerate all pages on a website.
The paper chose 10 sites, including health, finance, video rental, and civil liberties. Traces are collected from encrypted requests and replies, and some simple pre-processing is done. In particular, the traffic volumes are collated in bursts and only their sizes are stored. This is done to add robustness to jitter in the traffic. Traces are then clustered using k-means and Gaussians are used to model each of the clusters. The use of the Gaussian distribution provides some further resilience to noise in the size of resources.
A machine learning approach is then followed to select which features distinguish pages: a logistic regression model is used to learn weights that best separate pages. A Hidden Markov Model is then used to track full traces of used navigation through an encrypted web-site.
To evaluate the approach traces were collected using virtual machines. This allows for the full state of a VM to be frozen, to reset the machine state perfectly between trace collection. Traces were collected in sessions where user state was meant to be preserved, and otherwise a fresh VM could be spun to clear the state. This way different conditions of cache on/off, cookies and browsing different sites were used for the collection. Interestingly the effect of cache being on systematically reduced the accuracy of the attack by 10%-20%.
Finally, the paper presents a defense against traffic analysis. It is based on padding the bursts of traffic to some threshold in order to confuse the feature extraction stage. Since many thresholds are possible, and the maximum is chosen, subject to a size “inflation” budget. Other defenses were also tried and compared, and there is a substantial reduction in the accuracy of this attack.
The paper “A Predictive Differentially-Private Mechanism for Mobility Traces” looks at sanitizing mobility traces within the paradigm of differential privacy.
The idea is that a user wishes to use a location-based service. However, a user also wishes to maintain some privacy, so they will somewhat distort the reported location to hide their exact location. Of course, there is a clear trade-off between the utility, namely the accuracy of the reported location, and the privacy that can be maintained. In the case of this work the utility is related with the accuracy of the reported location compared with the real location.
At the heart of the system lies a definition of privacy based on “geo-indistinguishability”. The insight is that the locations “close-by” need to be indistinguishable, while locations very far apart may be distinguished. This offers a higher degree of information leakage than traditional differential privacy, but stands a chance to offer some utility for a single user trace.
A previously proposed mechanism offers such privacy, through first perturbing the center point of the user location (using a 2D generalization of the Laplacian distribution) and the requesting information about a larger mechanism. Its privacy degrades in a predictable manner when multiple observations are seen by the adversary. However, the authors note that real-world traces are very correlated with each other. For example a user stays in a cafe for a while, or they follow a certain path on a motorway. This insight may be used to reduce the noise introduced by the mechanism.
First a straw man mechanism is proposed: a prediction function is defined that tries to predict the next position to report from the previous published position. If the prediction yields a “good enough” location, subject to some threshold, the old prediction is used. If not a new prediction is used, at the cost to the privacy budget used. However, this simple scheme breaks the definition of geo-indistinguishability.
The strawman mechanism can be strengthened by doing a private test for the accuracy of the prediction, which in itself consumes some amount of the privacy budget. This results in information not leaking from the private prediction test on the data, and yields a geo-indistringuishable mechanism.
To make the mechanism more easy to integrate into location-based services a privacy budget manager is also devised. The manager is provided with a certain target privacy level and utility, and will configure the parameters of the mechanism to offer good utility subject to the constraints.
The evaluation was gone on the GeoLife traces from MSR, that were processed to simulate queries to an LBS, through sub-sampling.
Interestingly, a plug-in for Firefox and Chrome is available that implements the approach.
The paper “Quantifying the Effect of Co-location Information on Location Privacy” presented by Alexandra-Mihaela Olteanu discusses the important problem of co-location on location privacy in mobile networks.
The work notes that co-location information is widespread: for example users tag a number of people on pictures in social networks; face recognition is getting better; and devices record the devices around them. Interestingly, the information an adversary may infer from this co-location information is not hidden by traditional location privacy mechanisms. In fact this is an instance of privacy technologies not doing a very good job at hiding information leaking from interactions between users. When correlations between user activity is observable by an adversary, the adversary may combine the information from both to increase the accuracy of their inferences. In fact the actions of one user may have serious consequences on the privacy of another (a co-target).
This work attempts to quantify the degree of privacy lost from such combined inferences. It uses the location privacy model by Shokri et al (S&P). Users locations and traces are modeled using a Markov model and the adversary observes co-locations. Tracking a single user is the traditional inferences of the hidden Markov model. With co-locations the attack is more complex since the constraints implied by co-locations need to be honored. This increases the information of the adversary, but also increases the computational complexity of the attack. As a result the authors also propose a heuristic attack, that ignores some of the information / constraints but tries to keep a certain set of observations consistent.
The evaluation was performed on the GeoLife (MSR Asia) dataset. Interestingly co-location information can be inferred from such raw traces, to simulate a number of scenarios. For example one may vary the fraction of co-location events observed by the adversary or the location privacy mechanism used. The result show, unsurprisingly, that the adversary observing co-locations has a significant impact on privacy. They also show that observing a target with low privacy settings may lead to the compromise of a co-target with high privacy settings.
This is a very nice work. As someone in the audience pointed out, some of the computational complexities may be tackled through using sampling based estimations of the posterior distribution that is otherwise intractable. This is probably a worthy space for follow-up research. Relaxing the Markov mobility assumption (which makes the posterior computations even more complex) is another avenue for future work.
(The first session of PETS2014 deal with privacy for mobile devices. )
The paper “Exploiting Delay Patterns for User IPs Identification in Cellular Networks” observes that a significant number of mobile operators (over 50% of the market in North America and over 30% in Europe) assign public and routable IP addresses to mobile devices. That opens the devices to denial of service attacks, resource depletion, etc. But how can an adversary find the IP address of a specific user? If the adversary can observe a large fraction of the network this may be easy. The paper shows that even a small entity — like a single user — may track a specific user’s IP.
The tracking attack uses specificities of how mobile devices use the cell network. It turns out that the network stack may be in different states: “Idle”, “cell dispatch” or “cell fetch”, to conserve battery. Most of the time a device is in “Idle”. The authors notice that the push notification of IM services allows for indirectly injecting delay patterns on a target device. To receive the notification the device goes to a high everge reception / transmission state and for a time window (of 10-15 sec) the latency to reach the device drops. An adversary may use this insight to identify the IP of a device associated with an IM identifier.
So the attack methodology goes as follows: the attacker send an IM message, lowering the latency of the target device. Then they scan a range of devices by IP to detect if the latency is compatible with the hypothesis it has received a push notification. If not, the IP may be excluded. The attack is repeated a number of times to gain increasing certainty about the exact address of the target. Graphs suggest that about 10-20 iterations the space of possible device IPs becomes significantly smaller. However, for best result the repeated probes should be spread quite a few minutes apart. However, there is still some confusion between the target device and devices that always transmit. Eliminating those further improves the accuracy of the attack.
Simple countermeasures involve either firewalling devices to make it difficult to reach them, or use IPv6 making the space of possible addresses to scan unfeasibly large.
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
[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.
[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.
21 June 2014
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”.
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:
- Alfredo Rial, George Danezis: Privacy-preserving smart metering. WPES 2011: 49-60
- Klaus Kursawe, George Danezis, Markulf Kohlweiss: Privacy-Friendly Aggregation for the Smart-Grid. PETS 2011: 175-191
- George Danezis, Markulf Kohlweiss, Alfredo Rial: Differentially Private Billing with Rebates. Information Hiding 2011: 148-162
- George Danezis, Benjamin Livshits: Towards ensuring client-side computational integrity. CCSW 2011: 125-130
- Andres Molina-Markham, George Danezis, Kevin Fu, Prashant J. Shenoy, David E. Irwin: Designing Privacy-Preserving Smart Meters with Low-Cost Microcontrollers. Financial Cryptography 2012: 239-253
- Gilles Barthe, George Danezis, Benjamin Grégoire, César Kunz, Santiago Zanella Béguelin: Verified Computational Differential Privacy with Applications to Smart Metering. CSF 2013: 287-301
- Cedric Fournet, Markulf Kohlweiss, George Danezis and Zhengqin Luo. ZQL: A Compiler for Privacy-Preserving Data Processing. USENIX Security Symposium, Washington DC, 2013.
- George Danezis, Cedric Fournet, Markulf Kohlweiss and Santiago Zanella-Beguelin. Smart Meter Aggregation via Secret-Sharing. ACM SEGS 2013: Smart Energy Grid Security Workshop, Berlin, 2013.
- Carmela Troncoso, George Danezis, Eleni Kosta, Josep Balasch, Bart Preneel: PriPAYD: Privacy-Friendly Pay-As-You-Drive Insurance. IEEE Trans. Dependable Sec. Comput. 8(5): 742-755 (2011)
- George Danezis, Markulf Kohlweiss, Benjamin Livshits, Alfredo Rial: Private Client-Side Profiling with Random Forests and Hidden Markov Models. Privacy Enhancing Technologies 2012: 18-37