# On the Security of a Certificateless Proxy Signature Scheme with Message Recovery

Authors: Wenbo Shi; Debiao He; Peng Gong
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

A proxy signature scheme allows a proxy signer to sign messages on behalf of an original signer within a given context. It has lots of practical applications in distributed systems, grid computing, mobile agent applications, distributed shared object systems, global distribution networks, and mobile communications. Recently, Padhye et al. proposed a certificateless proxy signature scheme with message recovery and claimed the scheme is secure against both of the two types of adversaries. However, in this paper, we will show that Padhye et al.’s scheme is not secure against the Type I adversary. The analysis shows their scheme is not secure for practical applications.


---

## Body

## 1. Introduction

The proxy signature scheme is an important cryptographic mechanism, which was introduced first by Mambo et al. [1] in 1996. In the scheme, the original signer could delegate his signing capability to the proxy signer. After that, the proxy signer could sign a message on behalf of the original signer. The proxy signature has been widely used in distributed shared object systems, grid computing, mobile agent environment and global distribution networks, where delegation of rights is quite common [2, 3].Recently, certificateless public key cryptography was studied widely since it could solve the certificate management problem in the traditional public key cryptography and the problem in the identity-based public key cryptography. Many certificateless key agreement schemes [4–6] and certificateless signature schemes [7–9] have been proposed for different applications. To satisfy the applications in the certificateless environment, many certificateless proxy signature (CLPS) schemes [10–17] have been proposed. In 2005, Li et al. [10] proposed the first CLPS scheme. Later, Yap et al. [11] and Lu et al. [12] found that Li et al.’s scheme is not secure at all. Lu et al. [12] also proposed an improved CLPS scheme. In 2009, Chen et al. [13] proposed the first security model for the CLPS scheme. They also proposed a new CLPS scheme and demonstrated it was provably secure in the security model. To improve performance, several other CLPS schemes [14–16] with provably security were also proposed. All the above CLPS schemes are based on bilinear pairings. The performance of these schemes [10–16] is not satisfactory since the bilinear pairing operation is very complicated. To avoid bilinear pairing operation, Padhye and Tiwari [17] proposed a certificateless proxy signature scheme with message recovery. They also proved their scheme is secure against chosen message and identity attacks in the random oracle model. In this letter, we will show and discuss the security of Padhye et al.’s scheme and show it is not secure against the Type I adversary.The rest of the paper is organized as follows. Section2 gives a review of Padhye et al.’s scheme. Section 3 discusses the security problem in Padhye et al.’s scheme. Finally, we conclude the paper in Section 4.


## 2. Review of Padhye et al.’s Scheme

