Article

An attack on the proactive RSA signature scheme in the URSA ad hoc network access control protocol

Authors:

Stanislaw Jarecki,

Jeong Hyun YiAuthors Info & Claims

SASN '04: Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks

Pages 1 - 9

https://doi.org/10.1145/1029102.1029105

Published: 25 October 2004 Publication History

Abstract

Recently, Luo, et al. in a series of papers [17, 14, 13, 18, 15] proposed a set of protocols for providing ubiquitous and robust access control [URSA] in mobile ad hoc networks without relying on a centralized authority. The URSA protocol relies on the new proactive RSA signature scheme, which allows members in an ad hoc group to make access control decisions in a distributed manner. The proposed proactive RSA signature scheme is assumed secure as long as no more than an allowed threshold of participating members is simultaneously corrupted at any point in the lifetime of the scheme.

In this paper we show an attack on this proposed proactive RSA scheme, in which an admissible threshold of malicious group members can completely recover the group RSA secret key in the course of the lifetime of this scheme. Our attack stems from the fact that the threshold signature protocol which is a part of this proactive RSA scheme leaks some seemingly innocuous information about the secret signature key. We show how the corrupted members can in uence the execution of the scheme in such a way so that the slowly leaked information is used to reconstruct the entire shared secret.

References

[1]

J. Blomer and A. May. New Partial Key Exposure Attacks on RSA. In D. Boneh, editor, CRYPTO '03, number 2729 in LNCS, pages 27--43. IACR, 2003.]]

[2]

A. Boldyreva. Efficient threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme. In Proceedings of International Workshop on Practice and Theory in Public Key Cryptography, volume 2567 of LNCS, pages 31--46, 2003.]]

Digital Library

[3]

D. Boneh, G. Durfee, and Y. Frankel. An attack on RSA given a small fraction of the private key bits. In ASIACRYPT'98, number 1514 in LNCS, pages 25--34, 1998.]]

Digital Library

[4]

D. Boneh, B. Lynn, and H. Shacham. Short Signatures from the Weil Pairing. In C. Boyd, editor, ASIACRYPT'01, number 2248 in LNCS, pages 514--532. IACR, 2001.]]

Digital Library

[5]

J. Camenisch and M. Michels. Separability and efficiency for generic group signature schemes. In In Advances in Cryptology - CRYPTO '99, volume 1666 of LNCS, pages 106--121, 1999.]]

Digital Library

[6]

Y. Desmedt and Y. Frankel. Threshold cryptosystems. In G. Brassard, editor, CRYPTO '89, number 435 in LNCS, pages 307--315. IACR, 1990.]]

Digital Library

[7]

Y. Frankel, P. Gemmell, P. D. MacKenzie, and M. Yung. Optimal-Resilience Proactive Public-Key Cryptosystems. In Foundations of Computer Science FOCS'97, pages 384--393, 1997.]]

Digital Library

[8]

Y. Frankel, P. Gemmell, P. D. MacKenzie, and M. Yung. Proactive RSA. In Proc. of Crypto'97, pages 440--454, 1997.]]

Digital Library

[9]

R. Gennaro, S.Jarecki, H.Krawczyk, and T.Rabin. Robust Threshold DSS Signature. In M. Abadi, editor, Information and Computation, vol. 164 (1), pages 54--84. 2001.]]

Digital Library

[10]

A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk, and M. Yung. Proactive public key and signature systems. In ACM Conference on Computers and Communication Security, 1997.]]

Digital Library

[11]

A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive Secret Sharing, Or How To Cope With Perpetual Leakage. In D. Coppersmith, editor, CRYPTO '95, number 963 in LNCS, pages 339--352. IACR, 1995.]]

Digital Library

[12]

S. Jarecki and N. Saxena. Further Simplifications in Proactive RSA Signature Schemes. In submission. Draft available from the authors and on http: eprint.iacr.org. August 2004.]]

[13]

J. Kong, H. Luo, K. Xu, D. L. Gu, M. Gerla, and S. Lu. Adaptive Security for Multi-level Ad-hoc Networks. In Journal of Wireless Communications and Mobile Computing (WCMC), volume 2, pages 533--547, 2002.]]

