Authentication of Satellite-Based Augmentation Systems with Over-the-Air Rekeying Schemes

2.1 ECDSA Key Structure

We propose a two-level ECDSA key structure, as suggested by Neish (2020).

Level-1 keys will be 256-bit-security ECDSA keys managed internationally by a trusted Certificate Authority (CA). Each level-1 key will be in use for 100 weeks. The CA will compute a large number of level-1 keys for use in the perpetual future and will encrypt each key individually via AES-128 with different AES encryption keys (one for each level-1 key) maintained as secret by the CA. The CA will distribute the AES-ciphertext to receiver manufacturers. Receivers will be preloaded with the collection of 512-bit public keys and encrypted with 128-bit keys via the AES-128. As level-1 keys expire, the CA will distribute the keys to decrypt the AES-ciphertext, one at a time, for the Provider to distribute via MT51. As the receiver receives the key to decrypt its onboard AES-ciphertext, it will update its current level-1 ECDSA public key. Each level-1 public key will be 512-bits. Any signature derived therefrom will be a 1024-bits.

Level-2 keys will be 128-bit-security ECDSA keys managed by the Provider. Each level-2 key will be in use for ten weeks. To create a new level-2 key, the Provider will generate a secure-random private ECDSA key and an associated public key. The Provider will then submit the new public key to the CA for a signature from the CA’s current level-1 key. Provider will then distribute the new public key and the associated authenticating signature over the SBAS. The receiver will receive a new level-2 public key and the authenticating signature, verifying the received new level-2 public key with the associated decrypted level-1 public key.

The Provider will use the level-2 keys to authenticate the TESLA Hash Path Ends. Keys derived from the TESLA Hash Paths will be used to authenticate the bulk of SBAS messages with HMACs. For all levels, the authenticating pseudorandom data delivered will accompany data (e.g., SBAS message preamble, MTs, and other data) that must be sent as per the definitions described below. A specific signature must be derived from the entire SBAS message used to deliver that particular key. Concretely, when a level-1 key authenticates a level-2 key, the level-1 signature must be derived from the entire set of messages used to deliver the level-2 key and the expiration time of the accompanying key. In other words, the level-1 signature must be derived from the complete messages containing overhead data, not just from the level-2 key itself. If this does not take place, then the accompanying data, most notably the key expiration times, will not be secured by the cryptographic primitives.

2.2 TESLA Hash Path and HMAC Keys

Each TESLA Hash Path will be used over one week. The Provider will generate an entire Hash Path before its actual use and then broadcast the Hash Path End signed by the current level-2 ECDSA key via MT51. Each Hash Point, except the Hash Path End, will be associated with at least five HMAC keys that will be used to authenticate at least five messages with HMAC, depending on the number of iterations of Equation (2). Therefore, a Hash Path will include 100,801 Hash Points, one for each sixth second for the week, and one for the Hash Path End.

To generate a Hash Path P, the Provider will derive a secure random 128-bit salt S^P from level-2 ECDSA authentication, as described in Section 3.2.1. Let the Hash Points of P be denoted , and let t_i be the time at which the Provider publicly releases via broadcast. Here, t_i is an integer time (e.g., time in seconds since the GPS epoch). We propose Equation (1) to define the Hash Path where || denotes bit concatenation and ⊘ denotes integer division.

1

The purpose of the integer division is explained in Section 3.2.2. We propose a left-most 16-bit truncated signature from HMAC that authenticates each SBAS message delivered via MT50. Each message m_j, sent at t_j, will be provided with a unique HMAC key k_j. The key k_j for each message m_j will be generated according to Equation (2). The signature s_j derived therefrom will be according to Equation (3). t_j is the integer time that the authenticated message will be broadcast and received. PRN is the pseudorandom code associated with the broadcasting geostationary satellite. Frequency is the frequency band of the particular transmission (e.g., a string containing L1 or L5). We discuss the necessity of the concatenation and HMAC operations of Equation (2) in Sections 3.2 and 3.3. Equation (2) ensures that the HMAC for each message from each satellite has its own key.

2

3

The output of Equation (3) is truncated to its 16 most-significant bits. We note that because Equation (1) uses a concatenation operation because the input data is less than 512-bits, the block size for the selected Hash Function. Equation (1) would need to be modified if the input data were to be larger than 512-bits; this will be critical to mitigate length extension attacks (Boneh & Shoup, 2017).

Section 2.5 and Algorithms 1 and 2 describe how the Provider and receivers should perfrom authentication, queueing, and caching to verify messages.

2.3 Message Type (MT) 50

The findings shown in Table 1 present our proposed definition of MT50 with bit allocations. The Provider will send an MT50 with every six messages. The delayed key release used to authenticate messages means that each message will be authenticated between 7 and 11 seconds after its broadcast. Provider should set the cadence of the integrity messages so that each immediately precedes the scheduled MT50s to minimize the time needed for their authentication. If the receiver cannot authenticate a message because of a lost MT50, it generally disregards the message. (Information that alerts the receivers to decrease the level of trust need not be disregarded). Within the message definition, there are five 16-bit HMACs and one 128-bit Hash Point. Once the receiver receives an MT50, the five HMACs included correspond to the previous messages with a secret Hash Point known only to the Provider at the message sending time. The 128-bit Hash Point included corresponds to the HMACS included in the previous MT50 message sent six seconds earlier. Figure 3 provides a conceptual diagram of the delayed Hash Point key release.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 3

