# PUF-Based Mutual-Authenticated Key Distribution for Dynamic Sensor Networks

Authors: Yanan Liu; Yijun Cui; Lein Harn; Zheng Zhang; Hao Yan; Yuan Cheng; Shuo Qiu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Because of the movements of sensor nodes and unknown mobility pattern, how to ensure two communicating (static or mobile) nodes authenticate and share a pairwise key is important. In this paper, we propose a mutual-authenticated key distribution scheme based on physical unclonable functions (PUFs) for dynamic sensor networks. Compared with traditional key predistribution schemes, the proposal reduces the storage overhead and the key exposure risks and thereby improves the resilience against node capture attacks. Mutual authentication is provided by the PUF challenge-response mechanism. However, the PUF response is not transmitted in plain forms so as to resist the modelling attacks, which is vulnerable in some existing PUF-based schemes. We demonstrate the proposed scheme to improve the secure connectivity and other performances by analysis and experiments.


---

## Body

## 1. Introduction

Many applications of wireless sensor networks (WSNs) are working in hostile battlefield environments or unmanned areas with poor conditions. Sensor nodes and wireless channels are vulnerable to malicious attacks, such as physical capture nodes, data tampering, and side channel attacks [1–3]. Data encryption is a crucial technology to ensure secure communication between the cloud and end-devices [4–6]. The authentication and key distribution are the premise and foundation [7, 8].In 2002, Eschenauer and Gligor proposed a random key predistribution scheme [9] for the resource limited sensors. In 2007, Du et al. applied Eschenauer’s scheme into hierarchical sensor networks and proposed an asymmetric key predistribution scheme (AP) [10]. This kind of “probabilistic” schemes had low computation and communication overhead but cannot ensure that any two of communicating nodes share a pairwise key. Besides, the key storage amount showed a tradeoff between the network connectivity and resilience against node capture attacks. In 2009, Boujelben proposed a key management scheme based on the Blom matrix [11] to improve the resilience against node capture; however, the computation cost for matrix operation was too complicated for common sensors [12]. In terms of public key algorithms, in 2012, Benamar et al. [13] proposed a dynamic security key management model for hierarchical sensor networks based on public key infrastructure (PKI). In 2015, Lee and Kim [14] proposed a key renewal scheme with sensor authentication under clustered wireless sensor networks based on modular exponentiation which was similar to the Diffie–Hellman key exchange. These schemes increased the connectivity; however, the public key computational overhead was too large for sensors. In 2010, Han et al. [15] proposed an approach for dynamic node authentication and key exchange, which reduces the overhead of mobile node reauthentication. Each sink node authenticates other neighboring sink and sensor nodes and supports reauthentication with less communication and computation overhead. In 2015, Erfani et al. [16] proposed a key management scheme, which used key predistribution and postdeployment key establishment mechanisms for dynamic sensor networks. The predistributed keys are loaded to the memory of sensor nodes before network deployment, and after that, some postdeployment keys are generated and stored in each sensor node. In Erfani’s approach, the base station is involved in intracluster authentication and key distribution, which costs too much communication overheads. In 2020, Tian et al. [17] proposed a blockchain-based secure key management scheme with trustworthiness in dynamic wireless sensor networks, which designed a secure cluster formation algorithm and a secure node movement algorithm to implement key management.This paper proposed a mutual authenticated key distribution scheme based on physical unclonable functions (PUFs) in dynamic sensor networks, so as to help the sink node to authenticate and distribute session keys to the static and mobile sensors. Lightweight mutual authentication is guaranteed by a challenge-response mechanism based on the PUF. To address the PUF challenge-response pairs (CRPs) exposure problem, the CRPs are not transmitted as plaintext in order to resist the modelling attack to PUF. In addition, sensors are not required to prestore any keys in memory, which not only saves the storage overhead but also improves the resilience against sensor node capture attacks.


## 2. Physical Unclonable Function (PUF)

### 2.1. Review of PUFs

Physical unclonable function (PUF) is a new encryption component that can extract random differences introduced by inconsistencies in manufacturing processes between gate circuits or connection lines (wires) in integrated circuits (IC). These random differences can be used to generate an encrypted (response) signal with certain rules [18]. Random differences in a physical object can be interpreted as the unique “fingerprint” of a hardware instant. In addition to IC PUFs [19], there are silicon PUFs [20], coated PUFs [21], and so on. We use a one-way mapping function P to describe PUF, which can be expressed as(1)P:C⟶R:Pc=r,c∈C,r∈R.The functional mapping between inputc and output r is instance-specific and unpredictable prior to the actual fabrication of the circuit. When an electrical stimulus is applied to the structure, it reacts in an unpredictable (but instance-wise repeatable) manner due to the complex interaction of the stimulus with the physical microstructure of the device. The exact nature of this microstructure depends on physical factors introduced during manufacturing. The applied stimulus is considered as the “challenge,” while the reaction generated by the PUF is considered as the “response.” A specific challenge and its response together form a challenge-response pair (CRP) (c, r), and the CRP dataset acts as a unique fingerprint for the instance.The attractive features of PUFs are light-weightiness, unpredictability, unclonability, and uniqueness, which make PUFs valuable in designing ultralightweight authentication, key generation, and other security protocols [22, 23]. Device authentication is the process that an authenticator verifies the identity of a device client before communication. PUF CRP can be implemented in the challenge-response authentication mechanism. The authenticator creates a CRP database that stores all the challenges and their expected responses from registered clients. To verify the identity of a client, the authenticator first selects a challenge from the database and sends it to the client. The client generates a response to the challenge using its on-board PUF and provides it to the authenticator. By comparing the current client’s response against the one stored in the CRP database, the authenticator infers whether the client is trusted or not.This new type of schemes speeds up the authentication process and also lightens the key storage and thereby reduces key exposure risk. A PUF with a large enough challenge space to make exhaustive enumeration of its CRP set infeasible is termed a strong PUF and is the PUFs of choice in most practical security applications. We keep ourselves confined to strong PUFs in this work. Since the assessment of a PUF implies a physical measurement, it is very susceptible to circuit noise. Hence, to make it reliable and to have full entropy, [22] had proposed an error correction circuit with a very low hardware overhead to reduce the fuzziness of the PUF’s responses and make it more robust and reliable. However, in our work, we consider each PUF structure as a black-box challenge-response system, where a set of challenges are available and the system responds with a set of sufficiently different responses.In 2015, Allam proposed a scheme that depends on the physical layer mechanisms, which consist of PUF and Channel Status Information (CSI) for providing point-to-point real-time hardware-based authentication technique between two parties communicating directly through wireless media and effective key exchange to assure an authenticated secure channel between them [23]. In 2013, Bahrampour and Atani proposed a Key Management Protocol for Wireless Sensor Networks based on PUFs, in which the PUFs were used to design the public keys [24]. In 2017, Chatterjee et al. proposed a PUF-based secure communication protocol for PUF [25]. The PUF was used to generate the public key based on the bilinear pairing of each device in the key agreement protocol. In 2018, Braeken improved Chatterjee’s protocol efficiency by way of employing the Elliptic Curve Qu Vanstone (ECQV) [26]. In 2019, Li et al. proposed a PUF-based secure communication system for the Internet of Things [27]. In 2020, Zhang et al. proposed a PUF-based Key Distribution in Wireless Sensor Networks [28].


### 2.2. Configurable RO PUFs

The PUF circuit, which is the core of authentication and key distribution in our scheme, should be easily implemented on the FPGA with good uniqueness and reliability. In our previous work, several types of configurable RO PUF are proposed, including MUX based RRO PUF in [29], XOR gate based XCRO PUF in [30], and tristate configurable TCRO PUF in [31]. In this paper, the MUX based RRO PUF is chosen. The MUX based configurable RO (CRO) PUF was first introduced in [32], where each ring oscillator can be reconfigured by using a multiplexer to select one of two inverters that are connected to the multiplexer to form an RO. Our reconfigurable RRO design, as shown in Figure 1, is consisted of a chain of inverter delay units and an AND gate delay unit. When the configurable signal of a MUX is “0,” the upper path will be chosen. On the contrary, when the signal is “1,” the lower path will be chosen to construct the RO structure. The configure procedure extracts the transfer difference of each MUX and the delay of the upper and lower path.Figure 1
RRO PUF structure.


### 2.3. Implement of PUFs

The PUF used in our approach is implemented and studied based on Xilinx SoC FPGAs and will be applied to real-world scenarios based on ASIC or SoC FPGA including ARM core (e.g., Xilinx Zynq-7000 series, Altera SoC or Microsemi Smart Fusion2) after validation. As shown in Figure2, the main components include MUX, XOR gate, inverters, and AND gate. In the implementation of the RRO PUF, the primitive MUXF7 is chosen for the multiplexer, the primitive LUT1 is adopted for the inverter, and LUT2 is utilized for the AND gate. Eight delay units that include seven inverter delay units and one AND gate delay unit are included in the single RRO array. Each delay unit occupies one slice and two delay units can be implemented in one configurable logic block (CLB). Therefore, four CLBs are needed to implement one RRO PUF array. In order to make sure that all RROs are identically routed, they are created as hard macros to avoid the bias introduced in the placement and routing. The detailed design can be referred in authors’ previous work [29].Figure 2
Implementation of an RRO in a CLB.


