# Secure Key Distribution Using Fragmentation and Assimilation in Wireless Sensor and Actor Networks

Authors: AtaUllah Ghafoor; Muhammad Sher; Muhammad Imran; Abdelouahid Derhab
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Secure key distribution is one of the most important building blocks to ensure confidentiality in wireless sensor and actor networks (WSANs). However, the key distribution becomes a challenging task when keys have to be relayed by compromised nodes in order to establish secure communication between distant nodes. To deal with this issue, we propose in this paper a key distribution scheme, named key distribution using fragmentation and assimilation (KDFA).  In this scheme, the sender node splits the actual key into fragments and sends them through intermediate actor nodes towards the receiver node. The latter assimilates these key fragments using XOR operation to reconstruct the actual key. In this case, attacker cannot retrieve the actual key and only gets the key fragment. KDFA is composed of two parts: (a) key distribution protocol (KDP) to distribute the key using intra-actor and interactor communication scenarios and (b) key fragmentation algorithm (KFA) to slice the key using binary calculations. KDFA execution has been specified and formally verified using Rubin logic. Moreover, the performance and the resilience of the proposed protocol are further analyzed through extensive simulations using ns-2.35. Results show that KDFA is resilient against actor node compromise and key exposure.


---

## Body

## 1. Introduction

A wireless sensor and actor network (WSAN) is a distributed system of sensor and actor nodes that are interconnected through wireless links [1, 2]. The sensor nodes gather information about the environment such as temperature and vibration and send them a base station (or sink) using a hop-by-hop communication. On the other hand, the actor nodes perform actions in response to some specific events. Such networks are widely used in applications like buildings/house monitoring [3], water sprinkling on fire detection [4], surveillance and intruder detection, traffic monitoring, health and habitat monitoring, and so forth [5, 6]. Actor nodes play a vital role at taking actions to change the behavior of the environment by analyzing and responding to the events [7]. They also communicate with ordinary sensor nodes to collect data as shown in Figure 1.Figure 1
Communication scenarios in WSAN.Secure key distribution in WSAN is mandatory because most of the applications require confidentiality of data exchanged between nodes located in different regions [8, 9]. In the literature, some secure key establishment schemes have been proposed to enhance security and ensure confidentiality. In existing symmetric key management schemes [10–12], if a node is compromised then the new key distribution messages passing through that node are also compromised. Therefore, the links are compromised before their establishment, and it is not possible to establish end-to-end key between the sender and the receiver as messages can be decrypted and then reencrypted at the intermediate nodes. An intermediate malicious node can interpret these keys and help other malicious nodes at joining the network using valid keys. The problem becomes more complex when indirect keys are exchanged between distant nodes in different regions because more intermediate nodes are involved and the probability of the key to be relayed by malicious intermediate nodes increases.In the existing key distribution schemes, all the keys that pass through compromised nodes also become compromised. The issue studied in this paper is how to exchange secret keys among distant nodes in the presence of malicious intermediate nodes. To deal with this issue, we propose a key distribution using fragmentation and assimilation (KDFA) scheme for establishing indirect keys between two distant sensor nodes. The main contribution offered by KDFA is that the sender node slices the actual key into fragments and sends them via intermediate actor nodes towards the receiver node. The distant receiver node assimilates the key fragments using XOR operation to obtain the original key. In this case, the attacker can only get the key fragment because the original key is never transmitted. The condition for successful attack is to capture all the fragment key packets related to one key, which is not a trivial task. If an attacker succeeds at identifying the intermediate nodes and subverting the key fragments then only one key is exposed. Therefore, KDFA is expected to provide better secure key distribution scheme and achieve better resilience against malicious nodes in comparison to other schemes.KDFA is composed of two parts: (a) key fragmentation algorithm (KFA), which divides the keys of different sizes into an appropriate number of key fragments, and (b) key distribution protocol (KDP) provides a stepwise description for exchanging secure messages to distribute pairwise keys. In addition, we have formally specified and verified KDFA using Rubin logic [13]. The latter validates the protocol as per standard requirements of cryptographic operations like authentication, message integrity, message freshness, encryption, decryption, and so forth. It also helps at identifying the deficiencies in the protocol and possibilities of node compromise attacks, and it is also near to real implementation. KDFA is further simulated under ns-2.35 to assess its effectiveness in terms of resilience against compromised nodes. Results show that two uncompromised nodes can distribute a key securely even if a large number of intermediate nodes are compromised.The rest of paper is organized as follows: system model and problem statement are provided in Section2. Section 3 presents related work. Section 4 details KDFA operations for key distribution. Section 5 provides a detailed formal specification and analysis of KDFA using Rubin logic. Simulation scenarios and results in terms of resilience, fragmentation computation, and communication overhead are given in Section 6. Finally, Section 7 concludes the work and outlines future research directions.


## 2. System Model and Problem Statement

We consider a model of WSAN, in which the nodes composing the networks (i.e., sensors, actors, and the sink) are randomly deployed in the network field. We assume that each actor knows the keys of all the sensor nodes in the network and can move around within the network field to collect data from sensors. We also assume that nodes within communication range of each other have already established keys among them.During indirect key establishment between ordinary distant nodes, the sender node transmits a pairwise key via intermediate nodes. The message that contains a new key is encrypted by the preestablished key between the sender and the intermediate node. The latter decrypts the key and then reencrypts it using the preestablished key with the next intermediate node and so on. By following the same process, the new key reaches the receiver node. The problem in this scenario is that any new secret key is available to intermediate nodes in a plain text form. If one of the intermediate nodes is compromised then that key is compromised before its establishment. Similarly, future key passed through that nodes become also compromised. The same problem holds in [10–12, 14–17] for WSN and [9, 16, 18–20] for WSAN.This allows the attacker to perform illegal activities by either code alteration or falsifying the broadcast messages. New indirect keys can also be established with that malicious node. An adversary can also introduce new node to the network by preloading the compromised keys onto it along with a duplicate ID of a sensor node that was expired by the attacker. This new duplicated node can receive the packets destined for the actual node. In a similar way the situation can be worse if a large number of new compromised actor nodes are introduced to the network.


## 3. Related Work

Key management schemes have been extensively investigated in the context of indirect key establishment between nodes in WSNs and WSANs. In this scenario, a symmetric key is transmitted by the sender node to the receiver node using intermediaries. Intermediate nodes in the literature are called agent [15], gateway [10], bridge [12], or proxy [17]. These nodes play a vital role for intercluster communication in WSN. We will use the name gateway to represent such nodes. Also, the similar role is played by actors for indirect key establishment in WSAN [9, 16, 18–20].


### 3.1. Gateway Node Based Schemes

Zhou et al. [15] provided a pairwise intergroup key distribution scenario where an agent node pair is used to share keys between senders and receivers. This scenario is depicted in Figure 2 where the sender node n2 sends the message via an agent node pair n7 and n23 to the receiver node n30. This scheme uses an agent pair to transmit a single key whereas in our proposed scheme (i.e., KDFA) actor pairs are used instead.Figure 2
Interagent key distribution.Addya and Turuk [10] proposed a scheme, which required the gateway node to set up an intergroup path key between nodes of two clusters. A single node is acting as a gateway node instead of a node pair because it has shared keys of both clusters. This node should be located at a common region of two clusters similar to the locations of nodes 5, 11 as illustrated in Figure 3. Intercluster communication between cluster 1 and cluster 2 is established through node 5. There could be multiple gateway nodes in a common region. The scheme uses a gateway node to transmit a single key which is similar to the intra-actor communication scheme proposed in KDFA.Figure 3
Intercluster communication using gateway nodes.Zhou and Fang [21] proposed a symmetric polynomial based scheme where polynomial shared keys are preloaded in each sensor to calculate the direct key after deployment. Nodes located at the junction of two clusters receive two polynomials and can play the role of gateway. To achieve satisfactory level of security, coefficient degree must satisfy (1) where Ni is the size of group i, t is the degree of polynomial, and K is the count of preloaded security credentials:(1)0≤Ni-2≤tNikK+1!2K+1i=1,2,…,K.In this scheme, if a new node joins the network or existing node leaves the network then new polynomial is calculated to refresh the existing keys. It requires a large amount of communication overhead. It could be reduced by adopting XOR based key freshness scheme [22] where a magic word is shared among all member nodes to refresh the key in an efficient manner.Huang’s scheme [14] mitigated the effects of compromised nodes by applying the Reed-Solomon encoding scheme to divide the seed of a key into n codewords and transmit each codeword via different node-disjoint path. KDFA applies the idea of partitioning on indirect keys as in [14]. However, instead of using some encoding scheme, it just uses a lightweight fragmentation mechanism to partition the key into small-sized fragments.


