On the Security of Certificateless Signature Schemes

Abstract

Wireless Sensor Network (WSN) has proved its presence in various real time applications and hence the security of such embedded devices is a vital issue. Certificateless cryptography is one of the recent paradigms to provide security. Certificateless public key cryptography (CL-PKC) deals effectively with the twin issues of certificate management in traditional public key cryptography and key escrow problem in identity-based cryptography. CL-PKC has attracted special attention in the field of information security as it has opened new avenues for improvement in the present security architecture. Recently, Tsai et al. proposed an improved certificateless signature scheme without pairing and claimed that their new construction is secure against different kinds of attacks. In this paper, we present a security analysis of their scheme and our results show that scheme does not have resistance against malicious-KGC attack. In addition, we have found some security flaws in the certificateless signature scheme of Fan et al. and proved the scheme vulnerable to Strong Type I attack.

1. Introduction

The validation of public keys by a trusted third party, also known as Certificate Authority (CA), makes traditional Public Key Infrastructure (PKI) uneconomical. The user selects a public key and then CA provides a digital certificate to associate the public key with the user's identity. The management of these certificates is a complex issue and increases the computation and storage cost manifold. To resolve the issues of PKC a revolutionary ID-based infrastructure was introduced by Shamir [1] in 1984. This seminal concept of Identity Based Cryptography (IBC) allows the user to choose a public key of its own choice such as email ID, phone number, and name. In IBC, users do not generate their own private keys as in traditional PKC. Private keys are generated by Key Generation Centre (KGC), maintains the private keys of all the users, but there is always a possibility of the misuse of these private keys as they can be used to decrypt any ciphertext and forge the signature of user on any message for signature generation. Eventually, this new paradigm solved the problem of certificate management but gave birth to inherent problem of key escrow.

In 2003, Al-riyami and Paterson [2] proposed a novel approach to eliminate the inherent key escrow problem of IBC as well as the use of certificates in traditional PKC. This approach is known as CL-PKC, where KGC generates a partial-private key for the user while user's secret key and partial-private key are used to generate the public key of the user. In other words, CL-PKC differs from IBC in terms of arbitrary public key, and when a signature is transmitted, user's public key is attached with it but not certified by any of the trusted authority. Moreover, KGC is not aware of the secret key of the user.

However, Al-riyami and Paterson's [2] scheme has been proved insecure against Type I adversary by Huang et al. [3] and proposed an improved scheme. A generic construction has been proposed by Yum and Lee [4] in 2004 which is based on identity based signature. Later, Hu et al. [5] found it insecure against key replacement attack and proposed an improved version. Meanwhile Libert and Quisquater [6] proposed another generic construction without precomputations, which is based on Al-riyami and Paterson's work. In 2005, Gorantla and Saxena [7] proposed an efficient CLS scheme but it was found to be insecure against the key replacement attack by Cao et al. [8]. Li et al. [9] and Zhang et al. [10] proposed CLS schemes based on elliptic curve but verification algorithms in their schemes require four pairing computations. To improve the performance, Yap et al. [11] proposed an efficient CLS scheme which required only two bilinear pairings. However, Park and Kang [12] found that the scheme [11] is insecure against a key replacement attack. Recently, Au et al. [13] suggested a new kind of malicious-but-passive-KGC attack where adversary may get access to the secret/public key of KGC and then modified Hu et al.'s model [5] for capturing the attack. In 2007, Huang et al. [14] proposed two new short CLS schemes and claimed their first scheme is provably secure against a Normal Type I adversary as well as Super Type II adversary and the second scheme is secure against Super Type I and Type II adversaries. Unfortunately, Shim [15] claimed that the first scheme in [14] is universally forgeable by the Type I adversary. Later, Tso et al. [16–18] presented efficient short CLS schemes. Recently two CLS schemes were proposed by Xu et al. in [19, 20] for mobile wireless cyber-physical systems, and emergency mobile wireless cyber-physical systems respectively. They were claimed to provide high efficiency and provable security. However, Zhang et al. [21] has shown that these two schemes are universally forgeable against public key replacement attack. Wang et al. [22] proposed a scheme which need not compute the pairing $e(P,P)=g$ at the sign stage, rather it precomputes and publishes the system parameters.