A conceptual diagram of how consecutive MT50 messages relate to each other The colors correspond to a specific Hash Point along the Hash Path. Each MT50 includes the HMACs of the five previous messages and the Hash Point used for the HMACs sent with six earlier messages.

As per the SBAS specifications, in the event of a GNSS integrity alert, an alert message must be sent by the Provider with four messages in a row. Therefore, occasionally an alert message will take priority over an MT50. The salted Hash Function described in Equation (1) accommodates small perturbations to the schedule resulting from alert messages as described in Section 3.2.2 and Figure 4. Even with an MT50 delay, each MT50 must sign the messages that it would have signed without an alert as described in Section 3.2.2.

• Download figure
• Open in new tab
• Download powerpoint

FIGURE 4

Conceptual diagram of accommodations made by the counter scheme to perturbations in the MT50 schedule

In the diagram, “m” denotes a standard message, and “I” represents an integrity message. Integrity messages that would be sent on a nominal schedule are marked blue and additional integrity messages during an alert are marked in yellow. Note that T ⊘ 6 does not change in the event of an alert message MT50 delay, as shown in red; thus, the Hash Path is preserved.

2.4 Message Type (MT) 51

In this work, we provide two MT51 definitions with a 128-bit OTAR Payload Segment and an 84-bit metadata section. This version includes many features that could be relevant to SBAS stakeholders. We have not specified which features should be incorporated. This will be deferred until all SBAS stakeholders have had their considerations heard. The information in Section 4.1 discusses how to modify the 128-84-bit allocation if SBAS stakeholders would prefer not to use the additional features described later in the text. However, given the academic context of this work, and because our design meets the key performance indicators (KPIs), we choose to publish the 128-bit feature-rich design. Tables 2 and 3 provide our proposed definition of MT51 with bit allocations. The Provider must broadcast MT51 messages for approximately 1 in every 18 messages for MT51 as described in Section 4.4. These messages do not need to be sent on a rigid schedule; they can be sent in the extra space within the current SBAS schedule.

The payload section for MT51 is only 128-bits which leaves 84-bits for metadata that describes how a receiver should interpret the 128-bit payload. The larger 84-bits allows users to introduce additional features, such as parallel and redundant key management as well as several other features explained later in the text. Table 4 provides an sample set of unique MT51 messages, each containing a 128-bit segment per message, that form an Authentication Stack (defined in Section 2.5). To distinguish the key updated with a specific MT51 and the key used to authenticate that MT51, we call the key associated with the MT51-delivered payload the Germane Key and the key used to authenticate that delivered payload the Authenticating Key. The metadata specifies the following, matching the order shown in Table 3. (1) it will identify the system to which the Germane Key applies; (2) it will specify whether the payload is an ECDSA public key, an AES decryption key for an ECDSA public key, or a TESLA Hash Path End; (3) it will provide a 16-bit hash of the entire Germane Key so that the receiver can immediately associate the OTAR Payload Segment with a specific key; (4) it will designate the expiration time of the Germane Key; (5) it will provide a 16-bit hash of the entire authenticating key so that the receiver can immediately associate the authenticating pseudorandom data OTAR Payload Segment with a specific authenticating key; (6) it will specify whether the payload itself is a key or authentication signature; (7) it will identify the segment number of the authenticating pseudorandom data so that the receiver can aggregate the authenticating pseudorandom data segments over time.

The signatures used to authenticate a particular key must be derived from the entire set of full MT51 messages used to deliver them. The metadata associated with authenticating pseudorandom data includes the expiration time. These keys are only secure for specific lengths of time, as described in Section 2.1 and 2.2; hence, the expiration time must be authenticated together with the corresponding authenticating pseudorandom data so that each key is retired securely. After the expiration of a particular key, receivers must reject all messages signed with the expired key.

2.5 Procedures

Algorithm 1 describes the procedure needed by the Providers to use TESLA securely. In addition, the Providers must assemble OTAR data by coordinating with the CA as described in Section 2.1. Algorithm 2 captures how a receiver should operate beginning with a cold start and includes specifications of some of the onboard data structures that should be used to track key maintenance. The term “cold start” is used to describe use of a receiver that has been off for an extended period with onboard Level-2 ECDSA or TESLA information that has expired according to its onboard clock. Upon cold start, a receiver must track and record incoming SBAS messages. A receiver should not use any unauthenticated data. NB: the complete set of MT51s is self-authenticating. Therefore, it must track the incoming MT51 messages until it has received a complete set of unexpired Level-1 ECDSA public key, Level-2 ECDSA public key, TESLA Hash Path End, and the associated signatures (collectively known as the “Authentication Stack”). The receiver must track and store MT51 messages until the aggregate OTAR Payloads of authenticating pseudorandom data provides a successful ECDSA authentication of the entire Authentication Stack, including a level-1 key onto a level-2 key and a level-2 key onto the Hash Path End. Until it has received and verified a complete set of unique MT51s included in the Authentication Stack, the receiver cannot assert an authenticated fix and must ignore the SBAS corrections and integrity data (i.e., non-MT51 messages) derived from incoming messages. Once the Authentication Stack is received and verified by ECDSA, the receiver can process and authenticate MT50 messages via TESLA and can also associate the MT50-delivered HMACs with messages to authenticate and process the SBAS correction and integrity data. The Provider repeatedly broadcasts the current Authentication Stack, as discussed in Section 4.4 to accommodate random receiver startups.

