# An ImprovedμTESLA Protocol Based on Queuing Theory and Benaloh-Leichter SSS in WSNs

Authors: Haiping Huang; Tianhe Gong; Tao Chen; Mingliang Xiong; Xinxing Pan; Ting Dai
Journal: Journal of Sensors
 (2016)

---

## Abstract

Broadcast authentication is a fundamental security technology in wireless sensor networks (ab. WSNs). As an authentication protocol, the most widely used in WSN,μTESLA protocol, its publication of key is based on a fixed time interval, which may lead to unsatisfactory performance under the unstable network traffic environment. Furthermore, the frequent network communication will cause the delay authentication for some broadcast packets while the infrequent one will increase the overhead of key computation. To solve these problems, this paper improves the traditional μTESLA by determining the publication of broadcast key based on the network data flow rather than the fixed time interval. Meanwhile, aiming at the finite length of hash chain and the problem of exhaustion, a self-renewal hash chain based on Benaloh-Leichter secret sharing scheme (SRHC-BL SSS) is designed, which can prolong the lifetime of network. Moreover, by introducing the queue theory model, we demonstrate that our scheme has much lower key consumption than μTESLA through simulation evaluations. Finally, we analyze and prove the security and efficiency of the proposed self-renewal hash chain, comparing with other typical schemes.


---

## Body

## 1. Introduction

We can imagine there will be thousands of sensors deployed in the future space, but how can we ensure the security of these sensors? Aside from confidential communications, authentication is one of the essential services in security protocols of wireless sensor networks (ab. WSNs) system [1]. If the authentication system stays defective or noneffective, attackers may launch threats to the whole network such as the wormhole attack, the man-in-the-middle attack, and the multiple identities attack. Data leakage may occur even in a military area, which can cause serious consequences. Therefore, the study of authentication system especially the broadcast authentication protocol for large-scale WSNs still remains challenging. However, restrained by the finite resources of WSNs, many previous protocols cannot be directly applied to the broadcast authentication of WSNs. For example, most protocols rely on asymmetric mechanism such as the public key cryptography, but this mechanism has heavy communication, computation, and storage overhead, which are impractical for WSNs.Therefore, designing a protocol that can guarantee the data integrity, confidentiality, and authentication in the broadcast has been a popular research topic in WSNs. One straightforward solution is to let the base station and all other nodes share a common broadcast authentication key, but the key will be disclosed if one of nodes is corrupt. Another solution is to use one-time key for each packet so that the leak of current key will not have a bad influence on the following packets, but the cost of frequently updating keys is unacceptable for WSNs. Perrig et al. proposed a classic broadcast authentication protocolμTESLA [2], which has a great improvement over the original protocol TESLA [3, 4]. The contribution of μTESLA protocol is to implement a broadcast authentication process based on the symmetric key mechanism instead of the asymmetric one, and it overcomes the problems in traditional protocols by delaying the publication of one-way hash function key. This protocol decreases the computational complexity for broadcast authentication and improves the authentication efficiency as well. In the following paragraph, we will give a brief overview of μTESLA.The main idea ofμTESLA is to broadcast a packet authenticated by the key K
m
a
c at first and then publish K
m
a
c so that there is no way to forge the broadcast packets before the publication of the key. In addition, the protocol achieves the secret sharing with the key generation algorithm shared by the entire network. The one-way hash function and the key chain mechanism can ensure the safety of keys and the tolerance of packet loss. Figure 1 illustrates the broadcast authentication process of μTESLA.Figure 1
The broadcast authentication process ofμTESLA.μTESLA protocol consists of three phases: (
1
) securely initializing the configuration of base station, (
2
) bootstrapping the new receivers, and (
3
) authenticating the broadcast packets. The base station generates a key pool (
K
N
-
1
,
K
N
-
2
,
…
,
K
1
,
K
0
) by one-way hash function in the first phase and determines the synchronization time interval T
i
n
t and the key-delayed-disclosure time interval d
×
T
i
n
t. The synchronization time interval represents the lifetime of a broadcast key, which means the broadcast packets sent from the base station use the same key K
i in a synchronous period [
i
×
T
i
n
t
,
(
i
+
1
)
×
T
i
n
t
]. The value of integer d should make d
×
T
i
n
t longer than the time of packet-switching between the base station and the farthest node so that all the nodes can be ensured to have received the broadcast packet before the corresponding key is disclosed.When the new node joins the network,μTESLA distributes the key synchronized parameters and initialized related keys to the new node based on the SNEP protocol [3]. For example, Figure 1 shows the process of node A requesting to join the broadcast network during the time interval i
×
T
i
n
t
,
i
+
1
×
T
i
n
t. Consider(1)A⟶S:NA∥DreqS⟶A:TS∥Ki∥Ti∥Tint∥d,MACKAS,NA∥TS∥Ki∥Ti∥Tint∥d,where N
A is a nonce which is generated by A to achieve a strong freshness authentication; D
r
e
q is a request data packet; K
A
S is an authentication key between A and S; T
S is the current time; K
i is an initial key; T
i is the starting time of the current synchronization interval; T
i
n
t is the synchronization interval; and d is the disclosure delay. The key will be published after d
×
T
i
n
t.After receiving a broadcast packet from the base station, the receiver will judge the validity of authentication key based on the synchronization time. The node will further verify the key’s validity by running the hash calculation on it. Finally, the node will use the key to authenticate the packets that have been stored in the buffer during the time interval.InμTESLA protocol, the publication of key is dependent on a specific time interval, which is fixed after initialization. However, we notice that the current network traffic is not stable in each time interval, and we divide this unstable traffic into two cases:(i)
The base station broadcasts the packets frequently to the sensor nodes. In this case, the broadcast packets in one time interval will dramatically increase. If the key is still disclosed according to the original time interval, the excessive number of packets is unable to get a timely authentication and the storage space of the sensor nodes will be exhausted inevitably.
(ii)
The base station just broadcasts a few packets in a long time. In this case, it is possible that there are few packets during the fixed time interval. Consequently, the release of keys will lead to the increase of communication and computation overhead, which degrades the efficiency of key chain.To decrease unnecessary consumption as well as to ensure security in the process of broadcast authentication, in this paper, we replace the fixed time interval with network traffic to determine the publication of broadcast key. In other words, the base station will not publish the authentication key unless it has broadcasted a certain number of packets. And our experiment has shown that some drawbacks ofμTESLA can be solved based on our mechanism.Due to the one-way and lightweight characteristics, hash chains have been widely applied to various scenarios such as one-time password system [5], video stream security [6, 7], micropayment protocol [8], key distribution scheme [9], and broadcast authentication [10]. However, there is a trade-off between the length and the efficiency of hash chain. The exhaustion of the current hash chain will inevitably result in producing another new hash chain initialized with the public key cryptography. And this reinitialization will bring about the extra overhead of the network.Aimed at overcoming the inadequacies of the above schemes, another concern of this paper is to design a novel self-renewal one-way hash chain scheme based on Benaloh-Leichter SSS (SRHC-BL). This scheme can effectively prolong the lifetime of network and increase the tolerance of key loss. Comparing with the typical self-renewal hash chain schemes, our approach has the benefit of higher security and less consumption of communication, computation, and storage.Therefore, the main contribution of this paper can be summarized as follows:(1)
A novel key distribution method based on data flow instead of fixed time interval is proposed in order to keep network stable in any situations. In addition, some special cases are discussed as the supplement.
(2)
A self-renewal one-way hash chain scheme based on Benaloh-Leichter SSS is adapted for both keeping extending life time of network and ensuring the tolerance of key loss.
(3)
Simulation experiments and theoretical analysis based on queue model are conducted to compare the storage cost and calculation complex among our schemes and traditionalμTESLA protocol. Consequently, the result proves that our design achieves a better performance.


## 2. Preliminary Knowledge

### 2.1. Basic Concepts of Queue Theory

Queue theory, also known as random service system theory, is a theoretical basis for the queuing problem. It is one of the interdisciplinary theories of probability, statistics, and operational research. Queuing phenomenon is composed of two aspects: demand service and provide service. Here are four common queuing models as follows: M/D/1/∞ queuing model, M/M/1/∞ queuing model, M/G/1/∞ queuing model, and G/G/1/∞ queuing model.Queuing system has the following six features, which can be applied to the broadcast authentication in WSNs:(i)
Input process, which characterizes and describes the law of data packets coming to the random service system.
(ii)
Service time, namely, the time for the base station to authenticate the data packets.
(iii)
Waiter, namely, the base station.
(iv)
Size of line determined by the number of customers waiting to be served, which characterizes the number of valid data packets to be processed by the base station.
(v)
Customer source, which corresponds to the data packets.
(vi)
Queue rule, determined by the detail of queuing model.


### 2.2. Basic Concepts of Self-Renewal Hash Chain

In this section, we introduce some basic concepts of SSS and the definition of the Benaloh-Leichter SSS.


#### 2.2.1. Concept of SSS

First, we formally define the necessary monotone access structure.Definition 1.
Given a setP, a monotone access structure on P is a family of subsets Z
⊆
2
P such that(2)A∈Z,A⊆A′⊆P.↓A′∈Z.
Letn be an integer, n
≥
2, let the set of participants be P
=
p
1
,
p
2
,
⁡
…
,
p
n, and let an access structure Z defined on P be comprised of a collection of subsets of P
.
Z is a monotone access structure whenever A
∈
Z and A
⊆
A
′
⊆
P.Similarly,Z-SSS is a method of generating (S, (I
1
,
…
,
I
n)) such that,(1)
for anyA
∈
Z, finding the element S, given the set {
I
i
∣
i
∈
A
}, is easy,
(2)
for anyA
∈
Z
¯, finding the element S, given the set {
I
i
∣
i
∈
A
}, is difficult.The setZ is the authorized access structure or simply the access structure, S is the secret, and I
1
,
…
,
I
n are the shares (or the shadows) of S. The elements of the set Z are the authorized access sets of the scheme.


