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 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.
Introduction
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 were later found to be flawed, with one even traced back to a bug in the verification tool ProVerif. This research provides a definitive answer using a more rigorous mathematical framework to catch subtle "branching" attacks that simpler methods miss.
Methodology: Formal Verification via Applied $\pi$-Calculus
The authors employ the applied $\pi$-calculus, a formal language used to model concurrent processes and cryptographic protocols. The syntax of this calculus, shown in Figure 3, allows for the precise definition of processes ($P, Q$) and terms ($M, N$), including cryptographic primitives like encryption and MACs.
The 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?). We 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, we use "open" (symbolic) bisimilarity. This allows us to "lazily" instantiate inputs only when they are needed to trigger a specific protocol branch.
- Classical $\mathcal{FM}$ Logic: We developed a specific modal logic to "certify" attacks. Once a vulnerability is found via bisimilarity, it is expressed as a formula in this logic, providing a clear, step-by-step recipe for the attack.
The ePassport Vulnerability
The core of the discovery lies in how the ePassport responds to specific inputs from a reader. The interaction, illustrated in Figure 2, involves the exchange of nonces and keys to establish a secure session.
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 to protect privacy. An attacker doesn't need to crack encryption to track a user; 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, effectively linking the two sessions.
Key Results and Impact
- Confirmed Vulnerabilities: We discovered and implemented a re-identification attack. We 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: We 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: We proved that standard trace-based verification is too weak for privacy properties; bisimilarity is essential for finding these "interactive" attacks.
Conclusion
This work highlights a cautionary tale: a decade-old "proof" of ePassport security was actually false because of a bug in verification software. This underscores the need for diverse formal methods and human-readable "attack certificates." While we have established a mathematical framework, building a fully automated tool that generates these complex modal logic formulas for any protocol remains a challenge for future research. Furthermore, implementing mitigations like Time-based One-time Passwords (TOTP) requires international consensus, making the path to a fix a long-term global effort.
Summary updated