# Security Analysis and Improvements of Session Key Establishment for Clustered Sensor Networks

Authors: Jiye Kim; Jongho Moon; Jaewook Jung; Dongho Won
Journal: Journal of Sensors
 (2016)

---

## Abstract

WSN (wireless sensor network) is one of the main technologies in IoT (Internet of Things) applications or services. To date, several schemes have been proposed to establish a pair-wise key between two nodes in WSN, and most of them are designed to establish long-term keys used throughout the network lifetime. However, in the near future, if WSN will be used for information infrastructures in various fields such as manufacturing, distribution, or public facilities management and its life cycle can be as long as that of other common networks, it will definitely be advantageous in terms of security to encrypt messages using session keys instead of long-term keys. In this paper, we propose a session key establishment scheme for clustered sensor networks that is based on elliptic curve Diffie-Hellman (ECDH) key exchange and hash chain. The proposed scheme eliminates vulnerabilities of existing schemes for WSN and has improved security. The proposed scheme is efficient in terms of energy costs compared to related schemes.


---

## Body

## 1. Introduction

A wireless sensor network (WSN) is composed of dozens to thousands of sensor nodes and more than one gateway and is employed with the objective of collecting data regarding the conditions or changes in the target area [1, 2]. WSN is one of the key technologies in IoT (Internet of Things) applications or services and is expected to be employed in various applications in fields such as military, healthcare, public facilities management, manufacturing, distribution, and agriculture in the near future [1, 3–5]. However, WSN is vulnerable to attacks such as node impersonation attacks, man-in-the-middle (MITM) attacks, and denial-of-service (DoS) attacks by eavesdropping or altering of the messages transmitted in wireless channels, as are other common wireless networks [6–8]. Therefore, WSN should employ security techniques to meet the security requirements of data confidentiality and integrity, availability of services, and node authentication [9].The key establishment scheme is one of the most fundamental and feasible security techniques [10]. Lai et al.’s BROSK [11], Eschenauer and Gligor’s random key pool-based scheme [12], and so forth provide the function of establishing a pair-wise key between sensor nodes [13]. Such schemes are designed with the objective of establishing a long-term key to be used throughout the lifetime of WSN under the assumption that the life cycle of WSN is much shorter than the life cycle of other networks [14]. For example, if WSN is installed to monitor a hostile environment that is not easily accessible to people, such as a battlefield or a disaster area, its life cycle is shorter than the attack time needed to determine the cryptographic keys. In this case, it is more effective for the cryptographic keys not to be rekeyed after being established, except when adding new nodes or eliminating existing nodes. However, if WSN is used for information infrastructures in fields such as manufacturing, distribution, or public facilities management, its life cycle may be long. In this case, there is a need for a session key establishment scheme that continuously renews cryptographic keys according to a cycle or an event [14].In an information and communication system, the message sender encrypts the confidential data and transmits it in the form of ciphertext to the message receiver. However, if an attacker obtains the decryption key by hacking, he/she can obtain the plaintext or additionally perform other serious attacks using the key. In order to decrease the damage caused by such key exposure, a cryptographic key known as a session key is used only for a limited period of time. In communication protocols based on session keys, even if an attacker obtains one of the session keys, the number of ciphertexts he/she can decrypt with it is limited. Also, he/she needs more pairs of plaintext and ciphertext for cryptanalysis or needs to obtain more session keys for other attacks. Therefore, encryption of messages using session keys is definitely advantageous in terms of security [15].In this paper, we focus on WSNs applied to applications such as healthcare, public facilities management, and industrial automation systems. Applying WSNs to such systems is more advantageous in terms of network performance and management costs compared to applying wired networks [18]. However, in such systems, WSNs should be operated for a long period of time and are security-critical. Moreover, for easy network management, such applications can employ clustered and hierarchical sensor networks, as shown in Figure 1 [19, 20]. When employing clustered sensor networks for such applications, the communication between the gateway and the cluster head requires stronger security than the communication between the cluster head and the sensor node; this is because the cluster head collects the data sensed by sensor nodes in its cluster and transmits it to the gateway [17]. Therefore, it is appropriate to apply the session key to the communication between the gateway and the cluster head in order to increase security. However, we found that existing session key establishment schemes for WSNs [16, 17] have several security flaws; they do not provide mutual authentication between two nodes and are vulnerable to node impersonation attacks and MITM attacks. In addition, neither scheme can guarantee secrecy of future session keys if the long-term keying materials stored in the cluster head are exposed to an attacker.Figure 1
The flow of the sensed data in a clustered sensor network. In practice, the data is transmitted hop-by-hop between nonneighboring nodes.In this paper, we propose a scheme to establish a session key between the gateway and the cluster head in order to enable the cluster head to transmit encrypted data to the gateway. Our proposed scheme should eliminate the weaknesses of existing schemes in order to achieve improved security. Moreover, not only the security but also the energy costs should be considered when designing the scheme because the nodes in WSNs are battery-powered. To meet these design requirements, the proposed scheme establishes session keys based on elliptic curve Diffie-Hellman (ECDH) key exchange [21, 22], an effective asymmetric key technique. Also, it employs hash chain [23–27] in order to provide mutual authentication between the gateway and the cluster head, verification of message integrity, and session key establishment, considering energy costs.Our major contributions are as follows: first, the proposed scheme is secure against possible attacks in key establishment schemes for WSN, such as session key attacks, replay attacks, and node capture attacks. Also, it resists both node impersonation attacks and MITM attacks through mutual authentication of two communication parties and verification of message integrity. Second, compared to long-term key establishment, there is less research on session key establishment between two nodes in WSN, and the studies are relatively more recent. Third, computation and communication costs incurred by a cluster head affect its energy consumption [28–30]. Therefore, the proposed scheme is designed to minimize the number of messages transmitted between two nodes for efficiency in terms of communication costs. Also, even though it employs asymmetric key techniques, it is more efficient in terms of computation costs compared to other schemes with similar design requirements and key establishment techniques.The remainder of the paper is organized as follows. Section2 reviews several key establishment schemes between nodes in WSN. Section 3 describes the assumptions, design requirements, and main ideas of our proposed scheme. Section 4 proposes the improved scheme and describes its phases in detail. Section 5 analyzes the security of the proposed scheme against possible attacks in key establishment schemes for WSN. Section 6 is devoted to analyzing its energy costs compared to other schemes with similar design requirements and key establishment techniques. Finally, Section 7 concludes this paper.


## 2. Review of Related Works

A few key establishment schemes have been proposed to establish a pair-wise key between sensor nodes and to provide the rekeying function in case of additions of new sensor nodes or revocation of existing sensor nodes [11, 12, 31–34]. In Lai et al.’s BROSK [11], all sensor nodes share only one master key, and each sensor node establishes a pair-wise key with its neighboring nodes using that master key. This scheme is very efficient and simple, but the entire network can become vulnerable if even one sensor node in the network is compromised by an attacker. Eschenauer and Gligor proposed a pair-wise key establishment scheme based on a random key pool [12]. In the predeployment phase of their scheme, keys are randomly chosen from one key pool and are preloaded in the sensor node. After deploying sensor nodes to the field, if a sensor node determines it has the same key as its neighboring node, it sets the same key to be the pair-wise key between two nodes. In this scheme, if an attacker compromises another sensor node that has the pair-wise key between two sensor nodes, he/she can decrypt the message transmitted between these two sensor nodes. Several modified schemes have been proposed in order to compensate for this weakness [32–34]. Based on Eschenauer and Gligor’s scheme, Chan et al. proposed a scheme where a pair-wise key can be established only when two sensor nodes share multiple keys instead of one key [32]. On the other hand, Du et al. proposed a scheme that combines the random key pool-based method with Blom’s method [33], which establishes a pair-wise key between two nodes using the symmetric matrix K in K
=
A
·
G, where matrix G is the public information, and matrix A is private information in a finite field [35]. Also, Liu et al. proposed a scheme that combines Eschenauer and Gligor’s method with the polynomial-based method [34] that establishes a pair-wise key between two nodes using t-degree polynomial f
(
x
,
y
) that satisfies f
(
i
,
j
)
=
f
(
j
,
i
) [36]. All of Chan et al., Du et al., and Liu et al.’s schemes are proposed to securely protect the links between uncompromised nodes unless a threshold number of nodes are compromised [32–34].All of the schemes mentioned above have been proposed to establish a long-term key used throughout the life cycle of WSN [14]. Compared to such schemes, session key establishment schemes between nodes in WSN have been proposed more recently. References [14, 37, 38] proposed EBS-based rekeying schemes. Eltoweissy et al. proposed the exclusion basis system (EBS), which updates a group key for normal nodes when it evicts malicious nodes from a communication group [39]. An EBS-based scheme has a key pool of size k
+
m (1
<
k,  m
<
n, where n is the number of nodes in a group). k administrative keys from the key pool are assigned to each node. When the scheme evicts some malicious nodes from the group, only m messages are needed to update a group key because the messages are encrypted using unknown keys to malicious ones. Chen and Lin proposed a session key establishment scheme for grid-based sensor networks [40]. This scheme is based on one-way hash function, mutual authentication between communication parties, and symmetric key encryption as follows: first, secret parameters (a
i
,
a
i
-
1) and (b
j
,
b
j
-
1) are preloaded to the sensor node S
i and the cluster head C
j, respectively. Then, the scheme encrypts the messages transmitted from S
i to C
j using the key K
i
=
h
(
a
i
∥
a
i
-
1
) and the ones from C
j to the gateway using the key K
j
=
h
(
b
j
∥
b
j
-
1
). After a period of time, K
i and K
j are replaced with K
i
′
=
h
(
K
i
a
i
R
N
1
) and K
j
′
=
h
(
K
j
b
j
R
N
2
), respectively, where both R
N
1 and R
N
2 are generated by the cluster head C
j. Eldefrawy et al. proposed a session key agreement scheme based on asymmetric key techniques [41]. In this scheme, the gateway receives random numbers from all sensor nodes in a cluster in order to compute a session key for communication between member nodes in the cluster. The scheme encrypts the random numbers transmitted from sensor nodes to the gateway based on RSA [42] and the session keys from the gateway to sensor nodes based on elliptic curve cryptography [21]. Meanwhile, [43–45] proposed polynomial secret-sharing-based session key establishment schemes to address the node compromise problem.Chen and Li’s scheme [16] and Lee and Kim’s scheme [17] employ different key establishment techniques to establish session keys between the gateway and the cluster head in clustered sensor networks. Chen and Li’s scheme establishes the (
i
+
1
)th session key by computing s
k
i
+
1
=
h
(
s
k
i
∥
s
k
i
-
1
), where s
k
i
-
1 and s
k
i represent the (
i
-
1
)th and ith session keys, respectively [16]. However, if an attacker obtains s
k
i and s
k
i
-
1 of C
H
j, the future session keys to be generated in the ith and the following sessions can be computed. In other words, Chen and Li’s scheme does not guarantee the secrecy of future session keys. Lee and Kim applied a modified Diffie-Hellman key exchange (DHKE) technique [46] to their scheme in order to consider the efficiency in terms of computation costs of cluster heads [17]. However, because all cluster heads in this scheme share only one private key, which is a long-term key used throughout the life cycle of the WSN, it can also be compromised by an attacker. Therefore, this scheme cannot guarantee the secrecy of future session keys. Furthermore, we found that their scheme is vulnerable to node impersonation attacks or MITM attacks. In Appendices A through D, we review Chen and Li’s scheme and Lee and Kim’s scheme in detail and analyze their security.


