# Cryptanalysis of a Certificateless Aggregate Signature Scheme for Healthcare Wireless Sensor Network

Authors: Yu Zhan; Baocang Wang
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Certificateless aggregate signatures aggregaten signatures from n different users into one signature. Therefore, a verifier can judge whether all signatures are valid by verifying once. With this advantage, certificateless aggregate signatures are widely used in the environment of limited computing resources. Recently, a novel certificateless aggregate signature scheme was proposed by Kumar et al. This scheme’s security was claimed to be secure against two types of attackers under the random oracle model. In this paper, we indicate that their scheme is unable to achieve this security goal. We show an attack algorithm that the second type of attacker could forge a valid signature under an identity without the private key of the target user. Moreover, we demonstrate that the second type of attacker could forge a valid aggregate signature.


---

## Body

## 1. Introduction

Digital signature is one of the most significant concerns in the traditional public key cryptosystems. There are several types of signature schemes in the development of signature technology: public key infrastructure- (PKI-) based signature schemes, identity-based signature schemes [1, 2], and certificateless signature schemes [3, 4]. In the earliest PKI-based signature schemes, a trusted certificate authority (CA) is needed to generate a certificate that corresponds to the public key of a legitimate user. Hence, these schemes initially have to obtain and verify the certificate. This causes an amount of computational costs. Identity-based signature schemes leave out CA, but each legitimate user’s private key is produced and secretly assigned by the private key generator (PKG) which is also fully trusted. Accordingly, this kind of scheme is vulnerable to the attacks launched by the PKG. Certificateless signature schemes (CLS) overcome the shortcomings of the two kinds of schemes above. In this kind of scheme, key generation center (KGC) is in charge of calculating partial private keys and assigning the keys to legitimate users secretly. Each user calculates his private key that involves the partial private key. Consequently, not only can the user’s legitimacy be verified, but also the KGC is incapable of launching an attack by recovering the user’s private key.In addition, in some application scenarios, the pattern of verifying one signature one time fails to meet the requirement of fast data processing. To solve this problem, Boneh et al. first put forward the concept of aggregate signature in 2003 [5]. Aggregate signature enables multiple signatures signed by multiple users to be aggregated into a single signature. Hence, the verifier can believe that all signatures are valid by verifying only once. This pattern greatly reduces the costs of communication and computation.It is natural to combine the certificateless signature with the aggregate signature. As a result, lots of certificateless aggregate signature (CL-AS) schemes have been presented, such as [6–9]. Recently, Kumar et al. proposed a novel certificateless signature scheme with bilinear pairing. Furthermore, they extended the CLS scheme to a CL-AS scheme [10]. They illustrated that their schemes are secure against two types of attackers. These two types of attackers have been widely used in the security proof of CL-AS. The details of the attackers are given below:(i)
Type I: an outside attacker who can replace the public keys of users and compromise the private keys of users. However, the attacker is unable to recover the master key or the partial private key.(ii)
Type II: an “honest-but-curious” KGC with the master key. However, it cannot replace the public keys of users or compromise the private keys of users.We prove that Kumar et al.’s schemes cannot prevent the Type II attacker from forging a valid signature. The rest of this paper is organized as follows. We review the related work in Section2 and describe the details of Kumar et al.’s schemes in Section 3. In Section 4, we show the attack algorithms. Finally, we concluded in Section 5.


## 2. Related Work