Recently, Du and Wen [23] presented a short CLS scheme and claimed that it is secure against Strong adversaries. However, Fan et al. [24] and Choi et al. [25] independently showed it to be insecure against Strong Type I adversary. Further, Fan et al. [24] proposed a CLS scheme from bilinear pairing with additional property of nonrepudiation but later it was found in [26] that the scheme does not acheive Girault's level 3 security. Later, Tian et al. [27] claimed that the scheme [25] didnot withstand against Strong Type II adversary.

In certificateless infrastructure, the majority of the schemes lacks in some common security issue. To attack a CLS scheme broadly two types of adversaries have been defined: Type I and Type II. A Type I adversary can replace a user's public key but is not able to obtain KGC's master secret key and a Type II adversary is a malicious KGC who knows the master secret key but cannot replace user's public key. Although Huang et al. [28] divide the potential adversaries according to their attack power and enrich the CL-PKC with three more categories. A clear definition of all the three categories of adversaries, Normal, Strong, and Super, has been provided together with the security models. On association with the existing categorization of Type I and Type II adversaries, six types of adversaries can be obtained. These are Normal Type I, Strong Type I, Super Type I, Normal Type II, Strong Type II, and Super Type II. In fact, if a scheme is secure against a Super Type I (II) adversary, it will guarantee the security against Normal and Strong Type I (II) adversaries but the reverse may not be true.

In any certificateless scheme, it is always a good idea to avoid pairing operation as it leads to the increase in computation cost manifold as compared to any other operation. An interesting attempt has been made by He et al. [29] in 2011. He et al. developed an efficient short CLS scheme without pairing. The advantage of the scheme is that it does not use any pairing operation and the length of signature is short. However, in 2012, Tian and Huang [30] proved that the scheme cannot resist against Strong Type II adversary having an access to the master secret key of the KGC. Later Tsai et al. [31] discovered that the short CLS scheme [29] cannot withstand against Type II adversary and proposed an improved scheme to overcome the weaknesses of He et al.'s [29] scheme. In this paper, we provide a cryptanalysis on the Tsai et al. [31] scheme by using two Type II attacks.

As all the schemes based on ID-based cryptography have been implemented on sensor network, so these schemes are similarly applicable to Wireless Sensor Network [32]. Mica2, Micaz, Tmote sky, and TelosB are the commonly available motes and can be used for implementation. Evaluation of these schemes can be on the basis of various factors like energy consumption, computation time, and security provided. The schemes discussed here in this papers are very much of interest because they are free from pairing, so easily applicable to WSN. But with less resource consumption scheme should not compromise with security. These schemes are found to be vulnerable and few flaws have been reported. In this paper few attacks have been given which will help to improve the scheme.

The rest of the paper is organized as follows. Section 2 presents some preliminaries and complexity assumptions. Section 3 reviews the Tsai et al.'s scheme [31]. In Section 4, we discuss the security analysis of Tsai et al.'s scheme and prove that the scheme is insecure against Strong Type II attack. Section 5 reviews the Fan et al.'s scheme [24]. In Section 6, we discuss the security analysis of Fan et al.'s scheme and proved in insecure against Strong Type I attack followed by the concluding remarks on the presented work.

2. Preliminaries

This section revisits the fundamentals used in the CLS scheme.

2.1. Overview of Elliptic Curve Cryptography

An elliptic curve [33, 34] is a set of points over a finite field $GF(p)$ , a Galois Field of order p, which satisfies the Weierstra ℬ equation [35]

$$\begin{array}{cc}& y^{\mathrm{2}}+a_{\mathrm{1}}xy+a_{\mathrm{3}}y=x^{\mathrm{3}}+a_{\mathrm{2}}{x}^{\mathrm{2}}+a_{\mathrm{4}}x+a_{\mathrm{6}}\end{array}$$

(1)

but for simplification of computations, cryptographic applications prefer the simple form of Weierstra ℬ equation as