[14]

J. Kong, P. Zerfos, H. Luo, S. Lu, and L. Zhang. Providing Robust and Ubiquitous Security Support for MANET. In IEEE 9th International Conference on Network Protocols (ICNP), 2001.]]

Digital Library

[15]

H. Luo, J. Kong, P. Zerfos, S. Lu, and L. Zhang. URSA: Ubiquitous and Robust Access Control for Mobile Ad Hoc Networks, available on-line at http://www.cs.ucla.edu/wing/publication/publication.html. In IEEE/ACM Transactions on Networking (ToN), to appear, Oct 2004.]]

Digital Library

[16]

Songwu Lu. Comments on Recent Advances in Cryptoanalysis of URSA. A draft communicated to the authors by email by Songwu Lu, on August 16th, 2004.]]

[17]

H. Luo and S. Lu. Ubiquitous and Robust Authentication Services for Ad Hoc Wireless Networks. Technical Report TR-200030, Dept. of Computer Science, UCLA, 2000.]]

[18]

H. Luo, P. Zerfos, J. Kong, S. Lu, and L. Zhang. Self-securing Ad Hoc Wireless Networks. In Seventh IEEE Symposium on Computers and Communications (ISCC '02), 2002.]]

Digital Library

[19]

M. Narasimha, G. Tsudik, and J. H. Yi. On the Utility of Distributed Cryptography in P2P and MANETs: The Case of Membership Control. In IEEE 11th International Conference on Network Protocol (ICNP), pages 336--345, November 2003.]]

Digital Library

[20]

R. Ostrovsky and M. Yung. How to withstand mobile virus attacks. In 10th ACM Symp. on the Princ. of Distr. Comp., pages 51--61, 1991.]]

Digital Library

[21]

T. Rabin. A Simplified Approach to Threshold and Proactive RSA. In H. Krawczyk, editor, CRYPTO '98, number 1462 in LNCS, pages 89--104. IACR, 1998.]]

Digital Library

[22]

N. Saxena, G. Tsudik, and J. H. Yi. Admission Control in Peer-to-Peer: Design and Performance Evaluation. In ACM Workshop on Security of Ad Hoc and Sensor Networks (SASN), pages 104--114, October 2003.]]

Digital Library

[23]

N. Saxena, G. Tsudik, and J. H. Yi. Identity-based Access Control for Ad Hoc Groups. In Submission, September 2004.]]

[24]

A. Shamir. How to Share a Secret. Commun. ACM, 22(11):612--613, Nov. 1979.]]

Digital Library

[25]

L. Zhou and Z. J. Haas. Securing Ad Hoc Networks. IEEE Network Magazine, 13(6):24--30, 1999.]]

Digital Library

Cited By

Harchol YAbraham IPinkas B(2018)Distributed SSH Key Management with Proactive RSA Threshold SignaturesApplied Cryptography and Network Security10.1007/978-3-319-93387-0_2(22-43)Online publication date: 10-Jun-2018
https://doi.org/10.1007/978-3-319-93387-0_2
Weerasinghe NLadas AAdigun OPfluegel EPolitis C(2015)Securing Neighbourhood Discovery for Mobile Ad-Hoc Networks2015 IEEE 82nd Vehicular Technology Conference (VTC2015-Fall)10.1109/VTCFall.2015.7391135(1-2)Online publication date: Sep-2015
https://doi.org/10.1109/VTCFall.2015.7391135
Oreku GPazynyuk TOreku GPazynyuk T(2015)The Distributed Signature Scheme (DSS) Based on RSASecurity in Wireless Sensor Networks10.1007/978-3-319-21269-2_5(65-75)Online publication date: 13-Sep-2015
https://doi.org/10.1007/978-3-319-21269-2_5
Show More Cited By

Index Terms

An attack on the proactive RSA signature scheme in the URSA ad hoc network access control protocol
1. Networks
  1. Network protocols
    1. Application layer protocols

Recommendations

On the insecurity of proactive RSA in the URSA mobile ad hoc network access control protocol

Access control is the fundamental security service in ad hoc groups. It is needed not only to prevent unauthorized entities from joining the group, but also to bootstrap other security services. Luo, et al. proposed a set of protocols for providing ...
Proxy-protected signature secure against the undelegated proxy signature attack