#### 2.2.2. Benaloh-Leichter SSS

Definition 2.
LetP be a set. The set V of variables indexed by P is the set V
=
v
p
:
p
∈
P.Definition 3.
Given a monotone functionF on variables indexed by a set P, the access structure defined by F is the set of subsets of A of P for which F is true precisely when the variables indexed by A are set to be true.It is clear that, for every monotone functionF, the access structure defined by F is a monotone access structure.Definition 4.
For a given setP and a monotone access structure Z denoted by Z
m
i
n on P, define F
(
Z
) to be the set of monotone function on P variables such that, for every formula F
∈
F
(
Z
), the output of F is true if and only if the true variables in F correspond exactly to a set A
∈
Z.Note thatF
,
F
′
∈
F
(
Z
) implies F and F
′ denote the same function. They may, however, use entirely different expressions to express this function.The formula can be expressed using only∧ operator and ∨ operator, and it is sufficient to indicate how to “split” the secret with these operators.Definition 5.
One can recursively define the share of a secretS with respect to a formula F as follows:(3)F=S,i,ifF=vi,1≤i≤n⋃i=1nSharesS,Fi;ifF=F1∨F2∨⋯∨Fn⋃i=1nSharessi,Fi;ifF=F1∧F2∧⋯∧Fn,where based on Definitions 1, 2, and 3, selecting the specific integer n and Z
m
i
n, for the case F
=
F
1
∧
F
2
∧
⋯
∧
F
n, one can use a (
k
,
n
)-threshold secret sharing scheme for deriving some shares s
1
,
s
2
,
…
,
s
k corresponding to the secret S, and then every distinct share is assigned to each I
i. Thus one has I
i
=
{
s
i
∣
(
s
i
,
i
)
∈
S
h
a
r
e
s
(
S
,
F
)
}, for all 1
≤
i
≤
n, where F is an arbitrary formula in the set F
A.


#### 2.2.3. Definition of Hash Chain

Definition 6.
The secure hash function is a publicly known functionf
n
:
0,1
∗
→
0,1
k, it takes s as an input, and the output is a bit string f
n
(
s
) of length n. In f
n
(
s
), s is generated randomly from a pseudo-random string generator. One-way hash chain can be visually expressed as follows:(4)s→h·hs→h·h2s⋯→h·hns.


## 2.1. Basic Concepts of Queue Theory

Queue theory, also known as random service system theory, is a theoretical basis for the queuing problem. It is one of the interdisciplinary theories of probability, statistics, and operational research. Queuing phenomenon is composed of two aspects: demand service and provide service. Here are four common queuing models as follows: M/D/1/∞ queuing model, M/M/1/∞ queuing model, M/G/1/∞ queuing model, and G/G/1/∞ queuing model.Queuing system has the following six features, which can be applied to the broadcast authentication in WSNs:(i)
Input process, which characterizes and describes the law of data packets coming to the random service system.
(ii)
Service time, namely, the time for the base station to authenticate the data packets.
(iii)
Waiter, namely, the base station.
(iv)
Size of line determined by the number of customers waiting to be served, which characterizes the number of valid data packets to be processed by the base station.
(v)
Customer source, which corresponds to the data packets.
(vi)
Queue rule, determined by the detail of queuing model.


## 2.2. Basic Concepts of Self-Renewal Hash Chain

In this section, we introduce some basic concepts of SSS and the definition of the Benaloh-Leichter SSS.


### 2.2.1. Concept of SSS

First, we formally define the necessary monotone access structure.Definition 1.
Given a setP, a monotone access structure on P is a family of subsets Z
⊆
2
P such that(2)A∈Z,A⊆A′⊆P.↓A′∈Z.
Letn be an integer, n
≥
2, let the set of participants be P
=
p
1
,
p
2
,
⁡
…
,
p
n, and let an access structure Z defined on P be comprised of a collection of subsets of P
.
Z is a monotone access structure whenever A
∈
Z and A
⊆
A
′
⊆
P.Similarly,Z-SSS is a method of generating (S, (I
1
,
…
,
I
n)) such that,(1)
for anyA
∈
Z, finding the element S, given the set {
I
i
∣
i
∈
A
}, is easy,
(2)
for anyA
∈
Z
¯, finding the element S, given the set {
I
i
∣
i
∈
A
}, is difficult.The setZ is the authorized access structure or simply the access structure, S is the secret, and I
1
,
…
,
I
n are the shares (or the shadows) of S. The elements of the set Z are the authorized access sets of the scheme.


### 2.2.2. Benaloh-Leichter SSS

Definition 2.
LetP be a set. The set V of variables indexed by P is the set V
=
v
p
:
p
∈
P.Definition 3.
Given a monotone functionF on variables indexed by a set P, the access structure defined by F is the set of subsets of A of P for which F is true precisely when the variables indexed by A are set to be true.It is clear that, for every monotone functionF, the access structure defined by F is a monotone access structure.Definition 4.
For a given setP and a monotone access structure Z denoted by Z
m
i
n on P, define F
(
Z
) to be the set of monotone function on P variables such that, for every formula F
∈
F
(
Z
), the output of F is true if and only if the true variables in F correspond exactly to a set A
∈
Z.Note thatF
,
F
′
∈
F
(
Z
) implies F and F
′ denote the same function. They may, however, use entirely different expressions to express this function.The formula can be expressed using only∧ operator and ∨ operator, and it is sufficient to indicate how to “split” the secret with these operators.Definition 5.
One can recursively define the share of a secretS with respect to a formula F as follows:(3)F=S,i,ifF=vi,1≤i≤n⋃i=1nSharesS,Fi;ifF=F1∨F2∨⋯∨Fn⋃i=1nSharessi,Fi;ifF=F1∧F2∧⋯∧Fn,where based on Definitions 1, 2, and 3, selecting the specific integer n and Z
m
i
n, for the case F
=
F
1
∧
F
2
∧
⋯
∧
F
n, one can use a (
k
,
n
)-threshold secret sharing scheme for deriving some shares s
1
,
s
2
,
…
,
s
k corresponding to the secret S, and then every distinct share is assigned to each I
i. Thus one has I
i
=
{
s
i
∣
(
s
i
,
i
)
∈
S
h
a
r
e
s
(
S
,
F
)
}, for all 1
≤
i
≤
n, where F is an arbitrary formula in the set F
A.


### 2.2.3. Definition of Hash Chain

Definition 6.
The secure hash function is a publicly known functionf
n
:
0,1
∗
→
0,1
k, it takes s as an input, and the output is a bit string f
n
(
s
) of length n. In f
n
(
s
), s is generated randomly from a pseudo-random string generator. One-way hash chain can be visually expressed as follows:(4)s→h·hs→h·h2s⋯→h·hns.


## 2.2.1. Concept of SSS

First, we formally define the necessary monotone access structure.Definition 1.
Given a setP, a monotone access structure on P is a family of subsets Z
⊆
2
P such that(2)A∈Z,A⊆A′⊆P.↓A′∈Z.
Letn be an integer, n
≥
2, let the set of participants be P
=
p
1
,
p
2
,
⁡
…
,
p
n, and let an access structure Z defined on P be comprised of a collection of subsets of P
.
Z is a monotone access structure whenever A
∈
Z and A
⊆
A
′
⊆
P.Similarly,Z-SSS is a method of generating (S, (I
1
,
…
,
I
n)) such that,(1)
for anyA
∈
Z, finding the element S, given the set {
I
i
∣
i
∈
A
}, is easy,
(2)
for anyA
∈
Z
¯, finding the element S, given the set {
I
i
∣
i
∈
A
}, is difficult.The setZ is the authorized access structure or simply the access structure, S is the secret, and I
1
,
…
,
I
n are the shares (or the shadows) of S. The elements of the set Z are the authorized access sets of the scheme.


## 2.2.2. Benaloh-Leichter SSS

Definition 2.
LetP be a set. The set V of variables indexed by P is the set V
=
v
p
:
p
∈
P.Definition 3.
Given a monotone functionF on variables indexed by a set P, the access structure defined by F is the set of subsets of A of P for which F is true precisely when the variables indexed by A are set to be true.It is clear that, for every monotone functionF, the access structure defined by F is a monotone access structure.Definition 4.
For a given setP and a monotone access structure Z denoted by Z
m
i
n on P, define F
(
Z
) to be the set of monotone function on P variables such that, for every formula F
∈
F
(
Z
), the output of F is true if and only if the true variables in F correspond exactly to a set A
∈
Z.Note thatF
,
F
′
∈
F
(
Z
) implies F and F
′ denote the same function. They may, however, use entirely different expressions to express this function.The formula can be expressed using only∧ operator and ∨ operator, and it is sufficient to indicate how to “split” the secret with these operators.Definition 5.
One can recursively define the share of a secretS with respect to a formula F as follows:(3)F=S,i,ifF=vi,1≤i≤n⋃i=1nSharesS,Fi;ifF=F1∨F2∨⋯∨Fn⋃i=1nSharessi,Fi;ifF=F1∧F2∧⋯∧Fn,where based on Definitions 1, 2, and 3, selecting the specific integer n and Z
m
i
n, for the case F
=
F
1
∧
F
2
∧
⋯
∧
F
n, one can use a (
k
,
n
)-threshold secret sharing scheme for deriving some shares s
1
,
s
2
,
…
,
s
k corresponding to the secret S, and then every distinct share is assigned to each I
i. Thus one has I
i
=
{
s
i
∣
(
s
i
,
i
)
∈
S
h
a
r
e
s
(
S
,
F
)
}, for all 1
≤
i
≤
n, where F is an arbitrary formula in the set F
A.


## 2.2.3. Definition of Hash Chain

Definition 6.
The secure hash function is a publicly known functionf
n
:
0,1
∗
→
0,1
k, it takes s as an input, and the output is a bit string f
n
(
s
) of length n. In f
n
(
s
), s is generated randomly from a pseudo-random string generator. One-way hash chain can be visually expressed as follows:(4)s→h·hs→h·h2s⋯→h·hns.