In 2003, Al-Riyami et al. [3] first introduced the notion of certificateless public key cryptosystem that is designed to solve the key escrow and certificate management issues. Besides, they proposed a CLS scheme as an instance. After that, the design and cryptanalysis of certificateless signature have become attractive research focuses. Huang et al. [11] indicated that Al-Riyami et al.’s scheme is incapable of resisting the public key replacement attack and they proposed an improvement scheme to fix the security vulnerability. Yum et al. [12] utilized the standard signature scheme and the ID-based signature scheme to propose a generic construction of CLS. Similarly, their scheme is insecure against the public key replacement attack [13]. Zhang et al. [14] presented a provably secure CLS scheme with bilinear pairing. Cao et al. [15] gave an attack algorithm for Gorantla et al.’s CLS scheme [4]. Liu et al. [16] presented a CLS scheme under the standard model. Xiong et al. [17] and Xia et al. [18] soon showed that Liu et al.’s scheme cannot achieve the security goals they claimed, respectively. Yeh et al. [19] proposed a CLS scheme which proved to be insecure by Jia et al. [20]. In addition, there are several CLS schemes that have not yet been identified as having security issues, such as [17, 21, 22].As we mentioned above, the design and analysis of CL-AS schemes have been the concern of researchers. In 2007, Castro et al. [23] proposed an efficient CL-AS scheme. Similar with the later CL-AS schemes presented by Gong [24] and Zhang [6], the computational complexity of their schemes is too high to implement in practice. In 2010, Zhang et al. [25] introduced a novel CL-AS scheme. However, their scheme is unpractical since it needs a synchronous clock to aggregate signatures. In 2013, Xiong et al. [7] proposed a CL-AS scheme which needs constant bilinear pairing computations and is more efficient than previous works. Zhang et al. [26] and He et al. [27] indicated that the scheme [7] cannot resist the public key replacement attack. Meanwhile, Cheng et al. [8] and Tu et al. [28] presented improvement schemes based on Xiong et al.’s, respectively. Recently, researchers have gradually focused on the design of CL-AS schemes in special application environments. In 2015, Malhi et al. [29] showed a CL-AS scheme for vehicular ad hoc networks. Kumar et al. [30] found the security loophole of Malhi et al.’s scheme and gave an improvement scheme. However, Yang et al. [31] indicated that the improvement scheme is still insecure, and they proposed a new improvement scheme. Although the security of many schemes is no longer convincing, the schemes, e.g., [8, 28, 31], are still secure now.


## 3. Review of Kumar Et Al.’s Scheme

In this section, we first review the security model of Kumar et al.’s schemes [10].


### 3.1. Security Model

In their security model, the challengerC provides the following oracles to the adversary A.KeyGen(IDi): Input an identity IDi of user, and this oracle will output a public key pki under the identityIDi.RevealSK(IDi): Input an identity IDi of user, and this oracle will output the private key ski under the identity IDi.RevealPK(IDi): Input an identity IDi of user, and this oracle will output the partial private key ppki under the identity IDi.ReplaceKey(IDi,pki′,ski′): Input an identity IDi as well as a key pair (pki′,ski′), and the original key pair will be replaced with the input one.Sign(IDi,mi): If the identity IDi has never been queried with the oracle KeyGen, return error symbol ⊥. Else, the oracle runs the signing algorithm with the current key pair under IDi and outputs the result.The EUF-CMA (existential unforgeability against chosen message attacks) security model [32] for their CLS scheme consists of two games: Games 1 and 2.Game.
In this game, the adversary corresponds to the Type I attacker.
Setup: the challengerC runs the setup algorithm. Then, C keeps the master key secretly and returns the corresponding public key to A.
Queries: the adversaryA could query the above five oracles in polynomial bound.
Output: After querying, the adversary outputs a messagem, the identity of target user ID∗, and a signature of message σ∗.
The adversaryA will win this game if σ∗ is a valid signature of m while Sign(ID∗,m) and RevealPK(ID∗) have never been queried.Game.
In this game, the adversary corresponds to the Type II attacker.
Setup: the challengerC runs the setup algorithm. Then, C returns the master key and the corresponding public key to A.
Queries: the adversaryA can query the above oracles expect ReplaceKey in polynomial bound. It is unnecessary to provide the RevealPK oracle since the adversary could calculate the partial private key under an identity with the master key by itself.
Output: after querying, the adversary outputs a messagem, the identity of target user ID∗, and a signature of message σ∗.
The adversaryA will win this game if σ∗ is a valid signature of m while Sign(ID∗,m) and RevealSK(ID∗) have never been queried.The CLS scheme is EUF-CMA secure only if the probability polynomial adversary cannot win in both games with nonnegligible advantages. The security model for the CL-AS scheme consists of two games too. The details are given below.Game.
In this game, the adversary corresponds to the Type I attacker.
The Setup and Queries stages are the same with Game 1.
Output: After querying, the adversary outputs a tuple({mi},{IDi∗},σ∗), where {mi} is a set of messages, {IDI∗} is a set of the identities of target users, and σ∗ is an aggregate signature of {mi}.
Ifσ∗ is a valid aggregate signature of {mi} while there is at least one identity IDj that has never been queried for Sign(IDj∗,mj) and RevealPK(IDj∗), the adversary A wins this game.Game.
In this game, the adversary corresponds to the Type II attacker.
The Setup and Queries stages are the same as Game 2.
Output: After querying, the adversary outputs a tuple({mi},{IDi∗},σ∗), where {mi} is a set of messages, {IDi∗} is a set of the identities of target users, and σ∗ is an aggregate signature of {mi}.
Ifσ∗ is a valid aggregate signature of {mi} while there is at least one identity IDj that has never been queried for Sign(IDj∗,mj) and RevealSK(IDj∗), the adversary A wins this game.The CL-AS scheme is EUF-CMA secure only if the probability polynomial adversary cannot win in both games with nonnegligible advantages.Next, we review the Kumar et al.’s scheme that includes seven algorithms. The details are given below.


