# An Improved Broadcast Authentication Protocol for Wireless Sensor Networks Based on the Self-Reinitializable Hash Chains

Authors: Haiping Huang; Qinglong Huang; Fu Xiao; Wenming Wang; Qi Li; Ting Dai
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Broadcast authentication is a fundamental security primitive in wireless sensor networks (WSNs), which is a critical sensing component of IoT. Although symmetric-key-basedμTESLA protocol has been proposed, some concerns about the difficulty of predicting the network lifecycle in advance and the security problems caused by an overlong long hash chain still remain. This paper presents a scalable broadcast authentication scheme named DH-μTESLA, which is an extension and improvement of μTESLA and Multilevel μTESLA, to achieve several vital properties, such as infinite lifecycle of hash chains, security authentication, scalability, and strong tolerance of message loss. The proposal consists of the t,n-threshold-based self-reinitializable hash chain scheme (SRHC-TD) and the d-left-counting-Bloom-filter-based authentication scheme (AdlCBF). In comparison to other broadcast authentication protocols, our proposal achieves more security properties such as fresh node’s participation and DoS resistance. Furthermore, the reinitializable hash chain constructed in SRHC-TD is proved to be secure and has less computation and communication overhead compared with typical solutions, and efficient storage is realized based on AdlCBF, which can also defend against DoS attacks.


---

## Body

## 1. Introduction

With the rapid development of Internet of Things (IoT) and 5G technology, the number of sensing terminals, such as various sensor nodes and tiny IoT devices, has also increased dramatically [1–3]. Edge computing is a new emerging paradigm that overcomes the scalability problem of traditional wireless sensor networks (WSNs) architecture [4–7]. The combination of wireless sensor networks and edge computing can more effectively deploy the network and process a large amount of sensory data from sensor nodes.In hostile and harsh conditions, such as large-scale agricultural monitoring and homeland border detection, sensor nodes are usually deployed to the monitoring area by aircraft, and the base station may be a temporarily deployed edge server such as mobile weather station or UAVs (unmanned aerial vehicles for agricultural surveillance), whose computation and storage capacities are not always powerful. These sensor nodes are difficult to recycle and need to be replenished after damage or exhaustion. For effectively acquiring and perceiving data from massive sensors, the base station (or edge server) usually sends commands or application updating data packets to vast sensor nodes through broadcasting. It is necessary for sensor nodes to authenticate the identity of the sender, together with the validity and integrity of these messages [8–11]. Thus, the broadcast authentication becomes an essential service in practical and secure wireless sensor networks or IoT. The broadcast authentication protocol in wireless sensor network needs to meet the following three principles [12]: (1) any malicious receiver being able to hardly forge any packet from the sender; (2) low communication, computation, and storage overheads; and (3) tolerance of message loss or fault.Based on the three principles, many broadcast authentication protocols applied in WSNs have appeared sequentially.μTESLA [13] is one of the most representative broadcast authentication protocols. The contributions of μTESLA lie in the low computation strength and high authentication speed by using the special asymmetry mechanism, which is realized by delaying the disclosure of symmetric keys. Subsequently, an improved version named Multilevel μTESLA [14] has been proposed to extend the capability of μTESLA. With the continuous concern regarding broadcast authentication, some novel protocols [15–19] sequentially emerge in WSNs, followed by the Multilevel μTESLA protocol.Although these protocols are distinguished from each other, most of them are the enhanced versions ofμTESLA or Multilevel μTESLA, which contribute to the safety and efficiency by improving the organization form of broadcast authentication. However, the disadvantages of them cannot be ignored. First, a traditional asymmetric mechanism, such as non-light-weight public key cryptography (PKC) in [20], is not encouraged to be used in broadcast authentication due to its high computation overheads and impracticability in resource-constrained sensor networks. Second, the light-weight hash key chain is adopted by most of these protocols. However, an overlong hash chain may lead to the increase of storage overhead and information divulging risk on the base station, especially in the edge computing scenario, and a short one will be consumed quickly, because the running time of the network is uncertain and the entire lifetime of a large-scale network is hard to predict. Third, a long hash chain has security risks itself. Håstad and Näslund [21] show that, in a hash chain composed of the same hash functions, the attackers inverting the k-th iteration are actually k times easier than inverting a single hash function. Kwon and Hong [22] find some future keys of μTESLA by utilizing time-memory-data-tradeoff technique in a 64-bit hash chain.Furthermore, in complex and dangerous environments, it is necessary to authenticate the fresh node supplemented in edge computing scenario. The absence of the trusted authentication interactions is easy for the vicious nodes to create fake data packets. In a severe case, the base station will suffer DoS attacks as an authentication centre. Similarly, the sensor nodes also need the ability to quickly distinguish valid messages from fake ones against DoS attacks. This means that these protocols cannot achieve a satisfactory security level.In order to address the above problems in the existing protocols, further improve the security, and broaden application scenarios, this paper puts forward a reformed broadcast authentication protocol named DH-μTESLA. The main contributions of our proposal can be described as follows:(i)
We design at,n-threshold-based self-reinitializable hash chain scheme (SRHC-TD), which constructs a reinitializable hash chain securely to improve the lifecycle of hash chains while keeping a desirable efficiency. In our scheme, hash chains will continue to generate without the need to predict and determine the lifetime of the network in advance. This scheme also has a strong tolerance to message loss.(ii)
Ad-left-counting-Bloom-filter-based authentication scheme (AdlCBF) is proposed, which can handle the secure authentication of fresh sensor nodes. The AdlCBF scheme will effectively achieve the demands of authentication speed, memory space, and data security with the increasing number of sensor nodes joining the network. This scheme ensures that our protocol is well scalable for a large-scale network, and it can effectively resist DoS attacks on the base station caused by the request of massive illegal nodes.The remainder of this paper is organized as follows. Section2 gives the overview of related work. Some notations and concepts are defined in Section 3. The SRHC-TD scheme and AdlCBF scheme are described in Section 4 and Section 5, respectively. In Section 6, we describe the DH-μTESLA protocol in detail. Section 7 illustrates the security analysis. The evaluation and comparison of the proposed schemes are described in Section 8. Section 9 concludes this paper.


## 2. Related Work

### 2.1. Hash Chain

The hash chain was first proposed by Lamport in 1981 and has been widely used in various applications due to its high security and efficiency, including one-time password (OTP) system [23] and broadcast authentication [24]. However, after all hash values of a hash chain are consumed, a new hash chain must be generated, which is expensive in most applications. For example, in OTP system, the commitment of a new hash chain and corresponding parameters need to be reregistered to the server or the client, which will consume significant computation and communication overhead [25]. In μTESLA protocol, the problem of unicasting the initial parameters on a node-to-node basis is quite expensive [24]. In order to solve this problem, many schemes have been put forward.Bicakci and Baykal [26] and Di Pietro et al. [27] employed public key cryptography to generate a hash chain. Although the problem of limited length was solved, the computational overhead was increased (one public key operation takes hundreds of times as long as one hash operation). Park [25] constructed an infinite length hash chain by employing multiple short hash chains for OTP system. Nevertheless, this scheme cannot be used in broadcast authentication because the hash chain will be broken if any authentication message is lost.Goyal firstly proposed the reinitializable hash chain (RHC) scheme [28], whose main idea was that when an RHC is exhausted, a new RHC can be regenerated safely and undeniably. In 2006, Zhang and Zhu put forward the self-updating hash chain (SUHC) scheme based on Hard Core Predicate algorithm [29]. The main idea of SUHC is that it distributes the first chain’s every key value along with one bit of the second one’s commitment. In this manner, the receiver would gain all bits of the second chain’s commitment when the first one is exhausted. On the basis of [29], Zhang et al. designed the self-renewal hash chain (SRHC) scheme [30] as the improvement of SUHC, which has a different selection algorithm of random numbers. Xu et al. also proposed a self-updating one-time password (SUOTP) mutual authentication protocol in a similar way [31]. However, in all these schemes, the commitment can be reconstructed if and only if all the random numbers were received integrally.


### 2.2. Broadcasting Authentication Protocol in WSNs

μTESLA, originated from TESLA, was developed for source-constrained networks [13]. However, it did not overcome the problems that TESLA protocol experiences with mobile nodes losing the authentication packets caused by high velocities, requirement of loose time synchronization, limited length of hash chain, and reliability. Therefore, lots of solutions were proposed in order to address the abovementioned problems.Liu et al. [16] proposed a Scalable μTESLA that introduces the use of Merkel hash tree in μTESLA for the distribution of initial parameters and commitments and also enhances scalability by increasing the number of senders. Liu and Ning proposed Multilevel μTESLA to extend the capability of μTESLA in three aspects [14]. Firstly, it predetermines and broadcasts the initial parameters rather than unicasting them by point-to-point authentication used in μTESLA. Moreover, it adopts the multilevel hash chain to distribute broadcast messages, which prolongs the usage cycle while not increasing the length of hash chain compared with μTESLA. Finally, it uses redundant message transmission and random selection strategies to distribute key chain commitments, which improves the survivability against DoS attacks.Recently, Al Dhaheri et al. [32] proposed a TLI-μTESLA based on Multilevel μTESLA, which reduced the delay between the sender and the receiver. Kwon and Hong presented an extendable broadcast authentication scheme called X-TESLA, which considers the problem arising from sleep modes, networks failures, and idle sessions [22]. Furthermore, a long-duration TESLA [33] was proposed to overcome the finite length of hash chain used in μTESLA by employing a hierarchical hash chain.Apart from like-μTESLA protocols, there exist other types of broadcast authentication protocols that can be applied in WSNs. Groza et al. [34] designed a light-weight broadcast authentication for controller area network that achieves immediate authentication at small costs in bandwidth. Shim et al. [35] proposed an identity-based broadcast authentication scheme called EIBAS using ID-based signature. Similarly, a Chebyshev-map-based broadcast authentication is presented by Luo et al., which also uses ID-based signature [8]. However, the overhead of ID-based signature is higher than symmetric primitive. Besides, Bloom filter (BF) and counting Bloom filter (CBF) have been explicitly and widely used in the broadcast authentication schemes [36–39] to generate and verify authentication information, realize the public key management when combined with hash chain, and compare multiple MACs (message authentication codes) for reducing the message size. Kim and An employ BF-based source authentication (BFBSA) to achieve the security of packets with variable sizes in WSNs [38]. Bao et al. [39] proposed a light-weight authentication by combining BF and TESLA, which prevents active attacks and adds a privacy-preserving feature for vehicular ad hoc networks.


## 2.1. Hash Chain

The hash chain was first proposed by Lamport in 1981 and has been widely used in various applications due to its high security and efficiency, including one-time password (OTP) system [23] and broadcast authentication [24]. However, after all hash values of a hash chain are consumed, a new hash chain must be generated, which is expensive in most applications. For example, in OTP system, the commitment of a new hash chain and corresponding parameters need to be reregistered to the server or the client, which will consume significant computation and communication overhead [25]. In μTESLA protocol, the problem of unicasting the initial parameters on a node-to-node basis is quite expensive [24]. In order to solve this problem, many schemes have been put forward.Bicakci and Baykal [26] and Di Pietro et al. [27] employed public key cryptography to generate a hash chain. Although the problem of limited length was solved, the computational overhead was increased (one public key operation takes hundreds of times as long as one hash operation). Park [25] constructed an infinite length hash chain by employing multiple short hash chains for OTP system. Nevertheless, this scheme cannot be used in broadcast authentication because the hash chain will be broken if any authentication message is lost.Goyal firstly proposed the reinitializable hash chain (RHC) scheme [28], whose main idea was that when an RHC is exhausted, a new RHC can be regenerated safely and undeniably. In 2006, Zhang and Zhu put forward the self-updating hash chain (SUHC) scheme based on Hard Core Predicate algorithm [29]. The main idea of SUHC is that it distributes the first chain’s every key value along with one bit of the second one’s commitment. In this manner, the receiver would gain all bits of the second chain’s commitment when the first one is exhausted. On the basis of [29], Zhang et al. designed the self-renewal hash chain (SRHC) scheme [30] as the improvement of SUHC, which has a different selection algorithm of random numbers. Xu et al. also proposed a self-updating one-time password (SUOTP) mutual authentication protocol in a similar way [31]. However, in all these schemes, the commitment can be reconstructed if and only if all the random numbers were received integrally.


## 2.2. Broadcasting Authentication Protocol in WSNs

μTESLA, originated from TESLA, was developed for source-constrained networks [13]. However, it did not overcome the problems that TESLA protocol experiences with mobile nodes losing the authentication packets caused by high velocities, requirement of loose time synchronization, limited length of hash chain, and reliability. Therefore, lots of solutions were proposed in order to address the abovementioned problems.Liu et al. [16] proposed a Scalable μTESLA that introduces the use of Merkel hash tree in μTESLA for the distribution of initial parameters and commitments and also enhances scalability by increasing the number of senders. Liu and Ning proposed Multilevel μTESLA to extend the capability of μTESLA in three aspects [14]. Firstly, it predetermines and broadcasts the initial parameters rather than unicasting them by point-to-point authentication used in μTESLA. Moreover, it adopts the multilevel hash chain to distribute broadcast messages, which prolongs the usage cycle while not increasing the length of hash chain compared with μTESLA. Finally, it uses redundant message transmission and random selection strategies to distribute key chain commitments, which improves the survivability against DoS attacks.Recently, Al Dhaheri et al. [32] proposed a TLI-μTESLA based on Multilevel μTESLA, which reduced the delay between the sender and the receiver. Kwon and Hong presented an extendable broadcast authentication scheme called X-TESLA, which considers the problem arising from sleep modes, networks failures, and idle sessions [22]. Furthermore, a long-duration TESLA [33] was proposed to overcome the finite length of hash chain used in μTESLA by employing a hierarchical hash chain.Apart from like-μTESLA protocols, there exist other types of broadcast authentication protocols that can be applied in WSNs. Groza et al. [34] designed a light-weight broadcast authentication for controller area network that achieves immediate authentication at small costs in bandwidth. Shim et al. [35] proposed an identity-based broadcast authentication scheme called EIBAS using ID-based signature. Similarly, a Chebyshev-map-based broadcast authentication is presented by Luo et al., which also uses ID-based signature [8]. However, the overhead of ID-based signature is higher than symmetric primitive. Besides, Bloom filter (BF) and counting Bloom filter (CBF) have been explicitly and widely used in the broadcast authentication schemes [36–39] to generate and verify authentication information, realize the public key management when combined with hash chain, and compare multiple MACs (message authentication codes) for reducing the message size. Kim and An employ BF-based source authentication (BFBSA) to achieve the security of packets with variable sizes in WSNs [38]. Bao et al. [39] proposed a light-weight authentication by combining BF and TESLA, which prevents active attacks and adds a privacy-preserving feature for vehicular ad hoc networks.


