Security Analysis and Hardened Redesign of TrustCNAV for Reliable GNSS Civil Navigation Message Authentication in Transport Systems

Global Navigation Satellite Systems (GNSS) underpin safety-critical transport. Air traffic management, maritime navigation, rail operations, and logistics platforms depend on Positioning, Navigation, and Timing (PNT) derived from broadcast civil navigation message (CNAV) signals. The operational risk is not limited to jamming. A capable spoofer can inject forged navigation data while sustaining signal tracking, which turns a cyber intrusion into a physical hazard. TrustCNAV [1] targets this threat by proposing certificateless aggregate authentication for CNAV, aiming for immediate verification and low receiver workload without pairing operations.

The transport relevance of CNAV authentication is not uniform across application domains. In railway train-control architectures, forged or replayed navigation data can distort train-location reporting and degrade movement-authority logic. In aviation and uncrewed-aircraft settings, the more immediate concern is whether the receiver degrades safely when authenticated and non-authenticated data coexist or when message validation arrives too late for time-critical decision loops. In autonomous road systems, strict authentication may improve trustworthiness yet also reduce availability if only a subset of signals can be authenticated in real time. These scenario-dependent trade-offs mean that protocol latency, update trust, and failure handling matter as much as signature algebra [2], [3], [4]. For concreteness, the engineering interpretation in this paper centers on GNSS-based railway positioning, where authenticated CNAV screening can directly affect train-location reporting, movement-authority logic, and the decision to accept, reject, or degrade a suspect navigation update [4].

Work on GNSS threats and defenses shows why protocol guarantees should be tested against realistic field assumptions. Psiaki and Humphreys separated meaconing from structured synthesis and highlighted that defenses must accommodate receiver constraints and non-ideal propagation [5]. Humphreys argued that cryptographic checks matter only when the receiver also enforces time-consistency and a detection logic, because the attacker can exploit timing semantics without breaking message integrity [2]. Surveys confirm that spoofing equipment keeps getting cheaper, while GNSS receivers appear in more connected, software-managed transport systems that expand the attack surface [6].

Signal-level defenses such as distortion monitoring and correlation tests can raise the attacker’s cost, but their effectiveness varies with antenna configuration, multipath, and front-end quality [7]. Data-level defenses provide an explicit accept/reject gate at the navigation-message layer. GNSS authentication proposals built on unpredictable signal structures, delayed disclosure, and message authentication have clarified the security-latency trade space and have motivated deployment programs such as Open Service Navigation Message Authentication (OSNMA)-like mechanisms [3], [8], [9], [10], [11], [12], [13], [14]. At the same time, replay and distance-decreasing strategies remain practical in transport contexts because they target time-of-transmission and receiver policy rather than hash collisions or discrete logs [3], [10].

TrustCNAV’s key claim is that a certificateless, pairing-free signature structure can authenticate CNAV efficiently, and that aggregation across satellites reduces total verification time at the receiver [1]. This fits operational needs: receivers often validate multiple satellite messages per epoch, and even small per-message savings can accumulate into meaningful delay reductions. Still, transport deployments rarely satisfy the assumptions used in standard reductions. Ground segments can leak secrets. Parameter updates can travel over maintenance channels with uneven authentication. Implementation faults, especially nonce failures, can break otherwise sound algebra.

This paper presents an independent security analysis and hardened redesign of TrustCNAV. We examine whether a pairing-free certificateless CNAV authentication scheme remains trustworthy when transport-relevant deployment assumptions are relaxed, especially under nonce faults, unauthenticated public-parameter updates, and mixed-epoch buffering. To improve the practical relevance of the study, we also relate the protocol discussion to transport environments in which authentication delay or failure can affect rail positioning, aviation timing logic, or automated road navigation policies.

Our contributions are therefore: (i) an explicit reconstruction of TrustCNAV’s message flow and signature equations; (ii) vulnerability proofs with concrete attack traces and clarified deployment assumptions; (iii) a redesign that strengthens binding, nonce robustness, authenticated parameter distribution, and epoch invariants while keeping pairing-free verification; and (iv) a evaluation including communication overhead, transport-scenario interpretation, and bounded symbolic trace exploration for the specific attack classes studied here; the overall workflow appears in Figure 1.

