Robust Distributed Reprogramming Protocol of Wireless Sensor Networks for Healthcare Systems

Abstract

With the development of the wireless communication technologies, the wireless sensor networks (WSNs for short) are considered as one of the key research areas in healthcare systems. However, there is sometimes a need for removing bugs or adding new functionalities after WSNs are deployed. Wireless reprogramming is a process for propagating a new code image or relevant commands to sensor nodes in WSNs. In this paper, we propose a robust distributed reprogramming protocol of WSNs for healthcare systems, in which the security requirements are proved to be secure based on the elliptic curve discrete logarithm problem, such as existential unforgeability of signature for code image, authenticity of code image, freshness, and node compromised tolerance.

1. Introduction

Wireless sensor networks (WSNs for short) are spatially distributed sensors to gather physical or environmental information. The distributed sensors cooperate to pass their data through the network to a main location [1]. Recently, WSNs are considered as potential applications in providing high quality for healthcare services in recent years [2]. In healthcare applications, it may be necessary for removing bugs or adding new functionalities after WSNs are deployed. The reprogramming is an important operation function to propagate a new code image or relevant commands to sensor nodes in WSNs. However, an adversary may intercept or modify the transmitted messages in a WSN. Hence, it is critical to design a secure protocol for securely propagating a new code image or relevant commands to sensor nodes in WSNs.

In 2008, Das and Joshi [3] adopted orthogonality principle to design a protocol for dynamically updating sensor nodes in WSNs. A shared secret chosen by a base station has to be preinstalled on all sensor nodes before deploying them in a WSN, and the shared secret is used to validate a received advertisement message. After all sensor nodes accept a correct advertisement message, the sensor nodes dynamically update the shared secret. However, Zeng et al. [4] demonstrated that Das and Joshi's protocol is vulnerable to an impersonation attack. Assume that an adversary obtains the shared secret as he/she has compromised a sensor node. Then, the adversary can impersonate the base station to install his/her preferred program on sensor nodes by using the shared secret. Zeng et al. further proposed an improved scheme, but Wang et al. [5] pointed out that Zeng et al.'s proposed protocol [4] still suffers from an impersonation attack. In 2012, He et al. [6] showed that an adversary can impersonate a base station to install his/her preferred program on sensor nodes in a WSN, and further, the adversary can control the whole WSN. He et al. proposed two simple countermeasures which are formally validated by model checking. Soon afterwards, He et al. [7] proposed a secure and distributed reprogramming protocol (SDRP for short) based on an identity-based signature scheme in WSNs. In the SDRP, multiple authorized users are supported and each authorized user may have a different privilege for reprogramming sensor nodes. Subsequently, He et al. [8] and Yeo et al. [9] pointed out that there is a private key compromised problem in the SDRP, respectively. Furthermore, He et al. proposed an improved protocol based on Barreto et al.'s identity-based signature scheme [10]. In 2014, Shim [11] showed that He et al.'s improved protocol [8] is entirely broken and further proposed an improved protocol based on a pairing-free identity-based signature scheme. However, we find that Shim's proposed improved protocol is unworkable because the signature verification does not hold true. Among various secure protocols in WSNs [3–9, 11–24], most of the published reprogramming protocols [3, 6, 12–14, 16, 18, 20–23] are based on the centralized approach, which assumes the existence of a base station, and only the base station has the authority to reprogram sensor nodes. The centralized approach is not reliable in reality because of inefficiency, weak scalability, and vulnerability to potential attacks along the communication path [24].

Inspired from He et al.'s protocol [7], we adopt a short signature scheme to design a robust distributed reprogramming protocol of WNSs for healthcare applications. In the proposed protocol, each sensor node validates the received message by verifying the corresponding signature. The proposed protocol provides the following requirements.

• (1)

Existential unforgeability of signature for code image: any adversary cannot successfully forge a signature for any code image by mounting chosen-message attacks. That is, only authorized users can construct valid reprogramming packets.

(2)

Authenticity of code image: prior to the start of installation, a sensor node can verify the source of a code image.

(3)

Freshness: prior to the start of installation, a sensor node can confirm that the to-be-installed program is the newest version.

(4)

