  The ubiquitous presence of mobile communication devices and the continuous
development of mo- bile data applications, which results in high level of
mobile devices' activity and exchanged data, often transparent to the user,
makes privacy preservation an important feature of mobile telephony systems. We
present a formal analysis of the UMTS Authentication and Key Agreement
protocol, using the applied pi-calculus and the ProVerif tool. We formally
verify the model with respect to privacy properties. We show a linkability
attack which makes it possible, for individuals with low-cost equipment, to
trace UMTS subscribers. The attack exploits information leaked by poorly
designed error messages.
