When Cryptography Needs a Hand: Practical Post-Quantum Authentication for V2V Communications

When Cryptography Needs a Hand: Practical Post-Quantum Authentication for V2V Communications

Speakers: Geoff Twardokus

Conference: NDSS Symposium

YouTube: (no public video)

Overview

This talk, "When Cryptography Needs a Hand: Practical Post-Quantum Authentication for V2V Communications," presented by Geoff Twardokus, addresses the critical and immediate threat quantum computing poses to the security of connected vehicle technologies, specifically vehicle-to-vehicle (V2V) communication. V2V systems are fundamental to intelligent transportation and autonomous driving, enabling vehicles to broadcast essential safety messages (BSMs) containing data like location and heading. These BSMs are currently secured using Elliptic Curve Digital Signature Algorithm (ECDSA), a cryptographic primitive highly vulnerable to attacks by sufficiently powerful quantum computers. Given that vehicles sold today will remain on the road for 12-15 years, potentially until 2039 or beyond, and experts estimate a 50% chance of a quantum computer capable of breaking classical cryptography emerging within this timeframe, the need for a robust, quantum-resistant solution is urgent.

The core challenge lies in the lack of crypto agility in existing vehicle hardware security modules (HSMs) and the significant overhead of current Post-Quantum Cryptography (PQC) algorithms, which cannot be directly integrated into V2V systems due to stringent message size and latency constraints. An attacker with quantum capabilities could forge valid ECDSA signatures, leading to catastrophic scenarios such as fake emergency brake activations or multi-car pile-ups. Twardokus's work proposes a novel and practical approach to integrate PQC into V2V, focusing on a Partially Hybrid authentication protocol combined with an AI-enabled scheduling technique for certificate transmissions. This solution aims to balance security and performance, ensuring backward compatibility and minimal overhead, thereby laying a foundational path for quantum-secure V2V communications during the crucial transition period.

Background

[▶ Watch: Introduction: V2V security, quantum threat, and challenges (0:00)]()

V2V communication is designed to enhance road safety and efficiency by allowing vehicles to exchange Basic Safety Messages (BSMs) at least once every 100 milliseconds. These BSMs, along with security information, are encapsulated in Secure Protocol Data Units (SPDUs) and broadcast via technologies like DSRC (Dedicated Short Range Communications) or C-V2X (Cellular V2X). The security requirements are defined by IEEE 1609.2 and 1609.2.1 standards, which mandate ECDSA (specifically 256-bit or 384-bit elliptic curves) for digital signatures.

A critical component of V2V security is the use of pseudonym certificates. These certificates replace permanent user identities with ephemeral, cryptographically unlinkable identifiers, rotated every five minutes and valid for up to one week. They are essential for protecting the integrity of public signature verification keys. The standards define both explicit and implicit certificates, with the presented work focusing on explicit certificates as PQ implicit certificates are not yet available. To minimize transmission length and maximize system capacity, current standards dictate that a vehicle includes its full pseudonym certificate in only every fifth SPDU, transmitting a hash of the certificate in the remaining 80% of messages. This certificate transmission cycle is a key area identified for optimization. The Peer-to-Peer Certificate Distribution (P2PCD) protocol also allows vehicles to request unknown issuer certificates from peers, a mechanism that becomes problematic with the larger sizes of PQ algorithms.

V2V communication technologies impose strict constraints. DSRC, based on IEEE 802.11p, supports a maximum frame payload of 2,304 bytes. In contrast, C-V2X, utilizing 4G/5G cellular technology, has a much stricter maximum payload of only 437 bytes. This C-V2X limit is insufficient to contain even a single PQC signature, let alone a signature and public key, which can span thousands of bytes. Consequently, the research primarily focuses on DSRC.

The talk analyzed four prominent PQ signature algorithms: Falcon, Dilithium, Sphincs+ (NIST-standardized), and XMSS (a hash-based alternative). For NIST Level 1 security, Falcon-512, Dilithium-II, and Sphincs+-128s were selected. XMSS-SHA2_16_256 (Level 5) was chosen to provide at least 3,000 unforgeable signatures, necessary for a 5-minute pseudonym certificate validity. A direct replacement of ECDSA with any of these PQC algorithms in a Pure-PQ design was found to be infeasible, as their public keys, certificates, and signatures would exceed the DSRC 2,304-byte frame limit. Even a Fully Hybrid design, employing dual ECDSA-PQ signatures, would incur significant overhead, potentially only viable with Falcon but still with substantial frame size increases. This analysis underscored the necessity of a phased, highly optimized hybrid approach for PQC integration.