$$\begin{array}{cc}& y^{\mathrm{2}}=x^{\mathrm{3}}+ax+b,\end{array}$$

(2)

where $a,b\in GF(p)$ .

2.2. Complexity Assumptions

The security of elliptic curve based cryptosystem is based on the assumption that the Elliptic Curve Discrete Logarithm Problem (ECDLP) is hard, which can be defined as follows.

Let E be an elliptic curve over a finite field $F_p$ . Suppose, there are points P, Q on the curve $E(F_p)$ for given generator P. Determine k such that $Q=[k]P$ .

3. Review of Tsai et al.'s Short CLS Scheme

In this section, we briefly review the short certificateless signature scheme based on ECDLP [31]. The scheme works as follows.

Setup. Let G be a cyclic additive group, let $E/F_p$ be an elliptic curve E over a prime finite field $F_p$ defined by an equation $y^{\mathrm{2}}=x^{\mathrm{3}}+ax+b$ , and let p be k-bit prime number, where $p\in G$ . Initially, the KGC computes its master public key $P_{\text{pub}}=xP$ and chooses two secure one-way hash functions: $H_{\mathrm{1}}:\{\mathrm{0,1}{\}}^{*}\times G\times G\to Z_n^{*}$ and $H_{\mathrm{2}}:\{\mathrm{0,1}{\}}^{*}\times G\times G\times G\to Z_n^{*}$ , where $x\in Z_n^{*}$ is the master key chosen by KGC. The KGC then publishes public parameters $\{F_p,E/F_p,G,P,P_{\text{pub}},H_{\mathrm{1}},H_{\mathrm{2}}\}$ and keeps master key x secret.

Set-Secret Value. A signer chooses his/her identity $\text{ID}$ and his/her secret value $x_{\text{ID}}$ . The signer then computes $P_{\text{ID}}=x_{\text{ID}}P$ and keeps master key x secret $x_{\text{ID}}$ .

Partial-Private-Key Extract. The KGC computes $R_{\text{ID}}=r_{\text{ID}}P$ and $h_{\text{ID}}=H_{\mathrm{1}}(\text{ID},R_{\text{ID}},P_{\text{ID}})$ for each signer with his/her identity $\text{ID}\in \{\mathrm{0,1}{\}}^{*}$ , where $r_{\text{ID}}\in Z_n^{*}$ is a random number. The KGC then computes $s_{\text{ID}}=r_{\text{ID}}+h_{\text{ID}}x$ mod n and sends $(s_{\text{ID}},R_{\text{ID}})$ to the user via a secure channel. Notably, the tuple $(s_{\text{ID}},R_{\text{ID}})$ is the partial-private key of the user and the user can confirm its validity by checking the following equation: $s_{\text{ID}}P=R_{\text{ID}}+h_{\text{ID}}·P_{\text{pub}}$ . If the equation holds, the partial-private key $(s_{\text{ID}},R_{\text{ID}})$ is valid; otherwise, the signer rejects the partial-private key $(s_{\text{ID}},R_{\text{ID}})$ .

Set-Private Key. The signer uses $s{k}_{\text{ID}}=(x_{\text{ID}},s_{\text{ID}})$ as his/her private key.

Set-Public Key. The signer adopts $p{k}_{\text{ID}}=(P_{\text{ID}},R_{\text{ID}})$ as his/her public key.

Sign. Assume a signer wants to sign a message m, he/she performs the following steps to generate signature $(R,s)$ on chosen message m.

• (i)

The signer computes $R=l·P$ , $h_{\mathrm{1}}=H_{\mathrm{2}}(m,R,P_{\text{ID}},R_{\text{ID}})$ , $h_{\mathrm{2}}=H_{\mathrm{2}}(m,R,P_{\text{ID}},R_{\text{ID}},P_{\text{pub}})$ , where r_ID is a random number.

(ii)

The signer checks whether $gcd(l+h_{\mathrm{1}},n)$ equals 1. If it does not hold, the signer returns to step (i).

(iii)

