Network Security

Università degli studi di Trento

Trento, Italy

Secure data aggregation

A report presented in partial fulfillment of the requirement for the course Network Security

September 2005

Christian Marzadro

Mirko Muro

Table of contents

• Introduction 1
• Attack model 1
• Data aggregation 2
• Cluster 3
• Hierarchical 4
• Key management and authentication 5
• Key symmetric vs asymmetric 5
• In cluster scheme 5
• In hierarchical scheme 8
• The mean 8
• The sum 14
• The minimum 15
• The median 17
• Conclusion 21
• Bibliography 29

1 Introduction

Sensor networks promise viable solutions to many monitoring problems. Real time traffic monitoring, wildfire tracking, wildlife monitoring, or building safety monitoring are the field where sensor networks are found. However, the practical deployment of sensor networks runs into many challenges imposed by real-world demands. Sensor networks deployed for mission-critical applications are potential targets for malicious attacks.

In fact, in many applications sensors are deployed in open environments, and hence are vulnerable to physical attacks, potentially compromising the sensor’s cryptographic keys. These sensors are not equipped with tamper-resistant hardware due to cost constraints. When the sensors are deployed for battlefield surveillance and forest fire monitoring, we would that the sensor network must not only report each relevant event promptly, but also reject false reports injected by attackers.

The primary security challenges for wireless sensor networks lie in addressing the conflict between limited resources (energy, computational overhead, memory, etc.) and security requirements. The sensors are usually simple, low powered devices that can transmit only within a small range (cluster) of their location, and so (usually) they cannot report the measurements directly to the distant home server.

Thus, a sensor-enhanced is often used as an intermediary between the base station and the sensor nodes. Particularly challenging for information aggregation in large sensor networks is the relationship between the resource constraints and security issues. Message aggregation can reduce communication overhead significantly, but message aggregation makes security more difficult.

Aggregation collects results from several sensors and calculates a smaller message that summarizes the important information from a group of sensors. For example, suppose the operator is interested in the average sensor reading for some value in the network. Given a query, it may be unnecessary and inefficient to return all raw data collected from each sensor, due to the communication constraints; instead, information should be processed and aggregated within the network and only processed and aggregated information is returned.

In the case where the sensor network is too large, it is possible to subdivide it in clusters and build a hierarchical aggregator to enable the aggregation, due to the capability to handle the whole network by a single aggregator.

In Section 2 we present threat models (like Stealthy Attack). In Section 3 and Section 4 we deal respectively with the data aggregation scheme and their key distribution. Whereupon, in Section 5, Section 6, Section 7 and Section 8 are listed a series of aggregation functions, respectively Mean, Sum, Minimum and Median function. Finally, Section 9 compares the papers and tries to explain the advantages and disadvantages for all the methods analysed.

2 Attack model

In sensor networks an attacker can perform a wide variety of attacks. We focus on stealthy attacks, where the attacker’s goal is to make the home server accept false aggregation results, which are significantly different from the true results determined by the measured values, while not being detected by the home server.

We consider a setting with a polynomially bounded attacker, which can corrupt some of the sensors as well as the aggregator. Actions of a corrupted device are totally determined by the adversary. Some sensors may be compromised and report wrong values that will affect the aggregation result. If a corrupted sensor simply reports a wrong value, it may be difficult to detect the misbehavior since such a detection may require application/semantics specific knowledge.

An attacker can manipulate, without limit, the result of the aggregation operation, gaining complete control over the computed aggregate. For instance, any protocol that computes the average, sum, minimum, or maximum function is insecure against malicious data, no matter how these functions are computed.

In a sensor network formed by a lot of nodes, the same stimulus being detected by multiple sensors is a necessary condition that enables cross-verification of reported events in the presence of compromised nodes. If there is a single node that is monitoring an area, it would be difficult to verify whether an event reported by this single node is real or forged. Only with multiple sensing nodes is it possible to cross-check the ground truth. Under the assumption that the data from the sensors can be trusted, it is assumed that within a cluster up to nodes could be compromised.

All articles assume that base stations remain trustworthy and unassailable. This assumption seems plausible: base stations are rarer and hence we can spend more on them, so it may be feasible to enclose them in high-quality tamper resistant enclosures or to place them in physically secure, access-controlled locations.