## 3. Our Scheme

### 3.1. The Key Distribution Algorithm Based on Data Flow

Compared with the traditionalμTESLA protocol which releases keys based on the fixed time interval, our approach releases keys according to the data flow based on the queue theory and the renewable hash chain.


#### 3.1.1. Assumptions

(i)
μTESLA protocol is as follows:
(1)
the packet transmission time between the base station and the farthest node isT
m
a
x;
(2)
the base station releases the key everyT
i
n
t by a fixed time interval;
(3)
the delay time of key publication isσ
×
T
i
n
t, and it satisfies the condition that σ
×
T
i
n
t
>
T
m
a
x;
(4)
the verification condition isT
c
+
Δ
-
T
1
/
T
i
n
t
<
i
+
σ
-
1, where T
c is the current time, Δ is the maximum clock difference, T
1 is the start time, and i is the ith interval time.
(ii)
The improved broadcast authentication protocol based on the queue theory and the renewable hash chain is as follows:
(1)
the maximum speed (or frequency) for the base station to send packets isV
s
m
a
x;
(2)
the maximum transmission speed (or frequency) in WSNs isV
t
m
a
x;
(3)
the communication radius of the base station isR
b
s;
(4)
the base station releases the authentication key everyN
i
n
t packets based on data traffic;
(5)
the delay of data flow of key publication isN
i
n
t
+
θ, and it satisfies the condition that N
i
n
t
+
θ
/
V
s
m
a
x
>
R
b
s
/
V
t
m
a
x;
(6)
the verification condition is(
N
c
-
N
1
)
/
N
i
n
t
<
i
+
θ
-
1, where N
c is the identification number of packets that is currently received, N
1 is the ID number of first packet received, and i is the ith time interval of data flow.


#### 3.1.2. The Process of Key Distribution Based on Data Flow

The process of broadcast authentication based on queue theory and renewable hash chain is shown in Figure2. Comparing with Figure 1, we can see the difference between μTESLA and ours; μTESLA maps the key distribution to the time domain, while ours maps the key distribution to the flow domain.Figure 2
The process of broadcast authentication based on queue theory.


#### 3.1.3. Several Cases to Discuss

Case 1.
If the base station has not broadcasted a packet after a long period, and the number of packets broadcasted has not achieved a certain threshold, the base station will not release the key during this long period, which disables the node to authenticate the buffered packets. In this case, we can set a time thresholdT (T is the upper bound of broadcast key lifetime). So after time T, the base station is required to release key no matter whether the condition is satisfied.Case 2.
It is very common to have packet loss in WSNs. Consider the following case: the base station will not send packets in a long period and thus the key for the next round will not be released either, but unfortunately, at this time, one node lost the current authentication key, which implies that this node cannot authenticate the remaining packets in the buffer any more. In terms of this case, we set the interval time2
T for the node to wait, where T is the upper bound of broadcast key lifetime. If the waiting time exceeds 2
T, the node can send the request message to the base station for the key of current round.Case 3.
Synchronization problem: how do we know which packet should be authenticated by which type of key? We use the counting mechanism to solve this problem. That is, the broadcast packet sent by the base station is counted from 0 toN and authentication key is also numbered from 0 to N so that we can create the relations between the packet and the key by simply mapping.


### 3.2. A Self-Renewal Hash Chain Based on Benaloh-Leichter SSS

In this section, we propose a novel self-renewed hash chain based on Benaloh-Leichter SSS. This scheme has three phases: the hash chain initial phase, the hash chain usage phase, and the hash chain extension phase. LetC and R denote communication initiator and the recipient, respectively.


#### 3.2.1. Initial Phase

In the initial phase,C and R are synchronized in time, and there is a maximum error time denoted as Δ; R can reject the message which exceeds the time Δ plus the acceptable transmission delay.(1)
The initiatorC generates an initial random value s as the seed of the first hash chain, and then C uses the preloaded hash function to compute n hash value of the first hash chain. Consider(5)s→h·hs→h·h2s⋯→h·hns.
(2)
Then,C selects Z
m
i
n based on Benaloh-Leichter SSS and a new random value s
′ to generate n hash value of the next hash chain. Consider(6)s′→h·hs′→h·h2s′⋯→h·hns′.
(3)
Therefore, according to the Benaloh-Leichter SSS,C takesh
n
(
s
′
)as the secret S, divides it into n parts as the set V, and then defines the set F
(
Z
) as the set of formula on set V. Further, we select an arbitrary formula F in the set F
A. In this case, according to Z
m
i
n we can obtain Shares
(
S
,
F
) of the secret S. Thus, the shares corresponding to the secret S in the access structure Z are distributed as shadows I
1
,
I
2
,
…
,
I
n.


#### 3.2.2. Usage Phase

(1)
Before the usage phase,C and R have confirmed the initial time T
0, and meanwhile the value h
n
(
s
) and the hash function have been preloaded in R securely, as well as the message authentication code M
A
C
0
(
h
n
-
1
(
s
)
⊕
I
1
). During the usage phase, the hash value is used from h
n
-
1
s (firstly) to s (finally) corresponding to the time period T
0
+
i
∗
Δ
1
≤
i
≤
n.
(2)
In the timeT
0
+
Δ, C releases the Msg1 and its corresponding message authentication code MAC1 to R, the formats of Msg1 and MAC1 are shown, respectively, as follows:(7)Msg1T0+Δ,hn-1s,I1,MAC1,MAC1hn-2s⊕I2.So in the timeT
0
+
i
∗
Δ (1
≤
i
≤
n), C will compute and release(8)MsgiT0+i∗Δ,hn-is,Ii,MACi,MACihn-i-1s⊕Ii+1,where M
s
g
i is the content of current message and M
A
C
i is used to verify M
A
C
i
-
1.
(3)
For theith authentication, after R receives the M
s
g
i and M
A
C
i, R will calculate the difference between the last time of receiving packets and the current time of receiving packets. If the difference has not exceeded Δ, R will carry out the following steps:
(a)
Compute and verify whetherh
(
h
n
-
i
(
s
)
) is equal to h
n
-
i
+
1
(
s
), where h
n
-
i
+
1
(
s
) is the valid hash value stored in the last process. If it is equal, R saves it.
(b)
Compute and verify whetherI
i
⊕
h
n
-
i
(
s
) is equal to M
A
C
i
-
1. If it is, R saves M
A
C
i and I
i.On the other hand, if the difference exceedsΔ,(a)
C dropsh
n
-
i
(
s
)and I
i and saves M
A
C
i; then it will wait until the next authentication process, which is assumed as the jth authentication where i
<
j;
(b)
compute and verify whetherh
j
-
i
+
1
(
h
n
-
j
(
s
)
) is equal to h
n
-
i
+
1
(
s
), where h
n
-
i
+
1
(
s
) is the valid hash value stored in the last process; if it is equal, R saves it;
(c)
compute and verify whetherh
n
-
j
s
⊕
I
j is equal to M
A
C
j
-
1; if all checks are valid, R verifies C successfully and then stores the shadow I
i.The hash chain usage phase has a detailed description inμTESLA. If the hash chain is exhausted, the protocol goes into the hash chain extension phase.


#### 3.2.3. Extension Phase

When one hash chain has been exhausted,R has stored n shadows I
i. One thing we need to notice is that even though the number of shadows that R has stored is less than n (as long as the number is not less than k), we can still recover the final secret S. The detailed description is as follows.(1)
Based on the shadowsI
1
,
I
2
,
…
,
I
n, we can easily deduce S
h
a
r
e
s
(
S
,
F
)corresponding to the secret S with the (
k
,
n
)-threshold secret sharing scheme.
(2)
With theS
h
a
r
e
s
(
S
,
F
), we can simply recover the secret S. In other words, we have obtained the tail of the next hash chainh
n
(
s
′
). Then, a new hash chain can be applied in the right way, and we can use the same protocol in the next hash chain in order to achieve the purpose of self-renewed one.Therefore, this protocol provides an on-demand hash chain extension without exhaustion, so the hash chain is able to work smoothly and infinitely.


## 3.1. The Key Distribution Algorithm Based on Data Flow

Compared with the traditionalμTESLA protocol which releases keys based on the fixed time interval, our approach releases keys according to the data flow based on the queue theory and the renewable hash chain.


### 3.1.1. Assumptions

(i)
μTESLA protocol is as follows:
(1)
the packet transmission time between the base station and the farthest node isT
m
a
x;
(2)
the base station releases the key everyT
i
n
t by a fixed time interval;
(3)
the delay time of key publication isσ
×
T
i
n
t, and it satisfies the condition that σ
×
T
i
n
t
>
T
m
a
x;
(4)
the verification condition isT
c
+
Δ
-
T
1
/
T
i
n
t
<
i
+
σ
-
1, where T
c is the current time, Δ is the maximum clock difference, T
1 is the start time, and i is the ith interval time.
(ii)
The improved broadcast authentication protocol based on the queue theory and the renewable hash chain is as follows:
(1)
the maximum speed (or frequency) for the base station to send packets isV
s
m
a
x;
(2)
the maximum transmission speed (or frequency) in WSNs isV
t
m
a
x;
(3)
the communication radius of the base station isR
b
s;
(4)
the base station releases the authentication key everyN
i
n
t packets based on data traffic;
(5)
the delay of data flow of key publication isN
i
n
t
+
θ, and it satisfies the condition that N
i
n
t
+
θ
/
V
s
m
a
x
>
R
b
s
/
V
t
m
a
x;
(6)
the verification condition is(
N
c
-
N
1
)
/
N
i
n
t
<
i
+
θ
-
1, where N
c is the identification number of packets that is currently received, N
1 is the ID number of first packet received, and i is the ith time interval of data flow.


### 3.1.2. The Process of Key Distribution Based on Data Flow