GNSS spoofing analysis has long emphasized that authentication and detection interact: message integrity does not automatically yield a safe navigation solution unless the receiver constrains timing and consistency [2]. Psiaki and Humphreys cataloged the attack space, including replay/meaconing and structured synthesis, and argued that defenses must respect receiver cost and antenna constraints [5]. Surveys further document how spoofing threats evolve with software-defined radios and the growing integration of GNSS into Internet-of-Things (IoT)-like transport control stacks [6].

Navigation message authentication research has evolved along two broad lines. One line attaches cryptographic tags or signatures to navigation data, including one-way hash-chain variants and signature-based authentication in BeiDou-style settings [15], [16]. Another line leverages system structure through unpredictable data and delayed disclosure to provide origin authentication with deployment-friendly overhead. Studies of OSNMA testing, CHIMERA/OSNMA integration, and unpredictability mapping illustrate the practical limits of delayed disclosure, especially around time-to-first-authenticated-fix and receiver synchronization [9], [11], [12]. Parameter-selection work for delayed-disclosure protocols highlights the security-latency balance when receivers must wait for key release [13], and semi-assisted designs aim to reduce this waiting time under realistic link conditions [14]. Replay detection remains contentious: partial-correlation detection and worst-case attacker models show that a determined adversary can trade distortion against delay and can exploit mixed authenticated and non-authenticated environments during transitional deployments [10], [17], [18].

Recent developments indicate that GNSS navigation-message authentication is moving from proof-of-concept to operational and field-assessed deployment. The Galileo OSNMA Initial Service is now documented through an operational service-definition framework [19], and recent field work has examined OSNMA behavior under interference-affected radio frequency (RF) road environments [20]. At the same time, transport-specific studies show that spoofing materially affects GNSS-based railway train-positioning architectures and that resilience depends on how message authentication interacts with broader system design [4]. These developments sharpen the practical question addressed in this paper: whether a low-latency CNAV authentication protocol remains trustworthy when deployment assumptions about keys, updates, and batching are stressed.

Certificateless authentication and aggregation appear widely in transport networks outside GNSS. Vehicular Ad Hoc Networks (VANETs) use certificateless mechanisms to reduce certificate management overhead while retaining conditional privacy and traceability goals [21]. Pairing-free certificateless aggregate signatures and key-insulated certificateless authentication in IoT environments highlight recurring pitfalls: poorly authenticated public-key distribution can enable replacement attacks, and implementation faults can negate reduction proofs [22], [23]. Blockchain-based accountability layers have been proposed for GNSS message distribution, though they introduce operational complexity and depend on connectivity assumptions that do not always hold for avionics [24].

TrustCNAV sits at the intersection of immediate verification, certificateless keying, and aggregation [1]. Its novelty lies in binding CNAV structure to a pairing-free aggregate signature equation and claiming low receiver consumption [1]. Our manuscript focuses on the parts that determine real-world trust: authenticity of public parameters, robustness of nonce generation, and epoch-consistent aggregation policies.

We analyze the TrustCNAV protocol of Wu et al. [1] as an executable message-binding mechanism, then validate the redesign with a bounded symbolic trace-exploration layer. First, we extract the broadcast flow and rewrite it as explicit message instances $M_i$ where each CNAV packet carries (ID$_i$, $m_i$, $T_i$, $F_i$, $SIG_i$) and the receiver recomputes hashes and elliptic-curve relations; this makes parsing and canonical encoding part of the security claim. Second, we model the key schedule by separating KGC-issued components from Ground Control Station (GCS) secrets, representing them as compositional terms that can be substituted under compromise (Mas-Key, Pri-O_ID$_{i}$, Pub-T_ID$_{i}$) while keeping public artifacts (Mas-Pub, Pub-O_ID$_{i}$, Pub-T_ID$_{i}$, Pub-Key_ID$_{i}$) as attacker-observable. Third, we define adversary capabilities aligned with transport operations: an external spoofer who records and replays CNAV; a network attacker who can inject alternative public parameters; an insider who can extract secrets from the ground segment; and a fault-capable attacker who can induce nonce repetition during signing. Fourth, we set protocol invariants that must hold for safety, including (a) per-message authenticity before aggregation, (b) epoch consistency of all messages admitted into an aggregate check, and (c) non-recoverability of long-term signing keys from signature transcripts. Fifth, we search for violating traces through algebraic substitution and transcript construction.

