May  2020, 14(2): 177-205. doi: 10.3934/amc.2020015

Malleability and ownership of proxy signatures: Towards a stronger definition and its limitations

1. 

Department of Computer Science and Automation, Indian Institute of Science, India

2. 

Izmir Institute of Technology, Urla, Izmir, 35430 Turkey

Received  July 2017 Revised  January 2018 Published  September 2019

Proxy signature is a cryptographic primitive that allows an entity to delegate singing rights to another entity. Noticing the ad-hoc nature of security analysis prevalent in the existing literature, Boldyreva, Palacio and Warinschi proposed a formal security model for proxy signature. We revisit their proposed security definition in the context of the most natural construction of proxy signature – delegation-by-certificate. Our analysis indicates certain limitations of their definition that arise due to malleability of proxy signature as well as signature ownership in the context of standard signature. We propose a stronger definition of proxy signature to address these issues. However, we observe that the natural reductionist security argument of the delegation-by certificate proxy signature construction under this definition seems to require a rather unnatural security property for a standard signature.

Citation: Sanjit Chatterjee, Berkant Ustaoğlu. Malleability and ownership of proxy signatures: Towards a stronger definition and its limitations. Advances in Mathematics of Communications, 2020, 14 (2) : 177-205. doi: 10.3934/amc.2020015
References:
[1]

A. Bakker, M. van Steen and A. S. Tanenbaum, A law-abiding peer-to-peer network for free-software distribution, in IEEE International Symposium on Network Computing and Applications NCA 2001, Cambridge, MA, USA, IEEE Computer Society, (2001), 60–67. doi: 10.1109/NCA.2001.962516.  Google Scholar

[2]

L. Bassham, W. Polk and R. Housley, Algorithms and identifiers for the internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 3279 (Proposed Standard), (2002). Updated by RFCs 4055, 4491, 5480, 5758. doi: 10.17487/rfc3279.  Google Scholar

[3]

M. Bellare and P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, in 11 CCS'93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, ACM, (1993), 62–73. doi: 10.1145/168588.168596.  Google Scholar

[4]

D. J. Bernstein, Multi-User Schnorr Security, Revisited, Cryptology ePrint Archive, Report 2015/996, 2015, http://eprint.iacr.org/. Google Scholar

[5]

S. Blake-Wilson and A. Menezes, Unknown key-share attacks on the station-to-station (sts) protocol, In Public Key Cry.Ptography, (1999), 154–170. doi: 10.1007/3-540-49162-7_12.  Google Scholar

[6]

A. Boldyreva, A. Palacio and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, Cryptology ePrint Archive, Report 2003/096, 2003, http://eprint.iacr.org/. Google Scholar

[7]

A. BoldyrevaA. Palacio and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, Journal of Cryptology, 25 (2012), 57-115.  doi: 10.1007/s00145-010-9082-x.  Google Scholar

[8]

Certicom Research, SEC 1: Elliptic Curve Cryptography, Version 2.0, 2009. Available at: http://www.secg.org/. Google Scholar

[9]

D. Cooper, S. Santesson, S. Farrell, S. Boeyen, R. Housley and W. Polk, Internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 5280 (Proposed Standard), 2008. Updated by RFC 6818 RFC 8398, RFC 8399. doi: 10.17487/rfc5280.  Google Scholar

[10]

D. DerlerC. Hanser and D. Slamanig, Privacy-enhancing proxy signatures from non-interactive anonymous credentials, Data and Applications Security and Privacy, 8566 (2014), 49-65.  doi: 10.1007/978-3-662-43936-4_4.  Google Scholar

[11]

I. Foster, C. Kesselman, G. Tsudik and S. Tuecke, A security architecture for computational grids, in CCS '98 Proceedings of the 5th ACM Conference on Computer and Communications Security, San Francisco, CA, USA, ACM, (1998), 83–92. doi: 10.1145/288090.288111.  Google Scholar

[12]

S. GalbraithJ. Malone-Lee and N. P. Smart, Public key signatures in the multi-user setting, Information Processing Letters, 83 (2002), 263-266.  doi: 10.1016/S0020-0190(01)00338-6.  Google Scholar

[13]