Key Findings

[▶ Watch: Current V2V security standards and certificate management (4:00)]()

The research makes several pivotal contributions to safeguarding V2V communications against quantum threats:

1. Phased Roadmap for PQ Transition: The talk establishes a clear, three-era roadmap for V2V's transition to a quantum-secure future. Era A_v, starting today, addresses the immediate threat where ECDSA could be broken within 'v' hours (e.g., 2038 for a 1-hour break time, requiring 317 million qubits). Era B (mid-2030s) envisages new hardware and protocols enabling fully hybrid authentication. Era C (around 2045) marks the full transition to a pure-PQC ecosystem. The presented work focuses on Era A_v, assuming current hardware and protocol constraints.

1. Partially Hybrid Authentication Protocol: This novel protocol is designed for the urgent Era A_v. It continues to sign BSMs with classical ECDSA but crucially protects the integrity of the ECDSA verification key within the pseudonym certificate using dual ECDSA-PQ signatures. This means the issuer's signature on the pseudonym certificate is quantum-secure. To provide robust, near-term protection against quantum forgery, the validity period of the ECDSA verification keys is reduced from one week to 'v' hours (e.g., 1 day), with 'v' being adjustable as quantum attack capabilities evolve. The protocol is provably secure under the i-unforgeability definition, ensuring its resilience as long as the underlying ECDSA, PQ algorithm, and hash function remain secure.

1. AI-Enabled V2V Spectrum Optimization: The research identified a significant inefficiency in current V2V standards: up to 99.3% of full certificate transmissions are redundant, as receivers often already possess the necessary certificates. To address this, an innovative machine learning model, a random forest classifier, is introduced. This model enables vehicles to act as intelligent agents, adaptively reducing full certificate transmission intervals based on environmental factors like vehicle density and distance to neighbors. It predicts optimal intervals (500, 1000, 2000, or 5000 ms) and data rates (6 or 9 Mbps). Trained on diverse VEINS simulations, the classifier achieved 94% accuracy, effectively conserving spectrum and maintaining certificate dissemination latency by leveraging an extended P2PCD protocol for proactive certificate requests.

1. Falcon-512 as the Only Viable PQC Algorithm: Extensive experimental validation, considering strict DSRC frame size limits and latency requirements, identified Falcon-512 as the only NIST-approved PQC algorithm currently viable for V2V applications. Other candidates like Dilithium, Sphincs+, and XMSS were found to exceed frame duration or signature verification time constraints, making them unsuitable for the current V2V environment. For instance, Falcon achieved a system capacity (U_max) of 101 vehicles based on frame duration and 224 vehicles based on signature verification time on Qualcomm ARMv8 V2V chipsets, comfortably exceeding the 100-vehicle requirement. It also met the 10 BSM/second signing rate.

1. Minimal Overhead and Backward Compatibility: The combined Partially Hybrid design and AI-enabled spectrum optimization demonstrate remarkable efficiency. Simulations showed an average added delay of only 0.39 ms per message compared to pure ECDSA in high-density traffic (100 vehicles/km), which is negligible given the substantial security upgrade. The Frame Loss Ratio (FLR) increased by a minimal 7-8% (e.g., from 0.42 to 0.45 at 100 vehicles/km) with the optimized hybrid approach, confirming its low overhead. Crucially, the design supports backward compatibility, allowing non-PQC-capable vehicles to ignore PQ components and continue verifying ECDSA signatures, facilitating a smooth transition via software updates.

Technical Deep Dive

[▶ Watch: PQC algorithm analysis and V2V frame size limitations (6:00)]()

The proposed solution addresses the quantum threat to V2V communications through a carefully structured, phased approach and innovative technical mechanisms.

The phased transition roadmap (conceptually shown in Figure 5 of the original presentation) delineates three distinct eras:

• Era A_v: The immediate period, lasting until ECDSA becomes vulnerable to quantum attacks within 'v' hours. This era is characterized by the need to protect existing ECDSA-based systems without requiring new hardware. The presented Partially Hybrid design is specifically tailored for this era.
• Era B: An overlapping transition phase where new hardware and improved communication protocols enable a Fully Hybrid PQ authentication scheme. This is hypothesized to begin around the mid-2030s.
• Era C: The final phase, likely around 2045, where ECDSA is disallowed, leading to a Pure-PQ ecosystem.

The research focuses intensely on Era A_v due to its immediate relevance and the constraints of current V2V hardware and protocols. The cornerstone of the solution for this era is the Partially Hybrid design. This design maintains the use of classical ECDSA for signing individual BSMs, which are generated at a high rate (10+ per second) and require rapid verification. However, the critical innovation lies in how the pseudonym certificates are secured. Instead of relying solely on an ECDSA signature from the Certificate Authority (CA) for the vehicle's public key, the hybrid certificate employs dual ECDSA-PQ signatures by the issuer. This means that the issuer's key pair, and thus the signature on the pseudonym certificate containing the vehicle's ECDSA verification key, is protected against quantum attacks.

The hybrid certificate structure (formally defined in Table II of the original presentation) combines an explicit ECDSA certificate with a PQ-based certificate over the same ECDSA verification key. It includes fields for the PQ signature algorithm and the PQ signature generated by the issuer, alongside the classical ECDSA signature. To mitigate the quantum threat against the vehicle's BSM signing key, the validity period of the ECDSA verification keys is significantly reduced to 'v' hours (e.g., 1 day) from the current standard of one week. This parameter 'v' can be dynamically adjusted as quantum computing capabilities evolve, providing an adaptive layer of security.

Meeting DSRC's 2,304-byte frame size constraint for these larger hybrid certificates is achieved through fragmentation. The hybrid certificate is split into multiple parts (C_1 to C_α), which are then transmitted across several SPDUs within a certificate transmission cycle. The number of fragments, α, is optimized to be minimal while ensuring each SPDU remains within the payload limit.

The threat model assumes an adversary capable of observing, dropping, replaying, or altering SPDUs, with the goal of spoofing or altering BSMs and forging certificates. The adversary is assumed to have quantum capabilities, specifically being able to break ECDSA within 'v' hours, requiring 13 to 317 million qubits depending on the attack timeframe. However, the attacker cannot acquire more than one pseudonym certificate per CA, and secure computations, honest CAs, and valid certificates for legitimate pseudonyms are assumed.

To manage the increased data volume from hybrid certificates without impairing communication reliability, the system incorporates AI-Enabled Spectrum Optimization. The research found that current V2V security standards lead to a staggering 99.3% redundancy in full certificate transmissions. To counter this, vehicles are empowered as intelligent agents utilizing a random forest classifier to adaptively reduce the frequency of full certificate transmissions. This machine learning model predicts the optimal full-certificate SPDU interval (500, 1000, 2000, or 5000 ms) and data rate (6 or 9 Mbps). The model's learning parameters include estimated vehicle density (derived from received SPDU count) and distance to neighboring vehicles (estimated by RSS). Trained on diverse VEINS simulations, this classifier achieved 94% accuracy, significantly reducing spectrum usage. It extends the IEEE 1609.2 P2PCD protocol to allow vehicles to proactively request pseudonym certificates from peers, ensuring that certificates are still disseminated efficiently despite increased transmission intervals.

The system design and architecture (illustrated conceptually in Figure 6 of the original presentation) operates in three stages within each certificate transmission cycle (τ BSMs):

1. Stage 1 (i = 1 to α-1): The sender transmits a BSM, its ECDSA signature, a hash of the hybrid certificate, and a fragment C_i of the hybrid certificate. The receiver collects these fragments.
2. Stage 2 (i = α): The sender transmits the last fragment C_α. Once all fragments are received, the receiver reconstructs the full hybrid certificate C_s. It then performs dual verification, using both the PQ and ECDSA signatures on the certificate. If valid, the ECDSA verification key pk_s is extracted and marked as verified. If verification fails, BSM processing is delayed.
3. Stage 3 (i = α+1 to τ): For subsequent messages within the cycle, the sender transmits only the BSM, its ECDSA signature, and the hash of the hybrid certificate. The receiver verifies the BSM using the previously extracted and verified pk_s.