### 3.2. Actor Node Based Schemes

Du et al. [9] proposed a distributed key establishment scheme for WSAN, in which actors are preloaded with symmetric keys and public key certificates as well. After deployment, node A can request from its neighbors to sign its certificate where an actor can also be one of the signers. Neighboring nodes sign the received certificate by using their self-generated private key KNi-1 and return the signatures {Certa}KNi-1 back to node A. Afterwards, communicating nodes can exchange a key by sharing symmetric session key encrypted using public keys. If a node is captured then its certificates are also removed from the list of neighboring nodes. It claims to achieve guaranteed security if a small number of nodes are malicious. In this scheme, nodes are relying on ordinary intermediate nodes for signing the certificates where a malicious node can also take part in establishing keys. KDFA is a reliable scheme that ensures the resilience and the secure key distribution in case a large number of nodes are compromised.Mármol et al. [19] proposed WSANRep to maintain node reputation to detect the malicious nodes and exclude from the network. Global reputation of a network WSANj can be calculated by a group Gi at the tth transaction using (2) where α, β, and γ are weights assigned based on previous experiences:(2)GRepGi,WSANjt=αGi,WSANj·GRepGi,WSANjt-1+βGi,WSANj·RepGi,WSANj+γGi,WSANj·RepO,WSANj.Kashi and Sharifi [23] illustrated a categorical comparison for weak coordination and connectivity between actors and sensor nodes. It recommends that powerful actor nodes can help sensor nodes in routing and forwarding data to the sink. KDFA provides a strong resilience to protect the key exposure at intermediate compromised nodes. Interactor connectivity is the mandatory part for this communication; therefore, connectivity restoration [24–26] should also be considered to achieve sustainable communication and coordination [27] in different regions using actor nodes.Y. Lee and S. Lee [20] proposed a scheme to establish pairwise keys between two sensors and between sensors and actors for secure communication in WSAN. A region key is also distributed by actor nodes to its neighboring sensor nodes for a specific task and keys expire after a fixed time quanta. Public key cryptography was proposed only for upper layer communication between actors and the sink nodes. Key distribution through public key cryptography is an expensive task in terms of computation and a central KDC could be a single point of failure. KDFA does not require a KDC and it ensures secure key distribution as compared to the existing schemes.


## 3.1. Gateway Node Based Schemes

Zhou et al. [15] provided a pairwise intergroup key distribution scenario where an agent node pair is used to share keys between senders and receivers. This scenario is depicted in Figure 2 where the sender node n2 sends the message via an agent node pair n7 and n23 to the receiver node n30. This scheme uses an agent pair to transmit a single key whereas in our proposed scheme (i.e., KDFA) actor pairs are used instead.Figure 2
Interagent key distribution.Addya and Turuk [10] proposed a scheme, which required the gateway node to set up an intergroup path key between nodes of two clusters. A single node is acting as a gateway node instead of a node pair because it has shared keys of both clusters. This node should be located at a common region of two clusters similar to the locations of nodes 5, 11 as illustrated in Figure 3. Intercluster communication between cluster 1 and cluster 2 is established through node 5. There could be multiple gateway nodes in a common region. The scheme uses a gateway node to transmit a single key which is similar to the intra-actor communication scheme proposed in KDFA.Figure 3
Intercluster communication using gateway nodes.Zhou and Fang [21] proposed a symmetric polynomial based scheme where polynomial shared keys are preloaded in each sensor to calculate the direct key after deployment. Nodes located at the junction of two clusters receive two polynomials and can play the role of gateway. To achieve satisfactory level of security, coefficient degree must satisfy (1) where Ni is the size of group i, t is the degree of polynomial, and K is the count of preloaded security credentials:(1)0≤Ni-2≤tNikK+1!2K+1i=1,2,…,K.In this scheme, if a new node joins the network or existing node leaves the network then new polynomial is calculated to refresh the existing keys. It requires a large amount of communication overhead. It could be reduced by adopting XOR based key freshness scheme [22] where a magic word is shared among all member nodes to refresh the key in an efficient manner.Huang’s scheme [14] mitigated the effects of compromised nodes by applying the Reed-Solomon encoding scheme to divide the seed of a key into n codewords and transmit each codeword via different node-disjoint path. KDFA applies the idea of partitioning on indirect keys as in [14]. However, instead of using some encoding scheme, it just uses a lightweight fragmentation mechanism to partition the key into small-sized fragments.


## 3.2. Actor Node Based Schemes

Du et al. [9] proposed a distributed key establishment scheme for WSAN, in which actors are preloaded with symmetric keys and public key certificates as well. After deployment, node A can request from its neighbors to sign its certificate where an actor can also be one of the signers. Neighboring nodes sign the received certificate by using their self-generated private key KNi-1 and return the signatures {Certa}KNi-1 back to node A. Afterwards, communicating nodes can exchange a key by sharing symmetric session key encrypted using public keys. If a node is captured then its certificates are also removed from the list of neighboring nodes. It claims to achieve guaranteed security if a small number of nodes are malicious. In this scheme, nodes are relying on ordinary intermediate nodes for signing the certificates where a malicious node can also take part in establishing keys. KDFA is a reliable scheme that ensures the resilience and the secure key distribution in case a large number of nodes are compromised.Mármol et al. [19] proposed WSANRep to maintain node reputation to detect the malicious nodes and exclude from the network. Global reputation of a network WSANj can be calculated by a group Gi at the tth transaction using (2) where α, β, and γ are weights assigned based on previous experiences:(2)GRepGi,WSANjt=αGi,WSANj·GRepGi,WSANjt-1+βGi,WSANj·RepGi,WSANj+γGi,WSANj·RepO,WSANj.Kashi and Sharifi [23] illustrated a categorical comparison for weak coordination and connectivity between actors and sensor nodes. It recommends that powerful actor nodes can help sensor nodes in routing and forwarding data to the sink. KDFA provides a strong resilience to protect the key exposure at intermediate compromised nodes. Interactor connectivity is the mandatory part for this communication; therefore, connectivity restoration [24–26] should also be considered to achieve sustainable communication and coordination [27] in different regions using actor nodes.Y. Lee and S. Lee [20] proposed a scheme to establish pairwise keys between two sensors and between sensors and actors for secure communication in WSAN. A region key is also distributed by actor nodes to its neighboring sensor nodes for a specific task and keys expire after a fixed time quanta. Public key cryptography was proposed only for upper layer communication between actors and the sink nodes. Key distribution through public key cryptography is an expensive task in terms of computation and a central KDC could be a single point of failure. KDFA does not require a KDC and it ensures secure key distribution as compared to the existing schemes.


## 4. Key Distribution Using Fragmentation and Assimilation (KDFA)