In this section, we will review Padhye et al.’s scheme. For convenience, some notations used in the paper are described in the Abbreviations section.Padhye et al.’s CLPS scheme is composed of ten algorithms, which areSetup, Partial-Private-Key-Extract, Set-Secret-Value,. Set-Private-Key, Set-Public-Key, DelGen, DelVerif, PKGen, PSign, and PSVerif. The details of these algorithms are described as follows.Setup. Taking a security parameter k as inputs, the KGC runs this algorithm to generate the system parameters. (1)
KGC chooses ak-bit prime p, generates an elliptic curve E over finite field Fp, generates a group G of elliptic curve points on E with prime order n, and determines a generator P of G.(2)
KGC chooses the master keymk=x∈Zn* and computes the master public key Ppub=x·P.(3)
KGC chooses four cryptographic secure hash functionsHi:{0,1}*→Zn*, where i=1,2,3,4.(4)
KGC publishesparams={Fp,E,G,P,Ppub,H1,H2,H3,H4} as system parameters and secretly keeps the master key x.Partial-Private-Key-Extract. Taking a user’s identity IDU, system parameters params, and the master key x as inputs, KGC runs the algorithm to generate the user’s partial private key.(1)
KGC generates a random numberkU∈Zn* and computes KU=kU·P and hU=H1(IDU,KU).(2)
KGC computesdU=(kU+hUs)modn and sends (dU,KU) to the user through a secure channel.Set-Secret-Value. Taking system parameters params as inputs, the user U runs the algorithm to generate the secure value.(1)
U generates a random number xU∈Zn* and computes PU=xU·P.(2)
U sets xU as the secret value.Set-Private-Key. Taking the secret value xU and the partial private key dU as inputs, the user sets skU=(xU,dU) as his private key.Set-Public-Key. Taking PU and KU as inputs, the user sets pkU=(PU,KU) as his public key.DelGen. Taking system parameters params, the original signer OS’s private key skOS=(xOS,dOS), the proxy signer PS’s public key pkOS=(POS,KOS), and a warrant message mω as inputs, the original signer OS runs this algorithm to generate a delegation on the warrant message mω.(1)
OS generates a random number rOS∈Zn* and computes ROS=rOS·P.(2)
OS computes σOS=((xOS+dOS)eOS+rOS)modn and sends the delegation (mω,ROS,σOS) to the proxy signer PS, where eOS=H2(mω,IDOS,KOS,POS,ROS).DelVerif. Take the delegation (mω,ROS,σOS), system parameters params, and OS’s public key pkOS=(POS,KOS) as inputs; PS runs the algorithm to verify the validity of the delegation.(1)
PS computes eOS=H2(mω,IDOS,KOS,POS,ROS) and hOS=H1(IDOS,KOS).(2)
PS checks whether the equation σOS·P=eOS(POS+KOS+hOSPpub)+ROS holds. If it holds, PS accepts the delegation; otherwise, PS rejects the delegation.PKGen. Taking system parameters params, the delegation (mω,ROS,σOS), and PS’s private key skPS=(xPS,dPS) as inputs, PS runs the algorithm to generate his proxy private key.(1)
PS computes ePS=H3(mω,IDPS,KPS,PPS).(2)
PS computes DPS=(σOS+ePS(xPS+dPS))modn and sets DPS as the proxy key.PSign. Taking a message m∈{0,1}*, system parameters params, and the proxy private key DPS as inputs, PS runs this algorithm to generate a proxy signature.(1)
PS generates a random number rPS∈Zn* and computes RPS=rPS·P.(2)
PS computes tPS=(m∣∣H4(m)+(RPS)x)modn, where (RPS)x denotes the x-coordinates of the elliptic curve group point RPS.(3)
PS computes e=H5(tPS,POS,KPS,PPS) and σPS=(rPS-eDPS)modn.(4)
PS outputs (mω,σOS,ROS,tPS,σPS) as the proxy signature.PSVerif. Taking the proxy signature (mω,σOS,ROS,tPS,σPS), the message m, OS’s public key pkOS=(POS,KOS), PS’s public key pkPS=(PPS,KPS), and system parameters params as inputs, the verifier V runs this algorithm to verify the validity of the proxy signature.(1)
V computes eOS=H2(mω,IDOS,KOS,POS,ROS), hOS=H1(IDOS,KOS), ePS=H3(mω,IDPS,KPS,PPS), hPS=H1(IDPS,KPS), and e=H5(tPS,POS,KPS,PPS).(2)
V computes ∣∣H4(m)=tPS-(σPS·P+e(eOS(POS+KOS+hOS·Ppub)+ROS + ePS(PPS + KPS + hPS·Ppub)))x.(3)
V checks whether the hash result of the recovered m is equal to H4(m). If they are equal, V accepts the signature; otherwise, V rejects the signature.


## 3. Security Analysis of Padhye et al.’s Scheme

There are two types of adversaries with different capabilities in CLPS schemes. They are known as Type I adversaries and Type II adversaries. The Type I adversaryAI models an outsider adversary, who could replace the public key of any user with a value of his choice, but he does not have access to the master key. The Type II adversary AII models the malicious KGC who has access to the master key, but he cannot replace the user’s public key replacement. Padhye et al. claimed their scheme was secure against both of the two types of adversaries. In this section, we will show that a Type I adversary AI could generate a legal delegation of any warrant message and a legal proxy signature of any message.