## 3. Design Outline of the Proposed Scheme

We consider the applications of WSNs such as healthcare, public facilities management, and industrial automation systems. The WSNs utilized for such applications should be operated for a long period of time and are security-critical.


### 3.1. Network Model

Regarding the WSN that employs the proposed scheme, we assume the following:(i)
The WSN is a clustered sensor network divided into several clusters; it consists of three types of nodes: sensor nodes, cluster heads, and a gateway. In a cluster, the sensor nodes sense the conditions or change regarding the target area and transmit the data to their cluster head. The cluster heads not only control the sensor nodes in respective clusters [13] but also collect the data sensed by the sensor nodes and transmit the data to the gateway [17].
(ii)
Sensor nodes have limited resources such as power, computation and communication capability, memory, and transmission range [1, 47–50], whereas the gateway has an abundance of these resources.
(iii)
Cluster heads are fixed and not selected from ordinary sensor nodes because resources of cluster heads are richer than those of ordinary sensor nodes. Nevertheless, our scheme can still be also applied to WSNs that perform cluster head selection [51]. This will be discussed at greater length in Section 4.2.
(iv)
A sensor node or a cluster head communicates with a nonneighboring node in a hop-by-hop fashion. We assume that the intermediate nodes between the cluster head and the gateway are not required to read the message contents exchanged between two nodes. Therefore, though the cluster head transmits its message hop-by-hop to the nonneighboring gateway, the message is encrypted/decrypted only at the two nodes; that is, the message encryption/decryption is performed end-to-end.
(v)
In WSNs, sensor nodes or cluster heads are usually battery-powered. In this study, because the WSN nodes have a long life cycle, their batteries should be replaced or charged once every few years of system operation [18].
(vi)
Sensor nodes or cluster heads can be randomly scattered in a target area or deployed according to a defined network topology. We assume that their spatial distribution depends on the application.
(vii)
All nodes in the WSN, that is, sensor nodes, cluster heads, and the gateway, are static. That is, they are not mobile.


### 3.2. Adversary Capabilities

We assume that an attacker can eavesdrop on or modify transmitted messages. Sensor nodes and cluster heads are vulnerable to physical attacks because they are usually deployed without tamper-proof devices in unattended environments [30, 52–54]. Therefore, an attacker can perform node capture attacks, that is, the capture of a node in a WSN and the extraction of secret parameters for use in subsequent attacks. The gateway is a trusted node that is not compromised and is secure against privileged-insider attacks or stolen-verifier attacks.


### 3.3. Design Requirements

The goal of our proposed scheme is for the cluster head to securely transmit the data to the gateway. For this goal, the proposed scheme provides functions to establish a session key between the cluster head and the gateway and encrypt/decrypt the data using it. In addition, the security weaknesses of existing schemes described in Section2 will be addressed in the proposed scheme. The design requirements of the proposed scheme are as follows:(i)
Because the proposed scheme protects the data using a session key, the session key should not be exposed to an attacker attempting to eavesdrop on transmitted messages. Furthermore, although long-term parameters in the cluster head are exposed to an attacker, the attacker should be unable to compute future or past session keys.
(ii)
To achieve confidentiality and integrity of the data transmitted between the gateway and the cluster head, the proposed scheme should be designed such that it is secure against possible attacks on key establishment schemes such as node impersonation attacks, MITM attacks, and replay attacks.
(iii)
The security protocols alone cannot perfectly prevent node capture attacks; however, the proposed scheme should be designed to minimize the effects of such attacks [7]. That is, even if some sensor nodes are compromised by node capture attacks, it should have no effect on the communication with other normal nodes or the security of the entire network [9].
(iv)
Sensor nodes or cluster heads are battery-powered and their batteries should be replaced or charged once every few years of system operation [18]. This implies that the resources of cluster heads in our network model can be relatively richer than those of sensor nodes in other sensor networks; however, they are still limited. Therefore, the proposed scheme should be designed to consider the energy consumption and security. For this, the scheme will be designed to be efficient in terms of computation and communication costs.


### 3.4. Notations

Notations section shows the notations used in the remainder of the paper:(i)
A pair of private and public keys for RSA signature [42] (k
g
,
p
r
,
k
g
,
p
u
b) is generated as follows: the scheme chooses two large primes p and q and computes m
=
p
·
q. It chooses e
∈
{
1,2
,
…
,
Φ
(
m
)
-
1
} which fulfills the notion that g
c
d
(
e
,
Φ
(
m
)
)
=
1, where Φ
(
m
)
=
(
p
-
1
)
(
q
-
1
). Then, it computes d which fulfills the notion that d
·
e
≡
1
m
o
d
Φ
(
m
). Here, the public key k
g
,
p
u
b is m and e, and the private key k
g
,
p
r is d. In this paper, S
I
G
k
g
,
p
r
(
x
) denotes the signing of a message x with the private key k
g
,
p
r, and it means x
d
m
o
d
Φ
(
m
). V
E
R
k
g
,
p
u
b
(
s
,
x
) denotes the verifying of a message x and its signature s with the public key k
g
,
p
u
b. It computes x
∗
=
s
e
m
o
d
Φ
(
m
) and then compares x with x
∗. If x
∗
=
x, then the signature s is valid; otherwise, it is invalid.
(ii)
A pair of private and public keys for ECDH [21, 22] (d
j
i
,
Q
j
i) is generated as follows: the scheme chooses a large prime p and defines the elliptic curve E over Z
p
(
p
>
3
) which is the set of all pairs (
x
,
y
) which fulfills the notion that y
2
≡
x
3
+
a
x
+
b
m
o
d
p and an imaginary point of infinity O, where 4
a
3
+
27
b
2
≠
0
m
o
d
p
(
a
,
b
∈
Z
p
). When P is a primitive element on the elliptic curve E and “×” denotes an elliptic curve multiplication, the scheme chooses an integer d
j
i (0
<
d
j
i
<
n, where n is the number of points on E) and computes Q
j
i
=
d
j
i
×
P. Here, Q
j
i is another element on E.


### 3.5. Main Ideas

Symmetric key-based session key establishment schemes are efficient with regard to computation costs; however, one of their persisting issues is the sharing and updating of the symmetric key, that is, the session key encryption key (KEK) by two nodes [15]. Moreover, if the KEK is a long-term key, it is futile to employ the session key because it can be exposed to an attacker. Meanwhile, another method to establish a session key is to generate the next session key using keying materials stored in the previous session, similar to Chen and Li’s scheme [16]. However, in such schemes, if an attacker obtains keying materials in a session, the past or future session keys can be computed.To meet the requirements described in Section3.3, our proposed scheme is designed as follows:(i)
The proposed scheme establishes a session key based on asymmetric key techniques in order to resist session key attacks and provide secrecy of past or future session keys. To take into account computation costs and energy consumption of cluster heads, the proposed scheme chooses an efficient key exchange technique, ECDH [21, 22], from asymmetric key techniques with the same security level.
(ii)
To resist node impersonation attacks, MITM attacks, and so forth, the proposed scheme should provide mutual authentication between the gateway and the cluster head and verify message integrity. To realize this, the proposed scheme is designed based on the hash chain containing the digests of public keys generated by the gateway, as shown in Figure2. The gateway transmits one element of the hash chain to the cluster head for each session. Using the received hash chain element, the cluster head can authenticate the message sender and verify the integrity of the message. In our scheme, the cluster head can perform these processes efficiently in terms of computation and communication costs by computing only a single hash value.Figure 2
Hash chain generation in the proposed scheme.


