An Efficient Data Aggregation Protocol Concentrated on Data Integrity in Wireless Sensor Networks

Abstract

Wireless sensor networks consist of a great number of sensor nodes with strictly limited computation capability, storage, communication resources, and battery power. Because they are deployed in remote and hostile environments and hence are vulnerable to physical attacks, sensor networks face many practical challenges. Data confidentiality, data integrity, source authentication, and availability are all major security concerns. In this paper, we focus on the very problem of preserving data integrity and propose an Efficient Integrity-Preserving Data Aggregation Protocol (EIPDAP) to guarantee the integrity of aggregation result through aggregation in sensor networks. In EIPDAP, base station can immediately verify the integrity of aggregation result after receiving the aggregation result and corresponding authentication information. However, to check integrity, most existing protocols need an additional phase which will consume a lot of energy and cause network delay. Compared with other related schemes, EIPDAP reduces the communication overhead per node to $O(\mathrm{\Delta })$ , where $\mathrm{\Delta }$ is the degree of the aggregation tree for the network. To the best of our knowledge, EIPDAP has the most optimal upper bound on solving the integrity-preserving data aggregation problem.

1. Introduction

Wireless sensor networks (WSNs) have many security-critical applications such as real-time traffic monitoring, wildfire tracking, or military surveillance. In a sensor network, thousands of low-cost sensor nodes collectively monitor an area within a certain range and report their own data to the base station which distributes a data query. However, this would incur high communication overhead which cannot be afforded by sensor nodes. Data aggregation [1, 2] mechanisms are proposed to reduce the power consumption. Data aggregation poses security threat; many secure data aggregation protocols [3, 4] have been emerging over these years, which prove to be secure and considerably improve the resource utilization.

Although data confidentiality could guarantee that legal parties obtain plain data without being leaked out to adversaries, it does not protect data from being altered [5–7]. In this paper, we focus on the problem of preserving data integrity through aggregation in sensor networks. Message authentication codes (MACs) are used in [8] to protect data integrity, while causing other problems, such as high communication overhead. In this paper, we present a provably secure sensor network integrity-preserving aggregation protocol based on the elliptic curve discrete logarithm problem for general networks with hierarchical aggregator topologies, assuming that adversaries are able to corrupt a (small) fraction of sensors. With the increasing of sensor node's computation capacity, public key cryptography, such as elliptic curve cryptosystems (ECC), is suitable for constrained environments such as WSN. In [9], authors propose secure data aggregation schemes using ECC to obtain data confidentiality and integrity in the data aggregation because of their smaller key size, faster computations, and reductions in processing power, storage space, and bandwidth. TinyECC is proposed by Liu and Ning [10] which provides ECC-based operations that can be flexibly configured and integrated into WSN applications.

An adversary can perform a variety of attacks. For example, a denial-of-service (DoS) attack can totally block the communication between sensor nodes and the base station. However, this attack is not concerned because it is detectable by the querier and solutions can be implemented to remedy this situation. In stealthy attack [4], the attacker's goal is to make the base station accept false aggregation results, which are significantly different from the true results determined by the measure values, while not being detected by the base station. Our goal is to prevent this kind of attack even when high-level aggregator is corrupted.

A number of protocols [11–13] have been proposed which focus on the problem that how can the base station obtain a good approximation of the aggregation result and how to obtain data integrity when a fraction of sensor nodes are compromised. One common sensor feature is the disproportionately high cost of transmitting information, as compared to performing local computation. For example, a Berkeley mote spends approximately the same amount of energy to compute 800 instructions as it does in sending a single bit of data. It thus becomes essential to reduce the number of bits forwarded by intermediate nodes, in order to extend the entire network's lifetime [14]. All the above schemes need to verify the integrity of aggregation result in an additional phase which consumes a lot of energy and causes network delay.

In this paper we propose EIPDAP, which can immediately verify the integrity of aggregation result after receiving the aggregation result and corresponding authentication information, hence significantly reducing energy consumption and communication delay which will be caused if the verification process is done through another query-and-forward phase.

The rest of the paper is organized as follows: in Section 2 we describe a survey of other approaches to integrity-preserving aggregation in sensor networks, in Section 3 more details about the problem we are trying to solve are discussed, in Section 4 we describe a new scheme that is, the centerpiece of our work, and in Section 5 the security properties and performance of our scheme are analyzed.

2. Related Work

There has been a number of works on preserving integrity in aggregation protocols for sensor networks. Many protocols have been proposed for the single-aggregator model [4, 13, 15]. But the aggregator in these schemes suffers from significantly high congestion and only reduces communications on the link between the aggregator and the base station. So this model is not scalable to large multihop sensor deployments.

Another significant work is introduced in [11]. The main idea of this approach is that each node sends its value, complement, and commitment up the aggregation tree and then a commitment would pass down the tree for a node to verify that if its value was added into the SUM aggregation and the complement of its data value was added into the COMPLEMENT aggregation. However, the scheme requires three phases. The delay aggregation strategy used in the second phase increases communication from $O(1)$ to $O(\log n)$ , computation from $O(1)$ to $O(q\log n)$ , where n is the number of nodes in the network and q is the number of forests in the commitment tree. The result-checking phase costs $O(\mathrm{\Delta }{\log }^{2}n)$ congestion. Frikken and Dougherty in [12] improves Chan's approach by reducing the maximum communication to $O(\mathrm{\Delta }\log n)$ .