Node compromised tolerance: even though a sensor node is compromised, the compromised sensor node will not cause other uncompromised sensor nodes to violate authenticity of code image, integrity of code image, and freshness.

2. Overview of He et al.'s SDRP

In this section, we review the first proposed distributed reprogramming protocol (SDRP for short) proposed by He et al. [7]. The symbols used in the subsequent descriptions are listed as follows.

The Used Symbols and Descriptions

G: an additive group with an order q, where q is a large prime.

$G_T$ : a multiplicative group with an order q, where q is a large prime.

P: a generator in G.

q: a prime number.

$\widehat{e}$ : a bilinear mapping function, defined as $\widehat{e}:G\hspace{0.17em}\times \hspace{0.17em}G\to G_T$ .

s: a master key for a sensor network owner.

${\mathrm{P}\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}}$ : a public key for a sensor network owner, where $\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}}=s·P$ .

$H_1$ : a hash function defined as $H_{\mathrm{1}}:\{\mathrm{0,1}{\}}^{\ast }\to G$ .

$H_2$ : a hash function defined as $H_{\mathrm{2}}:\{\mathrm{0,1}{\}}^{\ast }\to Z_q^{\ast }$ .

$U_j$ : an authorized user.

$U{\mathrm{I}\mathrm{D}}_j$ : an identifier for $U_j$ , where $U{\mathrm{I}\mathrm{D}}_j\in \{\mathrm{0,1}{\}}^{\ast }$ .

${\text{Pri}}_j$ : a privilege for $U_j$ .

${\mathrm{P}\mathrm{K}}_j$ : a public key for $U_j$ , where ${\mathrm{P}\mathrm{K}}_j=H_{\mathrm{1}}(U{\mathrm{I}\mathrm{D}}_j\parallel {\text{Pri}}_j)\in G$ .

${\text{SK}}_j$ : a private key for $U_j$ , where ${\text{SK}}_j=s·{\mathrm{P}\mathrm{K}}_j$ .

He et al.'s SDRP includes System Initialization Phase, User Preprocessing Phase, and Sensor Node Verification Phase, and there are three kinds of roles: Sensor Network Owner (SNO for short), Authorized User (AU for short), and Sensor Node (SN for short). The detailed descriptions of each phase are given in the following.

System Initialization. In this phase, a sensor network owner SNO first generates his/her own private/public key pair s/ $\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}}$ and system parameters. Then, SNO assigns the privilege to each authorized user AU and generates the corresponding key pair for AU. The detailed descriptions of all steps are shown as follows.

• (1)

Choose an additive group G and a multiplicative group $G_T$ , where G and $G_T$ have the same order q.

(2)

Generate a generator P for G.

(3)

Choose a bilinear mapping function $\widehat{e}$ .

(4)

Randomly choose a master key $s\in Z_q^{\ast }$ .

(5)

Compute the corresponding public key $\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}}=s\hspace{0.17em}·\hspace{0.17em}P$ .

(6)

Choose two secure one-way hash functions $H_{\mathrm{1}}$ and $H_{\mathrm{2}}$ .

(7)

Load the system parameters $\{G,G_T,\widehat{e},q,P,\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}},H_{\mathrm{1}},H_{\mathrm{2}}\}$ into the sensor nodes before deploying a sensor network.

(8)

Assign the privilege ${\text{Pri}}_j$ to each AU $U_j$ with an identifier $U{\mathrm{I}\mathrm{D}}_j\in \{\mathrm{0,1}{\}}^{\ast }$ .

(9)

Generate the corresponding private/public key pair ${\text{SK}}_j/{\mathrm{P}\mathrm{K}}_j$ for each $U_j$ , where

$$\begin{array}{cc}& {\text{PK}}_j=H_{\mathrm{1}}\left(U{\text{ID}}_j\parallel {\text{Pri}}_j\right)\in G,\\ {\text{SK}}_j=s·{\text{PK}}_j.\end{array}$$

(1)

(10)

Send $\{{\text{PK}}_j,{\text{SK}}_j,{\text{Pri}}_j\}$ to each $U_j$ via a secure channel.