## 3. Preliminaries

### 3.1. Notation

The symbols and notations used in our protocol are listed in Table1.Table 1
Notations used in the protocol.
SymbolsDescriptionnLength of hash chainLOutput length of hash functionSThe secret that needs to be sharedIiSecret sharesPU, PU′Seed of hash chainmLNumber of secret sharesξi, ζiKey authentication codeTcCurrent time used to synchronize the time of the whole networkΔMaximum clock difference between the sender and the receiverTiThe start time of intervaliTintDuration of each time intervalδDisclosure delaySiSensor nodeKSi, KPiPrivate key and public key of sensor node, respectivelySBBase stationIDi, IDBThe addresses of sensor node and base station, respectivelyN, NiRandom nonceAdditionally,Mmtype=mtype,sadr,dadr,∗ is designed as a message format, where mtype is the message type, sadr is the source address, dadr is the destination address, and ∗ represents some additional options.


### 3.2. Basic Definitions

Definition 1 (partition).
Partition is the process of transforming a binary number ofL bits into m2l-radix numbers. This process can be simply represented as L=m,l or m=⌈L/l⌉. If l cannot divide L exactly, several zeros whose number is exactly the remainder should be filled on the front of the binary number.Definition 2 (repetition vector, value vector, and repetition degree).
Suppose that there aremm≥1 variables, and the value of each variable is in a set containing nn≥1 integers. For a group of these variables, there are q1≤q≤minm,n different values among these variables, which are denoted as vi,i=1,2,…,q. Then, m−q is called repetition degree and v1,v2,…,vq is called value vector. Suppose that there are pi1≤pi≤m variables whose value is vi, such that ∑i=1qpi=m. Then, p1,p2,…,pq is called repetition vector.Definition 3 (repetition rate).
Form variables, the values are a set of n integers, such that repetition degree is m−q. Then the number of assignments of these variables is(1)Sm,nq=Cmp1,Cm−p1p2,…,Cpqpq⋅n!n−q!.
The repetition ratePq is defined as(2)Pq=Sm,nq∑i=1minm,nSm,ni.Definition 4 (difficulty degree).
Suppose that there arem integers whose repetition degree is m−q. Then q is called difficulty degree.Definition 5 (average difficulty degree).
Suppose that there arem integers, whose difficulty degree is q and repetition rate is Pq. Then average difficulty degree Dq is defined as the weighted sum of difficulty degree:(3)Dq=∑q=1minm,nPq⋅q.Definition 6 (Mignotte’s sequence).
Letn and t be integers; n≥2, and 2≤t≤n. A t,n-Mignotte sequence is a sequence of positive integers m1<m2<⋯<mn, such that, for all 1≤i<j≤n and mi,mj=1, mn−t+2⋅mn−t+3⋅⋯⋅mn<m1⋅m2⋅⋯⋅mt.


## 3.1. Notation

The symbols and notations used in our protocol are listed in Table1.Table 1
Notations used in the protocol.
SymbolsDescriptionnLength of hash chainLOutput length of hash functionSThe secret that needs to be sharedIiSecret sharesPU, PU′Seed of hash chainmLNumber of secret sharesξi, ζiKey authentication codeTcCurrent time used to synchronize the time of the whole networkΔMaximum clock difference between the sender and the receiverTiThe start time of intervaliTintDuration of each time intervalδDisclosure delaySiSensor nodeKSi, KPiPrivate key and public key of sensor node, respectivelySBBase stationIDi, IDBThe addresses of sensor node and base station, respectivelyN, NiRandom nonceAdditionally,Mmtype=mtype,sadr,dadr,∗ is designed as a message format, where mtype is the message type, sadr is the source address, dadr is the destination address, and ∗ represents some additional options.


## 3.2. Basic Definitions

Definition 1 (partition).
Partition is the process of transforming a binary number ofL bits into m2l-radix numbers. This process can be simply represented as L=m,l or m=⌈L/l⌉. If l cannot divide L exactly, several zeros whose number is exactly the remainder should be filled on the front of the binary number.Definition 2 (repetition vector, value vector, and repetition degree).
Suppose that there aremm≥1 variables, and the value of each variable is in a set containing nn≥1 integers. For a group of these variables, there are q1≤q≤minm,n different values among these variables, which are denoted as vi,i=1,2,…,q. Then, m−q is called repetition degree and v1,v2,…,vq is called value vector. Suppose that there are pi1≤pi≤m variables whose value is vi, such that ∑i=1qpi=m. Then, p1,p2,…,pq is called repetition vector.Definition 3 (repetition rate).
Form variables, the values are a set of n integers, such that repetition degree is m−q. Then the number of assignments of these variables is(1)Sm,nq=Cmp1,Cm−p1p2,…,Cpqpq⋅n!n−q!.
The repetition ratePq is defined as(2)Pq=Sm,nq∑i=1minm,nSm,ni.Definition 4 (difficulty degree).
Suppose that there arem integers whose repetition degree is m−q. Then q is called difficulty degree.Definition 5 (average difficulty degree).
Suppose that there arem integers, whose difficulty degree is q and repetition rate is Pq. Then average difficulty degree Dq is defined as the weighted sum of difficulty degree:(3)Dq=∑q=1minm,nPq⋅q.Definition 6 (Mignotte’s sequence).
Letn and t be integers; n≥2, and 2≤t≤n. A t,n-Mignotte sequence is a sequence of positive integers m1<m2<⋯<mn, such that, for all 1≤i<j≤n and mi,mj=1, mn−t+2⋅mn−t+3⋅⋯⋅mn<m1⋅m2⋅⋯⋅mt.


## 4. (t, n)-Threshold-Based Self-Reinitializable Hash Chain Scheme

### 4.1.t,n-Mignotte’s Threshold Secret Sharing Scheme

Given at,n-Mignotte sequence, the scheme works as follows [40]:(1)
The secretS is chosen as a random integer such that β<S<α, wherein α=m1⋅m2…mt and β=mn−t+2⋅mn−t+3…mn.(2)
The secret shareIi is chosen by the formula Ii=Smodmi, for all 1≤i≤n.(3)
Givent distinct shares Ii1,Ii2,…,Iit, the secret S can be recovered using the Chinese Remainder Theorem, and any two such S are congruent moduli mi1⋅mi2…mit:(4)x≡Ii1modmi1,x≡Ii2modmi2,⋮x≡Iitmodmit.


### 4.2.t,n-Mignotte’s Threshold Secret Sharing Scheme

The proposed self-reinitializable hash chain has multiple phases: initialization, publication, verification, recombination, and self-renewal. A new hash chain can be reinitialized without extra communication when the last hash chain is exhausted. Figure1 shows the framework of the broadcast authentication process involving the construction of self-reinitializable hash chain.Figure 1
The broadcasting process uses a reinitializable one-way hash key chain. Each key is used in its corresponding time interval. After distributing the seed of the previous key chain, the next key chain’s commitmenthnPUi+1 will be calculated (I). After δ time intervals, a key will be disclosed (II). When the receiver receives the corresponding key (III), the stored packets can be authenticated (IV).


#### 4.2.1. Initialization

In the initialization phase, the sender and the receiver negotiate the length of hash chainn and a secure hash function h:0,1∗⟶0,1L with a security parameter L, which means that the output of h is an L-bits string, and L can be partitioned into mL,lL. At first, the sender does the following steps.(i)
Initialize a seed. Choose an appropriatet,mL-Mignotte sequence, denoted as x1,x2,...xmL. Unite all the sequential values xi into SU and hxi into PU, for all 1≤i≤mL.(ii)
Initialize a hash chain. ConsiderPU as the seed and generate a hash chain of length n, as shown in (I) of Figure 1:(5)PU,hPU,h2PU,…,hnPU,wheren−1 is an integral multiple of mL.(iii)
Generate the next chain. Same as the first two steps, we choose a newt,mL′-Mignotte sequence and compute SU′ and PU′. Then, we get a new hash chain:(6)PU′,hPU′,h2PU′,…,hnPU′.PartitionhnPU′ into mL2lL-radix numbers, denoted as c1,c2,…,cmL, whose repetition degree is mL−qL and difficulty degree is qL:(i)
Letα=x1⋅x2,…,xt and β=xmL−t+2⋅xmL−t+3,…,xmL. If t=qL and β<hNPU′<α, then select hnPU′ as the secret S. Otherwise, return to the previous step.(ii)
According toIi=Smodxi, calculate mL secret shadows I1,I2,…,ImL.(iii)
Compute the key authentication codes (KAC), denoted asζi and ξi−1, where ξi−1=hn−iPU⊕ζi, ζi=xck+1,Ick+1≪ri, k=imodmL, and ri is the number made up of the i-th bit, the 2i-th bit, the 3i-th bit, and so on of PU. In particular, ξ0=hn−1PU⊕ζ1, ζ1=xc1+1,Ic1+1≪r1, and r1=SU.(iv)
PublishhnPU,ξ0 to the verifier securely. Actually, this pair of parameters will be sent cryptographically to the nodes in Algorithm 1 or 2 of Section 5.Algorithm 1: Direct authentication of fresh nodes.
(1)
for fresh node Sido(2)
Si⟶SB: Ma=a′′,IDB,IDi,KPi,Ni(3)
SB: computes and compares the fingerprint IDi,KPi(4)
if the fingerprint is true then(5)
SB⟶Si: Mar=a′r′,IDi,IDB,A1,SignA1,KSB, where A1=TchnPUc,ξ0c,…TscTi′TintδNB(6)
else(7)
Authentication failure(8)
end if(9)
end forAlgorithm 2: Authentication of fresh nodes with cluster heads.
(1)
for fresh node Sido(2)
Si⟶SB: Ma=a′′,IDB,IDi,KPi,Ni(3)
SCH⟶SB: Maa=a′′,IDB,IDCH,KPCH,NCH,IDB,IDi,KPi,Ni(4)
SB: computes and compares the fingerprints IDi,KPi and IDCH,KPCH(5)
if the fingerprint IDi,KPi is true thenif the fingerprint IDCH,KPCH is true then(6)
SB⟶Si: Mar=a′′,IDi,IDB,A2,SignA2,KSB, where A2=′SCHislegal′TchnPUc,ξ0c,…TscTi′TintδNB(7)
SB⟶SCH: Marr=a′rr′,IDCH,IDB,A3,SignA3,KSB, where A3=s′iislegal′NB(8)
else(9)
SB⟶Si: Mar=a′rr′,IDi,IDB,A4,SignA4,KSB, where A4=′SCHisillegal′TchnPUc,ξ0c,…TscTi′TintδNB(10)
end if(11)
else(12)
if the fingerprint IDCH,KPCH is true then(13)
SB⟶SCH: Marr=a′rr′,IDCH,IDB,A5,SignA5,KSB, where A5=s′iisillegal′NB(14)
else(15)
Authentication failure(16)
end if(17)
end if(18)
end for


#### 4.2.2. Publication

In the phase of publication, the sender computes and distributes hash values and the corresponding certification proofs for verification. For thei-th (i=1,2,…,n−1) distribution, the sender does the following steps:(i)
Compute or retrieve the link values of hash chainhn−i−1PU and hn−iPU=hhn−i−1PU(ii)
Computeζi and ξi(iii)
Construct and publish the certification framehn−iPU,ζi,ξi, while in the n-th distribution, publish the seed PU and SU, as shown in (II) of Figure 1


#### 4.2.3. Verification

For thei-th (i=1,2,…,n−1) verification, the receiver does the following steps, as shown in (III) and (IV) of Figure 1:(1)
If⌊Tc+Δ−Ti/Tint⌋<i+δ−1, the receiver receives the certification frame hn−iPU,ζi,ξi from the sender:(i)
Compute and verify whetherhhn−iPU is equal to hn−i+1PU, where hn−i+1PU is a link value sent and saved in the last valid session(ii)
Compute and verify whetherhn−iPU⊕ζi is equal to ξi−1If all checks are passed, the receiver verifies the sender successfully and then storesζi. The receiver also should store ξi in the buffer for the next verification.(2)
If⌊Tc+Δ−Ti/Tint⌋≥i+δ−1, the receiver drops hn−iPU and ζi and saves ξi. Then, it will wait for the next valid certification frame hn−jPU,ζj,ξj, where j>i.(i)
Compute and verify whetherhj−i+1hn−jPU is equal to hn−i+1PU, where hn−i+1PU is a link value sent and saved in the last valid session.(ii)
Compute and verify whetherhn−jPU⊕ζj is equal to ξj−1.If all checks are passed, the receiver verifies the sender successfully and then storesζj and ξj for the same reason.


#### 4.2.4. Recombination