Algorithms 1 and 2 delineate only the single satellite and single frequency cases. To augment those algorithms to handle the multiple satellite or multiple frequencies, five messages should be signed and verified for each satellite and each frequency, as described by Equations (2) and (3). This means that the MT51 Authentication Stack is used for all satellites and frequencies, but each message for each satellite and frequency is provided with its own authentication via TESLA. By reusing he same Authentication Stack for all satellites and frequencies, we exploit the scalability of TESLA allowing for smaller TFAFs (see Section 3.2).

Upon full receipt of the Authentication Stack, receivers must hash the Hash Point from the most recent MT50 to the MT51-provided Hash Path End. In the special case in which the receiver has only been off a short time, turned offline, and then turned back online during the use of the same Hash Path, the receiver TFAF is the time required to hash to the Hash Path End. The worst-case number of hash computations is the length of the Hash Path (about 100,000) and will occur when a receiver first turns on at or near the expiration of the Hash Path. With standard commodity hardware (e.g., an Intel Core i5 Processor), a worst-case time of approximately 10 seconds will be observed if a receiver is turned on immediately before a Hash Path expires. We measured this time by experimenting with personal laptops that were not specifically built for this process. With hardware acceleration, this process time could decrease and evaluated in parallel with other standard receiver processes. This initial hashing computation only occurs when the receiver is turned on and should not hinder processing SBAS navigation data in real-time after an authenticated fix.

3.1 TESLA Loss Tolerance

TESLA allows receivers to derive missed Hash Points from Hash Points released later along the Provider’s pre-computed Hash Path that has been kept secret. For example, suppose a receiver misses an MT50 message and therefore does not receive a Hash Point. The receiver can derive that missing Hash Point by computing the Hash of the next released Hash Point. In another example, suppose a receiver misses several day’s worth of Hash Points; upon receipt of a new Hash Point, the receiver can hash all the way down to the Hash Path End as described in Equation (1) to document the new messages’ immediate authenticity. This property scales along the length of the Hash Path. If a receiver is off longer than the Hash Path’s length or applicability, it will need to OTAR the Hash Path End via MT51 and ECDSA.

Regarding loss tolerance of messages and the security of 16-bit HMACs, we implement a main idea previously described by Neish (2020). The smaller 16-bit HMAC design of MT50 aids in general tolerance of message loss. Suppose, instead, each MT50 contained a single HMAC that authenticated the previous five messages as a group. If any of the five earlier messages were lost, the receiver would not verify any of the messages in this group. Therefore, to accommodate message loss, we specify that each HMAC from the set of five smaller HMACs individually authenticates each of the five previous messages. Because the 16-bit length of the HMACs is unusually small with respect to cryptographic authentication, we take special care to specify our spoofing detection procedures and ensure cryptographic independence of keys, as described in Section 3.3.

3.2 TESLA Efficiency

The number of authenticating pseudorandom data bits required to perform OTAR of a Hash Path does not increase with Hash Path length. While complete OTAR requires a daunting 2048 bits, as described in Table 5, the bits do not scale with Hash Path length because the Provider sends only a Hash Path End authenticated with ECDSA. If the Provider finds that the overhead required to perform OTAR of a Hash Path has become too burdensome on the schedule, the Provider can increase the Hash Path’s length and decrease the OTAR transmission frequency. Increasing the Hash Path length requires the Provider to compute a longer Hash Path for each OTAR and and for receivers to hash more in the event of cold start. However, this burden is negligible because commodity hardware can compute Hash Paths on the lengths specified in this work within seconds, as described in Section 2.5. In any case, MT51 can reassign Hash Points mid-way through a Hash Path to decrease this burden. For instance, while a Provider could generate week-long Hash Paths, it could assign Hash Path Ends each day or each hour to alleviate the burden of the initial hashing operation. Given the 128-bit Hash Point length, a Hash Path length on the order of decades is safe from attack (Neish, 2020). Therefore, the OTAR transmission frequency is primarily driven by the desired TFAF, as discussed in Section 4.4.

To meet a standard 128-bit security level for TESLA, we must use cryptographically-independent 128-bit long keys for each HMAC. It is generally desirable to minimize the number of bits required for TESLA Hash Path distribution. We achieve this by deriving all cryptographic keys from the same 128-bit Hash Path. Specifically, each iteration of Equation (2), from each combination of time, satellite, and frequency, is derived from the same 128-bit Hash Point distribution. Thus, we do not need to generate a separate Hash Path for each stream of authenticated information. Provided each of the keys derived is cryptographically independent, the outcome is cryptographically secure. Ensuring cryptographically-independent keys is achieved by the intermediate HMAC operation shown by Equation (2) as described in Section 3.3. This allows a single Hash Point to authenticate multiple messages and a single Hash Path for a set of SBAS satellites.