In addition to these manual steps, we add a bounded symbolic trace-exploration layer rather than claiming a full mechanized proof. We describe the protocol using the following event predicates and safety query form:

The transition system explores honest broadcast, replay, parameter replacement, nonce-fault injection, epoch selection, batch verification, and optional fallback individual verification. To keep the search tractable, hash-equivalent states are merged, duplicate transcript prefixes are pruned, and exploration stops at user-defined limits on depth, batch size, and attacker actions. Under these bounds, the procedure finds the expected accepting traces against the original TrustCNAV variant and finds no accepting traces for the improved variant under the same modeled capabilities. We present these results as bounded symbolic evidence for the specific trace classes studied here, not as a general proof comparable to ProVerif or Tamarin [25], [26].

To keep the description consistent with the transport context, we also use standard modeling idioms as templates for key and trust binding:

These examples illustrate a device-derived seed without exposing a raw identifier, a session key bound to nonces and a context label, and trust updates based only on cryptographically verified events. They do not claim that TrustCNAV itself uses PUFs or game-theoretic utilities.

TrustCNAV is a broadcast authentication protocol for CNAV. Entities include a Key Generation Center/Key Management Center (KGC/KMC), a GCS, satellites $S_i$, and receivers [1]. The scheme operates over an elliptic-curve group with base point $P$ and master secret Mas-Key held by the KGC. The system parameters are summarized as:

Provisioning proceeds per satellite identity ID$_i$. The KGC selects $c_i$ in $\mathbb{Z}_p$ and computes the partial satellite values as follows:

It transmits (ID$_i$, Pub-O_ID$_i$, Pri-O_ID$_i$) to the GCS. The GCS chooses Pub-T_ID$_i$ in $\mathbb{Z}_p$ and computes:

For each CNAV payload $m_i$ at time $T_i$, the signer samples $f_i$ in $\mathbb{Z}_p$ and computes the following values:

The receiver checks freshness via a local window on $T_i$, recomputes $h_{1,i}$ and $h_{3,i}$, and verifies the individual signature equation:

For aggregation across satellites in the same positioning epoch, it computes:

The aggregate verification equation is:

TrustCNAV’s algebraic structure supports efficient verification, but several implementation- and deployment-facing issues can break its intended guarantees.

Nonce reuse collapses the effective signing key. The signature scalar follows:

Because the nonce is exposed through the transmitted elliptic-curve point, reuse is observable when the same satellite identity emits two broadcasts with the same $F_i$ but different ($m_i$, $T_i$):

Under that condition, an eavesdropper who records the two signature transcripts obtains:

Once SK$_i$ is recovered, the attacker forges signatures for arbitrary CNAV payloads $m^*$ by choosing $f^*$ with $F^*$ = $f^*\,\cdot\,P$, recomputing ${h_\mathrm{3}}^*$, and outputting:

Public-parameter replacement enables key-substitution traces when parameter acquisition or update is not strongly authenticated. Receivers typically learn Pub-O_ID$_i$ and Pub-T_ID$_i$ through operational channels, cached updates, or maintenance interfaces. If an attacker can replace these values for some ID$_i$, the verification equation becomes a lever. For a substituted key pair, the receiver computes:

An attacker who controls the substituted parameters can pick any scalar $x$, set the substituted public value, and craft an accepting transcript as follows:

This attack therefore targets deployments in which receivers obtain or refresh public parameters without a pinned trust anchor. If those parameters are already distributed in a signed package authenticated by the receiver, the attack does not apply; the problem is that the original TrustCNAV description does not fully specify such an authenticated operational path.

(i) KGC compromise expands into universal forgery under realistic leakage. The certificateless model splits trust between the KGC and the GCS. Yet the partial private value embeds Mas-Key linearly, and the public relation makes the dependency visible:

(ii) If Mas-Key leaks, a Type-II attacker can recompute Pri-O_ID$_i$ for any identity after observing Pub-O_ID$_i$. If, in addition, Pub-T_ID$_i$ leaks from the ground segment, the attacker reconstructs:

(iii) The attacker can then forge as in the nonce-reuse attack.

Freshness checks can be bypassed by replay within acceptance windows and by distance-decreasing traces. Each broadcast includes a timestamp $T_i$, and the receiver checks:

A meaconer who records the broadcast message and re-broadcasts it within the accepted window preserves signature validity:

Even when $\Delta T$ is tight, the attacker can shift perceived time-of-transmission in ways that alter pseudorange. The present redesign, therefore does not claim to defeat distance-decreasing attacks; it only narrows replay and batching abuse at the message-verification layer.

(iv) Aggregate authentication can accept mixed-epoch sets unless the receiver enforces per-message invariants. The aggregate check uses:

(v) This equation remains valid even if the set includes messages from different epochs, provided the attacker supplies the corresponding tuples ($F_i$, $\mathrm{SIG}_i$, $T_i$, $m_i$). Figure 2 sketches the original three-layer framework in which such cross-epoch mixing can happen at the receiver interface when broadcast data are buffered.

(vi) Missing point validation and subgroup checks create denial-of-service and edge-case acceptance risks. The verification equations assume that points $F_i$, Pri-O_ID$_i$, and Pub-T_ID$_i$ lie on the correct curve and have the correct order. If the receiver accepts malformed points, an attacker can inject $F_i$ = $\infty$ (point at infinity) or a small-subgroup element. Figure 3 and Figure 4 summarize the main attack surfaces across the satellite-ground-receiver path, including parameter substitution and replay injection.

These vulnerabilities do not contradict the original unforgeability reduction in the random-oracle model; they show that operational trust hinges on binding, parameter authenticity, and implementation correctness as much as on the hardness of discrete logarithms.

To address mixed-epoch batching concretely, the receiver applies Algorithm 1 (in the appendix) before batch verification. The flow uses aggregation as the primary fast path after structural admissibility checks, while individual verification is reserved for fallback diagnosis when a batch fails.

We keep the pairing-free certificateless structure, then harden three practical failure points: trust anchors, nonce robustness, and epoch-consistent aggregation. In the design, aggregation is retained because it can still reduce cost when used as the primary batch-verification fast path after inexpensive structural checks, rather than as a redundant post-check after every individual signature has already been verified.

Trust anchor for public parameters. A certificateless design still needs an authenticated distribution path for public parameters that the receiver uses during verification. Our paper treats satellite public parameters as a signed package issued by the authority and distributed through operational channels that the receiver can authenticate using a pinned authority public key. This package binds the identity, validity interval, and parameter digest, which prevents public-parameter replacement without inflating per-message bandwidth. In aviation-style deployments, the receiver can provision the authority public key during certification or maintenance, similar to how other safety-critical roots of trust are installed. Concretely, the receiver stores the authority public key during provisioning or maintenance, verifies the signature on each parameter package before any CNAV batch is accepted, checks the validity interval, and then loads Pri-O_ID$_i$ and Pub-T_ID$_i$ into a trusted parameter store. Any unsigned, expired, or mismatched package is rejected before batch verification begins.

Deterministic nonce and implementation robustness. The signer must prevent nonce repetition across reboots and failure modes. We adopt deterministic nonce derivation seeded by device entropy and protected by monotone state. This blocks signing-key recovery from repeated nonces while keeping computation lightweight. Receivers should validate curve points and reject unexpected identities before expensive verification.

Epoch-consistent aggregation. We redefine aggregation as the primary fast path rather than a redundant post-check. The receiver first performs inexpensive structural checks—canonical parsing, authenticated parameter lookup, point validation, epoch selection, and identity de-duplication—then executes one batch verification over the candidate set. Individual verification is reserved for fault isolation or logging only when the aggregate check fails. This preserves the computational rationale for aggregation while closing the cross-epoch mixing pitfall.

These steps keep TrustCNAV’s structure recognizable while tying operational acceptance to enforceable checks and authenticated inputs.

Table 1 summarizes replay handling, privacy, computation time, and the per-message authentication overhead for the three designs. The latency values should be read as reference software-side point estimates rather than deployment-certified hardware benchmarks. The reported latency figures should be read as representative software-side averages obtained from repeated runs under the same reference configuration.