After all hash values have been published, the whole hash chain has been exhausted, and the receiver has stored the seedPU and mL or fewer ζis:(i)
Compute and check whetherζi1 and ζi2 share the same sequence value xck+1 and the same secret shadow Ick+1, where i1−i2≡0modmL, k=i1modmL, and i1,i2=1,2,…,n−1(ii)
After verifications for all KACs, the receiver obtainsqL distinct sequence values xck+1 and qL distinct secret shadows Ick+1, and it also gets the ordering relation of permutation of all the mL sequence valuesThen, the receiver recovershnPU′ in two ways:(i)
Ordered verification: for all themL sequence values xc1,xc2,…,xcmL, the union of their subscripts is the commitment of the second chain, denoted by hnPU′1. That is, hnPU′1=c1,c2,…,cmL.(ii)
CRT verification: givent (t=qL) distinct pairs of xck+1,Ick+1, using CRT, the unique solution modulo xc1+1⋅xc2+1,…,xct+1 of the set of equations is the commitment of the second chain, denoted by hnPU′2.IfhnPU′1=hnPU′2, then the recombination is successful and we can obtain the new hash chain hnPU′=hnPU′1=hnPU′2.


#### 4.2.5. Self-Renewal

After recombination, the next chain starts to work and another new chain is also generated including a pair of instancesSU″ and PU″ and the corresponding commitment hnPU″. Iterations of the above processes have a result that hash chains work continuously and infinitely.


## 4.1.t,n-Mignotte’s Threshold Secret Sharing Scheme

Given at,n-Mignotte sequence, the scheme works as follows [40]:(1)
The secretS is chosen as a random integer such that β<S<α, wherein α=m1⋅m2…mt and β=mn−t+2⋅mn−t+3…mn.(2)
The secret shareIi is chosen by the formula Ii=Smodmi, for all 1≤i≤n.(3)
Givent distinct shares Ii1,Ii2,…,Iit, the secret S can be recovered using the Chinese Remainder Theorem, and any two such S are congruent moduli mi1⋅mi2…mit:(4)x≡Ii1modmi1,x≡Ii2modmi2,⋮x≡Iitmodmit.


## 4.2.t,n-Mignotte’s Threshold Secret Sharing Scheme

The proposed self-reinitializable hash chain has multiple phases: initialization, publication, verification, recombination, and self-renewal. A new hash chain can be reinitialized without extra communication when the last hash chain is exhausted. Figure1 shows the framework of the broadcast authentication process involving the construction of self-reinitializable hash chain.Figure 1
The broadcasting process uses a reinitializable one-way hash key chain. Each key is used in its corresponding time interval. After distributing the seed of the previous key chain, the next key chain’s commitmenthnPUi+1 will be calculated (I). After δ time intervals, a key will be disclosed (II). When the receiver receives the corresponding key (III), the stored packets can be authenticated (IV).


### 4.2.1. Initialization

In the initialization phase, the sender and the receiver negotiate the length of hash chainn and a secure hash function h:0,1∗⟶0,1L with a security parameter L, which means that the output of h is an L-bits string, and L can be partitioned into mL,lL. At first, the sender does the following steps.(i)
Initialize a seed. Choose an appropriatet,mL-Mignotte sequence, denoted as x1,x2,...xmL. Unite all the sequential values xi into SU and hxi into PU, for all 1≤i≤mL.(ii)
Initialize a hash chain. ConsiderPU as the seed and generate a hash chain of length n, as shown in (I) of Figure 1:(5)PU,hPU,h2PU,…,hnPU,wheren−1 is an integral multiple of mL.(iii)
Generate the next chain. Same as the first two steps, we choose a newt,mL′-Mignotte sequence and compute SU′ and PU′. Then, we get a new hash chain:(6)PU′,hPU′,h2PU′,…,hnPU′.PartitionhnPU′ into mL2lL-radix numbers, denoted as c1,c2,…,cmL, whose repetition degree is mL−qL and difficulty degree is qL:(i)
Letα=x1⋅x2,…,xt and β=xmL−t+2⋅xmL−t+3,…,xmL. If t=qL and β<hNPU′<α, then select hnPU′ as the secret S. Otherwise, return to the previous step.(ii)
According toIi=Smodxi, calculate mL secret shadows I1,I2,…,ImL.(iii)
Compute the key authentication codes (KAC), denoted asζi and ξi−1, where ξi−1=hn−iPU⊕ζi, ζi=xck+1,Ick+1≪ri, k=imodmL, and ri is the number made up of the i-th bit, the 2i-th bit, the 3i-th bit, and so on of PU. In particular, ξ0=hn−1PU⊕ζ1, ζ1=xc1+1,Ic1+1≪r1, and r1=SU.(iv)
PublishhnPU,ξ0 to the verifier securely. Actually, this pair of parameters will be sent cryptographically to the nodes in Algorithm 1 or 2 of Section 5.Algorithm 1: Direct authentication of fresh nodes.
(1)
for fresh node Sido(2)
Si⟶SB: Ma=a′′,IDB,IDi,KPi,Ni(3)
SB: computes and compares the fingerprint IDi,KPi(4)
if the fingerprint is true then(5)
SB⟶Si: Mar=a′r′,IDi,IDB,A1,SignA1,KSB, where A1=TchnPUc,ξ0c,…TscTi′TintδNB(6)
else(7)
Authentication failure(8)
end if(9)
end forAlgorithm 2: Authentication of fresh nodes with cluster heads.
(1)
for fresh node Sido(2)
Si⟶SB: Ma=a′′,IDB,IDi,KPi,Ni(3)
SCH⟶SB: Maa=a′′,IDB,IDCH,KPCH,NCH,IDB,IDi,KPi,Ni(4)
SB: computes and compares the fingerprints IDi,KPi and IDCH,KPCH(5)
if the fingerprint IDi,KPi is true thenif the fingerprint IDCH,KPCH is true then(6)
SB⟶Si: Mar=a′′,IDi,IDB,A2,SignA2,KSB, where A2=′SCHislegal′TchnPUc,ξ0c,…TscTi′TintδNB(7)
SB⟶SCH: Marr=a′rr′,IDCH,IDB,A3,SignA3,KSB, where A3=s′iislegal′NB(8)
else(9)
SB⟶Si: Mar=a′rr′,IDi,IDB,A4,SignA4,KSB, where A4=′SCHisillegal′TchnPUc,ξ0c,…TscTi′TintδNB(10)
end if(11)
else(12)
if the fingerprint IDCH,KPCH is true then(13)
SB⟶SCH: Marr=a′rr′,IDCH,IDB,A5,SignA5,KSB, where A5=s′iisillegal′NB(14)
else(15)
Authentication failure(16)
end if(17)
end if(18)
end for


### 4.2.2. Publication

In the phase of publication, the sender computes and distributes hash values and the corresponding certification proofs for verification. For thei-th (i=1,2,…,n−1) distribution, the sender does the following steps:(i)
Compute or retrieve the link values of hash chainhn−i−1PU and hn−iPU=hhn−i−1PU(ii)
Computeζi and ξi(iii)
Construct and publish the certification framehn−iPU,ζi,ξi, while in the n-th distribution, publish the seed PU and SU, as shown in (II) of Figure 1


### 4.2.3. Verification

For thei-th (i=1,2,…,n−1) verification, the receiver does the following steps, as shown in (III) and (IV) of Figure 1:(1)
If⌊Tc+Δ−Ti/Tint⌋<i+δ−1, the receiver receives the certification frame hn−iPU,ζi,ξi from the sender:(i)
Compute and verify whetherhhn−iPU is equal to hn−i+1PU, where hn−i+1PU is a link value sent and saved in the last valid session(ii)
Compute and verify whetherhn−iPU⊕ζi is equal to ξi−1If all checks are passed, the receiver verifies the sender successfully and then storesζi. The receiver also should store ξi in the buffer for the next verification.(2)
If⌊Tc+Δ−Ti/Tint⌋≥i+δ−1, the receiver drops hn−iPU and ζi and saves ξi. Then, it will wait for the next valid certification frame hn−jPU,ζj,ξj, where j>i.(i)
Compute and verify whetherhj−i+1hn−jPU is equal to hn−i+1PU, where hn−i+1PU is a link value sent and saved in the last valid session.(ii)
Compute and verify whetherhn−jPU⊕ζj is equal to ξj−1.If all checks are passed, the receiver verifies the sender successfully and then storesζj and ξj for the same reason.


### 4.2.4. Recombination

After all hash values have been published, the whole hash chain has been exhausted, and the receiver has stored the seedPU and mL or fewer ζis:(i)
Compute and check whetherζi1 and ζi2 share the same sequence value xck+1 and the same secret shadow Ick+1, where i1−i2≡0modmL, k=i1modmL, and i1,i2=1,2,…,n−1(ii)
After verifications for all KACs, the receiver obtainsqL distinct sequence values xck+1 and qL distinct secret shadows Ick+1, and it also gets the ordering relation of permutation of all the mL sequence valuesThen, the receiver recovershnPU′ in two ways:(i)
Ordered verification: for all themL sequence values xc1,xc2,…,xcmL, the union of their subscripts is the commitment of the second chain, denoted by hnPU′1. That is, hnPU′1=c1,c2,…,cmL.(ii)
CRT verification: givent (t=qL) distinct pairs of xck+1,Ick+1, using CRT, the unique solution modulo xc1+1⋅xc2+1,…,xct+1 of the set of equations is the commitment of the second chain, denoted by hnPU′2.IfhnPU′1=hnPU′2, then the recombination is successful and we can obtain the new hash chain hnPU′=hnPU′1=hnPU′2.


### 4.2.5. Self-Renewal

After recombination, the next chain starts to work and another new chain is also generated including a pair of instancesSU″ and PU″ and the corresponding commitment hnPU″. Iterations of the above processes have a result that hash chains work continuously and infinitely.


## 4.2.1. Initialization

In the initialization phase, the sender and the receiver negotiate the length of hash chainn and a secure hash function h:0,1∗⟶0,1L with a security parameter L, which means that the output of h is an L-bits string, and L can be partitioned into mL,lL. At first, the sender does the following steps.(i)
Initialize a seed. Choose an appropriatet,mL-Mignotte sequence, denoted as x1,x2,...xmL. Unite all the sequential values xi into SU and hxi into PU, for all 1≤i≤mL.(ii)
Initialize a hash chain. ConsiderPU as the seed and generate a hash chain of length n, as shown in (I) of Figure 1:(5)PU,hPU,h2PU,…,hnPU,wheren−1 is an integral multiple of mL.(iii)
Generate the next chain. Same as the first two steps, we choose a newt,mL′-Mignotte sequence and compute SU′ and PU′. Then, we get a new hash chain:(6)PU′,hPU′,h2PU′,…,hnPU′.PartitionhnPU′ into mL2lL-radix numbers, denoted as c1,c2,…,cmL, whose repetition degree is mL−qL and difficulty degree is qL:(i)
Letα=x1⋅x2,…,xt and β=xmL−t+2⋅xmL−t+3,…,xmL. If t=qL and β<hNPU′<α, then select hnPU′ as the secret S. Otherwise, return to the previous step.(ii)
According toIi=Smodxi, calculate mL secret shadows I1,I2,…,ImL.(iii)
Compute the key authentication codes (KAC), denoted asζi and ξi−1, where ξi−1=hn−iPU⊕ζi, ζi=xck+1,Ick+1≪ri, k=imodmL, and ri is the number made up of the i-th bit, the 2i-th bit, the 3i-th bit, and so on of PU. In particular, ξ0=hn−1PU⊕ζ1, ζ1=xc1+1,Ic1+1≪r1, and r1=SU.(iv)
PublishhnPU,ξ0 to the verifier securely. Actually, this pair of parameters will be sent cryptographically to the nodes in Algorithm 1 or 2 of Section 5.Algorithm 1: Direct authentication of fresh nodes.
(1)
for fresh node Sido(2)
Si⟶SB: Ma=a′′,IDB,IDi,KPi,Ni(3)
SB: computes and compares the fingerprint IDi,KPi(4)
if the fingerprint is true then(5)
SB⟶Si: Mar=a′r′,IDi,IDB,A1,SignA1,KSB, where A1=TchnPUc,ξ0c,…TscTi′TintδNB(6)
else(7)
Authentication failure(8)
end if(9)
end forAlgorithm 2: Authentication of fresh nodes with cluster heads.
(1)
for fresh node Sido(2)
Si⟶SB: Ma=a′′,IDB,IDi,KPi,Ni(3)
SCH⟶SB: Maa=a′′,IDB,IDCH,KPCH,NCH,IDB,IDi,KPi,Ni(4)
SB: computes and compares the fingerprints IDi,KPi and IDCH,KPCH(5)
if the fingerprint IDi,KPi is true thenif the fingerprint IDCH,KPCH is true then(6)
SB⟶Si: Mar=a′′,IDi,IDB,A2,SignA2,KSB, where A2=′SCHislegal′TchnPUc,ξ0c,…TscTi′TintδNB(7)
SB⟶SCH: Marr=a′rr′,IDCH,IDB,A3,SignA3,KSB, where A3=s′iislegal′NB(8)
else(9)
SB⟶Si: Mar=a′rr′,IDi,IDB,A4,SignA4,KSB, where A4=′SCHisillegal′TchnPUc,ξ0c,…TscTi′TintδNB(10)
end if(11)
else(12)
if the fingerprint IDCH,KPCH is true then(13)
SB⟶SCH: Marr=a′rr′,IDCH,IDB,A5,SignA5,KSB, where A5=s′iisillegal′NB(14)
else(15)
Authentication failure(16)
end if(17)
end if(18)
end for


## 4.2.2. Publication

In the phase of publication, the sender computes and distributes hash values and the corresponding certification proofs for verification. For thei-th (i=1,2,…,n−1) distribution, the sender does the following steps:(i)
Compute or retrieve the link values of hash chainhn−i−1PU and hn−iPU=hhn−i−1PU(ii)
Computeζi and ξi(iii)
Construct and publish the certification framehn−iPU,ζi,ξi, while in the n-th distribution, publish the seed PU and SU, as shown in (II) of Figure 1


## 4.2.3. Verification