While the Providers could maintain separate Hash Paths for each satellite, using a single Hash Path may decrease the time required to receive the Authentication Stack by cold start receivers. For instance, WAAS uses three geostationary satellites. WAAS could use the same Hash Path for all of its satellites and broadcast the set of unique MT51 messages that make up the Authentication Stack out-of-phase, thereby decreasing the TFAF by 66.6%, while accommodating receivers that do not track each satellite. We can extend this argument for the L1 and L5 frequency bands by decreasing the TFAF by 83.3%. Our selection of a TFAF for a receiver tracking by a single geostationary SBAS satellite on a single frequency is discussed in Section 4.4.

3.2.1 ECDSA-derived Hash Path Salt

The security of each TESLA Hash Path hinges on the difficulties involved in computing any earlier preimage Hash Point before it is released by the Provider. Unsalted Hash Paths are susceptible to pre-computation attacks, also known as Rainbow Table Attacks (Boneh & Shoup, 2017). To perform these attacks, an attacker pre-computes a large number of Hash Paths and stores them in hopes that one of the pre-computed Hash Paths contains a currently secure mid Hash Path Hash Point. If this were to occur, the attacker then has saved Hash Points located earlier on the no-longer-secure Hash Path and can thus spoof SBAS-authenticated messages. To prevent this from occurring, we must introduce random variations (known as “salt”) to the Hash Function which will render pre-computation attacks unfeasible.

A well-designed salt scheme will have the following characteristics: (1) the salt scheme must be sufficiently strong to deter pre-computation attacks; (2) the scheme must accommodate spontaneous and episodic message loss (e.g., receiver interference or receiver offline cold start); and (3) he scheme must not impose a burden on the message scheduler. A 128-bit salt would suffice for the security requirements. Given the modular design of the proposed MT51, one could append a designation for the salt of a particular Hash Path to the metadata definitions shown in Table 3 This would require an additional message sent by OTAR to a Hash Path. This would be unlikely to pose a burden on the SBAS schedule. However, we propose an alternative that saves an MT51 message by basing the Hash Path salt on the level-2 signature protocol. We suggest that the Provider might compute a Hash Path Salt S^P for Equation (1) via Algorithm 3.

In this case, the Provider computes a cryptographically-secure nonce for every ECDSA signature. Using Algorithm 3, the salt derives a public quantity derived from a nonce. For ECDSA, this is the curve point C. The analogous number in EC-Schnorr signatures is usually called r. This C is cryptographically-secure and random because it is derived from the cryptographically-secure nonce generated at signing. Use of this entity as the Hash Path salt saves an MT51 message without compromising the signing key or the Hash Path.

While this scheme provides the advantage of one less message for OTAR, it impedes the scheme’s flexibility. Using a nonce more than once reveals will reveal the secret private key used to authenticate the data. This means that the Hash Path and its authentication signatures are immutable. The Provider cannot remove a Hash Point mid Hash Path to save receivers the computation of hashing down to the signed Hash Path End because the salt derived from it would then be different. Providers also cannot change any of the metadata (e.g., the expiration time). To reincorporate these two features, as mentioned above, the Provider could augment the MT51 metadata and distribute the salt as a separate MT51.

• Download figure
• Open in new tab
• Download powerpoint

ALGORITHM 3

Transmitting Salt S^P without additional message with ECDSA

3.3 TESLA Security

Previous work identified the appropriate security-level lengths under conservative adversary models (Neish, 2020). These findings assert that a TESLA Hash Point length of 115-bits and an HMAC length of 15-bits will be sufficient to deter a supercomputer-level attack over the time-between-authentication interval and assert a sufficiently low probability of success. In this work, we have rounded up these numbers to the nearest base-2 number, at 128 and 16, respectively. Increasing these lengths adds additional security-level protection. The primary reason for 128 Hash Point lengths is that, as specified, MT51 can accommodate 128 bits. Section 4 discusses why 128 bits was selected to aid in the scheme’s maintenance. The selection of 16-bit HMAC lengths follows our general strategy of 2-bit lengths and aids in the flexibility of the scheme, as discussed in Section 4.1.

Until the Hash Point is released, the HMACs are indistinguishable from random bits. Given the security of the salted Hash Path, the probability that an adversary could generate a preimage Hash Point is 2⁻¹²⁸. This probability is sufficiently low so that it should not be expected to occur ever even with the support of vast computational resources. As described in Section 3.2, given the desire to use the 128-bit Hash Path efficiently at a particular Hash Point time interval, we desire to authenticate many different pieces of information simultaneously (e.g., five messages per Hash Point, Section 4.2). Thus, we have taken a conservative approach in our construction to mitigate any anticipated vulnerabilities when implementing potential feature extensions in this SBAS TESLA design or any other GNSS-TESLA constellation concepts (Anderson et al., 2022; O’Hanlon et al., 2022). To discourage implementation errors when applying these design concepts, we ensure that each piece of information authenticated with an HMAC has its own cryptographically-independent HMAC key as described in Equation (2).