A secure hop-by-hop data aggregation protocol SDAP for sensor networks is proposed in [13]. The authors believe that we should be more concerned about high-level nodes, since these nodes represent a large portion of the final result delivered to base station and there would be more catastrophic consequences if they are compromised. Hence, SDAP dynamically partitions the topology tree into multiple logical groups of similar sizes using a probabilistic approach, following the divide-and-conquer principle. In this way, fewer nodes are located under a high-level sensor node in a logical subtree resulting in reduced potential security threat by a compromised high-level node. SDAP introduces probability and attestation to the data result-checking; the communication required per node is $O(\log \hspace{0.17em}(n/n_g))$ . Because SDAP just let part nodes be attested, attestation algorithm cannot find all compromised nodes. By adding attestation paths can increase the detection probability, but it will increase communication cost.

Aggregate message authentication codes introduced by Katz and Lindell (CT-RSA 2008) [8] provided a new perspective of preserving integrity. In their construction, aggregating MAC simply computes the XOR of all the MACs into one value, the size of which is the same as an ordinary MAC. After receiving all the data and the final aggregate MAC, the base station uses secret keys shared with each node to compute a new aggregate MAC from these data and compares it with the received aggregate MAC. Although it remarkably reduces communication overhead we have seen in former protocols [11–13] and is easy to perform, it suffers from the “mix-and-match” attacks [16] in which the adversary can easily forge several types of aggregate combinations.

In [9], the authors proposed a new algorithm using homomorphic encryption and additive digital signatures to achieve confidentiality, integrity, and availability for in-network aggregation in WSN. However, the protocol cannot resist stealthy attack. We discuss concrete attack on the protocol due to Albath and Madria [9] in the appendix.

Besides, there have been several protocols designed for preserving the confidentiality of the aggregation results [17–19]. This issue is orthogonal to our work and is not considered in this paper.

3. Problem Model

This section contains the definitions of basic problems and includes discussion on the nodes' setup, the security infrastructure, and the attack model.

3.1. Network Assumptions

We assume a query-based sensor network with a large number of sensors and a powerful base station with transmission ranges covering the whole wireless sensor network can broadcast messages to all nodes directly. Before aggregation process, sensors will form a tree topology where base station locates at the root.

We further assume that the base station would broadcast an authenticated query before collecting data. If there is no aggregation tree, then an aggregation tree should be formed as the query has been sent to all nodes. Our protocol takes the structure of the aggregation tree as given. One method for constructing an aggregation tree is described in TaG [20].

Each node is sensing an integer value r that is in the range $(0,v]$ (we rule out “0” in defense of ${\theta }_i$ which we will explain later) for some application-based value v. The goal is to return the SUM result with two tags proving that the SUM result has not been forged (even in the presence of malicious nodes). Due to resource constrains, all readings need to be aggregated by aggregators while being transmitted over a multihop path.

3.2. Security Infrastructure

We assume that each node i has a unique identifier $s_i$ , private keys $r_i,l_i\in Z_p$ and shares a private key ${sk}_i$ and a private point ${\theta }_i\in$ cyclic elliptic group $E(Z_p)$ with base station. ECC domain parameters including the generator point $G\in E(Z_p)$ are preloaded in all nodes. In each node i we set two parameters ${\alpha }_i$ and ${\beta }_i$ which will be used later:

$$\begin{array}{cc}& {\alpha }_i=r_{i}G,\\ {\beta }_i=r_i{\alpha }_i.\end{array}$$

(1)

3.3. Attack Model and Security Goals

We consider a setting with a polynomially bounded adversary, which can physically access the sensors and read their interval values. The adversary is also restricted to corrupt a (small) fraction of nodes including the aggregators.

Once the adversary compromises a sensor node, it can obtain all the node's secret keys. An adversary can modify, forge, or discard messages or simply transmit false aggregate results, and its goal is to forge valid aggregate result to be accepted by the base station. The higher false aggregate result level is, more catastrophic consequence will be caused.

In this setting, we focus on stealthy attacks [4] where the attacker's goal is to make the base station accept false aggregate results while not being detected by base station. And our security goal is to prevent stealthy attacks. In particular, we want to guarantee that once the aggregate result has been accepted by the base station, it is indeed the real result aggregated by honest nodes.

Definition 1 (integrity-preserving aggregation algorithm).

An aggregation algorithm is integrity-preserving if, by tampering with the aggregation process, an adversary is unable to induce the base station to accept any forged aggregate result.

Since if a sensor node is compromised, the adversary can obtain all its confidential information (e.g., cryptographic keys) and send false data without being detected. In this paper we will focus on the situation where an aggregator is compromised and see whether it can forge a valid aggregate result.

In this paper, however, we do not address the denial-of-service attack where the adversary prevents the querier from getting any aggregation result at all; because nodes' not responding queries clearly indicate that something is wrong and solutions can be implemented to remedy this situation.

4. Our Work

In this section, we present a new approach, especially aiming to preserve integrity of the aggregation result. We first give an overview of this approach and then present the details.

4.1. Overview