## 2.1. Review of PUFs

Physical unclonable function (PUF) is a new encryption component that can extract random differences introduced by inconsistencies in manufacturing processes between gate circuits or connection lines (wires) in integrated circuits (IC). These random differences can be used to generate an encrypted (response) signal with certain rules [18]. Random differences in a physical object can be interpreted as the unique “fingerprint” of a hardware instant. In addition to IC PUFs [19], there are silicon PUFs [20], coated PUFs [21], and so on. We use a one-way mapping function P to describe PUF, which can be expressed as(1)P:C⟶R:Pc=r,c∈C,r∈R.The functional mapping between inputc and output r is instance-specific and unpredictable prior to the actual fabrication of the circuit. When an electrical stimulus is applied to the structure, it reacts in an unpredictable (but instance-wise repeatable) manner due to the complex interaction of the stimulus with the physical microstructure of the device. The exact nature of this microstructure depends on physical factors introduced during manufacturing. The applied stimulus is considered as the “challenge,” while the reaction generated by the PUF is considered as the “response.” A specific challenge and its response together form a challenge-response pair (CRP) (c, r), and the CRP dataset acts as a unique fingerprint for the instance.The attractive features of PUFs are light-weightiness, unpredictability, unclonability, and uniqueness, which make PUFs valuable in designing ultralightweight authentication, key generation, and other security protocols [22, 23]. Device authentication is the process that an authenticator verifies the identity of a device client before communication. PUF CRP can be implemented in the challenge-response authentication mechanism. The authenticator creates a CRP database that stores all the challenges and their expected responses from registered clients. To verify the identity of a client, the authenticator first selects a challenge from the database and sends it to the client. The client generates a response to the challenge using its on-board PUF and provides it to the authenticator. By comparing the current client’s response against the one stored in the CRP database, the authenticator infers whether the client is trusted or not.This new type of schemes speeds up the authentication process and also lightens the key storage and thereby reduces key exposure risk. A PUF with a large enough challenge space to make exhaustive enumeration of its CRP set infeasible is termed a strong PUF and is the PUFs of choice in most practical security applications. We keep ourselves confined to strong PUFs in this work. Since the assessment of a PUF implies a physical measurement, it is very susceptible to circuit noise. Hence, to make it reliable and to have full entropy, [22] had proposed an error correction circuit with a very low hardware overhead to reduce the fuzziness of the PUF’s responses and make it more robust and reliable. However, in our work, we consider each PUF structure as a black-box challenge-response system, where a set of challenges are available and the system responds with a set of sufficiently different responses.In 2015, Allam proposed a scheme that depends on the physical layer mechanisms, which consist of PUF and Channel Status Information (CSI) for providing point-to-point real-time hardware-based authentication technique between two parties communicating directly through wireless media and effective key exchange to assure an authenticated secure channel between them [23]. In 2013, Bahrampour and Atani proposed a Key Management Protocol for Wireless Sensor Networks based on PUFs, in which the PUFs were used to design the public keys [24]. In 2017, Chatterjee et al. proposed a PUF-based secure communication protocol for PUF [25]. The PUF was used to generate the public key based on the bilinear pairing of each device in the key agreement protocol. In 2018, Braeken improved Chatterjee’s protocol efficiency by way of employing the Elliptic Curve Qu Vanstone (ECQV) [26]. In 2019, Li et al. proposed a PUF-based secure communication system for the Internet of Things [27]. In 2020, Zhang et al. proposed a PUF-based Key Distribution in Wireless Sensor Networks [28].


## 2.2. Configurable RO PUFs

The PUF circuit, which is the core of authentication and key distribution in our scheme, should be easily implemented on the FPGA with good uniqueness and reliability. In our previous work, several types of configurable RO PUF are proposed, including MUX based RRO PUF in [29], XOR gate based XCRO PUF in [30], and tristate configurable TCRO PUF in [31]. In this paper, the MUX based RRO PUF is chosen. The MUX based configurable RO (CRO) PUF was first introduced in [32], where each ring oscillator can be reconfigured by using a multiplexer to select one of two inverters that are connected to the multiplexer to form an RO. Our reconfigurable RRO design, as shown in Figure 1, is consisted of a chain of inverter delay units and an AND gate delay unit. When the configurable signal of a MUX is “0,” the upper path will be chosen. On the contrary, when the signal is “1,” the lower path will be chosen to construct the RO structure. The configure procedure extracts the transfer difference of each MUX and the delay of the upper and lower path.Figure 1
RRO PUF structure.


## 2.3. Implement of PUFs

The PUF used in our approach is implemented and studied based on Xilinx SoC FPGAs and will be applied to real-world scenarios based on ASIC or SoC FPGA including ARM core (e.g., Xilinx Zynq-7000 series, Altera SoC or Microsemi Smart Fusion2) after validation. As shown in Figure2, the main components include MUX, XOR gate, inverters, and AND gate. In the implementation of the RRO PUF, the primitive MUXF7 is chosen for the multiplexer, the primitive LUT1 is adopted for the inverter, and LUT2 is utilized for the AND gate. Eight delay units that include seven inverter delay units and one AND gate delay unit are included in the single RRO array. Each delay unit occupies one slice and two delay units can be implemented in one configurable logic block (CLB). Therefore, four CLBs are needed to implement one RRO PUF array. In order to make sure that all RROs are identically routed, they are created as hard macros to avoid the bias introduced in the placement and routing. The detailed design can be referred in authors’ previous work [29].Figure 2
Implementation of an RRO in a CLB.


## 3. PUF-Based Mutual Authentication and Key Distribution

### 3.1. Network Model

Large-scale wireless sensor networks are usually deployed in a hierarchical clustered structure and contain heterogeneous nodes, such as a base station (BS), several sink nodes (SN), and a number of low-energy sensors. BS is assumed to be resourceful and global trusted. It manages the entire network and stores all gathered information by sensor nodes. Sink node is assumed to have higher hardware configurations than sensors, including memory, communication, and computation ability. A sink node acts as a gateway between sensor nodes and BS. Sensors are divided into nonoverlapping clusters; they collect data from surroundings and send raw data to the sink node. Sensor nodes are assumed to have a random linear movement pattern, while the BS and sink nodes are static like Han and Erfani schemes [15, 16]. Because of unpredictable position of mobile sensors, how to ensure a sink node to authenticate and distribute a pairwise key to every present cluster-member sensor is difficult.In our network model, assume there aren sensors, named S0,…,n−1, and m sink nodes, named SN0,…,m−1. Each sensor node has a unique ID Si and embeds a chip with a PUF structure, denoted as PSi. Before network deployment, all the nodes are divided into m deployment groups (DGs), denoted as DGii=0,…,m−1. In each DG, there is 1 SN and d = n/m sensors, and the SN is called the “Home-SN” of these d sensors. Nodes in a DG will be thrown into the destination area together, so as to form a cluster. Figure 3 gives an example with 3 DGs and 9 sensors.Figure 3
An example of the deployment model with 3 sink nodes and 9 sensors.


### 3.2. Initialization and Network Deployment

Before network deployment, for each sensorSi, take a random challenge number cSi as the input of PUF PSi and get the output response rSi; prestore the PUF CRP (cSi, rSi) to the Home-SN of Si by indexing with the sensor ID Si. For example, in Figure 3, in DG0, take the sink node SN0 as the Home-SN of sensors S0, S1, and S2. Generate a CRP for each sensor as (cS0, rS0), (cS1, rS1), and (cS2, rS2) and save them into the memory of SN0.After network deployment, the sink node launches the cluster forming process (not discussed in this paper, please refer to [33]), which divides all sensor nodes into clusters with no cross coverage. Each cluster includes a sink node, which is called the “cluster head” (CH), and n/m sensors, which are called the “cluster members” (CM). Nodes in the same DG form a cluster with very high probability since they are thrown close to each other. It shows an ideal deployment example in Figure 4.Figure 4
The network deployment.In order to ensure the secure intracluster communication, a sink node needs to authenticate and distributes a pairwise key to every cluster-member sensor. In a short period after network deployment, assume sensors are static. It is easy for the sink node to run the authentication and key distribution according to the challenge-response mechanism based on PUF CRP. However, after some working time, a sensor moves into another cluster’s region (as shown in Figure5), in which the sink node does not share the PUF CRP of the mobile sensor. In this situation, the sink node in the present cluster, called the “Present-SN,” should authenticate the mobile sensor via the help of the Home-SN. In the following section, we will describe our approach by two subschemes for static sensors and mobile sensors, respectively.Figure 5
S6 moves from C2 into C1.The differences between these two subschemes mainly happened in the following aspects: (1) there were two entities in static subscheme: Home-SN and the sensor; there were three entities in mobile subscheme: Home-SN, Present-SN, and the sensor; (2) in the static subscheme, the (Present also Home) SN generated the session key with the sensor; in the mobile subscheme, the Home-SN generated the session key between the Present-SN and the sensor; (3) in the static subscheme, the (Present also Home) SN authenticated the sensor directly; in the mobile subscheme, the Home SN-helped the Present-SN to authenticate the sensor.


