Supporting structured credentials and sensitive policies through interoperable strategies for automated trust negotiation

ABSTRACT

Business and military partners, companies and their customers, and other closely cooperating parties may have a compelling need to conduct sensitive interactions on line, such as accessing each other's local services and other local resources. Automated trust negotiation is an approach to establishing trust between parties so that such interactions can take place, through the use of access control policies that specify what combinations of digital credentials a stranger must disclose to gain access to a local resource. A party can use many different strategies to negotiate trust, offering tradeoffs between the length of the negotiation, the amount of extraneous information disclosed, and the computational effort expended. To preserve parties' autonomy, each party should ideally be able to choose its negotiation strategy independently, while still being guaranteed that negotiations will succeed whenever possible---that the two parties' strategies will interoperate. In this paper we provide the formal underpinnings for that goal, by formalizing the concepts of negotiation protocols, strategies, and interoperation. We show how to model the information flow of a negotiation for use in analyzing strategy interoperation. We also present two large sets of strategies whose members all interoperate with one another, and show that these sets contain many practical strategies. We develop the theory for black-box propositional credentials as well as credentials with internal structure, and for access control policies whose contents are (respectively are not) sensitive. We also discuss how these results fit into TrustBuilder, our prototype system for trust negotiation.

REFERENCES

• 1: Krzysztof R. Apt , David S. Warren , Mirek Truszczynski, The Logic Programming Paradigm: A 25-Year Perspective, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 2: Blaze, M., Feigenbaum, J., Ioannidis, J., and Keromytis, A. 1999. The KeyNote Trust Management System Version 2. In Internet Draft RFC 2704.
• 3: Matt Blaze , Joan Feigenbaum , Angelos D. Keromytis, KeyNote: Trust Management for Public-Key Infrastructures (Position Paper), Proceedings of the 6th International Workshop on Security Protocols, p.59-63, April 15-17, 1998
• 4: Piero Bonatti , Pierangela Samarati, Regulating service access and information release on the Web, Proceedings of the 7th ACM conference on Computer and communications security, p.134-143, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352620]
• 5: Dierks, T. and Allen, C. 1999. The TLS Protocol Version 1.0. IETF.
• 6: Farrell, S. 1998. TLS Extension for Attribute Certificate Based Authorization. IETF.
• 7: Frier, A., Karlton, P., and Kocher, P. 1996. The SSL 3.0 Protocol. Netscape Communications Corp.
• 8: Amir Herzberg , Yosi Mass, Relying Party Credentials Framework, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.328-343, April 08-12, 2001
• 9: Amir Herzberg , Yosi Mass , Joris Michaeli , Yiftach Ravid , Dalit Naor, Access Control Meets Public Key Infrastructure, Or: Assigning Roles to Strangers, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.2, May 14-17, 2000
• 10: Hess, A., Jacobson, J., Mills, H., Wamsley, R., Seamons, K., and Smith, B. 2002. Advanced Client/Server Authetication in TLS. In Network and Distributed System Security Symposium. San Diego, CA.
• 11: IETF 2001. Simple Public Key Infrastructure (SPKI) IETF.
• 12: IETF 2002. Simple Public Key Infrastructure (X.509) (pkix). IETF.
• 13: Nayeem Islam , Rangachari Anand , Trent Jaeger , Josyula R. Rao, A Flexible Security System for Using Internet Content, IEEE Software, v.14 n.5, p.52-59, September 1997 [doi>10.1109/52.605931]
• 14: William Johnston , Srilekha Mudumbai , Mary Thompson, Authorization and Attribute Certificates for Widely Distributed Access Control, Proceedings of the 7th Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises, p.340-345, June 17-19, 1998
• 15: Ninghui Li , Benjamin Grosof , Joan Feigenbaum, A Practically Implementable and Tractable Delegation Logic, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.27, May 14-17, 2000
• 16: Ninghui Li , William H. Winsborough , John C. Mitchell, Distributed credential chain discovery in trust management: extended abstract, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502005]
• 17: Rescorla, E. 1998. HTTP Over TLS. IETF.
• 18: Konstantinos Sagonas , Terrance Swift , David S. Warren, XSB as an efficient deductive database engine, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.442-453, May 24-27, 1994, Minneapolis, Minnesota, United States
• 19: Seamons, K., Winslett, M., and Yu, T. 2001. Limiting the Disclosure of Access Control Policies during Automated Trust Negotiation. In Network and Distributed System Security Symposium. San Diego, CA.
• 20: W3C 2002. Platform for Privacy Preferences (P3P) Specification W3C.
• 21: Winsborough, W., Seamons, K., and Jones, V. 2000. Automated Trust Negotiation. In DARPA Information Survivability Conference and Exposition. Hilton Head Island, SC.
• 22: Ting Yu , Xiaosong Ma , Marianne Winslett, PRUNES: an efficient and complete strategy for automated trust negotiation over the Internet, Proceedings of the 7th ACM conference on Computer and communications security, p.210-219, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352633]
• 23: Ting Yu , Marianne Winslett , Kent E. Seamons, Interoperable strategies in automated trust negotiation, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502004]
• 24: Zimmerman, P. 1994. PGP User's Guide. MIT Press.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Security, Theory, Verification

Keywords:
Automated trust negotiation, access control, digital credentials, interoperable strategies