An RSA-Like Scheme for Multiuser Broadcast Authentication in Wireless Sensor Networks

Abstract

For network users roaming in a wireless sensor network (WSN), they can broadcast queries to WSNs to obtain the latest sensed data from sensor nodes using their mobile devices. In such a scenario, each sensor node has to verify the validity of every query sent from users. In this paper, RSA-like public key cryptography is employed to design a mechanism for multiuser broadcast authentication in WSNs. Within the proposed scheme, the use of certificates becomes optional. When users broadcast queries to WSNs, each sensor node can verify every query immediately without buffering any one. As a result, the energy cost for verifying a query by a sensor node is very small. Furthermore, our scheme provides enough scalability and security. The quantitative analyses show that our scheme is efficient in terms of storage and computational overheads.

1. Introduction

Wireless sensor networks (WSNs) are widely used in various applications, such as building automation, mobile object tracking, and habitat monitoring [1, 2]. A WSN usually consists of one or more base stations and a large number of sensor nodes. Because the sensor nodes are resource-constrained and usually deployed in hostile environments, they are vulnerable to malicious attacks. Thus, broadcast authentication becomes a critical issue in WSNs, which can prevent adversaries from injecting bogus queries. Traditional schemes [3–8] applied the key pools, space pools of matrix or polynomials to establish the pairwise key between any two neighboring sensor nodes. Although these schemes can establish a secure communication channel, they cannot withstand injecting bogus queries.

Thus, three scenarios are considered in this paper. The first scenario is that users broadcast messages to WSNs using their own mobile device dynamically, and then each sensor node will verify these messages. The second scenario is that once malicious users are revoked by the base station, the action of rekeying will be triggered by the base station. The third scenario is that when new users join WSNs, the base station will take some appropriate actions for these users.

In this paper, an RSA-like scheme is employed to construct a multiuser broadcast authentication mechanism. Although it is usually thought that RSA is expensive for sensor nodes in terms of computational overhead, however, the authors in the work in [9] showed that the cost of the RSA signature verification is not really expensive. Because each sensor node only needs to verify the RSA signature, the computational cost for a sensor node to verify a message is acceptable. As reported in [10], public key cryptography is viable on an Atmel ATmega128 at 8 MHz for resource-constrained sensor nodes. The authors tested and implemented elliptic curve point multiplication and RSA operations on two 8-bit microcontrollers with assembly languages. Elliptic Curve Cryptography (ECC) is more computationally efficient than RSA, but RSA can still be implemented for sensor nodes, such as Crossbow MICA Motes. For example, in the implementation of [10], it requires 0.81 s for 160-bit ECC point multiplication and 0.43 s and 10.99 s for RSA-1024 public key operation and private key operation, respectively. Furthermore, the Chinese Remainder Theorem (CRT) can accelerate RSA private key operations, namely, decryption and signature generation.

Broadcast authentication enables each sensor node to verify the received messages which are originated with the authorized source and were not modified. In our scheme, when a user broadcasts a query message to WSNs, each sensor node only has to verify the signature attached in the message using the public key computed by the base station. At the beginning of network initialization, the base station generates RSA public key and private key for each sensor node and each user, respectively. Once a user is revoked, the base station has to regenerate a new RSA public key for each sensor node. At the same time, other users do not have to change their own private key. So sensor nodes do not have to store a revocation list in their own memory. The main contributions of this paper are described as follows:

• (1)

We propose an RSA-like scheme to secure the multiuser broadcast. Our scheme provides enough security with 1024-bit RSA and great scalability.

(2)

In our scheme, each sensor node does not buffer any message, and it can verify every message immediately. Thus, the impact of DoS attacks can be mitigated.

(3)

Once illegal network users are revoked by the base station, all the current users do not have to obtain new authentication information from the base station. On the other hand, there is no need for each current user to reobtain his/her private key from the base station after he/she has participated in WSN.

(4)

Each sensor node only has to store one network public key, which is 1024 bits. No matter how many network users are there in WSNs, each sensor node can verify these messages. Therefore, our scheme is more efficient in terms of storage overhead as compared with the previous schemes.

(5)

A quantitative energy consumption analysis on computational cost for verifying a message shows that our scheme indeed outperforms the previous schemes.

The rest of this paper is organized as follows. In Section 2, the related work will be introduced. In Section 3, the network and adversary models used in this paper are presented. Subsequently, RSA cryptosystem and the concept of RSA master-key will be described in Section 3. In Section 4, the proposed multiuser broadcast authentication scheme is presented. Section 5 is the discussions of our proposed scheme. Section 6 is the performance evaluation in terms of communication, storage, and computational overheads. The conclusion is made in Section 6.

2. Related Work

In order to prevent adversaries from injecting bogus queries, the authors in the work in [11] first proposed a scheme, called μTESLA, to overcome this problem. They employed a one-way hash function to generate a key chain for the authentication of broadcast messages. However, a source requires maintaining a long chain of keys for the long-term uses. In addition, μTESLA suffers from serious DoS attacks. Each sensor node has to buffer all received messages within a time interval, and then it can verify these messages by using the delayed disclosure key broadcasted by the base station at the next time interval. The base station and sensor nodes are assumed to be loosely time synchronized.

Furthermore, the authors in the work in [12] proposed a novel protocol called BABRA to address the problem of broadcast authentication in WSNs. Unlike μTESLA, BABRA can support broadcast for infinite rounds. At the same time, it eliminates the requirement of key chain. Nevertheless, BABRA also suffers from serious DoS attacks, since each sensor node has to buffer all messages before the corresponding key is disclosed.

In [13], the authors proposed a broadcast source authentication mechanism based on multiple MACs (Message Authentication Codes). The scheme requires sensor nodes to have different overlapping set of keys. When the source wants to broadcast a query, it uses its keys to compute multiple MACs and appends them to the message. Then, the recipient can verify the message based on the MACs by using the common keys shared with the source. In comparison with the above schemes, each recipient could verify a message immediately. Therefore, the impact of DoS attacks can be mitigated. However, the key predistribution under a hierarchical structure results in scalability issues. The authors in the work in [14, 15] proposed broadcast authentication schemes using one-time signature. As compared with the above schemes, each sensor node can verify a query immediately without buffering others. However, the number of signatures is limited when a lot of queries are signed by the source.

The authors in the work in [16] first proposed a protocol for multiuser broadcast authentication, in which any unauthorized user cannot broadcast queries to a WSN arbitrarily. Each authorized user may be equipped with a powerful mobile device, and then he/she can broadcast queries to WSNs for the purpose of obtaining the latest sensed data from sensor nodes in WSNs. Whenever a WSN processes a query, sensor nodes are able to verify the query. However, the user's public key certificate incurs additional communication and computational overheads.