## 3.1. Network Model

Regarding the WSN that employs the proposed scheme, we assume the following:(i)
The WSN is a clustered sensor network divided into several clusters; it consists of three types of nodes: sensor nodes, cluster heads, and a gateway. In a cluster, the sensor nodes sense the conditions or change regarding the target area and transmit the data to their cluster head. The cluster heads not only control the sensor nodes in respective clusters [13] but also collect the data sensed by the sensor nodes and transmit the data to the gateway [17].
(ii)
Sensor nodes have limited resources such as power, computation and communication capability, memory, and transmission range [1, 47–50], whereas the gateway has an abundance of these resources.
(iii)
Cluster heads are fixed and not selected from ordinary sensor nodes because resources of cluster heads are richer than those of ordinary sensor nodes. Nevertheless, our scheme can still be also applied to WSNs that perform cluster head selection [51]. This will be discussed at greater length in Section 4.2.
(iv)
A sensor node or a cluster head communicates with a nonneighboring node in a hop-by-hop fashion. We assume that the intermediate nodes between the cluster head and the gateway are not required to read the message contents exchanged between two nodes. Therefore, though the cluster head transmits its message hop-by-hop to the nonneighboring gateway, the message is encrypted/decrypted only at the two nodes; that is, the message encryption/decryption is performed end-to-end.
(v)
In WSNs, sensor nodes or cluster heads are usually battery-powered. In this study, because the WSN nodes have a long life cycle, their batteries should be replaced or charged once every few years of system operation [18].
(vi)
Sensor nodes or cluster heads can be randomly scattered in a target area or deployed according to a defined network topology. We assume that their spatial distribution depends on the application.
(vii)
All nodes in the WSN, that is, sensor nodes, cluster heads, and the gateway, are static. That is, they are not mobile.


## 3.2. Adversary Capabilities

We assume that an attacker can eavesdrop on or modify transmitted messages. Sensor nodes and cluster heads are vulnerable to physical attacks because they are usually deployed without tamper-proof devices in unattended environments [30, 52–54]. Therefore, an attacker can perform node capture attacks, that is, the capture of a node in a WSN and the extraction of secret parameters for use in subsequent attacks. The gateway is a trusted node that is not compromised and is secure against privileged-insider attacks or stolen-verifier attacks.


## 3.3. Design Requirements

The goal of our proposed scheme is for the cluster head to securely transmit the data to the gateway. For this goal, the proposed scheme provides functions to establish a session key between the cluster head and the gateway and encrypt/decrypt the data using it. In addition, the security weaknesses of existing schemes described in Section2 will be addressed in the proposed scheme. The design requirements of the proposed scheme are as follows:(i)
Because the proposed scheme protects the data using a session key, the session key should not be exposed to an attacker attempting to eavesdrop on transmitted messages. Furthermore, although long-term parameters in the cluster head are exposed to an attacker, the attacker should be unable to compute future or past session keys.
(ii)
To achieve confidentiality and integrity of the data transmitted between the gateway and the cluster head, the proposed scheme should be designed such that it is secure against possible attacks on key establishment schemes such as node impersonation attacks, MITM attacks, and replay attacks.
(iii)
The security protocols alone cannot perfectly prevent node capture attacks; however, the proposed scheme should be designed to minimize the effects of such attacks [7]. That is, even if some sensor nodes are compromised by node capture attacks, it should have no effect on the communication with other normal nodes or the security of the entire network [9].
(iv)
Sensor nodes or cluster heads are battery-powered and their batteries should be replaced or charged once every few years of system operation [18]. This implies that the resources of cluster heads in our network model can be relatively richer than those of sensor nodes in other sensor networks; however, they are still limited. Therefore, the proposed scheme should be designed to consider the energy consumption and security. For this, the scheme will be designed to be efficient in terms of computation and communication costs.


## 3.4. Notations

Notations section shows the notations used in the remainder of the paper:(i)
A pair of private and public keys for RSA signature [42] (k
g
,
p
r
,
k
g
,
p
u
b) is generated as follows: the scheme chooses two large primes p and q and computes m
=
p
·
q. It chooses e
∈
{
1,2
,
…
,
Φ
(
m
)
-
1
} which fulfills the notion that g
c
d
(
e
,
Φ
(
m
)
)
=
1, where Φ
(
m
)
=
(
p
-
1
)
(
q
-
1
). Then, it computes d which fulfills the notion that d
·
e
≡
1
m
o
d
Φ
(
m
). Here, the public key k
g
,
p
u
b is m and e, and the private key k
g
,
p
r is d. In this paper, S
I
G
k
g
,
p
r
(
x
) denotes the signing of a message x with the private key k
g
,
p
r, and it means x
d
m
o
d
Φ
(
m
). V
E
R
k
g
,
p
u
b
(
s
,
x
) denotes the verifying of a message x and its signature s with the public key k
g
,
p
u
b. It computes x
∗
=
s
e
m
o
d
Φ
(
m
) and then compares x with x
∗. If x
∗
=
x, then the signature s is valid; otherwise, it is invalid.
(ii)
A pair of private and public keys for ECDH [21, 22] (d
j
i
,
Q
j
i) is generated as follows: the scheme chooses a large prime p and defines the elliptic curve E over Z
p
(
p
>
3
) which is the set of all pairs (
x
,
y
) which fulfills the notion that y
2
≡
x
3
+
a
x
+
b
m
o
d
p and an imaginary point of infinity O, where 4
a
3
+
27
b
2
≠
0
m
o
d
p
(
a
,
b
∈
Z
p
). When P is a primitive element on the elliptic curve E and “×” denotes an elliptic curve multiplication, the scheme chooses an integer d
j
i (0
<
d
j
i
<
n, where n is the number of points on E) and computes Q
j
i
=
d
j
i
×
P. Here, Q
j
i is another element on E.


## 3.5. Main Ideas

Symmetric key-based session key establishment schemes are efficient with regard to computation costs; however, one of their persisting issues is the sharing and updating of the symmetric key, that is, the session key encryption key (KEK) by two nodes [15]. Moreover, if the KEK is a long-term key, it is futile to employ the session key because it can be exposed to an attacker. Meanwhile, another method to establish a session key is to generate the next session key using keying materials stored in the previous session, similar to Chen and Li’s scheme [16]. However, in such schemes, if an attacker obtains keying materials in a session, the past or future session keys can be computed.To meet the requirements described in Section3.3, our proposed scheme is designed as follows:(i)
The proposed scheme establishes a session key based on asymmetric key techniques in order to resist session key attacks and provide secrecy of past or future session keys. To take into account computation costs and energy consumption of cluster heads, the proposed scheme chooses an efficient key exchange technique, ECDH [21, 22], from asymmetric key techniques with the same security level.
(ii)
To resist node impersonation attacks, MITM attacks, and so forth, the proposed scheme should provide mutual authentication between the gateway and the cluster head and verify message integrity. To realize this, the proposed scheme is designed based on the hash chain containing the digests of public keys generated by the gateway, as shown in Figure2. The gateway transmits one element of the hash chain to the cluster head for each session. Using the received hash chain element, the cluster head can authenticate the message sender and verify the integrity of the message. In our scheme, the cluster head can perform these processes efficiently in terms of computation and communication costs by computing only a single hash value.Figure 2
Hash chain generation in the proposed scheme.


## 4. Description of the Proposed Scheme

Our scheme is composed of the following three phases: predeployment phase, hash chain setup phase, and key establishment phase. The predeployment phase is performed before cluster heads are deployed in the field. After that, the hash chain setup phase and the key establishment phase are performed. Each of these phases is described in detail from Section4.1 to Section 4.3.


### 4.1. Predeployment Phase

Keying materials include information or algorithms required for key establishment. Not only in the proposed scheme but also in many secure protocols for WSN, keying materials are preloaded into nodes before they are deployed in the field [16, 17, 33, 55]. There are two reasons for preloading the keying materials. First, WSN is difficult to be equipped with secure channels such as mail compared to other common networks. Second, computation or communication costs can be reduced by skipping the initialization process after nodes are deployed in the target area. The predeployment phase of our scheme is as follows (steps (P-1) to (P-4)):(P-1)
The scheme generates a pair of private and public keys for RSA signature [42] (k
g
,
p
r, k
g
,
p
u
b) as described in Section 3.4.
(P-2)
The two keys (k
g
,
p
r, k
g
,
p
u
b) are preloaded into G
W. The private key k
g
,
p
r is stored only in G
W and is not shared with other nodes. The public key k
g
,
p
u
b is preloaded into all cluster heads. In the hash chain setup phase described in Section 4.2, G
W signs the first element of the hash chain using k
g
,
p
r, and C
H
j verifies the signature using k
g
,
p
u
b.
(P-3)
The scheme generates a pair of private and public keys for ECDH [21, 22] (d
j
1
,
Q
j
1) as described in Section 3.4.
(P-4)
The two keysd
j
1 and Q
j
1 are preloaded into C
H
j. d
j
1 is not shared with any cluster heads or sensor nodes other than C
H
j. Q
j
1 are stored in the database of G
W. In the hash chain setup phase described in Section 4.2, (d
j
1
,
Q
j
1) are used for C
H
j to establish a session key based on ECDH [21, 22].When this phase is completed, (k
g
,
p
r, k
g
,
p
u
b) and Q
j
1 are preloaded into G
W. (d
j
1, Q
j
1) and k
g
,
p
u
b are preloaded into C
H
j. The private key of G
W, k
g
,
p
r, and the private key of C
H
j, d
j
1, are secret parameters that cannot be shared with other nodes.