### 3.1. Attack on the Delegation

LetOS be the original signer with identity IDOS and the public key pkOS=(POS,KOS). Let AI be a Type I adversary. AI could generate a proxy signature of a message m and the warrant message mω through the following steps.(1)
AI generates a random number lA∈Zn* and computes hOS=H1(IDOS,KOS) and POS′=lA·P-KOS-hOS·Ppub.(2)
AI replaces pkOS=(POS,KOS) with pkOS′=(POS′,KOS).(3)
AI generates a random number rA∈Zn* and computes RA=rA·P.(4)
AI computes σA=(lAeA+rA)modn and sends the delegation (mω,RA,σA) to the proxy signer PS, where eA=H2(mω,IDOS,KOS,POS′,RA).SincePOS′=lA·P-KOS-hOS·Ppub and RA=rA·P, then we have
(1)eA(POS′+KOS+hOSPpub)+RA====eA(lA·P-KOS-hOS·Ppub+KOS+hOSPpub)+rA·P+rA·P====eA·lA·P+rA·P=(eA·lA+rA)P====σA·P.Therefore, the generated delegation could pass the proxy signerPS’s verification and AI generates a delegation of a warrant message mω successfully.


### 3.2. Attack on the Proxy Signature

LetOS be the original signer with identity IDOS and the public key pkOS=(POS,KOS). Let PS be the original signer with identity IDPS and the public key pkPS=(PPS,KPS). Let AI be a Type I adversary. AI could generate a delegation of a warrant message mω through the following steps.(1)
AI generates two random number lOS,lPS∈Zn* and computes hOS=H1(IDOS,KOS), hPS=H1(IDPS,KPS), POS′=lOS·P-KOS-hOS·Ppub, and PPS′=lPS·P-KPS-hPS·Ppub.(2)
AI replaces pkOS=(POS,KOS) and pkPS=(PPS,KPS) with pkOS′=(POS′,KOS) and pkPS′=(PPS′,KOS) separately.(3)
AI generates a random number rOS∈Zn* and computes ROS=rOS·P,     eOS=H2(mω,IDOS,KOS,POS′,RA) and σOS=(lOSeOS+rOS)modn.(4)
AI generates a random number rPS∈Zn* and computes RPS=rPS·P, tPS=(m∣∣H4(m)+(RPS)x)modn, ePS=H3(mω,IDPS,KPS,PPS′), e=H5(tPS,POS′,KPS,PPS′) and σPS=(rPS-e(σOS+ePSlPS))modn.(5)
PS outputs (mω,σOS,ROS,tPS,σPS) as the proxy signature.SincePOS′=lOS·P-KOS-hOS·Ppub, PPS′=lPS·P-KPS-hPS·Ppub, σOS=(lOSeOS+rOS)modn, ROS=rOS·P and RPS=rPS·P, then we have
(2)σPS·P+e(eOS(POS′+KOS+hOS·Ppub)·P+e+ROS+ePS(PPS′+KPS+hPS·Ppub))=(rPS-e(σOS+ePSlPS))·P=+e(eOS(lOS·P-KOS-hOS·Ppub+KOS+hOS·Ppub)+++++rOS·P+ePS(lPS·P-KPS-hPS+rOS·P+ePS+++++·Ppub+KPS+hPS·Ppub))=(rPS-e(σOS+ePSlPS))·P=+e(eOSlOS·P+rOS·P+ePSlPS·P)=rPS·P-e(σOS+ePSlPS)·P=+e((lOSeOS+rOS)+ePSlPS)·P=rPS·P-e(σOS+ePSlPS)·P=+e(σOS+ePSlPS)·P=rPS·P.
Therefore, the generated signature could pass the verification and AI generates a signature successfully.


## 3.1. Attack on the Delegation