In [17–19], the main idea of these schemes is to preload each sensor node/network user with some secret information. After that, sensor nodes can compute session keys shared between them and users. Hence, the authenticity of users can be verified through these session keys. All the above schemes are based on challenge-response protocols. Although the above schemes have been proposed for user authentication, most of them do not provide adequate efficiency. By contrast, some schemes in [20–22] focus on the mechanism, in which each sensor node can verify every query directly without challenging any nonce. These schemes provide adequate efficiency for multiuser broadcast authentication. However, it is still difficult to deal with the resource-constrained problem and sensor nodes compromise attack. An efficient scheme is proposed to address the problems without incurring much overhead.

The authors in the work in [16] proposed the first solution to the problem called authenticated querying. They utilized Elliptic Curve Cryptography (ECC) to construct the user authentication scheme, which only considered the situation that a user's query involves a single sensor node. Besides, this scheme incurs additional communication overhead because the user's certificate needs to be transmitted. Furthermore, each sensor node has to verify the user's certificate and signature. Obviously, it also incurs additional computational overhead. A fully symmetric key based solution was proposed for authenticated querying [17]. The authors used a bivariate polynomial to establish shared keys between the user and the sensor nodes that should process the user's query. Then, these sensor nodes can verify the authenticity of the user by using the shared keys between them and the user. The scheme is effectively tolerant of the sensor node compromise attack, but it still incurs additional communication overhead because the collection of MACs needs to be transmitted. In particular, when there are a large number of sensor nodes that should process the user's query, the collection of MACs will be big.

The authors in the work in [19] proposed a distributed user access control scheme, which includes local authentication and remote authentication. Unfortunately, this scheme incurs significant communication overhead, especially when the user's access control list is heavy. The reason is that the access control list needs to be transmitted. In [18], the authors proposed a user authentication scheme with the self-certified key (SCK) cryptosystem. The main idea is to establish pairwise keys between the user and his/her local sensor nodes. Then, these sensor nodes can verify the authenticity of the user. Because each sensor node is preloaded with a public/private key pair, the scheme suffers from serious sensor node compromise attack. An adversary may utilize the keying material of a compromised sensor node to impersonate a legal user to destroy the WSNs.

In [22], the authors initially proposed two basic schemes called CAS and DAS. In CAS, each user is equipped with a public/private key pair and his/her public key certificate signed by the base station, and then he/she signs every broadcast message with his/her private key. Upon receiving the message, each sensor node can verify the public key certificate of the user by using the public key of the base station. Finally, each sensor node can verify the message the user broadcasts in the WSNs. However, the certificate has to be transmitted and verified by each sensor node. CAS introduces additional communication and computational overheads. In DAS, each sensor node has to store all the users' ID information and their corresponding public keys. However, the storage of DAS is neither efficient nor scalable. This scheme is not suitable for storage-constrained sensor nodes when there are a large number of users.

Subsequently, the authors proposed two advanced schemes called BAS and HAS. In BAS, each sensor node is required to store a Bloom filter and k hash functions. Upon receiving a message, each sensor node can check whether the user's ID and his/her corresponding public key are authentic by using the Bloom filter and k hash functions. However, the probability of a false positive ( $f_{\mathrm{r}\mathrm{e}\mathrm{q}}$ ) may happen even though it is very small. It may suggest that an illegal user is authentic. Besides, BAS supports up to 1,000 users when $f_{\mathrm{r}\mathrm{e}\mathrm{q}}=\mathrm{2.03}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{17}}$ for a Bloom filter of 9.8 KB. It incurs a large amount of storage overhead, and the maximum supported number of users is limited by the storage limit and $f_{\mathrm{r}\mathrm{e}\mathrm{q}}$ . Therefore, an improved scheme called HAS was proposed to support more users. To achieve this goal, HAS utilizes the Bloom filter and Merkle hash tree. Nevertheless, it still incurs a large amount of storage overhead and lacks scalability.

The authors in the work in [21] proposed three broadcast authentication schemes. The first scheme is CAS as mentioned before, and the second scheme is based on Merkle hash tree. The base station first constructs a Merkel hash tree, in which each leaf node contains the hash value of a user's ID and his/her corresponding public key. Then, each sensor node has to store the value of the final root node of the hash tree. At the same time, each user has to obtain his/her auxiliary authentication information (AAI). When a user broadcasts a message to the WSNs, he/she signs the message and appends his/her AAI to the message. Upon receiving this message, each sensor node can verify the user's public key by using AAI. If the final hash value is equal to the value of the final root node, each sensor node can verify the user's public key. The Merkle hash tree based scheme does not require the users' public key certificate to be transmitted. In addition, this scheme can be improved by increasing the number of stored hash values in each sensor node. Thus, the size of AAI can be reduced. However, once a user is revoked by the base station, each current user has to obtain his/her updated AAI from the base station. It is impractical for the current users. The third scheme is an ID-based authentication scheme. The concept of ID-based cryptography originated from [23]. A user's ID is just like the user's public key. In this scheme, the user's public key is $U_{\mathrm{I}\mathrm{D}}\parallel v_i$ , where $U_{\mathrm{I}\mathrm{D}}$ is the user's ID and $v_i$ is the current time interval. Each sensor node can verify the message broadcasted by the user using $U_{\mathrm{I}\mathrm{D}}\parallel v_i$ and the network public key. However, this scheme requires each sensor node to perform two expensive pairing operations. In addition, each user has to obtain a new private key from the base station at the beginning of each time interval. Once some users are revoked, each sensor node needs to store a revocation list only within the current time interval.

An ID-based signature scheme called BNN-IBS [24] is based on Schnorr signature [25], and the authors in the work in [20] proposed a variant of BNN-IBS called vBNN-IBS with a smaller signature size. The proposed scheme called IMBAS [20] is also used to secure the multiuser broadcast. When a user wants to broadcast a message to WSNs, he/she signs the message using vBNN-IBS signature. The base station can also broadcast a message to WSNs with a smaller message size. Upon receiving a message broadcasted by the user (or the base station), each sensor node can verify it immediately. Furthermore, each sensor node also has to store the IDs of the revoked users as a revocation list infinitely when the number of revoked users increases unceasingly. As a result, it can be found that the public key cryptography is easier to be used for multiuser broadcast authentication than the symmetric key cryptography.

In [20–22], the authors used Elliptic Curve Cryptography (ECC) based schemes to secure multiuser broadcast authentication. $E/F_p$ used in [20–22] denotes the elliptic curve over the finite field $F_p$ , where p is a large odd prime. The elliptic curve $E/F_p$ is defined by the equation $y^{\mathrm{2}}=x^{\mathrm{3}}+ax+b$ , where $a,b\in F_q$ . $G_{\mathrm{1}}$ is a q-order subgroup of the additive group of points of $E/F_p$ [21].

3. Preliminaries