### 4.2. Hash Chain Setup Phase

In the hash chain setup phase,G
W generates a hash chain to be used in the key establishment phase discussed in Section 4.3. If the number of elements in the hash chain is n, during n sessions, the hash chain setup phase is performed once only in the first session, and the key establishment phase is performed (
n
-
1
) times in total, once in each session from the second to the nth session. In this phase, when G
W transmits the first element of the hash chain, H
1, with its signature to C
H
j, C
H
j verifies that H
1 is generated by G
W and is not altered during the transmission using the signature. Figure 3 depicts the hash chain setup phase. The detailed process of this phase is as follows (steps (H-1) to (H-11)):(H-1)
G
W generates n private keys (
d
g
n
,
d
g
n
-
1
,
…
,
d
g
2
,
d
g
1
) used for ECDH [21, 22] of n sessions. Then, G
W computes n public keys (Q
g
n
,
Q
g
n
-
1
,
…
,
Q
g
2
,
Q
g
1) corresponding to the private keys.
(H-2)
G
W generates a single hash chain containing n elements, as shown in Figure 2, using the public keys (Q
g
n
,
Q
g
n
-
1
,
…
,
Q
g
2
,
Q
g
1). First, G
W computes the hashed value of Q
g
n; that is, H
n
=
h
(
Q
g
n
), and it then computes the following values in order, H
n
-
1
=
h
(
Q
g
n
-
1
∥
H
n
)
,
H
n
-
2
=
h
Q
g
n
-
2
∥
H
n
-
1
,
…
,
H
2
=
h
(
Q
g
2
∥
H
3
)
,
H
1
=
h
(
Q
g
1
∥
H
2
):(1)
H
n
=
h
Q
g
n
,
H
n
-
1
=
h
Q
g
n
-
1
∥
H
n
,
H
n
-
2
=
h
Q
g
n
-
2
∥
H
n
-
1
,
⋮
H
2
=
h
Q
g
2
∥
H
3
,
H
1
=
h
Q
g
1
∥
H
2
.
(H-3)
G
W signs the first element of the hash chain (H
1) using its private key k
g
,
p
r; that is, s
g
=
S
I
G
k
g
,
p
r
(
H
1
∥
I
D
j
∥
T
g
), where I
D
j is the identity of C
H
j, and T
g is the current timestamp of G
W system. Then, G
W transmits the message {
H
1
,
s
g
,
H
2
,
Q
g
1
,
T
g
} to C
H
j.
(H-4)
C
H
j determines if (
T
j
-
T
g
)
≤
Δ
T, where T
j is the current timestamp of C
H
j system, and Δ
T is the maximum permitted transmission delay time. If (
T
j
-
T
g
)
≤
Δ
T, then the next step proceeds; otherwise, this phase is aborted.
(H-5)
C
H
j verifies s
g using the preloaded public key k
g
,
p
u
b; that is, C
H
j performs V
E
R
k
g
,
p
u
b
(
s
g
,
H
1
∥
I
D
j
∥
T
g
). If the verification is successful, then the next step is performed.
(H-6)
C
H
j compares the hashed value of Q
g
1 and H
2 with H
1. In H
1
=
h
(
Q
g
1
∥
H
2
), it is very difficult to compute Q
g
1 or H
2 from H
1 because of the characteristics of the one-way hash function. Therefore, C
H
j can verify that Q
g
1 and H
2 are generated by G
W and not altered during the transmission by verifying H
1
=
h
(
Q
g
1
∥
H
2
). If the verification is obtained, then C
H
j stores H
2, and the next step will be performed.
(H-7)
C
H
j generates a pair of private and public keys (
d
j
2
,
Q
j
2
) for ECDH [21, 22] in the next session.
(H-8)
C
H
j computes the session key s
k
1
=
d
j
1
×
Q
g
1 for this first session. Then, C
H
j replaces (
d
j
1
,
Q
j
1
) with (
d
j
2
,
Q
j
2
).
(H-9)
C
H
j encrypts d
a
t
a
1 and Q
j
2 using the session key s
k
i; that is, it performs C
d
a
t
a
1
=
E
N
C
s
k
1
(
I
D
j
∥
d
a
t
a
1
∥
Q
j
2
), where d
a
t
a
1 represents the data that C
H
j wants to transmit to G
W in this session. Then, C
H
j transmits the message {
C
d
a
t
a
1
} to G
W.
(H-10)
Upon receiving the message fromC
H
j, G
W finds [
I
D
j
,
Q
j
1
] from its database and then computes the session key s
k
1
=
d
g
1
×
Q
j
1.
(H-11)
G
W decrypts C
d
a
t
a
1 using s
k
1. If the decryption is completed and the result values (
I
D
j
∗
∥
d
a
t
a
1
∥
Q
j
2
) are correct, it means that the message sender computed the same session key as s
k
1 of G
W. Therefore, G
W can authenticate C
H
j as the message sender and verify that the message is not altered during the transmission by checking the decryption result. G
W will replace [
I
D
j
,
Q
j
1
] with [
I
D
j
,
Q
j
2
] in its database for the next session.Figure 3
Hash chain setup phase of the proposed scheme.Our proposed scheme is more suitable for a network model wherein cluster heads are fixed and not selected from ordinary sensor nodes. In this case, the resources of cluster heads are usually richer than those of ordinary sensor nodes. Nevertheless, our scheme can still be applied to WSNs that perform random node deployment, clustering, or cluster head selection [51]. In the predeployment phase, our scheme preloads only three keys, that is, d
j
1, Q
j
1, and k
g
,
p
u
b, to the cluster head C
H
j. Even though nodes in WSNs have limited memory, they do not require additional memory to store these three keys. Therefore, when the cluster heads are replaced, the scheme preloads three keys to all cluster head candidates in the predeployment phase. Then, only the selected cluster heads perform the hash chain setup phase in the field.


### 4.3. Key Establishment Phase

After the hash chain setup phase generates a hash chain withn elements in the first session, the key establishment phase is performed for each session from the second session to the last, nth session. G
W transmits a key establishment request message including one element of the hash chain to C
H
j. Then, C
H
j verifies the message, generates the session key based on ECDH [21, 22], encrypts the data using the key, and transmits it as the response message to G
W. If all verifications in this phase are passed successfully, G
W and C
H
j can share the same session key and encrypt/decrypt the data using the key. Figure 4 shows the process of the key establishment phase as follows (steps (K-1) to (K-7)):(K-1)
G
W transmits the key establishment request message {
Q
g
i
,
H
i
+
1
} to C
H
j.
(K-2)
C
H
j computes h
(
Q
g
i
∥
H
i
+
1
) and verifies that H
i
=
h
(
Q
g
i
∥
H
i
+
1
), where H
i is stored in the previous session. If the verification is passed, then C
H
j replaces H
i with H
i
+
1, and the next step is performed.
(K-3)
C
H
j computes the session key s
k
i
=
d
j
i
×
Q
g
i.
(K-4)
C
H
j generates its new private and public keys d
j
i
+
1 and Q
j
i
+
1 for the next (
i
+
1
)th session and replaces (
d
j
i
,
Q
j
i
) with (
d
j
i
+
1
,
Q
j
i
+
1
).
(K-5)
C
H
j encrypts d
a
t
a
i and Q
j
i
+
1 using the session key s
k
i; that is, C
d
a
t
a
i
=
E
N
C
s
k
i
(
I
D
j
∥
d
a
t
a
i
∥
Q
j
i
+
1
), where d
a
t
a
i is the data that C
H
j wants to transmit to G
W in this session, and I
D
j is the identity of C
H
j. Then, it transmits the response message {
C
d
a
t
a
i
} to G
W.
(K-6)
WhenG
W receives the message from C
H
j, it finds [
I
D
j
,
Q
j
i
] from its database and computes the session key s
k
i
=
d
g
i
×
Q
j
i.
(K-7)
G
W decrypts C
d
a
t
a
i using s
k
i and determines whether or not the decryption result is correct. If the verification is passed successfully, G
W can authenticate C
H
j as the message sender and verify that the message was not altered during the transmission. G
W replaces [
I
D
j
,
Q
j
i
] with [
I
D
j
,
Q
j
i
+
1
] in its database.Figure 4
Key establishment phase of the proposed scheme.AfterG
W exhausts the last element of the hash chain in the key establishment phase for the nth session, the scheme performs the hash chain setup phase for a set of n new sessions.


## 4.1. Predeployment Phase