User Preprocessing. Suppose that an AU $U_j$ attempts to construct new reprogramming packets. He/she has to sign the packets with his/her private key and then sends them to the sensor nodes. The $U_j$ performs the following tasks.

• (1)

Partition the code image into l pages with the fixed size.

(2)

Split the page i into n packets with the fixed sized, where $\mathrm{1}\le i\le l$ . Note that the n packets are denoted as $Pk{t}_{i,\mathrm{1}},APk{t}_{i,\mathrm{2}},\dots ,Pk{t}_{i,n}$ .

(3)

Compute the hashing value for each packet, where the hash value for each packet in the page i is appended to the corresponding packet in the page $i-1$ .

(4)

Use the Merkle hash tree [25] for authenticating the hash values for the packets in page 1. The packets related to the Merkle hash tree are referred to in page 0. Suppose that m represent the root of the Merkle hash tree and the metadata about the code image.

(5)

Sign m to generate the signature ${\sigma }_j$ with his/her private key ${\text{SK}}_j$ :

$$\begin{array}{cc}& {\sigma }_j=H_{\mathrm{2}}\left(m\right)·{\text{SK}}_j.\end{array}$$

(2)

(6)

Send $\{U{\mathrm{I}\mathrm{D}}_j,{\text{Pri}}_j,m,{\sigma }_j\}$ to the target sensor nodes as the notification for the new code image.

Sensor Node Verification. Upon receiving $\{U{\mathrm{I}\mathrm{D}}_j,{\text{Pri}}_j,m,{\sigma }_j\}$ , each sensor node SN has to verify the received messages prior to the start of installation as follows.

• (1)

Verify the legality for the privilege ${\text{Pri}}_j$ and the received messages. If both of them are valid, SN continues to perform Step (2); otherwise, SN rejects the messages.

(2)

Verify the signature by using SNO's public key:

$$\begin{array}{cc}& \widehat{e}\left({\sigma }_j,P\right)=\widehat{e}\left(H_{\mathrm{2}}\left(m\right)·H_{\mathrm{1}}\left(U{\text{ID}}_j\parallel {\text{Pri}}_j\right),{\text{PK}}_{\text{SNO}}\right).\end{array}$$

(3)

If the above equality holds, ${\sigma }_j$ is the valid signature, and each SN accepts the received messages; otherwise, SN rejects the messages.

Security Analysis. According to He et al.'s [8] and Yeo et al.'s [9] analysis, He et al.'s SDRP [7] is vulnerable to a key compromise attack. Assume that $H_{\mathrm{2}}(m)$ and q are coprime. An adversary can compute the inverse $H_{\mathrm{2}}(m{)}^{-\mathrm{1}}$ and derive the private ${\text{SK}}_j=H_{\mathrm{2}}(m{)}^{-\mathrm{1}}·{\sigma }_j$ from the signature ${\sigma }_j$ , where ${\sigma }_j=H_{\mathrm{2}}(m)·{\text{SK}}_j$ . He et al.'s SDRP [7] cannot achieve the security requirements as they claimed.

3. Our Proposed Reprogramming Protocol for Healthcare Systems

The basic idea for our proposed protocol is that maintenance staffs responsible for maintaining different healthcare applications have to register with the sensor owner. Upon the successful registration, a staff receives a smart card storing authorized private key. Then, the staff can construct secure reprogramming packets to WSNs, whenever demanded. In order to assure the validity for the packets, the sensor nodes in WSNs have to verify the signature for the packets.

Our reprogramming protocol also consists of three phases: System Initialization, User Preprocessing, and Sensor Node Verification. The descriptions for System Initialization Phase in our proposed protocol are almost the same as ones in He et al.'s SDRP [7], but an extra one-way hash function $H_{\mathrm{3}}$ is used in our protocol, where $H_{\mathrm{3}}:G\to Z_q^{\ast }$ . The detailed descriptions for User Preprocessing and Sensor Node Verification are as follows.

User Preprocessing. Assume that an AU $U_j$ constructs the reprogramming packets, signs the packets with his/her own private key, and sends them to the sensor nodes. The steps from (1) to (4) for constructing reprogramming packets are the same as He et al.'s SDRP [7]. We also assume that the message m represents the root of the Merkle hash tree [25] and the metadata about the code image. Other steps for the $U_j$ are as follows.