First, the concepts of the proposed network model and adversary model are introduced. Then, the review of RSA public key cryptosystem and the concept of RSA master-key are presented in the section.

3.1. The Network Model

In this model, the sensor network consists of a base station and a large number of sensor nodes. The base station is assumed to be powerful, while sensor nodes are resource-constrained. Furthermore, there are a large number of network users. These users who roam in WSNs can use their mobile devices to broadcast queries to WSNs for the purpose of obtaining the latest sensed data. The mobile devices of the users are more powerful than resource-constrained sensor nodes in terms of computation, communication, storage, and energy abilities. The number of network users may be dynamic. In this paper, the WSNs time is assumed to be loosely synchronized.

3.2. The Adversary Model

We assume that the base station is always trustworthy, but sensor nodes may be compromised by an adversary. Therefore, there may be some malicious sensor nodes in the WSNs. The adversary is able to compromise or capture not only sensor nodes but also users' mobile devices, and then all the secret information (e.g., keying material or secret data) held by them is known by the adversary. In addition, the adversary may impersonate these captured users to broadcast bogus messages to WSNs. So these users of WSNs have to be revoked by the base station to prevent them from destroying WSNs. Furthermore, the adversary can flood bogus messages into WSNs to exhaust the precious energy of sensor nodes. Note that the adversary can also eavesdrop and resend the messages.

3.3. RSA Public Key Cryptosystem

We give an introduction to RSA public key cryptosystem. In RSA cryptosystem, each participant holds a public/private key pair, which is generated by a certificate authority (CA). The steps of generating the public/private key pair are described as follows:

•  

(1) Two large primes p and q are randomly chosen, and then $N=p\times q$ can be computed.

 

(2) To choose a parameter e, (1) have to be satisfied:

$$\begin{array}{cc}& GCD\left(ø\left(N\right),e\right)=\mathrm{1},\\ \mathrm{1}<e<ø\left(N\right),\end{array}$$

(1)

 

where $ø\left(N\right)=\left(p-1\right)\left(q-1\right)$ is Euler's totient function of N. Consequently, a parameter d can be computed through Extended Euclidean algorithm, such that

$$\begin{array}{cc}& e\times d\equiv \mathrm{1}\mathrm{mod}ø\left(N\right).\end{array}$$

(2)

 

(3) Finally, $\left(N,e\right)$ is the public key and d is the private key.

Now, assume that A wants to send a message M to B. If A wants to prove the confidentiality of M, he/she can use B's public key $(e_B,N_B)$ to encrypt the message M. Then, A sends the encrypted message C to B, where $C=M^{e_B}\mathrm{mod}{N}_B$ . Upon receiving the encrypted message C, B can use his/her private key $d_B$ to recover the message M by computing

$$\begin{array}{cc}& M=C^{d_B}\mathrm{mod}{N}_B.\end{array}$$

(3)

On the other hand, if A wants to prove the origin and integrity of M, he/she can use his/her private key $d_A$ to sign the message M. Then, A sends the message M with the signature S to B, where $S=M^{d_A}\mathrm{mod}{N}_A$ . Upon receiving the message M and the signature S, B can use A's public key $(e_A,N_A)$ to verify the signature by computing

$$\begin{array}{cc}& M^{\prime }=S^{e_A}\mathrm{mod}{N}_A.\end{array}$$

(4)

And then B checks whether $M=M^{\prime }$ or not. The signature is accepted if so and rejected otherwise.

3.4. RSA Master-Key

The authors in the work in [26] proposed an RSA master-key scheme, which is built on RSA cryptosystem. Suppose that there are n entities $f_{\mathrm{1}},f_{\mathrm{2}},\dots ,f_n$ :

• (1)

CA randomly chooses large primes $p_{\mathrm{1}},q_{\mathrm{1}},p_{\mathrm{2}},q_{\mathrm{2}},\dots ,p_n,q_n$ and a positive integer $e_H$ which is relatively prime to L, where $L=LCM\left\{L_{\mathrm{1}},L_{\mathrm{2}},\dots ,L_n\right\}$ and $L_i=ø(p_i\times q_i)$ for $i=\mathrm{1,2},\dots ,n$ .

(2)

Let $m_i=p_i\times q_i$ for $i=\mathrm{1,2},\dots ,n$ . CA computes the corresponding $d_H$ such that $e_H\times d_H\equiv \mathrm{1}$ ( $\mathrm{m}\mathrm{o}\mathrm{d}L$ ). Then, let $e_i\equiv e_H$ ( $\mathrm{m}\mathrm{o}\mathrm{d}{L}_i$ ) and $d_i\equiv d_H$ ( $\mathrm{m}\mathrm{o}\mathrm{d}{L}_i$ ) for each i.

(3)

For $i=\mathrm{1,2},\dots ,n$ , let ( $m_i,e_i,d_i$ ) be defined as the ith entity's RSA system with elementary encryption key $e_i$ and decryption key $d_i$ . The sequence ( $e_H,d_H,p_{\mathrm{1}},q_{\mathrm{1}},p_{\mathrm{2}},q_{\mathrm{2}},\dots ,p_n,q_n$ ) is called the master-key of the system. This master-key is only known by CA.

(4)

Therefore, each $f_i$ can be encrypted into $\widehat{f_i}$ , where $\widehat{f_i}\equiv f_i^{e_i}$ ( $\mathrm{m}\mathrm{o}\mathrm{d}{m}_i$ ). It can also be $f_i\equiv {\widehat{f_i}}^{d_i}$ ( $\mathrm{m}\mathrm{o}\mathrm{d}{m}_i$ ). In fact, we have $f_i\equiv {\widehat{f_i}}^{d_H}$ ( $\mathrm{m}\mathrm{o}\mathrm{d}{m}_i$ ) for all i due to the equation $e_H\times d_H\equiv \mathrm{1}$ ( $\mathrm{m}\mathrm{o}\mathrm{d}L$ ).

4. The Proposed Multiuser Broadcast Authentication Scheme

In this section, a scheme for multiuser broadcast authentication, which is based on RSA cryptosystem and the master-key scheme [26], is presented. The detailed steps of our scheme are described in the following sections.

4.1. Our Scheme

We assume that there are m network users in WSNs, and the base station is the highest authority. The task of the base station is to generate a private key for each user and assign a public key for each sensor node. We use the RSA-like scheme to secure the multiuser broadcast. When the event which a user joins or leaves happens, our scheme can cope with the situation. Furthermore, once a user is compromised, the base station will take an appropriate action to cope with such a situation. The steps of our scheme are described as follows.

4.1.1. The Setup Phase