Equation (2) also takes the secure Hash Point and uses HMAC to derive cryptographically-independent keys by applying HMAC with the Hash Point as the HMAC key field together with unique contextual information in the HMAC message field. In the specific case of Equation (2), the HMAC message field includes the message time, the satellite PRN code, and the frequency. The time parameter allows a single Hash Point to authenticate the five messages individually because each message is sent at a different time. The PRN code allows all of the satellites to share the same Hash Path because each satellite has its own unique PRN code; the same is the case with the frequency. Our time, PRN code, and frequency band choices are arbitrary, except that our selection guarantees uniqueness; each message from each satellite and from each band is provided with a cryptographically-independent key that can be used to derive the HMAC. Any unique identifying information, such as a counter, would suffice to ensure that the output of Equation (2) is cryptographically independent.

There are several ways to construct a secure scheme without the intermediate HMAC operation of Equation (2), for example, prepending the context to the signed data. Careful consideration must be take to avoid implementation errors that might introduce vulnerabilities including, but not limited to, (1) allowing an adversary to spoof a message from one satellite so that it would appear to be coming from another satellite (or another frequency); (2) allowing an adversary to spoof a message from another time (given that we sign five messages at a time using this scheme); (3) allowing an adversary to prefix the context of one message to another to engage in a swap and provide context for confusion attacks (e.g., especially when the signed data are not of fixed length); (4) allowing an adversary to engage in related-key attacks (Peyrin et al., 2012); or (5) deriving additional data using this key (e.g., in signal watermarking concepts as described in Anderson et al. (2022); O’Hanlon et al. (2022)) performed in a reversible manner, allowing an adversary to have access to an unreleased TESLA Hash Point. Our construction with Equation (2) separates context and content to mitigate these issues and provides a clear way to extend authentication by generating additional and irreversible cryptographically-independent information (Section 4.2 (Anderson et al., 2022; O’Hanlon et al., 2022)) in an implementation-error-proof manner.

Because the Hash Point is not known to an adversary when the HMACs are released, the probability that an adversary can forge a 16-bit HMAC is 2⁻¹⁶. To provide adequate protection against forgery, we must specify a conservative approach for forgery detection. For example, if any of the smaller HMACs fails the verification algorithm, the receiver must discard all non-MT51 information from that particular SBAS satellite and restart collecting new SBAS data. While 2⁻¹⁶ is a relatively high probability, this is sufficient for the SBAS context because (1) an adversary does not yet have access to the delay-released key nor an HMAC verification oracle (from the cryptography security context), and (2) once forgery has been detected, all prior SBAS data will be immediately discarded. While the details will be presented in a forthcoming work, the receiver logic will be set up so that a single message forgery event will not result in an integrity failure. this will decrease the likelihood of harmful forgery to 2⁻³² < 10⁻⁹. The likelihood that an adversary could forge so many messages successfully is small enought to meet the security level required by the stakeholders.

Our selection of SHA-256 for the Hash Path and HMAC generation is not necessarily required. We select SHA-256 because it is standard and widely-used. However, the Providers may wish to consider other standardized hashing functions such as SHA-384 or those from SHA3 group to address other concerns, for example, future-proofing and hardware concerns. We selected HMAC-SHA-256, which includes SHA-256 as its primitive, to simplify the protocol. The widespread and straightforward use of SHA-256 aids in the continued security of the proposed scheme. If the SHA-256 security is broken, it will be widely-publicized and quickly exchanged for another hash function. Providers would need to replace only a single function in their implementation to continue operation, much like the recent SHA-1 deprecation.

4.1 MT51 Metadata Design

We specified the inclusion of a Germane and Authenticating Key hash within the authenticating pseudorandom data metadata. Since the payload is pseudorandom, metadata must exist so that the receiver can associate the unique MT51 payloads. Any identifying feature would suffice, for example, the ordered key number which rolls over every 2¹⁶ = 65536 keys. However, the use of hash on the entire key provides additional features. The key schedule need not be rigid, linear, or sequential. The Provider and the CA can maintain several redundant level-2 and level-1 keys, respectively. Multiple keys, potentially managed in isolation by the Provider and the CA, might provide redundant security. The Provider would need to check to be certain that the two unexpired keys do not share the same 16-bit identifying hash; however, this would be a rare occurrence and the Provider would simply need to draw another key at random in that event.