### 3.3. Static Sensors Subscheme

The approach of a sink node SN0 authenticating and distributing a pairwise key to a static sensor S0 is described as shown in Figure 6.(1)
After network deployment and clustering process, in the clusterC0, the sink node SN0 detects a sensor S0 in its cluster. SN0 reads a PUF CRP in its memory: (cS0, rS0) by indexing of idS0.(2)
SN0 computes a temporary key keySN0:(2)keySN0=HrS0timestamp1,whereH is a hash function.SN0 generates a session key keySN0−S0 and encrypts it by keySN0 to get cipher1:(3)cipher1=EkeySN0,keySN0−S0.E is symmetric encryption (e.g., AES). Then, SN0 encrypts cS0 by using keySN0−S0:(4)cipher2=EkeySN0−S0,cS0timestamp1.Then, SN0 generates a secret random number nonce1 and encrypts it by using keySN0−S0:(5)cipher3=EkeySN0−S0,nonce1.SN0 sends the challenge cS0, cipher1, cipher2, and cipher3 to S0:(6)SN0⟶S0:cS0cipher1cipher2cipher3timestamp1.(3)
After receiving the message, the sensorS0 firstly inputs cS0 into the PUF structure PS0, which is embedded during the initialization phase, and gets the output response r0:(7)r0=PS0cS0.S0 computes a temporary key, keyS0:(8)keyS0=Hr0timestamp1.Then,S0 decrypts the cipher1 to get the pairwise key, keyS0−SN0:(9)plain1=DkeyS0,cipher1=DkeyS0,EkeySN0,keySN0−S0=keyS0−SN0.The functionD is the decryption operation of E.S0 decrypts cipher2 by using keyS0−SN0 and gets plain2:(10)plain2=DkeyS0−SN0,cipher2=DkeyS0−SN0,EkeySN0−S0,cS0timestamp1.The sensorS0 checks if the equation plain2=cS0‖timestamp1 is correct.If not,S0 deduces that the sink node SN0 is not its valid Home-SN, since it does not share a correct PUF CRP of SN0 (cS0, rS0). The SN0 fails the authentication by S0 and the scheme quits.If correct,S0 infers that keyS0−SN0=keySN0−S0; then keyS0 equals keySN0, and r0 equals rS0. This means the sink node SN0 indeed shares a CRP (cS0, rS0) of the PUF PS0 and passes the authentication by S0.S0 decrypts the cipher3 by using keyS0−SN0 and gets plain3:(11)plain3=DkeyS0−SN0,cipher3=DkeyS0−SN0,EkeySN0−S0,nonce1.S0 constructs and sends a message authentication code (MAC) to the SN0:(12)S0⟶SN0:MACplain3.(4)
SN0 checks if the equation MACplain3=MACnonce1 is correct.If correct, SN0 infers that the S0 carried out a correct nonce1 by computing the correct pairwise key, keyS0−SN0, which is derived by the correct response rS0 of PUF PS0. Thus, the sensor S0 passes the authentication by SN0.If not, SN0 deduces that the sensor is not a valid S0 as it declares, since it cannot output a correct response of rS0 so as to compute a correct keyS0−SN0. S0 fails the authentication and quits.From now on, an intracluster pairwise keykeyS0−SN0=keySN0−S0 is established and utilized to encrypt the communications between S0 and SN0. The mutual authentication is implemented by PUF CRP and the intracluster communication security is assured. Besides, the process is safe from the replay attack because the temporary key is derived involving the timestamps.Figure 6
Authentication and key distribution between SN0 and static sensor S0.


### 3.4. Mobile Sensors Subscheme

The network is dynamic during the working time. As shown in Figure5, the sensor S6 moves from the cluster C2, where it is thrown on, into the cluster region of C1. Therefore, the Home-SN of S6 is SN2 and the Present-SN is SN1. However, the SN1 does not share the PUF CRP of S6, and it should implement the authentication and key distribution via the help of SN2. The subscheme is described as shown in Figure 7.(1)
The sink node SN1 broadcasts the id of sensor S6 to request help. This is a round of intercluster communication.(2)
The sink node SN2 reads a PUF CRP in its memory: (cS6, rS6) by indexing of idS6.SN2 computes a temporary key, keySN:(13)keySN2=HrS6timestamp11.SN2 generates a session key between SN1 and S6, keySN1−S6, and encrypts it by keySN2:(14)cipher11=EkeySN2,keySN1−S6.Then, SN2 encrypts the cS6 by using keySN1−S6 to get cipher22:(15)cipher22=EkeySN1−S6,cS6timestamp11.SN2 encrypts the key keySN1−S6 by an intercluster key, keySN1−SN2, shared between SN1 and SN2:(16)cipher33=EkeySN1−SN2,keySN1−S6.SN2 sends the challenge cS6, cipher11, cipher22, and cipher33 to SN1:(17)SN2⟶SN1:cS6cipher11cipher22cipher33timestamp11.(3)
SN1 decrypts the cipher33 to get the session key, keySN1−S6:(18)plain33=DkeySN1−SN2,cipher33=keySN1−S6.Then, SN1 generates a secret random number nonce11 and encrypts it by using keySN1−S6:(19)cipher44=EkeySN1−S6,nonce11.SN1 sends the challenge cS6, cipher11, cipher22, and cihper44 to the sensor S6:(20)SN1⟶S6:cS6cipher11cipher22cipher44timestamp11.(4)
After receiving the message, the sensorS6 firstly inputs cS0 into the PUF structure PS6, which is embedded during the initialization phase, and gets the output response r6:(21)r6=PS6cS6.S6 computes a temporary key, keyS6:(22)keyS6=Hr6timestamp11.Then,S6 decrypts cipher11 to get the pairwise key, keyS6−SN1:(23)plain11=DkeyS6,cipher11=DkeyS6,EkeySN2,keySN1−S6=keyS6−SN1.S6 decrypts cipher22 by using keyS6−SN1 and gets plain22:(24)plain22=DkeyS6−SN1,cipher22=DkeyS6−SN1,EkeySN1−S6,cS6timestamp11.The sensorS6 checks if the equation plain22=cS6‖timestamp11 is correct.If not,S6 deduces that the cipher11 and cipher22 are not generated from its valid Home-SN or not forwarded from a trusted Present-SN. The SN1 fails the authentication by S6 and quits.If correct,S6 infers that the Present-SN SN1 is trusted by SN2 and passed the authentication.S6 decrypts cipher44 by using keyS6−SN1 and gets plain44:(25)plain44=DkeyS6−SN1,cipher44=DkeyS6−SN1,EkeySN1−S6,nonce11.S0 constructs and sends a message authentication code (MAC) to the SN1:(26)S6⟶SN1:MACplain44.(5)
SN1 checks if the equation MACplain44=MACnonce11 is correct:If correct, SN1 infers that the S6 carried out a correct nonce11 by computing the correct pairwise key, keyS6−SN1, which is derived by the correct response rS6 of PUF PS6. Thus, the sensor S6 passes the authentication by SN1.If not, SN1 deduces that the sensor is not a valid S6 as it declares, since it cannot output a correct response of rS6 to compute a correct keyS6−SN1. S6 fails the authentication and quits.Figure 7
Authentication and key distribution between SN1 and mobile sensor S6.


## 3.1. Network Model

Large-scale wireless sensor networks are usually deployed in a hierarchical clustered structure and contain heterogeneous nodes, such as a base station (BS), several sink nodes (SN), and a number of low-energy sensors. BS is assumed to be resourceful and global trusted. It manages the entire network and stores all gathered information by sensor nodes. Sink node is assumed to have higher hardware configurations than sensors, including memory, communication, and computation ability. A sink node acts as a gateway between sensor nodes and BS. Sensors are divided into nonoverlapping clusters; they collect data from surroundings and send raw data to the sink node. Sensor nodes are assumed to have a random linear movement pattern, while the BS and sink nodes are static like Han and Erfani schemes [15, 16]. Because of unpredictable position of mobile sensors, how to ensure a sink node to authenticate and distribute a pairwise key to every present cluster-member sensor is difficult.In our network model, assume there aren sensors, named S0,…,n−1, and m sink nodes, named SN0,…,m−1. Each sensor node has a unique ID Si and embeds a chip with a PUF structure, denoted as PSi. Before network deployment, all the nodes are divided into m deployment groups (DGs), denoted as DGii=0,…,m−1. In each DG, there is 1 SN and d = n/m sensors, and the SN is called the “Home-SN” of these d sensors. Nodes in a DG will be thrown into the destination area together, so as to form a cluster. Figure 3 gives an example with 3 DGs and 9 sensors.Figure 3
An example of the deployment model with 3 sink nodes and 9 sensors.


