Breaking Unlinkability of the ICAO 9303 Standard for e-Passports using Bisimilarity

We clear up confusion surrounding privacy claims about the ICAO
9303 standard for e-passports. The ICAO 9303 standard includes a Basic Access
Control (BAC) protocol that should protect the user from being traced from one
session to another. While it is well known that there are attacks on BAC, allowing
an attacker to link multiple uses of the same passport, due to differences in implementation; there still remains confusion about whether there is an attack on unlinkability directly on the BAC protocol as specified in the ICAO 9303 standard.
This paper clarifies the nature of the debate, and sources of potential confusion.
We demonstrate that the original privacy claims made are flawed, by uncovering attacks on a strong formulation of unlinkability. We explain why the use of
the bisimilarity equivalence technique is essential for uncovering our attacks. We
also clarify what assumptions lead to proofs of formulations of unlinkability using weaker notions of equivalence. Furthermore, we propose a fix for BAC within
the scope of the standard, and prove that it is correct, again using a state-of-the-art
approach to bisimilarity.