Formal Analysis of V2X Revocation Protocols

Jorden Whitefield, Liqun Chen, Frank Kargl, Andrew Paverd, Steve A. Schneider, Helen Treharne, Stephan Wesemeyer

TL;DR

Researchers used the Tamarin prover to formally analyze "Rewire," a state-of-the-art protocol for revoking malicious vehicles in V2X (Vehicle-to-Everything) networks. They discovered critical flaws in existing versions—including a previously unknown authentication vulnerability—and proposed a new, formally verified protocol called Obscure Token (O-token) that ensures secure revocation without sacrificing driver privacy.

What Problem Does This Paper Address?

In Intelligent Transportation Systems (ITS), vehicles constantly broadcast their location and status. To prevent tracking (privacy), vehicles use "pseudonyms"—temporary digital credentials—instead of a single long-term ID.

The challenge arises when a vehicle misbehaves (e.g., broadcasting fake traffic data). The Revocation Authority (RA) must be able to invalidate all of that vehicle's pseudonyms. However, if the revocation process makes it easy to link all pseudonyms back to a single identity, privacy is destroyed. Existing protocols like "Rewire" attempted to solve this using trusted hardware on the vehicle, but their security had only been evaluated informally. This paper seeks to provide a rigorous, formal guarantee that these protocols actually work as intended.

Methods

The authors employed formal verification using the Tamarin prover, a powerful symbolic analysis tool.

  • Modeling: They translated the protocols into multiset rewriting rules and first-order logic.
  • Adversary Model: They assumed a "Dolev-Yao" adversary, who controls the entire network (can intercept, delete, or inject messages) but cannot break standard cryptography or access the vehicle's internal Trusted Component (TC).
  • Proof Goals: They defined seven specific goals (G1–G7) to test the protocols, ranging from basic executability to complex properties like "non-injective synchronisation" (ensuring messages happen in the right order) and "Revoke after change" (ensuring a vehicle can't escape revocation by switching pseudonyms).

Datasets

As this is a formal methods paper focusing on protocol logic rather than empirical data, no traditional datasets (like traffic traces or image sets) were used. Instead, the "data" consists of the formal models of the three protocols (Rewire Plain, Rewire R-token, and O-token), which the authors have made publicly available for the research community.

Key Insights and Ideas

  • The "Pseudonym Escape" Flaw: In the simplest version of Rewire (Plain), a vehicle can dodge a "revoke" command simply by switching to a new pseudonym before the command arrives. The protocol fails because the vehicle's hardware only looks for commands addressed to its current active pseudonym.
  • The "Spoofable Confirmation" Flaw: The more advanced "R-token" version was designed to fix the escape flaw. However, the formal analysis revealed a new, unknown vulnerability: the Revocation Authority (RA) cannot actually verify that a "revocation successful" confirmation message came from the target vehicle. An attacker could intercept the revocation request and send a fake confirmation, leaving the malicious vehicle active on the road.
  • Co-Design is Key: The authors argue that security protocols should be "co-designed" with formal models. Their proposed O-token protocol was built specifically to satisfy the formal requirements that the previous protocols failed.

Key Results

The paper compares three protocols against seven security and functional goals:

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 ✓
  • Rewire Plain failed functional correctness (G5).
  • Rewire R-token failed all authentication properties (G2-G4) and verifiable revocation (G7).
  • O-token passed all seven goals. It achieves this by adding a unique asymmetric key pair to the pseudonym that allows the RA to verify the confirmation message without ever needing to resolve the vehicle's long-term identity.

Limitations and Future Work

  • The "Trusted Device" Assumption: The protocol relies on a Trusted Component (TC) inside the car that is guaranteed to delete keys when told. The authors acknowledge that the industry is still debating the right trust model for these devices.
  • Liveness: The current analysis proves that if a confirmation is received, it is valid. Future work aims to prove "liveness"—the guarantee that a revocation request must eventually result in a confirmation.
  • Heartbeats: Real-world implementations often use "heartbeat" messages to ensure vehicles stay connected. The authors suggest that future formal models should incorporate time and heartbeats to model more complex adversarial behaviors, such as an attacker physically blocking revocation signals.

Summary updated

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.
BibTeX
@inproceedings{whitefield2017formal,
  author = {Jorden Whitefield and Liqun Chen and Frank Kargl and Andrew Paverd and Steve A. Schneider and Helen Treharne and Stephan Wesemeyer},
  title = {{Formal Analysis of V2X Revocation Protocols}},
  booktitle = {STM},
  year = {2017},
  doi = {10.1007/978-3-319-68063-7\_10},
}

Loading related content...

Figure