### 3.2. Setup Algorithm

Given the security parameterλ, the setup algorithm that was performed by KGC generates a system parameter param and a master key msk as follows.(1)
Randomly select a primep according to the security parameter λ.(2)
Select an additive cyclic groupG1 and a multiplicative cyclic group G2 of prime order p. Particularly, g is a random generator of G1.(3)
Select a bilinear mape~:G1×G1→G2 which is effective to compute.(4)
Randomly select a master keymsk=s←Zp∗, and compute the corresponding public key as mpk=sg.(5)
Define three secure hash functions:H0:{0,1}∗→G1, H1:{0,1}∗→G1, and H2:{0,1}∗→Zp∗.(6)
Disclose the system parameterparam=(H0,H1,H2,g,G1,G2,e~,mpk) and keep msk secretly.All of the algorithms below need the system parameterparam to calculate. We omit it in the following descriptions.


### 3.3. Partial Private Key Generation Algorithm

With a user’s identityIDi, this algorithm generates a partial private key. The KGC performs as follows.(1)
CalculatePi=H0(IDi).(2)
Calculate the partial private key asppki=sPi.(3)
Transmitppki through a secure communication channel to the user Ui.


### 3.4. Key Generation Algorithm

This algorithm outputs a public/private key pair for a userUi under IDi. The user performs as follows.(1)
Randomly selectxi←Zp∗ as the private key, i.e., ski=xi.(2)
Compute the public key aspki=xig.


### 3.5. Signing Algorithm

Given a partial private keyppki, a private key ski under an identity IDi, the state information α (randomly selected from the public parameter), and a message mi as inputs, the user Ui generates a signature σi of mi as follows.(1)
Randomly selectri←Zp∗ and compute Ti=rig.(2)
Calculatehi=H2(mi,IDi,pki,Ti) and Q=H1(α).(3)
CalculateVi=ppki+riQ+hiximpk.(4)
Set the signature asσi=(Ti,Vi).


### 3.6. Verification Algorithm

This algorithm takes a public keypki under an identity IDi, the state information α, a signature σi, and a message mi as inputs. The verifier performs as follows.(1)
ComputePi=H0(IDi), hi=H2(IDi,mi,pki,Ti), and Q=H1(α).(2)
Verify whether the equatione~Vi,g=e~(Pi+hipki,mpk)e~(Q,Ti) holds. If yes, accept the signature σi.


### 3.7. Aggregation Algorithm

This algorithm takesn signatures {σ1,σ2,…,σn} of n messages {m1,m2,⋯,mn} as inputs. These signatures are generated by n users under identities {ID1,ID2,…,IDn}, respectively. Then, the aggregator sets the aggregate signature as σ=T1,T2,…,Tn,V after calculating V=∑i=1nVi.


### 3.8. Aggregate Verification Algorithm

Given an aggregate signatureσ, n public keys {pk1,pk2,…,pkn} under identities {ID1,ID2,…,IDn}, n messages {m1,m2,⋯mn}, and the state information α as inputs, this algorithm performs as follows.(1)
ComputePi=H0IDi, hi=H2IDi,mi,pki,Ti for i=1,…,n.(2)
ComputeQ=H1(α).(3)
Verify whether the equatione~(V,g)=e~(∑i=1nPi+hipki,mpk)e~(Q,∑i=1nTi) holds. If yes, accept σ.We clearly show the loophole of their schemes in the next section.