The proposed scheme KDFA provides a reliable solution to the key exposure problem at compromised intermediate nodes. A sender node transmits a request to nearby actors for establishing key with a distant receiver node that is located outside the communication range. Actors can play a vital role at routing keys between sender and receiver nodes. Key distribution process begins when a sender uses a light weight fragmentation mechanism to divide the key intof fragments and transmits them through f intermediate actor nodes in the paths towards the receiver. The receiver calculates the actual key by taking XOR of these key fragments. In this process, number of key fragments “f” is decided by the administrator and it depends on the safety of deployment region and the security level required by the application. In most of the cases, the recommended value for f is either 2 or 3. In KDFA, the attacker can only get the key fragment by capturing intermediate nodes and not the complete original key. It provides an efficient way to secure the pairwise key establishment scheme by improving the resilience against the node capture attacks.Actor nodes can distribute the key fragments using one of the following communication scenarios. In the first scenario, the sender requests to establish an indirect key with a node located outside its transmission range but exist within the communication range of nearby actor nodes. The actor node has keys of all the nodes in the network and can act as an intermediate node to establish a secret key between senderSi and receiver Rk. This scenario is shown in Figure 4 where f=2 fragments are transmitted using actor nodes Ax and Ay. Afterwards, Si and Rk can exchange encrypted messages via ordinary intermediate sensor nodes.Figure 4
Intra-actor communication for key distribution.In the second scenario, the sender node transmits two key fragments to the actor node pair to establish indirect key with a distant nodeRk that is not within transmission range of actor Ax and Ay. Actors request the adjacent actor to distribute the key fragments to Rk. It requires interactor communication between two actor pairs for f=2 fragments, as illustrated in Figure 5.Figure 5
Inter-actor communication for key distribution.In the third scenario, the sender node requests from nearby actor node pair to establish indirect key with a distant node by distributing key fragments. ActorAx is within the transmission range of Rk and directly sends the key fragment to Rk. But the receiver node Rk is out of the transmission range of the second actor Ay, which requires interactor communication to distribute the key fragment to Rk. Figure 6 depicts the key establishment for the f=2 key fragments using hybrid communication scenario.Figure 6
Hybrid communication for key distribution.During the key distribution process, if there is only one actor in the range of the sender node and the second actor node is not available within a threshold value of time thenf key fragment messages are sent via a single actor node. An upper-bound on the delay between consecutive transmissions of fragments can be imposed so that the receiver node will wait for the next fragment. An extra functionality can be added to the receiver code to manage the freshness as different messages originated by the same node reach the receivers at different time instants. During the waiting phase, another actor can visit the sender node’s area to transmit other fragments because the actors frequently visit areas to collect data from the sensor nodes. In all case, the property ensured by KDFA is that a single key is never sent in one message.KDFA is applicable for static and mobile sensor nodes. In war field, two or more distant soldiers can exchange their current positions securely to move together towards the target. In industry, big machines are turned on in a sequential manner to avoid power hazards. Distant machines can be synchronized to turn on or off by exchanging secure messages. There exist a number of similar application scenarios where our scheme can effectively provide secure messaging.A list of notations used in KDFA is provided with brief description in Table1.Table 1
Notations.
Sr.
Notation
Description
1
S
i
Sender node
2
R
k
Receiver node
3
F
Number of key fragments
4
A
x, Ay
Actor nodes
5
K
F
m, KFm+1
Two key fragments
6
n
i, ni+1
Nonce values formSi
7
t
i, ti+1
Timestamps fromSi
8
C
1, C2, C3
Cipher text of messages 1, 2, and 3
9
K
S
i
-
A
x,  KSi-Ay
Secret keys between senderSi and actors Ax and Ay
10
K
A
x
-
R
k, KAy-Rk
Secret keys between receiverRk and actors Ax and Ax
11
K
S
i
-
R
k
New key established between distant nodesSi and Rk


### 4.1. Key Fragmentation Algorithm (KFA)

It is used by the sender node to divide the key intof fragments. If the key size is divisible by f then equal-sized fragments are produced like 32-bit key is divided into 2 fragments of size 16-bit each, but in case of 3 fragments the result will be two fragments of size 10 and the last fragment of size 12. The size of the last fragment is calculated as per line 7 in Pseudocode 1.Pseudocode 1:Key fragmentation.
(1)if Remainder of (keySize, f) is 0 then
(2)fragmentSize = keySize/f
(3)LFz  = fragmentSize
(4)else
(5)fragmentSize =  ⌞keySize/f⌟
(6)addBits = keySize − (fragmentSize * f)
(7)LFz  = fragmentSize + addBits
(8)end ifStep 1, 2. If a selected key size in bits is completely divisible by f, for example, a 32-bit key with f=2, then the remainder Rem(32,2) is zero. It produces 2 fragments of 16-bit each.Step 3. Last fragment size is equal to the fragment size because the key size is completely divisible.Step 4, 5. If the key size is not completely divisible by f, for example, a 32-bit key with f=3. In this case, the remainder Rem(32,3) is not zero. It will create three fragments of 10-bit each with a total of 30 bits and an extra fourth fragment of size 2-bit is also created. The last fragment is smaller than the selected fragment size, which is 10 in this case.Step 6. This problem is mitigated by calculating additional bits and then padded them to the last fragment. Initially a fragment size is calculated by dividing the key size by f and the floor is taken to get the lower value for the fragment size. If a key size is 32 with f=3 then the fragment size is 10. It will create (f-1) fragments of (fragmentSize×(f-1)) bits. It will produce two fragments of 20 bits when key size = 32, f=3 and fragment Size = 10. Additional number of bits required for padding for the last fragment is calculated by multiplying the fragment size by f to get the total size in bits of all fragments. Then, we ignore extra bits left due to floor operation. It will result into 32 − 30 = 2 bits.Step 7. The last fragment size LFz is calculated by adding the number of padded additional bits to the fragment size. In the case of above scenario, fragment size is 10 and additional bits are 2; therefore, the last fragment size equals 12 bits.Bitwise representation of this technique is elaborated in the following example where a 16-bit key1110011101010101 is divided into f=2 fragments that are 1110011100000000 and 0000000001010101. In this case the remainder Rem(16,2) = 0 that satisfies the if condition where fragment size is equal to 8 bit. The original key will be obtained by taking the XOR as follows:(3)00000000010101011110011100000000_1110011101010101.In another scenario, 16-bit key1110011101010101 is divided into f=3 fragments including 1110000000000000, 0000011101000000, and 0000000000010101. It is obvious that the first two fragments contain 5 key bits and 11 padded zeros whereas the last fragment contains one extra bit from the original key, that is, 6 bits of key and 10 zeros. In this case the remainder Rem(16,3) = 1 which is not equal to zero. Therefore the else part of algorithm (i.e., line (4)) is executed where the fragment size equals 5 and the last fragment size equals 6. By applying the XOR operation on these fragments, the original key is obtained as follows:(4)111000000000000000000111010000000000000000010101_1110011101010101.


### 4.2. Key Distribution Protocol (KDP)

The sender and receiver nodes establish the secret keys using KDP protocol. In this section, all the protocol steps are elaborated along with description of message contents for intra-actor distribution scenario. It includes senderSi, actors Ax, Ay, and receiver node Rk. KDP starts when the sender node Si randomly selects an actor node for sending one key fragment KFm and sends it to actor Ax encrypted with the association key it shares with Ax. Key fragment KFm represents the mth key fragment where 1≤m≤f. Ax is the actor node where x represents the randomly selected actor ID. The value of x could be any number from 1 to Q, which represents the total number of actors in the network. Node Si will encrypt the message (KFm, Rk, ni, ti, MAC(KFm∥ni∥ti)) using a shared preestablished key with the actor node Ax as described in (5). In the message, ni is nonce value, ti is timestamp, MAC(KFm∥ni∥ti) is hash of concatenated strings of KFm, and ni and ti are used to ensure integrity protection of key fragment and also guard against replay attacks:(5)C1=EKSi-AxKFm,Rk,ni,ti,MACKFm∥ni∥ti.Sender node Si sends the message (IDSi, C1) to actor node Ax.After receiving the message, actorAx decrypts the message, as per(6)KFm,Rk,ni,ti,MACKFm∥ni∥ti=DKSi-AxIDSi,C1.Actor Ax reencrypts the retrieved message using the association key KAx-Rk shared with the receiver node Rk, as shown in(7)C2=EKAx-SiKFm,ni,ti,MACKFm∥ni∥ti.Actor Ax sends the message (IDAx,C2) to the receiver node Rk.Upon receiving the message, the receiver nodeRk decrypts the message using its preestablished key with Ax, as illustrated in(8)KFm,ni,ti,MACKFm∥ni∥ti=DKAx-RkIDAx,C2.Actor Ay also reencrypts the message according to (9) by using the preestablished key between actor Ay and the receiver node Rk:(9)C3=EKAy-SiKFm+1,ni+1,ti+1,MACKFm+1∥ni+1∥ti+1.Actor Ay sends the message (IDAy,C3) to the receiver Node Rk.R
k then recovers KFm+1 as identified in (10) by using its preloaded association key KAy-Rk established with Ay:(10)KFm+1,ni+1,ti+1,MACKFm+1∥ni+1∥ti+1=DKAy-RkIDAy,C3.Finally Rk receives f key fragments and assimilates the pairwise key using (11) where × represents XOR operation:(11)KSi-Rk=KFm×KFm+1.For Interactor distribution scenario,Ax transmits the message to Bx and then Bx sends it to the receiver node Rk. Similarly Ay transmits via By to the receiver node Rk. Following additional messages are sent for interactor scenario:Ax→Bx: EKAx-Bx(KFm,ni,ti,MACKFm∥ni∥ti)Ay→By: EKAy-By(KFm+1,ni+1,ti+1,MACKFm+1∥ni+1∥ti+1)Bx→Rk: EKBx-Rk(KFm,ni,ti,MACKFm∥ni∥ti)By→Rk: EKBy-Rk(KFm+1,ni+1,ti+1,MACKFm+1∥ni+1∥ti+1).