• (5)

Choose a random number $r_j\in Z_q^{\ast }$ .

(6)

Compute $R_j=r_j·P$ .

(7)

Generate the nonce $n_j$ .

(8)

Compute $S_j$ by using his/her private key ${\text{SK}}_j$ :

$$\begin{array}{cc}& S_j=r_j^{-\mathrm{1}}\left(H_{\mathrm{1}}\left(m\parallel n_j\right)+H_{\mathrm{3}}\left(R_j\right)·{\text{SK}}_j\right).\end{array}$$

(4)

(9)

Send $\{U{\mathrm{I}\mathrm{D}}_j,{\text{Pri}}_j,m,R_j,S_j\}$ to the target sensor nodes as the notification for the new code image.

Sensor Node Verification. Upon receiving $\{U{\mathrm{I}\mathrm{D}}_j,{\text{Pri}}_j,m,R_j,S_j\}$ , each sensor node SN verifies the received messages to assure the validity prior to the start of installation. Detailed descriptions are as follows.

• (1)

Verify the legality for the privilege ${\text{Pri}}_j$ and the received message. If both of them are valid, SN continues to perform the next step; otherwise, SN rejects the received messages.

(2)

Verify the signature with the public key of the SNO and public system parameters:

$$\begin{array}{cc}& \widehat{e}\left(R_j,S_j\right)=\widehat{e}\left(P,H_{\mathrm{1}}\left(m\parallel n_j\right)\right)\widehat{e}{\left({\text{PK}}_{\text{SNO}},Q\right)}^{H_{\mathrm{3}}\left(R_j\right)},\end{array}$$

(5)

where $Q=H_{\mathrm{1}}(U{\text{ID}}_j\parallel {\text{Pri}}_j)$ . If the above equality holds, the received signature $(R_j,S_j)$ is valid, and each SN accepts the received messages; otherwise, each SN rejects the received messages.

Correctness. According to the verification equation, each sensor node can verify if the signature $(R_j,S_j)$ is valid:

$$\begin{array}{cc}& \widehat{e}\left(R_j,S_j\right)=\widehat{e}\left(r_j·P,r_j^{-\mathrm{1}}\left(H_{\mathrm{1}}\left(m\parallel n_j\right)+H_{\mathrm{3}}\left(R_j\right)·{\text{SK}}_j\right)\right)=\widehat{e}\left(P,r_j{r}_j^{-\mathrm{1}}\left(H_{\mathrm{1}}\left(m\parallel n_j\right)+H_{\mathrm{3}}\left(R_j\right)·{\text{SK}}_j\right)\right)=\widehat{e}\left(P,H_{\mathrm{1}}\left(m\parallel n_j\right)+H_{\mathrm{3}}\left(R_j\right)·{\text{SK}}_j\right)=\widehat{e}\left(P,H_{\mathrm{1}}\left(m\parallel n_j\right)\right)\widehat{e}\left(P,H_{\mathrm{3}}\left(R_j\right)·{\text{SK}}_j\right)=\widehat{e}\left(P,H_{\mathrm{1}}\left(m\parallel n_j\right)\right)\widehat{e}{\left(P,{\text{SK}}_j\right)}^{H_{\mathrm{3}}\left(R_j\right)}=\widehat{e}\left(P,H_{\mathrm{1}}\left(m\parallel n_j\right)\right)\widehat{e}{\left(P,s·{\text{PK}}_j\right)}^{H_{\mathrm{3}}\left(R_j\right)}=\widehat{e}\left(P,H_{\mathrm{1}}\left(m\parallel n_j\right)\right)\widehat{e}{\left(s·P,{\text{PK}}_j\right)}^{H_{\mathrm{3}}\left(R_j\right)}=\widehat{e}\left(P,H_{\mathrm{1}}\left(m\parallel n_j\right)\right)\widehat{e}{\left({\text{PK}}_{\text{SNO}},{\text{PK}}_j\right)}^{H_{\mathrm{3}}\left(R_j\right)}=\widehat{e}\left(P,H_{\mathrm{1}}\left(m\parallel n_j\right)\right)\widehat{e}{\left({\text{PK}}_{\text{SNO}},Q\right)}^{H_{\mathrm{3}}\left(R_j\right)}.\end{array}$$

