How to securely replicate services

ABSTRACT

We present a method for constructing replicated services that retain their availability and integrity despite several servers and clients being corrupted by an intruder, in addition to others failing benignly. We also address the issue of maintaining a causal order among client requests. We illustrate a security breach resulting from an intruder's ability to effect a violation of causality in the sequence of requests processed by the service and propose an approach to counter this attack. An important and novel feature of our techniques is that the client need not be able to identify or authenticate even a single server. Instead, the client is required to possess only a single public key for the service. We demonstrate the performance of our techniques with a service we have implemented using one of our protocols.

REFERENCES

• 1: André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991 [doi>10.1145/128738.128742]
• 2: Ernest A. Brickell, A survey of hardware implementations of RSA (abstract), Proceedings on Advances in cryptology, p.368-370, July 1989, Santa Barbara, California, United States
• 3: CHOR, B., AND DWORK, C 1989. Randomization in Byzantine agreement. Adv. Comput Res. 5, 443-497.
• 4: CRISTIAN, F., AGHILI, H., STRONG, R., AND DOLEV, D. 1985. Atomic broadcast: From simple message diffusion to Byzantine agreement. In Proceedings of the 15th International Sympostum on Fault-Tolerant Computing. 200-206. A revised version appears as IBM Res. Lab. Tech. Rep. RJ5244 {April 1989), IBM, Armonk, N.Y.
• 5: Dorothy E. Denning, Digital signatures with RSA and other public-key cryptosystems, Communications of the ACM, v.27 n.4, p.388-392, April 1984 [doi>10.1145/358027.358052]
• 6: Yvo Desmedt , Yair Frankel, Shared Generation of Authenticators and Signatures (Extended Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.457-469, August 11-15, 1991
• 7: Yvo G. Desmedt , Yair Frankel, Threshold cryptosystems, Proceedings on Advances in cryptology, p.307-315, July 1989, Santa Barbara, California, United States
• 8: Danny Dolev , Cynthia Dwork , Moni Naor, Non-malleable cryptography, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.542-552, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103474]
• 9: ELGAMAL, T. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory. IT-31o 4 (July), 469-472.
• 10: FELDMAN, P. 1987. A practical scheme for non-interactive verifiable secret sharing. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science. IEEE, New York, 427-437.
• 11: 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]
• 12: FRANKEL, Y., AND DESMEDT, Y. 1992. Distributed reliable threshold multislgnature. Tech. Rep. TR-92-04-02, Dept. of EE & CS, Univ. of Wisconsin at Milwaukee
• 13: GONG, L. 1989. Securely replicating authentication services In Proceedtngs of the 9th Internat~onal Conference on Dzstmbuted Computing Systems. 85-91.
• 14: Ajei Gopal , Ray Strong , Sam Toueg , Flaviu Cristian, Early-delivery atomic broadcast, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.297-309, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93430]
• 15: Maurice Herlihy , J. D. Tygar, How to Make Replicated Data Secure, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.379-391, August 16-20, 1987
• 16: JOSEPH, M.K. 1987. Towards the elimination of the effects of malicious lognc: Fault tolerance approaches. In Proceedtngs of the l Oth NBS/NCSC National Computer Secumty Conference. NBS/NCSC, Washington, D.C., 238-244.
• 17: Hugo Krawczyk, Distributed fingerprints and secure information dispersal, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.207-218, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164075]
• 18: Chi-Sung Laih , Lein Harn, Generalized Threshold Cryptosystems, Proceedings of the International Conference on the Theory and Applications of Cryptology: Advances in Cryptology, p.159-166, November 11-14, 1991
• 19: LAMPORT, L. 1978a. The implementation ofrehable distributed multiprocess systems. Comput. Netw. 2, 95-114.
• 20: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 21: Butler Lampson , Martín Abadi , Michael Burrows , Edward Wobber, Authentication in distributed systems: theory and practice, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.265-310, Nov. 1992 [doi>10.1145/138873.138874]
• 22: Chae Hoon Lim , Pil Joong Lee, Another method for attaining security against adaptively chosen ciphertext attacks, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.420-434, January 1994, Santa Barbara, California, United States
• 23: Holger Orup , Erik Svendsen , Erik Andreasen, VICTOR: an efficient RSA hardware implementation, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.245-252, February 1991, Aarhus, Denmark
• 24: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• 25: Micheal K. Reiter, A Secure Group Membership Protocol, Proceedings of the 1994 IEEE Symposium on Security and Privacy, p.176, May 16-18, 1994
• 26: Michael Kendrik Reiter, A security architecture for fault-tolerant systems, Cornell University, Ithaca, NY, 1993
• 27: Micheal Reiter , Li Gong, Preventing Denial and Forgery of Causal Relationships in Distributed Systems, Proceedings of the 1993 IEEE Symposium on Security and Privacy, p.30, May 24-26, 1993
• 28: Michael Reiter , Kenneth Birman , Li Gong, Integrating Security in a Group Oriented Distributed System, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.18, May 04-06, 1992
• 29: Aleta Marie Ricciardi, The group membership problem in asynchronous systems, Cornell University, Ithaca, NY, 1993
• 30: 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
• 31: 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]
• 32: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 33: SEDLAK, H. 1988. The RSA cryptography processor, in Advances in Cryptology: Proceedings of EUROCRYPT '87. Lecture Notes in Computer Science, vol. 304. Springer-Verlag, New York, 95-105.
• 34: SHAND, M., AND VUILLEMIN, J. 1993. Fast implementations of RSA cryptography. In Proceedings of the 11th IEEE Symposium on Computer Arithmetic. IEEE, New York.
• 35: Santosh K. Shrivastava , Paul D. Ezhilchelvan , Neil A. Speirs , Sha Tao , Alan Tully, Principal Features of the VOLTAN Family of Reliable Node Architectures for Distributed Systems, IEEE Transactions on Computers, v.41 n.5, p.542-549, May 1992 [doi>10.1109/12.142680]
• 36: STEINER, J. G., NEUMAN, C., AND SCHILLER, J.I. 1988. Kerberos: An authentication service for open network systems. In Proceedings of the USENIX Winter Conference. USENIX Association, 191-202.
• 37: TURN, R., AND HABIBI, J. 1986. On the interactions of security and fault-tolerance. In Proceedings of the 9th NBS/NCSC National Computer Security Conference. NBS/NCSC, Washington D.C., 138-142.
• 38: Victor L. Voydock , Stephen T. Kent, Security Mechanisms in High-Level Network Protocols, ACM Computing Surveys (CSUR), v.15 n.2, p.135-171, June 1983 [doi>10.1145/356909.356913]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

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

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.6 Security and Protection
          Subjects: Authentication; Cryptographic controls

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

General Terms:
Reliability, Security

Keywords:
causality, replication, state machines, threshold cryptography