For thei-th (i=1,2,…,n−1) verification, the receiver does the following steps, as shown in (III) and (IV) of Figure 1:(1)
If⌊Tc+Δ−Ti/Tint⌋<i+δ−1, the receiver receives the certification frame hn−iPU,ζi,ξi from the sender:(i)
Compute and verify whetherhhn−iPU is equal to hn−i+1PU, where hn−i+1PU is a link value sent and saved in the last valid session(ii)
Compute and verify whetherhn−iPU⊕ζi is equal to ξi−1If all checks are passed, the receiver verifies the sender successfully and then storesζi. The receiver also should store ξi in the buffer for the next verification.(2)
If⌊Tc+Δ−Ti/Tint⌋≥i+δ−1, the receiver drops hn−iPU and ζi and saves ξi. Then, it will wait for the next valid certification frame hn−jPU,ζj,ξj, where j>i.(i)
Compute and verify whetherhj−i+1hn−jPU is equal to hn−i+1PU, where hn−i+1PU is a link value sent and saved in the last valid session.(ii)
Compute and verify whetherhn−jPU⊕ζj is equal to ξj−1.If all checks are passed, the receiver verifies the sender successfully and then storesζj and ξj for the same reason.


## 4.2.4. Recombination

After all hash values have been published, the whole hash chain has been exhausted, and the receiver has stored the seedPU and mL or fewer ζis:(i)
Compute and check whetherζi1 and ζi2 share the same sequence value xck+1 and the same secret shadow Ick+1, where i1−i2≡0modmL, k=i1modmL, and i1,i2=1,2,…,n−1(ii)
After verifications for all KACs, the receiver obtainsqL distinct sequence values xck+1 and qL distinct secret shadows Ick+1, and it also gets the ordering relation of permutation of all the mL sequence valuesThen, the receiver recovershnPU′ in two ways:(i)
Ordered verification: for all themL sequence values xc1,xc2,…,xcmL, the union of their subscripts is the commitment of the second chain, denoted by hnPU′1. That is, hnPU′1=c1,c2,…,cmL.(ii)
CRT verification: givent (t=qL) distinct pairs of xck+1,Ick+1, using CRT, the unique solution modulo xc1+1⋅xc2+1,…,xct+1 of the set of equations is the commitment of the second chain, denoted by hnPU′2.IfhnPU′1=hnPU′2, then the recombination is successful and we can obtain the new hash chain hnPU′=hnPU′1=hnPU′2.


## 4.2.5. Self-Renewal

After recombination, the next chain starts to work and another new chain is also generated including a pair of instancesSU″ and PU″ and the corresponding commitment hnPU″. Iterations of the above processes have a result that hash chains work continuously and infinitely.


## 5.d-Left-Counting-Bloom-Filter-Based Authentication Scheme

In the combination of WSNs and edge computing, the base station is usually an edge server or is deployed as an unmanned aerial vehicle along with the sensor nodes, which requires the consideration of the computing and storage capabilities of the base station. These new sensor nodes need to be authenticated to make sure that they are not malicious nodes before joining the network. In the edge computing scenario, the storage space of the base station should be mainly used to cache and process the sensed data to provide data service for IoT applications. However, due to the participation of nodes, the base station needs to maintain a vast lookup table, which will occupy more storage space for authenticating the sensor nodes.In the AdlCBF scheme, we aim to solve two problems: one is the reduction of storage overhead in the base station, and the other is the nodes’ authentication and the parameters distribution of broadcast authentication when a new node joins the network. ECDSA is used to generate a signatureSignA,KSA with authentication information A to be signed and the private key of the source KSA. In order to reduce storage space, we introduce the d-left counting Bloom filter to construct a dlCBF to store the fingerprint for each node instead of allocating storage space directly.


### 5.1. Construction of dlCBF

In DH-μTESLA, every sensor node Si holds a public key KPi and a private key KSi allocated by the base station SB. The base station constructs a dlCBF to store the fingerprint of ID and key information instead of storing them directly. There are three steps to construct a dlCBF, as shown in Figure 2.Step 1. The base station applies a hash function H⋅ to map each node’s pair of ID and public key IDi,KPi to the true fingerprint fSi=HIDiKPi=bi,ri. Each true fingerprint consists of two parts. The first part represents the bucket index bi which corresponds to the storage location, while the second part ri is the real practicable element to be stored in the corresponding array of bi.Step 2. The base station uses the additional pseudorandom permutations P1,P2,…,Pd to expand d locations, which are the d replaceable choices for each true fingerprint fSi. As shown in Figure 2, they are actually d subarrays P1fSi=bi1,ri1,P2fSi=bi2,ri2,…,PdfSi=bid,rid, where PjfSi=bij,rij represents the tuple of storage location and practicable element corresponding to the j-th choice of fSij=1,2,…,d. There exist two kinds of collisions in dlCBF. One is that two different fingerprint replacements map to the same location of subarray; that is, P1fSi=bi1,ri1≠P1fSi=bj1,rj1; however, bi1=bj1, which means that the bucket of each subarray needs more storage cells for different elements. The other is that two true but different fingerprints have the same replacement; that is, fSi≠fSj; however, PdfSi=PdfSj. In this case, a counter is needed to record the number of the same elements stored. So, the storage cost of bucket is the sum of all counting of its storage cells.Step 3. The base station selects the leftmost one simultaneously with the minimum storage cost as the final storage location from the d choices.Figure 2
The construction ofd-left counting Bloom filter.


### 5.2. Authentication Process of Fresh Nodes

When a fresh sensor node applies to join the network, it should be authenticated and only the legal one can acquire the key chain commitment and other configuration information. Because the participation of new nodes always occurs during the whole network lifetime, the authenticating process appears before and after the network initialization phase. In other words, there are two kinds of fresh nodes: one can communicate with the base station directly and the other one is not close to it. Thus, two different cases will be discussed, respectively. In the former case, the base station authenticates the fresh node directly by Algorithm1. Meanwhile, in the latter case, the fresh node will be authenticated through cluster head by Algorithm 2.Both Algorithms1 and 2 only describe the authentication process of single fresh node. When multiple fresh sensor nodes participate in the network synchronously, the cluster heads will aggregate the authentication application messages to generate only one revised authentication message Maa and then send it to the base station that can batch-process them. Thus, these two algorithms can also be used in the multiauthentication cases.


## 5.1. Construction of dlCBF

In DH-μTESLA, every sensor node Si holds a public key KPi and a private key KSi allocated by the base station SB. The base station constructs a dlCBF to store the fingerprint of ID and key information instead of storing them directly. There are three steps to construct a dlCBF, as shown in Figure 2.Step 1. The base station applies a hash function H⋅ to map each node’s pair of ID and public key IDi,KPi to the true fingerprint fSi=HIDiKPi=bi,ri. Each true fingerprint consists of two parts. The first part represents the bucket index bi which corresponds to the storage location, while the second part ri is the real practicable element to be stored in the corresponding array of bi.Step 2. The base station uses the additional pseudorandom permutations P1,P2,…,Pd to expand d locations, which are the d replaceable choices for each true fingerprint fSi. As shown in Figure 2, they are actually d subarrays P1fSi=bi1,ri1,P2fSi=bi2,ri2,…,PdfSi=bid,rid, where PjfSi=bij,rij represents the tuple of storage location and practicable element corresponding to the j-th choice of fSij=1,2,…,d. There exist two kinds of collisions in dlCBF. One is that two different fingerprint replacements map to the same location of subarray; that is, P1fSi=bi1,ri1≠P1fSi=bj1,rj1; however, bi1=bj1, which means that the bucket of each subarray needs more storage cells for different elements. The other is that two true but different fingerprints have the same replacement; that is, fSi≠fSj; however, PdfSi=PdfSj. In this case, a counter is needed to record the number of the same elements stored. So, the storage cost of bucket is the sum of all counting of its storage cells.Step 3. The base station selects the leftmost one simultaneously with the minimum storage cost as the final storage location from the d choices.Figure 2
The construction ofd-left counting Bloom filter.


## 5.2. Authentication Process of Fresh Nodes

When a fresh sensor node applies to join the network, it should be authenticated and only the legal one can acquire the key chain commitment and other configuration information. Because the participation of new nodes always occurs during the whole network lifetime, the authenticating process appears before and after the network initialization phase. In other words, there are two kinds of fresh nodes: one can communicate with the base station directly and the other one is not close to it. Thus, two different cases will be discussed, respectively. In the former case, the base station authenticates the fresh node directly by Algorithm1. Meanwhile, in the latter case, the fresh node will be authenticated through cluster head by Algorithm 2.Both Algorithms1 and 2 only describe the authentication process of single fresh node. When multiple fresh sensor nodes participate in the network synchronously, the cluster heads will aggregate the authentication application messages to generate only one revised authentication message Maa and then send it to the base station that can batch-process them. Thus, these two algorithms can also be used in the multiauthentication cases.


## 6. DH-μTESLA Protocol

Based on the above schemes, SRHC-TD and AdlCBF, there are five phases to describe the proposed protocol: setup, bootstrap, broadcast, authentication, and a new chain generation. We explain how the base station broadcasts message at the beginning of the network.


### 6.1. Setup

The base station first generates a sequence of secret messages using SRHC-TD scheme, which is described in Section4.


### 6.2. Bootstrap

Any receiver in the network should have the commitment and relative parameters of the reinitializable one-way hash chain acquired by Algorithms1 and 2 in Section 5, including the length of hash chain n, a secure hash function h:0,1∗⟶0,1L, and the partition pair mL,lL. Besides, the legal node also gains other initial parameters, such as the current time Tc, the maximum clock difference δ between the sender and the receiver, the start time Ti of interval i, and the duration of each time interval Tint.


### 6.3. Broadcast

The lifetime of a sensor node, which is much longer than that of one-way hash chain, is divided into fixed intervals of durationTint. The sender uses the key value of hash chain to compute the message authentication code (MAC) of message packets in the current time interval. Then, the sender broadcasts the packet with MAC in the same time interval and discloses a key value of hash chain with corresponding key authentication code (KAC) after a certain delay δ×Tint.


### 6.4. Authentication

When a node receives a message packet with the MAC, it stores the packet and the MAC in the buffer. Once the node receives a key disclosure packet with KAC, the sensor node first verifies the key value with KAC, which is related to the message packet that has been stored, as described in Section4.


### 6.5. Generate a New Chain

When the hash chain runs out, the base station should generate the next chain and the node needs to recover the commitment of the new chain.


## 6.1. Setup

The base station first generates a sequence of secret messages using SRHC-TD scheme, which is described in Section4.


## 6.2. Bootstrap

Any receiver in the network should have the commitment and relative parameters of the reinitializable one-way hash chain acquired by Algorithms1 and 2 in Section 5, including the length of hash chain n, a secure hash function h:0,1∗⟶0,1L, and the partition pair mL,lL. Besides, the legal node also gains other initial parameters, such as the current time Tc, the maximum clock difference δ between the sender and the receiver, the start time Ti of interval i, and the duration of each time interval Tint.


## 6.3. Broadcast

The lifetime of a sensor node, which is much longer than that of one-way hash chain, is divided into fixed intervals of durationTint. The sender uses the key value of hash chain to compute the message authentication code (MAC) of message packets in the current time interval. Then, the sender broadcasts the packet with MAC in the same time interval and discloses a key value of hash chain with corresponding key authentication code (KAC) after a certain delay δ×Tint.


## 6.4. Authentication

When a node receives a message packet with the MAC, it stores the packet and the MAC in the buffer. Once the node receives a key disclosure packet with KAC, the sensor node first verifies the key value with KAC, which is related to the message packet that has been stored, as described in Section4.


## 6.5. Generate a New Chain

When the hash chain runs out, the base station should generate the next chain and the node needs to recover the commitment of the new chain.


## 7. Security Analysis

### 7.1. Resistance with Chosen Plaintext Attack

Except the initial seed and the commitment, each key of a hash chain is not only the ciphertext (as the output) but also the plaintext (as the input) of the hash function. Thus, each value shares the same length, which reduces the key space as well as the cracked time. Thus, it is easy to suffer from the chosen plaintext attack. In our scheme, the KAC consists of two parts, which can be used to check whether the shared secret has been changed. Allζi are different because of the left shift operation, which can prevent the chosen plaintext attacks effectively.


### 7.2. Fault Tolerance

The length of key chainn−1 is an integral multiple of mL, so all xci+1,Ici+1 can be transmitted cyclically when the network is running. Thus, it can avoid the situation where one missing secret shadow would make the secret hnPU′ unsolvable. Before a hash chain is running out, each receiver stores mLxci+1,Ici+1 at most, while only qL distinct sequence values xci+1 and secret shadows Ici+1 are needed to recover the secret hnPU′. In other words, the number of faults or missing message packets should be less than mL−qL. The highest packet loss rate that our solution can tolerate is mL−qL/mL.Assuming that the probability that a sensor node cannot receive a key disclosure packet isf and n−1=k⋅mL which means that the same secret shadow will be disclosed k times, the probability that a certain secret shadow Ici+1 is not received by the sensor node is reduced to fk. Suppose that the sensor node has a half chance to receive the packet (it will be lower in practice); that is, f=0.5 and k=10. The probability that the sensor node loses Ici+1 is less than 0.1%. In our scheme, in order to recover the commitment of next hash chain, only qL secret shadows are needed. Thus, the probability that the sensor nodes receives qL different secret shadows is CmLqL1−fkqL⋅fkmL−qL. Then, the probability that the sensor node cannot obtain the commitment of next hash chain is(7)pd=1−CmLqL1−fkqL⋅fkmL−qL.If the length of hash chain is 321, which can cover about 5 minutes with time interval of 1 second,qL=16 and mL=32; the probability that the sensor node cannot recover the commitment of next hash chain when the hash chain runs out is pd≤5.9×10−40.


### 7.3. DoS Attack Tolerance