(6)

Note that $Q=H_{\mathrm{1}}(U{\mathrm{I}\mathrm{D}}_j\parallel {\text{Pri}}_j)$ .

4. Security Analysis and Efficiency Comparison

Based on the elliptic curve discrete logarithm problem (ECDLP for short) [26, 27], the computation Diffie-Hellman problem (CDH for short) [28], the decisional Diffie-Hellman problem (DDH for short) [28], and the assumption of one-way hash function (OWHF for short) [29], we will analyze our reprogramming protocol and verify if it satisfies the security requirements: existential unforgeability of signature for code image, authenticity of code image, freshness, and node compromise tolerance. In addition, we will compare the computation costs in our proposed protocol with the ones in He et al.'s protocol [8]. The descriptions for the ECDLP, the CDH, the DDH, and the OWHF are as follows.

Definition 1 (elliptic curve discrete logarithm problem).

Let E be an elliptic curve defined over $GF(p)$ . Given $(P,Q)$ , determining an integer r such that $Q=r·P$ is computationally infeasible, where $P,Q\in E$ the order of E is a large prime q, and $\mathrm{0}\le r\le q-\mathrm{1}$ .

Definition 2 (computation Diffie-Hellman problem).

Given $(P$ , $a·P$ , $b·P)$ , computing $ab·P$ is computationally infeasible, where $P\in G_{\mathrm{1}}$ and $a,b\in Z_q^{\ast }$ .

Definition 3 (decisional Diffie-Hellman problem).

Given $(P$ , $a·P$ , $b·P$ , $c·P)$ , deciding if $c=ab$ is computationally infeasible, where $P\in G_{\mathrm{1}}$ and $a,b,c\in Z_q^{\ast }$ .

Definition 4 (one-way hash function).

Let H be a one-way hash function. The input for H is a message m with an arbitrary length, and the output for H is a hashing value $H(m)$ with a fixed length. There are three properties. (1) Given $H(m)$ , deriving m is computationally infeasible. (2) Finding two different messages m and $m^{\prime }$ such that $H(m)=H(m^{\prime })$ is computationally infeasible. (3) There exists an efficient algorithm to compute $H(m)$ .

We give a formal definition for existential unforgeability of a signature for a code image under a chosen-message attack, which is based on the established notion of existential unforgeability against chosen-message attacks [30, 31]. The game between an adversary $\mathcal{A}$ and a challenger $\mathcal{C}$ is defined as follows.

S :given a security parameter k, the challenger $\mathcal{C}$ first builds up a system parameter set π. Then, the $\mathcal{C}$ generates a private/public key pair $(s,\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}})$ and a private/public key pair $({\text{SK}}_j,{\mathrm{P}\mathrm{K}}_j)$ for each authorized user AU with an identifier $U_j$ . Finally, the adversary $\mathcal{A}$ is given π, $\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}}$ , and ${\mathrm{P}\mathrm{K}}_j$ , and the private keys ${\mathrm{S}\mathrm{K}}_j$ and s are kept secret by the $\mathcal{C}$ .

Q :the $\mathcal{A}$ can submit various queries to the $\mathcal{C}$ as follows.

• (1)

$H_1$ queries: to respond to the $\mathcal{A}$ 's queries, the $\mathcal{C}$ maintains a ${\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}}_{H_{\mathrm{1}}}$ .

(2)

$H_3$ queries: to respond to the $\mathcal{A}$ 's queries, the $\mathcal{C}$ maintains a ${\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}}_{H_{\mathrm{3}}}$ .

(3)

Signature for code image: for requesting a signature ${\sigma }_j$ for a code image, the $\mathcal{A}$ submits a message m and a public key ${\mathrm{P}\mathrm{K}}_j$ . Upon receiving the request, the $\mathcal{C}$ computes the signature under the public key ${\mathrm{P}\mathrm{K}}_j$ and returns the result to $\mathcal{A}$ .

F :