The process of broadcast authentication based on queue theory and renewable hash chain is shown in Figure2. Comparing with Figure 1, we can see the difference between μTESLA and ours; μTESLA maps the key distribution to the time domain, while ours maps the key distribution to the flow domain.Figure 2
The process of broadcast authentication based on queue theory.


### 3.1.3. Several Cases to Discuss

Case 1.
If the base station has not broadcasted a packet after a long period, and the number of packets broadcasted has not achieved a certain threshold, the base station will not release the key during this long period, which disables the node to authenticate the buffered packets. In this case, we can set a time thresholdT (T is the upper bound of broadcast key lifetime). So after time T, the base station is required to release key no matter whether the condition is satisfied.Case 2.
It is very common to have packet loss in WSNs. Consider the following case: the base station will not send packets in a long period and thus the key for the next round will not be released either, but unfortunately, at this time, one node lost the current authentication key, which implies that this node cannot authenticate the remaining packets in the buffer any more. In terms of this case, we set the interval time2
T for the node to wait, where T is the upper bound of broadcast key lifetime. If the waiting time exceeds 2
T, the node can send the request message to the base station for the key of current round.Case 3.
Synchronization problem: how do we know which packet should be authenticated by which type of key? We use the counting mechanism to solve this problem. That is, the broadcast packet sent by the base station is counted from 0 toN and authentication key is also numbered from 0 to N so that we can create the relations between the packet and the key by simply mapping.


## 3.1.1. Assumptions

(i)
μTESLA protocol is as follows:
(1)
the packet transmission time between the base station and the farthest node isT
m
a
x;
(2)
the base station releases the key everyT
i
n
t by a fixed time interval;
(3)
the delay time of key publication isσ
×
T
i
n
t, and it satisfies the condition that σ
×
T
i
n
t
>
T
m
a
x;
(4)
the verification condition isT
c
+
Δ
-
T
1
/
T
i
n
t
<
i
+
σ
-
1, where T
c is the current time, Δ is the maximum clock difference, T
1 is the start time, and i is the ith interval time.
(ii)
The improved broadcast authentication protocol based on the queue theory and the renewable hash chain is as follows:
(1)
the maximum speed (or frequency) for the base station to send packets isV
s
m
a
x;
(2)
the maximum transmission speed (or frequency) in WSNs isV
t
m
a
x;
(3)
the communication radius of the base station isR
b
s;
(4)
the base station releases the authentication key everyN
i
n
t packets based on data traffic;
(5)
the delay of data flow of key publication isN
i
n
t
+
θ, and it satisfies the condition that N
i
n
t
+
θ
/
V
s
m
a
x
>
R
b
s
/
V
t
m
a
x;
(6)
the verification condition is(
N
c
-
N
1
)
/
N
i
n
t
<
i
+
θ
-
1, where N
c is the identification number of packets that is currently received, N
1 is the ID number of first packet received, and i is the ith time interval of data flow.


## 3.1.2. The Process of Key Distribution Based on Data Flow

The process of broadcast authentication based on queue theory and renewable hash chain is shown in Figure2. Comparing with Figure 1, we can see the difference between μTESLA and ours; μTESLA maps the key distribution to the time domain, while ours maps the key distribution to the flow domain.Figure 2
The process of broadcast authentication based on queue theory.


## 3.1.3. Several Cases to Discuss

Case 1.
If the base station has not broadcasted a packet after a long period, and the number of packets broadcasted has not achieved a certain threshold, the base station will not release the key during this long period, which disables the node to authenticate the buffered packets. In this case, we can set a time thresholdT (T is the upper bound of broadcast key lifetime). So after time T, the base station is required to release key no matter whether the condition is satisfied.Case 2.
It is very common to have packet loss in WSNs. Consider the following case: the base station will not send packets in a long period and thus the key for the next round will not be released either, but unfortunately, at this time, one node lost the current authentication key, which implies that this node cannot authenticate the remaining packets in the buffer any more. In terms of this case, we set the interval time2
T for the node to wait, where T is the upper bound of broadcast key lifetime. If the waiting time exceeds 2
T, the node can send the request message to the base station for the key of current round.Case 3.
Synchronization problem: how do we know which packet should be authenticated by which type of key? We use the counting mechanism to solve this problem. That is, the broadcast packet sent by the base station is counted from 0 toN and authentication key is also numbered from 0 to N so that we can create the relations between the packet and the key by simply mapping.


## 3.2. A Self-Renewal Hash Chain Based on Benaloh-Leichter SSS

In this section, we propose a novel self-renewed hash chain based on Benaloh-Leichter SSS. This scheme has three phases: the hash chain initial phase, the hash chain usage phase, and the hash chain extension phase. LetC and R denote communication initiator and the recipient, respectively.


### 3.2.1. Initial Phase

In the initial phase,C and R are synchronized in time, and there is a maximum error time denoted as Δ; R can reject the message which exceeds the time Δ plus the acceptable transmission delay.(1)
The initiatorC generates an initial random value s as the seed of the first hash chain, and then C uses the preloaded hash function to compute n hash value of the first hash chain. Consider(5)s→h·hs→h·h2s⋯→h·hns.
(2)
Then,C selects Z
m
i
n based on Benaloh-Leichter SSS and a new random value s
′ to generate n hash value of the next hash chain. Consider(6)s′→h·hs′→h·h2s′⋯→h·hns′.
(3)
Therefore, according to the Benaloh-Leichter SSS,C takesh
n
(
s
′
)as the secret S, divides it into n parts as the set V, and then defines the set F
(
Z
) as the set of formula on set V. Further, we select an arbitrary formula F in the set F
A. In this case, according to Z
m
i
n we can obtain Shares
(
S
,
F
) of the secret S. Thus, the shares corresponding to the secret S in the access structure Z are distributed as shadows I
1
,
I
2
,
…
,
I
n.


### 3.2.2. Usage Phase

(1)
Before the usage phase,C and R have confirmed the initial time T
0, and meanwhile the value h
n
(
s
) and the hash function have been preloaded in R securely, as well as the message authentication code M
A
C
0
(
h
n
-
1
(
s
)
⊕
I
1
). During the usage phase, the hash value is used from h
n
-
1
s (firstly) to s (finally) corresponding to the time period T
0
+
i
∗
Δ
1
≤
i
≤
n.
(2)
In the timeT
0
+
Δ, C releases the Msg1 and its corresponding message authentication code MAC1 to R, the formats of Msg1 and MAC1 are shown, respectively, as follows:(7)Msg1T0+Δ,hn-1s,I1,MAC1,MAC1hn-2s⊕I2.So in the timeT
0
+
i
∗
Δ (1
≤
i
≤
n), C will compute and release(8)MsgiT0+i∗Δ,hn-is,Ii,MACi,MACihn-i-1s⊕Ii+1,where M
s
g
i is the content of current message and M
A
C
i is used to verify M
A
C
i
-
1.
(3)
For theith authentication, after R receives the M
s
g
i and M
A
C
i, R will calculate the difference between the last time of receiving packets and the current time of receiving packets. If the difference has not exceeded Δ, R will carry out the following steps:
(a)
Compute and verify whetherh
(
h
n
-
i
(
s
)
) is equal to h
n
-
i
+
1
(
s
), where h
n
-
i
+
1
(
s
) is the valid hash value stored in the last process. If it is equal, R saves it.
(b)
Compute and verify whetherI
i
⊕
h
n
-
i
(
s
) is equal to M
A
C
i
-
1. If it is, R saves M
A
C
i and I
i.On the other hand, if the difference exceedsΔ,(a)
C dropsh
n
-
i
(
s
)and I
i and saves M
A
C
i; then it will wait until the next authentication process, which is assumed as the jth authentication where i
<
j;
(b)
compute and verify whetherh
j
-
i
+
1
(
h
n
-
j
(
s
)
) is equal to h
n
-
i
+
1
(
s
), where h
n
-
i
+
1
(
s
) is the valid hash value stored in the last process; if it is equal, R saves it;
(c)
compute and verify whetherh
n
-
j
s
⊕
I
j is equal to M
A
C
j
-
1; if all checks are valid, R verifies C successfully and then stores the shadow I
i.The hash chain usage phase has a detailed description inμTESLA. If the hash chain is exhausted, the protocol goes into the hash chain extension phase.


### 3.2.3. Extension Phase

When one hash chain has been exhausted,R has stored n shadows I
i. One thing we need to notice is that even though the number of shadows that R has stored is less than n (as long as the number is not less than k), we can still recover the final secret S. The detailed description is as follows.(1)
Based on the shadowsI
1
,
I
2
,
…
,
I
n, we can easily deduce S
h
a
r
e
s
(
S
,
F
)corresponding to the secret S with the (
k
,
n
)-threshold secret sharing scheme.
(2)
With theS
h
a
r
e
s
(
S
,
F
), we can simply recover the secret S. In other words, we have obtained the tail of the next hash chainh
n
(
s
′
). Then, a new hash chain can be applied in the right way, and we can use the same protocol in the next hash chain in order to achieve the purpose of self-renewed one.Therefore, this protocol provides an on-demand hash chain extension without exhaustion, so the hash chain is able to work smoothly and infinitely.


## 3.2.1. Initial Phase

In the initial phase,C and R are synchronized in time, and there is a maximum error time denoted as Δ; R can reject the message which exceeds the time Δ plus the acceptable transmission delay.(1)
The initiatorC generates an initial random value s as the seed of the first hash chain, and then C uses the preloaded hash function to compute n hash value of the first hash chain. Consider(5)s→h·hs→h·h2s⋯→h·hns.
(2)
Then,C selects Z
m
i
n based on Benaloh-Leichter SSS and a new random value s
′ to generate n hash value of the next hash chain. Consider(6)s′→h·hs′→h·h2s′⋯→h·hns′.
(3)
Therefore, according to the Benaloh-Leichter SSS,C takesh
n
(
s
′
)as the secret S, divides it into n parts as the set V, and then defines the set F
(
Z
) as the set of formula on set V. Further, we select an arbitrary formula F in the set F
A. In this case, according to Z
m
i
n we can obtain Shares
(
S
,
F
) of the secret S. Thus, the shares corresponding to the secret S in the access structure Z are distributed as shadows I
1
,
I
2
,
…
,
I
n.