Both the base station and the sensor node are vulnerable to DoS attack that is hard to prevent. The attacker may forge the message, such as key distribution message and authentication message, to confuse both the sensor node and the base station.In MultilevelμTESLA, when the lower level chain draws to an end, the upper level is used to authenticate the commitment for the next lower level chain by commitment distribution message (CDM),(8)CDMi=Ki+2,0MACKiiKi+2,0Ki−1,in its i-th interval, where ∥ denotes concatenation, Ki+2,0 is the commitment of the lower level chain, and Ki−1 or Ki is a key of the upper level chain. The attacker can fabricate a CDM by replacing Ki+2,0 or MACKiiKi+2,0 and the sensor node can easily verify Ki−1 with Ki−2 which is released in CDMi−1. Nevertheless, the sensor node has no way to authenticate other parameters in CDMi because the key will be released later. In order to solve this problem, Multilevel μTESLA provides two variants, needing more buffers (hundreds of bytes) to store multiple CDMs in sensor node or requiring more storage space for additional precomputed chains in the base station and larger payload of CDMs. Meanwhile, in our protocol, the commitment of next chain is released with the distribution of keys. When a sensor node received a certification frame hn−iPU,ζi,ξi, it could be authenticated immediately by a single XOR operation. The sensor node can distinguish the validity of the message at a very fast speed without a little buffer (about 8 bytes). With the same condition in Section 7.2, assume that the bandwidth is 10 kbps and the hash function is 64 bits; the relative communication overhead is just 64⋅2/10240⋅1=0.0125.On the other hand, a fresh sensor node needs to be authenticated before joining the network. An attacker may launch the flood attack toward the base station with forged messages containing valid public keys, which can be obtained by eavesdropping. However, the attacker cannot alter the ID information ofMa or Maa. Even if the ID can be forged, after receiving the same authentication message multiple times, the base station will find that it is being attacked. Meanwhile, a sensor node will be aware that an attack is going on and alert the base station when it fails to receive the authentication response message Mar or receive the wrong responses multiple times in one round. Also, when a cluster head receives the authentication message Ma, the authentication response message Mar, or added authentication response message Maar multiple times from the same node, it will be aware that an attack is going on and alert the base station.


### 7.4. Provable Security

Because SRHC-TD is formed by many chains, we will discuss the provable security of SRHC-TD with two cases: one is the successive key in the same hash chain; and the other is the head-tail key connecting the current hash chain and the next one.We choose the Random Oracle model to analyse the provable security of SRHC-TD. In the Random Oracle model, attackers have the polynomial calculation ability of any secret parameterk. The reliability of all algorithms of SRHC-TD is determined by the secret parameter k. Specifically, the probability of cracking hash functions is the reciprocal regarding the exponential function of k, the probability of cracking CRT is the reciprocal regarding the power function of k, and the probability of cracking partition algorithm is the reciprocal regarding the logarithmic function of k:(a)
After theith time interval, we suppose that the receivers (including the attackers) have received hn−iPU,ζi,ξi. Attackers must forge hfaken−i−1 and ζi+1 within the i+1th time interval and make them meet the equations hhfaken−i−1=hn−iPU and hfaken−i−1⊕ζi+1=ξi. Suppose that the calculation ability of attackers can be represented as the polynomial Tadvk and they can query Oracle any number of times within each time interval. If the probability of cracking hash operation is e−k, the probability of breaking SRHC-TD can be expressed as(9)PrAdvk=1=Prhfaken−i−1=hn−i−1PU,hfaken−i−1⊕ζi+1=ξi=Tadvkek⋅ek,whereTadvk can be expressed as the general form of polynomial. So, we can deduce PrAdvk=1=ankn+an−1kn−1+⋯+a1k+a0/e2k. Evaluating the limit value of PrAdvk=1, we can deduce(10)limk⟶∞PrAdvk=1=limk⟶∞ankne2k=limk⟶∞an⋅nkn−12⋅e2k=⋯=limk⟶∞an⋅n!2n⋅e2k=0.(b)
At the ends of then−1-th time interval, only PU has not been published in the first hash chain. The receivers (including the attackers) have obtained mL number of ζi. Attackers must forge PU and PUfake within the nth time interval and make them meet the following conditions: (1) hPUfake=hPU; (2) when i1−i2≡0modmL, ζi1 and ζi2 contain the same sequence value xck+1 and the same shadow Ick+1, where k=i1+1modmL, i1,i2=1,2,…,n−1; (3) the solution hnPU′1 derived from the proof method of ordering is the same as the solution hnPU′2 derived from the proof method of CRT. The fake value PUfake must meet all the three conditions. We suppose that the calculation ability of attackers can be represented as the polynomial Tadvk and they can query Oracle any number of times within each time interval. If the probability of cracking hash operation is e−k, the probability of cracking CRT is k−e, and the probability of cracking partition algorithm is 1/lnk; then the probability of breaking SRHC-TD can be expressed as(11)PrAdvk=1=PrhPUfake=hPU,hnPU′1=hnPU′2xci1+1modmL+1=xci2+1modmL+1,Ici1+1modmL+1=Ici1+1modmL+1=Tadvkek⋅ke⋅lnk,where Tadvk can be expressed as the general form of polynomial Tadvk=ankn+an−1kn−1+⋯+a1k+a0. Evaluating the limit value of PrAdvk=1, we can deduce(12)limk⟶∞PrAdvk=1=limk⟶∞anknek⋅ke⋅lnk=limk⟶∞ankn−eek⋅lnk=limk⟶∞ann−ekn−e−1ek⋅lnk+1/k=⋯=limk⟶∞ann−e!ek⋅lnk+n−e/k−⋯+n−e−1!/kn−e=limk⟶∞ann−e!ek⋅lnk=0.Considering the above two cases, there exists a positive integerN, when k>N; for any ε, there must be PrAdvk=1<ε. So, the successful probability of attackers can be ignored and the SRHC-TD scheme has provable security.


## 7.1. Resistance with Chosen Plaintext Attack

Except the initial seed and the commitment, each key of a hash chain is not only the ciphertext (as the output) but also the plaintext (as the input) of the hash function. Thus, each value shares the same length, which reduces the key space as well as the cracked time. Thus, it is easy to suffer from the chosen plaintext attack. In our scheme, the KAC consists of two parts, which can be used to check whether the shared secret has been changed. Allζi are different because of the left shift operation, which can prevent the chosen plaintext attacks effectively.


## 7.2. Fault Tolerance

The length of key chainn−1 is an integral multiple of mL, so all xci+1,Ici+1 can be transmitted cyclically when the network is running. Thus, it can avoid the situation where one missing secret shadow would make the secret hnPU′ unsolvable. Before a hash chain is running out, each receiver stores mLxci+1,Ici+1 at most, while only qL distinct sequence values xci+1 and secret shadows Ici+1 are needed to recover the secret hnPU′. In other words, the number of faults or missing message packets should be less than mL−qL. The highest packet loss rate that our solution can tolerate is mL−qL/mL.Assuming that the probability that a sensor node cannot receive a key disclosure packet isf and n−1=k⋅mL which means that the same secret shadow will be disclosed k times, the probability that a certain secret shadow Ici+1 is not received by the sensor node is reduced to fk. Suppose that the sensor node has a half chance to receive the packet (it will be lower in practice); that is, f=0.5 and k=10. The probability that the sensor node loses Ici+1 is less than 0.1%. In our scheme, in order to recover the commitment of next hash chain, only qL secret shadows are needed. Thus, the probability that the sensor nodes receives qL different secret shadows is CmLqL1−fkqL⋅fkmL−qL. Then, the probability that the sensor node cannot obtain the commitment of next hash chain is(7)pd=1−CmLqL1−fkqL⋅fkmL−qL.If the length of hash chain is 321, which can cover about 5 minutes with time interval of 1 second,qL=16 and mL=32; the probability that the sensor node cannot recover the commitment of next hash chain when the hash chain runs out is pd≤5.9×10−40.


## 7.3. DoS Attack Tolerance

Both the base station and the sensor node are vulnerable to DoS attack that is hard to prevent. The attacker may forge the message, such as key distribution message and authentication message, to confuse both the sensor node and the base station.In MultilevelμTESLA, when the lower level chain draws to an end, the upper level is used to authenticate the commitment for the next lower level chain by commitment distribution message (CDM),(8)CDMi=Ki+2,0MACKiiKi+2,0Ki−1,in its i-th interval, where ∥ denotes concatenation, Ki+2,0 is the commitment of the lower level chain, and Ki−1 or Ki is a key of the upper level chain. The attacker can fabricate a CDM by replacing Ki+2,0 or MACKiiKi+2,0 and the sensor node can easily verify Ki−1 with Ki−2 which is released in CDMi−1. Nevertheless, the sensor node has no way to authenticate other parameters in CDMi because the key will be released later. In order to solve this problem, Multilevel μTESLA provides two variants, needing more buffers (hundreds of bytes) to store multiple CDMs in sensor node or requiring more storage space for additional precomputed chains in the base station and larger payload of CDMs. Meanwhile, in our protocol, the commitment of next chain is released with the distribution of keys. When a sensor node received a certification frame hn−iPU,ζi,ξi, it could be authenticated immediately by a single XOR operation. The sensor node can distinguish the validity of the message at a very fast speed without a little buffer (about 8 bytes). With the same condition in Section 7.2, assume that the bandwidth is 10 kbps and the hash function is 64 bits; the relative communication overhead is just 64⋅2/10240⋅1=0.0125.On the other hand, a fresh sensor node needs to be authenticated before joining the network. An attacker may launch the flood attack toward the base station with forged messages containing valid public keys, which can be obtained by eavesdropping. However, the attacker cannot alter the ID information ofMa or Maa. Even if the ID can be forged, after receiving the same authentication message multiple times, the base station will find that it is being attacked. Meanwhile, a sensor node will be aware that an attack is going on and alert the base station when it fails to receive the authentication response message Mar or receive the wrong responses multiple times in one round. Also, when a cluster head receives the authentication message Ma, the authentication response message Mar, or added authentication response message Maar multiple times from the same node, it will be aware that an attack is going on and alert the base station.


## 7.4. Provable Security

Because SRHC-TD is formed by many chains, we will discuss the provable security of SRHC-TD with two cases: one is the successive key in the same hash chain; and the other is the head-tail key connecting the current hash chain and the next one.We choose the Random Oracle model to analyse the provable security of SRHC-TD. In the Random Oracle model, attackers have the polynomial calculation ability of any secret parameterk. The reliability of all algorithms of SRHC-TD is determined by the secret parameter k. Specifically, the probability of cracking hash functions is the reciprocal regarding the exponential function of k, the probability of cracking CRT is the reciprocal regarding the power function of k, and the probability of cracking partition algorithm is the reciprocal regarding the logarithmic function of k:(a)
After theith time interval, we suppose that the receivers (including the attackers) have received hn−iPU,ζi,ξi. Attackers must forge hfaken−i−1 and ζi+1 within the i+1th time interval and make them meet the equations hhfaken−i−1=hn−iPU and hfaken−i−1⊕ζi+1=ξi. Suppose that the calculation ability of attackers can be represented as the polynomial Tadvk and they can query Oracle any number of times within each time interval. If the probability of cracking hash operation is e−k, the probability of breaking SRHC-TD can be expressed as(9)PrAdvk=1=Prhfaken−i−1=hn−i−1PU,hfaken−i−1⊕ζi+1=ξi=Tadvkek⋅ek,whereTadvk can be expressed as the general form of polynomial. So, we can deduce PrAdvk=1=ankn+an−1kn−1+⋯+a1k+a0/e2k. Evaluating the limit value of PrAdvk=1, we can deduce(10)limk⟶∞PrAdvk=1=limk⟶∞ankne2k=limk⟶∞an⋅nkn−12⋅e2k=⋯=limk⟶∞an⋅n!2n⋅e2k=0.(b)
At the ends of then−1-th time interval, only PU has not been published in the first hash chain. The receivers (including the attackers) have obtained mL number of ζi. Attackers must forge PU and PUfake within the nth time interval and make them meet the following conditions: (1) hPUfake=hPU; (2) when i1−i2≡0modmL, ζi1 and ζi2 contain the same sequence value xck+1 and the same shadow Ick+1, where k=i1+1modmL, i1,i2=1,2,…,n−1; (3) the solution hnPU′1 derived from the proof method of ordering is the same as the solution hnPU′2 derived from the proof method of CRT. The fake value PUfake must meet all the three conditions. We suppose that the calculation ability of attackers can be represented as the polynomial Tadvk and they can query Oracle any number of times within each time interval. If the probability of cracking hash operation is e−k, the probability of cracking CRT is k−e, and the probability of cracking partition algorithm is 1/lnk; then the probability of breaking SRHC-TD can be expressed as(11)PrAdvk=1=PrhPUfake=hPU,hnPU′1=hnPU′2xci1+1modmL+1=xci2+1modmL+1,Ici1+1modmL+1=Ici1+1modmL+1=Tadvkek⋅ke⋅lnk,where Tadvk can be expressed as the general form of polynomial Tadvk=ankn+an−1kn−1+⋯+a1k+a0. Evaluating the limit value of PrAdvk=1, we can deduce(12)limk⟶∞PrAdvk=1=limk⟶∞anknek⋅ke⋅lnk=limk⟶∞ankn−eek⋅lnk=limk⟶∞ann−ekn−e−1ek⋅lnk+1/k=⋯=limk⟶∞ann−e!ek⋅lnk+n−e/k−⋯+n−e−1!/kn−e=limk⟶∞ann−e!ek⋅lnk=0.Considering the above two cases, there exists a positive integerN, when k>N; for any ε, there must be PrAdvk=1<ε. So, the successful probability of attackers can be ignored and the SRHC-TD scheme has provable security.


## 8. Performance Evaluation

### 8.1. Evaluation of SRHC-TD

