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

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: Alexandra Boldyreva, Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.31-46, January 06-08, 2003
• 3: Dan Boneh , Glenn Durfee , Yair Frankel, An Attack on RSA Given a Small Fraction of the Private Key Bits, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.25-34, October 18-22, 1998
• 4: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 5: Jan Camenisch , Markus Michels, Separability and Efficiency for Generic Group Signature Schemes, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.413-430, August 15-19, 1999
• 6: Yvo Desmedt , Yair Frankel, Threshold Cryptosystems, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.307-315, August 20-24, 1989
• 7: Y. Frankel , P. Gemmell , P. D. MacKenzie , Moti Yung, Optimal-resilience proactive public-key cryptosystems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.384, October 19-22, 1997
• 8: Yair Frankel , Peter Gemmell , Philip D. MacKenzie , Moti Yung, Proactive RSA, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.440-454, August 17-21, 1997
• 9: Rosario Gennaro , Stanisław Jarecki , Hugo Krawczyk , Tal Rabin, Robust threshold DSS signatures, Information and Computation, v.164 n.1, p.54-84, Jan. 10, 2001 [doi>10.1006/inco.2000.2881]
• 10: Amir Herzberg , Markus Jakobsson , Stanislław Jarecki , Hugo Krawczyk , Moti Yung, Proactive public key and signature systems, Proceedings of the 4th ACM conference on Computer and communications security, p.100-110, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266442]
• 11: Amir Herzberg , Stanislaw Jarecki , Hugo Krawczyk , Moti Yung, Proactive Secret Sharing Or: How to Cope With Perpetual Leakage, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.339-352, August 27-31, 1995
• 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: Providing Robust and Ubiquitous Security Support for Mobile Ad Hoc Networks, Proceedings of the Ninth International Conference on Network Protocols, p.251, November 11-14, 2001
• 15: Haiyun Luo , Jiejun Kong , Petros Zerfos , Songwu Lu , Lixia Zhang, URSA: ubiquitous and robust access control for mobile ad hoc networks, IEEE/ACM Transactions on Networking (TON), v.12 n.6, p.1049-1063, December 2004 [doi>10.1109/TNET.2004.838598]
• 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: Haiyun Luo , Petros Zerfos , Jiejun Kong , Songwu Lu , Lixia Zhang, Self-Securing Ad Hoc Wireless Networks, Proceedings of the Seventh International Symposium on Computers and Communications (ISCC'02), p.567, July 01-04, 2002
• 19: Maithili Narasimha , Gene Tsudik , Jeong Hyun Yi, On the Utility of Distributed Cryptography in P2P and MANETs: The Case of Membership Control, Proceedings of the 11th IEEE International Conference on Network Protocols, p.336, November 04-07, 2003
• 20: Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112605]
• 21: Tal Rabin, A Simplified Approach to Threshold and Proactive RSA, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.89-104, August 23-27, 1998
• 22: Nitesh Saxena , Gene Tsudik , Jeong Hyun Yi, Admission control in Peer-to-Peer: design and performance evaluation, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986873]
• 23: N. Saxena, G. Tsudik, and J. H. Yi. Identity-based Access Control for Ad Hoc Groups. In Submission, September 2004.
• 24: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 25: L. Zhou and Z. J. Haas. Securing Ad Hoc Networks. IEEE Network Magazine, 13(6):24--30, 1999.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

General Terms:
Security

Keywords:
RSA, admission control, group membership, mobile ad-hoc networks, peer-to-peer, proactive cryptosystems, threshold cryptosystems