The signer computes $s=(l+h_{\mathrm{1}}{)}^{-\mathrm{1}}(h_{\mathrm{2}}·x_{\text{ID}}+s_{\text{ID}})$ mod n and then sends $(R,s)$ to the verifier.

Verify. Upon receiving the signature $(R,s)$ on message m from the signer, the verifier can confirm the validity of signature $(R,s)$ using the following equation:

$$\begin{array}{cc}& s·\left(R+h_{\mathrm{1}}·P\right)=h_{\mathrm{2}}·P_{\text{ID}}+R_{\text{ID}}+h_{\text{ID}}·P_{\text{pub}},\end{array}$$

(3)

where $h_{\mathrm{1}}=H_{\mathrm{2}}(m,R,P_{\text{ID}},R_{\text{ID}})$ , $h_{\mathrm{2}}=H_{\mathrm{2}}(m,R,P_{\text{ID}},R_{\text{ID}},P_{\text{pub}})$ , and $h_{\text{ID}}=H_{\mathrm{1}}(\text{ID},R_{\text{ID}},P_{\text{ID}})$ .

If the above equation holds, signature $(R,s)$ is valid; otherwise, the verifier rejects the signature.

4. Cryptanalysis of Tsai et al.'s Short CLS Scheme

In this section, we prove that the He et al. [29] CLS scheme is forgeable by the Strong Type II adversary; that is, the adversary can forge users certificateless signatures by using malicious-KGC attack. Tsai et al. proposed an improvement in the He et al.'s [29] scheme and claimed that the scheme is secure under discrete logarithm assumption in random oracle model. Unfortunately, the scheme was found to be insecure against the malicious-KGC attack.

4.1. Attack 1

The adversary ${𝒜}_{\text{II}}$ will perform the following steps.

• (i)

The adversary ${𝒜}_{\text{II}}$ choose random numbers $t,l^{\prime }\in Z_n^{*}$ and a message $m^{\prime }$ and computes

$$\begin{array}{cc}& R^{\prime }=l^{\prime }P.\end{array}$$

(4)

 

The adversary ${𝒜}_{\text{II}}$ replaces the KGC's master public key $P_{\text{pub}}$ with

$$\begin{array}{cc}& P_{\text{pub}}^{\prime }=\frac{t-R_{\text{ID}}}{h_{\text{ID}}^{\prime }},\end{array}$$

(5)

 

where, $h_{\text{ID}}^{\prime }=H_{\mathrm{1}}(\text{ID},P_{\text{ID}},R_{\text{ID}})$ .

 

And, the adversary generates the signature as

$$\begin{array}{cc}& s^{\prime }=\frac{t+h_{\mathrm{2}}^{\prime }{P}_{\text{ID}}}{\left(l^{\prime }+h_{\mathrm{1}}^{\prime }\right)P}\mathrm{mod}\hspace{0.17em}n,\end{array}$$

(6)

 

where $h_{\mathrm{1}}^{\prime }=H_{\mathrm{2}}(m^{\prime },R^{\prime },P_{\text{ID}},R_{\text{ID}})$ , $h_{\mathrm{2}}^{\prime }=H_{\mathrm{2}}(m^{\prime },R^{\prime },P_{\text{ID}},R_{\text{ID}},P_{\text{pub}}^{\prime })$ . Clearly, $(R^{\prime },s^{\prime })$ is the forged signature on the message $m^{\prime }$ .

(ii)

To check the validity of the signature, the verifier can perform the following verification by using the following equation:

$$\begin{array}{l}{s}^{\prime }·\left(R^{\prime }+h_1^{\prime }·P\right)=\frac{t+h_2^{\prime }{P}_{\text{ID}}}{\left(l^{\prime }+h_1^{\prime }\right)P}·\left(l^{\prime }P+h_1^{\prime }P\right)\hfill \\ =t+h_2^{\prime }{P}_{\text{ID}}\hfill \\ =h_2^{\prime }·P_{\text{ID}}+\left[\frac{t-R_{\text{ID}}}{h_{\text{ID}}^{\prime }}·h_{\text{ID}}^{\prime }+R_{\text{ID}}\right]\hfill \\ =h_2^{\prime }·P_{\text{ID}}+R_{\text{ID}}+h_{\text{ID}}^{\prime }·P_{\text{pub}}^{\prime }.\hfill \end{array}$$