There are two possible ways to store a hash chain in base station. One is to generate a chain and allocate specialized space to store the whole chain. The other one is to store the seed of a chain and compute the link value when it needs to be used. Obviously, the former reduces the computation consumption but increases the memory consumption, while the latter is on the contrary.Considering the above two situations, the consumptions of SRHC-TD will be compared with those of RHCs [28–30] from two aspects, computation and communication, as follows. Table 2 shows the variable symbols and the corresponding variable names. Table 3 shows the consumptions of SRHC-TD and RHCs in detail.Table 2
The variable symbols and the corresponding variable names.
SymbolsDescriptionLThe output length of hash functionnThe length of a hash chainmThe length of Mignotte’s sequenceHThe computational overhead of a hash functionRThe computational overhead of generating a random numberBThe computational overhead of mapping a random number to one single bit using Hard Core PredicateIThe computational overhead of generating a secret shadowIi in SRHC-TDPrThe computational overhead of computingri in SRHC-TDMThe computational overhead of a left shift operationXThe computational overhead of an XOR operationCThe computational overhead of computing solutions to equationsTable 3
The consumptions in SRHC-TD and the RHCs.
Storage methodThe whole chainThe seedRHC [28]InitializationComputation2n+3⋅H+2R3n+2⋅H+2RCommunication2L2LPublication and verification and recombinationComputation2n+3⋅H+2R0.5n2+3n−4H+2n−1RCommunication4nL4nLSUHC [29]InitializationComputation2n+1⋅H+3R+B3n⋅H+3R+BCommunication2L2LPublication and verification and recombinationComputation5n⋅H+n⋅R+2nB0.5n2+9n+2⋅H+n⋅R+2nBCommunication4nL4nLSRHC [30]InitializationComputation2n+1⋅H+3R3nH+3RCommunication2L2LPublication and verification and recombinationComputation3n⋅H+n⋅R+2nB0.5n2+5n+2⋅H+n⋅R+2nBCommunication3nL3nLSRHC-TDInitializationComputation2n+m⋅H+2m⋅R+mI+X+M+Pr3n+2m−1⋅H+2m⋅R+mI+X+M+PrCommunication2L2LPublication and verification and recombinationComputationnH+2nM+2nX+2nPr+C0.5n2+n⋅H+2nM+2nX+2nPr+CCommunication3nL3nLFor ease of analysis, we assume that the length of the hash chain is greater than the output length of the hash function; that isn>m. In fact, the length of the hash chain is usually around 1000 because a short chain will lead to frequent regeneration or failure due to excessive packet loss rate. It is remarkable that if the base station only stores seeds, the calculation time increases exponentially. The length of hash chains n is a significant factor affecting the computation time.From Table3, we can see that the storage method of the hash chain has no effect on the communication overhead. In the initialization phase, the above schemes have the same communication overhead, while in the publication, verification, and recombination phases, our scheme has the same overhead as SRHC and is lower than RHC and SUHC, as shown in Figure 3. To evaluate the performance of our scheme in terms of computation overhead, we implement the operation used in the proposed scheme and other schemes on an Ubuntu 12.04 virtual machine with an Intel Core i5-4300 CPU @ 2.60 GHz. We use the 64-bit version of RC5 and generate a Mignotte’s sequence whose length is 32. In this case, each hash operation takes 0.0037 ms. Besides, the times consumed by shifting, XOR, and modular operation, denoted as TM, TX, and TI, are 0.0002 ms, 0.0002 ms, and 0.0003 ms, respectively. The generation of a 32-bit random number and TB takes 0.0004 ms, and it takes 0.0161 ms to recover the commitment. The time consumed in computing ri is so little that it can be ignored.Figure 3
Comparison of communication overhead in publication, verification, and recombination phases.Figure4 shows that, in the initialization phase, the time taken by our scheme increases by approximately 0.26 ms compared to the other three schemes, due to the generation of sharing secrets. However, in publication, verification, and recombination phases, our scheme takes less time, especially when the base station stores the entire hash chain, as shown in Figure 5. If the hash chain contains 1000 keys and the base station stores the entire hash chain, compared to [28–30], the computation overhead of SRHC-TD is reduced by 39.07%, 77.08%, and 63.28%, respectively. If the base station only stores the seed of the hash chain, our scheme’s computation overhead is reduced from 0.2% to 0.81%. It is worth noting that when the base station stores the entire chain, the computation time is 1000 times that of the case when it stores the seed. The main reason for this result is that when the base station releases the key which the sensor node used to authenticate the broadcast message, it needs to recover the key first. The base station needs to hash the seed value many times when the base station only stores the seed. However, if the base station stores the entire hash chain, which takes up more storage space, the key can be found easily. Thus, a more efficient way is that the base station stores some “checkpoints” for recovering the key. The greater the number of checkpoints stored by the base station is, the closer the time consumption is, according to Figure 5(a).Figure 4
Comparison of time consumption in initialization phase. (a) The base station stores the whole hash chain. (b) The base station only stores the seed of hash chain. The lower right corner of the figure is a partial enlargement.
(a)(b)Figure 5
Comparison of time consumption in publication, verification, and recombination phases. (a) The base station stores the whole hash chain. (b) The base station only stores the seed of hash chain. The lower right corner of the figure is a partial enlargement.
(a)(b)Thus, it is easy to compare the consumptions of SRHC-TD with the RHCs, as shown in Table4. It shows that the SRHC-TD has a better performance in publication, verification, and recombination phase. The computation and communication overhead of SRHC-TD are much less than other schemes, especially when the node only stores the seed of hash chain.Table 4
The comparisons of SRHC-TD and the RHCs.
Storage methodThe whole chainThe seedInitializationComputationSRHC < SUHC < RHC < SRHC-TDSRHC < SUHC < RHC < SRHC-TDCommunicationSRHC-TD = RHC = SRHC = SUHCSRHC-TD = RHC = SRHC = SUHCPublication and verification and recombinationComputationSRHC-TD < RHC < SRHC < SUHCSRHC-TD < RHC < SRHC < SUHCCommunicationSRHC-TD = SRHC < RHC = SUHCSRHC-TD = SRHC < RHC = SUHCAs we know, the largest contributor to energy consumption in WSNs is communication complexity, and computation overhead is the second, where the energy cost of sending and receiving a packet is several times that of computing or processing a packet [41]. The publication, verification, and recombination phases last much longer than the initialization phase over the lifetime of the network, and the initialization phase runs in the base station. Although our scheme has a higher consumption overhead in initialization phase, our energy consumption is lower than other schemes on the whole.


### 8.2. Evaluation of AdlCBF

In AdlCBF scheme, the fresh node can be authenticated by the base station using the ECDSA signature and the fingerprint of the node. ECDSA is a light-weight algorithm and it is based on the elliptic curve. The sensor node (or cluster head node) only needs to generate and verify a signature once when it joins the network. Thus, the overhead of authenticating a fresh sensor node is acceptable. Besides, thed-left counting Bloom filter is adopted to reduce the storage space. We will compare AdlCBF with Direct Access and CBF, respectively, regarding the storage overhead.


#### 8.2.1. Comparison with Direct Access

The basic simulation configurations of constructing a dlCBF are shown in Table5, where q stands for a large prime number.Table 5
The basic simulation configurations.
ParametersValueElements numberm=500000Subsequences number4Bucket number per subsequencem/24=20833Average load per bucket6Cells number per bucket8Counter length2 bitsStorage element lengthr = 14 bitsHash functionMD5Pseudorandom permutationPiHx=aHxmod2qProportional parameter in permutationaA random odd number below2qSuppose that the length of public keyKPA in ECDSA is x; then, 2x−1≥n, where n is the maximum on the elliptic curve. To guarantee the uniqueness of each node’s public key, let n≥m. Thus, we can obtain x≥log2n+1≥log2m+1=18.93, and the minimum length of public key is 19 bits. In the same way, the minimum length of ID is 19 bits, too. So, if the 500000 elements are stored with the form of plaintext, the required memory space is 500000×19+19=19000000 bits. When the 500000 elements are stored in AdlCBF, the required memory space is 4mr+2/3=10666667 bits. Thus, the former one is 1.78125 times more than the latter one. In conclusion, AdlCBF has better storage efficiency than the Direct Access.On the constructed AdlCBF, we repeat operations of adding an element, querying an element, and deleting an element, respectively, 3000 times. We record the consumed time for each operation and calculate the average value of the recorded time for every 300 times. Thus, one set of tests is accomplished and then we keep on conducting the remaining 9 tests similarly. The result is shown in Table6. The more intuitive representation of changes in consumption time is shown in Figure 6.Table 6
The statistics of consumed time.
AdditionQueryDeletionTest 10.230.080.32Test 20.210.070.35Test 30.310.130.40Test 40.250.120.42Test 50.200.100.35Test 60.270.100.39Test 70.300.090.30Test 80.240.080.38Test 90.210.070.35Test 100.230.090.36Average time0.250.100.36Figure 6
The statistics of consumed time.As shown in Table6, the query time is actually the authenticating time in AdlCBF, whose changes are quite small, relative to addition and deletion. In AdlCBF, the main operations are done by CPU, while in the Direct Access, the main operations are done by RAM. As we know, the read-write speed of CPU is two or three orders of magnitude faster than RAM. According to the space and the query time of AdlCBF, we can obtain that the required time in the Direct Access is in the range of 1.78 ms to 17.81 ms. In conclusion, AdlCBF has more satisfactory query efficiency.


#### 8.2.2. Comparison with CBF

The upper bound on false positive probability of AdlCBF is1/2r×2×4×6=24×2−r, while the false positive probability of CBF is 2−ln2c, where the standard CBF uses cm counters for tracking m elements and each counter is 4 bits [42]. When c=r+2/3, the two approaches have the same amount of space. However, when considering the false positive probability ratio of CBF to AdlCBF, we obtain 2−ln2r+2/3/24×2−r=52.65. Thus, with the same storage space, the false positive probability of the standard CBF is larger than that of AdlCBF.The storage space of AdlCBF is4mr+2/3, while the total bits of CBF is 4cm. When 2−ln2c=24×2−r, the two approaches share the same false positive probability. However, when considering the space ratio of CBF to AdlCBF, we obtain 4m⋅ln24×2−r/4mr+2/3=2.55. Thus, with the same false positive probability, the storage cost of the standard CBF is larger than that of AdlCBF.


### 8.3. Comparison with Other Variants

#### 8.3.1. Overhead

In this section, we discuss in detail the similarities and differences with MultilevelμTESLA [14] and Scalable μTESLA [22] in terms of the storage and computation requirement.To concentrate on the comparison of storage and computation overhead, we fix the following parameters. First, we establish a two-levelμTESLA, where the duration of each low-level time interval is 100 ms, and each low-level key chain consists of 600 keys. Thus, if the top-level hash chain has 300 keys, the two-level μTESLA can cover 300 minutes, where the hash function and MAC are both 64 bits. Second, we set 300 hash chains and each hash chain has 600 keys in Scalable μTESLA. Finally, in our protocol, we set the hash chain to be the same as the above hash chain, and the threshold is set to [16, 32] where each secret fragment of the new commitment will be distributed about 20 times. For clarity and ease of analysis, we assume that the packet rate is 100 per minute and these packets are sent continuously.(1) Storage Overhead. To generate a new hash chain and obtain the commitment used in the next period, all these protocols have to buffer data in sensor nodes. In the two-level μTESLA, the sensor node uses 624-byte storage space to buffer 39 CDMs, which can achieve authenticating the commitment of next low-level hash chain with a nearly 100% probability, because the sensor node has no way to confirm whether the MAC value in CMD is modified before the corresponding key is released. In the Scalable μTESLA, each sensor node only needs to store a hash value, the root of Merkel hash tree, which occupies 8 bytes. If there are more than one potential sender in the network, the sensor node needs to store two roots of Merkel tree occupying 16 bytes. Meanwhile, in our scheme, the commitment of next hash chain is divided into 32 secret parts and each part is distributed along with keys used to authenticate the broadcast packets. We have to buffer 32 ζi’s to recover the commitment of a new hash chain which only occupied 256 bytes.(2) Computation Overhead. We focus on the computation overhead of authenticating or generating the commitment used in the next period of time and authenticate the disclosed key. In Multilevel μTESLA, when the sensor node receives a CDM, the sensor node will buffer it with a certain probability. For each buffered CDM, the sensor node needs to authenticate the top-level key first by a hash operation and the MAC will be authenticated when the corresponding key is released after a certain delay. Thus, during 300 minutes, the computation overhead is 300⋅39⋅TH+TMAC+300⋅100⋅TH, where T⋅ represents the consumed time of the operation. In the Scalable μTESLA, the sensor node needs 1+log2300=10 hash operations to verify the commitments according to the root of Merkel hash chain. Thus, the computation overhead is 300⋅1+log2300⋅TH+300⋅100⋅TH. However, when there are n potential senders in the network, the sensor node needs to verify the validity of the sender with additional 1+log2n hash operations first before verifying the commitment. In our proposal, part of the commitment is sent with the distribution of the corresponding key. For each distribution, the sensor node only needs a XOR operation to authenticate the commitment fragment and recover the commitment at the end of the hash chain. Therefore, the computation overhead is 300⋅100⋅TH+TX+299⋅TC.As shown in Table7, in comparison with Multilevel μTESLA, our solution has less overhead due to the simple and immediate operation of authenticating the commitment of next hash chain. We have a similar computation overhead to that of Scalable μTESLA. Although Scalable μTESLA has smaller storage overhead, the sensor node needs more computation before verifying the commitment when there are multiple potential senders, even if some of these senders only send the message once. More importantly, we eliminate the overlong or redundant hash chains that exist in Multilevel μTESLA and Scalable μTESLA in order to ensure that the hash chains are not exhausted before the whole network dies.Table 7
Comparisons with other variants.
Storage overhead (bytes)Computation overhead (ms)MultilevelμTESLA624197.5800ScalableμTESLA∗8122.1000Ours256121.8139∗There is only one potential sender.


#### 8.3.2. Features