## 3.1. Security Model

In their security model, the challengerC provides the following oracles to the adversary A.KeyGen(IDi): Input an identity IDi of user, and this oracle will output a public key pki under the identityIDi.RevealSK(IDi): Input an identity IDi of user, and this oracle will output the private key ski under the identity IDi.RevealPK(IDi): Input an identity IDi of user, and this oracle will output the partial private key ppki under the identity IDi.ReplaceKey(IDi,pki′,ski′): Input an identity IDi as well as a key pair (pki′,ski′), and the original key pair will be replaced with the input one.Sign(IDi,mi): If the identity IDi has never been queried with the oracle KeyGen, return error symbol ⊥. Else, the oracle runs the signing algorithm with the current key pair under IDi and outputs the result.The EUF-CMA (existential unforgeability against chosen message attacks) security model [32] for their CLS scheme consists of two games: Games 1 and 2.Game.
In this game, the adversary corresponds to the Type I attacker.
Setup: the challengerC runs the setup algorithm. Then, C keeps the master key secretly and returns the corresponding public key to A.
Queries: the adversaryA could query the above five oracles in polynomial bound.
Output: After querying, the adversary outputs a messagem, the identity of target user ID∗, and a signature of message σ∗.
The adversaryA will win this game if σ∗ is a valid signature of m while Sign(ID∗,m) and RevealPK(ID∗) have never been queried.Game.
In this game, the adversary corresponds to the Type II attacker.
Setup: the challengerC runs the setup algorithm. Then, C returns the master key and the corresponding public key to A.
Queries: the adversaryA can query the above oracles expect ReplaceKey in polynomial bound. It is unnecessary to provide the RevealPK oracle since the adversary could calculate the partial private key under an identity with the master key by itself.
Output: after querying, the adversary outputs a messagem, the identity of target user ID∗, and a signature of message σ∗.
The adversaryA will win this game if σ∗ is a valid signature of m while Sign(ID∗,m) and RevealSK(ID∗) have never been queried.The CLS scheme is EUF-CMA secure only if the probability polynomial adversary cannot win in both games with nonnegligible advantages. The security model for the CL-AS scheme consists of two games too. The details are given below.Game.
In this game, the adversary corresponds to the Type I attacker.
The Setup and Queries stages are the same with Game 1.
Output: After querying, the adversary outputs a tuple({mi},{IDi∗},σ∗), where {mi} is a set of messages, {IDI∗} is a set of the identities of target users, and σ∗ is an aggregate signature of {mi}.
Ifσ∗ is a valid aggregate signature of {mi} while there is at least one identity IDj that has never been queried for Sign(IDj∗,mj) and RevealPK(IDj∗), the adversary A wins this game.Game.
In this game, the adversary corresponds to the Type II attacker.
The Setup and Queries stages are the same as Game 2.
Output: After querying, the adversary outputs a tuple({mi},{IDi∗},σ∗), where {mi} is a set of messages, {IDi∗} is a set of the identities of target users, and σ∗ is an aggregate signature of {mi}.
Ifσ∗ is a valid aggregate signature of {mi} while there is at least one identity IDj that has never been queried for Sign(IDj∗,mj) and RevealSK(IDj∗), the adversary A wins this game.The CL-AS scheme is EUF-CMA secure only if the probability polynomial adversary cannot win in both games with nonnegligible advantages.Next, we review the Kumar et al.’s scheme that includes seven algorithms. The details are given below.


## 3.2. Setup Algorithm

Given the security parameterλ, the setup algorithm that was performed by KGC generates a system parameter param and a master key msk as follows.(1)
Randomly select a primep according to the security parameter λ.(2)
Select an additive cyclic groupG1 and a multiplicative cyclic group G2 of prime order p. Particularly, g is a random generator of G1.(3)
Select a bilinear mape~:G1×G1→G2 which is effective to compute.(4)
Randomly select a master keymsk=s←Zp∗, and compute the corresponding public key as mpk=sg.(5)
Define three secure hash functions:H0:{0,1}∗→G1, H1:{0,1}∗→G1, and H2:{0,1}∗→Zp∗.(6)
Disclose the system parameterparam=(H0,H1,H2,g,G1,G2,e~,mpk) and keep msk secretly.All of the algorithms below need the system parameterparam to calculate. We omit it in the following descriptions.