(7)

4.2. Attack 2

The adversary ${𝒜}_{\text{II}}$ will perform the following steps to forge a signature.

• (i)

The adversary    ${𝒜}_{\text{II}}$ selects a random number $t^{\prime }\in Z_n^{*}$ and computes $R^{\prime }=t^{\prime }·P$ .

(ii)

   ${𝒜}_{\text{II}}$ chooses a random number $r_{\text{ID}}^{\prime }\in Z_n^{*}$ and computes $R_{\text{ID}}^{\prime }=r_{\text{ID}}^{\prime }·P$ .

(iii)

The adversary obtains the hash values $h_1^{\prime }=H_{\mathrm{2}}(m^{\prime },R^{\prime },P_{\text{ID}},R_{\text{ID}}^{\prime })$ , $h_{\mathrm{2}}^{\prime }=H_{\mathrm{2}}(m^{\prime },R^{\prime },P_{\text{ID}},R_{\text{ID}}^{\prime },P_{\text{pub}})$ , and $h_{\text{ID}}^{\prime }=H_{\mathrm{1}}(\text{ID},P_{\text{ID}},R_{\text{ID}}^{\prime })$ .

(iv)

${𝒜}_{\text{II}}$ assesses whether $gcd(l+h_{\mathrm{1}},n)$ equals 1. If it does not hold, the signer returns to step (i).

(v)

As the the adversary is of Type II, the value of x is known. Then, ${𝒜}_{\text{II}}$ computes

$$\begin{array}{cc}& s^{\prime }={\left(t^{\prime }+h_{\mathrm{1}}^{\prime }\right)}^{-\mathrm{1}}\left(r_{\text{ID}}^{\prime }+h_{\text{ID}}^{\prime }·x+\frac{h_{\mathrm{2}}^{\prime }·P_{\text{ID}}}{P}\right)\mathrm{mod}\hspace{0.17em}n.\end{array}$$

(8)

 

The signature is $(R^{\prime },s^{\prime })$ on message $m^{\prime }$ .

(vi)

To check the validity of the signature, the verifier can perform the following verification as follows:

$$\begin{array}{cc}& s^{\prime }·\left(R^{\prime }+h_{\mathrm{1}}^{\prime }·P\right)=h_{\mathrm{2}}^{\prime }·P_{\text{ID}}+R_{\text{ID}}+h_{\text{ID}}^{\prime }·P_{\text{pub}},\end{array}$$

(9)

 

where $h_{\mathrm{1}}^{\prime }=H_{\mathrm{2}}(m^{\prime },R^{\prime },P_{\text{ID}},R_{\text{ID}}^{\prime })$ , $h_{\mathrm{2}}^{\prime }=H_{\mathrm{2}}(m^{\prime },R^{\prime },P_{\text{ID}},R_{\text{ID}}^{\prime },P_{\text{pub}})$ , and $h_{\text{ID}}^{\prime }=H_{\mathrm{1}}(\text{ID},P_{\text{ID}},R_{\text{ID}}^{\prime })$

