On the difficulty of achieving anonymity for Vehicle-2-X communication

Vehicle-2-X communications are hailed as the future to improve safety on the roads. Ensuring that messages sent by vehicles contain correct information is crucial to fulfill this objective, as misleading information could disrupt traffic and create potentially dangerous situations. Thus, Vehicle-2-X communication requires authentication to ensure that messages come from legitimate vehicles, and to identify vehicles that send misleading information. If a unique public key certificate per vehicle is used to authenticate messages, then the identification of misbehaving (or malfunctioning) vehicles is straightforward, and so is the revocation of their credentials. This solution however, offers no privacy protection to drivers, as the tracking of all the vehicles' movements is equally trivial. A privacy-preserving alternative is to authenticate messages using (unlinkable) one-time pseudonyms, but these protocols are computationally expensive and their certificate revocation process is more complex. Intermediate solutions that trade off privacy and efficiency are based on multiple certificates per vehicle, which may or may not be unique, that are reused to authenticate messages. In this work we analyze two such intermediate solutions that have been proposed by IntelliDrive, US Department of Transportation (DoT). We show that by exploiting the reuse of pseudonyms and spatio-temporal constraints the service provider is capable of tracking a large percentage of vehicles. Furthermore, we find that one of the schemes fails to provide privacy even if the adversary does not control the service provider and only listens to the communications of vehicles. © 2011 Elsevier B.V. All rights reserved.status: publishe