S. Goldwasser, S. Micali and R. Rivest, A "paradoxical" solution to the signature problem, Proceedings of the IEEE 25th Annual Symposium on Foundations of Computer Science, (1984), 441–448. doi: 10.1109/SFCS.1984.715946.  Google Scholar

[14]

S. GoldwasserS. Micali and R. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. of Computing, 17 (1988), 281-308.  doi: 10.1137/0217017.  Google Scholar

[15]

B. Jens-MatthiasS. Röhrich and R. Steinwandt, Key substitution attacks revisited: Taking into account malicious signers, International Journal of Information Security, 5 (2006), 30-36.   Google Scholar

[16]

E. Kiltz, D. Masny and J. Pan, Schnorr Signatures in the Multi-User Setting, Cryptology ePrint Archive, Report 2015/1122, 2015, http://eprint.iacr.org/. Google Scholar

[17]

N. Koblitz and A. Menezes, Another look at security definitions, Advances in Mathematics of Communications, 7 (2013), 1-38.  doi: 10.3934/amc.2013.7.1.  Google Scholar

[18]

A. K. Lenstra, J. P. Hughes, M. Augier, J. W. Bos, T. Kleinjung and C. Wachter, Ron was Wrong, Whit is Right, Cryptology ePrint Archive, Report 2012/064, 2012, http://eprint.iacr.org/. Google Scholar

[19]

M. Mambo, K. Usuda and E. Okamoto, Proxy signatures for delegating signing operation, in CCS '96, Proceedings of the 3rd ACM Conference on Computer and Communications Security, New Delhi, India, ACM, (1996), 48–57. doi: 10.1145/238168.238185.  Google Scholar

[20]

U. Maurer, Intrinsic limitations of digital signatures and how to cope with them, in Information Security, (2003), 180–192. doi: 10.1007/10958513_14.  Google Scholar

[21]

A. Menezes and N. Smart, Security of signature schemes in a multi-user setting, Designs, Codes and Cryptography, 33 (2004), 261-274.  doi: 10.1023/B:DESI.0000036250.18062.3f.  Google Scholar

[22]

NIST National Institute of Standards and Technology, Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, 2007. Available via: http://csrc.nist.gov/publications/PubsSPs.html. Google Scholar

[23]

NIST National Institute of Standards and Technology, Digital Signature Standard (DSS) (FIPS 186-4), 2013. Google Scholar

[24]

T. Pornin and J. P. Stern, Digital signatures do not guarantee exclusive ownership, Applied Cryptography and Network Security, 3531 (2005), 138-150.  doi: 10.1007/11496137_10.  Google Scholar

[25]

M. Stevens, A. Lenstra and B. de Weger, Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities, in Advances in Cryptology—EUROCRYPT 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4515 (2007), 1–22. doi: 10.1007/978-3-540-72540-4_1.  Google Scholar

[26]

M. Stevens, A. Sotirov, J. Appelbaum, A. Lenstra, D. Molnar, D. A. Osvik and B. de Weger, Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate, in Advances in Cryptology-CRYPTO 2009, Lecture Notes in Comput. Sci., Springer, Berlin, 5677 (2009), 55–69. doi: 10.1007/978-3-642-03356-8_4.  Google Scholar

[27]

S. Vaudenay, Digital signature schemes with domain parameters: Yet another parameter issue in ECDSA, in ACISP, Lecture Notes in Computer Science, Springer, 3108 (2004), 188–199. doi: 10.1007/978-3-540-27800-9_17.  Google Scholar

[28]

P. Yee, Updates to the internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 6818 (Proposed Standard), (2013), updates: RFC 5280. doi: 10.17487/rfc6818.  Google Scholar

[29]

The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.0), 2017, http://www.sagemath.org. Google Scholar

show all references

References:
[1]

A. Bakker, M. van Steen and A. S. Tanenbaum, A law-abiding peer-to-peer network for free-software distribution, in IEEE International Symposium on Network Computing and Applications NCA 2001, Cambridge, MA, USA, IEEE Computer Society, (2001), 60–67. doi: 10.1109/NCA.2001.962516.  Google Scholar

[2]

L. Bassham, W. Polk and R. Housley, Algorithms and identifiers for the internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 3279 (Proposed Standard), (2002). Updated by RFCs 4055, 4491, 5480, 5758. doi: 10.17487/rfc3279.  Google Scholar