The proxy signature scheme enables an original signer to delegate his/her signing capability to a designated proxy signer, thereby the proxy signer can sign messages on behalf of the original signer. Recently, Zhou et al. proposed two proxy-protected ...
New Identity-Based Sequential Aggregate Signature Scheme from RSA
ISBAST '13: Proceedings of the 2013 International Symposium on Biometrics and Security Technologies

An identity-based sequential aggregate signature (IBSAS) scheme provides a shorter aggregate signature for multiple signers in which each signer has signed his/her own message and all generated signatures are aggregated in sequence. During aggregate ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SASN '04: Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks

October 2004

124 pages

ISBN:1581139721

DOI:10.1145/1029102

General Chairs:
Sanjeev Setia
George Mason University
,
Vipin Swarup
The MITRE Corporation

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 October 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CCS04

Sponsor:

CCS04: 11th ACM Conference on Computer and Communications Security 2004

October 25, 2004

Washington DC, USA

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
946
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Harchol YAbraham IPinkas B(2018)Distributed SSH Key Management with Proactive RSA Threshold SignaturesApplied Cryptography and Network Security10.1007/978-3-319-93387-0_2(22-43)Online publication date: 10-Jun-2018
https://doi.org/10.1007/978-3-319-93387-0_2
Weerasinghe NLadas AAdigun OPfluegel EPolitis C(2015)Securing Neighbourhood Discovery for Mobile Ad-Hoc Networks2015 IEEE 82nd Vehicular Technology Conference (VTC2015-Fall)10.1109/VTCFall.2015.7391135(1-2)Online publication date: Sep-2015
https://doi.org/10.1109/VTCFall.2015.7391135
Oreku GPazynyuk TOreku GPazynyuk T(2015)The Distributed Signature Scheme (DSS) Based on RSASecurity in Wireless Sensor Networks10.1007/978-3-319-21269-2_5(65-75)Online publication date: 13-Sep-2015
https://doi.org/10.1007/978-3-319-21269-2_5
Dossogne JLafitte FVan Heule DElçi AGaur MOrgun MMakarevich O(2013)Secure and practical threshold RSAProceedings of the 6th International Conference on Security of Information and Networks10.1145/2523514.2523529(79-85)Online publication date: 26-Nov-2013
https://dl.acm.org/doi/10.1145/2523514.2523529
Chen JWu J(2012)A Survey on Applied Cryptography in Secure Mobile Ad Hoc Networks and Wireless Sensor NetworksWireless Technologies10.4018/978-1-61350-101-6.ch401(864-892)Online publication date: 2012
https://doi.org/10.4018/978-1-61350-101-6.ch401
Yang Y(2012)A communication efficient group key distribution scheme for MANETsProceedings of the 6th international conference on Network and System Security10.1007/978-3-642-34601-9_27(361-372)Online publication date: 21-Nov-2012
https://dl.acm.org/doi/10.1007/978-3-642-34601-9_27
Jarecki SSaxena N(2010)On the insecurity of proactive RSA in the URSA mobile ad hoc network access control protocolIEEE Transactions on Information Forensics and Security10.1109/TIFS.2010.20581045:4(739-749)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1109/TIFS.2010.2058104
Saxena NTsudik GYi J(2009)Efficient Node Admission and Certificateless Secure Communication in Short-Lived MANETsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2008.7720:2(158-170)Online publication date: 1-Feb-2009
https://dl.acm.org/doi/10.1109/TPDS.2008.77
Saxena NYi J(2009)Noninteractive self-certification for long-lived mobile ad hoc networksIEEE Transactions on Information Forensics and Security10.1109/TIFS.2009.20319464:4(946-955)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1109/TIFS.2009.2031946
Chao G(2009)Study on Privacy Protection and Anonymous Communication in Peer-to-Peer NetworksProceedings of the 2009 International Conference on Multimedia Information Networking and Security - Volume 0210.1109/MINES.2009.147(522-525)Online publication date: 18-Nov-2009
https://dl.acm.org/doi/10.1109/MINES.2009.147
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten