Content area
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.
(ProQuest: ... denotes non-US-ASCII text omitted.)
Wenbo Shi 1 and Debiao He 2 and Peng Gong 3
Recommended by Wanquan Liu
1, Department of Electronic Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China
2, School of Mathematics and Statistics, Wuhan University, Wuhan, Hubei 430072, China
3, National Key Laboratory of Mechatronic Engineering and Control, School of Mechatronical Engineering, Beijing Institute of Technology, Beijing 100081, China
Received 19 January 2013; Accepted 5 April 2013
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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. Section 2 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 are Setup , 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 a k -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 key mk=x∈Zn* and computes the master public key Ppub =x·P .
(3) KGC chooses four cryptographic secure hash functions Hi :{0,1}* [arrow right]Zn* , where i=1,2,3,4 .
(4) KGC publishes params={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 number kU ∈Zn* and computes KU =kU ·P and hU =H1 (IDU ,KU ) .
(2) KGC computes dU =(kU +hU s)...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 adversary AI 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
Let OS 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[variant prime] =lA ·P-KOS -hOS ·Ppub .
(2) AI replaces pkOS =(POS ,KOS ) with pkOS[variant prime] =(POS[variant prime] ,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[variant prime] ,RA ) .
Since POS[variant prime] =lA ·P-KOS -hOS ·Ppub and RA =rA ·P , then we have [figure omitted; refer to PDF]
Therefore, the generated delegation could pass the proxy signer PS 's verification and AI generates a delegation of a warrant message mω successfully.
3.2. Attack on the Proxy Signature
Let OS 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[variant prime] =lOS ·P-KOS -hOS ·Ppub , and PPS[variant prime] =lPS ·P-KPS -hPS ·Ppub .
(2) AI replaces pkOS =(POS ,KOS ) and pkPS =(PPS ,KPS ) with pkOS[variant prime] =(POS[variant prime] ,KOS ) and pkPS[variant prime] =(PPS[variant prime] ,KOS ) separately.
(3) AI generates a random number rOS ∈Zn* and computes ROS =rOS ·P , eOS =H2 (mω ,IDOS ,KOS ,POS[variant prime] ,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[variant prime] ) , e=H5 (tPS ,POS[variant prime] ,KPS ,PPS[variant prime] ) and σPS =(rPS -e(σOS +ePSlPS ))...modn .
(5) PS outputs (mω ,σOS ,ROS ,tPS ,σPS ) as the proxy signature.
Since POS[variant prime] =lOS ·P-KOS -hOS ·Ppub , PPS[variant prime] =lPS ·P-KPS -hPS ·Ppub , σOS =(lOSeOS +rOS )...modn , ROS =rOS ·P and RPS =rPS ·P , then we have [figure omitted; refer to PDF] 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.
Abbreviations
p :
A large prime number
F p :
A finite field
E :
An elliptic curve defined by the equation y2 =x3 +ax+b , where a,b∈Fp and Δ=4a3 +27b2 ...0;0
G :
The group consists of points on E and the infinite point O
n :
The order of G , where n is a large prime number
P :
A generator of group G
( x , P pub ) :
The master/public key pair of the key generation centre (KGC)
U :
A user
I D U :
The identity of U
d U :
The partial private key of U
x U :
The secret value of U
sk U :
The private key of U
pk U :
The public key of U
OS :
The original signer
PS :
The proxy signer
D PS :
The proxy key.
Acknowledgments
The authors thank the editors and the anonymous reviewers for their valuable comments. This research was supported by National Natural Science Foundation of China (nos. 61202447 and 61201180), Natural Science Foundation of Hebei Province of China (no. F2013501066), Northeastern University at Qinhuangdao Science and Technology Support Program (no. xnk201307), Beijing Natural Science Foundation (no. 4132055), and Excellent Young Scholars Research Fund of Beijing Institute of Technology.
[1] M. Mambo, K. Usuda, E. Okamoto, "Proxy signatures: delegation of the power to sign messages," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , vol. E79-A, no. 9, pp. 1338-1354, 1996.
[2] S. F. Tzeng, M. S. Hwang, "Digital signature with message recovery and its variants based on elliptic curve discrete logarithm problem," Computer Standards and Interfaces , vol. 26, no. 2, pp. 61-71, 2004.
[3] M. S. Hwang, C. C. Lee, S. F. Tzeng, "A new proxy signature scheme for a specified group," Information Sciences , vol. 227, pp. 102-115, 2013.
[4] D. He, Y. Chen, J. Chen, R. Zhang, W. Han, "A new two-round certificateless authenticated key agreement protocol without bilinear pairings," Mathematical and Computer Modelling , vol. 54, no. 11-12, pp. 3143-3152, 2011.
[5] D. He, J. Chen, J. Hu, "A pairing-free certificateless authenticated key agreement protocol," International Journal of Communication Systems , vol. 25, no. 2, pp. 221-230, 2012.
[6] D. He, S. Padhye, J. Chen, "An efficient certificateless two-party authenticated key agreement protocol," Computers & Mathematics with Applications , vol. 64, no. 6, pp. 1914-1926, 2012.
[7] D. He, J. Chen, R. Zhang, "An efficient and provably-secure certificateless signature scheme without bilinear pairings," International Journal of Communication Systems , vol. 25, no. 11, pp. 1432-1442, 2012.
[8] D. He, Y. Chen, J. Chen, "A provably secure certificateless proxy signature scheme without pairings," Mathematical and Computer Modelling , vol. 57, no. 9-10, pp. 2510-2518, 2013.
[9] D. He, B. Huang, J. Chen, "A new certificateless short signature scheme," IET Information Security . In press
[10] X. Li, K. Chen, L. Sun, "Certificateless signature and proxy signature schemes from bilinear pairings," Lithuanian Mathematical Journal , vol. 45, no. 1, pp. 76-83, 2005.
[11] W. Yap, S. Heng, B. Goi, "Cryptanalysis of some proxy signature schemes without certificates," in Proceedings of the 1st Workshop on Information Security Theory and Practices (WISTP '07), vol. 4462, of Lecture Notes in Computer Science, pp. 115-126, Springer, Heraklion, Greece, May 2007.
[12] R. Lu, D. He, C. Wang, "Cryptanalysis and improvement of a certificateless proxy signature scheme from bilinear pairings," in Proceedings of the 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD '07), pp. 285-290, Qingdao, China, July 2007.
[13] H. Chen, F.-T. Zhang, R.-S. Song, "Certificateless proxy signature scheme with provable security," Journal of Software , vol. 20, no. 3, pp. 692-701, 2009.
[14] H. Xiong, F. Li, Z. Qin, "A provably secure proxy signature scheme in certificateless cryptography," Informatica , vol. 21, no. 2, pp. 277-294, 2010.
[15] L. Zhang, F. Zhang, Q. Wu, "Delegation of signing rights using certificateless proxy signatures," Information Sciences , vol. 184, pp. 298-309, 2012.
[16] S. Seo, K. Choi, J. Hwang, S. Kim, "Delegation of signing rights using certificateless proxy signatures," Information Sciences , vol. 188, pp. 321-337, 2012.
[17] S. Padhye, N. Tiwari, "ECDLP-based certificateless proxy signature scheme with message recovery," Transactions on Emerging Telecommunications Technologies , 2012.
Copyright © 2013 Wenbo Shi et al. Wenbo Shi et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.