LetOS be the original signer with identity IDOS and the public key pkOS=(POS,KOS). Let AI be a Type I adversary. AI could generate a proxy signature of a message m and the warrant message mω through the following steps.(1)
AI generates a random number lA∈Zn* and computes hOS=H1(IDOS,KOS) and POS′=lA·P-KOS-hOS·Ppub.(2)
AI replaces pkOS=(POS,KOS) with pkOS′=(POS′,KOS).(3)
AI generates a random number rA∈Zn* and computes RA=rA·P.(4)
AI computes σA=(lAeA+rA)modn and sends the delegation (mω,RA,σA) to the proxy signer PS, where eA=H2(mω,IDOS,KOS,POS′,RA).SincePOS′=lA·P-KOS-hOS·Ppub and RA=rA·P, then we have
(1)eA(POS′+KOS+hOSPpub)+RA====eA(lA·P-KOS-hOS·Ppub+KOS+hOSPpub)+rA·P+rA·P====eA·lA·P+rA·P=(eA·lA+rA)P====σA·P.Therefore, the generated delegation could pass the proxy signerPS’s verification and AI generates a delegation of a warrant message mω successfully.


## 3.2. Attack on the Proxy Signature

LetOS be the original signer with identity IDOS and the public key pkOS=(POS,KOS). Let PS be the original signer with identity IDPS and the public key pkPS=(PPS,KPS). Let AI be a Type I adversary. AI could generate a delegation of a warrant message mω through the following steps.(1)
AI generates two random number lOS,lPS∈Zn* and computes hOS=H1(IDOS,KOS), hPS=H1(IDPS,KPS), POS′=lOS·P-KOS-hOS·Ppub, and PPS′=lPS·P-KPS-hPS·Ppub.(2)
AI replaces pkOS=(POS,KOS) and pkPS=(PPS,KPS) with pkOS′=(POS′,KOS) and pkPS′=(PPS′,KOS) separately.(3)
AI generates a random number rOS∈Zn* and computes ROS=rOS·P,     eOS=H2(mω,IDOS,KOS,POS′,RA) and σOS=(lOSeOS+rOS)modn.(4)
AI generates a random number rPS∈Zn* and computes RPS=rPS·P, tPS=(m∣∣H4(m)+(RPS)x)modn, ePS=H3(mω,IDPS,KPS,PPS′), e=H5(tPS,POS′,KPS,PPS′) and σPS=(rPS-e(σOS+ePSlPS))modn.(5)
PS outputs (mω,σOS,ROS,tPS,σPS) as the proxy signature.SincePOS′=lOS·P-KOS-hOS·Ppub, PPS′=lPS·P-KPS-hPS·Ppub, σOS=(lOSeOS+rOS)modn, ROS=rOS·P and RPS=rPS·P, then we have
(2)σPS·P+e(eOS(POS′+KOS+hOS·Ppub)·P+e+ROS+ePS(PPS′+KPS+hPS·Ppub))=(rPS-e(σOS+ePSlPS))·P=+e(eOS(lOS·P-KOS-hOS·Ppub+KOS+hOS·Ppub)+++++rOS·P+ePS(lPS·P-KPS-hPS+rOS·P+ePS+++++·Ppub+KPS+hPS·Ppub))=(rPS-e(σOS+ePSlPS))·P=+e(eOSlOS·P+rOS·P+ePSlPS·P)=rPS·P-e(σOS+ePSlPS)·P=+e((lOSeOS+rOS)+ePSlPS)·P=rPS·P-e(σOS+ePSlPS)·P=+e(σOS+ePSlPS)·P=rPS·P.
Therefore, the generated signature could pass the verification and AI generates a signature successfully.


## 4. Conclusion

In this paper, we have demonstrated that Padhye et al.’s CLPS scheme with message recovery is not secure against the Type I adversary by giving concrete attacks. The analysis shows their scheme is not secure for practical applications. We will try to give a countermeasure to overcome weaknesses in their scheme in the future.



---

*Source: 761694-2013-04-23.xml*