Crucially, the design ensures backward compatibility. The Partially Hybrid design can be deployed via software updates. Non-PQC-capable vehicles can simply ignore the PQ certificate components, continuing to verify only the ECDSA signatures. To prevent rollback attacks, the protocol assumes all vehicles send and expect hybrid certificates, with the sender's certificate explicitly indicating its PQ-signing capabilities. The formal security analysis, captured by Theorem 1 and Corollary 1, bounds the adversary's advantage in forging V2V messages. It demonstrates that the protocol's i-unforgeability is bounded by the existential unforgeability of ECDSA for BSM forgery, the minimum of ECDSA and PQ existential unforgeability for certificate forgery, and the second pre-image resistance of the hash function, ensuring security as long as these underlying primitives hold.

Demo / Proof of Concept

[▶ Watch: Proposed phased transition roadmap for quantum-secure V2V (8:00)]()

To thoroughly evaluate the proposed Partially Hybrid authentication protocol and AI-enabled spectrum optimization, a comprehensive testbed named PQ-V2Verifier was developed. This testbed represents a significant overhaul of the existing open-source V2Verifier, specifically enhanced to support DSRC and IEEE 1609.2-compliant BSM signing and verification using ECDSA, along with expanded certificate verification functionalities from IEEE 1609.2.1 and optimizations for high-volume signature operations.

For cryptographic algorithm implementations, the researchers leveraged established open-source libraries. Botan was used for ECDSA, Dilithium, and XMSS, while liboqs provided implementations for Falcon and Sphincs+. The experimental setup utilized a diverse range of hardware, including laptops connected to Universal Software Radio Peripheral (USRP) SDRs to emulate V2V devices in both indoor and outdoor environments. Additionally, real V2V devices equipped with Qualcomm chipsets were used to assess the performance of PQC algorithms on industry-standard hardware, providing a realistic measure of viability despite the PQC implementations not being fully optimized for ARMv8 architectures.

For large-scale simulations, a custom module called PQ-VEINS was built for the widely recognized VEINS simulator. VEINS is a powerful tool that combines vehicular traffic modeling with DSRC simulation, allowing for the realistic assessment of wireless communication challenges in vehicular networks. The PQ-VEINS module specifically implemented the IEEE 1609.2 security standards, the proposed Partially Hybrid design instantiated with Falcon-512, and the AI spectrum optimization technique. Simulations were conducted in urban environments modeled after Erlangen, Germany, under varying traffic densities (60 and 100 vehicles/km) over 100 iterations for each scenario, providing robust statistical data on scalability, efficiency, and reliability.

The evaluation results confirmed the practical viability of the proposed solution. In terms of scalability, Pure ECDSA achieved a maximum supported vehicle count (U_max) of 165. For the Partially Hybrid design, only the Falcon-512 instantiation met the requirement of supporting at least 100 vehicles, achieving a U_max of 101 based on frame duration constraints and a robust 224 based on signature verification time on Qualcomm ARMv8 V2V chipsets. Dilithium, Sphincs+, and XMSS instantiations yielded U_max values below 100 or significantly slower verification times, rendering them unsuitable. Falcon also demonstrated the ability to sign 32 messages per second, comfortably exceeding the 10 BSMs per second requirement.

Efficiency was measured by the end-to-end delay per BSM. In simulations with 100 vehicles/km, Pure ECDSA had a total end-to-end time of 903.4 μs. The Partially Hybrid design without AI optimization increased this to 1572.4 μs, adding approximately 0.6 ms. However, with the AI spectrum optimization, the total time was reduced to 1303.3 μs, resulting in a negligible average added delay of only 0.39 ms per message compared to ECDSA. This demonstrates the significant impact of the AI optimization in mitigating PQC overhead.

Reliability was assessed using the Frame Loss Ratio (FLR). For 100 vehicles/km, ECDSA had an FLR of 0.42. The Partially Hybrid without AI increased FLR to 0.68 (+61.9%). Critically, with AI optimization, the FLR was only 0.45, an increase of just 7.1% compared to ECDSA. Outdoor experiments using USRPs in real vehicles further corroborated these findings, with the Falcon-based Partially Hybrid design showing a frame loss rate of 7.4% compared to 1.2% for ECDSA, reinforcing its practical viability and low overhead in real-world conditions.

Defensive Implications

[▶ Watch: Core idea of the Partially Hybrid authentication design (8:45)]()

The findings from this research provide crucial guidance for defenders—automakers, transportation infrastructure providers, and standards bodies—to proactively address the quantum threat to V2V communications. Immediate action is warranted given the long lifespan of vehicles and the projected timeline for quantum computer development.

Firstly, prioritizing crypto agility in future V2V hardware security modules (HSMs) is paramount. While this research provides a software-deployable interim solution, the long-term goal should be hardware that can seamlessly integrate new cryptographic primitives, including future PQ algorithms, without requiring extensive recalls or over-the-air updates that often suffer from low adoption rates.

Secondly, implementers should focus on the Partially Hybrid authentication protocol as a practical and immediate step. This involves updating existing vehicle software to protect the issuer's signature on pseudonym certificates with dual ECDSA-PQ signatures, even while BSMs continue to be signed with classical ECDSA. This can be achieved through over-the-air (OTA) software updates for currently deployed vehicles, leveraging the backward compatibility feature of the design.

Thirdly, the research strongly advocates for the adoption of Falcon-512 as the preferred NIST-approved PQC algorithm for DSRC-based V2V systems. Its demonstrated viability in meeting stringent frame size and latency constraints makes it the most suitable candidate among current PQC standards. This recommendation should inform procurement decisions and future standard updates for V2V security.

Fourthly, the AI-enabled spectrum optimization technique should be integrated into V2V communication stacks. By adaptively reducing redundant certificate transmissions, this technique not only mitigates the overhead introduced by larger PQ certificates but also enhances overall system capacity and efficiency. Defenders should explore deploying machine learning models within vehicular systems to dynamically manage communication resources.

Fifthly, standards bodies (e.g., IEEE) must evolve V2V security standards to formally incorporate hybrid certificates and the phased transition roadmap. This includes defining specifications for hybrid certificate structures, fragmentation mechanisms, and updated certificate management protocols that can accommodate both classical and quantum-resistant components. The concept of attenuating certificate validity periods (e.g., from one week to 'v' hours) should also be considered as an adaptive security measure.

Finally, while the current work primarily focuses on DSRC, defenders must acknowledge the future challenge of C-V2X integration. Despite its stricter payload limits making direct PQC integration currently impractical, research and development efforts should be initiated to devise innovative solutions for quantum-secure C-V2X, anticipating its growing importance in connected vehicle ecosystems. This proactive stance will ensure a robust and future-proof security posture for intelligent transportation systems.

Key Takeaways

• Quantum Threat is Imminent: Connected V2V communications face a severe and near-term threat from quantum computers, capable of breaking current ECDSA-based security protocols within the lifespan of vehicles on the road today.
• Direct PQC Integration is Infeasible: Current NIST-standardized Post-Quantum Cryptography algorithms introduce too much overhead (large signature/key sizes, high latency) for direct, wholesale replacement of ECDSA in V2V systems under existing DSRC or particularly strict C-V2X constraints.
• Partially Hybrid Approach for Transition: A novel Partially Hybrid authentication protocol that uses classical ECDSA for BSM signing but protects pseudonym certificates with dual ECDSA-PQ signatures, combined with an AI-enabled spectrum optimization technique, provides a practical and provably secure solution for the initial transition period.
• Falcon-512 is the Most Viable: Extensive experimental validation identified Falcon-512 as the only NIST-approved PQC algorithm that meets the strict scalability, efficiency, and reliability requirements for V2V applications under current DSRC constraints.
• Minimal Overhead: The combined hybrid protocol and AI optimization add a negligible average delay of only 0.39 ms per message and a minimal increase in Frame Loss Ratio (7-8%), demonstrating its efficiency and practicality for safety-critical V2V systems.
• Backward Compatibility is Crucial: The proposed design ensures backward compatibility, allowing non-PQC-capable vehicles to continue operating, which is essential for a smooth and widespread adoption via software updates.

About the Speaker(s)

Geoff Twardokus presented this work, "When Cryptography Needs a Hand: Practical Post-Quantum Authentication for V2V Communications," at the NDSS Symposium. While specific biographical details such as his title or affiliation are not provided in the transcript or metadata, the technical depth and practical focus of the research suggest expertise in cybersecurity, cryptography, and intelligent transportation systems, likely within an academic research institution or an industry R&D department. His work demonstrates a keen understanding of the unique challenges and constraints of securing safety-critical V2V environments against emerging quantum threats.