Abstract
Research on vehicular networking (V2X) security has produced a range of security mechanisms and protocols tailored for this domain, addressing both security and privacy. Typically, the security analysis of these proposals has largely been informal. However, formal analysis can be used to expose flaws and ultimately provide a higher level of assurance in the protocols. This paper focusses on the formal analysis of a particular element of security mechanisms for V2X found in many proposals: the revocation of malicious or misbehaving vehicles from the V2X system by invalidating their credentials. This revocation needs to be performed in an unlinkable way for vehicle privacy even in the context of vehicles regularly changing their pseudonyms. The REWIRE scheme by Forster et al. and its subschemes BASIC and RTOKEN aim to solve this challenge by means of cryptographic solutions and trusted hardware. Formal analysis using the TAMARIN prover identifies two flaws with some of the functional correctness and authentication properties in these schemes. We then propose Obscure Token (OTOKEN), an extension of REWIRE to enable revocation in a privacy preserving manner. Our approach addresses the functional and authentication properties by introducing an additional key-pair, which offers a stronger and verifiable guarantee of successful revocation of vehicles without resolving the long-term identity. Moreover OTOKEN is the first V2X revocation protocol to be co-designed with a formal model.
Introduction
In Intelligent Transportation Systems (ITS), vehicles (V2X) constantly broadcast their location and status to improve safety and efficiency. To prevent tracking and maintain driver privacy, vehicles utilize "pseudonyms"—temporary digital credentials—rather than a single long-term identity. However, a critical challenge arises when a vehicle misbehaves, such as by broadcasting malicious or false traffic data. In such cases, a Revocation Authority (RA) must be able to invalidate all of that vehicle's pseudonyms.
The difficulty lies in performing this revocation without compromising privacy; the process must not allow an observer to link all of a vehicle's pseudonyms back to its long-term identity. Existing proposals, such as the REWIRE scheme, attempt to solve this using trusted hardware on the vehicle. The following diagram illustrates the general architecture and interaction between the Certification Authority (CA), Provider of Pseudonyms (PP), Revocation Authority (RA), and the vehicles.
Methodology: Formal Verification with Tamarin
To move beyond informal security evaluations, this research employs formal verification using the Tamarin prover, a symbolic analysis tool. The protocols are modeled using multiset rewriting rules and first-order logic to represent the system's state and transitions.
The analysis assumes a "Dolev-Yao" adversary model, where the attacker has full control over the network—capable of intercepting, deleting, or injecting messages—but cannot break standard cryptographic primitives or access a vehicle's internal Trusted Component (TC). The protocols were evaluated against seven specific goals (G1–G7), covering functional correctness, authentication (e.g., non-injective synchronization), and the ability to revoke a vehicle even after it switches pseudonyms.
The notation used in these models, as detailed in the table above, defines the cryptographic primitives such as asymmetric key pairs ($SK, PK$), pseudonyms ($Ps$), and the specific tokens (R-TOKEN and O-TOKEN) used to facilitate secure revocation.
Vulnerabilities in Existing Protocols
Formal analysis revealed critical flaws in the REWIRE family of protocols:
- The "Pseudonym Escape" Flaw (Rewire Plain): In the basic version, a vehicle can evade a revocation command by simply switching to a new pseudonym before the command is processed. The vehicle's hardware only monitors commands addressed to its currently active pseudonym, failing goal G5.
- The "Spoofable Confirmation" Flaw (Rewire R-token): The R-token variant was designed to fix the escape flaw by using a token ($\sigma_{Ps_i(V_j)}$) to link pseudonyms. However, Tamarin identified a previously unknown authentication vulnerability: the RA cannot verify that a "revocation successful" confirmation actually originated from the target vehicle. An adversary could intercept the request and spoof the confirmation, leaving the malicious vehicle active.
The O-TOKEN Protocol
To address these issues, the authors propose Obscure Token (O-token). Unlike previous protocols, O-token was co-designed with its formal model to ensure all security goals are met from the outset. It introduces an additional asymmetric key pair for an O-TOKEN ($\phi_{Ps_i(V_j)}$), which allows the RA to verify the revocation confirmation without needing to resolve the vehicle's long-term identity. This maintains privacy while providing a verifiable guarantee of successful revocation.
Results and Conclusion
The comparative analysis demonstrates that O-token is the only protocol to satisfy all defined security and functional requirements.
| Goal | Description | Plain | R-token | O-token |
|---|---|---|---|---|
| G1 | Executable (Sanity check) | ✓ | ✓ | ✓ |
| G2-G4 | Authentication Properties | ✓ | X | ✓ |
| G5 | Revoke after pseudonym change | X | ✓ | ✓ |
| G7 | Verifiable Revocation | n/a | X | ✓ |
While O-token provides a robust solution, it relies on the assumption of a secure Trusted Component within the vehicle. Future work will explore "liveness" properties—ensuring revocation requests must eventually succeed—and the impact of real-world network behaviors like heartbeats and signal blocking.
Summary updated