Keying materials include information or algorithms required for key establishment. Not only in the proposed scheme but also in many secure protocols for WSN, keying materials are preloaded into nodes before they are deployed in the field [16, 17, 33, 55]. There are two reasons for preloading the keying materials. First, WSN is difficult to be equipped with secure channels such as mail compared to other common networks. Second, computation or communication costs can be reduced by skipping the initialization process after nodes are deployed in the target area. The predeployment phase of our scheme is as follows (steps (P-1) to (P-4)):(P-1)
The scheme generates a pair of private and public keys for RSA signature [42] (k
g
,
p
r, k
g
,
p
u
b) as described in Section 3.4.
(P-2)
The two keys (k
g
,
p
r, k
g
,
p
u
b) are preloaded into G
W. The private key k
g
,
p
r is stored only in G
W and is not shared with other nodes. The public key k
g
,
p
u
b is preloaded into all cluster heads. In the hash chain setup phase described in Section 4.2, G
W signs the first element of the hash chain using k
g
,
p
r, and C
H
j verifies the signature using k
g
,
p
u
b.
(P-3)
The scheme generates a pair of private and public keys for ECDH [21, 22] (d
j
1
,
Q
j
1) as described in Section 3.4.
(P-4)
The two keysd
j
1 and Q
j
1 are preloaded into C
H
j. d
j
1 is not shared with any cluster heads or sensor nodes other than C
H
j. Q
j
1 are stored in the database of G
W. In the hash chain setup phase described in Section 4.2, (d
j
1
,
Q
j
1) are used for C
H
j to establish a session key based on ECDH [21, 22].When this phase is completed, (k
g
,
p
r, k
g
,
p
u
b) and Q
j
1 are preloaded into G
W. (d
j
1, Q
j
1) and k
g
,
p
u
b are preloaded into C
H
j. The private key of G
W, k
g
,
p
r, and the private key of C
H
j, d
j
1, are secret parameters that cannot be shared with other nodes.


## 4.2. Hash Chain Setup Phase

In the hash chain setup phase,G
W generates a hash chain to be used in the key establishment phase discussed in Section 4.3. If the number of elements in the hash chain is n, during n sessions, the hash chain setup phase is performed once only in the first session, and the key establishment phase is performed (
n
-
1
) times in total, once in each session from the second to the nth session. In this phase, when G
W transmits the first element of the hash chain, H
1, with its signature to C
H
j, C
H
j verifies that H
1 is generated by G
W and is not altered during the transmission using the signature. Figure 3 depicts the hash chain setup phase. The detailed process of this phase is as follows (steps (H-1) to (H-11)):(H-1)
G
W generates n private keys (
d
g
n
,
d
g
n
-
1
,
…
,
d
g
2
,
d
g
1
) used for ECDH [21, 22] of n sessions. Then, G
W computes n public keys (Q
g
n
,
Q
g
n
-
1
,
…
,
Q
g
2
,
Q
g
1) corresponding to the private keys.
(H-2)
G
W generates a single hash chain containing n elements, as shown in Figure 2, using the public keys (Q
g
n
,
Q
g
n
-
1
,
…
,
Q
g
2
,
Q
g
1). First, G
W computes the hashed value of Q
g
n; that is, H
n
=
h
(
Q
g
n
), and it then computes the following values in order, H
n
-
1
=
h
(
Q
g
n
-
1
∥
H
n
)
,
H
n
-
2
=
h
Q
g
n
-
2
∥
H
n
-
1
,
…
,
H
2
=
h
(
Q
g
2
∥
H
3
)
,
H
1
=
h
(
Q
g
1
∥
H
2
):(1)
H
n
=
h
Q
g
n
,
H
n
-
1
=
h
Q
g
n
-
1
∥
H
n
,
H
n
-
2
=
h
Q
g
n
-
2
∥
H
n
-
1
,
⋮
H
2
=
h
Q
g
2
∥
H
3
,
H
1
=
h
Q
g
1
∥
H
2
.
(H-3)
G
W signs the first element of the hash chain (H
1) using its private key k
g
,
p
r; that is, s
g
=
S
I
G
k
g
,
p
r
(
H
1
∥
I
D
j
∥
T
g
), where I
D
j is the identity of C
H
j, and T
g is the current timestamp of G
W system. Then, G
W transmits the message {
H
1
,
s
g
,
H
2
,
Q
g
1
,
T
g
} to C
H
j.
(H-4)
C
H
j determines if (
T
j
-
T
g
)
≤
Δ
T, where T
j is the current timestamp of C
H
j system, and Δ
T is the maximum permitted transmission delay time. If (
T
j
-
T
g
)
≤
Δ
T, then the next step proceeds; otherwise, this phase is aborted.
(H-5)
C
H
j verifies s
g using the preloaded public key k
g
,
p
u
b; that is, C
H
j performs V
E
R
k
g
,
p
u
b
(
s
g
,
H
1
∥
I
D
j
∥
T
g
). If the verification is successful, then the next step is performed.
(H-6)
C
H
j compares the hashed value of Q
g
1 and H
2 with H
1. In H
1
=
h
(
Q
g
1
∥
H
2
), it is very difficult to compute Q
g
1 or H
2 from H
1 because of the characteristics of the one-way hash function. Therefore, C
H
j can verify that Q
g
1 and H
2 are generated by G
W and not altered during the transmission by verifying H
1
=
h
(
Q
g
1
∥
H
2
). If the verification is obtained, then C
H
j stores H
2, and the next step will be performed.
(H-7)
C
H
j generates a pair of private and public keys (
d
j
2
,
Q
j
2
) for ECDH [21, 22] in the next session.
(H-8)
C
H
j computes the session key s
k
1
=
d
j
1
×
Q
g
1 for this first session. Then, C
H
j replaces (
d
j
1
,
Q
j
1
) with (
d
j
2
,
Q
j
2
).
(H-9)
C
H
j encrypts d
a
t
a
1 and Q
j
2 using the session key s
k
i; that is, it performs C
d
a
t
a
1
=
E
N
C
s
k
1
(
I
D
j
∥
d
a
t
a
1
∥
Q
j
2
), where d
a
t
a
1 represents the data that C
H
j wants to transmit to G
W in this session. Then, C
H
j transmits the message {
C
d
a
t
a
1
} to G
W.
(H-10)
Upon receiving the message fromC
H
j, G
W finds [
I
D
j
,
Q
j
1
] from its database and then computes the session key s
k
1
=
d
g
1
×
Q
j
1.
(H-11)
G
W decrypts C
d
a
t
a
1 using s
k
1. If the decryption is completed and the result values (
I
D
j
∗
∥
d
a
t
a
1
∥
Q
j
2
) are correct, it means that the message sender computed the same session key as s
k
1 of G
W. Therefore, G
W can authenticate C
H
j as the message sender and verify that the message is not altered during the transmission by checking the decryption result. G
W will replace [
I
D
j
,
Q
j
1
] with [
I
D
j
,
Q
j
2
] in its database for the next session.Figure 3
Hash chain setup phase of the proposed scheme.Our proposed scheme is more suitable for a network model wherein cluster heads are fixed and not selected from ordinary sensor nodes. In this case, the resources of cluster heads are usually richer than those of ordinary sensor nodes. Nevertheless, our scheme can still be applied to WSNs that perform random node deployment, clustering, or cluster head selection [51]. In the predeployment phase, our scheme preloads only three keys, that is, d
j
1, Q
j
1, and k
g
,
p
u
b, to the cluster head C
H
j. Even though nodes in WSNs have limited memory, they do not require additional memory to store these three keys. Therefore, when the cluster heads are replaced, the scheme preloads three keys to all cluster head candidates in the predeployment phase. Then, only the selected cluster heads perform the hash chain setup phase in the field.


## 4.3. Key Establishment Phase

After the hash chain setup phase generates a hash chain withn elements in the first session, the key establishment phase is performed for each session from the second session to the last, nth session. G
W transmits a key establishment request message including one element of the hash chain to C
H
j. Then, C
H
j verifies the message, generates the session key based on ECDH [21, 22], encrypts the data using the key, and transmits it as the response message to G
W. If all verifications in this phase are passed successfully, G
W and C
H
j can share the same session key and encrypt/decrypt the data using the key. Figure 4 shows the process of the key establishment phase as follows (steps (K-1) to (K-7)):(K-1)
G
W transmits the key establishment request message {
Q
g
i
,
H
i
+
1
} to C
H
j.
(K-2)
C
H
j computes h
(
Q
g
i
∥
H
i
+
1
) and verifies that H
i
=
h
(
Q
g
i
∥
H
i
+
1
), where H
i is stored in the previous session. If the verification is passed, then C
H
j replaces H
i with H
i
+
1, and the next step is performed.
(K-3)
C
H
j computes the session key s
k
i
=
d
j
i
×
Q
g
i.
(K-4)
C
H
j generates its new private and public keys d
j
i
+
1 and Q
j
i
+
1 for the next (
i
+
1
)th session and replaces (
d
j
i
,
Q
j
i
) with (
d
j
i
+
1
,
Q
j
i
+
1
).
(K-5)
C
H
j encrypts d
a
t
a
i and Q
j
i
+
1 using the session key s
k
i; that is, C
d
a
t
a
i
=
E
N
C
s
k
i
(
I
D
j
∥
d
a
t
a
i
∥
Q
j
i
+
1
), where d
a
t
a
i is the data that C
H
j wants to transmit to G
W in this session, and I
D
j is the identity of C
H
j. Then, it transmits the response message {
C
d
a
t
a
i
} to G
W.
(K-6)
WhenG
W receives the message from C
H
j, it finds [
I
D
j
,
Q
j
i
] from its database and computes the session key s
k
i
=
d
g
i
×
Q
j
i.
(K-7)
G
W decrypts C
d
a
t
a
i using s
k
i and determines whether or not the decryption result is correct. If the verification is passed successfully, G
W can authenticate C
H
j as the message sender and verify that the message was not altered during the transmission. G
W replaces [
I
D
j
,
Q
j
i
] with [
I
D
j
,
Q
j
i
+
1
] in its database.Figure 4
Key establishment phase of the proposed scheme.AfterG
W exhausts the last element of the hash chain in the key establishment phase for the nth session, the scheme performs the hash chain setup phase for a set of n new sessions.