## 4.1. Key Fragmentation Algorithm (KFA)

It is used by the sender node to divide the key intof fragments. If the key size is divisible by f then equal-sized fragments are produced like 32-bit key is divided into 2 fragments of size 16-bit each, but in case of 3 fragments the result will be two fragments of size 10 and the last fragment of size 12. The size of the last fragment is calculated as per line 7 in Pseudocode 1.Pseudocode 1:Key fragmentation.
(1)if Remainder of (keySize, f) is 0 then
(2)fragmentSize = keySize/f
(3)LFz  = fragmentSize
(4)else
(5)fragmentSize =  ⌞keySize/f⌟
(6)addBits = keySize − (fragmentSize * f)
(7)LFz  = fragmentSize + addBits
(8)end ifStep 1, 2. If a selected key size in bits is completely divisible by f, for example, a 32-bit key with f=2, then the remainder Rem(32,2) is zero. It produces 2 fragments of 16-bit each.Step 3. Last fragment size is equal to the fragment size because the key size is completely divisible.Step 4, 5. If the key size is not completely divisible by f, for example, a 32-bit key with f=3. In this case, the remainder Rem(32,3) is not zero. It will create three fragments of 10-bit each with a total of 30 bits and an extra fourth fragment of size 2-bit is also created. The last fragment is smaller than the selected fragment size, which is 10 in this case.Step 6. This problem is mitigated by calculating additional bits and then padded them to the last fragment. Initially a fragment size is calculated by dividing the key size by f and the floor is taken to get the lower value for the fragment size. If a key size is 32 with f=3 then the fragment size is 10. It will create (f-1) fragments of (fragmentSize×(f-1)) bits. It will produce two fragments of 20 bits when key size = 32, f=3 and fragment Size = 10. Additional number of bits required for padding for the last fragment is calculated by multiplying the fragment size by f to get the total size in bits of all fragments. Then, we ignore extra bits left due to floor operation. It will result into 32 − 30 = 2 bits.Step 7. The last fragment size LFz is calculated by adding the number of padded additional bits to the fragment size. In the case of above scenario, fragment size is 10 and additional bits are 2; therefore, the last fragment size equals 12 bits.Bitwise representation of this technique is elaborated in the following example where a 16-bit key1110011101010101 is divided into f=2 fragments that are 1110011100000000 and 0000000001010101. In this case the remainder Rem(16,2) = 0 that satisfies the if condition where fragment size is equal to 8 bit. The original key will be obtained by taking the XOR as follows:(3)00000000010101011110011100000000_1110011101010101.In another scenario, 16-bit key1110011101010101 is divided into f=3 fragments including 1110000000000000, 0000011101000000, and 0000000000010101. It is obvious that the first two fragments contain 5 key bits and 11 padded zeros whereas the last fragment contains one extra bit from the original key, that is, 6 bits of key and 10 zeros. In this case the remainder Rem(16,3) = 1 which is not equal to zero. Therefore the else part of algorithm (i.e., line (4)) is executed where the fragment size equals 5 and the last fragment size equals 6. By applying the XOR operation on these fragments, the original key is obtained as follows:(4)111000000000000000000111010000000000000000010101_1110011101010101.


## 4.2. Key Distribution Protocol (KDP)

The sender and receiver nodes establish the secret keys using KDP protocol. In this section, all the protocol steps are elaborated along with description of message contents for intra-actor distribution scenario. It includes senderSi, actors Ax, Ay, and receiver node Rk. KDP starts when the sender node Si randomly selects an actor node for sending one key fragment KFm and sends it to actor Ax encrypted with the association key it shares with Ax. Key fragment KFm represents the mth key fragment where 1≤m≤f. Ax is the actor node where x represents the randomly selected actor ID. The value of x could be any number from 1 to Q, which represents the total number of actors in the network. Node Si will encrypt the message (KFm, Rk, ni, ti, MAC(KFm∥ni∥ti)) using a shared preestablished key with the actor node Ax as described in (5). In the message, ni is nonce value, ti is timestamp, MAC(KFm∥ni∥ti) is hash of concatenated strings of KFm, and ni and ti are used to ensure integrity protection of key fragment and also guard against replay attacks:(5)C1=EKSi-AxKFm,Rk,ni,ti,MACKFm∥ni∥ti.Sender node Si sends the message (IDSi, C1) to actor node Ax.After receiving the message, actorAx decrypts the message, as per(6)KFm,Rk,ni,ti,MACKFm∥ni∥ti=DKSi-AxIDSi,C1.Actor Ax reencrypts the retrieved message using the association key KAx-Rk shared with the receiver node Rk, as shown in(7)C2=EKAx-SiKFm,ni,ti,MACKFm∥ni∥ti.Actor Ax sends the message (IDAx,C2) to the receiver node Rk.Upon receiving the message, the receiver nodeRk decrypts the message using its preestablished key with Ax, as illustrated in(8)KFm,ni,ti,MACKFm∥ni∥ti=DKAx-RkIDAx,C2.Actor Ay also reencrypts the message according to (9) by using the preestablished key between actor Ay and the receiver node Rk:(9)C3=EKAy-SiKFm+1,ni+1,ti+1,MACKFm+1∥ni+1∥ti+1.Actor Ay sends the message (IDAy,C3) to the receiver Node Rk.R
k then recovers KFm+1 as identified in (10) by using its preloaded association key KAy-Rk established with Ay:(10)KFm+1,ni+1,ti+1,MACKFm+1∥ni+1∥ti+1=DKAy-RkIDAy,C3.Finally Rk receives f key fragments and assimilates the pairwise key using (11) where × represents XOR operation:(11)KSi-Rk=KFm×KFm+1.For Interactor distribution scenario,Ax transmits the message to Bx and then Bx sends it to the receiver node Rk. Similarly Ay transmits via By to the receiver node Rk. Following additional messages are sent for interactor scenario:Ax→Bx: EKAx-Bx(KFm,ni,ti,MACKFm∥ni∥ti)Ay→By: EKAy-By(KFm+1,ni+1,ti+1,MACKFm+1∥ni+1∥ti+1)Bx→Rk: EKBx-Rk(KFm,ni,ti,MACKFm∥ni∥ti)By→Rk: EKBy-Rk(KFm+1,ni+1,ti+1,MACKFm+1∥ni+1∥ti+1).


## 5. KDFA Formal Specification