## 3.2. Initialization and Network Deployment

Before network deployment, for each sensorSi, take a random challenge number cSi as the input of PUF PSi and get the output response rSi; prestore the PUF CRP (cSi, rSi) to the Home-SN of Si by indexing with the sensor ID Si. For example, in Figure 3, in DG0, take the sink node SN0 as the Home-SN of sensors S0, S1, and S2. Generate a CRP for each sensor as (cS0, rS0), (cS1, rS1), and (cS2, rS2) and save them into the memory of SN0.After network deployment, the sink node launches the cluster forming process (not discussed in this paper, please refer to [33]), which divides all sensor nodes into clusters with no cross coverage. Each cluster includes a sink node, which is called the “cluster head” (CH), and n/m sensors, which are called the “cluster members” (CM). Nodes in the same DG form a cluster with very high probability since they are thrown close to each other. It shows an ideal deployment example in Figure 4.Figure 4
The network deployment.In order to ensure the secure intracluster communication, a sink node needs to authenticate and distributes a pairwise key to every cluster-member sensor. In a short period after network deployment, assume sensors are static. It is easy for the sink node to run the authentication and key distribution according to the challenge-response mechanism based on PUF CRP. However, after some working time, a sensor moves into another cluster’s region (as shown in Figure5), in which the sink node does not share the PUF CRP of the mobile sensor. In this situation, the sink node in the present cluster, called the “Present-SN,” should authenticate the mobile sensor via the help of the Home-SN. In the following section, we will describe our approach by two subschemes for static sensors and mobile sensors, respectively.Figure 5
S6 moves from C2 into C1.The differences between these two subschemes mainly happened in the following aspects: (1) there were two entities in static subscheme: Home-SN and the sensor; there were three entities in mobile subscheme: Home-SN, Present-SN, and the sensor; (2) in the static subscheme, the (Present also Home) SN generated the session key with the sensor; in the mobile subscheme, the Home-SN generated the session key between the Present-SN and the sensor; (3) in the static subscheme, the (Present also Home) SN authenticated the sensor directly; in the mobile subscheme, the Home SN-helped the Present-SN to authenticate the sensor.


## 3.3. Static Sensors Subscheme

The approach of a sink node SN0 authenticating and distributing a pairwise key to a static sensor S0 is described as shown in Figure 6.(1)
After network deployment and clustering process, in the clusterC0, the sink node SN0 detects a sensor S0 in its cluster. SN0 reads a PUF CRP in its memory: (cS0, rS0) by indexing of idS0.(2)
SN0 computes a temporary key keySN0:(2)keySN0=HrS0timestamp1,whereH is a hash function.SN0 generates a session key keySN0−S0 and encrypts it by keySN0 to get cipher1:(3)cipher1=EkeySN0,keySN0−S0.E is symmetric encryption (e.g., AES). Then, SN0 encrypts cS0 by using keySN0−S0:(4)cipher2=EkeySN0−S0,cS0timestamp1.Then, SN0 generates a secret random number nonce1 and encrypts it by using keySN0−S0:(5)cipher3=EkeySN0−S0,nonce1.SN0 sends the challenge cS0, cipher1, cipher2, and cipher3 to S0:(6)SN0⟶S0:cS0cipher1cipher2cipher3timestamp1.(3)
After receiving the message, the sensorS0 firstly inputs cS0 into the PUF structure PS0, which is embedded during the initialization phase, and gets the output response r0:(7)r0=PS0cS0.S0 computes a temporary key, keyS0:(8)keyS0=Hr0timestamp1.Then,S0 decrypts the cipher1 to get the pairwise key, keyS0−SN0:(9)plain1=DkeyS0,cipher1=DkeyS0,EkeySN0,keySN0−S0=keyS0−SN0.The functionD is the decryption operation of E.S0 decrypts cipher2 by using keyS0−SN0 and gets plain2:(10)plain2=DkeyS0−SN0,cipher2=DkeyS0−SN0,EkeySN0−S0,cS0timestamp1.The sensorS0 checks if the equation plain2=cS0‖timestamp1 is correct.If not,S0 deduces that the sink node SN0 is not its valid Home-SN, since it does not share a correct PUF CRP of SN0 (cS0, rS0). The SN0 fails the authentication by S0 and the scheme quits.If correct,S0 infers that keyS0−SN0=keySN0−S0; then keyS0 equals keySN0, and r0 equals rS0. This means the sink node SN0 indeed shares a CRP (cS0, rS0) of the PUF PS0 and passes the authentication by S0.S0 decrypts the cipher3 by using keyS0−SN0 and gets plain3:(11)plain3=DkeyS0−SN0,cipher3=DkeyS0−SN0,EkeySN0−S0,nonce1.S0 constructs and sends a message authentication code (MAC) to the SN0:(12)S0⟶SN0:MACplain3.(4)
SN0 checks if the equation MACplain3=MACnonce1 is correct.If correct, SN0 infers that the S0 carried out a correct nonce1 by computing the correct pairwise key, keyS0−SN0, which is derived by the correct response rS0 of PUF PS0. Thus, the sensor S0 passes the authentication by SN0.If not, SN0 deduces that the sensor is not a valid S0 as it declares, since it cannot output a correct response of rS0 so as to compute a correct keyS0−SN0. S0 fails the authentication and quits.From now on, an intracluster pairwise keykeyS0−SN0=keySN0−S0 is established and utilized to encrypt the communications between S0 and SN0. The mutual authentication is implemented by PUF CRP and the intracluster communication security is assured. Besides, the process is safe from the replay attack because the temporary key is derived involving the timestamps.Figure 6
Authentication and key distribution between SN0 and static sensor S0.


## 3.4. Mobile Sensors Subscheme

The network is dynamic during the working time. As shown in Figure5, the sensor S6 moves from the cluster C2, where it is thrown on, into the cluster region of C1. Therefore, the Home-SN of S6 is SN2 and the Present-SN is SN1. However, the SN1 does not share the PUF CRP of S6, and it should implement the authentication and key distribution via the help of SN2. The subscheme is described as shown in Figure 7.(1)
The sink node SN1 broadcasts the id of sensor S6 to request help. This is a round of intercluster communication.(2)
The sink node SN2 reads a PUF CRP in its memory: (cS6, rS6) by indexing of idS6.SN2 computes a temporary key, keySN:(13)keySN2=HrS6timestamp11.SN2 generates a session key between SN1 and S6, keySN1−S6, and encrypts it by keySN2:(14)cipher11=EkeySN2,keySN1−S6.Then, SN2 encrypts the cS6 by using keySN1−S6 to get cipher22:(15)cipher22=EkeySN1−S6,cS6timestamp11.SN2 encrypts the key keySN1−S6 by an intercluster key, keySN1−SN2, shared between SN1 and SN2:(16)cipher33=EkeySN1−SN2,keySN1−S6.SN2 sends the challenge cS6, cipher11, cipher22, and cipher33 to SN1:(17)SN2⟶SN1:cS6cipher11cipher22cipher33timestamp11.(3)
SN1 decrypts the cipher33 to get the session key, keySN1−S6:(18)plain33=DkeySN1−SN2,cipher33=keySN1−S6.Then, SN1 generates a secret random number nonce11 and encrypts it by using keySN1−S6:(19)cipher44=EkeySN1−S6,nonce11.SN1 sends the challenge cS6, cipher11, cipher22, and cihper44 to the sensor S6:(20)SN1⟶S6:cS6cipher11cipher22cipher44timestamp11.(4)
After receiving the message, the sensorS6 firstly inputs cS0 into the PUF structure PS6, which is embedded during the initialization phase, and gets the output response r6:(21)r6=PS6cS6.S6 computes a temporary key, keyS6:(22)keyS6=Hr6timestamp11.Then,S6 decrypts cipher11 to get the pairwise key, keyS6−SN1:(23)plain11=DkeyS6,cipher11=DkeyS6,EkeySN2,keySN1−S6=keyS6−SN1.S6 decrypts cipher22 by using keyS6−SN1 and gets plain22:(24)plain22=DkeyS6−SN1,cipher22=DkeyS6−SN1,EkeySN1−S6,cS6timestamp11.The sensorS6 checks if the equation plain22=cS6‖timestamp11 is correct.If not,S6 deduces that the cipher11 and cipher22 are not generated from its valid Home-SN or not forwarded from a trusted Present-SN. The SN1 fails the authentication by S6 and quits.If correct,S6 infers that the Present-SN SN1 is trusted by SN2 and passed the authentication.S6 decrypts cipher44 by using keyS6−SN1 and gets plain44:(25)plain44=DkeyS6−SN1,cipher44=DkeyS6−SN1,EkeySN1−S6,nonce11.S0 constructs and sends a message authentication code (MAC) to the SN1:(26)S6⟶SN1:MACplain44.(5)
SN1 checks if the equation MACplain44=MACnonce11 is correct:If correct, SN1 infers that the S6 carried out a correct nonce11 by computing the correct pairwise key, keyS6−SN1, which is derived by the correct response rS6 of PUF PS6. Thus, the sensor S6 passes the authentication by SN1.If not, SN1 deduces that the sensor is not a valid S6 as it declares, since it cannot output a correct response of rS6 to compute a correct keyS6−SN1. S6 fails the authentication and quits.Figure 7
Authentication and key distribution between SN1 and mobile sensor S6.


