The SecureRing group communication system

ABSTRACT

Secure reliable group communication protocols can facilitate the development of survivable distributed systems that are able to remain correct and reliable despite intrusions that cause some nodes to behave in an arbitrary or malicious manner. However, the development of such protocols is itself difficult, and prior systems have exhibited high overheads, primarily due to the cost of digital signatures. The SecureRing group communication system provides secure, reliable, totally-ordered message delivery and group membership services despite the malicious corruption of a constant fraction of the processors within the system. The network is assumed not to partition, and persistent communication faults are handled as processor faults. The SecureRing message delivery protocol makes use of message digests in a signed token to allow a single digital signature to cover multiple messages, and to avoid the need for multiple rounds of message exchange in normal operation. While these techniques mean that messages are not authenticated in real time, they enable the SecureRing protocols to achieve high throughput and reasonable latency.

REFERENCES

• 1: D. A. Agarwal , L. E. Moser , P. M. Melliar-Smith , R. K. Budhia, The Totem multiple-ring ordering and topology maintenance protocol, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.93-132, May 1998 [doi>10.1145/279227.279228]
• 2: Y. Amir , L. E. Moser , P. M. Melliar-Smith , D. A. Agarwal , P. Ciarfella, The Totem single-ring ordering and membership protocol, ACM Transactions on Computer Systems (TOCS), v.13 n.4, p.311-342, Nov. 1995 [doi>10.1145/210223.210224]
• 3: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 4: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 5: DIFFIE,W.AND HELLMAN, M. 1976. New directions in cryptography. IEEE Trans. Inf. Theory IT- 22, 6 (Nov.), 644-654.
• 6: ELLISON,R.J.,FISHER, D. A., LINGER,R.C.,LIPSON,H.F.,LONGSTAFF,T.,AND MEAD, N. R. 1997. Survivable network systems: An emerging discipline. Tech. Rep. CMU/SEI-97-TR-013 (Nov.), Software Engineering Institute, Carnegie Mellon University.
• 7: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 8: Kim Potter Kihlstrom , Louise E. Moser, Survivable distributed systems: design and implementation (common object request broker architecture), 1999
• 9: KIHLSTROM,K.P.,MOSER,L.E.,AND MELLIAR-SMITH, P. M. 1997. Solving consensus in a Byzantine environment using an unreliable fault detector. In Proceedings of the International Conference on Principles of Distributed Systems (Chantilly, France, Dec.), 61-75.
• 10: Kim Potter Kihlstrom , L. E. Moser , P. M. Melliar-Smith, The SecureRing Protocols for Securing Group Communication, Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences-Volume 3, p.317, January 06-09, 1998 [doi>10.1109/HICSS.1998.656294]
• 11: LACY,J.B.,MITCHELL,D.P.,AND SCHELL, W. M. 1993. CryptoLib: Cryptography in software. In Proceedings of the 4th USENIX Security Workshop (Santa Clara, CA, Oct.), 1-17.
• 12: Dahlia Malkhi , Michael Merritt , Ohad Rodeh, Secure Reliable Multicast Protocols in a WAN, Proceedings of the 17th International Conference on Distributed Computing Systems (ICDCS '97), p.87, May 27-30, 1997
• 13: Dahlia Malkhi , Michael Reiter, A high-throughput secure reliable multicast protocol, Journal of Computer Security, v.5 n.2, p.113-127, Jan. 1997
• 14: Dahlia Malkhi , Michael Reiter, Unreliable Intrusion Detection in Distributed Computations, Proceedings of the 10th Computer Security Foundations Workshop (CSFW '97), p.116, June 10-12, 1997
• 15: Dahlia Malkhi , Michael K. Reiter, Secure and Scalable Replication in Phalanx, Proceedings of the The 17th IEEE Symposium on Reliable Distributed Systems, p.51, October 20-23, 1998
• 16: Louise E. Moser , P. M. Melliar-Smith, Byzantine-resistant total ordering algorithms, Information and Computation, v.150 n.1, p.75-111, April 10, 1999 [doi>10.1006/inco.1998.2770]
• 17: L. E. Moser , P. M. Melliar-Smith , D. A. Agarwal , R. K. Budhia , C. A. Lingley-Papadopoulos, Totem: a fault-tolerant multicast group communication system, Communications of the ACM, v.39 n.4, p.54-63, April 1996 [doi>10.1145/227210.227226]
• 18: MOSER, L. E., MELLIAR-SMITH,P.M.,AND NARASIMHAN, N. 2000. The Secure Group communication system. In Proceedings of the IEEE Information Survivability Conference (Hilton Head, SC, Jan. 2000), 256-270.
• 19: Providing Support for Survivable CORBA Applications with the Immune System, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.507, May 31-June 04, 1999
• 20: NARASIMHAN, P., MOSER,L.E.,AND MELLIAR-SMITH, P. M. 1996. Message packing as a performance enhancement strategy with application to the Totem protocols. In Proceedings of the IEEE Global Telecommunications Conference (London, UK, Nov. 1996), 649-653.
• 21: NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY. 1995. Secure hash standard. Federal Information Processing Standards Publication 180-1.
• 22: Michael K. Reiter, Secure agreement protocols: reliable and atomic group multicast in rampart, Proceedings of the 2nd ACM Conference on Computer and communications security, p.68-80, November 1994, Fairfax, Virginia, United States [doi>10.1145/191177.191194]
• 23: Michael K. Reiter, The Rampart Toolkit for Building High-Integrity Services, Selected Papers from the International Workshop on Theory and Practice in Distributed Systems, p.99-110, September 05-09, 1994
• 24: Michael K. Reiter, A Secure Group Membership Protocol, IEEE Transactions on Software Engineering, v.22 n.1, p.31-42, January 1996 [doi>10.1109/32.481515]
• 25: Ronald L. Rivest, The MD4 Message Digest Algorithm, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.303-311, August 11-15, 1990
• 26: RIVEST, R. L. 1992. The MD5 message digest algorithm. Internet Activities Board.
• 27: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]

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:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.6 Security and Protection
          Subjects: Invasive software (e.g., viruses, worms, Trojan horses)

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Invasive software (e.g., viruses, worms, Trojan horses)

General Terms:
Reliability, Security

Keywords:
Byzantine faults, group communication, intrusion, partial synchrony, state machine replication, survivability