## 3.3. Partial Private Key Generation Algorithm

With a user’s identityIDi, this algorithm generates a partial private key. The KGC performs as follows.(1)
CalculatePi=H0(IDi).(2)
Calculate the partial private key asppki=sPi.(3)
Transmitppki through a secure communication channel to the user Ui.


## 3.4. Key Generation Algorithm

This algorithm outputs a public/private key pair for a userUi under IDi. The user performs as follows.(1)
Randomly selectxi←Zp∗ as the private key, i.e., ski=xi.(2)
Compute the public key aspki=xig.


## 3.5. Signing Algorithm

Given a partial private keyppki, a private key ski under an identity IDi, the state information α (randomly selected from the public parameter), and a message mi as inputs, the user Ui generates a signature σi of mi as follows.(1)
Randomly selectri←Zp∗ and compute Ti=rig.(2)
Calculatehi=H2(mi,IDi,pki,Ti) and Q=H1(α).(3)
CalculateVi=ppki+riQ+hiximpk.(4)
Set the signature asσi=(Ti,Vi).


## 3.6. Verification Algorithm

This algorithm takes a public keypki under an identity IDi, the state information α, a signature σi, and a message mi as inputs. The verifier performs as follows.(1)
ComputePi=H0(IDi), hi=H2(IDi,mi,pki,Ti), and Q=H1(α).(2)
Verify whether the equatione~Vi,g=e~(Pi+hipki,mpk)e~(Q,Ti) holds. If yes, accept the signature σi.


## 3.7. Aggregation Algorithm

This algorithm takesn signatures {σ1,σ2,…,σn} of n messages {m1,m2,⋯,mn} as inputs. These signatures are generated by n users under identities {ID1,ID2,…,IDn}, respectively. Then, the aggregator sets the aggregate signature as σ=T1,T2,…,Tn,V after calculating V=∑i=1nVi.


## 3.8. Aggregate Verification Algorithm

Given an aggregate signatureσ, n public keys {pk1,pk2,…,pkn} under identities {ID1,ID2,…,IDn}, n messages {m1,m2,⋯mn}, and the state information α as inputs, this algorithm performs as follows.(1)
ComputePi=H0IDi, hi=H2IDi,mi,pki,Ti for i=1,…,n.(2)
ComputeQ=H1(α).(3)
Verify whether the equatione~(V,g)=e~(∑i=1nPi+hipki,mpk)e~(Q,∑i=1nTi) holds. If yes, accept σ.We clearly show the loophole of their schemes in the next section.


## 4. Cryptanalysis of the Kumar Et Al.’s Schemes

We indicate that the KGC who owns the master keymsk is capable of forging a valid signature under an identity IDi without the corresponding private key ski. Furthermore, the KGC can forge a valid aggregate signature. The details of the attacks are given below.


### 4.1. Attack on the Certificateless Signature Scheme

Given a messagemi, a public key pki under an identity IDi, and the state information α, the KGC forges a signature σ of mi as follows.(1)
Randomly selectri∗←Zp∗ and calculate Ti∗=ri∗g.(2)
Calculatehi∗=H2(IDi,mi,pki,Ti∗), Q=H1(α), and Pi=H0(IDi).(3)
CalculateVi∗=s·Pi+ri∗Q+hi∗·s·pki.(4)
Set the signature asσ=(Ti∗,Vi∗)Correctness (1) e ~ V i ∗ , g = e ~ s · P i + r i ∗ Q + h i ∗ · s · p k i , g = e ~ s · P i + h i ∗ · s · p k i , g e ~ r i ∗ Q , g = e ~ P i + h i ∗ p k i , s g e ~ Q , r i ∗ g = e ~ P i + h i ∗ p k i , m p k e ~ Q , T i ∗Hence, σ=(Ti∗,Vi∗) is a valid signature of mi under IDi. This CLS scheme is insecure against the attack launched by the “honest-but-curious” KGC.


### 4.2. Attack on the Certificateless Aggregate Signature Scheme