## 5. Security Analysis of the Proposed Scheme

The existing schemes are not able to protect past or future session keys if long-term keying materials are exposed to an attacker. The proposed scheme employs asymmetric key techniques to improve this problem, especially ECDH [21, 22], considering computation efficiency in cluster heads. Additionally, it employs the hash chain composed of digests of public keys generated by the gateway in order to resist MITM attacks or node impersonation attacks and to provide mutual authentication of two nodes and the verification of message integrity, considering computation and communication costs:(i)
Data Encryption Using a Session Key. If the life cycle of WSN is much longer than the time required for an attacker to obtain cryptographic keys through cryptanalysis or hacking, it is better in terms of security to use the session key instead of a long-term key [15, 16, 56]. In the proposed scheme, C
H
j or G
W encrypts/decrypts the data using keys renewed in every session. Therefore, it is relatively more difficult for an attacker to guess cryptographic keys in our proposed scheme than in long-term key-based schemes because the information that he/she can obtain by eavesdropping messages is limited and valid in only one session. Furthermore, even when an attacker succeeds in guessing the cryptographic keys, the damage is significantly reduced because he/she can decrypt the data in only one session.
(ii)
Session Key Attacks. This attack is to obtain session keys by eavesdropping the messages exchanged between two nodes. In the key establishment phase of the proposed scheme, even if an attacker eavesdrops the key establishment request message {
Q
g
i
,
H
i
+
1
} transmitted from G
W to C
H
j, he/she cannot compute the session key. Even if he/she can extract the public key of G
W, Q
g
i
(
=
d
g
i
×
P
) from the message, it is very difficult to compute the private key of G
W, d
g
i, because of the elliptic curved discrete logarithm problem (ECDLP) [21, 22]. Also, the private key of G
W or C
H
j, d
g
i or d
j
i, respectively, is not transmitted to other nodes in an insecure channel because it is a secure parameter. As a result, the attacker cannot decrypt or alter C
d
a
t
a
i because he/she cannot compute the session key s
k
i
(
=
d
g
i
×
Q
j
i
=
d
j
i
×
Q
g
i
=
d
g
i
×
d
j
i
×
P
) without knowing anything of the private keys of two nodes.
(iii)
Mutual Authentication. This means that one node should be authenticated as a legitimate node by another node with which it is in communication.
AfterG
W generates a hash chain in the hash chain setup phase, it transmits the first element of the hash chain, H
1, and its signature, s
g, to C
H
j. C
H
j verifies H
1 and s
g using the public key of G
W, k
g
,
p
u
b. If the verification is passed, C
H
j can authenticate G
W as the sender of H
1. An attacker cannot impersonate G
W because he/she cannot forge the signature s
g without knowing the private key of G
W, k
g
,
p
r.
Meanwhile,C
H
j generates the public key Q
j
i
+
1 for the (
i
+
1
)th session and transmits it to G
W in the ith session. Then, G
W stores this Q
j
i
+
1 in its database. When G
W receives the message {
C
d
a
t
a
i
+
1
} from C
H
j in the next (
i
+
1
)th session, it finds the public key of C
H
j, Q
j
i
+
1, in its database and computes the session key s
k
i
+
1
=
d
g
i
+
1
×
Q
j
i
+
1. If G
W can decrypt C
d
a
t
a
i
+
1 using s
k
i
+
1, that is, if the result value of decryption is a correct plaintext, then G
W can authenticate C
H
j as the sender of the message {
C
d
a
t
a
i
+
1
}. However, if G
W fails to decrypt C
d
a
t
a
i
+
1 or the result value of decryption is a meaningless random value, the session key s
k
i
+
1 is the wrong value. In this case, G
W cannot be sure that the message sender is C
H
j.
(iv)
Node Impersonation Attacks. Node impersonation attacks in WSN mean that an attacker communicates with a legitimate node by impersonating a gateway, a sensor node, or a cluster head. In the proposed scheme, if G
W or C
H
j receives a message, it performs the authentication process of the message sender. Therefore, an attacker cannot impersonate G
W or C
H
j.
(v)
MITM Attacks. This means that a malicious node decrypts or alters the messages transmitted between two legitimate nodes. The proposed scheme resists MITM attacks by the mutual authentication between G
W and C
H
j and the verification of the received messages integrity.
In the hash chain setup phase, whenC
H
j receives the message {
H
1
,
s
g
,
H
2
,
Q
g
1
,
T
g
} from G
W, it checks if H
1 is the first element of the hash chain generated by G
W; that is, it verifies the signature of H
1, s
g. If this verification is passed successfully, it means that the message sender is G
W and that the value of H
1 is not altered during the transmission. Each element of the hash chain, H
i, is the digest of Q
g
i and H
i
+
1, that is, h
(
Q
g
i
∥
H
i
+
1
). Other nodes except G
W are not able to compute Q
g
i or H
i
+
1 from H
i because h
(
·
) is a one-way hash function. Therefore, after C
H
j completes one verification of H
1 and s
g, the following (
n
-
1
) key establishment request messages can be successively verified using H
1. That is, whenever C
H
j receives the key establishment request message {
Q
g
i
∥
H
i
+
1
}, it compares H
i with the digest of Q
g
i and H
i
+
1 to verify the message integrity. As a result, an attacker cannot alter the first element of the hash chain, H
1, because he/she cannot forge the signature of G
W, s
g. Also, he/she cannot alter the rest of the elements from H
2 to H
n because of the characteristics of the one-way hash function.
Meanwhile, the message{
C
d
a
t
a
i
} transmitted from C
H
j to G
W is secure, unless the session key is exposed to the attacker because it is encrypted using the session key. Also, an attacker cannot alter this message without knowing the session key.
(vi)
Secrecy of Past or Future Session Keys. This means that an attacker should not be able to compute past or future session keys that were already used in the previous sessions or will be generated in the following sessions even when he/she obtains long-term keying materials. In the proposed scheme, G
W and C
H
j exchange their public keys, Q
g
i and Q
j
i, and generate the session key s
k
i
(
=
d
g
i
×
Q
j
i
=
d
j
i
×
Q
g
i
) based on ECDH [21, 22]. The parameters stored in C
H
j are k
g
,
p
u
b and (
d
j
i
,
Q
j
i
), where k
g
,
p
u
b is a long-term key, and (
d
j
i
,
Q
j
i
) are values renewed in each session. When they are exposed to an attacker, past or future session keys are protected as follows.
Even though an attacker obtainsk
g
,
p
u
b, he/she is not able to compute the private key k
g
,
p
r because of the integer factorization problem [42]. That is, because he/she cannot forge the signature of G
W, s
g, he/she cannot alter Q
g
i transmitted from G
W to C
H
j.
d
j
i and Q
j
i are ephemeral keys renewed in each session. This means that C
H
j replaces d
j
i and Q
j
i with d
j
i
+
1 and Q
j
i
+
1, respectively, in the end of the ith session. Assume the worst scenario in which an attacker obtains the private key, d
j
i
+
1, between the ith and (
i
+
1
)th sessions through some methods. Even in this case, the proposed scheme can protect the data securely transmitted before and after the (
i
+
1
)th session. For example, if an attacker knows the private key of C
H
j, d
j
i
+
1, and eavesdrops on the message of {
Q
g
i
+
1
,
H
i
+
2
} transmitted from G
W to C
H
j in the (
i
+
1
)th session, he/she can compute the session key s
k
i
+
1
=
d
j
i
+
1
×
Q
g
i
+
1 and decrypt the message C
d
a
t
a
i
+
1 using s
k
i
+
1. However, he/she cannot obtain any more information to restore the other session keys except s
k
i
+
1 from the decryption result of C
d
a
t
a
i
+
1, (
d
a
t
a
i
+
1
∥
Q
j
i
+
2
). As a result, the proposed scheme can assure the confidentiality of the data transmitted in all other sessions except the (
i
+
1
)th session.
(vii)
Replay Attacks. This means an attacker stores messages transmitted on security protocols and transmits them again later. The proposed scheme resists replay attacks as follows:
In the proposed scheme, the message transmitted fromG
W to C
H
j is the message {
H
1
,
s
g
,
Q
g
1
,
H
2
,
T
g
} in the hash chain setup phase or the message {
Q
g
i
,
H
i
+
1
} in the key establishment phase. The former contains the current timestamp of G
W system, T
g, and is verified by the message receiver C
H
j. The latter consists of the values that depend on the former because both are elements of a hash chain. Therefore, an attacker is not able to perform replay attacks using these messages.
The message{
C
d
a
t
a
i
} is transmitted from C
H
j to G
W as a response to the hash chain setup request of G
W or to the key establishment request of G
W. Therefore, an attacker cannot use this message for replay attacks.
(viii)
Node Capture Attacks. This means that an attacker physically captures some nodes deployed in WSN and extracts secret parameters from them for other attacks. In the proposed scheme, each cluster head generates a unique session key. Therefore, the links between uncompromised nodes are still secure even when one cluster head is compromised by node capture attacks. For example, assume that an attacker captures C
H
j and extracts d
j
i, Q
j
i, or k
g
,
p
u
b from it. The public key of G
W, k
g
,
p
u
b, is preloaded into not only C
H
j but also all cluster heads. However, an attacker cannot use it for any other attacks because he/she is not able to compute the private key k
g
,
p
r from k
g
,
p
u
b. Also, d
j
i and Q
j
i are not shared with other nodes except C
H
j, so the attacker cannot obtain other session keys except a session key between C
H
j and G
W using these two values.Table1 shows the comparison of the security in the proposed scheme and that in other schemes that have design requirements similar to ours. Table 1 shows which scheme is secure against possible attacks in key establishment schemes or provides security functionalities. This table shows that the proposed scheme is clearly improved in terms of security. In Appendices A through D, we review and analyze the security of the schemes proposed by Chen and Li and Lee and Kim.Table 1
Security comparison of the proposed scheme.
Security attacks or features
Chen and Li’s
Lee and Kim’s
The proposed
scheme [16]
scheme [17]
scheme
Data encryption using a session key
Partially
Partially
Yes
Session key attacks
Partially
Partially
Yes
Mutual authentication
No
No
Yes
Node impersonation attacks
Partially
No
Yes
MITM attacks
Partially
No
Yes
Secrecy of past session keys
Yes
Yes
Yes
Secrecy of future session keys
No
No
Yes
Replay attacks
Yes
No
Yes
Node capture attacks
Yes
No
Yes
Yes: the scheme resists the attacks or provides the functionality; No: the scheme does not resist the attacks or provide the functionality. Partially: “Yes” under the condition that the secret parameters stored inC
H
j have not been exposed to an attacker.