$$\begin{array}{l}{s}^{\prime }·\left(R^{\prime }+h_{\mathrm{1}}^{\prime }·P\right)\hfill \\ \hspace{1em}\hspace{1em}={\left(t^{\prime }+h_{\mathrm{1}}^{\prime }\right)}^{-\mathrm{1}}\left(r_{\text{ID}}^{\prime }+h_{\text{ID}}^{\prime }·x+\frac{h_{\mathrm{2}}^{\prime }·P_{\text{ID}}}{P}\right)\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}\times \left(t^{\prime }·P+h_{\mathrm{1}}^{\prime }·P\right)\hfill \\ \hspace{1em}\hspace{1em}={\left(t^{\prime }+h_{\mathrm{1}}^{\prime }\right)}^{-\mathrm{1}}\left(r_{\text{ID}}^{\prime }+h_{\text{ID}}^{\prime }·x+\frac{h_{\mathrm{2}}^{\prime }·P_{\text{ID}}}{P}\right)\left(t^{\prime }+h_{\mathrm{1}}^{\prime }\right)·P\hfill \\ \hspace{1em}\hspace{1em}=\left(r_{\text{ID}}^{\prime }+h_{\text{ID}}^{\prime }·x+\frac{h_{\mathrm{2}}^{\prime }·P_{\text{ID}}}{P}\right)·P\hfill \\ \hspace{1em}\hspace{1em}=\left(r_{\text{ID}}^{\prime }·P+h_{\text{ID}}^{\prime }·x·P+h_{\mathrm{2}}^{\prime }·P_{\text{ID}}\right)\hfill \\ \hspace{1em}\hspace{1em}=R_{\text{ID}}^{\prime }+h_{\mathrm{2}}^{\prime }{P}_{\text{ID}}+h_{\text{ID}}^{\prime }·P_{\text{pub}}.\hfill \end{array}$$

(10)

5. Review of Fan et al.'s Short CLS Scheme

In this section, we briefly review the short certificateless signature scheme based on ECDLP [24]. The scheme works as follows.

Setup. Let $G_{\mathrm{1}},\hspace{0.17em}\hspace{0.17em}{G}_{\mathrm{2}}$ , and $G_T$ be three cyclic additive groups of prime order $q\le {\mathrm{2}}^k$ where k is a security parameter, and let e be an efficiently computable bilinear pairing $e:G_{\mathrm{1}}\times G_{\mathrm{2}}\to G_T$ , which satisfies the properties of bilinearity and nondegeneracy. Suppose that a message m which will be signed is an element in $Z_q^{*}$ . KGC chooses two random generators $P_{\mathrm{1}}\in G_{\mathrm{1}}$ and $P_{\mathrm{2}}\in G_{\mathrm{2}}$ and a random integer $s\in Z_q^{*}$ . It then computes $P_{\text{pub}}=s{P}_{\mathrm{2}}\in G_{\mathrm{2}}$ and $g=e(P_{\mathrm{1}},P_{\mathrm{2}})\in G_T$ . It then selects two distinct cryptographic hash functions $H_{\mathrm{1}}:\{\mathrm{0,1}{\}}^{*}\to Z_q^{*}$ and $H_{\mathrm{2}}:\{\mathrm{0,1}{\}}^{*}\times G_{\mathrm{2}}\to Z_q^{*}$ . KGC publishes the system parameters, $\text{params}=\{k,G_{\mathrm{1}},G_{\mathrm{2}},e,q,P,g,P_{\text{pub}},H_{\mathrm{1}},H_{\mathrm{2}}\}$ , and keeps its master key s secret.

User-Key Gen. A user with identity $\text{ID}$ randomly chooses $r\in Z_q^{*}$ and then computes $p{k}_{\text{ID}}=r{P}_{\mathrm{2}}$ and $p{k}_{\text{ID}}^{\prime }=r(P_{\text{pub}}+Q_{\text{ID}}{P}_{\mathrm{2}})$ where $Q_{\text{ID}}=H_{\mathrm{1}}(\text{ID})$ . The user keeps r secretly and sets $(p{k}_{\text{ID}},p{k}_{\text{ID}}^{\prime })$ as its public key.

Partial-Private-Key Gen. KGC takes $\text{params}$ , the user's partial public information $(Q_{\text{ID}},p{k}_{\text{ID}})$ as inputs, and then generates the user's partial-private key $d_{\text{ID}}=\mathrm{1}/(s+Q_{\text{ID}}+H_{\mathrm{1}}(\text{ID}\parallel p{k}_{\text{ID}}))P_{\mathrm{1}}$ . Then KGC returns $d_{\text{ID}}$ to the user via a secure manner. After receiving $d_{\text{ID}}$ , the user checks the correctness of $d_{\text{ID}}$ by examining if $e(d_{\text{ID}},P_{\text{pub}}+Q_{\text{ID}}{P}_{\mathrm{2}}+H_{\mathrm{1}}(\text{ID}\parallel p{k}_{\text{ID}})P_{\mathrm{2}})=g$ . The private key of the user is $(d_{\text{ID}},r)$ .