## 4. Simulation, Analysis and Comparisons

We present the security and performance evaluation of the proposed scheme through simulation experiments and analysis. We provide extensive simulations to verify the performance metrics such as secure connectivity, resilience against node capture, memory consumption, and communication overhead. We compare the proposed approach with other key management schemes. In the simulation, we assume 10000 sensor nodes, and 100 sink nodes are randomly distributed in a 1000 × 1000 m field. Each sensor node has a fixed speed ranging from 1 to 10 m/s. The radio range of each sensor node is considered as 50 m.


### 4.1. Mutual Authentication

The basic idea of the authentication of our approach is the challenge-response mechanism based on the PUF CRP. In both subschemes, mutual authentication between the sink node and the (static or mobile) sensor is assured. Furthermore, the scheme quits before key distribution process if the authentication failed, that is, an unauthenticated sensor cannot participate the whole communication network. Compared with the PKI method, the PUF-based authentication speeds up and reduces the storage requirement.In some proposed PUF authentication schemes [21, 22], the challenge and response are always sent in plaintext. If attackers catch an entire PUF CRP, they are able to launch the replay attack and man-in-the-middle attack. In order to resist the replay attack, a strong PUF is usually employed to provide a plenty of CRPs and each of them is only used once. Then, different CRPs of a PUF are openly exposed in a dynamic network where a mobile node needs frequent authentication with new neighbors. This PUF structure is vulnerable to the modelling attack that tries to guess and predict the response value related to a certain challenge.In our scheme, the PUF response is not transmitted in plain but converted into an encryption key by hashing with a timestamp. A node succeeds the authentication if it decrypts and carries out a correct plaintext. This is a kind of symmetric authentication [34] combined with the PUF challenge-response mechanism. In order to prevent the replay attack, a timestamp has been used. The fact that the PUF response is not transmitted in plain effectively resists the modelling attack on PUF.


### 4.2. Overheads

We mainly consider the energy consumption in terms of storage, communication, and computation overheads. We mainly consider the following assumptions: MAC size is considered as 4 bytes, 4 bytes for time stamp, random nonce as 16 bytes, 32 bytes for key size, and 32 bytes for challenge/response of a PUF. We also consider 2 bytes for the node ids. The ciphertext has the same length with the key.


#### 4.2.1. Key Storage

In our approach, during the initialization phase, each sensor is not predistributed with any key in its memory, while each sink node is predistributed withn/m PUF CRPs. A PUF structure is embedded in a sensor (as a hardware) during the initialization phase (therefore, the storage overhead is not discussed in this paper). After the key distribution, the sensor stores 1 intracluster session key established with the sink node, while the sink node stores one intracluster session key for each cluster-member sensor. All the intermediate data generated in the key distribution process is deleted to release the storage space. Therefore, the storage overhead of a sensor is 32 bytes and that of a sink node is 32+32×2+2n/m=98n/mbytes.Du et al. proposed an AP scheme [10], which is a pure random key predistribution scheme. The main idea is to preload only a small number of keys (denoted as l) in low-ended sensors, while preloading a relatively large number of keys (denoted as M≫l) in each high-ended sink nodes. Any two nodes cannot establish a secure link if they do not share a common pairwise keys. Therefore, nodes need to store more keys to increase the probability of sharing common keys, which is defined as the secure connectivity. As analyzed in Erfani’s scheme [16], the sensor memory is partitioned into two parts: store α predistributed keys in the first part and β postdeployment keys in the second part. Each pair of neighboring nodes establish a common predistributed or postdeployment key to secure the communication. Erfani’s scheme claimed that each sink node stores only 1 key; BS stores a key table, which contained some information about sensor nodes’ keys. In addition, BS is aware of sink nodes’ keys.Table1 compares the amount of memory required for storing keys in the proposed scheme and other two solutions. The key storage in sink node of our scheme is higher than Erfani’s scheme, but the storage of sensor is much lower than both Erfani’s and AP schemes. Therefore, our scheme is efficient for resource limited sensor nodes, and this performance also brings an advantage of better resilience against node capture attack.Table 1
Comparison of storage overhead in different schemes (bytes).
Our schemeErfani’sAPSensor3232(α + β)32lSink98n/m3232MBS—32[n(α + β) + m]—


#### 4.2.2. Communication Overhead

In this paper, the communication overhead is measured by the message size and transmission rounds but does not consider the message overhead consisting of a protocol ID, a message ID, a check-sum, and the headers and footers of the low-level network layers.We analyze the communication overhead for static and mobile subschemes, respectively.In the static subscheme, to establish an intracluster pairwise key, the sensor sends only 1 MAC packet with 4 bytes, while the sink node sends 1 packet with 132 bytes.In the mobile subscheme, to establish an intracluster pairwise key, the sensor sends only 1 MAC packet with 4 bytes, while the Home-SN sends 1 packet with 132 bytes and the Present-SN sends 2 packets with 2 bytes and 132 bytes.Compared with the random key predistribution schemes like the AP, nodes do not need key construction or authentication but try to find a common key by sending the key indexes or encrypted challenges. The transmitted message size is linearly related to the size of the keyring. However, if two neighboring nodes do not share a common key, they must send further messages to ≥2 hops intermediate nodes.


#### 4.2.3. Computation Overhead

The most computation overhead is related to cryptography and authentication operations, and the PUF computation especially for sensors. As shown in Table2, to establish an intracluster pairwise key, the number of encryption or decryption operations in each sensor is 3 and 3 or 5 in a sink node. All these schemes use light weight cryptography methods. The computation overhead is higher than the random key predistribution scheme AP but still acceptable for both sensors and sink nodes.Table 2
Comparison of computation overhead.
Our schemeAPCryptography in sensor3NACryptography in sink nodeStatic: 3NAMobile: 5PUF1NA


### 4.3. Secure Connectivity

The security connectivity of a network is defined as the probability that two entities can establish a session key to secure the communications. Since this paper mainly proposes an approach for intracluster authentication and key distribution, we define the conception of “intracluster secure connectivity” as the probability that a sink node can establish a pairwise key with a cluster-member (static or mobile) sensor.This scheme is a kind of deterministic key distribution model, in which any sensor node can successfully establish a session key with no matter the Home-SN or the Present-SN. Therefore, the intracluster security connectivity is 100% in this scheme, which is a remarkable improvement compared with the probabilistic key distribution schemes [9, 10, 12].The random schemes, like AP scheme, must increase the amount of key storage to achieve high security connectivity. Figure8 shows the secure connectivity versus the key pool size P in the AP. There are four solid curves in Figure 8, from bottom to top, corresponding parameters [l, M] of [5, 125], [10, 250], [15, 375], and [20, 500], respectively. It is observed that the probability of sharing key increases when the number of preloaded keys increases. For the same parameters [l, M], the probability of sharing key decreases as the key pool size becomes large. In Figure 9, we also plot the secure connectivity for different numbers of preloaded keys in the AP and our scheme. As analyzed in the above section, the storage overhead of the sink node in our scheme is 98n/m≈10000 bytes, almost 300 32bytes-keys. It is worth emphasizing that the key storage of sensor nodes in our proposal is 0, which is significantly lower than that of AP scheme, but the connectivity is significantly higher than that of AP scheme. The Erfani’s scheme is also claimed of providing full secure connectivity in [16], however there is a trade-off between α and β in balancing the storage, connectivity, and resilience.Figure 8
Secure connectivity versus the key pool sizeP.Figure 9
Secure connectivity versus keyring size.


### 4.4. Resilience Against Node Capture

Sensor networks are usually deployed in an unattended environment, and attackers illegally obtain the secret information of nodes by capturing nodes and other physical attacks. Resilience against node capture is defined as the probabilityF (x) that the attacker can obtain the key in the uncaptured node directly or indirectly according to a certain number of captured nodes x:(27)Fx=number of compromised links between uncaptured nodesnumber of uncompromised links.


#### 4.4.1. Resilience against the Sensor Capture

Different from the traditional random key predistribution schemes [4, 5, 7], in this scheme, the sensor node does not prestore any keys or other key materials, which not only reduces the storage cost of the sensor but also improves the resilience against the sensor capture because the attacker cannot obtain any key that belong to a safe node despite capturing a sensor physically. Therefore, our proposal has perfect resilience against the sensor capture; that is,(28)FxS=0,where xS represents the number of captured sensor nodes.


#### 4.4.2. Resilience against the Sink Node Capture