The CL-AS scheme presented by Kumar et al. is also insecure against the attack launched by the “honest-but-curious” KGC. Givenn messages {m1,m2,…,mn} and n users under {ID1,ID2,…,IDn}, the KGC performs as follows.(1)
Generaten signatures with the algorithm given in Section 3.5: (m1,σ1),(m2,σ2),⋯,(mn,σn).(2)
CalculateV∗=∑i=1nVi∗.(3)
Set the aggregate signature asσ=(T1∗,T2∗,…,Tn∗,V∗).Correctness (2) e ~ V ∗ , g = e ~ ∑ i = 1 n V i ∗ , g = e ~ s · P 1 + r 1 ∗ Q + h 1 ∗ · s · p k 1 , g ⋯ e ~ s · P n + r n ∗ Q + h n ∗ · s · p k n , g = e ~ P 1 + h 1 ∗ p k 1 , m p k e ~ Q , T 1 ∗ ⋯ e ~ P n + h n ∗ p k n , m p k e ~ Q , T n ∗ = e ~ ∑ i = 1 n P i + h i ∗ p k i , m p k e ~ Q , ∑ i = 1 n T i ∗The forged aggregate signature sigma=T1∗,T2∗,…,Tn∗,V∗ is a valid aggregate signature according to Section 3.7. Hence, this CL-AS scheme is insecure either.


## 4.1. Attack on the Certificateless Signature Scheme

Given a messagemi, a public key pki under an identity IDi, and the state information α, the KGC forges a signature σ of mi as follows.(1)
Randomly selectri∗←Zp∗ and calculate Ti∗=ri∗g.(2)
Calculatehi∗=H2(IDi,mi,pki,Ti∗), Q=H1(α), and Pi=H0(IDi).(3)
CalculateVi∗=s·Pi+ri∗Q+hi∗·s·pki.(4)
Set the signature asσ=(Ti∗,Vi∗)Correctness (1) e ~ V i ∗ , g = e ~ s · P i + r i ∗ Q + h i ∗ · s · p k i , g = e ~ s · P i + h i ∗ · s · p k i , g e ~ r i ∗ Q , g = e ~ P i + h i ∗ p k i , s g e ~ Q , r i ∗ g = e ~ P i + h i ∗ p k i , m p k e ~ Q , T i ∗Hence, σ=(Ti∗,Vi∗) is a valid signature of mi under IDi. This CLS scheme is insecure against the attack launched by the “honest-but-curious” KGC.


## 4.2. Attack on the Certificateless Aggregate Signature Scheme

The CL-AS scheme presented by Kumar et al. is also insecure against the attack launched by the “honest-but-curious” KGC. Givenn messages {m1,m2,…,mn} and n users under {ID1,ID2,…,IDn}, the KGC performs as follows.(1)
Generaten signatures with the algorithm given in Section 3.5: (m1,σ1),(m2,σ2),⋯,(mn,σn).(2)
CalculateV∗=∑i=1nVi∗.(3)
Set the aggregate signature asσ=(T1∗,T2∗,…,Tn∗,V∗).Correctness (2) e ~ V ∗ , g = e ~ ∑ i = 1 n V i ∗ , g = e ~ s · P 1 + r 1 ∗ Q + h 1 ∗ · s · p k 1 , g ⋯ e ~ s · P n + r n ∗ Q + h n ∗ · s · p k n , g = e ~ P 1 + h 1 ∗ p k 1 , m p k e ~ Q , T 1 ∗ ⋯ e ~ P n + h n ∗ p k n , m p k e ~ Q , T n ∗ = e ~ ∑ i = 1 n P i + h i ∗ p k i , m p k e ~ Q , ∑ i = 1 n T i ∗The forged aggregate signature sigma=T1∗,T2∗,…,Tn∗,V∗ is a valid aggregate signature according to Section 3.7. Hence, this CL-AS scheme is insecure either.


## 5. Conclusions

Kumar et al. [10] proposed a CLS scheme and a CL-AS scheme. They claimed that these two schemes are both secure against two types of attackers. In this paper, we present attack algorithms for the two schemes, respectively. Details of our attacks show that the KGC can forge a valid signature of a message under a target identity without the corresponding private key. Similarly, the KGC can forge a valid aggregate signature. Hence, their schemes are insecure to implement in practical.



---

*Source: 6059834-2019-06-09.xml*