## 3.2.2. Usage Phase

(1)
Before the usage phase,C and R have confirmed the initial time T
0, and meanwhile the value h
n
(
s
) and the hash function have been preloaded in R securely, as well as the message authentication code M
A
C
0
(
h
n
-
1
(
s
)
⊕
I
1
). During the usage phase, the hash value is used from h
n
-
1
s (firstly) to s (finally) corresponding to the time period T
0
+
i
∗
Δ
1
≤
i
≤
n.
(2)
In the timeT
0
+
Δ, C releases the Msg1 and its corresponding message authentication code MAC1 to R, the formats of Msg1 and MAC1 are shown, respectively, as follows:(7)Msg1T0+Δ,hn-1s,I1,MAC1,MAC1hn-2s⊕I2.So in the timeT
0
+
i
∗
Δ (1
≤
i
≤
n), C will compute and release(8)MsgiT0+i∗Δ,hn-is,Ii,MACi,MACihn-i-1s⊕Ii+1,where M
s
g
i is the content of current message and M
A
C
i is used to verify M
A
C
i
-
1.
(3)
For theith authentication, after R receives the M
s
g
i and M
A
C
i, R will calculate the difference between the last time of receiving packets and the current time of receiving packets. If the difference has not exceeded Δ, R will carry out the following steps:
(a)
Compute and verify whetherh
(
h
n
-
i
(
s
)
) is equal to h
n
-
i
+
1
(
s
), where h
n
-
i
+
1
(
s
) is the valid hash value stored in the last process. If it is equal, R saves it.
(b)
Compute and verify whetherI
i
⊕
h
n
-
i
(
s
) is equal to M
A
C
i
-
1. If it is, R saves M
A
C
i and I
i.On the other hand, if the difference exceedsΔ,(a)
C dropsh
n
-
i
(
s
)and I
i and saves M
A
C
i; then it will wait until the next authentication process, which is assumed as the jth authentication where i
<
j;
(b)
compute and verify whetherh
j
-
i
+
1
(
h
n
-
j
(
s
)
) is equal to h
n
-
i
+
1
(
s
), where h
n
-
i
+
1
(
s
) is the valid hash value stored in the last process; if it is equal, R saves it;
(c)
compute and verify whetherh
n
-
j
s
⊕
I
j is equal to M
A
C
j
-
1; if all checks are valid, R verifies C successfully and then stores the shadow I
i.The hash chain usage phase has a detailed description inμTESLA. If the hash chain is exhausted, the protocol goes into the hash chain extension phase.


## 3.2.3. Extension Phase

When one hash chain has been exhausted,R has stored n shadows I
i. One thing we need to notice is that even though the number of shadows that R has stored is less than n (as long as the number is not less than k), we can still recover the final secret S. The detailed description is as follows.(1)
Based on the shadowsI
1
,
I
2
,
…
,
I
n, we can easily deduce S
h
a
r
e
s
(
S
,
F
)corresponding to the secret S with the (
k
,
n
)-threshold secret sharing scheme.
(2)
With theS
h
a
r
e
s
(
S
,
F
), we can simply recover the secret S. In other words, we have obtained the tail of the next hash chainh
n
(
s
′
). Then, a new hash chain can be applied in the right way, and we can use the same protocol in the next hash chain in order to achieve the purpose of self-renewed one.Therefore, this protocol provides an on-demand hash chain extension without exhaustion, so the hash chain is able to work smoothly and infinitely.


## 4. Performance Analysis

### 4.1. The Key Distribution Algorithm Based on Data Flow

(1) Our algorithm releases the keys based on the data flow instead of the original timeline and takes full account of the uneven distribution of arrival of the packets in the network.(2) Valid packets simulation in theμTESLA protocol: many simulation techniques in [11, 12] are introduced to wireless sensor networks to help researchers to understand the behavior of the network which is hard to capture in situ. In this paper, we use Matlab to simulate the four queuing models of M/D/1/∞, M/M/1/∞, M/G/1/∞, and GI/G/1/∞, respectively. We take the base station as the waiter and the broadcast packets as the customer source, so the service time obeys the distribution of the packets to be processed and broadcasted by the base station and customer source obeys the distribution of arrival of packets. By considering practical situations, we give an example of packets arriving intensively. The arrival of data packets of M/D/1/∞, M/M/1/∞, and M/G/1/∞ obeys Poisson distribution with the randomly selected parameter λ
=
0.5, while GI/G/1/∞ obeys the general random distribution. We set a fixed time interval T
i
n
t as 60 s and the numbers of valid packets N
s
t
r in T
i
n
t as 20, and the simulation time was half an hour. If the number is over 20, we would consider it as invalid one. There are two reasons for that. First, overly late authentication would cause the large storage overhead caused by the accumulated packets in the node buffer. Second, the message is more likely to be vulnerable to chosen plaintext attacks. It can also be proved that the conclusions of simulation experiments will not change by altering the values of parameters such as λ and T
i
n
t.(3) Simulation comparison of key packets consumed: we use Matlab to simulate the four queuing models of M/D/1/∞, M/M/1/∞, M/G/1/∞, and GI/G/1/∞, respectively, and we take the example of packets arriving sparsely. (a) The arrival of packets of M/D/1/∞ obeys the Poisson distribution with parameterλ
=
0.1 and the service time obeys the uniform distribution with a fixed value t
=
1 s. (b) The arrival of packets of M/M/1/∞ obeys the Poisson distribution with parameter λ
=
0.1 and the service time obeys the Poisson distribution with parameter μ
=
20. (c) The arrival of packets of M/G/1/∞ obeys the Poisson distribution with parameter λ
=
0.1 and the service time obeys the general random distribution. (d) The arrival of packets of GI/G/1/∞ and the service time obey the general random distribution. We set a fixed time interval T
i
n
t
=
60 s, and the data flow interval is N
i
n
t
=
20; the simulation time was ten hours.(i)
In terms of the intensive rate of packets arrival, based on the fixed time interval, the simulation results of valid data packets, dropped packets, and total packets for 4 queuing models M/D/1/∞, M/M/1/∞, M/G/1/∞, and GI/G/1/∞ are shown in Figures3–6, respectively.
(ii)
In terms of the sparse rate of packets arrival, we draw a comparison betweenμTESLA (based on the fixed interval) and our protocol (based on the data flow). The simulation results of key consumption for 4 queuing models M/D/1/∞, M/M/1/∞, M/G/1/∞, and GI/G/1/∞ are shown in Figures 7–10, respectively.Figure 3
Packets of M/D/1.Figure 4
Packets of M/M/1.Figure 5
Packets of M/G/1.Figure 6
Packets of GI/G/1.Figure 7
Keys consumption of M/D/1.Figure 8
Keys consumption of M/M/1.Figure 9
Keys consumption of M/G/1.Figure 10
Keys consumption of GI/G/1.From Figures3–6, we notice that the intensive rate of broadcast packets will cause the packets to be cached in the nodes and unable to be authenticated timely, which eventually results in the loss of packets. Also, the probability of choosing plaintext attack will become large if the number of packets exceeds the threshold N
s
t
r.Furthermore, from Figures7–10, the key consumption of our proposal is much lower than that of μTESLA. Consequently, the life cycle of the key chain would be prolonged, and the network overhead would be reduced.(4) The calculation complexity of the proposed algorithm is low. From Figures1 and 2, we can find that there is no fallback process in both μTESLA protocol and our algorithm. Although different network environments can contribute to different consumption of calculation, the proposed algorithm and μTESLA both keep O
(
n
), where n is the number of hash calculations during authentication processes. However, in the protocol of multilevel μTESLA [13], repeated hash operations are conducted to guarantee life time of keys at the expense of large amounts of calculations. For instance, m denotes the time of high-level calculation while n denotes that of low-level calculation in a 2-level μTESLA process, which leads to m
·
n times of calculation. When n
=
m, the complexity achieves O
(
n
2
); the order of magnitudes increases sharply and contributes to high calculation complexity if n becomes large. The variation tendency can be seen in Figure 11.Figure 11
The calculation of three algorithms.


### 4.2. A Self-Renewal Hash Chain Based on Benaloh-Leichter SSS

In this section, we will present the security and performance analysis of the proposed hash chain in Section3.


#### 4.2.1. Security

The security of this scheme is based on one-way function and Benaloh-Leichter SSS. The purpose ofXOR with hash value is to maintain the integrity and confidentiality of shadows. And the purpose of delaying key publication is to achieve nonrepudiation.Meanwhile, Benaloh-Leichter SSS can efficiently generate a much richer family of access structures than the current schemes, and it is convenient to view an access structure as a function. Any monotone Boolean function overn variables can be computed by a monotone formula. Thus, every access structure can be realized by the scheme of Benaloh-Leichter SSS. On the other hand, for every set that does not belong to the access structure, the elements in the set do not have any information on s
i; hence they will not reveal any information about secret S.Also in the phase of authentication, the tolerance of packet loss or fault is embodied in our proposal. However, in Benaloh-Leichter SSS, even somes
i was dropped or lost; secret S can still be verified by other valid s
i as long as the number of shadows is not less than k.Moreover, dual authentication in our scheme can strengthen the security and integrity. The first authentication is that whetherh
n
-
i
(
s
) and I
i are received in a valid interval and they will not be stored unless both of them are verified correctly. And the second authentication is to judge whether h
n
-
i
(
s
) is valid according toh
n
-
i
+
1
(
s
)which has been stored in the first authentication and whether I
i is valid by the exclusive-OR function. The shadow I
i will be accepted only if the packet passes the dual authentication.Finally, our self-renewal hash chain has satisfactory confidentiality. However, the shadowI
i exists in the packet with the form of plaintext and the attacker can obtain the key shadow information by snooping the packet. However, the attacker is unlikely to recover the secret S unless he or she can get more than k pieces of shadow, which obviously increases the difficulty. And even though the attacker can finally recover the secret S, he or she is still unable to produce the fake broadcast packets to play the role of the base station. The reason is that the secret S, namely,  h
n
(
s
′
), is the tail of the next hash chain, which can only be used to authenticate the subsequent keys. And due to one-way feature of the hash function, the attacker cannot generate  h
n
-
1
(
s
′
)
,
h
n
-
2
(
s
′
)
,
…
,
s
′, so he or she is unable to fake the packet to deceive other sensor nodes. If the attacker does, these nodes can easily detect the validity of packets with  h
n
(
s
′
).