The sink node acts as the cluster head, which maintains the intracluster secure communication with the cluster members and also the intercluster secure communication with other cluster heads externally. Each sink node is prestored with a number of CRPs in the initialization phase and uses the CRPs to authenticate and distribute pairwise keys with its cluster-member sensors.The physical capturing of a sink node breaks up both the internal and external cluster communication of it. The dismissed cluster members (sensors) become isolated nodes and may join other clusters. By repeating the authentication and key distribution process, the dismissed sensor obtains a new session key with its new cluster head. There is not any key that belong to a safe node that will be exposed by a physical captured sink node. Therefore, our proposal has perfect resilience against the sink node capture; that is,(29)FxSN=0,where xSN represents the number of captured sink nodes.


#### 4.4.3. Resilience against Selective Node Capture

Huang et al. [35] pointed out that, in many key management schemes, the selective node capture causes more damage to the network. In the selective node capture attacks, attackers attempt to capture nodes that may reveal more valid and fresh information about uncaptured nodes. In our proposed scheme, an adversary cannot figure out which sink node owns the CRP of a certain sensor, because all CRPs are randomly and safely selected from the CRP pool. Therefore, unless the adversary compromises all the sink nodes, it cannot choose a certain sink node to capture to maximize the uncompromised keys.


#### 4.4.4. Simulation Results

The AP scheme [10] proposed by Du et al. is a pure random key predistribution scheme in cluster sensor networks, with the advantage in saving nodes’ communication and computation overheads. But it is hard to balance the tradeoff between the security connectivity and security. Boujelben et al. [12] improved the AP by combining the Blom matrix in terms of the resilience against node capture but require quantity of storage overhead for matrix parameters. Erfani’s scheme [16] is a combination of the key pre-distribution and post-deployment key management scheme. When a sensor is captured, all predistributed and postdeployment keys of the node are compromised. But since the postdeployment key is not selected form the key pool, the compromise of such key does not affect the security of other communications, whereas compromising the predistributed keys of a sensor node will make other communication links insecure, because such keys are selected from the key pool and might be common with some sensors. Erfani’s scheme provides better resilience against node capture attack than the AP, and the resilience of sensor network depends on the number of predistributed keys α and key pool size P.We will compare our scheme with these schemes by simulation experiments. The size of key pool in AP, Boujelben’s, and Erfani’s schemes isP=10000. Similar to the experiments environment in [16], the keyring size is 100 in Erfani’s scheme.As shown in Figures10 and 11, the experimental results prove that, in the random key predistribution schemes, the resilience against node capture gets worse and worse with the number of captured nodes increasing, because the nodes store a large number of keys. In Boujelben et al. scheme, the nodes store matrixes instead of keys, so the resilience against node capture is better than that in the AP scheme, but the storage cost is λ times that of AP (λ is the matrix parameter).Figure 10
Resilience against the sensor capture.Figure 11
Resilience against the sink node capture.In our scheme, the sensor node does not store any key, and the sink node stores the CRPs rather than the key as well, so perfect resilience against node capture is provided.


### 4.5. PUF Security

In this paper, PUF is the core of the authentication and key distribution. The security of the PUF is crucially important. The main threats to some PUF-based schemes [36] include man-in-the-middle attack, replay attack, and the modelling attack to the PUF, because the PUF CRPs are transmitted in plain form. A PUF is considered failed when the adversaries can guess more than 75% bits of the response to a challenge after obtaining enough amount of CRPs of a given PUF. In our proposal, the response, generated by a PUF on a sensor on-the-fly, is not sent to the sink node directly but is utilized as an encryption key to encrypt the challenge. Such design can successfully protect the PUF from cloning attack, modelling attack, and side channel attacks, including electromagnetic analysis attack and differential fault attack. The eavesdropping is invalid, since all the transmitted messages are encrypted with symmetric algorithm (e.g., AES), the attackers cannot get any plain information about responses or keys. The scheme can withstand the man-in-the-middle attack and tamper attack, since the encrypted response protects its integrity in the wireless communications.In the replay attack, an attacker resends an old message, which has been sent for key generation request. In the proposed approach, timestamp has been used in generating the temporary key to prevent the replay attack. Besides, the session key is randomly generated between the sink node and sensor and will not be the same as the a priori key. An attacker can continuously resend an old message to consume the energy of sensor nodes; however, these messages will be discarded.Table3 shows the comprehensive comparison results among different authentication and key distribution schemes for sensor networks proposed in recent years. Unlike the key predistribution schemes, for example, AP [10], our scheme is perfectly resilient against node capture attacks, because a sensor does not prestore any keys that might secure other sensors’ communications. PUF CRPs provide a type of authentication by a challenge-response mechanism, but Chatterjee’s scheme [23] does not guarantee mutual authentication between two parties. In addition, PUFs provide another type of security guarantee implied by their unclonability and tamper evidence. Such property is only available to PUF-based solutions. However, PUF CRPs are sent as plaintext in [23, 25], which make them vulnerable to impersonation attack, but we avoid this in our scheme by encrypting the response of the CRPs. Also, in [14, 23, 25, 27], they used public key algorithm that consumed more computation overhead than the AP [10] and our proposal.Table 3
Comparisons of different key distribution schemes.
PropertyOursAP [10]Lee and Kim [14]Erfani et al. [16]Chatterjee et al. [25]Li et al. [27]Public key encryptionNoNoYesNoYesYesKey predistributionNoYesNoYesNoNoPerfect resilience against node captureYesNo—No——PUF-basedYesNoNoNoYesYesMutual authenticationYesNoYesYesNoYesResistant to modelling attacksYes———NoNoResistant to eavesdropping attacksYes———YesYesResistant to collusion attacksYes——Yes———: not applicable.


## 4.1. Mutual Authentication

The basic idea of the authentication of our approach is the challenge-response mechanism based on the PUF CRP. In both subschemes, mutual authentication between the sink node and the (static or mobile) sensor is assured. Furthermore, the scheme quits before key distribution process if the authentication failed, that is, an unauthenticated sensor cannot participate the whole communication network. Compared with the PKI method, the PUF-based authentication speeds up and reduces the storage requirement.In some proposed PUF authentication schemes [21, 22], the challenge and response are always sent in plaintext. If attackers catch an entire PUF CRP, they are able to launch the replay attack and man-in-the-middle attack. In order to resist the replay attack, a strong PUF is usually employed to provide a plenty of CRPs and each of them is only used once. Then, different CRPs of a PUF are openly exposed in a dynamic network where a mobile node needs frequent authentication with new neighbors. This PUF structure is vulnerable to the modelling attack that tries to guess and predict the response value related to a certain challenge.In our scheme, the PUF response is not transmitted in plain but converted into an encryption key by hashing with a timestamp. A node succeeds the authentication if it decrypts and carries out a correct plaintext. This is a kind of symmetric authentication [34] combined with the PUF challenge-response mechanism. In order to prevent the replay attack, a timestamp has been used. The fact that the PUF response is not transmitted in plain effectively resists the modelling attack on PUF.


## 4.2. Overheads

We mainly consider the energy consumption in terms of storage, communication, and computation overheads. We mainly consider the following assumptions: MAC size is considered as 4 bytes, 4 bytes for time stamp, random nonce as 16 bytes, 32 bytes for key size, and 32 bytes for challenge/response of a PUF. We also consider 2 bytes for the node ids. The ciphertext has the same length with the key.


### 4.2.1. Key Storage

In our approach, during the initialization phase, each sensor is not predistributed with any key in its memory, while each sink node is predistributed withn/m PUF CRPs. A PUF structure is embedded in a sensor (as a hardware) during the initialization phase (therefore, the storage overhead is not discussed in this paper). After the key distribution, the sensor stores 1 intracluster session key established with the sink node, while the sink node stores one intracluster session key for each cluster-member sensor. All the intermediate data generated in the key distribution process is deleted to release the storage space. Therefore, the storage overhead of a sensor is 32 bytes and that of a sink node is 32+32×2+2n/m=98n/mbytes.Du et al. proposed an AP scheme [10], which is a pure random key predistribution scheme. The main idea is to preload only a small number of keys (denoted as l) in low-ended sensors, while preloading a relatively large number of keys (denoted as M≫l) in each high-ended sink nodes. Any two nodes cannot establish a secure link if they do not share a common pairwise keys. Therefore, nodes need to store more keys to increase the probability of sharing common keys, which is defined as the secure connectivity. As analyzed in Erfani’s scheme [16], the sensor memory is partitioned into two parts: store α predistributed keys in the first part and β postdeployment keys in the second part. Each pair of neighboring nodes establish a common predistributed or postdeployment key to secure the communication. Erfani’s scheme claimed that each sink node stores only 1 key; BS stores a key table, which contained some information about sensor nodes’ keys. In addition, BS is aware of sink nodes’ keys.Table1 compares the amount of memory required for storing keys in the proposed scheme and other two solutions. The key storage in sink node of our scheme is higher than Erfani’s scheme, but the storage of sensor is much lower than both Erfani’s and AP schemes. Therefore, our scheme is efficient for resource limited sensor nodes, and this performance also brings an advantage of better resilience against node capture attack.Table 1
Comparison of storage overhead in different schemes (bytes).
Our schemeErfani’sAPSensor3232(α + β)32lSink98n/m3232MBS—32[n(α + β) + m]—