SBAS Providers could broadcast each other’s Hash Path Ends and key maintenance features to promote service continuity. Hence, we included the SBAS Service Provider ID in the metadata. SBAS Providers would not need to have access to one another’s secret data; they would only need to serve as repeaters. Whereas Section 4.4 discusses higher MT51-frequency to support the local SBAS authentication from cold receiver start, this feature would be low frequency and serve to support the local Provider schedule. Having Providers broadcasting each other keys at low frequency would contribute to TFAF when transferring to a new SBAS Provider. For example, we consider the case of two adjacent SBAS systems, WAAS and EGNOS, and an aircraft traversing from Europe to North America. It will take several hours for an aircraft to make this journey. If EGNOS broadcasts the WAAS keys once an hour, any westward-bound aircraft will receive the WAAS keys it needs to operate before reaching North America. This decreases the WAAS TFAF to zero. At a minimum, SBAS Providers could broadcast keys from adjacent SBAS Providers. Without this feature, when an aircraft enters a new SBAS service volume the first time in a given week (or 10 or 100 weeks), it must act as a cold-start receiver for as long as required to collect the Authentication Stack, as specified in Section 4.4.

Spare bits in the authenticating pseudorandom metadata could accommodate other features. These include scheme hyperparameters, such as the choice of a hash function or key or HMAC length. MT51 messages could authenticate specific messages immediately with ECDSA, including those identified by 16-bit hashes. If keys are ever compromised, MT51 could also disseminate key revocations. A revocation MT51 would include eight 16-bit hashes of the affected keys and would only need to be broadcast until the keys have been removed using standard procedure. Because each MT51 broadcast is accompanied by a germane expiration time, the Provider can arbitrarily shorten the applicability of a particular key by rebroadcasting the MT51 with a different expiration time, under the assumption that receivers actually receive and record that updated broadcast and that the Hash Path salt is not disrupted, as described in Section 3.2.1. Receivers would need to remember key expiration time changes and key revocations. Receivers that did not receive these updates would remain vulnerable. If the Provider can remove data, the metadata must include a parameter that identifies a given specific authentication. This is because without the germane key hash, authenticating key hash, segment number, and authentication instance number, the individual segments of pseudorandom data will not be associated. MT51 can manage other authentication schemes, including the program adopted by GNSS as described in Section 4.2. A GNSS authentication, especially one built on TESLA, would save bandwidth by deferring the its maintenance to SBAS.

There are many features that can be accommodated by the scheme’s modularity; however, if SBAS stakeholders prefer not to use these features, then the spare meta bits could also be used to aid in maintaining resistance to message loss. Providers could add redundant HMACS to the MT51 message and thus authenticate messages redundantly to alleviate MT50 message loss. Moreover, the delivery of 128-bits of authenticating pseudorandom data could be augmented via the use of fountain codes (Fernandez-Hernandez et al., 2017). The use of fountain codes may increase the reliability of delivering MT51 messages and decrease the number of transmitted messages required for an authenticated first fix. The selection of 128-bits supports the scheme’s efficiency because all data points are integrally divisible by 128. Special care must be taken to ensure that using fountain codes in the spare bits to augment those 128-bits would not change this integral-divisible property and thus will maintain efficiency.