We evaluate three designs: (a) baseline CNAV without cryptographic authentication, (b) original TrustCNAV, and (c) the improved protocol with authenticated parameter packaging, deterministic nonces, and epoch-invariant batch filtering. The evaluation should be read as a reference software study rather than an embedded hardware certification benchmark. To make the modeling assumptions explicit, Table 2 lists the configuration used in the software-side comparison. In this paper, the values in Table 1 are interpreted as representative averages from a software-based reference implementation study, and Table 2 makes the implementation environment, cryptographic instantiation, and run-to-run stability assumptions explicit.

Metrics follow:

We also add an overhead metric tailored to limited-bitrate navigation messages:

Because the present study compares protocol variants under the same reference workload, these metrics should be interpreted as software-side comparative indicators rather than certified field-performance guarantees.

Communication overhead accounting. TrustCNAV transmits an elliptic-curve point $F_i$ and a scalar $\mathrm{SIG}_i$ as its authentication data. Using compressed point encoding, the footprint is:

Our improved design binds an explicit epoch identifier to defeat mixed-epoch aggregation and replay acceptance. When the epoch identifier is transmitted, it can be encoded in 2 bytes:

The parameter package used to authenticate Pri-O_ID$_{i}$ and Pub-T_ID$_{i}$ is distributed out-of-band and does not inflate per-message CNAV size, which addresses the bandwidth concern for continuous broadcasts.

Latency and security outcomes. Under the reference software model, baseline CNAV yields high $S_\text{auth}$ under benign conditions but fails under injection because it lacks a cryptographic gate, and $D_\text{rep}$ stays near zero. Original TrustCNAV increases $D_\text{rep}$ when the timestamp window is tight, yet parameter substitution causes false acceptance if the receiver does not authenticate updates. Under a nonce-fault probability of 0.01 after a reboot, an attacker can recover the effective signing key after observing two signatures with repeated public nonce points, reducing $C_\text{res}$. The improved protocol prevents these failures in the modeled workloads by rejecting unauthenticated parameters, preventing nonce repetition, and enforcing epoch-consistent batching. The resulting authentication budget remains within the 1 Hz epoch window assumed in this study, but the accumulated 40.5–72.9 ms software-side cost for $n$ = 10 to 18 authenticated satellites may still be material for embedded receivers with tighter CPU, power, or real-time constraints. We therefore treat the reported values as reference software timings rather than deployment-ready guarantees for rail, aviation, or autonomous-vehicle platforms. In the representative railway-positioning scenario emphasized in this paper, a failed authenticated batch would mean that the affected GNSS message set is withheld from the train-location solution or handled in a degraded cross-checked mode rather than being silently accepted. This interpretation underscores that the reported timing values describe a protected message-screening stage in software, not a universal claim of end-to-end real-time suitability across all transport platforms.

Bounded symbolic trace-exploration results. The symbolic exploration procedure reports accepting attack traces for the original TrustCNAV variant, matching the vulnerabilities described in Section 4.2, and reports no accepting traces for the improved variant under the same modeled capabilities and search bounds. This analysis is deliberately limited: it checks only the modeled classes of nonce reuse, unauthenticated parameter replacement, replay handling, and mixed-epoch buffering. It should therefore be read as bounded symbolic evidence for the redesigned acceptance logic rather than as a general proof of protocol security.

Table 1 and Table 2 summarize the comparative overhead and reference evaluation assumptions used in the manuscript.

This paper presents an independent security reassessment of TrustCNAV by adding communication-overhead accounting, explicit trust-anchor discussion, transport-scenario interpretation, and a bounded symbolic trace-exploration layer. We showed that nonce faults and unauthenticated public-parameter updates can enable practical forgeries, and that weak epoch policies can undermine aggregation safety. The improved variant preserves pairing-free verification while adding authenticated parameter packaging, deterministic nonce generation, and epoch-invariant batch filtering. In the reference software study, these changes improve replay handling and compromise containment at the cost of additional verification latency. Important limitations remain: the present work does not defeat distance-decreasing attacks, the symbolic exploration is bounded and attack-class specific, and the reported timings are not hardware-level benchmarks for embedded transport receivers. Future work should therefore combine mechanized verification, authenticated-ranging or cross-sensor defenses, and platform-specific benchmarking on realistic rail, aviation, maritime, and autonomous-vehicle hardware. The practical deployment discussion is intentionally centered on GNSS-based railway positioning as a representative transport case, while broader applicability to aviation, maritime, or road platforms would still require platform-specific validation.