### 4.2.2. Communication Overhead

In this paper, the communication overhead is measured by the message size and transmission rounds but does not consider the message overhead consisting of a protocol ID, a message ID, a check-sum, and the headers and footers of the low-level network layers.We analyze the communication overhead for static and mobile subschemes, respectively.In the static subscheme, to establish an intracluster pairwise key, the sensor sends only 1 MAC packet with 4 bytes, while the sink node sends 1 packet with 132 bytes.In the mobile subscheme, to establish an intracluster pairwise key, the sensor sends only 1 MAC packet with 4 bytes, while the Home-SN sends 1 packet with 132 bytes and the Present-SN sends 2 packets with 2 bytes and 132 bytes.Compared with the random key predistribution schemes like the AP, nodes do not need key construction or authentication but try to find a common key by sending the key indexes or encrypted challenges. The transmitted message size is linearly related to the size of the keyring. However, if two neighboring nodes do not share a common key, they must send further messages to ≥2 hops intermediate nodes.


### 4.2.3. Computation Overhead

The most computation overhead is related to cryptography and authentication operations, and the PUF computation especially for sensors. As shown in Table2, to establish an intracluster pairwise key, the number of encryption or decryption operations in each sensor is 3 and 3 or 5 in a sink node. All these schemes use light weight cryptography methods. The computation overhead is higher than the random key predistribution scheme AP but still acceptable for both sensors and sink nodes.Table 2
Comparison of computation overhead.
Our schemeAPCryptography in sensor3NACryptography in sink nodeStatic: 3NAMobile: 5PUF1NA


## 4.2.1. Key Storage

In our approach, during the initialization phase, each sensor is not predistributed with any key in its memory, while each sink node is predistributed withn/m PUF CRPs. A PUF structure is embedded in a sensor (as a hardware) during the initialization phase (therefore, the storage overhead is not discussed in this paper). After the key distribution, the sensor stores 1 intracluster session key established with the sink node, while the sink node stores one intracluster session key for each cluster-member sensor. All the intermediate data generated in the key distribution process is deleted to release the storage space. Therefore, the storage overhead of a sensor is 32 bytes and that of a sink node is 32+32×2+2n/m=98n/mbytes.Du et al. proposed an AP scheme [10], which is a pure random key predistribution scheme. The main idea is to preload only a small number of keys (denoted as l) in low-ended sensors, while preloading a relatively large number of keys (denoted as M≫l) in each high-ended sink nodes. Any two nodes cannot establish a secure link if they do not share a common pairwise keys. Therefore, nodes need to store more keys to increase the probability of sharing common keys, which is defined as the secure connectivity. As analyzed in Erfani’s scheme [16], the sensor memory is partitioned into two parts: store α predistributed keys in the first part and β postdeployment keys in the second part. Each pair of neighboring nodes establish a common predistributed or postdeployment key to secure the communication. Erfani’s scheme claimed that each sink node stores only 1 key; BS stores a key table, which contained some information about sensor nodes’ keys. In addition, BS is aware of sink nodes’ keys.Table1 compares the amount of memory required for storing keys in the proposed scheme and other two solutions. The key storage in sink node of our scheme is higher than Erfani’s scheme, but the storage of sensor is much lower than both Erfani’s and AP schemes. Therefore, our scheme is efficient for resource limited sensor nodes, and this performance also brings an advantage of better resilience against node capture attack.Table 1
Comparison of storage overhead in different schemes (bytes).
Our schemeErfani’sAPSensor3232(α + β)32lSink98n/m3232MBS—32[n(α + β) + m]—


## 4.2.2. Communication Overhead

In this paper, the communication overhead is measured by the message size and transmission rounds but does not consider the message overhead consisting of a protocol ID, a message ID, a check-sum, and the headers and footers of the low-level network layers.We analyze the communication overhead for static and mobile subschemes, respectively.In the static subscheme, to establish an intracluster pairwise key, the sensor sends only 1 MAC packet with 4 bytes, while the sink node sends 1 packet with 132 bytes.In the mobile subscheme, to establish an intracluster pairwise key, the sensor sends only 1 MAC packet with 4 bytes, while the Home-SN sends 1 packet with 132 bytes and the Present-SN sends 2 packets with 2 bytes and 132 bytes.Compared with the random key predistribution schemes like the AP, nodes do not need key construction or authentication but try to find a common key by sending the key indexes or encrypted challenges. The transmitted message size is linearly related to the size of the keyring. However, if two neighboring nodes do not share a common key, they must send further messages to ≥2 hops intermediate nodes.


## 4.2.3. Computation Overhead

The most computation overhead is related to cryptography and authentication operations, and the PUF computation especially for sensors. As shown in Table2, to establish an intracluster pairwise key, the number of encryption or decryption operations in each sensor is 3 and 3 or 5 in a sink node. All these schemes use light weight cryptography methods. The computation overhead is higher than the random key predistribution scheme AP but still acceptable for both sensors and sink nodes.Table 2
Comparison of computation overhead.
Our schemeAPCryptography in sensor3NACryptography in sink nodeStatic: 3NAMobile: 5PUF1NA


## 4.3. Secure Connectivity

The security connectivity of a network is defined as the probability that two entities can establish a session key to secure the communications. Since this paper mainly proposes an approach for intracluster authentication and key distribution, we define the conception of “intracluster secure connectivity” as the probability that a sink node can establish a pairwise key with a cluster-member (static or mobile) sensor.This scheme is a kind of deterministic key distribution model, in which any sensor node can successfully establish a session key with no matter the Home-SN or the Present-SN. Therefore, the intracluster security connectivity is 100% in this scheme, which is a remarkable improvement compared with the probabilistic key distribution schemes [9, 10, 12].The random schemes, like AP scheme, must increase the amount of key storage to achieve high security connectivity. Figure8 shows the secure connectivity versus the key pool size P in the AP. There are four solid curves in Figure 8, from bottom to top, corresponding parameters [l, M] of [5, 125], [10, 250], [15, 375], and [20, 500], respectively. It is observed that the probability of sharing key increases when the number of preloaded keys increases. For the same parameters [l, M], the probability of sharing key decreases as the key pool size becomes large. In Figure 9, we also plot the secure connectivity for different numbers of preloaded keys in the AP and our scheme. As analyzed in the above section, the storage overhead of the sink node in our scheme is 98n/m≈10000 bytes, almost 300 32bytes-keys. It is worth emphasizing that the key storage of sensor nodes in our proposal is 0, which is significantly lower than that of AP scheme, but the connectivity is significantly higher than that of AP scheme. The Erfani’s scheme is also claimed of providing full secure connectivity in [16], however there is a trade-off between α and β in balancing the storage, connectivity, and resilience.Figure 8
Secure connectivity versus the key pool sizeP.Figure 9
Secure connectivity versus keyring size.


## 4.4. Resilience Against Node Capture

Sensor networks are usually deployed in an unattended environment, and attackers illegally obtain the secret information of nodes by capturing nodes and other physical attacks. Resilience against node capture is defined as the probabilityF (x) that the attacker can obtain the key in the uncaptured node directly or indirectly according to a certain number of captured nodes x:(27)Fx=number of compromised links between uncaptured nodesnumber of uncompromised links.


### 4.4.1. Resilience against the Sensor Capture

Different from the traditional random key predistribution schemes [4, 5, 7], in this scheme, the sensor node does not prestore any keys or other key materials, which not only reduces the storage cost of the sensor but also improves the resilience against the sensor capture because the attacker cannot obtain any key that belong to a safe node despite capturing a sensor physically. Therefore, our proposal has perfect resilience against the sensor capture; that is,(28)FxS=0,where xS represents the number of captured sensor nodes.


### 4.4.2. Resilience against the Sink Node Capture

The sink node acts as the cluster head, which maintains the intracluster secure communication with the cluster members and also the intercluster secure communication with other cluster heads externally. Each sink node is prestored with a number of CRPs in the initialization phase and uses the CRPs to authenticate and distribute pairwise keys with its cluster-member sensors.The physical capturing of a sink node breaks up both the internal and external cluster communication of it. The dismissed cluster members (sensors) become isolated nodes and may join other clusters. By repeating the authentication and key distribution process, the dismissed sensor obtains a new session key with its new cluster head. There is not any key that belong to a safe node that will be exposed by a physical captured sink node. Therefore, our proposal has perfect resilience against the sink node capture; that is,(29)FxSN=0,where xSN represents the number of captured sink nodes.


### 4.4.3. Resilience against Selective Node Capture

