Model Checking Security Protocols Using a Logic of Belief

Massimo Benerecetti, Fausto GiunchigliaTACAS 2000 · OpenReview

Abstract

In this paper, we demonstrate how model checking can be utilized for the verification of security protocols through a logic of belief. We model principals as processes capable of maintaining beliefs, employing an approach that treats temporal evolution and the belief aspects of principals separately. In this framework, belief formulae are treated as atomic propositions during temporal evolution, while a principal's beliefs about another agent are modeled by granting access to a representation of that agent as a process. We apply this framework to formalize and analyze the Andrew protocol as a motivating example.

Introduction

Security protocols, particularly those designed for authentication and key exchange, are fundamental to secure digital communication. However, verifying their correctness is notoriously difficult. Traditional model checking excels at verifying temporal properties—ensuring that certain states follow others in a specific order. Yet, security is often not just about the sequence of messages but about the internal state of belief of the participants. For instance, after a successful handshake, Principal A should not only possess a session key but should also believe that the key is fresh and believe that Principal B shares this belief.

While "Logics of Belief" (such as BAN logic) provide powerful tools for reasoning about trust, they often lack the automated, state-based verification capabilities of model checkers. This paper bridges that gap by introducing a formal framework that allows standard model checking tools to reason about epistemic properties.

The MAFSM Framework

The authors propose a new theoretical framework called MultiAgent Finite State Machines (MAFSM). The core innovation lies in the separation of temporal evolution from belief, treating them as orthogonal dimensions of the system.

The View Hierarchy

Instead of a single, monolithic state machine, the system is modeled as a tree of "views." The root of this tree, denoted as $\epsilon$, represents the perspective of an external observer. Each subsequent node represents a specific agent's perspective or a nested belief.

The View Hierarchy representing nested beliefs between agents A and B.

In this hierarchy:

  • View $B_A$ represents Principal A’s beliefs.
  • View $B_A B_B$ represents what Principal A believes Principal B believes.

This structure allows the model to remain finite and checkable, as most security protocols only require reasoning about two or three levels of nested belief.

Explicit vs. Implicit Beliefs

The framework distinguishes between two types of beliefs to maintain computational efficiency:

  1. Explicit Beliefs: These are treated as simple labels (atomic propositions) within a specific state machine. They represent facts that an agent holds to be true at a given time.
  2. Implicit Beliefs: These are verified by "jumping" from one state machine to another. To determine if Principal A implicitly believes a proposition $\phi$, the algorithm checks if $\phi$ holds in all states of the $B_A$ view that are compatible with A's current situation.
Mechanism for verifying implicit beliefs by transitioning between views.

By treating belief and time as orthogonal, the system can model how a principal's state changes over time while treating their beliefs as "black box" labels that are only expanded into full state-space explorations when necessary.

Case Study: The Andrew Protocol

To validate the framework, the authors formalized the Andrew Protocol, a well-known authentication handshake intended to share a secret key. Despite its design, the protocol is famously vulnerable to freshness attacks, where an attacker replays an old message to trick a principal into using an expired key.

Using the MAFSM framework and the NuSMV model checker, the authors were able to automatically identify this vulnerability. The model checker proved that the protocol fails to satisfy a critical security property: after the final message exchange, Principal A cannot definitively believe that Principal B believes the new session key is valid and fresh. The failure occurs because the principal cannot distinguish between a truly fresh message and a replayed one, modeled here as a lack of belief in the "freshness" variable.

Conclusion and Future Work

This research demonstrates that belief-based verification can be integrated into existing model checking technology with minimal variations. By keeping the number of "views" finite and utilizing explicit belief atoms, the authors provide a scalable way to prove whether a protocol achieves mutual trust.

However, limitations remain. The current approach requires a finite nesting of beliefs and necessitates manual definition of belief atoms and invariants for each view. Future work will focus on automating the translation from high-level protocol descriptions to these specific FSMs and exploring the scalability of the approach in environments with many principals and more complex nested belief structures.

Summary updated

Abstract

In this paper we show how model checking can be used for the verification of security protocols using a logic of belief. We model principals as processes able to have beliefs. The idea underlying the approach is to treat separately the temporal evolution and the belief aspects of principals. Therefore, when we consider the temporal evolution, belief formulae are treated as atomic propositions; while the fact that principal A has beliefs about another principal B is modeled as the fact that A has access to a representation of B as a process. As a motivating example, we use the framework proposed to formalize the Andrew protocol.
BibTeX
@inproceedings{benerecetti2000model,
  author = {Massimo Benerecetti and Fausto Giunchiglia},
  title = {{Model Checking Security Protocols Using a Logic of Belief}},
  booktitle = {TACAS},
  year = {2000},
  url = {https://openreview.net/forum?id=GqX94EVkK8},
}
Figure