Separately, we further compare DH-μTESLA with μTESLA [13], Multilevel μTESLA [14], Scalable μTESLA [22], and long-duration TESLA [33] in terms of some important aspects, and the details are shown in Table 8.Table 8
Comparisons of various broadcast authentication protocols.
Our schemeμTESLAMultilevelμTESLALong-duration TESLAScalableμTESLAStructureSingle-chainSingle-chainMultilevelMultilevelMerkel chainWithout using overlong hash chain√×××√Reinitializable√××√∗×Backward security√√√×√Resistance with chosen plaintext attack√×√××Resistance with DoS attack (sensor node)√×√×√Resistance with DoS attack (base station)√××××Fresh node authentication (by base station)√××××Fault tolerance√√√×√∗The length of top-level hash chain is unlimited.Our protocol seems more practical, since the structure of hash chain is simple while maintaining reinitialization and backward security. The long-duration TESLA is not secure once a sensor node is compromised. The attacker can forge the authentication message based on the information stored by the node due to the forward hash chain. In order to prolong the lifecycle of the network, long-duration TESLA uses an overlong hash chain which may weaken the security of the hash chain. ScalableμTESLA eliminates this threat using multiple short hash chains; however, the hash chain is not reinitializable.InμTESLA and its variants, after receiving the broadcast message, the sensor node needs to buffer the message because it cannot be authenticated immediately. Attackers can cause huge damage to the network through DoS attacks. Therefore, resistance to DoS attacks is an important feature. In order to prevent nodes from DoS attacks, Multilevel μTESLA, Scalable μTESLA, and our proposal give a solution. However, none of these variants can handle the authentication of fresh node and DoS attack on the base station, which are important features of our protocol.Furthermore, all protocols have a good fault tolerance except long-duration TESLA. InμTESLA, if a key disclosure packet of a broadcast message is lost, it also can be authenticated by the subsequent key disclosed. Multilevel μTESLA and Scalable μTESLA can handle the situation where the commitment of next hash chain is lost by broadcasting the same packet that contains the commitment periodically.


## 8.1. Evaluation of SRHC-TD

There are two possible ways to store a hash chain in base station. One is to generate a chain and allocate specialized space to store the whole chain. The other one is to store the seed of a chain and compute the link value when it needs to be used. Obviously, the former reduces the computation consumption but increases the memory consumption, while the latter is on the contrary.Considering the above two situations, the consumptions of SRHC-TD will be compared with those of RHCs [28–30] from two aspects, computation and communication, as follows. Table 2 shows the variable symbols and the corresponding variable names. Table 3 shows the consumptions of SRHC-TD and RHCs in detail.Table 2
The variable symbols and the corresponding variable names.
SymbolsDescriptionLThe output length of hash functionnThe length of a hash chainmThe length of Mignotte’s sequenceHThe computational overhead of a hash functionRThe computational overhead of generating a random numberBThe computational overhead of mapping a random number to one single bit using Hard Core PredicateIThe computational overhead of generating a secret shadowIi in SRHC-TDPrThe computational overhead of computingri in SRHC-TDMThe computational overhead of a left shift operationXThe computational overhead of an XOR operationCThe computational overhead of computing solutions to equationsTable 3
The consumptions in SRHC-TD and the RHCs.
Storage methodThe whole chainThe seedRHC [28]InitializationComputation2n+3⋅H+2R3n+2⋅H+2RCommunication2L2LPublication and verification and recombinationComputation2n+3⋅H+2R0.5n2+3n−4H+2n−1RCommunication4nL4nLSUHC [29]InitializationComputation2n+1⋅H+3R+B3n⋅H+3R+BCommunication2L2LPublication and verification and recombinationComputation5n⋅H+n⋅R+2nB0.5n2+9n+2⋅H+n⋅R+2nBCommunication4nL4nLSRHC [30]InitializationComputation2n+1⋅H+3R3nH+3RCommunication2L2LPublication and verification and recombinationComputation3n⋅H+n⋅R+2nB0.5n2+5n+2⋅H+n⋅R+2nBCommunication3nL3nLSRHC-TDInitializationComputation2n+m⋅H+2m⋅R+mI+X+M+Pr3n+2m−1⋅H+2m⋅R+mI+X+M+PrCommunication2L2LPublication and verification and recombinationComputationnH+2nM+2nX+2nPr+C0.5n2+n⋅H+2nM+2nX+2nPr+CCommunication3nL3nLFor ease of analysis, we assume that the length of the hash chain is greater than the output length of the hash function; that isn>m. In fact, the length of the hash chain is usually around 1000 because a short chain will lead to frequent regeneration or failure due to excessive packet loss rate. It is remarkable that if the base station only stores seeds, the calculation time increases exponentially. The length of hash chains n is a significant factor affecting the computation time.From Table3, we can see that the storage method of the hash chain has no effect on the communication overhead. In the initialization phase, the above schemes have the same communication overhead, while in the publication, verification, and recombination phases, our scheme has the same overhead as SRHC and is lower than RHC and SUHC, as shown in Figure 3. To evaluate the performance of our scheme in terms of computation overhead, we implement the operation used in the proposed scheme and other schemes on an Ubuntu 12.04 virtual machine with an Intel Core i5-4300 CPU @ 2.60 GHz. We use the 64-bit version of RC5 and generate a Mignotte’s sequence whose length is 32. In this case, each hash operation takes 0.0037 ms. Besides, the times consumed by shifting, XOR, and modular operation, denoted as TM, TX, and TI, are 0.0002 ms, 0.0002 ms, and 0.0003 ms, respectively. The generation of a 32-bit random number and TB takes 0.0004 ms, and it takes 0.0161 ms to recover the commitment. The time consumed in computing ri is so little that it can be ignored.Figure 3
Comparison of communication overhead in publication, verification, and recombination phases.Figure4 shows that, in the initialization phase, the time taken by our scheme increases by approximately 0.26 ms compared to the other three schemes, due to the generation of sharing secrets. However, in publication, verification, and recombination phases, our scheme takes less time, especially when the base station stores the entire hash chain, as shown in Figure 5. If the hash chain contains 1000 keys and the base station stores the entire hash chain, compared to [28–30], the computation overhead of SRHC-TD is reduced by 39.07%, 77.08%, and 63.28%, respectively. If the base station only stores the seed of the hash chain, our scheme’s computation overhead is reduced from 0.2% to 0.81%. It is worth noting that when the base station stores the entire chain, the computation time is 1000 times that of the case when it stores the seed. The main reason for this result is that when the base station releases the key which the sensor node used to authenticate the broadcast message, it needs to recover the key first. The base station needs to hash the seed value many times when the base station only stores the seed. However, if the base station stores the entire hash chain, which takes up more storage space, the key can be found easily. Thus, a more efficient way is that the base station stores some “checkpoints” for recovering the key. The greater the number of checkpoints stored by the base station is, the closer the time consumption is, according to Figure 5(a).Figure 4
Comparison of time consumption in initialization phase. (a) The base station stores the whole hash chain. (b) The base station only stores the seed of hash chain. The lower right corner of the figure is a partial enlargement.
(a)(b)Figure 5
Comparison of time consumption in publication, verification, and recombination phases. (a) The base station stores the whole hash chain. (b) The base station only stores the seed of hash chain. The lower right corner of the figure is a partial enlargement.
(a)(b)Thus, it is easy to compare the consumptions of SRHC-TD with the RHCs, as shown in Table4. It shows that the SRHC-TD has a better performance in publication, verification, and recombination phase. The computation and communication overhead of SRHC-TD are much less than other schemes, especially when the node only stores the seed of hash chain.Table 4
The comparisons of SRHC-TD and the RHCs.
Storage methodThe whole chainThe seedInitializationComputationSRHC < SUHC < RHC < SRHC-TDSRHC < SUHC < RHC < SRHC-TDCommunicationSRHC-TD = RHC = SRHC = SUHCSRHC-TD = RHC = SRHC = SUHCPublication and verification and recombinationComputationSRHC-TD < RHC < SRHC < SUHCSRHC-TD < RHC < SRHC < SUHCCommunicationSRHC-TD = SRHC < RHC = SUHCSRHC-TD = SRHC < RHC = SUHCAs we know, the largest contributor to energy consumption in WSNs is communication complexity, and computation overhead is the second, where the energy cost of sending and receiving a packet is several times that of computing or processing a packet [41]. The publication, verification, and recombination phases last much longer than the initialization phase over the lifetime of the network, and the initialization phase runs in the base station. Although our scheme has a higher consumption overhead in initialization phase, our energy consumption is lower than other schemes on the whole.


## 8.2. Evaluation of AdlCBF

In AdlCBF scheme, the fresh node can be authenticated by the base station using the ECDSA signature and the fingerprint of the node. ECDSA is a light-weight algorithm and it is based on the elliptic curve. The sensor node (or cluster head node) only needs to generate and verify a signature once when it joins the network. Thus, the overhead of authenticating a fresh sensor node is acceptable. Besides, thed-left counting Bloom filter is adopted to reduce the storage space. We will compare AdlCBF with Direct Access and CBF, respectively, regarding the storage overhead.


### 8.2.1. Comparison with Direct Access

The basic simulation configurations of constructing a dlCBF are shown in Table5, where q stands for a large prime number.Table 5
The basic simulation configurations.
ParametersValueElements numberm=500000Subsequences number4Bucket number per subsequencem/24=20833Average load per bucket6Cells number per bucket8Counter length2 bitsStorage element lengthr = 14 bitsHash functionMD5Pseudorandom permutationPiHx=aHxmod2qProportional parameter in permutationaA random odd number below2qSuppose that the length of public keyKPA in ECDSA is x; then, 2x−1≥n, where n is the maximum on the elliptic curve. To guarantee the uniqueness of each node’s public key, let n≥m. Thus, we can obtain x≥log2n+1≥log2m+1=18.93, and the minimum length of public key is 19 bits. In the same way, the minimum length of ID is 19 bits, too. So, if the 500000 elements are stored with the form of plaintext, the required memory space is 500000×19+19=19000000 bits. When the 500000 elements are stored in AdlCBF, the required memory space is 4mr+2/3=10666667 bits. Thus, the former one is 1.78125 times more than the latter one. In conclusion, AdlCBF has better storage efficiency than the Direct Access.On the constructed AdlCBF, we repeat operations of adding an element, querying an element, and deleting an element, respectively, 3000 times. We record the consumed time for each operation and calculate the average value of the recorded time for every 300 times. Thus, one set of tests is accomplished and then we keep on conducting the remaining 9 tests similarly. The result is shown in Table6. The more intuitive representation of changes in consumption time is shown in Figure 6.Table 6
The statistics of consumed time.
AdditionQueryDeletionTest 10.230.080.32Test 20.210.070.35Test 30.310.130.40Test 40.250.120.42Test 50.200.100.35Test 60.270.100.39Test 70.300.090.30Test 80.240.080.38Test 90.210.070.35Test 100.230.090.36Average time0.250.100.36Figure 6
The statistics of consumed time.As shown in Table6, the query time is actually the authenticating time in AdlCBF, whose changes are quite small, relative to addition and deletion. In AdlCBF, the main operations are done by CPU, while in the Direct Access, the main operations are done by RAM. As we know, the read-write speed of CPU is two or three orders of magnitude faster than RAM. According to the space and the query time of AdlCBF, we can obtain that the required time in the Direct Access is in the range of 1.78 ms to 17.81 ms. In conclusion, AdlCBF has more satisfactory query efficiency.


### 8.2.2. Comparison with CBF

The upper bound on false positive probability of AdlCBF is1/2r×2×4×6=24×2−r, while the false positive probability of CBF is 2−ln2c, where the standard CBF uses cm counters for tracking m elements and each counter is 4 bits [42]. When c=r+2/3, the two approaches have the same amount of space. However, when considering the false positive probability ratio of CBF to AdlCBF, we obtain 2−ln2r+2/3/24×2−r=52.65. Thus, with the same storage space, the false positive probability of the standard CBF is larger than that of AdlCBF.The storage space of AdlCBF is4mr+2/3, while the total bits of CBF is 4cm. When 2−ln2c=24×2−r, the two approaches share the same false positive probability. However, when considering the space ratio of CBF to AdlCBF, we obtain 4m⋅ln24×2−r/4mr+2/3=2.55. Thus, with the same false positive probability, the storage cost of the standard CBF is larger than that of AdlCBF.


## 8.2.1. Comparison with Direct Access

The basic simulation configurations of constructing a dlCBF are shown in Table5, where q stands for a large prime number.Table 5
The basic simulation configurations.
ParametersValueElements numberm=500000Subsequences number4Bucket number per subsequencem/24=20833Average load per bucket6Cells number per bucket8Counter length2 bitsStorage element lengthr = 14 bitsHash functionMD5Pseudorandom permutationPiHx=aHxmod2qProportional parameter in permutationaA random odd number below2qSuppose that the length of public keyKPA in ECDSA is x; then, 2x−1≥n, where n is the maximum on the elliptic curve. To guarantee the uniqueness of each node’s public key, let n≥m. Thus, we can obtain x≥log2n+1≥log2m+1=18.93, and the minimum length of public key is 19 bits. In the same way, the minimum length of ID is 19 bits, too. So, if the 500000 elements are stored with the form of plaintext, the required memory space is 500000×19+19=19000000 bits. When the 500000 elements are stored in AdlCBF, the required memory space is 4mr+2/3=10666667 bits. Thus, the former one is 1.78125 times more than the latter one. In conclusion, AdlCBF has better storage efficiency than the Direct Access.On the constructed AdlCBF, we repeat operations of adding an element, querying an element, and deleting an element, respectively, 3000 times. We record the consumed time for each operation and calculate the average value of the recorded time for every 300 times. Thus, one set of tests is accomplished and then we keep on conducting the remaining 9 tests similarly. The result is shown in Table6. The more intuitive representation of changes in consumption time is shown in Figure 6.Table 6
The statistics of consumed time.
AdditionQueryDeletionTest 10.230.080.32Test 20.210.070.35Test 30.310.130.40Test 40.250.120.42Test 50.200.100.35Test 60.270.100.39Test 70.300.090.30Test 80.240.080.38Test 90.210.070.35Test 100.230.090.36Average time0.250.100.36Figure 6
The statistics of consumed time.As shown in Table6, the query time is actually the authenticating time in AdlCBF, whose changes are quite small, relative to addition and deletion. In AdlCBF, the main operations are done by CPU, while in the Direct Access, the main operations are done by RAM. As we know, the read-write speed of CPU is two or three orders of magnitude faster than RAM. According to the space and the query time of AdlCBF, we can obtain that the required time in the Direct Access is in the range of 1.78 ms to 17.81 ms. In conclusion, AdlCBF has more satisfactory query efficiency.