Huang et al. [35] pointed out that, in many key management schemes, the selective node capture causes more damage to the network. In the selective node capture attacks, attackers attempt to capture nodes that may reveal more valid and fresh information about uncaptured nodes. In our proposed scheme, an adversary cannot figure out which sink node owns the CRP of a certain sensor, because all CRPs are randomly and safely selected from the CRP pool. Therefore, unless the adversary compromises all the sink nodes, it cannot choose a certain sink node to capture to maximize the uncompromised keys.


### 4.4.4. Simulation Results

The AP scheme [10] proposed by Du et al. is a pure random key predistribution scheme in cluster sensor networks, with the advantage in saving nodes’ communication and computation overheads. But it is hard to balance the tradeoff between the security connectivity and security. Boujelben et al. [12] improved the AP by combining the Blom matrix in terms of the resilience against node capture but require quantity of storage overhead for matrix parameters. Erfani’s scheme [16] is a combination of the key pre-distribution and post-deployment key management scheme. When a sensor is captured, all predistributed and postdeployment keys of the node are compromised. But since the postdeployment key is not selected form the key pool, the compromise of such key does not affect the security of other communications, whereas compromising the predistributed keys of a sensor node will make other communication links insecure, because such keys are selected from the key pool and might be common with some sensors. Erfani’s scheme provides better resilience against node capture attack than the AP, and the resilience of sensor network depends on the number of predistributed keys α and key pool size P.We will compare our scheme with these schemes by simulation experiments. The size of key pool in AP, Boujelben’s, and Erfani’s schemes isP=10000. Similar to the experiments environment in [16], the keyring size is 100 in Erfani’s scheme.As shown in Figures10 and 11, the experimental results prove that, in the random key predistribution schemes, the resilience against node capture gets worse and worse with the number of captured nodes increasing, because the nodes store a large number of keys. In Boujelben et al. scheme, the nodes store matrixes instead of keys, so the resilience against node capture is better than that in the AP scheme, but the storage cost is λ times that of AP (λ is the matrix parameter).Figure 10
Resilience against the sensor capture.Figure 11
Resilience against the sink node capture.In our scheme, the sensor node does not store any key, and the sink node stores the CRPs rather than the key as well, so perfect resilience against node capture is provided.


## 4.4.1. Resilience against the Sensor Capture

Different from the traditional random key predistribution schemes [4, 5, 7], in this scheme, the sensor node does not prestore any keys or other key materials, which not only reduces the storage cost of the sensor but also improves the resilience against the sensor capture because the attacker cannot obtain any key that belong to a safe node despite capturing a sensor physically. Therefore, our proposal has perfect resilience against the sensor capture; that is,(28)FxS=0,where xS represents the number of captured sensor nodes.


## 4.4.2. Resilience against the Sink Node Capture

The sink node acts as the cluster head, which maintains the intracluster secure communication with the cluster members and also the intercluster secure communication with other cluster heads externally. Each sink node is prestored with a number of CRPs in the initialization phase and uses the CRPs to authenticate and distribute pairwise keys with its cluster-member sensors.The physical capturing of a sink node breaks up both the internal and external cluster communication of it. The dismissed cluster members (sensors) become isolated nodes and may join other clusters. By repeating the authentication and key distribution process, the dismissed sensor obtains a new session key with its new cluster head. There is not any key that belong to a safe node that will be exposed by a physical captured sink node. Therefore, our proposal has perfect resilience against the sink node capture; that is,(29)FxSN=0,where xSN represents the number of captured sink nodes.


## 4.4.3. Resilience against Selective Node Capture

Huang et al. [35] pointed out that, in many key management schemes, the selective node capture causes more damage to the network. In the selective node capture attacks, attackers attempt to capture nodes that may reveal more valid and fresh information about uncaptured nodes. In our proposed scheme, an adversary cannot figure out which sink node owns the CRP of a certain sensor, because all CRPs are randomly and safely selected from the CRP pool. Therefore, unless the adversary compromises all the sink nodes, it cannot choose a certain sink node to capture to maximize the uncompromised keys.


## 4.4.4. Simulation Results

The AP scheme [10] proposed by Du et al. is a pure random key predistribution scheme in cluster sensor networks, with the advantage in saving nodes’ communication and computation overheads. But it is hard to balance the tradeoff between the security connectivity and security. Boujelben et al. [12] improved the AP by combining the Blom matrix in terms of the resilience against node capture but require quantity of storage overhead for matrix parameters. Erfani’s scheme [16] is a combination of the key pre-distribution and post-deployment key management scheme. When a sensor is captured, all predistributed and postdeployment keys of the node are compromised. But since the postdeployment key is not selected form the key pool, the compromise of such key does not affect the security of other communications, whereas compromising the predistributed keys of a sensor node will make other communication links insecure, because such keys are selected from the key pool and might be common with some sensors. Erfani’s scheme provides better resilience against node capture attack than the AP, and the resilience of sensor network depends on the number of predistributed keys α and key pool size P.We will compare our scheme with these schemes by simulation experiments. The size of key pool in AP, Boujelben’s, and Erfani’s schemes isP=10000. Similar to the experiments environment in [16], the keyring size is 100 in Erfani’s scheme.As shown in Figures10 and 11, the experimental results prove that, in the random key predistribution schemes, the resilience against node capture gets worse and worse with the number of captured nodes increasing, because the nodes store a large number of keys. In Boujelben et al. scheme, the nodes store matrixes instead of keys, so the resilience against node capture is better than that in the AP scheme, but the storage cost is λ times that of AP (λ is the matrix parameter).Figure 10
Resilience against the sensor capture.Figure 11
Resilience against the sink node capture.In our scheme, the sensor node does not store any key, and the sink node stores the CRPs rather than the key as well, so perfect resilience against node capture is provided.


## 4.5. PUF Security

In this paper, PUF is the core of the authentication and key distribution. The security of the PUF is crucially important. The main threats to some PUF-based schemes [36] include man-in-the-middle attack, replay attack, and the modelling attack to the PUF, because the PUF CRPs are transmitted in plain form. A PUF is considered failed when the adversaries can guess more than 75% bits of the response to a challenge after obtaining enough amount of CRPs of a given PUF. In our proposal, the response, generated by a PUF on a sensor on-the-fly, is not sent to the sink node directly but is utilized as an encryption key to encrypt the challenge. Such design can successfully protect the PUF from cloning attack, modelling attack, and side channel attacks, including electromagnetic analysis attack and differential fault attack. The eavesdropping is invalid, since all the transmitted messages are encrypted with symmetric algorithm (e.g., AES), the attackers cannot get any plain information about responses or keys. The scheme can withstand the man-in-the-middle attack and tamper attack, since the encrypted response protects its integrity in the wireless communications.In the replay attack, an attacker resends an old message, which has been sent for key generation request. In the proposed approach, timestamp has been used in generating the temporary key to prevent the replay attack. Besides, the session key is randomly generated between the sink node and sensor and will not be the same as the a priori key. An attacker can continuously resend an old message to consume the energy of sensor nodes; however, these messages will be discarded.Table3 shows the comprehensive comparison results among different authentication and key distribution schemes for sensor networks proposed in recent years. Unlike the key predistribution schemes, for example, AP [10], our scheme is perfectly resilient against node capture attacks, because a sensor does not prestore any keys that might secure other sensors’ communications. PUF CRPs provide a type of authentication by a challenge-response mechanism, but Chatterjee’s scheme [23] does not guarantee mutual authentication between two parties. In addition, PUFs provide another type of security guarantee implied by their unclonability and tamper evidence. Such property is only available to PUF-based solutions. However, PUF CRPs are sent as plaintext in [23, 25], which make them vulnerable to impersonation attack, but we avoid this in our scheme by encrypting the response of the CRPs. Also, in [14, 23, 25, 27], they used public key algorithm that consumed more computation overhead than the AP [10] and our proposal.Table 3
Comparisons of different key distribution schemes.
PropertyOursAP [10]Lee and Kim [14]Erfani et al. [16]Chatterjee et al. [25]Li et al. [27]Public key encryptionNoNoYesNoYesYesKey predistributionNoYesNoYesNoNoPerfect resilience against node captureYesNo—No——PUF-basedYesNoNoNoYesYesMutual authenticationYesNoYesYesNoYesResistant to modelling attacksYes———NoNoResistant to eavesdropping attacksYes———YesYesResistant to collusion attacksYes——Yes———: not applicable.


## 5. Conclusions

In a dynamic sensor network, how to ensure two communicating (static or mobile) nodes authenticate and share a pairwise key is difficult because the sensors’ mobility pattern or track is unknown. In this paper, we propose a mutual-authenticated key distribution scheme for the intracluster communication. In order to reduce the storage overhead and the key exposure risk of low-end sensors, we employ a CRO Physical Unclonable Function (PUF) in the mutual-authentication process, which has the lightweight, unclonability, and unpredictability advantages. Compared with the classical PUF challenge-response authentication mechanism in some literatures, the PUF response is not transmitted in plain forms so as to resist the modelling attacks on PUFs. We also demonstrate that the proposed scheme improves the secure connectivity and other performances by analysis and experiments.



---

*Source: 5532683-2021-05-03.xml*