# Robust Distributed Reprogramming Protocol of Wireless Sensor

Authors: Kuo-Yu Tsai
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 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.
e
^: a bilinear mapping function, defined as e^:G×G→GT.
s: a master key for a sensor network owner.
P
K
S
N
O: a public key for a sensor network owner, where PKSNO=s·P.
H
1: a hash function defined as H1:{0,1}∗→G.
H
2: a hash function defined as H2:{0,1}∗→Zq∗.
U
j: an authorized user.
U
I
D
j: an identifier for Uj, where UIDj∈{0,1}∗.
Pri
j: a privilege for Uj.
P
K
j: a public key for Uj, where PKj=H1(UIDj∥Prij)∈G.
SK
j: a private key for Uj, where SKj=s·PKj.He et al.’s SDRP includesSystem Initialization Phase,User Preprocessing Phase, andSensor Node Verification Phase, and there are three kinds of roles:Sensor Network Owner (SNO for short),Authorized User (AU for short), andSensor 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/PKSNO 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 groupG and a multiplicative group GT, where G and GT have the same order q.(2)
Generate a generatorP for G.(3)
Choose a bilinear mapping functione^.(4)
Randomly choose a master keys∈Zq∗.(5)
Compute the corresponding public keyPKSNO=s·P.(6)
Choose two secure one-way hash functionsH1 and H2.(7)
Load the system parameters{G,GT,e^,q,P,PKSNO,H1,H2} into the sensor nodes before deploying a sensor network.(8)
Assign the privilegePrij to each AU Uj with an identifier UIDj∈{0,1}∗.(9)
Generate the corresponding private/public key pairSKj/PKj for each Uj, where (1)PKj=H1UIDj∥Prij∈G,SKj=s·PKj.(10)
Send{PKj,SKj,Prij} to each Uj via a secure channel.User Preprocessing. Suppose that an AU Uj 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 Uj performs the following tasks.(1)
Partition the code image intol pages with the fixed size.(2)
Split the pagei into n packets with the fixed sized, where 1≤i≤l. Note that the n packets are denoted as Pkti,1,APkti,2,…,Pkti,n.(3)
Compute the hashing value for each packet, where the hash value for each packet in the pagei 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)
Signm to generate the signature σj with his/her private key SKj: (2)σj=H2m·SKj.(6)
Send{UIDj,Prij,m,σj} to the target sensor nodes as the notification for the new code image.Sensor Node Verification. Upon receiving {UIDj,Prij,m,σ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 privilegePrij 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:(3)e^σj,P=e^H2m·H1UIDj∥Prij,PKSNO. If the above equality holds, σ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 H2(m) and q are coprime. An adversary can compute the inverse H2(m)-1 and derive the private SKj=H2(m)-1·σj from the signature σj, where σj=H2(m)·SKj. 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, andSensor Node Verification. The descriptions forSystem 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 H3 is used in our protocol, where H3:G→Zq∗. The detailed descriptions forUser Preprocessing andSensor Node Verification are as follows.User Preprocessing. Assume that an AU Uj 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 Uj are as follows.(5)
Choose a random numberrj∈Zq∗.(6)
ComputeRj=rj·P.(7)
Generate the noncenj.(8)
ComputeSj by using his/her private key SKj: (4)Sj=rj-1H1m∥nj+H3Rj·SKj.(9)
Send{UIDj,Prij,m,Rj,Sj} to the target sensor nodes as the notification for the new code image.Sensor Node Verification. Upon receiving {UIDj,Prij,m,Rj,Sj}, 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 privilegePrij 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:(5)e^Rj,Sj=e^P,H1m∥nje^PKSNO,QH3Rj, where Q=H1(UIDj∥Prij). If the above equality holds, the received signature (Rj,Sj) 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 (Rj,Sj) is valid:(6)e^Rj,Sj=e^rj·P,rj-1H1m∥nj+H3Rj·SKj=e^P,rjrj-1H1m∥nj+H3Rj·SKj=e^P,H1m∥nj+H3Rj·SKj=e^P,H1m∥nje^P,H3Rj·SKj=e^P,H1m∥nje^P,SKjH3Rj=e^P,H1m∥nje^P,s·PKjH3Rj=e^P,H1m∥nje^s·P,PKjH3Rj=e^P,H1m∥nje^PKSNO,PKjH3Rj=e^P,H1m∥nje^PKSNO,QH3Rj. Note that Q=H1(UIDj∥Prij).


## 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, andnode 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).
LetE 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∈E the order of E is a large prime q, and 0≤r≤q-1.Definition 2 (computation Diffie-Hellman problem).
Given(P, a·P, b·P), computing ab·P is computationally infeasible, where P∈G1 and a,b∈Zq∗.Definition 3 (decisional Diffie-Hellman problem).
Given(P, a·P, b·P, c·P), deciding if c=ab is computationally infeasible, where P∈G1 and a,b,c∈Zq∗.Definition 4 (one-way hash function).
LetH 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′ such that H(m)=H(m′) 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 A and a challenger C is defined as follows.S:
given a security parameterk, the challenger C first builds up a system parameter set π. Then, the C generates a private/public key pair (s,PKSNO) and a private/public key pair (SKj,PKj) for each authorized user AU with an identifier Uj. Finally, the adversary A is given π, PKSNO, and PKj, and the private keys SKj and s are kept secret by the C.Q:
theA can submit various queries to the C as follows.
(1)
H1queries: to respond to the A’s queries, the C maintains a listH1.(2)
H3queries: to respond to the A’s queries, the C maintains a listH3.(3)
Signature for code image: for requesting a signature σj for a code image, the A submits a message m and a public key PKj. Upon receiving the request, the C computes the signature under the public key PKj and returns the result to A.F:
theA outputs a signature σ∗ for a target message m∗ and the A never submits the target message m∗ for requestingsignature for code image. We can say that A wins the game if the signature σ∗ is valid for the target m∗.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 algorithmA can forge the signature under a chosen-message attack, and let H1 and H3 be random oracles in the simulation and the polynomial-time algorithm A can make qH1 and qH3 queries to H1 and H3, respectively.
We will show how to construct a polynomial-time algorithmβ that solves the CDH problem by using the A. Let (P,a·P,b·P) be a random instance of the CDH problem. Computing ab·P is the goal for the β.
In theS phase, the algorithm β builds up a system parameter set π=q,G,GT,e^,P,H1,H3, I1=a·P, and I2=b·P with a security parameter k. Then, the β generates a private/public key pair (a,PKSNO) for the sensor network owner SNO and a private/public key pair (SKj,PKj) for an authorized user Uj, where PKSNO=a·P and PKj=b·P. Finally, the A is given π, PKSNO, and PKj, and the private keys a and SKj are kept secret.
In theQ phase, the A adaptively submits the following queries. (1)
H1queries: the β has to maintain a listH1 storing (m,nj,h1,j) for responding to the A’s queries. Upon receiving an H1query for any subdocument m, the β has to check if there is the tuple (m,nj,h1,j) in listH1. If it exits in listH1, the β returns h1,j and terminates the step; otherwise, the β generates a random number h1,j∈Zq∗, returns it, and stores (m,nj,h1,j) in listH1.(2)
H3queries: the β has to maintain a listH3 storing (ri,Ri,h3,i) for responding to the A’s queries. Upon receiving an h3 query for any Rj, the β checks if there is (rj,Rj,h3,j) in listH3. If the tuple exists in listH3, the β returns h3,j and terminates the step; otherwise, the β generates a random number h3,j∈Zq∗, returns it, and stores (rj,Rj,h3,j) in listH3.(3)
Signature for code image: the A submits m to the β and requests a signature σj. Upon receiving the request, the β simulates an H1 oracle to get (m,nj,h1,j) and simulates an H3 oracle to get (rj,Rj,h3,j). After the simulation, the β generates a random bit bj∈{0,1}. If bj=1, the β computes Si by using SKj and returns it; otherwise, the β randomly generates Si and returns it.Let ɛ′ be the probability that the A successfully outputs a signature σj∗ for a target mj∗. We can say that the successful probability ɛ that β solves the CDH problem is greater than ɛ′ according to the above simulation. That is, the proposed protocol can achieveexistential 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 algorithmA can simulate the following attacks: (1)
Given a SNO’s public key(a,PKSNO), an AU Uj’s identifier UIDj∈{0,1}∗, and the corresponding privilege Prij, the polynomial-time algorithm A attempts to output the private key SKj for the Uj. First of all, the A computes the Uj’s public key PKj=H1(UIDj∥Prij). Then, the A derives SNO’s private key a from the public key PKSNO=a·P. Finally, the A outputs the Uj’s private key SKj=s·PKj. However, the A cannot successfully output the Uj’s private key SKj because the A cannot derive s from the public key PKSNO=a·P assuming the hardness of the ECDLP.(2)
Given a signature(Rj,Sj), an AU Uj’s identifier UIDj∈{0,1}∗, and the corresponding privilege Prij, the polynomial-time algorithm A attempts to output the Uj’s private key SKj from the signature. First of all, the A derives rj from Rj. Then, the A computes rj·Sj=H1(m∥nj)+H3(Rj)·SKj. Finally, the A computes the inverse H3(Rj)-1 for H3(Rj) and further outputs the private key SKj. However, the A cannot successfully output the Uj’s private key SKj because the A cannot derive rj from Rj due to the ECDLP. According to the above analysis, the successful probability for the polynomial-time algorithm A cannot successfully be negligible. That is, any adversary cannot successfully impersonate the Uj 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 algorithmA can obtain the same messages shown in Theorem 6. Given a nonce nj∗, the A cannot successfully output another nonce nj′ such that H1(m∥nj∗)=H1(m∥nj′) due to the assumption of the OWHF. That is, the nonce nj 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 algorithmA can obtain the system parameters {G,GT,e^,q,P,PKSNO,H1,H3}. Further, the polynomial-time algorithm A can submit the same queries shown in Theorem 6. According to the above analysis, the 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.Texe: the time for computing a modular exponential operation.Tmul: the time for computing a modular multiplication operation.Tinv: the time for computing an inverse operation.Tecm: the time for computing an elliptic curve multiplication operation.Teca: the time for computing an elliptic curve addition operation.Tpairing: 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
e
x
e
+
T
e
c
m
T
i
n
v
+
3
T
e
c
m
Sensor node verification
T
e
x
e + Tmul + Tecm+Teca + Tpairing
T
e
x
e
+
3
T
p
a
i
r
i
n
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.



---

*Source: 139874-2015-11-01.xml*