the $\mathcal{A}$ outputs a signature ${\sigma }^{\ast }$ for a target message $m^{\ast }$ and the $\mathcal{A}$ never submits the target message $m^{\ast }$ for requesting signature for code image. We can say that $\mathcal{A}$ wins the game if the signature ${\sigma }^{\ast }$ is valid for the target $m^{\ast }$ .

Definition 5.

The proposed protocol is said to achieve existential unforgeability of signature for code image against chosen-message attacks if successful probability for any polynomially bounded adversary will be negligible in the above game.

Theorem 6.

The proposed protocol achieves existential unforgeability of signature for code image against chosen-message attacks in the random oracle model, assuming the hardness of the CDH problem.

Proof.

Assume that a polynomial-time algorithm $\mathcal{A}$ can forge the signature under a chosen-message attack, and let $H_{\mathrm{1}}$ and $H_{\mathrm{3}}$ be random oracles in the simulation and the polynomial-time algorithm $\mathcal{A}$ can make $q_{H_{\mathrm{1}}}$ and $q_{H_{\mathrm{3}}}$ queries to $H_{\mathrm{1}}$ and $H_{\mathrm{3}}$ , respectively.

We will show how to construct a polynomial-time algorithm β that solves the CDH problem by using the $\mathcal{A}$ . Let $(P,a·P,b·P)$ be a random instance of the CDH problem. Computing $ab·P$ is the goal for the β.

In the S phase, the algorithm β builds up a system parameter set $\pi =\mathrm{\hspace{0.17em}\hspace{0.17em}}〈q,G,G_T,\widehat{e},P,H_{\mathrm{1}},H_{\mathrm{3}}〉$ , $I_{\mathrm{1}}=a·P$ , and $I_{\mathrm{2}}=b·P$ with a security parameter k. Then, the β generates a private/public key pair $(a,\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}})$ for the sensor network owner SNO and a private/public key pair $({\mathrm{S}\mathrm{K}}_j,{\mathrm{P}\mathrm{K}}_j)$ for an authorized user $U_j$ , where $\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}}=a·P$ and ${\mathrm{P}\mathrm{K}}_j=b·P$ . Finally, the $\mathcal{A}$ is given π, $\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}}$ , and ${\mathrm{P}\mathrm{K}}_j$ , and the private keys a and ${\mathrm{S}\mathrm{K}}_j$ are kept secret.

In the Q phase, the $\mathcal{A}$ adaptively submits the following queries.

• (1)

$H_1$ queries: the β has to maintain a ${\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}}_{H_{\mathrm{1}}}$ storing $(m,n_j,h_{\mathrm{1},j})$ for responding to the $\mathcal{A}$ 's queries. Upon receiving an $H_{\mathrm{1}}$ query for any subdocument m, the β has to check if there is the tuple $(m,n_j,h_{\mathrm{1},j})$ in ${\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}}_{H_{\mathrm{1}}}$ . If it exits in ${\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}}_{H_{\mathrm{1}}}$ , the β returns $h_{\mathrm{1},j}$ and terminates the step; otherwise, the β generates a random number $h_{\mathrm{1},j}\in Z_q^{\ast }$ , returns it, and stores $(m,n_j,h_{\mathrm{1},j})$ in ${\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}}_{H_{\mathrm{1}}}$ .

(2)

$H_3$ queries: the β has to maintain a ${\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}}_{H_{\mathrm{3}}}$ storing $(r_i,R_i,h_{\mathrm{3},i})$ for responding to the $\mathcal{A}$ 's queries. Upon receiving an $h_{\mathrm{3}}$ query for any $R_j$ , the β checks if there is $(r_j,R_j,h_{\mathrm{3},j})$ in ${\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}}_{H_{\mathrm{3}}}$ . If the tuple exists in ${\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}}_{H_{\mathrm{3}}}$ , the β returns $h_{\mathrm{3},j}$ and terminates the step; otherwise, the β generates a random number $h_{\mathrm{3},j}\in Z_q^{\ast }$ , returns it, and stores $(r_j,R_j,h_{\mathrm{3},j})$ in ${\mathrm{l}\mathrm{i}\mathrm{s}\mathrm{t}}_{H_{\mathrm{3}}}$ .

(3)