#### 4.2.2. Complexity

In this part, we will analyze the performance of our proposal. Before that, we first define some parameters which are mentioned as follows:m: the output of hash function which is an m-bit string,
n: the length of hash chain,
i: the number of secret shadows in SRHC-BL,
M: the computation consumption of the hash function,
N: the computation consumption of the union operation,
R, R
A, R
A
′: the computation consumptions of generating a random number in RHC, ERHC, and SUHC (or SRHC), respectively,
A, A
′: the computation consumption of obtaining one bit from a random number by hard core predicate in SUHC and SRHC, respectively,
C, I, P: the computation consumption of obtaining S
h
a
r
e
s
(
S
,
F
), computing the shadows I
i, and picking secret shadows s
i from I
i in SRHC-BL successively,
E: the computation consumption of XOR,
L
M: the communication or memory consumption of m
(
b
i
t
),
L
s: the communication or memory consumption of the seed of hash chain,
L
r: the communication or memory consumption of the generated random number,
L
I: the communication or memory consumption of shadows I
i in SRHC-BL,
L
e: the communication or memory consumption of the secret shadows s
i in SRHC-BL.Then, we compare the computation, communication, and storage cost of our scheme SRHC-BL with the current schemes RHC, ERHC, SUHC, and SRHC. The comparison results are shown as follows.RHC is as follows:
Computation:(9)12m2+9mM+2mR.
Communication:(10)2LM+3m×Lr+6m-2.
Storage:(11)2Ls+3Lr+m+6×LM+m.
SUHC is as follows:
Computation:(12)12m2+12m-2·M+mRA+mA.
Communication:(13)6m-1·LM+2m·Lr.
Storage:(14)2Ls+Lr+m+6LM+m.
ERHC is as follows:
Computation:(15)12n2+5n+5m+5log2⁡m+5·M+2m+log2⁡m+1·R+2N.
Communication:(16)2n+m+log2⁡m+1·LM+m+log2⁡m+1·Lr.
Storage:(17)n+3m+log2⁡m+1·LM+m×1+2Lr.
SRHC is as follows:
Computation:(18)12m2+11m-2·M+m·RA′+mA′.
Communication:(19)4m·LM+2m·Lr.
Storage:(20)2Ls+3Lr+3+mLM+m.
SRHC-BL is as follows:
Computation:(21)12n2+7n-2M+2nE+nI+P+C.
Communication:(22)4n-2·LM+2n·LI.
Storage:(23)n+3·LM+n·LI+i·Le+2m.For simplicity, we assumed thatm
≈
n, R
≈
R
A
≈
R
A
′, A
≈
A
′, M
>
N, M
>
C
>
I
>
P, and L
M
≫
L
s
≈
L
r
≈
L
I
>
L
c, so that it is easy to know the performance of our SRHC-BL relative to RHC, ERHC, SUHC, and SRHC. Through comparison, we can draw the following conclusion: the consumption of SRHC-BL in the initialization phase is much less than other schemes, while, in the phase of key distribution and authentication, SRHC-BL’s consumptions of communication and storage are a little more than SRHC’s but much less than RHC’s, ERHC’s, and SUHC’s.


## 4.1. The Key Distribution Algorithm Based on Data Flow

(1) Our algorithm releases the keys based on the data flow instead of the original timeline and takes full account of the uneven distribution of arrival of the packets in the network.(2) Valid packets simulation in theμTESLA protocol: many simulation techniques in [11, 12] are introduced to wireless sensor networks to help researchers to understand the behavior of the network which is hard to capture in situ. In this paper, we use Matlab to simulate the four queuing models of M/D/1/∞, M/M/1/∞, M/G/1/∞, and GI/G/1/∞, respectively. We take the base station as the waiter and the broadcast packets as the customer source, so the service time obeys the distribution of the packets to be processed and broadcasted by the base station and customer source obeys the distribution of arrival of packets. By considering practical situations, we give an example of packets arriving intensively. The arrival of data packets of M/D/1/∞, M/M/1/∞, and M/G/1/∞ obeys Poisson distribution with the randomly selected parameter λ
=
0.5, while GI/G/1/∞ obeys the general random distribution. We set a fixed time interval T
i
n
t as 60 s and the numbers of valid packets N
s
t
r in T
i
n
t as 20, and the simulation time was half an hour. If the number is over 20, we would consider it as invalid one. There are two reasons for that. First, overly late authentication would cause the large storage overhead caused by the accumulated packets in the node buffer. Second, the message is more likely to be vulnerable to chosen plaintext attacks. It can also be proved that the conclusions of simulation experiments will not change by altering the values of parameters such as λ and T
i
n
t.(3) Simulation comparison of key packets consumed: we use Matlab to simulate the four queuing models of M/D/1/∞, M/M/1/∞, M/G/1/∞, and GI/G/1/∞, respectively, and we take the example of packets arriving sparsely. (a) The arrival of packets of M/D/1/∞ obeys the Poisson distribution with parameterλ
=
0.1 and the service time obeys the uniform distribution with a fixed value t
=
1 s. (b) The arrival of packets of M/M/1/∞ obeys the Poisson distribution with parameter λ
=
0.1 and the service time obeys the Poisson distribution with parameter μ
=
20. (c) The arrival of packets of M/G/1/∞ obeys the Poisson distribution with parameter λ
=
0.1 and the service time obeys the general random distribution. (d) The arrival of packets of GI/G/1/∞ and the service time obey the general random distribution. We set a fixed time interval T
i
n
t
=
60 s, and the data flow interval is N
i
n
t
=
20; the simulation time was ten hours.(i)
In terms of the intensive rate of packets arrival, based on the fixed time interval, the simulation results of valid data packets, dropped packets, and total packets for 4 queuing models M/D/1/∞, M/M/1/∞, M/G/1/∞, and GI/G/1/∞ are shown in Figures3–6, respectively.
(ii)
In terms of the sparse rate of packets arrival, we draw a comparison betweenμTESLA (based on the fixed interval) and our protocol (based on the data flow). The simulation results of key consumption for 4 queuing models M/D/1/∞, M/M/1/∞, M/G/1/∞, and GI/G/1/∞ are shown in Figures 7–10, respectively.Figure 3
Packets of M/D/1.Figure 4
Packets of M/M/1.Figure 5
Packets of M/G/1.Figure 6
Packets of GI/G/1.Figure 7
Keys consumption of M/D/1.Figure 8
Keys consumption of M/M/1.Figure 9
Keys consumption of M/G/1.Figure 10
Keys consumption of GI/G/1.From Figures3–6, we notice that the intensive rate of broadcast packets will cause the packets to be cached in the nodes and unable to be authenticated timely, which eventually results in the loss of packets. Also, the probability of choosing plaintext attack will become large if the number of packets exceeds the threshold N
s
t
r.Furthermore, from Figures7–10, the key consumption of our proposal is much lower than that of μTESLA. Consequently, the life cycle of the key chain would be prolonged, and the network overhead would be reduced.(4) The calculation complexity of the proposed algorithm is low. From Figures1 and 2, we can find that there is no fallback process in both μTESLA protocol and our algorithm. Although different network environments can contribute to different consumption of calculation, the proposed algorithm and μTESLA both keep O
(
n
), where n is the number of hash calculations during authentication processes. However, in the protocol of multilevel μTESLA [13], repeated hash operations are conducted to guarantee life time of keys at the expense of large amounts of calculations. For instance, m denotes the time of high-level calculation while n denotes that of low-level calculation in a 2-level μTESLA process, which leads to m
·
n times of calculation. When n
=
m, the complexity achieves O
(
n
2
); the order of magnitudes increases sharply and contributes to high calculation complexity if n becomes large. The variation tendency can be seen in Figure 11.Figure 11
The calculation of three algorithms.


## 4.2. A Self-Renewal Hash Chain Based on Benaloh-Leichter SSS

In this section, we will present the security and performance analysis of the proposed hash chain in Section3.


### 4.2.1. Security

The security of this scheme is based on one-way function and Benaloh-Leichter SSS. The purpose ofXOR with hash value is to maintain the integrity and confidentiality of shadows. And the purpose of delaying key publication is to achieve nonrepudiation.Meanwhile, Benaloh-Leichter SSS can efficiently generate a much richer family of access structures than the current schemes, and it is convenient to view an access structure as a function. Any monotone Boolean function overn variables can be computed by a monotone formula. Thus, every access structure can be realized by the scheme of Benaloh-Leichter SSS. On the other hand, for every set that does not belong to the access structure, the elements in the set do not have any information on s
i; hence they will not reveal any information about secret S.Also in the phase of authentication, the tolerance of packet loss or fault is embodied in our proposal. However, in Benaloh-Leichter SSS, even somes
i was dropped or lost; secret S can still be verified by other valid s
i as long as the number of shadows is not less than k.Moreover, dual authentication in our scheme can strengthen the security and integrity. The first authentication is that whetherh
n
-
i
(
s
) and I
i are received in a valid interval and they will not be stored unless both of them are verified correctly. And the second authentication is to judge whether h
n
-
i
(
s
) is valid according toh
n
-
i
+
1
(
s
)which has been stored in the first authentication and whether I
i is valid by the exclusive-OR function. The shadow I
i will be accepted only if the packet passes the dual authentication.Finally, our self-renewal hash chain has satisfactory confidentiality. However, the shadowI
i exists in the packet with the form of plaintext and the attacker can obtain the key shadow information by snooping the packet. However, the attacker is unlikely to recover the secret S unless he or she can get more than k pieces of shadow, which obviously increases the difficulty. And even though the attacker can finally recover the secret S, he or she is still unable to produce the fake broadcast packets to play the role of the base station. The reason is that the secret S, namely,  h
n
(
s
′
), is the tail of the next hash chain, which can only be used to authenticate the subsequent keys. And due to one-way feature of the hash function, the attacker cannot generate  h
n
-
1
(
s
′
)
,
h
n
-
2
(
s
′
)
,
…
,
s
′, so he or she is unable to fake the packet to deceive other sensor nodes. If the attacker does, these nodes can easily detect the validity of packets with  h
n
(
s
′
).


