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

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.

(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 I_DU , 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ω ,I_DPS ,_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 I_DOS 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 (I_DOS ,_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ω ,I_DOS ,_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 I_DOS and the public key _pkOS =(_POS ,_KOS ) . Let PS be the original signer with identity I_DPS 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 (I_DOS ,_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ω ,I_DOS ,_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 Δ=4^a3 +27^b2 ...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.

References

[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.