[3]

M. Bellare and P. Rogaway, Random oracles are practical: A paradigm for designing efficient protocols, in 11 CCS'93, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, ACM, (1993), 62–73. doi: 10.1145/168588.168596.  Google Scholar

[4]

D. J. Bernstein, Multi-User Schnorr Security, Revisited, Cryptology ePrint Archive, Report 2015/996, 2015, http://eprint.iacr.org/. Google Scholar

[5]

S. Blake-Wilson and A. Menezes, Unknown key-share attacks on the station-to-station (sts) protocol, In Public Key Cry.Ptography, (1999), 154–170. doi: 10.1007/3-540-49162-7_12.  Google Scholar

[6]

A. Boldyreva, A. Palacio and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, Cryptology ePrint Archive, Report 2003/096, 2003, http://eprint.iacr.org/. Google Scholar

[7]

A. BoldyrevaA. Palacio and B. Warinschi, Secure proxy signature schemes for delegation of signing rights, Journal of Cryptology, 25 (2012), 57-115.  doi: 10.1007/s00145-010-9082-x.  Google Scholar

[8]

Certicom Research, SEC 1: Elliptic Curve Cryptography, Version 2.0, 2009. Available at: http://www.secg.org/. Google Scholar

[9]

D. Cooper, S. Santesson, S. Farrell, S. Boeyen, R. Housley and W. Polk, Internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 5280 (Proposed Standard), 2008. Updated by RFC 6818 RFC 8398, RFC 8399. doi: 10.17487/rfc5280.  Google Scholar

[10]

D. DerlerC. Hanser and D. Slamanig, Privacy-enhancing proxy signatures from non-interactive anonymous credentials, Data and Applications Security and Privacy, 8566 (2014), 49-65.  doi: 10.1007/978-3-662-43936-4_4.  Google Scholar

[11]

I. Foster, C. Kesselman, G. Tsudik and S. Tuecke, A security architecture for computational grids, in CCS '98 Proceedings of the 5th ACM Conference on Computer and Communications Security, San Francisco, CA, USA, ACM, (1998), 83–92. doi: 10.1145/288090.288111.  Google Scholar

[12]

S. GalbraithJ. Malone-Lee and N. P. Smart, Public key signatures in the multi-user setting, Information Processing Letters, 83 (2002), 263-266.  doi: 10.1016/S0020-0190(01)00338-6.  Google Scholar

[13]

S. Goldwasser, S. Micali and R. Rivest, A "paradoxical" solution to the signature problem, Proceedings of the IEEE 25th Annual Symposium on Foundations of Computer Science, (1984), 441–448. doi: 10.1109/SFCS.1984.715946.  Google Scholar

[14]

S. GoldwasserS. Micali and R. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. of Computing, 17 (1988), 281-308.  doi: 10.1137/0217017.  Google Scholar

[15]

B. Jens-MatthiasS. Röhrich and R. Steinwandt, Key substitution attacks revisited: Taking into account malicious signers, International Journal of Information Security, 5 (2006), 30-36.   Google Scholar

[16]

E. Kiltz, D. Masny and J. Pan, Schnorr Signatures in the Multi-User Setting, Cryptology ePrint Archive, Report 2015/1122, 2015, http://eprint.iacr.org/. Google Scholar

[17]

N. Koblitz and A. Menezes, Another look at security definitions, Advances in Mathematics of Communications, 7 (2013), 1-38.  doi: 10.3934/amc.2013.7.1.  Google Scholar

[18]

A. K. Lenstra, J. P. Hughes, M. Augier, J. W. Bos, T. Kleinjung and C. Wachter, Ron was Wrong, Whit is Right, Cryptology ePrint Archive, Report 2012/064, 2012, http://eprint.iacr.org/. Google Scholar

[19]

M. Mambo, K. Usuda and E. Okamoto, Proxy signatures for delegating signing operation, in CCS '96, Proceedings of the 3rd ACM Conference on Computer and Communications Security, New Delhi, India, ACM, (1996), 48–57. doi: 10.1145/238168.238185.  Google Scholar

[20]