First, the base station randomly chooses $\mathrm{2}m+\mathrm{2}$ distinct large primes $p_i,q_i$ , ( $\mathrm{0}\le i\le m$ ), and it also chooses two distinct large primes $p_{\mathrm{b}\mathrm{s}},q_{\mathrm{b}\mathrm{s}}$ for itself. Second, the base station computes $N_{\mathrm{0}}=p_{\mathrm{0}}\times q_{\mathrm{0}}$ for each sensor node, $N_{\mathrm{b}\mathrm{s}}=p_{\mathrm{b}\mathrm{s}}\times q_{\mathrm{b}\mathrm{s}}$ for itself, and $N_{\mathrm{1}}=p_{\mathrm{1}}\times q_{\mathrm{1}}$ , $N_{\mathrm{2}}=p_{\mathrm{2}}\times q_{\mathrm{2}},\dots ,N_m=p_m\times q_m$ for users ${\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_{\mathrm{1}},{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_{\mathrm{2}},\dots ,{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_m$ . Note that $\mathrm{2}m+\mathrm{4}$ distinct large primes are only known by the base station, but $N_{\mathrm{1}},N_{\mathrm{2}},\dots ,N_m$ and $N_{\mathrm{b}\mathrm{s}}$ are public.

4.1.2. The Key Generation Phase

The base station computes the least common multiple $L_{\mathrm{0}}$ of $m+\mathrm{2}$ integers $ø(N_{\mathrm{0}}),ø(N_{\mathrm{1}}),\dots ,ø(N_m),ø(N_{\mathrm{b}\mathrm{s}})$ , such that

$$\begin{array}{cc}& L_{\mathrm{0}}=LCM\left\{ø\left(N_{\mathrm{0}}\right),ø\left(N_{\mathrm{1}}\right),\dots ,ø\left(N_m\right),ø\left(N_{\mathrm{b}\mathrm{s}}\right)\right\},\end{array}$$

(5)

where $ø(N_i)$ is Euler's totient function of $N_i$ and $ø(N_i)=(p_i-\mathrm{1})\times (q_i-\mathrm{1})$ . The base station chooses a parameter $d_{\mathrm{0}}$ which is relatively prime to $L_{\mathrm{0}}$ ( $\mathrm{1}<d_{\mathrm{0}}<L_{\mathrm{0}}$ ). Then, it can compute $e_{\mathrm{0}}$ through Extended Euclidean algorithm, such that

$$\begin{array}{cc}& d_{\mathrm{0}}\times e_{\mathrm{0}}\equiv \mathrm{1}\mathrm{mod}{L}_{\mathrm{0}}.\end{array}$$

(6)

Note that the bit-length of $e_{\mathrm{0}}$ can be first chosen as short as possible because each sensor node uses $e_{\mathrm{0}}$ to verify signatures. The notations $d_{\mathrm{0}}$ and $e_{\mathrm{0}}$ used here are opposite to the common notations of RSA. The reason is that we use $d_i$ to sign messages and $e_{\mathrm{0}}$ to verify signatures. After generating $d_{\mathrm{0}}$ , the base station uses it to generate the private keys $d_{\mathrm{1}},d_{\mathrm{2}},\dots ,d_m$ for users ${\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_{\mathrm{1}},{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_{\mathrm{2}},\dots ,{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_m$ and $d_{\mathrm{b}\mathrm{s}}$ for itself by computing

$$\begin{array}{cc}& d_i=d_{\mathrm{0}}\mathrm{mod}ø\left(N_i\right),\\ d_{\mathrm{b}\mathrm{s}}=d_{\mathrm{0}}\mathrm{mod}ø\left(N_{\mathrm{b}\mathrm{s}}\right),\end{array}$$

(7)

where $i=\mathrm{1,2},\dots ,m$ .

4.1.3. The Key Assignment Phase

After finishing the above key generation, the base station can preload/broadcast each sensor node with $e_{\mathrm{0}}$ prior to the WSNs deployment or during WSNs operation time. This method is similar to the method used in [21]. For users ${\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_{\mathrm{1}},{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_{\mathrm{2}},\dots ,{\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_m$ , the base station delivers $(d_{\mathrm{1}},N_{\mathrm{1}}),(d_{\mathrm{2}},N_{\mathrm{2}}),\dots ,(d_m,N_m)$ to them through a secure channel. The base station keeps its private key $d_{\mathrm{b}\mathrm{s}}$ . Hence, each user has two parameters $(d_i,N_i)$ , where $d_i$ must be kept secret and public $N_i$ can be used to represent his/her ID. The two parameters $(d_{\mathrm{b}\mathrm{s}},N_{\mathrm{b}\mathrm{s}})$ have the same meaning as above for the base station.

4.1.4. Multiuser Broadcast Authentication

Assume that a user $N_i$ wants to broadcast a message M to the WSNs; he/she uses his/her private key $d_i$ to sign M and broadcasts the following message:

$$\begin{array}{cc}& \left\{M,\mathrm{T}\mathrm{S},N_i,\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}\right\},\end{array}$$

(8)

where $\mathrm{T}\mathrm{S}$ is the timestamp and $\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}=h{\left(M,\mathrm{T}\mathrm{S},N_i\right)}^{d_i}\mathrm{mod}{N}_i$ .   $h(\ast )$ is a one-way hash function which maps arbitrary inputs to fixed length outputs. After receiving the message, a sensor node first checks whether $\mathrm{T}\mathrm{S}$ is fresh. If so, the sensor node will verify the signature $\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}$ by computing

$$\begin{array}{cc}& h\left(M,\mathrm{T}\mathrm{S},N_i\right)={\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}}^{e_{\mathrm{0}}}\mathrm{mod}{N}_i,\end{array}$$

(9)

where $e_{\mathrm{0}}$ is the public key generated by the base station. If the above equation holds, the signature will be accepted. Otherwise, it will be rejected. For the sake of simplicity, we refer to $h(M,\mathrm{T}\mathrm{S},N_i)$ as P. Because $L_o$ is a multiple of $ø(N_i)$ , we can show that

$$\begin{array}{cc}& e_{\mathrm{0}}\times d_i\mathrm{mod}{L}_{\mathrm{0}}=e_{\mathrm{0}}\times \left(d_{\mathrm{0}}\mathrm{mod}ø\left(N_i\right)\right)\mathrm{mod}{L}_{\mathrm{0}}=e_{\mathrm{0}}\times d_{\mathrm{0}}\mathrm{mod}ø\left(N_i\right)=\mathrm{1}.\end{array}$$

(10)

Therefore, $e_{\mathrm{0}}\times d_i=\mathrm{1}+t\times ø(N_i)$ , where $t\in N$ . According to Euler's Theorem, $P^{ø(N_i)}\mathrm{mod}{N}_i=\mathrm{1}$ , we can show that the above equation is correct as the following equation:

$$\begin{array}{cc}& {\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}}^{e_{\mathrm{0}}}\mathrm{mod}{N}_i={\left(P^{d_i}\mathrm{mod}{N}_i\right)}^{e_{\mathrm{0}}}\mathrm{mod}{N}_i\\ =P^{d_i\times e_{\mathrm{0}}}\mathrm{mod}{N}_i\\ =P^{\mathrm{1}+t\times ø\left(N_i\right)}\mathrm{mod}{N}_i,\hspace{1em}t\in N\\ =P\times P^{t\times ø\left(N_i\right)}\mathrm{mod}{N}_i\\ =P.\end{array}$$

(11)

The structure can be described according to Figure 1. The relation between users and sensor nodes belongs to a two-layer structure. Every sensor node can verify the signatures signed by users. Besides, the messages broadcasted by the base station can still be verified by every sensor node using the same manner, so we do not describe it again.

Figure 1

The two-layer structure.

4.2. User Revocation

In our scheme, once a user is revoked, the base station has to regenerate a corresponding public key $e_{\mathrm{0}}^{\prime }$ for sensor nodes. Suppose that a user ${\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_c$ is compromised, and then the base station takes the steps as follows.

4.2.1. The LCM Regeneration

The base station computes the least common multiple $L_{\mathrm{0}}^{\prime }$ of $m+\mathrm{1}$ integers $ø(N_{\mathrm{0}}),ø(N_{\mathrm{1}}),\dots ,ø(N_m),ø(N_{\mathrm{b}\mathrm{s}})$ , which do not include $ø(N_c)$ , such that $L_{\mathrm{0}}^{\prime }=LCM(ø(N_{\mathrm{0}}),ø(N_{\mathrm{1}}),\dots ,ø(N_m),ø(N_{\mathrm{b}\mathrm{s}}))$ .

4.2.2. The Public Key Regeneration

To update $e_{\mathrm{0}}$ with $e_{\mathrm{0}}^{\prime }$ , the base station uses the equation $d_{\mathrm{0}}\times e_{\mathrm{0}}^{\prime }\equiv \mathrm{1}\mathrm{mod}{L}_{\mathrm{0}}^{\prime }$ to regenerate $e_{\mathrm{0}}^{\prime }$ . Note that $d_{\mathrm{0}}$ is unchanging. The reason is that $d_{\mathrm{0}}$ is relatively prime to $L_{\mathrm{0}}$ . Once $L_{\mathrm{0}}$ is changed into $L_{\mathrm{0}}^{\prime }$ , $d_{\mathrm{0}}$ is still relatively prime to $L_{\mathrm{0}}^{\prime }$ .

4.2.3. The Public Key Broadcast

After regenerating $e_{\mathrm{0}}^{\prime }$ , the base station has to broadcast $e_{\mathrm{0}}^{\prime }$ to WSNs. First, $e_{\mathrm{0}}^{\prime }$ is signed by the base station with the base station's private key $d_{\mathrm{b}\mathrm{s}}$ for the purpose of proving its authenticity. Second, the base station broadcasts $e_{\mathrm{0}}^{\prime }$ with its signature, $\mathrm{T}\mathrm{S}$ , and $N_{\mathrm{b}\mathrm{s}}$ to WSNs. Third, upon the receipt of this message, a sensor node can use the public key $e_{\mathrm{0}}$ to verify the authenticity of $e_{\mathrm{0}}^{\prime }$ . Finally, the sensor node updates $e_{\mathrm{0}}$ with $e_{\mathrm{0}}^{\prime }$ if the signature verification succeeds. Note that $d_{\mathrm{0}}$ is unchanging, so the values $d_{\mathrm{1}},d_{\mathrm{2}},\dots ,d_m$ of legal users are still unchanging, too. Suppose that an adversary forges the message broadcasted by the base station; this attack will be detected by sensor nodes because the private key $d_{\mathrm{b}\mathrm{s}}$ is only known by the base station.

4.3. User Join

When a new user wants to join WSN, the steps are similar to the process of user revocation. Once a new user ${\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_{m+\mathrm{1}}$ wants to join WSN, the base station chooses two distinct large primes $p_{m+\mathrm{1}}$ and $q_{m+\mathrm{1}}$ and computes $N_{m+\mathrm{1}}=p_{m+\mathrm{1}}\times q_{m+\mathrm{1}}$ . Then, $L_{\mathrm{0}}$ can be recomputed by (5), and $d_{m+\mathrm{1}}=d_{\mathrm{0}}\mathrm{mod}ø(N_{m+\mathrm{1}})$ . Finally, the base station delivers $(d_{m+\mathrm{1}},N_{m+\mathrm{1}})$ to ${\mathrm{U}\mathrm{s}\mathrm{e}\mathrm{r}}_{m+\mathrm{1}}$ through a secure channel.

5. Discussion

In this section, the scheme in terms of security, DoS attacks, and scalability is analyzed.

(1) The Problem of Factoring $N_i$ . The security of our scheme is based on the difficulty of factoring $N_i$ into $p_i$ and $q_i$ . Suppose an adversary knows $N_{\mathrm{1}},N_{\mathrm{2}},\dots ,N_m$ , but he/she cannot compute $L_{\mathrm{0}}$ such that $L_{\mathrm{0}}=LCM(ø(N_{\mathrm{0}}),ø(N_{\mathrm{1}}),\dots ,ø(N_m))$ . The adversary cannot obtain $d_{\mathrm{0}}$ from the equation $d_{\mathrm{0}}\times e_{\mathrm{0}}\equiv \mathrm{1}\mathrm{mod}{L}_{\mathrm{0}}$ and use $d_{\mathrm{0}}$ to compute $d_i$ from the equation $d_i=d_{\mathrm{0}}\mathrm{mod}ø\left(N_i\right)$ . Hence, we believe that it is extremely difficult to obtain the private key $d_i$ of user $N_i$ .

(2) The Problem of Preventing the Unauthorized User. When an adversary impersonates a legal user $N_i$ to sign a message M with the key $d_c$ , sensor nodes will fail to verify the signature attached in the message. We show the result as the following equation:

$$\begin{array}{cc}& {\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}}^{e_{\mathrm{0}}}\mathrm{mod}{N}_i={\left(P^{d_c}\mathrm{mod}{N}_i\right)}^{e_{\mathrm{0}}}\mathrm{mod}{N}_i=P^{d_c\times e_{\mathrm{0}}}\mathrm{mod}{N}_i=P^{d_c\times e_{\mathrm{0}}\mathrm{mod}ø\left(N_i\right)}\mathrm{mod}{N}_i\ne P,\end{array}$$

(12)

where $P=h(M,\mathrm{T}\mathrm{S},N_i)$ . Because $d_c\ne d_{\mathrm{0}}\mathrm{mod}ø\left(N_i\right)$ , the signature verification fails. Therefore, the adversary cannot impersonate any legal user to inject bogus messages into WSNs successfully. Furthermore, the timestamp used in the message can also prevent the replay attack.

(3) Denial of Service (DoS) Attacks. According to [21, 27], μTESLA suffers from serious DoS attacks because each sensor node has to buffer all the messages received within one time interval. This problem can be mitigated by the immediate verification of messages. In our scheme, each sensor node can verify messages sent by legal or illegal users immediately, so our scheme can mitigate the impact of DoS attacks. If an adversary wants to broadcast forged messages to WSNs, this attack will be detected by the sensor nodes. And then they may notify the base station of such a situation.

(4) Scalability. When old sensor nodes exhaust their energy or the sensing region of a WSN has to be enlarged, new sensor nodes have to be deployed. Our scheme can deal with this problem by preloading these sensor nodes with the network public key $e_{\mathrm{0}}$ . If a new user wants to join WSNs, the base station will generate two distinct large primes $p_{\mathrm{n}\mathrm{e}\mathrm{w}}$ and $q_{\mathrm{n}\mathrm{e}\mathrm{w}}$ for him/her. Subsequently, the new user's ID $N_{\mathrm{n}\mathrm{e}\mathrm{w}}=p_{\mathrm{n}\mathrm{e}\mathrm{w}}\times q_{\mathrm{n}\mathrm{e}\mathrm{w}}$ is computed by the base station. At the same time, the base station has to regenerate the new network public key $e_{\mathrm{0}}^{\prime }$ . Then, it broadcasts $e_{\mathrm{0}}^{\prime }$ and its signature to the WSNs. Users can join WSNs without much overhead.

6. Performance Evaluations

In this section, the performance of our scheme in terms of communication, storage, and computational overheads is evaluated. Moreover, the scheme is compared with the previous schemes that were proposed for multiuser broadcast authentication.

6.1. Communication Overhead

In this section, our scheme and the previous schemes in terms of the communication overhead are evaluated. In [20–22], the authors used Elliptic Curve Cryptography (ECC) based schemes to secure multiuser broadcast authentication. To provide the same level of security strength as 1024-bit RSA, ECC requires p of 160 bits, if $G_{\mathrm{2}}$ is a q-order subgroup of the multiplicative group of the finite field $F_{p^{\mathrm{2}}}^{\ast }$ [28].

Like the assumptions used in [21], $\left|p\right|$ and $\left|q\right|$ are assumed to be 512 bits and 160 bits, respectively. And the embedded degree of $E/F_p$ is equal to 2. According to [21], suppose that a point is over $E/F_p$ , and only one of its X and Y coordinates needs to be transmitted because the other can be easily derived using the curve equation. We do not take this computational cost into account.

In this paper, 1024-bit RSA are applied to compare our scheme with the previous schemes. We recall that our broadcast message includes a user's ID $N_i$ , a message M, a timestamp $\mathrm{T}\mathrm{S}$ , and the signature attached in the message. We assume that the message M is 20 bytes, the timestamp $\mathrm{T}\mathrm{S}$ is 2 bytes, the user's ID is 2 bytes, and a one-way hash function with 20 bytes' outputs is used. In our scheme, both $N_i$ and the signature are 128 bytes with 1024-bit RSA.

In the remaining part of this paper, we refer to the certificate-based, Merkle hash tree based, and ID-based authentication schemes [21] as CAS, MAS, and IAS, respectively. The parameter m denotes the total number of users.

In CAS, a broadcast message includes a message M, a timestamp $\mathrm{T}\mathrm{S}$ , the signature (40 bytes) attached in the message, and the user's certificate (at least 86 bytes [9]) if Elliptic Curve Digital Signature Algorithm (ECDSA) is used. Hence, the total message size of CAS is 148 bytes. Similarly, the message sizes of MAS and IAS can also be evaluated by using the above parameters.

In HAS [22], the broadcast message includes a part message $M_{\mathrm{2}}$ ( $\left|M_{\mathrm{2}}\right|\ge \mathrm{14}$ bytes), two values over the finite field $Z_q$ , the public key of the user, and an AAI. We set $\left|M_{\mathrm{1}}\right|=\mathrm{10}$ with the saving of up to 10 bytes. Then, the resulting message size of HAS is $\left(\mathrm{74}+\mathrm{20}\times {\log }_{\mathrm{2}}m\right)/\mathrm{1000}$ bytes (supporting up to 1000 users and the probability of a false positive $f_{\mathrm{r}\mathrm{e}\mathrm{q}}=\mathrm{2.03}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{17}}$ ).

In IMBAS [20], the message broadcasted by a user (situation (1)) includes a message M, a timestamp $\mathrm{T}\mathrm{S}$ , a user's ID, one point of $E/F_p$ , and two values over the finite field $Z_q$ . Hence, the resulting message size is 84 bytes. If the message is broadcasted by the base station (situation (2)), it will include a part message $M_{\mathrm{2}}$ ( $\left|M_{\mathrm{2}}\right|\ge \mathrm{14}$ bytes) and two values over the finite field $Z_q$ . Therefore, the message size is 54 bytes (assuming that $\left|M_{\mathrm{1}}\right|=\mathrm{10}$ bytes).

Table 1 shows the comparisons of the different schemes in terms of message size. Furthermore, Figure 2 shows the evaluation results of the impact of the total number of network users on message size. When the number of network users varies from $\mathrm{0}$ to $\mathrm{10,000}$ , the message sizes of MAS and HAS increase with the number of network users. Instead, the message sizes of the other schemes are still unchanging.

Table 1

Comparisons of communication overhead for the related schemes.

Schemes	Message size
CAS [21]	148 bytes
MAS [21]	$\mathrm{84}+\mathrm{20}\times {\log }_{2}m$ bytes
IAS [21]	108 bytes
HAS [22]	$(\mathrm{74}+\mathrm{20}\times {\log }_{2}m)/\mathrm{1000}$ bytes
IMBAS [20]	84 bytes (1) 54 bytes (2)
Our scheme	278 bytes

Figure 2

Message size versus the total number of network users.

In addition, we quantify the performance on message broadcast for the six schemes. We use the MICA2DOT mote which is a popular platform for WSNs. The MICA2DOT mote is equipped with the Atmel ATmega128L 8-bit microcontroller at 4 MHz and the Chipcon CC1000 low-power wireless transceiver [9]. As reported in [9], the energy consumption of MICA2DOT mote in active and power-down modes is 13.8 and 0.0075 mW, respectively. Furthermore, the MICA2DOT mote consumes 59.2 and 28.6 μJ to transmit and receive one byte, respectively.

In our scheme, the broadcasting message is $\left\{M,\mathrm{T}\mathrm{S},N_i,\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}\right\}$ , and the size is 20 bytes (message M) + 2 bytes (timestamp $\mathrm{T}\mathrm{S}$ ) + 128 bytes ( $N_i$ ) + 128 bytes ( $\mathrm{S}\mathrm{i}\mathrm{g}\mathrm{n}$ ) = 278 bytes. The payload for each packet is 32 bytes, since we require 9 packets to transmit the broadcasting message. And each packet requires a 9 bytes' header, ensuing 8 bytes' preamble, which consists of source, destination, length, packet ID, CRC, and control bytes [9]. Therefore, it requires transmitting 441 bytes ( $\left(\mathrm{32}+\mathrm{9}+\mathrm{8}\right)\hspace{0.17em}\hspace{0.17em}\mathrm{b}\mathrm{y}\mathrm{t}\mathrm{e}\mathrm{s}\times \mathrm{9}=\mathrm{441}$ bytes). In addition, energy consumption on transmitting and receiving a broadcast message of our scheme is 441 × 59.2 μJ = 26.11 and 441 × 28.6 μJ = 12.61 mJ, respectively. To estimate the energy consumption of broadcasting a message to the entire network, each sensor node has to retransmit once and receive v times the same message, where v is the number of neighbors for a sensor node. Eventually, the total energy consumption of our scheme is $V\times (\mathrm{26.11}+v\times \mathrm{12.61})$ mJ, where V is the total number of sensor nodes. Similarly, the energy consumption of CAS, MAS, IAS, and IMBAS schemes on message broadcast can also be estimated. In order to have a consistent comparison environment, the parameters are chosen as the same as [21]. Figure 3 shows energy consumption of the schemes on message broadcast, where $v=\mathrm{20}$ , p is the probability of the user broadcast, the probability of the base station broadcast is $\mathrm{1}-p$ , and there are 1024 users ( $m=\mathrm{1024}$ ). Figure 4 shows the energy consumption of the schemes on message broadcast for a sensor node when v varies. Therefore, we can find that the other schemes except for MAS outperform our scheme, since our scheme has larger message size.

Figure 3

Energy consumption on message broadcast versus the total number of sensor nodes.

Figure 4

Energy consumption on message broadcast versus the number of neighbors for a sensor node.

6.2. Storage Overhead

In the comparison, the same settings are used as in Section 6.1. In CAS, each sensor node is required to store the ECC's parameters $(p,q,E/F_p,G_{\mathrm{1}},h,P$ , and $P_{\mathrm{p}\mathrm{u}\mathrm{b}})$ if ECDSA is used. h is a one-way hash function such as SHA-1, P is a generator of $G_{\mathrm{1}}$ , and $P_{\mathrm{p}\mathrm{u}\mathrm{b}}$ is the network public key of the base station. Note that $P_{\mathrm{p}\mathrm{u}\mathrm{b}}$ and P are two points over $E/F_p$ , among which only one of their X and Y coordinates needs to be stored.

In MAS, it requires each sensor node to keep the value $h_r$ which is the final root node of the hash tree. Furthermore, each sensor node has to store the ECC's parameters if an updated $h_r$ should be signed by the base station to prove its authenticity.

In IAS, each sensor node also has to be preloaded with the ECC's parameters $(p,q,E/F_p,G_{\mathrm{1}},G_{\mathrm{2}},\widehat{e},H,h,P$ , and $P_{\mathrm{p}\mathrm{u}\mathrm{b}})$ , where H is the MapToPoint hash function which can map strings to nonzero elements in $G_{\mathrm{1}}$ . When HAS supports up to 1000 users, each sensor node is required to store 9.8 KBytes for a single Bloom filter [22] ( $f_{\mathrm{r}\mathrm{e}\mathrm{q}}=\mathrm{2.03}\times \mathrm{1}{\mathrm{0}}^{-\mathrm{17}}$ ).

The parameters used by IMBAS [20] are similar to IAS's parameters not including $G_{\mathrm{2}}$ , $\widehat{e}$ , and H, so we do not describe them again. For our scheme, only the public key $e_{\mathrm{0}}$ has to be stored by each sensor node. For the sake of simplicity, we only quantify the parameters ( $p,q,a,b,P$ , and $P_{\mathrm{p}\mathrm{u}\mathrm{b}}$ ) for the ECC based schemes to compare our scheme with them.

The comparisons of the different schemes are shown in Table 2. Clearly, it can be observed that most of the schemes outperform HAS in terms of storage overhead for each sensor node. In addition, from Figure 5, it can be observed that the storage size of our scheme is much less than HAS. Moreover, the storage size of HAS increases significantly when the number of network users varies from $\mathrm{0}$ to $\mathrm{1000}$ . Therefore, it can be inferred that the scalability of HAS is not good as compared with the other schemes.

Table 2

Comparisons of storage overhead for the six schemes.

Schemes	Memory size	Quantitative result
CAS [21]	$p,q,a,b,P,P_{\mathrm{p}\mathrm{u}\mathrm{b}}$	≈120 bytes
MAS [21]	$p,q,a,b,h_r,P,P_{\mathrm{p}\mathrm{u}\mathrm{b}}$	≈140 bytes
IAS [21]	$p,q,a,b,P,P_{\mathrm{p}\mathrm{u}\mathrm{b}}$	≈120 bytes
HAS [22]	A Bloom filter, $p,q,a,b,P,P_{\mathrm{p}\mathrm{u}\mathrm{b}}$	≈10,155 bytes
IMBAS [20]	$p,q,a,b,P,P_{\mathrm{p}\mathrm{u}\mathrm{b}}$	≈120 bytes
Our scheme	$e_{\mathrm{0}}$	128 bytes

Figure 5

Storage size per sensor node versus the total number of network users.

6.3. Storage Overhead on Revocation List

An adversary may capture the devices of legal users, and then he/she can impersonate these legal users to broadcast bogus messages to WSNs for the purpose of exhausting the precious energy of sensor nodes. So the base station has to revoke these illegal users in WSNs. The previous schemes require each sensor node to store the IDs of revoked users infinitely when the number of revoked users increases unceasingly. For example, CAS, HAS, and IMBAS require each sensor node to store the revoked IDs. Therefore, the three schemes may incur a large amount of storage overhead.

In IAS, each sensor node stores the revoked IDs only within one time interval and removes them at the beginning of the next time interval because each user has to obtain a new private key from the base station at the beginning of each time interval. Instead, MAS and our scheme do not require each sensor node to store any revoked ID due to the update of $h_r$ and $e_{\mathrm{0}}$ . We assume that there are two hundred users that are revoked by the base station within each time interval.

Figure 6 shows the comparisons of the storage size for the six schemes with respect to the number of revoked users. In addition, once an illegal user is revoked, MAS requires current users to obtain the updated AAIs regenerated by the base station. This may be impractical for the current users roaming in WSNs. In IAS, each current user also has to obtain a new private key from the base station at the beginning of each time interval, so it is still impractical for the current users. Table 3 illustrates whether or not current users have to obtain new authentication information from the base station.

Table 3

A table illustrating whether or not current users have to obtain new authentication information from the base station for the six schemes.

	CAS [21]	MAS [21]	IAS [21]	HAS [22]	IMBAS [20]	Our scheme
Yes or No	No	Yes	Yes	No	No	No

Figure 6

Storage size per sensor node versus the number of revoked users.

6.4. Computational Overhead

In this section, the computational overhead of each sensor node will be evaluated by us. We focus on the computational overhead of verifying a message broadcasted by a user for each sensor node. Note that we still use the same assumptions as mentioned before for our evaluations. In order to compare our scheme with the other schemes in terms of computational overhead, we define seven notations as follows:

• (i)

$T_m$ is the time to perform one point multiplication operation over an elliptic curve.

(ii)

$T_p$ is the time to perform one pairing operation.

(iii)

$T_E$ is the time to perform one signature verification (ECDSA-160).

(iv)

$T_h$ is the time to perform one one-way hash function operation.

(v)

$T_H$ is the time to perform one MapToPoint hash function operation.

(vi)

$T_e$ is the time to perform one modular exponentiation operation in $G_{\mathrm{2}}$ .

(vii)

$T_{\mathrm{R}\mathrm{S}\mathrm{A}}$ is the time to perform one signature verification (RSA-1024).

In CAS, each sensor node has to perform two ECDSA signature verification procedures and two hash function operations. In MAS, to verify the user's public key, it requires a chain of hash function operations, and we assume that there are λ hash function operations to be performed. In IAS, it requires one modular exponentiation operation in $G_{\mathrm{2}}$ , one MapToPoint hash function operation, and two pairing operations. We simply assume that the total number of hash function operations for each sensor node to verify the user's public key is ${\lambda }^{\prime }$ in HAS. Furthermore, the main computational overhead of HAS is based on one ECDSA signature verification. When the message is broadcasted by the user, IMBAS takes three point multiplication operations and one hash function operation. In addition, IMBAS takes one ECDSA signature verification if the message is broadcasted by the base station. In our scheme, each sensor node is required to perform one hash function operation and one RSA signature verification.

According to [9], the energy cost to verify an ECDSA signature is 45.09 mJ in a MICA2DOT mote. Thus, we can estimate the time to perform an ECDSA signature verification is 45.09 mJ/13.8 mW = 3.267 s. We recall that 13.8 mW is the energy consumption of the MICA2DOT mote in active mode. Besides, assume that SHA-1 is used, and its energy consumption is 5.9 μJ/byte [9]. Therefore, the time to perform the SHA-1 hash function is 0.01 s when the input size is 24 bytes. Obviously, the time is very small, so it can be ignored.

For a MICA2 mote at 8 MHz, it takes 0.81 s to perform one point multiplication operation over an elliptic curve [10]. Thus, MICA2DOT mote roughly needs $\mathrm{0.81}\times \mathrm{8}/\mathrm{4}=\mathrm{1.62}$  s to perform such an operation. As reported in [29], the time to perform the Tate pairing on a 32-bit ST22 smartcard microprocessor at 33 MHz is 0.752 s. Thus, for the MICA2DOT mote, it roughly needs 6.204 s ( $\mathrm{0.752}\times \mathrm{33}/\mathrm{4}$ ) to perform the Tate pairing.

According to [21], the MapToPoint hash function takes 3.0 ms, a modular exponentiation operation in $G_{\mathrm{2}}$ takes 3.13 ms, and a Tate pairing operation takes 47.40 ms on a Pentium IV 2.26 GHz processor with 256 M RAM. Similarly, for the MICA2DOT mote, the times of performing the MapToPoint hash function and a modular exponentiation operation in $G_{\mathrm{2}}$ are $\mathrm{6.204}\times \mathrm{3.0}/\mathrm{47.40}=\mathrm{0.392}$ and $\mathrm{6.204}\times \mathrm{3.13}/\mathrm{47.40}=\mathrm{0.409}$  s, respectively. In addition, the energy consumption of the MICA2DOT mote to sign and verify a signature of 1024-bit RSA is 304 and 11.9 mJ, respectively [9]. We can also estimate the time to perform RSA signature verification is 11.9 mJ/13.8 mW = 0.862 s. In 160-bit ECDSA, the energy consumption to sign and verify a signature is 22.82 and 45.09 mJ, respectively [9].

The cost of generating an RSA signature is higher than that of verifying an RSA signature, but it does not matter in our scheme. The reason is that signatures are generated by users who are equipped with mobile devices or the powerful base station. In our scheme, each sensor node is required to perform only one RSA signatures verification.

Table 4 shows the computational time of the six schemes for verifying a message. We can observe that the computational time of our scheme is significantly less than that of the remaining schemes. Furthermore, it can also be inferred that IAS introduces a much higher computational overhead as compared to the remaining schemes because it requires each sensor node to perform two pairing operations.

Table 4

Comparisons of computational overhead for the six schemes.

Schemes	Computational overhead	Quantitative result
CAS [21]	$\mathrm{2}{T}_E+\mathrm{2}{T}_h$	≈6.534 s
MAS [21]	$T_E+(\lambda +\mathrm{1})T_h$	≈3.267 s
IAS [21]	$\mathrm{2}{T}_p+T_H+T_e$	≈13.209 s
HAS [22]	$T_E+{\lambda }^{\prime }{T}_h$	≈3.267 s
IMBAS [20]	$p(\mathrm{3}{T}_m+T_h)+$ $(\mathrm{1}-p)T_E$	≈4.2228 s ( $p=\mathit{0.6}$ ) ≈4.5414 s ( $p=\mathit{0.8}$ )
Our scheme	$T_{\mathrm{R}\mathrm{S}\mathrm{A}}+T_h$	≈0.862 s

Figure 7 also shows the energy consumption of the schemes for verifying a message when the total number of sensor nodes varies from $\mathrm{0}$ to $\mathrm{10,000}$ . Obviously, our scheme is better than previous schemes.

Figure 7

Energy consumption for verifying a message versus the total number of sensor nodes.

7. Conclusions

In this paper, we propose an RSA-like multiuser broadcast authentication scheme in WSNs. Although it is assumed that RSA is unsuitable for resource-constrained sensor nodes, the energy cost to verify an RSA signature is still acceptable for the sensor nodes. The quantitative analysis on computational cost for verifying a message shows that our scheme is more efficient than the previous schemes. Moreover, the main cost of computation always falls in the base station which is trustworthy and powerful. In our scheme, the storage cost for each sensor node takes a network public key only. No matter how many users are compromised in WSNs, the storage cost for each sensor node is still invariable because it only needs to update the network public key. On the other hand, each sensor node is able to verify every message immediately, so our scheme can mitigate the impact of DoS attacks. As a result, although our scheme has bigger message size, it is still adoptable for the WSNs in terms of storage overhead, computational overhead, scalability, and security requirements.