A final MT51 design must accommodate all the features relevant to SBAS stakeholders while maintaining the KPIs. The most relevant KPI for this discussion is TFAF, because the use of more features will require more metadata. This will increase the number of unique MT51s required for OTAR. We proposed MT51 because the minimum MT51 OTAR Payload Segment size was 128-bits. The conveniences associated with this choice are discussed in other sections. This choice permitted us to specify maximum metadata. However, as defined in Table 3, there could be redundant identifying information given certain assumptions about key management. Furthermore, some of the bits of metadata are never used (e.g., delivery of a 128-bit salt will never require more than one page). Because this work reflects an academic context, we are concerned with the breadth of features possible, given that our 128-bit design already meets the KPIs. Therefore, we acknowledge that there are other ways of constructing MT51 metadata that will avoid definition redundancy and spare bits. As SBAS Stakeholders discuss their desires (e.g., for the metadata to become more or less crowded, and noting that even MT51 has some spare bits. Therefore, we offer several suggestions on how to consider balancing the design while maintaining scheme modularity, simplicity, and flexibility.

For example, a plausible MT51 design could include a 192-bit OTAR payload or a larger payload. This can be achieved via any of the following: (1) the SBAS Provider could identify keys by their expiration time, thus removing the need for the Germane and Authenticating Key Hashes in the metadata; however, this would eliminate the possibility of parallel and redundant key management; (2) any metadata regarding the keys could be placed on its own page, provided the authenticating signatures were derived from that data to ensure its security; and (3) the SBAS Provider and receiver could agree on a defined ordering, for example, that depicted in Table 4, for an aggregate OTAR payload. We note that the 128-bit MT51 design does not require the receiver to presume anything about the OTAR schedule or use. In our simulation, the receiver implementation proceeds without knowledge of the 100, 10, and 1 week cadence, nor any insight into whether the keys are managed rigidly or linearly.

A 192-bit OTAR Payload Segment length almost maintains the integer-divisibility. An Authentication Stack from Table 5 using AES-256 to encrypt level-1 keys and having a separate TESLA salt MT51 would be integer-divisible by 192 with 2304 total bits and 12 192-bit MT51s. Alternatively, as features are removed, rather than shifting bit allocations from the metadata to the OTAR Payload Segment, SBAS Providers could instead arbitrarily replace metadata bits with fountain codes. This suggestion would maintain the integer-divisibility of MT51 on the authenticating pseudorandom data, thereby ensuring there is no wasted zero-padding on the delivered data, and will also add the loss-tolerant properties of MT51.

We implore the SBAS Stakeholders to have a future-proofing mindset that includes consideration of attributes that may be needed decades in the future. For example, cryptographic primitives will break and will need to be replaced. Likewise, quantum-computer resistant algorithms may be needed. The best way to maintain a future-proof mindset is to make MT51 agnostic to the data it is delivering and capable of expansion to any future pseudorandom data delivery requirements.

At a 128-bit OTAR Payload Segment, the required delivery of 16 unique MT51 already meets the KPIs. However, increasing the OTAR Payload Segment would decrease the number of unique MT51s. This would decrease the burden on the SBAS Schedule, decrease TFAF, and have a less of an effect on continuity and availability, among other considerations. Therefore, we expect the results shown in Section 6 to be repeatable in designs that feature a larger than 128-bit OTAR Payload Segment.

4.2 Core Constellation Ephemerides Authentication

Another feature that is accessible because of this scheme’s modularity is authentication of navigation messages from a GNSS application. GNSS messages have limited bandwidth and must maintain backward compatibility. MT51 provides a natural pathway that might be used to authenticate GNSS data with the 128-bit payload and spare meta-data bits. Table 3 provides the required metadata designations, including (1) the germane core constellation system; (2) the type of authenticating pseudorandom data; and (3) the authenticating pseudorandom data segment number. However, the payload will need to be modified to accommodate realistic operations.

Given the Satellite-Receiver-Earth geometry, we suggest that the 128-bit payload might be split into eight 16-bit payloads, as shown in Table 6. Each 16-bit HMAC within the MT51 payload corresponds to a specific satellite’s broadcast ephemerides. The MT51 metadata informs the receiver which satellites correspond to the payload HMACs. By splitting the payload into smaller HMACs, the receiver need not have access to the entire set of ephemerides to authenticate data from individual satellites.

4

5

Authenticating core constellation ephemerides exploits a main feature of TESLA which is its bandwidth efficiency. Core constellation ephemerides can derive from the same Hash Path as those distributed by MT50, meaning it would require minimal additional SBAS bandwidth. Equations (4) and (5) provide formulae that can be used to generate the necessary HMACs, where is the HMAC key for a particular ephemeris’ HMAC, is the HMAC broadcast and used for authentication. , t_j; PRN, Frequency, and SVN share the same definitions as those presented in Equation (1) and (2). Other information should be incorporated into these definitions (e.g., whether the signature is for the current or previous ephemeris). These details will be considered in our future work.

There are three important security details that remain to be addressed. First, similar to MT50, if any of one of the HMACs returns unauthenticated, the entire set of ephemerides data must be discarded. Second, the HMACs derive from a cryptographically-independent keys derived from a TESLA Hash Point, similar to that described in Section 3.3. Equations (4) and (5) use the sending time t_j, the SBAS PRN and frequency, and the core constellation satellite vehicle number. Third, the ephemeris HMACs must be sent before the release of the corresponding Hash Point according to the loose-time synchronized schedule (i.e., at least six seconds in advance).

SBAS could authenticate the broadcast ephemerides of every satellite globally and the receiver can draw from the entire set of HMACs, including the few within the view of the receiver. The metadata segment number informs the receiver from which set of eight satellites the HMACs are derive. For GPS, this would mean four MT51s. However, MT1 and MT31 already provide an issues-of-data mask of the 92-most relevant satellites currently under correction for a particular SBAS. Therefore, we propose that the order of the eight HMACs might correspond to the order prescribed in the issues of data already provided to the receiver. The issue of data index, either the IODP or IODM, must be placed in the unused sections of the metadata, and the metadata segment number field would determine the relevant eight HMACs, in order, among the set of 92. Since the issue of data index requires only two bits, SBAS could use the unused Germane Key Hash, Germane Key Expiration, and Authenticating Key Hash to send 12 HMACs per MT51. Alternatively, one could define a new message type that delivers 13 HMACs, the issue of data index, and the segment number.

4.3 MT50 Redundant Authentication

MT51s are self-authenticating messages resulting from the use of ECDSA. Upon receipt of the entire Authentication Stack, the receiver can assert authenticity to the level-1 key maintained by the CA. However, the MT51 messages are among the SBAS messages that are authenticated by TESLA and MT50. If the receiver has an ECDSA-verified Authentication Stack that can authenticate the bulk of SBAS messages via MT50, the receiver can use TESLA to verify the next Authentication Stack when it is delivered by MT51. In this manner, a receiver can assert the authenticity of the next Hash Path End without awaiting the associated authenticating pseudorandom data since an HMAC in the following MT50 will assert authenticity down to the current Hash Path End through the current level-1 key. In Section 4.4, we suggest that the next Authentication Stack might be rebroadcasted each hour. The ECDSA- and TESLA-based authentication of the next Authentication Stack will then be redundant to a receiver that has undergone an authenticated fix. Therefore, an argument can be made that broadcasting the hour-long frequency of the next Authentication Stack does not add to the scheme. Alternatively, MT50s could not authenticate MT51s will instead authenticate messages redundantly. These considerations will ultimately depend on the manufacturers’ implementation preferences and whether this logic should be incorporated into the process. To avoid implementation errors that might serve to exploit the authentication scheme, we suggest that, given stakeholder agnosticism, the simplest version might be selected. We believe that the scheme delineated above, where MT51 data is redundantly authenticated with MT50, is the simpler scheme overall.

4.4 MT51 Schedule Frequency

As discussed earlier, we propose that the cryptoperiod of the level-1, level-2, and TESLA Hash Paths might be 100, 10, and 1 week, respectively. Our selections are somewhat arbitrary and were chosen in an attempt to balance the bandwidth required to rotate key and Hash Path instances with security considerations such as the resources required for a brute-force attack and the likelihood that a key becomes compromised (e.g., leaked). Feasible scheme designs might permit level-1 cryptoperiods to be years longer, level-2 cryptoperiods to be as short as one month or one week, and Hash Paths to rotate every hour or at least once a day. While we will leave this consideration for future work, any choice made must meet minimum security requirements that are associated with the required computational time needed for exhaustive guessing of the keys. Upon cold receiver startup, we would like the TFAF be reasonably short. Therefore, the Authentication Stack must be sent out periodically. As shown in Table 5, a complete Authentication Stack requires 16 MT51s. We propose that the Provider might broadcast the current Authentication Stack every five minutes. In this way, the cold-start receiver achieves the first authenticated fix within the first five minutes, assuming no message loss. This will require a message to be transmitted from the 16 unique MT51s at a rate of 1 out of every 18 messages. With multiple geostationary satellites and frequencies, the satellites can broadcast the unique MT51s out of phase to decrease the TFAF as discussed in Section 3.2.

Furthermore, the next keys, applicable immediately upon expiration of the current keys, must be sent well before they are needed to facilitate a seamless transition as the current keys expire. To protect the security of a specific new key, it would be prudent to send the new key just before it will be put into use. For instance, we suggest that the Provider might send the next 100-week level-1 key repeatedly beginning five weeks before its actual use. The next 10-week level-2 and 1-week TESLA Hash Path End might be sent one week before their actual use. To demonstrate its minimal impact on the MT51 SBAS bandwidth, if a Provider sent the next Authentication Stack once every hour, together with the current Authentication Stack once every five minutes, the Provider would need to send a message from the set of 32 unique MT51s at a rate of 1 out of every 17 messages, rounded up. This assumes that each OTAR Payload Segment of the Authentication Stack is broadcast at the same frequency as a baseline. Since some sections of the Authentication Stack change less frequently, further optimization could be performed to balance the TFAF with the likelihood that receivers are off for longer than for one week, 10 weeks, or 100 weeks. For instance, the slowly varying OTAR Payload Segments could be broadcast once every 15 minutes with the weekly-varying OTAR Payload Segments broadcast every two minutes.

We note that Providers and receivers may not need to adhere to a set schedule for the key periods or the Hash Paths. As discussed above, the MT51 metadata and modularity afford flexibility with respect to the expiration of particular keys and the agreed-upon schedule for their expiration. Moreover, switching Hash Paths without warning does not add computational complexity to receiver verification. Each Hash Point is a hash, and hashes have constant-time look-up computational complexity, as presented in Algorithm 2. This means that if the Provider were to switch Hash Paths without warning, the receiver would need only one additional computation to check that the new Hash Point is the preimage to another ECDSA-verified Hash Path End. This means that SBAS could incorporate unscheduled or stochastic Hash Path switches, provided the appropriate MT51s are sent in advance, noting that the MT51s specify only Hash Path End expiration times and not their actual use time. If stakeholders elect not to have a rigid Hash Path schedule, a maximum Hash Path length upper bound must be specified so that receivers do not get stuck in an infinite loop as they attempt to hash down to an ECDSA-authenticated Hash Path End.

The selection of the level-1 cryptoperiod, level-2 cryptoperiod, and Hash Path length pose trade-offs among various SBAS stakeholders. With a very long Hash Path, aircraft are less likely to find themselves without the current Hash Path End via MT51 since the Hash Path End expires less frequently. Upon startup after a shutdown less than the Hash Path End cryptoperiod, receivers need not await delivery of an updated Authentication Stack via MT51, however, they must accommodate a more intense startup hashing operation to hash the current MT50 Hash Point to the authenticated Hash Path End. With a very short Hash Path (e.g., a Hash Path cryptoperiod of one day), receivers are more likely to be missing part of the Authentication Stack after a shutdown because the missing parts expired while the receiver was shut down. However, a shorter Hash Path will mean that less hash processing will be required at startup. These considerations become especially germane for aircraft that periodically traverse different SBAS service volumes. For instance, consider aircraft that regularly travel a transatlantic route. When outside a specific service volume, their devices will behave as shutdown receivers. Our selection described in Section 4.4 was to accommodate a short time to first fix. With a longer Hash Path, as flights travel across service volumes, the TFAF will more likely be bounded by receiver computational hash capability instead of the MT51 delivery schedule.