U. Maurer, Intrinsic limitations of digital signatures and how to cope with them, in Information Security, (2003), 180–192. doi: 10.1007/10958513_14.  Google Scholar

[21]

A. Menezes and N. Smart, Security of signature schemes in a multi-user setting, Designs, Codes and Cryptography, 33 (2004), 261-274.  doi: 10.1023/B:DESI.0000036250.18062.3f.  Google Scholar

[22]

NIST National Institute of Standards and Technology, Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, 2007. Available via: http://csrc.nist.gov/publications/PubsSPs.html. Google Scholar

[23]

NIST National Institute of Standards and Technology, Digital Signature Standard (DSS) (FIPS 186-4), 2013. Google Scholar

[24]

T. Pornin and J. P. Stern, Digital signatures do not guarantee exclusive ownership, Applied Cryptography and Network Security, 3531 (2005), 138-150.  doi: 10.1007/11496137_10.  Google Scholar

[25]

M. Stevens, A. Lenstra and B. de Weger, Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities, in Advances in Cryptology—EUROCRYPT 2007, Lecture Notes in Comput. Sci., Springer, Berlin, 4515 (2007), 1–22. doi: 10.1007/978-3-540-72540-4_1.  Google Scholar

[26]

M. Stevens, A. Sotirov, J. Appelbaum, A. Lenstra, D. Molnar, D. A. Osvik and B. de Weger, Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate, in Advances in Cryptology-CRYPTO 2009, Lecture Notes in Comput. Sci., Springer, Berlin, 5677 (2009), 55–69. doi: 10.1007/978-3-642-03356-8_4.  Google Scholar

[27]

S. Vaudenay, Digital signature schemes with domain parameters: Yet another parameter issue in ECDSA, in ACISP, Lecture Notes in Computer Science, Springer, 3108 (2004), 188–199. doi: 10.1007/978-3-540-27800-9_17.  Google Scholar

[28]

P. Yee, Updates to the internet X.509 public key infrastructure certificate and certificate revocation list (CRL) profile, RFC 6818 (Proposed Standard), (2013), updates: RFC 5280. doi: 10.17487/rfc6818.  Google Scholar

[29]

The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.0), 2017, http://www.sagemath.org. Google Scholar

Figure 1.  Different attack scenarios
[1]

Palash Sarkar, Subhadip Singha. Verifying solutions to LWE with implications for concrete security. Advances in Mathematics of Communications, 2021, 15 (2) : 257-266. doi: 10.3934/amc.2020057

[2]

Roberto Civino, Riccardo Longo. Formal security proof for a scheme on a topological network. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021009

[3]

Palash Sarkar, Subhadip Singha. Classical reduction of gap SVP to LWE: A concrete security analysis. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021004

[4]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228

[5]

Pengyu Chen. Periodic solutions to non-autonomous evolution equations with multi-delays. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 2921-2939. doi: 10.3934/dcdsb.2020211

[6]

Yuta Ishii, Kazuhiro Kurata. Existence of multi-peak solutions to the Schnakenberg model with heterogeneity on metric graphs. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021035

[7]

Yongkun Wang, Fengshou He, Xiaobo Deng. Multi-aircraft cooperative path planning for maneuvering target detection. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021050

[8]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[9]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037

[10]

Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021019

[11]

Shoufeng Ji, Jinhuan Tang, Minghe Sun, Rongjuan Luo. Multi-objective optimization for a combined location-routing-inventory system considering carbon-capped differences. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021051

[12]

Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066

[13]

Kazeem Olalekan Aremu, Chinedu Izuchukwu, Grace Nnenanya Ogwo, Oluwatosin Temitope Mewomo. Multi-step iterative algorithm for minimization and fixed point problems in p-uniformly convex metric spaces. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2161-2180. doi: 10.3934/jimo.2020063

[14]

Hideaki Takagi. Extension of Littlewood's rule to the multi-period static revenue management model with standby customers. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2181-2202. doi: 10.3934/jimo.2020064

[15]

Ru Li, Guolin Yu. Strict efficiency of a multi-product supply-demand network equilibrium model. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2203-2215. doi: 10.3934/jimo.2020065

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (515)
  • HTML views (1122)
  • Cited by (0)

Other articles
by authors

[Back to Top]