We have performed formal modeling using nonmonotonic cryptographic protocol (NCP) also called Rubin logic [13] to analyze and verify the KDFA protocol as per formal specifications. It validates the protocol as per standard requirements of cryptographic operations like authentication, message integrity, message freshness, encryption, decryption, and so forth. It also helps to identify the deficiencies in the proposed protocol and possibilities of compromise attacks. It is close to the actual implementation and flow of programming functions. In Rubin logic, the entities are assigned roles and a global set is also maintained where information about the protocol is maintained in these sets and it also maintains updated states of the users after each updateable operation. Global sets are accessible to all the member nodes and can be categorized into secret, observer, rule, and principal sets. A detailed discussion on formal specification for WSAN protocols is provided in [25, 28] along with appropriate case studies.We have reutilized the notations of KDFA predefined earlier in Table1 and a brief description is provided in Table 2 for all notations used in the following local set for formal specifications.Table 2
Notations of local set for KDFA.
Sr.
Notation
Description
1
K
F
m, KFm+1
First and second key fragment forf=2
2
P
S
i
F
m, PSiFm+1
Concatenated string atSi for the first and the second key fragment
3
M
1
–
M
2
Messages 1 to 2
4
C
1
–
C
5
Cipher texts ofM1 to M5
5
H
S
i
F
m, HSiFm+1
Hash calculated atSi for KFm  and KFm+1
6
H
∗, H∧
Hash of message (KFm, ni, ti) received at Ax and Rk for the first key fragment
7
H
+
Hash of message (KFm+1, ni+1, ti+1) received at Ay
8
H
~
Hash of concatenated reply message (ni, tk, HRk) from Rk
9
H
R
k
Hash calculated atRk for reply to Si
10
P
R
k
Concatenated string atRk for reply
11
m
c
Message count atRkA local set is maintained at each entity or node and can be categorized into possession POSS(), belief BEL(), and seen and behavior sets BL(). Detailed specification of this sets can be explored from [13, 16]. By applying Rubin logic on KDKF-AN, the local set is elaborated as follows and then its verification and analysis part provides a detailed overview of all sets maintained under the category of local set.Local Set for KDFA
(1)
Sender (Si)
POSS(Si) = {IDSi, KSi-Ax, KSi-Ay}
BEL(Si) = {#(IDSi), #(KSi-Ax), #(KSi-Ay)}
BL (Si) =
Hash(h(·); KFm,ni,ti) → HSiFm
Concat(KFm,ni,Rk,ti,HSiFm) → PSiFm
Encrypt({PSiFm}KSi-Ax) → C1
Send(Ax, {IDSi, C1}) → M1
Update(ni,ti,KFm)
Hash(h(·); KFm+1,ni+1,ti+1) → HSiFm+1
Concat(KFm+1,Rk,ni+1,ti+1,HSiFm+1) → PSiFm+1
Encrypt({PSiFm+1}KSi-Ay) → C2
Send(Ay, {IDSi, C2}) → M2
Update(ni+1, ti+1, KFm+1)
Receive(Rk, {IDRk, C5})
Split({IDRk, C5})
Decrypt({C5}KRk-Si) to get
[ni∗, tk, HRk]
Check-freshness(tAx-tk) ≥ Δt
if yes, then abort
Check(ni, ni∗)
MAC({Concat(ni, tk, HRk)}) → H~
Check(HRk, H~)
(2a)
Actor (Ax)
POSS(Ax) = {IDAx, KAx-Si, KAx-Rk}
BEL(Ax) = {#(IDAx), #(KAx-Si), #(KAx-Rk)}
BL(Ax) =
Receive(Si, {IDSi,C1})
Split({IDSi, C1})
Decrypt({C1}KAx-Si) to get
[KFm,Rk,ni,ti,HSiFm]
Check-freshness(tAx-ti) ≥ Δt
if yes, then abort
MAC({Concat (KFm, ni, ti)}) → H∗
Check(HSiFm, H∗)
Concat(KFm, ni, ti, HSiFm) → PAx
Encrypt({PAx}KAx-Rk) → C3
Send(Rk, {IDAx,C3}) → M3
Update(MID)
(2b)
Actor (Ay)
POSS(Ay) = {IDAy,KAy-Si,KAy-Ax,KAy-Rk}
BEL(Ay) = {#(IDAy), #(KAy-Si), #(KAy-Ax), #(KAy-Rk)}
BL(Ay) =
Receive(Si, {IDSi,C2})
Split({IDSi,C2})
Decrypt({C2}KAy-Si) to get
[KFm+1, Rk, ni+1, ti+1, HSiFm+1]
Check-freshness(tAy-ti+1) ≥ Δt
if yes, then abort
MAC({Concat(KFm+1, ni+1, ti+1)}) → H+
Check(HSiFm+1, H+)
Concat(KFm+1,ni+1,ti+1,HSiFm+1) → PAy
Encrypt({PAy}KAy-Rk) → C4
Send(Rk, {IDAy,C3}) → M4
Update(MID)
(3)
Receiver (Rk)
POSS(Rk) = {IDRk, KAy-Si, KAy-Si, mc}
BEL(Rk) = {#(IDRk), #(KAy-Si), #(KAy-Si), mc}
BL(Rk) =
Receive(Ax, {IDAx,C3})
Split({IDAx,C3})
Decrypt({C3}KAx-Rk) to get
[KFm,ni,ti,HSiFm]
Check-freshness(tk-ti) ≥ Δt
if yes, then abort
MAC({Concat(KFm,ni,ti)}) → H∧
Check(HSiFm,H∧)
INCR(mc,1)
Compare (mc equals f) if NO continue
XOR(KFm, KFm+1) → KRk-Si
Hash(h(·); ni, tk) → HRk
Concat(ni, tk, HRk) → PRk
Encrypt({PRk}KRk-Si) → C5
Send(Si, {IDRk, C5}) → M5
Update(MID).Local sets for all the entities including sender, receiver, and actor nodes are separately maintained. A possession set POSS(entity) contains all the parameters involved in encryption, decryption, and other operations performed at local memory of each entity as described in section below. A Behavior List BL() contains the list of operations and input arguments that are performed in near to implementation steps by entitiesSi, Ax, Ay, and Rk.


### 5.1. KDFA Analysis and Verification

In this section, KDFA is analyzed for intra-actor distribution scenario as discussed in Section4. In this scenario, the key distribution is initiated by the sender node (Si) by transmitting message M1 and M2 to actor node Ax and Ay, respectively, and by considering f=2 fragments. Rk receives the fragments and calculates the secret key. After sending operation, an update operation is performed to refresh the observer list as shown below.(i)
Concat(KFm, ni, Rk, ti, HSiFm) → PSiFm(ii)
Encrypt({PSiFm}KSi-Ax) → C1(iii)
Send(Ax, {IDSi,C1}) → M1(iv)
Update (ni, ti, KFm).Sender node further unicasts another message to actor node Ay for transmitting the second key fragment using message M2 towards receiver node Rk. The steps are similar whereas new parameters are included as shown below. (i)
Hash(h(·); KFm+1, ni+1, ti+1) → HSiFm+1(ii)
Concat(KFm+1, Rk, ni+1, ti+1, HSiFm+1) → PSiFm+1(iii)
Encrypt({PSiFm+1}KSi-Ay) → C2(iv)
Send(Ay, {IDSi,C2}) → M2(v)
Update(ni+1, ti+1, KFm+1).Related parameters including messages, ciphers, nonce values, actual key, key fragments, and hashes are saved in possession set at Si during the key establishment phase as shown below. POSS(Si) = {IDSi, KSi-Ax, KSi-Ay, PSiFm, ni, ti,KFm,HSiFmC1, M1, KFm+1, Rk,ni+1, ti+1,PSiFm+1,HSiFm+1, C2,M2, KSi-Rk}BEL(Si) = {#(IDSi),#(KSi-Ax),#(KSi-Ay)}.After sending two messages, control is passed to receive operation in appropriate actor node where messages are decrypted to retrieve concatenated message that are further split to get actual parameters. Freshness of message is checked by subtracting timestamp received ti, ti+1 from the actor’s timestamp tAx, tAy and if the answer is greater than the threshold Δt then further calculations are proceeded. Otherwise, message is discarded. MAC is also calculated as MAC({Concat(KFm, ni, ti)}) for concatenated parameters including KFm, ni, ti and compared to the hash values to ensure integrity protection. These operations, as shown in the following steps, are executed at actor node Ax and similar steps are followed by Ay with different parameters.(i)
Receive(Si, {IDSi,C1})(ii)
Split({IDSi,C1})(iii)
Decrypt({C1}KAx-Si) to get [KFm,Rk,ni,ti,HSiFm](iv)
Check-freshness(tAx-ti) ≥ Δt if yes, then abort(v)
MAC({Concat(KFm, ni, ti)}) → H∗(vi)
Check(HSiFm, H∗).Actor nodes Ax and Ay further send these key fragments towards the receiver node by encrypting with the preestablished key with receiver node Rk. (i)
Concat(KFm, ni, ti, HSiFm) → PAx(ii)
Encrypt({PAx}KAx-Rk) → C3(iii)
Send(Rk, {IDAx,C3}) → M3(iv)
Update(MID)(v)
Forget(PAx, ni, ti, KFm, Rk, C3, M3, H∗).Possession set at actor nodes Ax and Ay contains the following parameters during execution of the above-mentioned operations as shown below.POSS(Ax) = {IDAx, KAx-Si, KAx-Rk, PAx, Rk, ni, ti, KFm, C3, M3, H∗}BEL(Ax) = {#(IDAx), #(KAx-Si), #(KAx-Rk)}POSS(Ay) = {IDAy, KAy-Si, KAy-Rk, PAy, Rk, ni+1, ti+1, KFm+1, C4, M4, H+}BEL(Ay) = {#(IDAy), #(KAy-Si), #(KAy-Rk)}.Forget operation will result in removing these temporary values (PAx, ni, ti, KFm, Rk, C3, M3, H∗) from the possession set at Ax. Actor node Ay also performs the same operation with different parameters.The receiver nodeRk checks the freshness of message after decryption. Node Rk maintains a count in mc for key fragment messages, if mc is less than number of fragments f then Rk will continue to receive messages as shown in following steps.(i)
Receive(Ax, {IDAx, C3})(ii)
Split({IDAx, C3})(iii)
Decrypt({C3}KAx-Rk) to get [KFm, ni, ti, HSiFm](iv)
Check-freshness (tk-ti) ≥ Δt if yes, then abort(v)
MAC({Concat(KFm, ni, ti)}) → H∧(vi)
Check(HSiFm, H∧)(vii)
INCR(mc,1)(viii)
Compare(mc equals f) if no then continue.If mc is equal to f then Rk will apply the XOR operation on all the key fragments to calculate the actual key and then sends the acknowledgement message to the sender node Si as shown below.(i)
XOR(KFm, KFm+1) → KRk-Si(ii)
Hash(h(·); ni, tk) → HRk(iii)
Concat(ni, tk, HRk) → PRk(iv)
Encrypt(PRkKRk-Si) → C5(v)
Send(Si, {IDRk,C5}) → M5(vi)
Forget(PSiFm, ni, ti, KFm, HSiFm, H∧, C1, KFm+1, ni+1, ti+1, PSiFm+1, HSiFm+1, C3, HRk, PRk, C5, M5).Possession set values including nonce values ni, ni+1, time stamps ti, ti+1, key fragments KFm, KFm+1, cipher texts, C1, C3, and C5, hash values HSiFm, H∧, and HRk, concatenated strings PSiFm, PSiFm+1, and PRk, and secure keys are maintained at the receiver node Rk during the execution of the above-mentioned operations. POSS(Rk) = {IDRk,KRk-Ax, KRk-Ay, PSiFm, ni, ti, KFm, HSiFm, H∧, C1, KFm+1, ni+1, ti+1, PSiFm+1, HSiFm+1, C3, HRk, PRk, C5, M5, KRk-Si}BEL(Si) = {#(IDSi), #(KSi-Ax), #(KSi-Ay), #(KRk-Si)}.After execution of all steps, secure key KRk-Si is saved in belief set. Unnecessary values are removed by using Forget(PSiFm, ni, ti, KFm, HSiFm, H∧, C1, KFm+1, ni+1, ti+1, PSiFm+1, HSiFm+1, C3, HRk, PRk, C5, M5) operation after successful transmission of message from receiver Rk back to sender Si.The sender nodeSi receives the acknowledgement message M5 encrypted with currently established key KSi-Rk. Node Si decrypts the cipher text C5 to get [ni∗, tk, HRk] and verify the nonce value as shown in the following steps.(i)
Receive(Rk, {IDRk,C5})(ii)
Split({IDRk,C5})(iii)
Decrypt({C5}KRk-Si) to get [ni∗, tk, HRk](iv)
Check-freshness(tAx-tk) ≥ ΔT if yes, then abort(v)
Check(ni, ni∗)(vi)
MAC({Concat(ni, tk, HRk)}) → H~(vii)
Check(HRk, H~)(viii)
Forget(PSiFm, ni, ti, KFm, HSiFm, C1, M1, KFm+1, ni+1, ti+1, PSiFm+1, HSiFm+1, C2, M2).Possession set at Si is refreshed after the completion of key distribution process and receiving the acknowledging message from the receiver node Rk. Secret key KSi-Rk is also saved in the belief set. Si executes the above-mentioned Forget (PSiFm, ni, ti, KFm, HSiFm, C1, M1, KFm+1, ni+1, ti+1, PSiFm+1, HSiFm+1, C2, M2) operation to clear the unnecessary values from possession set that is shown below.POSS(Si) = {IDSi,KSi-Ax,KSi-Ay,KSi-Rk}BEL(Si) = {#(IDSi),#(KSi-Ax),#(KSi-Ay),#(KSi-Rk)}.


## 5.1. KDFA Analysis and Verification

In this section, KDFA is analyzed for intra-actor distribution scenario as discussed in Section4. In this scenario, the key distribution is initiated by the sender node (Si) by transmitting message M1 and M2 to actor node Ax and Ay, respectively, and by considering f=2 fragments. Rk receives the fragments and calculates the secret key. After sending operation, an update operation is performed to refresh the observer list as shown below.(i)
Concat(KFm, ni, Rk, ti, HSiFm) → PSiFm(ii)
Encrypt({PSiFm}KSi-Ax) → C1(iii)
Send(Ax, {IDSi,C1}) → M1(iv)
Update (ni, ti, KFm).Sender node further unicasts another message to actor node Ay for transmitting the second key fragment using message M2 towards receiver node Rk. The steps are similar whereas new parameters are included as shown below. (i)
Hash(h(·); KFm+1, ni+1, ti+1) → HSiFm+1(ii)
Concat(KFm+1, Rk, ni+1, ti+1, HSiFm+1) → PSiFm+1(iii)
Encrypt({PSiFm+1}KSi-Ay) → C2(iv)
Send(Ay, {IDSi,C2}) → M2(v)
Update(ni+1, ti+1, KFm+1).Related parameters including messages, ciphers, nonce values, actual key, key fragments, and hashes are saved in possession set at Si during the key establishment phase as shown below. POSS(Si) = {IDSi, KSi-Ax, KSi-Ay, PSiFm, ni, ti,KFm,HSiFmC1, M1, KFm+1, Rk,ni+1, ti+1,PSiFm+1,HSiFm+1, C2,M2, KSi-Rk}BEL(Si) = {#(IDSi),#(KSi-Ax),#(KSi-Ay)}.After sending two messages, control is passed to receive operation in appropriate actor node where messages are decrypted to retrieve concatenated message that are further split to get actual parameters. Freshness of message is checked by subtracting timestamp received ti, ti+1 from the actor’s timestamp tAx, tAy and if the answer is greater than the threshold Δt then further calculations are proceeded. Otherwise, message is discarded. MAC is also calculated as MAC({Concat(KFm, ni, ti)}) for concatenated parameters including KFm, ni, ti and compared to the hash values to ensure integrity protection. These operations, as shown in the following steps, are executed at actor node Ax and similar steps are followed by Ay with different parameters.(i)
Receive(Si, {IDSi,C1})(ii)
Split({IDSi,C1})(iii)
Decrypt({C1}KAx-Si) to get [KFm,Rk,ni,ti,HSiFm](iv)
Check-freshness(tAx-ti) ≥ Δt if yes, then abort(v)
MAC({Concat(KFm, ni, ti)}) → H∗(vi)
Check(HSiFm, H∗).Actor nodes Ax and Ay further send these key fragments towards the receiver node by encrypting with the preestablished key with receiver node Rk. (i)
Concat(KFm, ni, ti, HSiFm) → PAx(ii)
Encrypt({PAx}KAx-Rk) → C3(iii)
Send(Rk, {IDAx,C3}) → M3(iv)
Update(MID)(v)
Forget(PAx, ni, ti, KFm, Rk, C3, M3, H∗).Possession set at actor nodes Ax and Ay contains the following parameters during execution of the above-mentioned operations as shown below.POSS(Ax) = {IDAx, KAx-Si, KAx-Rk, PAx, Rk, ni, ti, KFm, C3, M3, H∗}BEL(Ax) = {#(IDAx), #(KAx-Si), #(KAx-Rk)}POSS(Ay) = {IDAy, KAy-Si, KAy-Rk, PAy, Rk, ni+1, ti+1, KFm+1, C4, M4, H+}BEL(Ay) = {#(IDAy), #(KAy-Si), #(KAy-Rk)}.Forget operation will result in removing these temporary values (PAx, ni, ti, KFm, Rk, C3, M3, H∗) from the possession set at Ax. Actor node Ay also performs the same operation with different parameters.The receiver nodeRk checks the freshness of message after decryption. Node Rk maintains a count in mc for key fragment messages, if mc is less than number of fragments f then Rk will continue to receive messages as shown in following steps.(i)
Receive(Ax, {IDAx, C3})(ii)
Split({IDAx, C3})(iii)
Decrypt({C3}KAx-Rk) to get [KFm, ni, ti, HSiFm](iv)
Check-freshness (tk-ti) ≥ Δt if yes, then abort(v)
MAC({Concat(KFm, ni, ti)}) → H∧(vi)
Check(HSiFm, H∧)(vii)
INCR(mc,1)(viii)
Compare(mc equals f) if no then continue.If mc is equal to f then Rk will apply the XOR operation on all the key fragments to calculate the actual key and then sends the acknowledgement message to the sender node Si as shown below.(i)
XOR(KFm, KFm+1) → KRk-Si(ii)
Hash(h(·); ni, tk) → HRk(iii)
Concat(ni, tk, HRk) → PRk(iv)
Encrypt(PRkKRk-Si) → C5(v)
Send(Si, {IDRk,C5}) → M5(vi)
Forget(PSiFm, ni, ti, KFm, HSiFm, H∧, C1, KFm+1, ni+1, ti+1, PSiFm+1, HSiFm+1, C3, HRk, PRk, C5, M5).Possession set values including nonce values ni, ni+1, time stamps ti, ti+1, key fragments KFm, KFm+1, cipher texts, C1, C3, and C5, hash values HSiFm, H∧, and HRk, concatenated strings PSiFm, PSiFm+1, and PRk, and secure keys are maintained at the receiver node Rk during the execution of the above-mentioned operations. POSS(Rk) = {IDRk,KRk-Ax, KRk-Ay, PSiFm, ni, ti, KFm, HSiFm, H∧, C1, KFm+1, ni+1, ti+1, PSiFm+1, HSiFm+1, C3, HRk, PRk, C5, M5, KRk-Si}BEL(Si) = {#(IDSi), #(KSi-Ax), #(KSi-Ay), #(KRk-Si)}.After execution of all steps, secure key KRk-Si is saved in belief set. Unnecessary values are removed by using Forget(PSiFm, ni, ti, KFm, HSiFm, H∧, C1, KFm+1, ni+1, ti+1, PSiFm+1, HSiFm+1, C3, HRk, PRk, C5, M5) operation after successful transmission of message from receiver Rk back to sender Si.The sender nodeSi receives the acknowledgement message M5 encrypted with currently established key KSi-Rk. Node Si decrypts the cipher text C5 to get [ni∗, tk, HRk] and verify the nonce value as shown in the following steps.(i)
Receive(Rk, {IDRk,C5})(ii)
Split({IDRk,C5})(iii)
Decrypt({C5}KRk-Si) to get [ni∗, tk, HRk](iv)
Check-freshness(tAx-tk) ≥ ΔT if yes, then abort(v)
Check(ni, ni∗)(vi)
MAC({Concat(ni, tk, HRk)}) → H~(vii)
Check(HRk, H~)(viii)
Forget(PSiFm, ni, ti, KFm, HSiFm, C1, M1, KFm+1, ni+1, ti+1, PSiFm+1, HSiFm+1, C2, M2).Possession set at Si is refreshed after the completion of key distribution process and receiving the acknowledging message from the receiver node Rk. Secret key KSi-Rk is also saved in the belief set. Si executes the above-mentioned Forget (PSiFm, ni, ti, KFm, HSiFm, C1, M1, KFm+1, ni+1, ti+1, PSiFm+1, HSiFm+1, C2, M2) operation to clear the unnecessary values from possession set that is shown below.POSS(Si) = {IDSi,KSi-Ax,KSi-Ay,KSi-Rk}BEL(Si) = {#(IDSi),#(KSi-Ax),#(KSi-Ay),#(KSi-Rk)}.


## 6. Simulation and Results

For simulation, we have used ns-2.35 on Fedora Core 12. During simulation scenarios, C language is used for providing send and receive functionalities along with packet formats for sensor nodes, actors, and sink. Encryption, decryption, fragmentation, and hash functions are also provided in C. Tcl is used to create nodes, deployment of network field, and linking the nodes. Messages scenarios are also exchanged as per KDP specifications. In WSAN, nodes and actors are randomly deployed in a region of 1200 × 1200 meters where nodes were static and actors can move within the network field. We have focused on providing key distribution services and data collection scenario is left for future work. Transmission range of nodes is set to 40 meters with different network sizes from 100 to 1000 nodes. It also includes 5 to 20 powerful actor nodes. Queue type is set to Queue/DropTail/PriQue as shown in Table3.Table 3
Simulation parameters.
Simulation Setup
Parameters
Values
Network field
1200 × 1200 meters
Actor Tx radius
300 m
Initial energy at node
1000 J
Tx power at node
0.819 J
Receiving power
0.049 J
Physical type
Wireless physical
Queue type
Queue/DropTail/PriQue
Antenna type
Omni antenna
Max packet in queue
50
Routing protocol
DSDV
Agent trace
ON
Router trace
ON


### 6.1. Resilience

During interactor communication (IAC) two ordinary nodes from different regions communicate using two actor nodes. The probability that an actor node being compromised in the path can be calculated using (12), where N is the network size and cp is the number of nodes captured by an attacker in the network:(12)PNAC=N-3cpN-2cp.The total number of uncompromised nodesN-2 means that 2 ordinary nodes are excluded from compromised nodes in network whereas N-3 represents the further exclusion of one actor node. The probability that a certain actor node is captured at either sender or receiver side can be calculated using(13)PAC=1-PNAC=cpN-2.Considering the scenario of dividing a key into two fragments, we can calculate the probability of capturing exactlyf=2 actor nodes that are randomly selected for IAC as PACF=2=PAC×PAC. We simulated KDFA scheme for a network of 1000 ordinary nodes with a transmission range of 40 meters and 50 actor nodes with transmission range of 250 meters.Results in Figure7(a) show that if 150 nodes are captured then there are 15% of chances to capture one actor node in the path. In case of fragmentation, there are only 2% for f=2 and 0.3% for f=3, which are exactly those actor nodes that are randomly selected to transmit the key fragments. Figure 7(b) further evaluates the scenario when more than 60% of the nodes are compromised. If 600 nodes are compromised then there are only 13% of chances for f=4, 21.7% for f=3, and 36% for f=2 scenario that f Actor nodes are captured. Hence resilience is very much improved due to fragmentation.Figure 7
Probability of an actor node being compromised when less than 40% nodes in the entire network are captured in (a) and more than 60% in (b).
(a)
(b)


### 6.2. Fragmentation Computation Cost

A key fragment size is calculated using KFA as discussed in Section4.1 where the size of the last fragment varies in case of odd number of fragments. Additional bits are added to last fragment as illustrated in step 7 and that is used to generate (14), where Lf is the size of the last fragment, Kz is the key size, and f is the number of fragments. The last key fragment size dependents on the remainder of Kz/f operation:(14)Lf=Kz+Kzf1-f.Figure8(a) shows the size of the last fragment by selecting f=2,3 and 4 key fragmentation scenarios for distributing the keys of sizes 16 bits, 32 bits, 64 bits, and 128 bits. In case of f=3 fragments, last fragment size is 24 bits whereas initial two fragments are 20 bits for distributing a 64-bit key. These 4 extra bits are produced because Kz is indivisible by f. Figure 8(b) illustrates the size of the initial key fragments. By considering a 32-bit bit scenario for f=3 fragments, the size of the initial two fragments is 10 bits. In case of even value for f, the last fragment size is the same as the initial key fragments.Figure 8
Size in bits of the last fragment in (a) and size of initial fragments in (b) where the number of total fragments isf=2,3,4.
(a)
(b)


### 6.3. Communication Overhead Analysis

In KDFA, the number of messages (MC) transmitted during intra- or interactor communication scenarios can be calculated using (15) where f represents the number of fragments. In this equation, MN and MA represent the number of messages transmitted by ordinary node and actor, respectively, during intra- or interactor communication scenario without fragmentation:(15)MC=MN+MA×f.In case of intra-actor communication,MN=MA=1 because the actual key was sent in single message like NEKM [20]. By applying fragmentation, the value of MC=4 for f=2 fragments using (15). Similarly, in interactor communication scenario, MN=1 and MA=2 and MC=6 for f=2 fragments using (15). Our main concern is to calculate the communication cost incurred by ordinary nodes. Therefore, we have ignored the value of MA. A sender transmits (MN×f) messages to actor nodes, and hence f-1 extra messages are sent by ordinary node due to fragmentation. If 2 key fragments are exchanged then only 2 messages are sent by the ordinary nodes to actors where 1 message is extra as compared to fragmentation less scenarios.An ordinary node can establish indirect keys with distant sensor nodes in outer circle of its transmission range as illustrated in Figure9(a). The total communication cost for indirect keying (TMC) can be calculated using (16) where NOC represents the total number of nodes in outer circle:(16)TMC=NOC×MN+MA×f.Figure 9(a) illustrates that if an ordinary node establishes keys with 6 nodes in its outer circle then 12 messages are exchanged by that node for f=2 key fragments. The same number of messages was sent in STSK [10] where an ordinary node was used as intermediary to exchange a single actual key per message without fragmentation. In NEKM [20], only 6 messages were sent to 6 nodes for key distribution using single actor without fragmentation. Message size for exchanging key fragment is 14 bytes that contains 16-bit sender ID, 32-bit key fragment, 16-bit nonce value, 16-bit timestamp, and 32-bit hash value according to (5). Our scheme requires extra 14 bytes to transmit one extra message in case of f=2 but such a little amount of overhead ensures the secure key distribution in severe environments even when a large number of nodes or actors are compromised. Fragmentation is only required for indirect key establishment that is less frequent as compared to direct keying. Once the key is distributed then that key is reused for future communication between these two nodes.Figure 9
(a) Effects of key fragmentation on communication overhead. (b) Probability of links between nodes and actors.
(a)
(b)M intra and M inter represent the values of communication cost (MC) for both scenarios. In this case, ordinary node transmits 12 messages for NOC=6 and f=2 in both intra- and interactor communication scenarios. The sender transmits the same number of messages to actors whether intra-, interactor, or hybrid communication scenarios is adopted by actors.If there areQ actor nodes in the network then PActor=N-1Q-1/NQ is the probability that a certain node is an actor. A node being an ordinary node could be identified with a probability (1-PActor). The probability of establishing links with gateway nodes at one end is PActor×(1-PActor). Figure 9(b) elucidates that in case of 50 actors in a network of 1000 nodes, only 9.5% links are established between actors and nodes, 90% between nodes, and only 0.2% between actors. By referring to these probabilities, we can claim that the chances of intra-actor communication are higher than the interactor communication scenarios.


## 6.1. Resilience

During interactor communication (IAC) two ordinary nodes from different regions communicate using two actor nodes. The probability that an actor node being compromised in the path can be calculated using (12), where N is the network size and cp is the number of nodes captured by an attacker in the network:(12)PNAC=N-3cpN-2cp.The total number of uncompromised nodesN-2 means that 2 ordinary nodes are excluded from compromised nodes in network whereas N-3 represents the further exclusion of one actor node. The probability that a certain actor node is captured at either sender or receiver side can be calculated using(13)PAC=1-PNAC=cpN-2.Considering the scenario of dividing a key into two fragments, we can calculate the probability of capturing exactlyf=2 actor nodes that are randomly selected for IAC as PACF=2=PAC×PAC. We simulated KDFA scheme for a network of 1000 ordinary nodes with a transmission range of 40 meters and 50 actor nodes with transmission range of 250 meters.Results in Figure7(a) show that if 150 nodes are captured then there are 15% of chances to capture one actor node in the path. In case of fragmentation, there are only 2% for f=2 and 0.3% for f=3, which are exactly those actor nodes that are randomly selected to transmit the key fragments. Figure 7(b) further evaluates the scenario when more than 60% of the nodes are compromised. If 600 nodes are compromised then there are only 13% of chances for f=4, 21.7% for f=3, and 36% for f=2 scenario that f Actor nodes are captured. Hence resilience is very much improved due to fragmentation.Figure 7
Probability of an actor node being compromised when less than 40% nodes in the entire network are captured in (a) and more than 60% in (b).
(a)
(b)


## 6.2. Fragmentation Computation Cost

A key fragment size is calculated using KFA as discussed in Section4.1 where the size of the last fragment varies in case of odd number of fragments. Additional bits are added to last fragment as illustrated in step 7 and that is used to generate (14), where Lf is the size of the last fragment, Kz is the key size, and f is the number of fragments. The last key fragment size dependents on the remainder of Kz/f operation:(14)Lf=Kz+Kzf1-f.Figure8(a) shows the size of the last fragment by selecting f=2,3 and 4 key fragmentation scenarios for distributing the keys of sizes 16 bits, 32 bits, 64 bits, and 128 bits. In case of f=3 fragments, last fragment size is 24 bits whereas initial two fragments are 20 bits for distributing a 64-bit key. These 4 extra bits are produced because Kz is indivisible by f. Figure 8(b) illustrates the size of the initial key fragments. By considering a 32-bit bit scenario for f=3 fragments, the size of the initial two fragments is 10 bits. In case of even value for f, the last fragment size is the same as the initial key fragments.Figure 8
Size in bits of the last fragment in (a) and size of initial fragments in (b) where the number of total fragments isf=2,3,4.
(a)
(b)


## 6.3. Communication Overhead Analysis

In KDFA, the number of messages (MC) transmitted during intra- or interactor communication scenarios can be calculated using (15) where f represents the number of fragments. In this equation, MN and MA represent the number of messages transmitted by ordinary node and actor, respectively, during intra- or interactor communication scenario without fragmentation:(15)MC=MN+MA×f.In case of intra-actor communication,MN=MA=1 because the actual key was sent in single message like NEKM [20]. By applying fragmentation, the value of MC=4 for f=2 fragments using (15). Similarly, in interactor communication scenario, MN=1 and MA=2 and MC=6 for f=2 fragments using (15). Our main concern is to calculate the communication cost incurred by ordinary nodes. Therefore, we have ignored the value of MA. A sender transmits (MN×f) messages to actor nodes, and hence f-1 extra messages are sent by ordinary node due to fragmentation. If 2 key fragments are exchanged then only 2 messages are sent by the ordinary nodes to actors where 1 message is extra as compared to fragmentation less scenarios.An ordinary node can establish indirect keys with distant sensor nodes in outer circle of its transmission range as illustrated in Figure9(a). The total communication cost for indirect keying (TMC) can be calculated using (16) where NOC represents the total number of nodes in outer circle:(16)TMC=NOC×MN+MA×f.Figure 9(a) illustrates that if an ordinary node establishes keys with 6 nodes in its outer circle then 12 messages are exchanged by that node for f=2 key fragments. The same number of messages was sent in STSK [10] where an ordinary node was used as intermediary to exchange a single actual key per message without fragmentation. In NEKM [20], only 6 messages were sent to 6 nodes for key distribution using single actor without fragmentation. Message size for exchanging key fragment is 14 bytes that contains 16-bit sender ID, 32-bit key fragment, 16-bit nonce value, 16-bit timestamp, and 32-bit hash value according to (5). Our scheme requires extra 14 bytes to transmit one extra message in case of f=2 but such a little amount of overhead ensures the secure key distribution in severe environments even when a large number of nodes or actors are compromised. Fragmentation is only required for indirect key establishment that is less frequent as compared to direct keying. Once the key is distributed then that key is reused for future communication between these two nodes.Figure 9
(a) Effects of key fragmentation on communication overhead. (b) Probability of links between nodes and actors.
(a)
(b)M intra and M inter represent the values of communication cost (MC) for both scenarios. In this case, ordinary node transmits 12 messages for NOC=6 and f=2 in both intra- and interactor communication scenarios. The sender transmits the same number of messages to actors whether intra-, interactor, or hybrid communication scenarios is adopted by actors.If there areQ actor nodes in the network then PActor=N-1Q-1/NQ is the probability that a certain node is an actor. A node being an ordinary node could be identified with a probability (1-PActor). The probability of establishing links with gateway nodes at one end is PActor×(1-PActor). Figure 9(b) elucidates that in case of 50 actors in a network of 1000 nodes, only 9.5% links are established between actors and nodes, 90% between nodes, and only 0.2% between actors. By referring to these probabilities, we can claim that the chances of intra-actor communication are higher than the interactor communication scenarios.


## 7. Conclusion

Key distribution schemes require agent nodes as intermediaries to establish keys between distant nodes. A compromised actor node can reveal all the keys passing through that node. Therefore, we have proposed a lightweight key fragmentation and assimilation scheme to mitigate the key exposure problem. Rubin logic is applied to model the proposed scheme KDFA and analysis is also performed to evaluate its accuracy of cryptographic operations and transmissions. Simulation results show the effectiveness of the proposed scheme over contemporary schemes in literature. According to results, 75% of communication is compromised in existing schemes whereas the proposed KDFA has the probability of exposing only 13% of communication when 60% of nodes are compromised. In the proposed scheme, sender transmits extra 14 bytes during key distribution process but using powerful actor nodes reduces the overhead for those messages exchanged through actors. In future, the proposed scheme will be analyzed to measure the effects of poor interactor connectivity on data extraction and aggregation.



---

*Source: 542856-2015-09-27.xml*