The design of our algorithm is based on the elliptic curve discrete logarithm problem. The overall algorithm consists of three main phases: query dissemination, aggregation-commit, and result-checking.

In query dissemination phase, the base station broadcasts the query to the network. An aggregation tree, or a directed spanning tree over the network topology with the base station at the root, is formed as the query sent to all the nodes, if one is not already present in the network. Then the path-keys and edge-key for each node encrypted with the secret key shared between base station and node are sent to the corresponding node. Path-key and edge-key are calculated by the base station according to the network topology. We show the detail of the calculation of the path-key in Section 4.2.

In aggregation-commit phase, each sensor node collects raw data and computes two corresponding tags before sending them to their own parent node in the aggregation tree. After receiving all the messages from all child nodes, aggregator performs modulo addition operations over the three items and forwards the result to high-level aggregators until the base station.

In the result-checking phase, the base station verifies the integrity of the SUM aggregation with two aggregation tags. Compared with Chan's and Keith's approach, ours does not require any dissemination from top root node down to the leaf nodes which causes congestion $O(\mathrm{\Delta }{\log }^{2}n)$ in Chan's approach and $O(\mathrm{\Delta }\log n)$ in Keith's approach and energy cost in this phase.

4.2. The SUM Approach

4.2.1. Query Dissemination Phase

Before aggregation, the base station broadcasts an authenticated query to the network. The query request message contains a nonce N to prevent replay attack [1]. If there is no aggregation tree, an aggregation tree with the base station at the root will be formed as the query has been sent to all nodes. Then the tree information will be reported back to the base station. After the base station receives the tree information, it calculates the path-key for each node: for each aggregator or sensor node i, base station generates a key $\text{bs}$ , and calculates edge key according to one-way hash function F, where

$$\begin{array}{cc}& k_{i-j}=F_{\text{bs}}\left(s_i,s_j,N\right),\end{array}$$

(2)

and node i is the parent of node j. $s_i$ and $s_j$ are unique identifiers of node i and node j.

For each sensor node i, base station also calculates two path-keys $k_{i,1}$ and $k_{i,2}$ as follows:

$$\begin{array}{cc}& k_{i,1}=\frac{\theta }{k_{\text{path}}},\mathrm{\hspace{0.17em}\hspace{0.17em}}\end{array}$$

(3)

$$\begin{array}{cc}& k_{i,2}=\frac{l}{k_{\text{path}}},\end{array}$$

(4)

where θ is a point in $E(Z_p)$ , l is an integer and they are both chosen by base station to enable data aggregation and prevent stealthy/replay attacks.

If the path from base station to sensor node i is 1-2-3-i, then $k_{\text{path}}=k_{1\text{-}2}{k}_{2\text{-}3}{k}_{3\text{-}i}$ .

Finally the base station with transmission ranges covering the whole wireless sensor network directly broadcasts to node i the path-keys and edge-keys encrypted with the secret key ${sk}_i$ .

4.2.2. Data Aggregation Phase

In the query dissemination phase, each node has already identified their parents and the base station has the overall view of the aggregation tree.

In Figure 1, take paths BS-10-8-3-1 and BS-10-8-3-2, for instance, as sensor node, nodes 3, 1, and 2 each has a message, that is, to be passed to their parents. And the message has the following format:

