Analysis of Authentication Protocols in Agent-Based Systems Using Labeled Tableaux

The study of multiagent systems (MASs) focuses on systems in which many intelligent agents interact with each other using communication protocols. For example, an authentication protocol is used to verify and authorize agents acting on behalf of users to protect restricted data and information. After authentication, two agents should be entitled to believe that they are communicating with each other and not with intruders. For specifying and reasoning about the security properties of authentication protocols, many researchers have proposed the use of belief logics. Since authentication protocols are designed to operate in dynamic environments, it is important to model the evolution of authentication systems through time in a systematic way. We advocate the systematic combinations of logics of beliefs and time for modeling and reasoning about evolving agent beliefs in MASs. In particular, we use a temporal belief logic called TML⁺ for establishing trust theories for authentication systems and also propose a labeled tableau system for this logic. To illustrate the capabilities of TML⁺, we present trust theories for several well-known authentication protocols, namely, the Lowe modified wide-mouthed frog protocol, the amended Needham-Schroeder symmetric key protocol, and Kerberos. We also show how to verify certain security properties of those protocols. With the logic TML⁺ and its associated modal tableaux, we are able to reason about and verify authentication systems operating in dynamic environments.