  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.
