Preserving Privacy Against Side-Channel Leaks

The privacy preserving issue has attracted significant attentions in various domains, including census data publishing, data mining, location-based services, mobile and wireless networks, social networks, Web applications, smart grids, and so on. A rich literature exists on this topic, with various privacy properties, utility measures, and privacy-preserving solutions developed. However, one of the most challenging threats to privacy, side-channel leaks, has received limited attention. In a side-channel leak, adversaries attempt to steal sensitive information not only from obvious sources, such as published data or the content of network packets, but also through other, less obvious (side) channels, such as their knowledge about anonymization algorithms or the packet sizes (to be discussed in more details in the coming chapters). Side channel leaks can usually further complicate privacy preservation tasks to a significant extent, as we will demonstrate in this book. Various side-channel attacks have been studied in different domains, such as:

In this chapter, we provide a brief review of related work on privacy preservation and side-channel attacks especially in the three related domains: data publishing, Web applications, and smart metering.

In this chapter, we study the side channel leak of sensitive micro-data in which adversaries combine the published data with their knowledge about the generalization algorithms used to produce such data, in order to refine their mental image about the sensitive data. Today, data owners are usually expected to disclose micro-data for research, analysis, and various other purposes. In disclosing micro-data with sensitive attributes, the goal is usually twofold. First, the data utility of disclosed data should be preserved to a certain level for analysis purposes. Second, the private information contained in such data must be sufficiently hidden. Typically, a disclosure algorithm would first sort potential generalization functions into a predetermined order (e.g., with decreasing utility), and then discloses data using the first generalization function that satisfies the desired privacy property. Knowledge about how such disclosure algorithms work can usually render the algorithm unsafe, because adversaries may refine their guesses of the sensitive data by “simulating” the algorithms and comparing with the disclosed data. In this chapter, we show that an existing unsafe algorithm can be transformed into a large family of safe algorithms, namely, k-jump algorithms. We then prove that the data utility of different k-jump algorithms is generally incomparable, which is independent of utility measures and privacy models. Finally, we analyze the computational complexity of k-jump algorithms, and confirm the necessity of safe algorithms even when a secret choice is made among algorithms.

In this chapter, we present a formal Privacy-Preserving Traffic Padding (PPTP) model encompassing the privacy requirements, padding costs, and padding methods to prevent side-channel leaks due to unique patterns in packet sizes and directions of the encrypted traffic among components of the Web application. Web-based applications are gaining popularity as they require less client-side resources, and are easier to deliver and maintain. On the other hand, Web applications also pose new security and privacy challenges. In particular, recent research revealed that many high profile Web applications might cause sensitive user inputs to be leaked from encrypted traffic due to side-channel attacks exploiting unique patterns in packet sizes and timing. Moreover, existing solutions, such as random padding and packet-size rounding, were shown to incur prohibitive overhead while still failing to guarantee sufficient privacy protection. In this chapter, we first observe an interesting similarity between this privacy-preserving traffic padding (PPTP) issue and another well studied problem, privacy-preserving data publishing (PPDP). Based on such a similarity, we present a formal PPTP model encompassing the privacy requirements, padding costs, and padding methods. We then formulate PPTP problems under different application scenarios, analyze their complexity, and design efficient heuristic algorithms. Finally, we confirm the effectiveness and efficiency of our algorithms by comparing them to existing solutions through experiments using real-world Web applications.

The solutions in the previous chapter rely on the assumption that adversaries do not possess prior background knowledge about possible user inputs, which is a common limitation shared by most existing solutions. In this chapter, we discuss a random ceiling padding approach whose results are resistant to such adversarial knowledge. Recent studies show that a Web-based application may be inherently vulnerable to side-channel attacks which exploit unique packet sizes to identify sensitive user inputs from encrypted traffic. Existing solutions based on packet padding or packet-size rounding generally rely on the assumption that adversaries do not possess prior background knowledge about possible user inputs. In this chapter, we propose a novel random ceiling padding approach whose results are resistant to such adversarial knowledge. Specifically, the approach injects randomness into the process of forming padding groups, such that an adversary armed with background knowledge would still face sufficient uncertainty in estimating user inputs. We formally present a generic scheme and discuss two concrete instantiations. We then confirm the correctness and performance of our approach through both theoretic analysis and experiments with two real world applications.

In this chapter, we discuss how sensitive information about a household’s appliance status may be leaked from fine-grained smart meter readings. This is also an example of side channel leak because the readings are not supposed to serve as a channel for learning about individual appliances’ on/off status. While the features in smart grid, underpinned by the fine-grained usage information, provide significant benefits for both utility and customers, they also pose new security and privacy challenges. Existing solutions on privacy-preserving smart metering usually assume the readings to be sensitive and aim at protecting the readings through aggregation. In this chapter, we observe that the privacy issue in smart metering goes beyond the fine-grained readings themselves. That is, it may not be sufficient to simply focus on protecting such readings through aggregation or other techniques, without first understanding how such readings may lead to inferences of the truly sensitive information, that is, the appliance status. To address this issue, we present a formal model for privacy based on inferring appliance status from fine-grained meter readings.

The previous chapters have described in-depth studies of side channel leaks in different applications. Although those side channel leaks and their corresponding countermeasures all look very different, there in fact exists some commonality in terms of both challenges and solutions. For example, in previous chapters, we usually apply a similar idea for tacking side channel leaks, i.e., we divide objects into groups and then break the linkage inside each group by obfuscating any observable information about the objects, where objects are either published micro-data records, encrypted packets (sizes) in web applications, or readings reported by a smart meter. In this chapter, we design a general framework for preserving privacy against side-channel leaks. We show how different problems may fit into this framework by revisiting the three side channel leaks covered in previous chapters.