Signature for code image: the $\mathcal{A}$ submits m to the β and requests a signature ${\sigma }_j$ . Upon receiving the request, the β simulates an $H_{\mathrm{1}}$ oracle to get $(m,n_j,h_{\mathrm{1},j})$ and simulates an $H_{\mathrm{3}}$ oracle to get $(r_j,R_j,h_{\mathrm{3},j})$ . After the simulation, the β generates a random bit $b_j\in \{\mathrm{0,1}\}$ . If $b_j=\mathrm{1}$ , the β computes $S_i$ by using ${\mathrm{S}\mathrm{K}}_j$ and returns it; otherwise, the β randomly generates $S_i$ and returns it.

Let ${\varepsilon }^{\prime }$ be the probability that the $\mathcal{A}$ successfully outputs a signature ${\sigma }_j^{\ast }$ for a target $m_j^{\ast }$ . We can say that the successful probability ɛ that β solves the CDH problem is greater than ${\varepsilon }^{\prime }$ according to the above simulation. That is, the proposed protocol can achieve existential unforgeability of signature for code image.

Theorem 7.

The proposed protocol is said to achieve authenticity of code image if successful probability for any polynomially bounded adversary will be negligible.

Proof.

The source of a code image must be verified by a sensor node prior to the installation. Assume that an adversary attempts to construct reprogramming packets. Thus, a polynomial-time algorithm $\mathcal{A}$ can simulate the following attacks:

• (1)

Given a SNO's public key $(a,\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}})$ , an AU $U_j$ 's identifier $U{\mathrm{I}\mathrm{D}}_j\in \{\mathrm{0,1}{\}}^{\ast }$ , and the corresponding privilege ${\text{Pri}}_j$ , the polynomial-time algorithm $\mathcal{A}$ attempts to output the private key ${\mathrm{S}\mathrm{K}}_j$ for the $U_j$ . First of all, the $\mathcal{A}$ computes the $U_j$ 's public key ${\mathrm{P}\mathrm{K}}_j=H_{\mathrm{1}}(U{\mathrm{I}\mathrm{D}}_j\parallel {\text{Pri}}_j)$ . Then, the $\mathcal{A}$ derives SNO's private key a from the public key $\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}}=a·P$ . Finally, the $\mathcal{A}$ outputs the $U_j$ 's private key ${\mathrm{S}\mathrm{K}}_j=s·{\mathrm{P}\mathrm{K}}_j$ . However, the $\mathcal{A}$ cannot successfully output the $U_j$ 's private key ${\mathrm{S}\mathrm{K}}_j$ because the $\mathcal{A}$ cannot derive s from the public key $\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}}=a·P$ assuming the hardness of the ECDLP.

(2)

Given a signature $(R_j,S_j)$ , an AU $U_j$ 's identifier $U{\mathrm{I}\mathrm{D}}_j\in \{\mathrm{0,1}{\}}^{\ast }$ , and the corresponding privilege ${\mathrm{P}\mathrm{r}\mathrm{i}}_j$ , the polynomial-time algorithm $\mathcal{A}$ attempts to output the $U_j$ 's private key ${\mathrm{S}\mathrm{K}}_j$ from the signature. First of all, the $\mathcal{A}$ derives $r_j$ from $R_j$ . Then, the $\mathcal{A}$ computes $r_j·S_j=H_{\mathrm{1}}(m\parallel n_j)+H_{\mathrm{3}}(R_j)·{\mathrm{S}\mathrm{K}}_j$ . Finally, the $\mathcal{A}$ computes the inverse $H_{\mathrm{3}}(R_j{)}^{-\mathrm{1}}$ for $H_{\mathrm{3}}(R_j)$ and further outputs the private key ${\mathrm{S}\mathrm{K}}_j$ . However, the $\mathcal{A}$ cannot successfully output the $U_j$ 's private key ${\mathrm{S}\mathrm{K}}_j$ because the $\mathcal{A}$ cannot derive $r_j$ from $R_j$ due to the ECDLP.

According to the above analysis, the successful probability for the polynomial-time algorithm $\mathcal{A}$ cannot successfully be negligible. That is, any adversary cannot successfully impersonate the $U_j$ to construct new reprogramming packets in the proposed protocol.

Theorem 8.