## 8.2.2. Comparison with CBF

The upper bound on false positive probability of AdlCBF is1/2r×2×4×6=24×2−r, while the false positive probability of CBF is 2−ln2c, where the standard CBF uses cm counters for tracking m elements and each counter is 4 bits [42]. When c=r+2/3, the two approaches have the same amount of space. However, when considering the false positive probability ratio of CBF to AdlCBF, we obtain 2−ln2r+2/3/24×2−r=52.65. Thus, with the same storage space, the false positive probability of the standard CBF is larger than that of AdlCBF.The storage space of AdlCBF is4mr+2/3, while the total bits of CBF is 4cm. When 2−ln2c=24×2−r, the two approaches share the same false positive probability. However, when considering the space ratio of CBF to AdlCBF, we obtain 4m⋅ln24×2−r/4mr+2/3=2.55. Thus, with the same false positive probability, the storage cost of the standard CBF is larger than that of AdlCBF.


## 8.3. Comparison with Other Variants

### 8.3.1. Overhead

In this section, we discuss in detail the similarities and differences with MultilevelμTESLA [14] and Scalable μTESLA [22] in terms of the storage and computation requirement.To concentrate on the comparison of storage and computation overhead, we fix the following parameters. First, we establish a two-levelμTESLA, where the duration of each low-level time interval is 100 ms, and each low-level key chain consists of 600 keys. Thus, if the top-level hash chain has 300 keys, the two-level μTESLA can cover 300 minutes, where the hash function and MAC are both 64 bits. Second, we set 300 hash chains and each hash chain has 600 keys in Scalable μTESLA. Finally, in our protocol, we set the hash chain to be the same as the above hash chain, and the threshold is set to [16, 32] where each secret fragment of the new commitment will be distributed about 20 times. For clarity and ease of analysis, we assume that the packet rate is 100 per minute and these packets are sent continuously.(1) Storage Overhead. To generate a new hash chain and obtain the commitment used in the next period, all these protocols have to buffer data in sensor nodes. In the two-level μTESLA, the sensor node uses 624-byte storage space to buffer 39 CDMs, which can achieve authenticating the commitment of next low-level hash chain with a nearly 100% probability, because the sensor node has no way to confirm whether the MAC value in CMD is modified before the corresponding key is released. In the Scalable μTESLA, each sensor node only needs to store a hash value, the root of Merkel hash tree, which occupies 8 bytes. If there are more than one potential sender in the network, the sensor node needs to store two roots of Merkel tree occupying 16 bytes. Meanwhile, in our scheme, the commitment of next hash chain is divided into 32 secret parts and each part is distributed along with keys used to authenticate the broadcast packets. We have to buffer 32 ζi’s to recover the commitment of a new hash chain which only occupied 256 bytes.(2) Computation Overhead. We focus on the computation overhead of authenticating or generating the commitment used in the next period of time and authenticate the disclosed key. In Multilevel μTESLA, when the sensor node receives a CDM, the sensor node will buffer it with a certain probability. For each buffered CDM, the sensor node needs to authenticate the top-level key first by a hash operation and the MAC will be authenticated when the corresponding key is released after a certain delay. Thus, during 300 minutes, the computation overhead is 300⋅39⋅TH+TMAC+300⋅100⋅TH, where T⋅ represents the consumed time of the operation. In the Scalable μTESLA, the sensor node needs 1+log2300=10 hash operations to verify the commitments according to the root of Merkel hash chain. Thus, the computation overhead is 300⋅1+log2300⋅TH+300⋅100⋅TH. However, when there are n potential senders in the network, the sensor node needs to verify the validity of the sender with additional 1+log2n hash operations first before verifying the commitment. In our proposal, part of the commitment is sent with the distribution of the corresponding key. For each distribution, the sensor node only needs a XOR operation to authenticate the commitment fragment and recover the commitment at the end of the hash chain. Therefore, the computation overhead is 300⋅100⋅TH+TX+299⋅TC.As shown in Table7, in comparison with Multilevel μTESLA, our solution has less overhead due to the simple and immediate operation of authenticating the commitment of next hash chain. We have a similar computation overhead to that of Scalable μTESLA. Although Scalable μTESLA has smaller storage overhead, the sensor node needs more computation before verifying the commitment when there are multiple potential senders, even if some of these senders only send the message once. More importantly, we eliminate the overlong or redundant hash chains that exist in Multilevel μTESLA and Scalable μTESLA in order to ensure that the hash chains are not exhausted before the whole network dies.Table 7
Comparisons with other variants.
Storage overhead (bytes)Computation overhead (ms)MultilevelμTESLA624197.5800ScalableμTESLA∗8122.1000Ours256121.8139∗There is only one potential sender.


### 8.3.2. Features

Separately, we further compare DH-μTESLA with μTESLA [13], Multilevel μTESLA [14], Scalable μTESLA [22], and long-duration TESLA [33] in terms of some important aspects, and the details are shown in Table 8.Table 8
Comparisons of various broadcast authentication protocols.
Our schemeμTESLAMultilevelμTESLALong-duration TESLAScalableμTESLAStructureSingle-chainSingle-chainMultilevelMultilevelMerkel chainWithout using overlong hash chain√×××√Reinitializable√××√∗×Backward security√√√×√Resistance with chosen plaintext attack√×√××Resistance with DoS attack (sensor node)√×√×√Resistance with DoS attack (base station)√××××Fresh node authentication (by base station)√××××Fault tolerance√√√×√∗The length of top-level hash chain is unlimited.Our protocol seems more practical, since the structure of hash chain is simple while maintaining reinitialization and backward security. The long-duration TESLA is not secure once a sensor node is compromised. The attacker can forge the authentication message based on the information stored by the node due to the forward hash chain. In order to prolong the lifecycle of the network, long-duration TESLA uses an overlong hash chain which may weaken the security of the hash chain. ScalableμTESLA eliminates this threat using multiple short hash chains; however, the hash chain is not reinitializable.InμTESLA and its variants, after receiving the broadcast message, the sensor node needs to buffer the message because it cannot be authenticated immediately. Attackers can cause huge damage to the network through DoS attacks. Therefore, resistance to DoS attacks is an important feature. In order to prevent nodes from DoS attacks, Multilevel μTESLA, Scalable μTESLA, and our proposal give a solution. However, none of these variants can handle the authentication of fresh node and DoS attack on the base station, which are important features of our protocol.Furthermore, all protocols have a good fault tolerance except long-duration TESLA. InμTESLA, if a key disclosure packet of a broadcast message is lost, it also can be authenticated by the subsequent key disclosed. Multilevel μTESLA and Scalable μTESLA can handle the situation where the commitment of next hash chain is lost by broadcasting the same packet that contains the commitment periodically.


## 8.3.1. Overhead

In this section, we discuss in detail the similarities and differences with MultilevelμTESLA [14] and Scalable μTESLA [22] in terms of the storage and computation requirement.To concentrate on the comparison of storage and computation overhead, we fix the following parameters. First, we establish a two-levelμTESLA, where the duration of each low-level time interval is 100 ms, and each low-level key chain consists of 600 keys. Thus, if the top-level hash chain has 300 keys, the two-level μTESLA can cover 300 minutes, where the hash function and MAC are both 64 bits. Second, we set 300 hash chains and each hash chain has 600 keys in Scalable μTESLA. Finally, in our protocol, we set the hash chain to be the same as the above hash chain, and the threshold is set to [16, 32] where each secret fragment of the new commitment will be distributed about 20 times. For clarity and ease of analysis, we assume that the packet rate is 100 per minute and these packets are sent continuously.(1) Storage Overhead. To generate a new hash chain and obtain the commitment used in the next period, all these protocols have to buffer data in sensor nodes. In the two-level μTESLA, the sensor node uses 624-byte storage space to buffer 39 CDMs, which can achieve authenticating the commitment of next low-level hash chain with a nearly 100% probability, because the sensor node has no way to confirm whether the MAC value in CMD is modified before the corresponding key is released. In the Scalable μTESLA, each sensor node only needs to store a hash value, the root of Merkel hash tree, which occupies 8 bytes. If there are more than one potential sender in the network, the sensor node needs to store two roots of Merkel tree occupying 16 bytes. Meanwhile, in our scheme, the commitment of next hash chain is divided into 32 secret parts and each part is distributed along with keys used to authenticate the broadcast packets. We have to buffer 32 ζi’s to recover the commitment of a new hash chain which only occupied 256 bytes.(2) Computation Overhead. We focus on the computation overhead of authenticating or generating the commitment used in the next period of time and authenticate the disclosed key. In Multilevel μTESLA, when the sensor node receives a CDM, the sensor node will buffer it with a certain probability. For each buffered CDM, the sensor node needs to authenticate the top-level key first by a hash operation and the MAC will be authenticated when the corresponding key is released after a certain delay. Thus, during 300 minutes, the computation overhead is 300⋅39⋅TH+TMAC+300⋅100⋅TH, where T⋅ represents the consumed time of the operation. In the Scalable μTESLA, the sensor node needs 1+log2300=10 hash operations to verify the commitments according to the root of Merkel hash chain. Thus, the computation overhead is 300⋅1+log2300⋅TH+300⋅100⋅TH. However, when there are n potential senders in the network, the sensor node needs to verify the validity of the sender with additional 1+log2n hash operations first before verifying the commitment. In our proposal, part of the commitment is sent with the distribution of the corresponding key. For each distribution, the sensor node only needs a XOR operation to authenticate the commitment fragment and recover the commitment at the end of the hash chain. Therefore, the computation overhead is 300⋅100⋅TH+TX+299⋅TC.As shown in Table7, in comparison with Multilevel μTESLA, our solution has less overhead due to the simple and immediate operation of authenticating the commitment of next hash chain. We have a similar computation overhead to that of Scalable μTESLA. Although Scalable μTESLA has smaller storage overhead, the sensor node needs more computation before verifying the commitment when there are multiple potential senders, even if some of these senders only send the message once. More importantly, we eliminate the overlong or redundant hash chains that exist in Multilevel μTESLA and Scalable μTESLA in order to ensure that the hash chains are not exhausted before the whole network dies.Table 7
Comparisons with other variants.
Storage overhead (bytes)Computation overhead (ms)MultilevelμTESLA624197.5800ScalableμTESLA∗8122.1000Ours256121.8139∗There is only one potential sender.


## 8.3.2. Features

Separately, we further compare DH-μTESLA with μTESLA [13], Multilevel μTESLA [14], Scalable μTESLA [22], and long-duration TESLA [33] in terms of some important aspects, and the details are shown in Table 8.Table 8
Comparisons of various broadcast authentication protocols.
Our schemeμTESLAMultilevelμTESLALong-duration TESLAScalableμTESLAStructureSingle-chainSingle-chainMultilevelMultilevelMerkel chainWithout using overlong hash chain√×××√Reinitializable√××√∗×Backward security√√√×√Resistance with chosen plaintext attack√×√××Resistance with DoS attack (sensor node)√×√×√Resistance with DoS attack (base station)√××××Fresh node authentication (by base station)√××××Fault tolerance√√√×√∗The length of top-level hash chain is unlimited.Our protocol seems more practical, since the structure of hash chain is simple while maintaining reinitialization and backward security. The long-duration TESLA is not secure once a sensor node is compromised. The attacker can forge the authentication message based on the information stored by the node due to the forward hash chain. In order to prolong the lifecycle of the network, long-duration TESLA uses an overlong hash chain which may weaken the security of the hash chain. ScalableμTESLA eliminates this threat using multiple short hash chains; however, the hash chain is not reinitializable.InμTESLA and its variants, after receiving the broadcast message, the sensor node needs to buffer the message because it cannot be authenticated immediately. Attackers can cause huge damage to the network through DoS attacks. Therefore, resistance to DoS attacks is an important feature. In order to prevent nodes from DoS attacks, Multilevel μTESLA, Scalable μTESLA, and our proposal give a solution. However, none of these variants can handle the authentication of fresh node and DoS attack on the base station, which are important features of our protocol.Furthermore, all protocols have a good fault tolerance except long-duration TESLA. InμTESLA, if a key disclosure packet of a broadcast message is lost, it also can be authenticated by the subsequent key disclosed. Multilevel μTESLA and Scalable μTESLA can handle the situation where the commitment of next hash chain is lost by broadcasting the same packet that contains the commitment periodically.


## 9. Conclusion

Our paper focuses on the key management and distribution of broadcast authentication in the combination of WSNs and edge computing with consideration of efficient storage and security issue caused by overlong hash chains, which are also important issues in IoT application scenarios. We propose an enhanced broadcast authentication protocol DH-μTESLA based on μTESLA, including SRHC-TD and AdlCBF schemes. Motivated by the fact that the disadvantages of μTESLA are the limited length of the hash chain and the security issue caused by an overlong hash chain, we design a (t, n)-threshold-based self-reinitializable hash chain scheme (SRHC-TD), which can withstand chosen plaintext attacks and is proven to be secure in Random Oracle model. Besides, in order to keep the scalability of the network, we put forward the d-left-counting-Bloom-filter-based authentication scheme (AdlCBF) and the base station is able to defend against DoS attack. The test simulation shows that, compared to other renewable hash chain schemes, our protocol has less energy consumption and the base station requires less storage space than Direct Access and CBF. Furthermore, compared to Multilevel μTESLA and Scalable μTESLA, our protocol takes less computation overhead in sensor node. In the end, we discussed the advantages of our protocol versus μTESLA, Multilevel μTESLA, long-duration TESLA, and Scalable μTESLA.There are still some issues worthy of further study in the future work. First, in our paper, we suppose that there is only one base station in the entire network. However, in some very large-scale sensor networks, there may be multiple base stations and the fresh node needs to decide which base station to join. Second, broadcast authentication in IoT with high packet loss rate is still an open issue which would be addressed effectively.



---

*Source: 8897282-2020-09-01.xml*