Discovering ePassport Vulnerabilities using Bisimilarity

Ross Horne, Sjouke Mauw

TL;DR

Researchers used advanced formal verification techniques—specifically bisimilarity in the applied $\pi$-calculus—to prove that global ePassport standards (ICAO 9303) are vulnerable to tracking. Their work uncovered flaws in both the original BAC protocol and the newer, "more secure" PACE protocol, allowing an attacker to re-identify individuals who recently passed through a checkpoint.

What Problem Does This Paper Address?

Electronic passports (ePassports) are designed with a core privacy requirement called unlinkability. This means an unauthorized third party should not be able to determine if two different protocol sessions involve the same passport. If a passport is "linkable," an attacker could theoretically track a traveler's movements.

For years, the security community debated whether the Basic Access Control (BAC) protocol—the standard used for initial authentication—satisfied this property. Earlier formal proofs suggested it was secure, but those proofs turned out to be flawed (one was even traced back to a bug in the verification tool ProVerif). The authors set out to provide a definitive answer using a more rigorous mathematical framework to catch subtle "branching" attacks that simpler methods miss.

Methods

The authors employ the applied $\pi$-calculus, a formal language used to model concurrent processes and cryptographic protocols. Their approach relies on several key innovations:

  • Bisimilarity vs. Trace Equivalence: Most security tools look for "trace equivalence" (can the attacker see a different sequence of messages?). The authors argue for bisimilarity, a stronger notion that models a "game" between an attacker and the system. If the attacker can make a move that the system cannot simulate in a way that maintains equivalence, the protocol is broken.
  • Open Bisimilarity: To handle the infinite number of possible messages an attacker could send, they use "open" (symbolic) bisimilarity. This allows them to "lazily" instantiate inputs only when they are needed to trigger a specific protocol branch.
  • Saturation (Reduction): They proved that the complex problem of "weak" unlinkability (which ignores internal system steps) can be reduced to "strong" bisimilarity, which is much easier to check and automate.
  • Classical $\mathcal{FM}$ Logic: They developed a specific modal logic to "certify" attacks. Once a vulnerability is found via bisimilarity, they write it as a formula in this logic, providing a clear, step-by-step recipe for the attack.

Datasets

As a formal methods paper, this work does not use traditional training datasets. Instead, the "data" consists of the formal specifications of the ICAO 9303 standard (the international standard for machine-readable travel documents). The authors also reference real-world implementation behaviors, such as those found in French and UK ePassports, to ensure their models reflect reality.

Key Insights and Ideas

  • The "Aha!" Moment on PACE: The most surprising finding is that the PACE protocol, introduced specifically to fix BAC's security weaknesses, is vulnerable to the exact same type of unlinkability attack. While PACE is better at protecting data secrecy, it fails just as badly at protecting privacy.
  • The Power of the Game: The authors show that an attacker doesn't need to crack encryption to track you. They just need to observe how the passport responds to "wrong" inputs. By carefully choosing which reader session to "replay" to a passport, an attacker can see if the passport "recognizes" a previous session's context.
  • Tool Vulnerability: The paper highlights a cautionary tale: a decade-old "proof" of ePassport security was actually false because of a bug in the verification software. This underscores the need for diverse formal methods and human-readable "attack certificates" (like their modal logic formulas).

Key Results

  • Confirmed Vulnerabilities: The authors discovered and implemented a re-identification attack. They reported this to the ICAO, who confirmed the vulnerability is real.
  • Global Impact: Since over 150 countries issue ePassports following these standards, the flaw potentially affects billions of documents in circulation.
  • Methodological Success: They successfully demonstrated a "tool chain" that moves from symbolic discovery (Open Bisimilarity) to formal certification (Modal Logic) to real-world exploit.
  • Trace Equivalence is Insufficient: They proved that standard trace-based verification is too weak for privacy properties; bisimilarity is essential for finding these "interactive" attacks.

Limitations and Future Work

  • Spurious Counter-examples: Because "open bisimilarity" is an under-approximation, it can sometimes flag "attacks" that aren't actually possible in the real world. Distinguishing these from real attacks still requires expert intuition.
  • Mitigation Hurdles: The authors suggest mitigations like Time-based One-time Passwords (TOTP) or strict session timeouts. However, implementing these requires international consensus and changes to hardware/policy, which is a slow process for a global standard.
  • Automation: While they have the mathematical framework, building a fully automated tool that generates these complex modal logic formulas for any protocol remains a challenge for future research.

Summary updated

Abstract

We uncover privacy vulnerabilities in the ICAO 9303 standard implemented by ePassports worldwide. These vulnerabilities, confirmed by ICAO, enable an ePassport holder who recently passed through a checkpoint to be reidentified without opening their ePassport. This paper explains how bisimilarity was used to discover these vulnerabilities, which exploit the BAC protocol - the original ICAO 9303 standard ePassport authentication protocol - and remains valid for the PACE protocol, which improves on the security of BAC in the latest ICAO 9303 standards. In order to tackle such bisimilarity problems, we develop here a chain of methods for the applied $\pi$-calculus including a symbolic under-approximation of bisimilarity, called open bisimilarity, and a modal logic, called classical FM, for describing and certifying attacks. Evidence is provided to argue for a new scheme for specifying such unlinkability problems that more accurately reflects the capabilities of an attacker.
BibTeX
@article{horne2021discovering,
  author = {Ross Horne and Sjouke Mauw},
  title = {{Discovering ePassport Vulnerabilities using Bisimilarity}},
  journal = {Log. Methods Comput. sci},
  year = {2021},
  doi = {10.23638/lmcs-17(2:24)2021},
}

Loading related content...

Figure