CL Sign. To produce the signature on message $m\in \{\mathrm{0,1}{\}}^{*}$ , the user with identity $\text{ID}$ performs the following steps:

• (i)

set $h=H_{\mathrm{2}}(m,p{k}_{\text{ID}})$ ,

(ii)

compute $S=(1/(r+h))d_{\text{ID}}$ , where S is the signature on message m of the user.

CL Verify. Given $\text{params}$ , message m, $p{k}_{\text{ID}}$ ,   $p{k}_{\text{ID}}^{\prime }$ , and the signature S on message m of the user with identity $\text{ID}$ , the signature can be verified as follows:

• (i)

let $h=H_{\mathrm{2}}(m,p{k}_{\text{ID}})$ ;

(ii)

if the following formula holds, the signature S is valid:

$$\begin{array}{l}e(S,p{k}_{\text{ID}}^{\prime }+H_{\mathrm{1}}\left(\text{ID}\parallel p{k}_{\text{ID}}\right)p{k}_{\text{ID}}\hfill \\ \hspace{1em}+h\left(P_{\text{pub}}+Q_{\text{ID}}{P}_{\mathrm{2}}+H_{\mathrm{1}}\left(\text{ID}\parallel p{k}_{\text{ID}}\right)P_{\mathrm{2}}\right))=g.\hfill \end{array}$$

(11)

6. Cryptanalysis of Fan et al.'s Short CLS Scheme

In this section, we demonstrate that the Fan et al. [24] CLS scheme is forgeable by the Strong Type I adversary; that is, adversary can replace a user's public key but is not able to obtain KGCs master secret key. ${𝒜}_{\text{I}}$ is able to retrieve the partial-private key of the user.

6.1. Attack

The ${𝒜}_{\text{I}}$ will perform the following steps.

• (i)

The adversary ${𝒜}_{\text{I}}$ chooses a random number $r^{\prime }\in Z_n^{*}$ and replaces a user's public key $P{K}_{\text{ID}}$ with $P{K}_{\text{ID}}^{*}=r^{\prime }{P}_{\mathrm{2}}$ and $P{K}_{\text{ID}}^{\prime }$ with $P{K}_{\text{ID}}^{\prime *}=r^{\prime }(P_{\text{pub}}+Q_{\text{ID}}{P}_{\mathrm{2}})$ .

(ii)

${𝒜}_{\text{I}}$ makes a strong sign query with $\text{ID},\hspace{0.17em}\hspace{0.17em}m$ , and $r^{\prime }$ as input and then the challenger returns a valid signature $S^{\prime }=(1/(r^{\prime }+h^{\prime }))d_{\text{ID}}$ where $h^{\prime }=H_{\mathrm{2}}(m,P{K}_{\text{ID}}^{*})$ .

(iii)

${𝒜}_{\text{I}}$ obtains the hash value $h^{\prime }$ on m,   $P{K}_{\text{ID}}^{*}$ by making a hash query.

(iv)

${𝒜}_{\text{I}}$ can then compute the user's partial-private key $d_{\text{ID}}=(r^{\prime }+h^{\prime })S^{\prime }$ as he knows the value of $r^{\prime }$ and $h^{\prime }$ .

7. Conclusion

The schemes discussed here are of much interest because they are free from pairing and hence can easily be applicable to WSN. But less resource consumption is not enough reason to compromise security. In this paper, security attacks have been applied on two different schemes. Tsai et al. proposed the CLS scheme without pairing which is claimed to be more efficient than the existing schemes (since pairing is always an expensive operation). An exhaustive cryptanalysis has been shown in Section 4 and the results indicate that the improved scheme by Tsai et al. does not resist against the Strong Type II attacks and hence is forgeable. Moreover, we have found that Fan et al's. CLS scheme is forgeable by the Strong Type I adversary. Therefore, to construct a secure certificateless signature scheme without bilinear pairing needs more attention.