$$\begin{array}{cc}& 〈x_i^{\#},{\alpha }_i^{\#},{\beta }_i^{\#}〉,\end{array}$$

(5)

where $x_i^{\#}$ is the SUM aggregation over all sensor nodes in the subtree; ${\alpha }_i^{\#}$ and ${{\beta }_i^{\#}}_{\mathrm{\hspace{0.17em}\hspace{0.17em}}}$ are the first and second tag, respectively.

Figure 1

Aggregation phase. The nodes 1, 2, 3, 4, 5, 6, and 7 are sensor nodes, and the nodes 8, 9, and 10 are aggregators while node 3 works as both sensor node and aggregator. Without losing generality, we assume that every intermediate node is able to sense raw data and performs aggregation like node 3 does.

For nodes 1 and 2:

$$\begin{array}{cc}& x_1^{\#}=x_1,\hspace{1em}\hspace{1em}{x}_2^{\#}=x_2,\\ {\alpha }_1^{\#}=x_1{k}_{\mathrm{1,1}}+x_1{\beta }_1{k}_{1,2},\\ {\alpha }_2^{\#}=x_2{k}_{2,1}+x_2{\beta }_2{k}_{2,2},\\ {\beta }_1^{\#}=x_1{\beta }_1+{\theta }_1,\hspace{1em}\hspace{1em}{\beta }_3^{\#}=x_3{\beta }_3+{\theta }_3.\end{array}$$

(6)

For aggregator/sensor node 3 with data $x_3$ , it first computes ${\alpha }_3^{\prime }$ and ${\beta }_3^{\prime }$ as a sensor node:

$$\begin{array}{cc}& x_3^{\prime }=x_3,\hspace{1em}\hspace{1em}{\alpha }_3^{\prime }=x_3{k}_{\mathrm{3,1}}+x_3{\beta }_3{k}_{\mathrm{3,2}},\\ {\beta }_3^{\prime }=x_3{\beta }_3+{\theta }_3.\end{array}$$

(7)

Then node 1 and 2 send their data and tags to node 3. After receiving all messages from its subtree, node 3 works as aggregator to perform aggregation:

$$\begin{array}{cc}& x_3^{\#}=x_1+x_2+x_3^{\prime },\\ {\alpha }_3^{\#}=k_{3\text{-}1}{\alpha }_1^{\#}+k_{3\text{-}2}{\alpha }_2^{\#}+{\alpha }_3^{\prime },\\ {\beta }_3^{\#}={\beta }_1^{\prime }+{\beta }_2^{\prime }+{\beta }_3^{\prime },\end{array}$$

(8)

and sends $〈x_3^{\#},{\alpha }_3^{\#},{\beta }_3^{\#}〉$ to node 8.

Aggregators 8 and 10 perform corresponding tasks:

$$\begin{array}{cc}& x_8^{\#}=x_3+x_4+x_5,\hspace{1em}\hspace{1em}{x}_{10}^{\#}=x_8^{\#}+x_9^{\#},\\ {\alpha }_8^{\#}=k_{8\text{-}3}{\alpha }_3^{\#}+k_{8\text{-}4}{\alpha }_4^{\#}+k_{8\text{-}5}{\alpha }_5^{\#},\\ {\alpha }_{10}^{\#}=k_{10\text{-}8}{\alpha }_8^{\#}+k_{10\text{-}9}{\alpha }_9^{\#},\\ {\beta }_8^{\#}={\beta }_3^{\#}+{\beta }_4^{\#}+{\beta }_5,\hspace{1em}\hspace{1em}{\beta }_{10}^{\#}={\beta }_8^{\#}+{\beta }_9^{\#},\end{array}$$

(9)

where node 8 sends $〈x_8^{\#},{\alpha }_8^{\#},{\beta }_8^{\#}〉$ to node 10, and node 10 sends $〈x_{10}^{\#},{\alpha }_{10}^{\#},{\beta }_{10}^{\#}〉$ to base station.

4.2.3. Result-Checking Phase

The purpose of result-checking phase is to enable base station to verify that the integrity of SUM $x_{10}^{\#}$ has not been violated. The verification is performed as follows.

Base station checks if

$$\begin{array}{cc}& {\beta }_{10}^{\#}-l^{-1}{k}_{\text{bs-}10}{\alpha }_8^{\#}=\sum _{}^{}{\theta }_i\mathrm{\hspace{0.17em}\hspace{0.17em}}-{\mathrm{\hspace{0.17em}\hspace{0.17em}}l}^{-1}\theta x_{10}^{\#},\end{array}$$

(10)

where $〈x_{10}^{\#},{\alpha }_{10}^{\#},{\beta }_{10}^{\#}〉$ is sent by node 10 to base station; θ, l, $k_{\text{bs-}10}$ , ${\theta }_i$ (i: from 1 to 7) are only known to base station and ${\mathrm{\hspace{0.17em}\hspace{0.17em}}l}^{-1}$ is the inverse of l modulo which is the order q of the elliptic curve group $E(Z_p)$ .

Since

$$\begin{array}{ll}& {\beta }_{10}^{\#}={\beta }_8^{\#}+{\beta }_9^{\#}\\ \phantom{{\beta }_{10}^{\#}}={\beta }_3^{\prime }+{\beta }_4^{\#}+{\beta }_5^{\#}+{\beta }_6^{\#}+{\beta }_7^{\#}\\ \phantom{{\beta }_{10}^{\#}}={\beta }_1^{\#}+{\beta }_2^{\#}+{\beta }_3^{\#}+{\beta }_4^{\#}+{\beta }_5^{\#}+{\beta }_6^{\#}+{\beta }_7^{\#}\\ \phantom{{\beta }_{10}^{\#}}\mathbf{=}{x}_1{\beta }_1+{\theta }_1+x_2{\beta }_2+{\theta }_2+x_3{\beta }_3+{\theta }_3+x_4{\beta }_4\\ \phantom{{\beta }_{10}^{\#}=}+{\theta }_4+x_5{\beta }_5+{\theta }_5+x_6{\beta }_6+{\theta }_6+x_7{\beta }_7+{\theta }_7\\ \phantom{{\beta }_{10}^{\#}}\mathbf{=}\left(x_1{\beta }_1+x_2{\beta }_2+x_3{\beta }_3+x_4{\beta }_4+x_5{\beta }_5+x_6{\beta }_6+x_7{\beta }_7\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \phantom{{\beta }_{10}^{\#}=}+\left({\theta }_1+{\theta }_2+{\theta }_3+{\theta }_4+{\theta }_5+{\theta }_6+{\theta }_7\right),\\ l^{-1}{k}_{\text{bs-}10}{\alpha }_{10}^{\#}\\ \hspace{1em}\hspace{1em}=l^{-1}{k}_{\text{bs-}10}\left(k_{10\text{-}8}{\alpha }_8^{\#}+k_{10\text{-}9}{\alpha }_9^{\#}\right)\\ \hspace{1em}\hspace{1em}=l^{-1}{k}_{\text{bs-}10}\\ \hspace{1em}\hspace{1em}\phantom{=}\times (k_{10\text{-}8}\left(k_{8\text{-}3}{\alpha }_3^{\#}+k_{8\text{-}4}{\alpha }_4^{\#}+k_{8\text{-}5}{\alpha }_5^{\#}\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \hspace{1em}\hspace{1em}\phantom{\times }\hspace{1em}+k_{10\text{-}9}\left(k_{9\text{-}6}{\alpha }_6^{\#}+k_{9\text{-}7}{\alpha }_7^{\#}\right))\\ =l^{-1}{k}_{\text{bs-}10}\\ \hspace{1em}\times (k_{10\text{-}8}(k_{8\text{-}3}\left({\alpha }_3^{\prime }+k_{3\text{-}1}{\alpha }_1^{\#}+k_{3\text{-}2}{\alpha }_2^{\#}\right)\\ \hspace{1em}\hspace{1em}\phantom{\times }\hspace{1em}\hspace{1em}\phantom{\times }+k_{8\text{-}4}{\alpha }_4^{\#}+k_{8\text{-}4}{\alpha }_5^{\#})\\ \hspace{1em}\hspace{1em}\phantom{\times }+k_{10\text{-}9}(k_{9\text{-}6}{\alpha }_6^{\#}+k_{9\text{-}7}{\alpha }_7^{\#}))\\ =l^{-1}{k}_{\text{bs-}10}{k}_{10\text{-}8}{k}_{8\text{-}3}\\ \hspace{1em}\times (k_{3\text{-}1}\left(\frac{l}{k_{\text{bs-}10}{k}_{10\text{-}8}{k}_{8\text{-}3}{k}_{3\text{-}1}}\right)x_1{\beta }_1\\ \hspace{1em}\hspace{1em}\hspace{0.5em}+k_{3\text{-}2}\left(\frac{l}{k_{\text{bs-}10}{k}_{10\text{-}8}{k}_{8\text{-}3}{k}_{3\text{-}2}}\right)x_2{\beta }_2\\ \hspace{1em}\hspace{1em}\hspace{0.5em}+\left(\frac{l}{k_{\text{bs-}10}{k}_{10\text{-}8}{k}_{8\text{-}3}}\right)x_3{\beta }_3)\\ \hspace{1em}+l^{-1}{k}_{\text{bs-}10}{k}_{10\text{-}8}\\ \hspace{1em}\times (k_{8\text{-}4}\left(\frac{l}{k_{\text{bs-}10}{k}_{10\text{-}8}{k}_{8\text{-}4}}\right)x_4{\beta }_4\\ \hspace{1em}\hspace{1em}\hspace{1em}+\mathrm{\hspace{0.17em}\hspace{0.17em}}{k}_{8\text{-}5}\left(\frac{l}{k_{\text{bs-}10}{k}_{10\text{-}8}{k}_{8\text{-}5}}\right)x_5{\beta }_5)\\ \hspace{1em}\hspace{1em}+l^{-1}{k}_{\text{bs-}10}{k}_{10\text{-}9}\\ \hspace{1em}\hspace{1em}\times (k_{9\text{-}6}\left(\frac{l}{k_{\text{bs-}10}{k}_{10\text{-}9}{k}_{9\text{-}6}}\right)x_6{\beta }_6\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}+\mathrm{\hspace{0.17em}\hspace{0.17em}}{k}_{9\text{-}7}\left(\frac{l}{k_{\text{bs-}10}{k}_{10\text{-}9}{k}_{9\text{-}7}}\right)x_7{\beta }_7)\\ =\left(x_1{\beta }_1+x_2{\beta }_2+x_3{\beta }_3+x_4{\beta }_4+x_5{\beta }_5+x_6{\beta }_6+x_7{\beta }_7\right)\\ \hspace{1em}\hspace{0.17em}\hspace{0.17em}+l^{-1}\theta \left(x_1+x_2+x_3+x_4+x_5+x_6+x_7\right).\end{array}$$

(11)

We can say that base station accepts the SUM aggregation $x_{10}^{\#}$ , or the two tags will only verify if all tags are generated by honest nodes and aggregated correctly along the path.

Again, note that $l^{-1}$ is the inverse of l modulo q which is the order of the elliptic curve group $E(Z_p)$ , and θ, l, $k_{\text{bs-}10}$ are only known to base station.

5. Analysis

This section discusses the security and congestion complexity of EIPDAP.

5.1. Overview

Once a node has been compromised, it is under the full control of the adversary which can record and inject messages as will. We also assume that the adversary can only corrupt a (small) fraction of nodes including the aggregators. Also, we do not concern denial-of-service attack. The following is the proof for security of EIPDAP.

Definition 2 (sensor node inconsistency).

Let $〈x_t^{\#},{\alpha }_t^{\#},{\beta }_t^{\#}〉$ be a message sent by sensor node t. There is an inconsistency at node t if either

• (1)

${\alpha }_t^{\#}\ne x_t{k}_{t,1}+x_t{\beta }_t{k}_{t,2}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{or}$

(2)

${\beta }_t^{\#}\ne x_t{\beta }_t+{\theta }_t$ .

Definition 3 (sensor node forgery).

An adversary eavesdropping on sensor node i successfully forges a new message $〈x_i^{*},{\alpha }_i^{*},{\beta }_i^{*}〉$ if

• (1)

$x_i^{*}\ne x_i^{\#}$ ,

(2)

${\alpha }_i^{*}=x_i^{*}{k}_{i,1}+x_i^{*}{\beta }_i{k}_{i,2}$ ,

(3)

${\beta }_i^{\#}=x_i^{*}{\beta }_i+{\theta }_i$ .

Since once a sensor node is compromised, the adversary can obtain all its confidential information (e.g., cryptographic keys) and send false data without being detected; however, we do not address this kind of forgery here.

Lemma 4.

Let the final SUM aggregation received by the base station be $x_{final}^{\#}$ , then $S_L+\mu \le x_{final}^{\#}\le S_L+\mu v$ where $S_L$ is the sum of the data values of all the legitimate nodes, and μ is the total number of corrupted nodes.

Proof .

As the conclusion is obvious here, so we do not prove in detail.

Lemma 5.

If elliptic curve discrete logarithm problem is hard, then it is not possible to forge a valid message as an honest sensor node for all eavesdropping probabilistic, polynomial adversaries.

Proof.

Let $〈x_i^{\#},{\alpha }_i^{\#},{\beta }_i^{\#}〉$ be an internal message sent by sensor node i to its parent.

Say adversary is eavesdropping on node i. In order to forge a valid message $〈x_i^{*},{\alpha }_i^{*},{\beta }_i^{*}〉$ for $x_i^{*}$ , A can easily compute a valid ${\alpha }_i^{*}=x_i^{*}{x}_i^{\#-1}{\alpha }_i^{\#}$ .

As ${\beta }_i^{\#}=x_i{\beta }_i+{\theta }_i=x_{i}yG$ for some integer y, a valid ${\beta }_i^{*}$ should be computed as

$$\begin{array}{ll}& {\beta }_i^{*}=x_i^{*}{\beta }_i+{\theta }_i=x_i^{*}{y}^{*}G\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \phantom{{\beta }_i^{*}}=x_i^{*}{y}^{*}{x}_i^{-1}{y}^{-1}{\beta }_i^{\#}G.\end{array}$$

(12)

Due to ${\theta }_i$ and ${\beta }_i$ , adversary cannot forge ${\beta }_i^{*}$ directly from $x_i^{*}{\beta }_i+{\theta }_i$ but to compute $x_i^{*}{y}^{*}{x}_i^{-1}{y}^{-1}{\beta }_i^{\#}G$ . A has $x_i^{*}$ , $x_i$ , ${\beta }_i^{\#}$ , and G; the factors it lack are y and $y^{*}$ .

Calculating y from ${\beta }_i^{\#}=x_{i}yG$ and $y^{*}$ from ${\beta }_i^{*}=x_i^{*}{y}^{*}G$ is ECDLP, which means calculating ${\beta }_i^{*}$ from $x_i^{*}{y}^{*}{x}_i^{-1}{y}^{-1}{\beta }_i^{\#}G$ is hard.

Another concern rises when adversary keeps eavesdropping on sensor node i and records the messages sent by i. Assume that adversary has

$$\begin{array}{cc}& \left\{〈x_{i\#j}^{\#},{\alpha }_{i\#j}^{\#}\mathrm{\hspace{0.17em}\hspace{0.17em}},{\beta }_{i\#j}^{\#}〉\mid j\in \left[1,n\right]\right\},\end{array}$$

(13)

where $〈x_{i\#j}^{\#},{\alpha }_{i\#j}^{\#},{\beta }_{i\#j}^{\#}〉$ represents the message $〈x_i^{\#},{\alpha }_i^{\#},{\beta }_i^{\#}〉$ , node i sends to parent in the jth query, and n is the number of queries. Note that in each query, every sensor node i chooses a new secret key $l_i$ .

For all $j\in [1,n]$ , adversary has

$$\begin{array}{cc}& {\beta }_{i\#j}^{\#}={\beta }_{i\#j}{x}_{i\#j}^{\#}+{\theta }_i.\end{array}$$

(14)

Because the number of variable is the number of equations plus one, so adversary cannot solve equations in (14) to obtain ${\beta }_{i\#j}$ or ${\theta }_i$ .

In conclusion, the probability of an adversary successfully forging a new message $〈x_i^{*},{\alpha }_i^{*},{\beta }_i^{*}〉$ when eavesdropping on sensor node i is negligible, completing the proof.

Definition 6 (aggregator inconsistency).

Let $〈x_t^{\#},{\alpha }_t^{\#},{\beta }_t^{\#}〉$ be an internal message aggregated by node t with two children u and v. Let $〈x_u^{\#},{\alpha }_u^{\#},{\beta }_u^{\#}〉$ and $〈x_v^{\#},{\alpha }_v^{\#},{\beta }_v^{\#}〉$ be two messages from u and v. There is an inconsistency at node t if

• (1)

$x_t^{\#}\ne x_t^{\prime }+x_u^{\#}+x_v^{\#}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{or}$

(2)

${\alpha }_t^{\#}\ne {\alpha }_t^{\prime }+{\alpha }_u^{\#}+{\alpha }_t^{\#}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{or}$

(3)

${\beta }_t^{\#}\ne {\beta }_u^{\prime }+{\beta }_u^{\#}+{\beta }_t^{\#}$ .

Definition 7 (compromised aggregator forgery).

An adversary which compromised a aggregator j successfully forges a new aggregate result $〈x_j^{*},{\alpha }_j^{*},{\beta }_j^{*}〉$ if

• (1)

$x_j^{*}\ne {x^{\#}}_j$ ,

(2)

${\alpha }_j^{*}={\alpha }_j^{\prime }+k_{j-1}{\alpha }_{j1}^{\#}+k_{j-2}{\alpha }_{j2}^{\#}+\cdots +k_{j-l}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\alpha }_{jl}^{\#}$ ( ${\alpha }_j^{\prime }=0$ if j does not sense data),

(3)

${\beta }_j^{\#}={\beta }_j^{\prime }+{\beta }_{j1}^{\#}+{\beta }_{j2}^{\#}+\cdots +{\beta }_{jl}^{\#}$ ( ${\beta }_j^{\prime }=0$ if j does not sense data), assuming aggregator j has l children  $j1,j2,\dots ,jl$ .

Lemma 8.

If elliptic curve discrete logarithm problem is hard, then it is not possible to forge a valid aggregate result for all probabilistic, polynomial adversaries even when a high-level aggregator is compromised.

Proof.

We assume that aggregator 10 has been compromised where an adversary is in complete control of node 10, obtaining all secret keys of node 10. Now an adversary attempts to forge SUM aggregation and two corresponding tags after eavesdropping several aggregations and records

$$\begin{array}{cc}& \left\{〈x_{10\#i}^{\#},{\alpha }_{10\#i}^{\#},{\beta }_{10\#i}^{\#}〉\mid i\in \left[1,n\right]\right\},\end{array}$$

(15)

where $〈x_{10\#i}^{\#},{\alpha }_{10\#i}^{\#},{\beta }_{10\#i}^{\#}〉$ represents the message $〈x_{10}^{\#},{\alpha }_{10}^{\#},{\beta }_{10}^{\#}〉$ , node 10 sends to base station in the $i\text{th}$ query, and n is the number of queries. Note that in each query, every sensor node j chooses a new secret key $l_j$ .

For all $i\in [1,n]$ , adversary has

$$\begin{array}{ll}& {\beta }_{10\#i}^{\#}=l^{-1}{k}_{\text{bs-}10}{\alpha }_{10\#i}^{\#}\\ \phantom{{\beta }_{10\#i}^{\#}}=\left({\theta }_1+{\theta }_2+{\theta }_3+{\theta }_4+{\theta }_5+{\theta }_6+{\theta }_7\right)\\ \phantom{\phantom{{{\beta }^{\#}}_{10\#i}}=\mathrm{\hspace{0.17em}\hspace{0.17em}}}-l^{-1}\theta x_{10\#i}^{\#}.\end{array}$$

(16)

Now adversary tries to forge a new message $〈x_{10}^{*},{\alpha }_{10}^{*},{\beta }_{10}^{*}〉$ which satisfies (14). Since node 10 is compromised, adversary has $x_8^{\#},x_9^{\#},x_{10}^{\#},k_{10\text{-}8},k_{10\text{-}9},{\alpha }_8^{\#},{\alpha }_9^{\#},{\beta }_8^{\#},{\beta }_9^{\#}$ in each query and the knowledge of the elliptic curve group $E(Z_p$ ).

Case 1. Intuitively, adversary tries to obtain l, $k_{\text{bs-}10}$ , θ, and ${\sum }_{}^{}{\theta }_i$ (i: from 1 to 7). However, this requires a powerful adversary which we do not concern here.

Case 2. Adversary tries to compute $l^{-1}\theta$ by multiplying $k_{i,1}$ (equals $\theta /k_{\text{path}}$ ) and the inverse of $k_{i,1}$ (equals $l/k_{\text{path}}$ ). However, all path-keys and temporal key are encrypted before forwarding to nodes, so adversary cannot compute $l^{-1}\theta$ when node 10 only works as an aggregator.

Case 3. Aggregator 10 also senses data. So adversary can compute $l^{-1}\theta$ as in Case 2 and $l^{-1}{k}_{\text{bs-}10}$ which is the inverse of $l/k_{\text{bs-}10}$ modulo q. Now adversary has

$$\begin{array}{ll}& {\beta }_{10}^{\#}-{\alpha }_{10}^{\#\#}\mathrm{\hspace{0.17em}\hspace{0.17em}}\\ \hspace{1em}={\theta }_1+{\theta }_2+{\theta }_3+{\theta }_4+{\theta }_5+{\theta }_6+{\theta }_7-x_{10}^{\#\#}\\ \hspace{1em}⟹{\beta }_{10}^{\#\#}\\ \hspace{1em}=y_1\left({\theta }_1+{\theta }_2+{\theta }_3+{\theta }_4+{\theta }_5+{\theta }_6+{\theta }_7\right)=y_{2}G\end{array}$$

(17)

for some integer $y_2$ . Similar to Lemma 4, since ${\sum }_{}^{}{\theta }_i$ (i: from 1 to 7) is kept secret from adversary and computing $y_2$ from ${\beta }_3^{\#\#}=y_{2}G$ is ECDLP, then ${\beta }_{10}^{\#\#}$ cannot be forged either.

In all cases, adversary can only forge a new message $〈x_{10}^{*},{\alpha }_{10}^{*},{\beta }_{10}^{*}〉$ with negligible probability, completing the proof.

Theorem 9.

EIPDAP is integrity-preserving.

Proof.

From Lemmas 5 and 8, we know that EIPDAP is secure against sensor node forgery in the presence of an eavesdropper and aggregator forgery when an aggregator is compromised. Thus, EIPDAP is integrity-preserving, completing the proof.

5.2. Congestion Complexity

The computational and memory costs are likely to be insignificant compared to communication [3, 14]. Higher computation surely causes more energy, but a Berkeley mote spends approximately the same amount of energy to compute 800 instructions as it does in sending a single bit of data [13, 20] in WSN.

Unlike general hard problems, there is no sub-exponential algorithm is known to solve the elliptic curve discrete logarithm problem (ECDLP), meaning that smaller parameters can be used in ECC than in other systems like RSA and DSA but with equivalent level of security. Because of their smaller key size, faster computations and reductions in processing power, storage space, and bandwidth, ECC is ideal for WSN. Although the use of elliptic curve cryptography incurs higher computational overhead than symmetric-key cryptography, our protocol is mainly designed to save energy.

In query dissemination phase, the base station collects aggregation tree information and broadcasts edge keys and path keys directly to the corresponding nodes. Collecting aggregation tree information costs each edge $O(1)$ congestion, and there is no congestion for sensor nodes and aggregators in broadcasting keys. In aggregation phase, each node forwards a message. The edge congestion in the aggregation tree is $O(1)$ . In result-checking phase, all operations are done in the base station, so there is no congestion in the aggregation tree. Congestion complexity comparisons with Chan's scheme, Keith's scheme, and SDAP are shown in Tables 1, 2, and 3.

Table 1

Edge congestion in the aggregation tree comparison, n is the number of the nodes, and $n_g$ is the group size.

	Query dissemination	Data aggregation	Result-checking
Chan's scheme	$O(1)$	$O(\log n$ )	$O({\log }^{2}n$ )
Keith's scheme	$O(1)$	$O(\log n$ )	$O(\log n$ )
SDAP	$O(1)$	$O(\mathrm{\Delta }\log \hspace{0.17em}(n/n_g)$ )	$O(\mathrm{\Delta }\log \hspace{0.17em}(n/n_g)$ )
EIPDAP	$O(1)$	$O($ 1)	0

Table 2

Node congestion in the aggregation tree comparison, Δ is the degree of the aggregation tree.

	Query dissemination	Data aggregation	Result-checking
Chan's scheme	$O(\mathrm{\Delta }$ )	$O(\mathrm{\Delta }\log n$ )	$O(\mathrm{\Delta }{\log }^{2}n$ )
Keith's scheme	$O(\mathrm{\Delta }$ )	$O(\mathrm{\Delta }\log n$ )	$O(\mathrm{\Delta }\log n$ )
SDAP	$O(\mathrm{\Delta }$ )	$O(\mathrm{\Delta }\log \hspace{0.17em}(n/n_g)$ )	$O(\mathrm{\Delta }\log \hspace{0.17em}(n/n_g)$ )
EIPDAP	$O(\mathrm{\Delta }$ )	$O(\mathrm{\Delta }$ )	0

Table 3

Aggregation tree congestion comparison.

	Query dissemination	Data aggregation	Result-checking
Chan's scheme	$O(n$ )	$O(n\log n$ )	$O(n\hspace{0.17em}{\log }^{2}n$ )
Keith's scheme	$O(n$ )	$O(n\log n$ )	$O(n\log n$ )
SDAP	$O(n$ )	$O(n$ )	$O(n\log n$ )
EIPDAP	$O(n$ )	$O(n$ )	0

By the comparison, we can conclude that EIPDAP has the minimum congestion and is much more energy efficient. Therefore it is much more suitable for power limited sensor networks.

6. Conclusion and Future Work

Protecting hierarchical data aggregation from losing integrity is a challenging problem in sensor networks. In this paper, we focus on the very problem of preserving data integrity and propose a novel approach to guarantee the integrity of aggregation result through aggregation in sensor networks. The main algorithm is based on performing modulo addition operation using ECC.

EIPDAP can immediately verify the integrity of aggregation result after receiving the aggregation result and corresponding authentication information, hence significantly reducing energy consumption and communication delay which will be caused if the verification phrase is done through another query-and-forward phase.

Compared with the other related schemes, our scheme reduces the communication required per node to $O(\mathrm{\Delta })$ , where $\mathrm{\Delta }$ is the degree of the aggregation tree for the network. To the best of our knowledge, our scheme has the most optimal upper bound on solving the integrity-preserving data aggregation problem. Based on the elliptic curve discrete logarithm problem, we prove that EIPDAP is integrity-preserving.

In the future, we will first further enrich EIPDAP in detail. Second, we will focus on the possibility of reducing the number of secret keys shared between sensor nodes and base station or the keys broadcast to all nodes. Third, based on the proposed algorithm, we may consider meeting other security requirements, like data confidentiality, source authentication, and availability.

We anticipate that our work provides new perspective on preserving integrity of hierarchical aggregation and encourages other researchers to consider this approach.