Another configuration is when we have all sensors that can reach the base station without using the sink model, and make jump sensor by sensor to forward the information to the base station. This is a good way to avoid the aggregation problem since the aggregation function is made by the powerful base station. But this scheme is not applicable for all wireless sensor networks, because the sensors deployed are usually cheap with low performance and sparse also far from the base station.

There are schemes that can compute the aggregation for these cases. But if they are bypassed by an attacker, it could make the base station accept false results. Thus, it is necessary to build a system that can allow the base station to verify the correctness of the data coming from the sensors. In this report we don’t consider the routing of information inside the network and how it can be implemented. The hypothesis is that the system is able to forward the information from the sensors to the base station, while there are a limited percentage of compromised nodes.

3 Data aggregation

Collecting results from several sensors and calculating a smaller message that summarizes the important information from a group of sensors is called aggregation. For example, suppose the operator is interested in the average sensor reading for some value in the network.

There are two types of aggregation:

• Out-Network Aggregation
• In-Network Aggregation

In the first case the base station performs an aggregation computation to obtain the ag-1 ). Thus, sensor nodes act as data sources, and the base station acts as aggregate (like in RAS¹ sink. It’s considered only a single base station and associated sensor nodes. It’s ignored the structure of the multi-hop network, assuming only that each sensor node has a separate link to the base station.

This abstracted architecture is depicted in Fig.1. The main problem of this configuration is that the aggregator forwards to the home server all data and authentication information from each sensor. Given all the data, the home server can verify authenticity of each data item, and answer all the statistical queries locally. However, the transmission is increased and consequently the power consumption of the whole sensor network.

1 “Resilient Aggregation in Sensor Networks” [8]

Fig. 1: An abstract sensor network architecture, with inessential underlying physical structures abstracted away. We have n sensor nodes (the small circles), each with a separate secure ith channel to a single trusted base station (the large solid square). The sensor sends measure-fx to the base station, and the base station uses the function to compute the aggregation measurement i = 9.y. n

In this picture, [8]

In the second case, In-Network Aggregation reduces the communication overhead, only processed and aggregated information is returned to the base station. It’s possible to subdivide the problem in two:

• Cluster
• Hierarchical

3.1 Cluster

The sensor networks allow each of the nodes to organize themselves into clusters once deployed. There are some nodes called aggregators or cluster-head that help aggregate information requested by a query. The aggregator collects the data from sensors and locally computes the aggregation result.

[3] proposes to send to the base station also the proof that² the sensor works correctly. Similar configurations are present in WBA, where a data fusion node receives data from a number of sensors, conducts data fusion, and then sends the result (decision) to the base station with the help of two witnesses.

If the Query is local, i.e. the detection of an event, we can consider the cluster like the number of sensors that reveal it. The Cluster-head described by SEF³ paper, is a normal sensor elected from the other sensors like it. The number of sensors that take part is low and so the number of data to compute, so the Cluster-Head doesn’t require high computation capacity.

2 “A Witness-Based Approach For Data Fusion Assurance In Wireless Sensor Networks” [9]

3 “Statistical En-route Filtering of injected False Data in Sensor Network, 2004” [4]

Fig. 2: An example sensor network. Suppose we want to monitor three areas of interest, the road, the river, and the munition plant, by deploying a cluster of sensor nodes (filled circles) in each area. The base station sends commands or queries to the sensor nodes, and receives reports from them. All the communications are relayed by some forwarding nodes (blank circles). [10]

3.2 Hierarchical

The hierarchic scheme is only presented by SAW⁴ where the sensor network is presented like a tree diagram. The leaves send the measure to their parent that computes the aggregation and sends the result to its parent. SAW says:

“Keep in mind, though, that the benefits of our protocol come when there are a large number of nodes arranged in a deep tree, so that many readings can be aggregated in a single message.”

In this paper, for simplicity, they assume only leaf nodes are collecting sensor readings, and intermediate nodes are just aggregating and forwarding data.

4 “Secure Aggregation for Wireless Sensor Networks” [5]

4 Key management and authentication

The configuration used by all protocols is that each node is initialized, before deployment, with a symmetric secret key. The base station establishes secrets with the ad hoc wireless nodes before deployment.

4.1 Key symmetric vs asymmetric

Security issues in mobile ad hoc networks are similar to those in sensor networks, but the defense mechanisms developed for ad hoc networks are not directly applicable to sensor networks. Ad hoc network security mechanisms are based on public key cryptography. Conventional public-key algorithms can help set up and manage keys in a network, but these algorithms are not feasible in a sensor network because of their communication and computation complexity.

Almost all protocols presented say that it is a risk to store the same key on every device to enable encryption or authentication, since an adversary who recovers the key from a single device will be able to control the entire network. Thus, it is necessary to use different keys for each sensor.

4.2 In cluster scheme

In SIA⁵, the authors assume that each sensor has a unique identifier and shares a separate secret cryptographic key with the base station and with the aggregator.

O(n)

The base station and the aggregator don’t need to store keys. In fact, they store KK and, and each sensor node stores the shared keys MAC (node simply a master key B A K B(node ID), where MAC is a secure message authentication code that is used ID) and MACK Ahere as a pseudo-random function.

To verify the authenticity of each sensor reading, each sensor shares a key with the aggregator. With the distribution of the keys it’s preventing only sensor impersonation, and not data coming from a damaged or corrupt sensor.

A new approach is that the authors of SIA call aggregate-commit-prove:

“aggregators help computing aggregation of sensor nodes’ raw data and reply to the home server with the aggregation result together with a commitment to the collection of data. The commitment to the input data ensures that the aggregator uses the data provided by the sensors, and that the statement to be verified by the home server about the correctness of computed results is meaningful.”

One efficient way of committing to the data is a Merkle hash-tree construction [6], [7]. This method is used also in the DAV⁶ algorithm. This is an efficient way to reduce the communication overhead between the network and the base station.

All the collected data are like the leaf nodes of the tree, and the aggregator then computes a binary hash tree starting from them. In other words, each internal node in the hash tree is computed as the hash value of the concatenation of the two child nodes. The root of the tree is called the ‘commitment’ [3] of the collected data.

Since the hash function in use is collision resistant, once the aggregator commits to the collected values, he cannot change any of the collected values. Fig.3 pag.6 gives an example of a Merkle hash tree.

5 “SIA: Secure Information Aggregation and verification protocol in Sensors Network” [3]

6 “A Secure Data aggregation and Verification Protocol for Sensor Networks” [2]

Fig. 3: Merkle hash tree used to commit to a set of values. The aggregator constructs the, ..., mm . To lower the size of verification Merkle hash tree over the sensor measurements 0 7 information, the aggregator first hashes the measurements with a cryptographic hash function, = ),H(mv assuming that the size of the hash is smaller than the size of the data. To e.g., 3,0 0 construct the Merkle hash tree, each internal value of the Merkle hash tree is derived from its = || ).H(v vv The Merkle hash tree is a commitment to all two child nodes: i,j i+1,2j i+1,2j+1 v , a verifier can authenticate any leaf value the leaf nodes, and given the authentic root node 0,0 by verifying that the leaf value is used to derive the root node.

For example, to authenticate m v , v , v mm , the aggregator sends along with , and is authentic the measurement 5 5 3,4 2,3 1,0 5 = || || )) || )).H(v H(H(v H(m vv [3] if the following equality holds: 0,0 1,0 3,4 5 2,3

A different point of view is to use an asymmetric system with the private key subdivided and another key for the sensor. In DAV [2] article they propose a protocol named Cluster Key Establishment that generates a secret cluster key for each cluster. Each sensor node only has a part of the secret cluster key and the cluster key is hidden from each node. The public key for the secret cluster key is known to all nodes within the cluster as well as the base station. Since the secret cluster key is hidden from all nodes, attacks on the cluster key are not possible.

In WBA, in order to prove the validity of the fusion result, the fusion node has to provide proofs from several witnesses. A witness is one who also conducts data fusion like a data fusion node.

“They assume that the data fusion node and witness nodes share a secret key with F the base station. Let denote the data fusion node. Assume that we have chosen 7, ..., w k , ..., km w , and represent the MAC keys they share with witnesses, 1 1m m the base station. To reduce energy consumption in this scheme, they analyzed and computed the minimum length needed for the Message Authentication Code (MAC) to achieve a predefined level of security.”

This configuration type is good because the number of bits used for MACs does not increase linear