### 4.2.2. Complexity

In this part, we will analyze the performance of our proposal. Before that, we first define some parameters which are mentioned as follows:m: the output of hash function which is an m-bit string,
n: the length of hash chain,
i: the number of secret shadows in SRHC-BL,
M: the computation consumption of the hash function,
N: the computation consumption of the union operation,
R, R
A, R
A
′: the computation consumptions of generating a random number in RHC, ERHC, and SUHC (or SRHC), respectively,
A, A
′: the computation consumption of obtaining one bit from a random number by hard core predicate in SUHC and SRHC, respectively,
C, I, P: the computation consumption of obtaining S
h
a
r
e
s
(
S
,
F
), computing the shadows I
i, and picking secret shadows s
i from I
i in SRHC-BL successively,
E: the computation consumption of XOR,
L
M: the communication or memory consumption of m
(
b
i
t
),
L
s: the communication or memory consumption of the seed of hash chain,
L
r: the communication or memory consumption of the generated random number,
L
I: the communication or memory consumption of shadows I
i in SRHC-BL,
L
e: the communication or memory consumption of the secret shadows s
i in SRHC-BL.Then, we compare the computation, communication, and storage cost of our scheme SRHC-BL with the current schemes RHC, ERHC, SUHC, and SRHC. The comparison results are shown as follows.RHC is as follows:
Computation:(9)12m2+9mM+2mR.
Communication:(10)2LM+3m×Lr+6m-2.
Storage:(11)2Ls+3Lr+m+6×LM+m.
SUHC is as follows:
Computation:(12)12m2+12m-2·M+mRA+mA.
Communication:(13)6m-1·LM+2m·Lr.
Storage:(14)2Ls+Lr+m+6LM+m.
ERHC is as follows:
Computation:(15)12n2+5n+5m+5log2⁡m+5·M+2m+log2⁡m+1·R+2N.
Communication:(16)2n+m+log2⁡m+1·LM+m+log2⁡m+1·Lr.
Storage:(17)n+3m+log2⁡m+1·LM+m×1+2Lr.
SRHC is as follows:
Computation:(18)12m2+11m-2·M+m·RA′+mA′.
Communication:(19)4m·LM+2m·Lr.
Storage:(20)2Ls+3Lr+3+mLM+m.
SRHC-BL is as follows:
Computation:(21)12n2+7n-2M+2nE+nI+P+C.
Communication:(22)4n-2·LM+2n·LI.
Storage:(23)n+3·LM+n·LI+i·Le+2m.For simplicity, we assumed thatm
≈
n, R
≈
R
A
≈
R
A
′, A
≈
A
′, M
>
N, M
>
C
>
I
>
P, and L
M
≫
L
s
≈
L
r
≈
L
I
>
L
c, so that it is easy to know the performance of our SRHC-BL relative to RHC, ERHC, SUHC, and SRHC. Through comparison, we can draw the following conclusion: the consumption of SRHC-BL in the initialization phase is much less than other schemes, while, in the phase of key distribution and authentication, SRHC-BL’s consumptions of communication and storage are a little more than SRHC’s but much less than RHC’s, ERHC’s, and SUHC’s.


## 4.2.1. Security

The security of this scheme is based on one-way function and Benaloh-Leichter SSS. The purpose ofXOR with hash value is to maintain the integrity and confidentiality of shadows. And the purpose of delaying key publication is to achieve nonrepudiation.Meanwhile, Benaloh-Leichter SSS can efficiently generate a much richer family of access structures than the current schemes, and it is convenient to view an access structure as a function. Any monotone Boolean function overn variables can be computed by a monotone formula. Thus, every access structure can be realized by the scheme of Benaloh-Leichter SSS. On the other hand, for every set that does not belong to the access structure, the elements in the set do not have any information on s
i; hence they will not reveal any information about secret S.Also in the phase of authentication, the tolerance of packet loss or fault is embodied in our proposal. However, in Benaloh-Leichter SSS, even somes
i was dropped or lost; secret S can still be verified by other valid s
i as long as the number of shadows is not less than k.Moreover, dual authentication in our scheme can strengthen the security and integrity. The first authentication is that whetherh
n
-
i
(
s
) and I
i are received in a valid interval and they will not be stored unless both of them are verified correctly. And the second authentication is to judge whether h
n
-
i
(
s
) is valid according toh
n
-
i
+
1
(
s
)which has been stored in the first authentication and whether I
i is valid by the exclusive-OR function. The shadow I
i will be accepted only if the packet passes the dual authentication.Finally, our self-renewal hash chain has satisfactory confidentiality. However, the shadowI
i exists in the packet with the form of plaintext and the attacker can obtain the key shadow information by snooping the packet. However, the attacker is unlikely to recover the secret S unless he or she can get more than k pieces of shadow, which obviously increases the difficulty. And even though the attacker can finally recover the secret S, he or she is still unable to produce the fake broadcast packets to play the role of the base station. The reason is that the secret S, namely,  h
n
(
s
′
), is the tail of the next hash chain, which can only be used to authenticate the subsequent keys. And due to one-way feature of the hash function, the attacker cannot generate  h
n
-
1
(
s
′
)
,
h
n
-
2
(
s
′
)
,
…
,
s
′, so he or she is unable to fake the packet to deceive other sensor nodes. If the attacker does, these nodes can easily detect the validity of packets with  h
n
(
s
′
).


## 4.2.2. Complexity

In this part, we will analyze the performance of our proposal. Before that, we first define some parameters which are mentioned as follows:m: the output of hash function which is an m-bit string,
n: the length of hash chain,
i: the number of secret shadows in SRHC-BL,
M: the computation consumption of the hash function,
N: the computation consumption of the union operation,
R, R
A, R
A
′: the computation consumptions of generating a random number in RHC, ERHC, and SUHC (or SRHC), respectively,
A, A
′: the computation consumption of obtaining one bit from a random number by hard core predicate in SUHC and SRHC, respectively,
C, I, P: the computation consumption of obtaining S
h
a
r
e
s
(
S
,
F
), computing the shadows I
i, and picking secret shadows s
i from I
i in SRHC-BL successively,
E: the computation consumption of XOR,
L
M: the communication or memory consumption of m
(
b
i
t
),
L
s: the communication or memory consumption of the seed of hash chain,
L
r: the communication or memory consumption of the generated random number,
L
I: the communication or memory consumption of shadows I
i in SRHC-BL,
L
e: the communication or memory consumption of the secret shadows s
i in SRHC-BL.Then, we compare the computation, communication, and storage cost of our scheme SRHC-BL with the current schemes RHC, ERHC, SUHC, and SRHC. The comparison results are shown as follows.RHC is as follows:
Computation:(9)12m2+9mM+2mR.
Communication:(10)2LM+3m×Lr+6m-2.
Storage:(11)2Ls+3Lr+m+6×LM+m.
SUHC is as follows:
Computation:(12)12m2+12m-2·M+mRA+mA.
Communication:(13)6m-1·LM+2m·Lr.
Storage:(14)2Ls+Lr+m+6LM+m.
ERHC is as follows:
Computation:(15)12n2+5n+5m+5log2⁡m+5·M+2m+log2⁡m+1·R+2N.
Communication:(16)2n+m+log2⁡m+1·LM+m+log2⁡m+1·Lr.
Storage:(17)n+3m+log2⁡m+1·LM+m×1+2Lr.
SRHC is as follows:
Computation:(18)12m2+11m-2·M+m·RA′+mA′.
Communication:(19)4m·LM+2m·Lr.
Storage:(20)2Ls+3Lr+3+mLM+m.
SRHC-BL is as follows:
Computation:(21)12n2+7n-2M+2nE+nI+P+C.
Communication:(22)4n-2·LM+2n·LI.
Storage:(23)n+3·LM+n·LI+i·Le+2m.For simplicity, we assumed thatm
≈
n, R
≈
R
A
≈
R
A
′, A
≈
A
′, M
>
N, M
>
C
>
I
>
P, and L
M
≫
L
s
≈
L
r
≈
L
I
>
L
c, so that it is easy to know the performance of our SRHC-BL relative to RHC, ERHC, SUHC, and SRHC. Through comparison, we can draw the following conclusion: the consumption of SRHC-BL in the initialization phase is much less than other schemes, while, in the phase of key distribution and authentication, SRHC-BL’s consumptions of communication and storage are a little more than SRHC’s but much less than RHC’s, ERHC’s, and SUHC’s.


## 5. Related Work

### 5.1. ImprovedμTESLA Protocol