## 6. Energy Cost Analysis of the Proposed Scheme

In this section, we analyze the efficiency of the proposed scheme in terms of computation and communication costs. Computation costs refer to the number of times each operation is performed on a cluster head or a gateway system in a scheme. Communication costs refer to the number of messages exchanged between two nodes in a scheme. In a WSN, these two costs affect the energy consumption of nodes [28–30]. In addition, we compare the computation and communication costs of our scheme with those of existing schemes that are similar to ours in terms of design requirements or key establishment techniques.We focus on the repeatedly performed phases, that is, the hash chain set up phase and the key establishment phase, and exclude the predeployment phase. The predeployment phase does not directly affect the efficiency because it is performed only prior to the deployment of sensor nodes and cluster heads in the field.


### 6.1. Computation Costs

Table2 shows the kinds of operations and the number of times they are performed on a cluster head or gateway system in the proposed scheme during n sessions. In the proposed scheme, the hash chain setup phase is performed once, and the key establishment phase is performed (
n
-
1
) times:(i)
When the hash chain setup phase is performed once, the gateway performs one signing of RSA signature ((H-3) in Figure3), data decryption ((H-11) in Figure 3), and ECDH key exchange ((H-10) in Figure 3) each. Moreover, the one-way hash operation ((H-2) in Figure 3) and ECDH key generation ((H-1) in Figure 3) are performed n times each.
(ii)
When the hash chain setup phase is performed once, the cluster head performs one verification of RSA signature ((H-5) in Figure3), one-way hash operation ((H-6) in Figure 3), data encryption ((H-9) in Figure 3), ECDH key generation ((H-7) in Figure 3), and ECDH key exchange ((H-8) in Figure 3) each.
(iii)
When the key establishment phase is performed(
n
-
1
) times, the gateway performs data decryption ((K-7) in Figure 4) and ECDH key exchange ((K-6) in Figure 4), (
n
-
1
) times each.
(iv)
When the key establishment phase is performed(
n
-
1
) times, the gateway performs one-way hash operation ((K-2) in Figure 4), data encryption ((K-5) in Figure 4), ECDH key exchange ((K-3) in Figure 4), and ECDH key generation ((K-4) in Figure 4) (
n
-
1
) times each.Table 2
Computation cost analysis of the proposed scheme (duringn sessions).
Phases
Nodes
Operations
1024-bit RSA
SHA1
64-bit AES
163-bit ECDH
Signing
Verification
Encryption
Decryption
Key generation
Key exchange
Hash chain setup
Gateway
1
0
n
0
1
n
1
(one time)
Cluster head
0
1
1
1
0
1
1
Key establishment
Gateway
0
0
0
0
n
-
1
0
n
-
1
(n
-
1 times)
Cluster head
0
0
n
-
1
n
-
1
0
n
-
1
n
-
1Table3 also shows the types of operations and the number of times they are performed on a cluster head or gateway system in Lee and Kim’s scheme [17] during n sessions. In terms of design requirements and key establishment techniques, our scheme is similar to that of Lee and Kim.Table 3
Computation cost analysis of Lee and Kim’s scheme [17] (during n sessions).
Phases
Nodes
Operations
SHA1
64-bit AES
163-bit ECDH
Encryption
Decryption
Key generation
Key exchange
Procedure 2
Gateway
n
n
n
n
n
(n times)
Cluster head
0
n
n
0
nTo analyze the energy costs of the proposed scheme, we define several notations as follows:(i)
R
S
A
s: the energy cost of performing a signing of 1024-bit RSA signature.
(ii)
R
S
A
v: the energy cost of performing a verification of 1024-bit RSA signature.
(iii)
H: the energy cost of performing a SHA1.
(iv)
E: the energy cost of performing a 64-bit AES encryption.
(v)
D: the energy cost of performing a 64-bit AES decryption.
(vi)
D
H
g: the energy cost of performing a 1024-bit DHKE key generation.
(vii)
D
H
e: the energy cost of performing a 1024-bit DHKE key exchange.
(viii)
E
C
g: the energy cost of performing a 163-bit ECDH key generation.
(ix)
E
C
e: the energy cost of performing a 163-bit ECDH key exchange.Potlapally et al. described the energy consumption of well-known cryptographic algorithms and security protocols using the experimentation results in [28] (Table 5).Table4 shows the energy costs of our scheme and Lee and Kim’s scheme based on computation cost analysis of the two schemes and Potlapally et al.’s experimentation results. Assume that the cluster head transmits the total of l byte data to the gateway during n sessions. To perform the proposed scheme, the gateway uses about 546.50
+
440.20
n
+
0.00121
l mJ (
=
R
S
A
s
+
n
H
+
n
D
+
n
E
C
g
+
n
E
C
e
), and the cluster head uses about 15.97
+
440.20
n
+
0.00121
l mJ (
=
R
S
A
v
+
n
H
+
n
E
+
n
E
C
g
+
n
E
C
e
). Under the same conditions, to perform Lee and Kim’s scheme, the gateway uses about 1922.46
n
+
0.00242
l mJ (
=
n
H
+
n
E
+
n
D
+
n
D
H
g
+
n
D
H
e
), and the cluster head uses about 1046.50
n
+
0.00242
l mJ (
=
n
E
+
n
D
+
n
D
H
e
).Table 4
Energy costs comparison of the proposed scheme (duringn sessions).
Schemes
Nodes
Total energy costs
Energy cost comparison∗ (mJ)
The proposed scheme
Gateway
R
S
A
s
+
n
H
+
n
D
+
n
E
C
g
+
n
E
C
e
546.50
+
440.20
n
+
0.00121
l
Cluster head
R
S
A
v
+
n
H
+
n
E
+
n
E
C
g
+
n
E
C
e
15.97
+
440.20
n
+
0.00121
l
Lee and Kim’s scheme [17]
Gateway
n
H
+
n
E
+
n
D
+
n
D
H
g
+
n
D
H
e
1922.46
n
+
0.00242
l
Cluster head
n
E
+
n
D
+
n
D
H
e
1046.50
n
+
0.00242
l
∗Energy cost comparison based on the experimental results in [28]. We assume that the cluster head transmits the total of l byte data to the gateway during n sessions.Table 5
Energy costs of cryptographic algorithms [28].
Cryptographic algorithms
Energy costs∗
Signing of 1024-bit RSA signature
546.50 mJ
Verification of 1024-bit RSA signature
15.97 mJ
SHA1
0.76μJ/byte
64-bit AES encryption
1.21μJ/byte
64-bit AES decryption
1.21μJ/byte
1024-bit DHKE key generation
875.96 mJ
1024-bit DHKE key exchange
1046.50 mJ
163-bit ECDH key generation
276.70 mJ
163-bit ECDH key exchange
163.50 mJ
∗These values are the experimental results in [28], in which the cryptographic algorithms were developed on a Compaq iPAQ H3670 equipped with a 206 MHz Intel SA-1110 StrongARM processor and 64 MB RAM.Given that the cluster heads are battery-powered, we have to focus more on the energy costs in the cluster head than in the gateway. Table4 shows that the energy cost of the cluster head in our scheme is smaller than that in Lee and Kim’s scheme (
15.97
+
440.20
n
+
0.00121
l
m
J
<
1046.50
n
+
0.00242
l
m
J
). Therefore, in terms of energy consumption based on computation costs, the proposed scheme is more efficient than Lee and Kim’s scheme. This can be attributed to the difference in the energy costs of the two key exchange algorithms, that is, 163-bit ECDH and 1024-bit DHKE; 163-bit ECDH and 1024-bit DHKE schemes have the same security level, but the energy consumption of the former is only one-quarter that of the latter (276.70
+
163.50
m
J
<
875.96
+
1046.5
m
J in Table 5) [28]. Meanwhile, the verification of RSA signature in the proposed scheme does not significantly affect the total energy costs of C
H
j, even though the scheme is an asymmetric key technique. This is because, for n sessions, the operation is performed only once in the hash chain setup phase and the verification is performed more efficiently than the signing in RSA signature (15.97
m
J
<
546.50
m
J in Table 5) [15, 28].


### 6.2. Communication Costs