The proposed protocol is said to achieve freshness if successful probability for any polynomially bounded adversary will be negligible.

Proof.

In the simulation, a polynomial-time algorithm $\mathcal{A}$ can obtain the same messages shown in Theorem 6. Given a nonce $n_j^{\ast }$ , the $\mathcal{A}$ cannot successfully output another nonce $n_j^{\prime }$ such that $H_{\mathrm{1}}(m\parallel n_j^{\ast })=H_{\mathrm{1}}(m\parallel n_j^{\prime })$ due to the assumption of the OWHF. That is, the nonce $n_j$ in the proposed protocol is used to ensure freshness.

Theorem 9.

The proposed protocol is said to achieve node compromise tolerance if successful probability for any polynomially bounded adversary will be negligible.

Proof.

Upon compromising a sensor node, a polynomial-time algorithm $\mathcal{A}$ can obtain the system parameters $\{G,G_T,\widehat{e},q,P,\mathrm{P}{\mathrm{K}}_{\mathrm{S}\mathrm{N}\mathrm{O}},H_{\mathrm{1}},H_{\mathrm{3}}\}$ . Further, the polynomial-time algorithm $\mathcal{A}$ can submit the same queries shown in Theorem 6. According to the above analysis, the $\mathcal{A}$ cannot cause an uncompromised node to violate the aforementioned security requirements.

In 2012, Gouvêa et al. [32] present a software implementation for an elliptic curve cryptosystem and a pairing-based cryptosystem for the MSP430 microcontroller family, which is used in wireless sensor nodes. That is, it is practical for the pairing computation using wireless sensor nodes. Further, we do not consider the time for computing a hashing value. The descriptions of symbols for different operations are shown as follows.

The Symbols for Different Operations.

$T_{\mathrm{e}\mathrm{x}\mathrm{e}}$ : the time for computing a modular exponential operation.

$T_{\mathrm{m}\mathrm{u}\mathrm{l}}$ : the time for computing a modular multiplication operation.

$T_{\mathrm{i}\mathrm{n}\mathrm{v}}$ : the time for computing an inverse operation.

$T_{\mathrm{e}\mathrm{c}\mathrm{m}}$ : the time for computing an elliptic curve multiplication operation.

$T_{\mathrm{e}\mathrm{c}\mathrm{a}}$ : the time for computing an elliptic curve addition operation.

$T_{\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}}$ : the time for computing a bilinear function.

In the following, we will compare the computation costs in our proposed protocol with ones in He et al.'s protocol [8]. From Table 1, we can see that our proposed protocol is slightly outperformed and achieves additional security requirements, which is lack of in He et al.'s protocol [8].

Table 1

Computation comparisons.

	He et al.'s protocol [8]	Our protocol
User preprocessing	$T_{\mathrm{e}\mathrm{x}\mathrm{e}}+T_{\mathrm{e}\mathrm{c}\mathrm{m}}$	$T_{\mathrm{i}\mathrm{n}\mathrm{v}}+\mathrm{3}{T}_{\mathrm{e}\mathrm{c}\mathrm{m}}$
Sensor node verification	$T_{\mathrm{e}\mathrm{x}\mathrm{e}}$ + $T_{\mathrm{m}\mathrm{u}\mathrm{l}}$ + $T_{\mathrm{e}\mathrm{c}\mathrm{m}}+T_{\mathrm{e}\mathrm{c}\mathrm{a}}$ + $T_{\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}}$	$T_{\mathrm{e}\mathrm{x}\mathrm{e}}+\mathrm{3}{T}_{\mathrm{p}\mathrm{a}\mathrm{i}\mathrm{r}\mathrm{i}\mathrm{n}\mathrm{g}}$

5. Conclusions

We propose a robust distributed reprogramming protocol providing existential unforgeability of signature for code image, authenticity of code image, freshness, and node compromised tolerance. The proposed protocol is applicable to healthcare systems, in which maintenance staffs responsible for maintaining different healthcare applications can construct secure reprogramming packets to WSNs, and the sensor nodes in WSNs can ensure the validity of the constructed packets. Considering the resource limitation of sensor node in WSNs, our future work is to design a lightweight distributed reprogramming protocol in WSNs.