Many hybrid broadcast authentication protocols have been proposed. Reference [14] proposed a broadcast authentication protocol with Bloom Filter compression to mainly reduce error rate of data broadcasting. Reference [15] introduced a multiuser broadcast authentication protocol to synchronously meet the requirements of multiuser. A lightweight secure authentication protocol was proposed in [16], which mainly focuses on the storage performance optimization. Reference [17] is a μTESLA-like scheme based on symmetric keys, but the signature takes a large storage cost. A secure protocol named GPLD (Global Partition, Local Diffusion) was proposed in [18]; this scheme based on the symmetric encryption system and the geographical location information allows the different multicast group to exist in wireless sensor networks, and nodes can also act as the broadcast source and relay. On the basis of [18, 19] a broadcast authentication scheme based on users, which achieves the promising security, scalability, and performance, was proposed. Reference [13] proposes an enhanced broadcast authentication protocol based on multilevel μTESLA, however, whose overhead has not achieved the satisfactory efficiency. Reference [20] put forward a broadcast authentication scheme with the Merkle tree; although it can effectively resist the DoS attacks, the authentication delay seems to be inappropriate for most applications. Taking the tolerance of data loss into account, [21] presents a link-layer packet recovery algorithm which improves the reliability and minimizes the latency.So we can see thatμTESLA protocol and its improved protocols are the mainstream of broadcast authentication protocol research in wireless sensor networks.


### 5.2. Reinitializable Hash Chain

Hash function has the characteristics of one-wayness and high computational efficiency. Therefore, the hash chain mechanism has been widely used into many encryption applications and services. Furthermore, the length of the hash chain is limited, which makes it difficult to meet the requirement of sustainability. And extending the length of the hash chain is difficult because a secure channel established through other encryption mechanisms is needed, and a large overhead is required.To solve this contradiction, researchers have proposed some hash chain schemes. Goyal introduced the reinitializable hash chain (RHC) scheme with the idea that a fire-new RHC will be regenerated safely and undeniably when the old RHC is exhausted. On the basis of RHC, [22] put forward the elegant reinitializable hash chain (ERHC) scheme, which uses the one-way hash function to regenerate the hash chain safely and infinitely instead of using the public key mechanism. However, due to the publication part of S
U to authentication for the next seed of hash chain, it is likely to be susceptible to the chosen plaintext attack. Reference [23] proposed the self-updating hash chain (SUHC) scheme based on the hard core predicate algorithm. The solution of SUHC is that the sender distributes the first chain’s every key value with one bit in the seed of second. In such a way, while the first one is exhausted, the receiver would receive all bits of second chain’s seed. On the basis of [23, 24] the self-renewal hash chain (SRHC) scheme was proposed. The main difference between the above two schemes is the generation method of the random numbers. The security distributions of the seed of SUHC and SRHC rely on the security distribution of k random numbers, where k denotes the length of chain. Furthermore, these two schemes require all the received random numbers to satisfy integrity and inevitability. And then the seed of a new chain can be reconstructed. However, both of them have given up the original fault tolerance of hash chain. Based on SUHC, [25] put forward a novel self-updating hash chain (NSUHC) scheme; afterwards, according to NSUHC, [26] proposed a new self-updating hash chain based on erasure coding (SUHC-EC). In the former scheme, the seed of a new hash chain is transformed from k-dimensional to n-dimensional (k
<
n) and the latter one is transformed from one-dimensional to n-dimensional. Therefore, two schemes select one of the n random values to release without repeating. The new seed can be resumed after k times. These two schemes seem to realize the renewable hash chain, but actually there is no difference from the conventional hash chain. Reference [27] proposed a new self-updating hash chain based on fair exchange idea (SRHC-FEI); this scheme uses one-time signature key to encrypt the first bit of the seed of a new hash chain in transmission when releasing the new hash value each time. It can enhance the security and fairness, but it inevitably increases the system time delay. After analysis, we can see that this scheme is also an enhanced scheme more than a strict hash chain renewable construction scheme.From the analysis of the above typical schemes we can see that they all transform every bit of the new chain’s seed into a random number and make the security of the new seed dependent on the security of distributed random numbers. Besides, they can successfully regenerate the new seed only when they receive all the random numbers correctly. As a result, they all weaken the security and increase the consumptions for reinitialization. On the other hand, NSUHC and SUHC-EC only expand the dimension of the seed of a new hash chain, but compared with RHC and ERHC and so forth, they increase the chance of encountering the man-in-the-middle attack. Above all, from a perspective of application of a hash chain, only RHC, ERHC, SUHC, and SRHC belong to the renewable construction scheme of hash chain.


## 5.1. ImprovedμTESLA Protocol

Many hybrid broadcast authentication protocols have been proposed. Reference [14] proposed a broadcast authentication protocol with Bloom Filter compression to mainly reduce error rate of data broadcasting. Reference [15] introduced a multiuser broadcast authentication protocol to synchronously meet the requirements of multiuser. A lightweight secure authentication protocol was proposed in [16], which mainly focuses on the storage performance optimization. Reference [17] is a μTESLA-like scheme based on symmetric keys, but the signature takes a large storage cost. A secure protocol named GPLD (Global Partition, Local Diffusion) was proposed in [18]; this scheme based on the symmetric encryption system and the geographical location information allows the different multicast group to exist in wireless sensor networks, and nodes can also act as the broadcast source and relay. On the basis of [18, 19] a broadcast authentication scheme based on users, which achieves the promising security, scalability, and performance, was proposed. Reference [13] proposes an enhanced broadcast authentication protocol based on multilevel μTESLA, however, whose overhead has not achieved the satisfactory efficiency. Reference [20] put forward a broadcast authentication scheme with the Merkle tree; although it can effectively resist the DoS attacks, the authentication delay seems to be inappropriate for most applications. Taking the tolerance of data loss into account, [21] presents a link-layer packet recovery algorithm which improves the reliability and minimizes the latency.So we can see thatμTESLA protocol and its improved protocols are the mainstream of broadcast authentication protocol research in wireless sensor networks.


## 5.2. Reinitializable Hash Chain

Hash function has the characteristics of one-wayness and high computational efficiency. Therefore, the hash chain mechanism has been widely used into many encryption applications and services. Furthermore, the length of the hash chain is limited, which makes it difficult to meet the requirement of sustainability. And extending the length of the hash chain is difficult because a secure channel established through other encryption mechanisms is needed, and a large overhead is required.To solve this contradiction, researchers have proposed some hash chain schemes. Goyal introduced the reinitializable hash chain (RHC) scheme with the idea that a fire-new RHC will be regenerated safely and undeniably when the old RHC is exhausted. On the basis of RHC, [22] put forward the elegant reinitializable hash chain (ERHC) scheme, which uses the one-way hash function to regenerate the hash chain safely and infinitely instead of using the public key mechanism. However, due to the publication part of S
U to authentication for the next seed of hash chain, it is likely to be susceptible to the chosen plaintext attack. Reference [23] proposed the self-updating hash chain (SUHC) scheme based on the hard core predicate algorithm. The solution of SUHC is that the sender distributes the first chain’s every key value with one bit in the seed of second. In such a way, while the first one is exhausted, the receiver would receive all bits of second chain’s seed. On the basis of [23, 24] the self-renewal hash chain (SRHC) scheme was proposed. The main difference between the above two schemes is the generation method of the random numbers. The security distributions of the seed of SUHC and SRHC rely on the security distribution of k random numbers, where k denotes the length of chain. Furthermore, these two schemes require all the received random numbers to satisfy integrity and inevitability. And then the seed of a new chain can be reconstructed. However, both of them have given up the original fault tolerance of hash chain. Based on SUHC, [25] put forward a novel self-updating hash chain (NSUHC) scheme; afterwards, according to NSUHC, [26] proposed a new self-updating hash chain based on erasure coding (SUHC-EC). In the former scheme, the seed of a new hash chain is transformed from k-dimensional to n-dimensional (k
<
n) and the latter one is transformed from one-dimensional to n-dimensional. Therefore, two schemes select one of the n random values to release without repeating. The new seed can be resumed after k times. These two schemes seem to realize the renewable hash chain, but actually there is no difference from the conventional hash chain. Reference [27] proposed a new self-updating hash chain based on fair exchange idea (SRHC-FEI); this scheme uses one-time signature key to encrypt the first bit of the seed of a new hash chain in transmission when releasing the new hash value each time. It can enhance the security and fairness, but it inevitably increases the system time delay. After analysis, we can see that this scheme is also an enhanced scheme more than a strict hash chain renewable construction scheme.From the analysis of the above typical schemes we can see that they all transform every bit of the new chain’s seed into a random number and make the security of the new seed dependent on the security of distributed random numbers. Besides, they can successfully regenerate the new seed only when they receive all the random numbers correctly. As a result, they all weaken the security and increase the consumptions for reinitialization. On the other hand, NSUHC and SUHC-EC only expand the dimension of the seed of a new hash chain, but compared with RHC and ERHC and so forth, they increase the chance of encountering the man-in-the-middle attack. Above all, from a perspective of application of a hash chain, only RHC, ERHC, SUHC, and SRHC belong to the renewable construction scheme of hash chain.


## 6. Conclusion

This paper proposes a novel secret key release scheme based on the data flow, which addresses some problems of traditional key release schemes based on the fixed time interval, effectively improves the efficiency of the utilization of keys, prolongs the life cycle of hash chain, and reduces the network communication overhead and computational cost.Moreover, we consider the scenario that when the number of packets using the same key to authenticate is greater than the thresholdN
s
t
r, it may disable some packets to get a timely authentication and thus results in the loss of data. Also, the probability of chosen plaintext attack will be increased. To solve these problems, we introduce the flow threshold mechanism to prevent the attacks and enhance network security as well.After that we put forward a new renewable hash chain based on Benaloh-Leichter SSS (SRHC-BL). The renewable process can be executed infinitely. And we have theoretically proved that SRHC-BL has better performance on integrity, confidentiality, and nonrepudiation by adopting the delay disclosure and one-wayness. In addition, our scheme can also tolerate message loss or fault due to the property of the shadows in Benaloh-Leichter SSS. Furthermore, the dual authentication and transformed secret shadows enable our scheme to have higher security than other schemes. Finally, the analysis of complexity has proved that SRHC-BL has less consumption than those typical schemes.



---

*Source: 9021650-2016-08-09.xml*