Communication costs as well as computation costs affect the energy costs of cluster heads [29, 30]. In our scheme, the messages {
H
1
,
s
g
,
H
2
,
Q
g
1
,
T
g
} and {
C
d
a
t
a
1
} are exchanged between the cluster head and the gateway in the hash chain setup phase, while the messages {
Q
g
i
,
H
i
+
1
} and {
C
d
a
t
a
i
} are exchanged in the key establishment phase. That is, in the proposed scheme, two message exchanges are needed between the two nodes during one session, which is same as the number of messages in Lee and Kim’s scheme and less than the three messages in Chen and Li’s scheme. The proposed scheme minimizes the number of messages, considering that it provides all functions of session key establishment, node authentication, and data encryption.


## 6.1. Computation Costs

Table2 shows the kinds of operations and the number of times they are performed on a cluster head or gateway system in the proposed scheme during n sessions. In the proposed scheme, the hash chain setup phase is performed once, and the key establishment phase is performed (
n
-
1
) times:(i)
When the hash chain setup phase is performed once, the gateway performs one signing of RSA signature ((H-3) in Figure3), data decryption ((H-11) in Figure 3), and ECDH key exchange ((H-10) in Figure 3) each. Moreover, the one-way hash operation ((H-2) in Figure 3) and ECDH key generation ((H-1) in Figure 3) are performed n times each.
(ii)
When the hash chain setup phase is performed once, the cluster head performs one verification of RSA signature ((H-5) in Figure3), one-way hash operation ((H-6) in Figure 3), data encryption ((H-9) in Figure 3), ECDH key generation ((H-7) in Figure 3), and ECDH key exchange ((H-8) in Figure 3) each.
(iii)
When the key establishment phase is performed(
n
-
1
) times, the gateway performs data decryption ((K-7) in Figure 4) and ECDH key exchange ((K-6) in Figure 4), (
n
-
1
) times each.
(iv)
When the key establishment phase is performed(
n
-
1
) times, the gateway performs one-way hash operation ((K-2) in Figure 4), data encryption ((K-5) in Figure 4), ECDH key exchange ((K-3) in Figure 4), and ECDH key generation ((K-4) in Figure 4) (
n
-
1
) times each.Table 2
Computation cost analysis of the proposed scheme (duringn sessions).
Phases
Nodes
Operations
1024-bit RSA
SHA1
64-bit AES
163-bit ECDH
Signing
Verification
Encryption
Decryption
Key generation
Key exchange
Hash chain setup
Gateway
1
0
n
0
1
n
1
(one time)
Cluster head
0
1
1
1
0
1
1
Key establishment
Gateway
0
0
0
0
n
-
1
0
n
-
1
(n
-
1 times)
Cluster head
0
0
n
-
1
n
-
1
0
n
-
1
n
-
1Table3 also shows the types of operations and the number of times they are performed on a cluster head or gateway system in Lee and Kim’s scheme [17] during n sessions. In terms of design requirements and key establishment techniques, our scheme is similar to that of Lee and Kim.Table 3
Computation cost analysis of Lee and Kim’s scheme [17] (during n sessions).
Phases
Nodes
Operations
SHA1
64-bit AES
163-bit ECDH
Encryption
Decryption
Key generation
Key exchange
Procedure 2
Gateway
n
n
n
n
n
(n times)
Cluster head
0
n
n
0
nTo analyze the energy costs of the proposed scheme, we define several notations as follows:(i)
R
S
A
s: the energy cost of performing a signing of 1024-bit RSA signature.
(ii)
R
S
A
v: the energy cost of performing a verification of 1024-bit RSA signature.
(iii)
H: the energy cost of performing a SHA1.
(iv)
E: the energy cost of performing a 64-bit AES encryption.
(v)
D: the energy cost of performing a 64-bit AES decryption.
(vi)
D
H
g: the energy cost of performing a 1024-bit DHKE key generation.
(vii)
D
H
e: the energy cost of performing a 1024-bit DHKE key exchange.
(viii)
E
C
g: the energy cost of performing a 163-bit ECDH key generation.
(ix)
E
C
e: the energy cost of performing a 163-bit ECDH key exchange.Potlapally et al. described the energy consumption of well-known cryptographic algorithms and security protocols using the experimentation results in [28] (Table 5).Table4 shows the energy costs of our scheme and Lee and Kim’s scheme based on computation cost analysis of the two schemes and Potlapally et al.’s experimentation results. Assume that the cluster head transmits the total of l byte data to the gateway during n sessions. To perform the proposed scheme, the gateway uses about 546.50
+
440.20
n
+
0.00121
l mJ (
=
R
S
A
s
+
n
H
+
n
D
+
n
E
C
g
+
n
E
C
e
), and the cluster head uses about 15.97
+
440.20
n
+
0.00121
l mJ (
=
R
S
A
v
+
n
H
+
n
E
+
n
E
C
g
+
n
E
C
e
). Under the same conditions, to perform Lee and Kim’s scheme, the gateway uses about 1922.46
n
+
0.00242
l mJ (
=
n
H
+
n
E
+
n
D
+
n
D
H
g
+
n
D
H
e
), and the cluster head uses about 1046.50
n
+
0.00242
l mJ (
=
n
E
+
n
D
+
n
D
H
e
).Table 4
Energy costs comparison of the proposed scheme (duringn sessions).
Schemes
Nodes
Total energy costs
Energy cost comparison∗ (mJ)
The proposed scheme
Gateway
R
S
A
s
+
n
H
+
n
D
+
n
E
C
g
+
n
E
C
e
546.50
+
440.20
n
+
0.00121
l
Cluster head
R
S
A
v
+
n
H
+
n
E
+
n
E
C
g
+
n
E
C
e
15.97
+
440.20
n
+
0.00121
l
Lee and Kim’s scheme [17]
Gateway
n
H
+
n
E
+
n
D
+
n
D
H
g
+
n
D
H
e
1922.46
n
+
0.00242
l
Cluster head
n
E
+
n
D
+
n
D
H
e
1046.50
n
+
0.00242
l
∗Energy cost comparison based on the experimental results in [28]. We assume that the cluster head transmits the total of l byte data to the gateway during n sessions.Table 5
Energy costs of cryptographic algorithms [28].
Cryptographic algorithms
Energy costs∗
Signing of 1024-bit RSA signature
546.50 mJ
Verification of 1024-bit RSA signature
15.97 mJ
SHA1
0.76μJ/byte
64-bit AES encryption
1.21μJ/byte
64-bit AES decryption
1.21μJ/byte
1024-bit DHKE key generation
875.96 mJ
1024-bit DHKE key exchange
1046.50 mJ
163-bit ECDH key generation
276.70 mJ
163-bit ECDH key exchange
163.50 mJ
∗These values are the experimental results in [28], in which the cryptographic algorithms were developed on a Compaq iPAQ H3670 equipped with a 206 MHz Intel SA-1110 StrongARM processor and 64 MB RAM.Given that the cluster heads are battery-powered, we have to focus more on the energy costs in the cluster head than in the gateway. Table4 shows that the energy cost of the cluster head in our scheme is smaller than that in Lee and Kim’s scheme (
15.97
+
440.20
n
+
0.00121
l
m
J
<
1046.50
n
+
0.00242
l
m
J
). Therefore, in terms of energy consumption based on computation costs, the proposed scheme is more efficient than Lee and Kim’s scheme. This can be attributed to the difference in the energy costs of the two key exchange algorithms, that is, 163-bit ECDH and 1024-bit DHKE; 163-bit ECDH and 1024-bit DHKE schemes have the same security level, but the energy consumption of the former is only one-quarter that of the latter (276.70
+
163.50
m
J
<
875.96
+
1046.5
m
J in Table 5) [28]. Meanwhile, the verification of RSA signature in the proposed scheme does not significantly affect the total energy costs of C
H
j, even though the scheme is an asymmetric key technique. This is because, for n sessions, the operation is performed only once in the hash chain setup phase and the verification is performed more efficiently than the signing in RSA signature (15.97
m
J
<
546.50
m
J in Table 5) [15, 28].


## 6.2. Communication Costs

Communication costs as well as computation costs affect the energy costs of cluster heads [29, 30]. In our scheme, the messages {
H
1
,
s
g
,
H
2
,
Q
g
1
,
T
g
} and {
C
d
a
t
a
1
} are exchanged between the cluster head and the gateway in the hash chain setup phase, while the messages {
Q
g
i
,
H
i
+
1
} and {
C
d
a
t
a
i
} are exchanged in the key establishment phase. That is, in the proposed scheme, two message exchanges are needed between the two nodes during one session, which is same as the number of messages in Lee and Kim’s scheme and less than the three messages in Chen and Li’s scheme. The proposed scheme minimizes the number of messages, considering that it provides all functions of session key establishment, node authentication, and data encryption.


## 7. Conclusion

In this paper, we propose a session key establishment scheme for clustered sensor networks based on ECDH [21, 22] and hash chain [23–27]. Our proposed scheme is secure against the possible attacks in key establishment schemes of WSN such as session key attacks, node impersonation attacks, MITM attacks, replay attacks, and node capture attacks. The scheme eliminates vulnerabilities of existing session key establishment schemes for WSN and provides secrecy of past or future session keys. Additionally, the proposed scheme is designed to minimize the number of messages for efficiency in terms of communication costs. Also, it is more efficient in terms of computation costs compared to other schemes based on asymmetric key techniques. Because of the efficiency of the proposed scheme, the cluster head requires less energy to operate.



---

*Source: 4393721-2016-06-30.xml*