We trace back through time to witness the progress in anti-spoofing solutions and describe how we arrived at the designs being implemented today; principally GPS’ CHIMERA, Galileo’s OSNMA, and ICAO’s SBAS data scheme.
The meteoric rise from the first use of GPS in the 1990s to billions of users of multiple constellations 30 years later can be understood from several key design choices made by GPS early on. GNSS is a one-to-many broadcast service, with signal power is below the noise floor and clever signal processing techniques to make use of them. The civilian signals have publicly available Interface Specifications (ISs) or Interface Control Documents (ICDs) that allow anyone to develop and market GNSS receivers. These aspects of GNSS that encouraged mass adoption come with consequences, however.
With the means to receive and demodulate GNSS signals made publicly available, enough information is present that allows individuals to generate GNSS signals of their own. Until recently, this has proved to be a benign and even beneficial utility. From this, a market for high precision GNSS signal simulators was born to provide receiver manufacturers and end users the means to test their systems under a wide variety of conditions before bringing their products to market. However, with recent advancements in radio frequency microelectronics, generating GNSS signals has become more accessible at a lower cost over time. The threat of broadcasting these fake signals has become a great cause for concern as the technology required to spoof GNSS signals has outpaced the GNSS community’s efforts to detect and mitigate these threats.
In response to this emerging hazard, several spoofing mitigation and detection strategies have been explored for application at the end user as well as by the service provider. For the end user, these techniques include monitoring internal receiver metrics, the adoption of independent positioning and timing resources, and hardware augmentations to detect true GNSS signal direction-of-arrival. GNSS service providers have also come to the table to help secure their publicly broadcast signals. This article focuses on the effort to provide authentication of GNSS ranging signals and data channels by both the core GNSS constellations as well as the augmentation systems that support them.
Cryptographic authentication uses signatures in the broadcast signal to provide confidence to end users on where the signals were generated. These signatures are created using a secret key that is privately held by the service provider and the signatures are verified using the secret key’s corresponding public key that is available to all end users. The field of cryptographic authentication has been developed with the capabilities of modern internet data rates in mind. Because GNSS services are broadcast systems and the data rates are much lower than nominal internet protocols, special care should be taken when designing and tailoring existing authentication schemes for use in GNSS.
In addition, interoperability between different systems has been a goal for different core constellations and SBAS systems. SBAS in particular has taken great strides to standardize the authentication methods being considered for implementation. These authentication systems, once implemented, are envisioned to last for decades and so incorporating authentication schemes that are resistant to future computing vulnerabilities, such as quantum computing, is also being considered today.
The Original Document
The 2001 Volpe report is widely recognized as the original document motivating the past two decades of work in anti-spoofing and anti-jamming. While the report focused on GPS, there was also mention of vulnerabilities in WAAS, LAAS and other GPS correction services. In this report, they refer to an internal memorandum written by Edwin Key from MITRE that identifies several spoofing mitigation strategies including IMU cross checks, time-of-arrival discrimination, and angle-of-arrival discrimination. While the report concluded that “the best anti-spoofing technique is probably the use of a multiple-element antenna to measure the angle-of-arrival of all received signals,” the report also explicitly mentions the use of backwards compatible cryptographic authentication on civilian signals.
In 2003, Logan Scott published a paper on incorporating authentication in civilian GPS signals. Scott recognized the democratization of software and hardware that would soon enable the masses to produce their own GPS signals. The solutions offered in his paper were to add cryptographic authentication to the data and signal levels of the civil GPS signals to protect them from spoofing attacks. He defined 3 levels of protection when it came to GNSS authentication:
• Data Message Authentication
• Public Spreading Code Authentication
• Private Spreading Code Authentication
Each of these methods offer successively more secure, yet more complex methods of authenticating GNSS signals. Data message authentication consists of putting digital signatures in the data stream of the GNSS and SBAS signals. While this protects users from data forgery attacks, it provides little protections on the ranging signals themselves.
The second level, public spreading code authentication, consists of ”puncturing” the chipping code using cryptographic means. Receivers would store digital samples of the signal where these punctures would be present and then verify the existence of these punctures with data later sent by the GNSS satellites. The drawback to data authentication and public spreading code authentication is that they both endure an authentication delay. In other words, the user must wait for a period of time before they can despread the stored cryptographic precorrelation samples or evaluate the digital signature sent by the GNSS satellite.
The third level, private spreading code authentication, uses a symmetric key scheme where users have access to the same private key as the GNSS provider. Similar to public spreading code authentication, the chipping code would be punctured, but users in this case would not have to wait for data to be broadcast from the GNSS satellites to check the authenticity of the spreading code since they already have the keys available to them.
This method enables users to instantaneously verify that the received signals came from the correct source, but since all users would have access to the private keys, special protections would need to be in place so that users themselves would never gain access to these keys. This could be done with the inclusion of tamper-resistant hardware, but at a price. This hardware can be relatively expensive and cumbersome for some applications. Proper management of secret keys to be shared among users also provides a major impediment to private spreading code authentication.
These different GNSS authentication levels are not mutually exclusive. Scott outlined how they could be simultaneously implemented on the same signal channels. An important precedent was set by his work in that all GNSS authentication designs offer backwards compatibility for users who do not wish to use the authentication data incorporated in the GNSS channels. For the most part, civil authentication designs put forward since this work have operated with backwards compatibility in mind with the exception of the Galileo Commercial Service (CS), which employs a fully encrypted spreading code service that only authorized users have access to, similar to the GPS military P(Y) or M code. These three different levels of protection still concisely classify the different authentication proposals that have come forward since Scott’s publication. We use them to contextualize GNSS authentication proposals for the remainder of this article.
European Voices
In 2004 two European publications outlined potential designs for GNSS authentication. Kuhn presented a data authentication design that added a secret spreading sequence below the thermal noise. Similar to Scott’s proposal, receivers would buffer the bandwidth of the hidden markers while they are broadcast to be verified later. What was different with this implementation, however, was that these markers would be discovered by using a pseudorandom function where the seed for that function would be sent at a later time. It was recognized by both Scott and Kuhn that receivers would need to have loose-time synchronization. After the seed or key is released, anyone can generate the spreading code sequence. Receivers needed to be sure of their timing with respect to the true GNSS time so that they would not accept signals that arrived after the seed had been released.
Pozzobon et al. that same year published a paper that outlined the potential markets for a Galileo authentication service. It was already known that Galileo was considering pursuing encrypted services, but through this publication it became clear that Galileo could also be pursuing data authentication and potentially public spreading code authentication for the public signals. Namely, it was announced that the Open Service (OS) could provide navigation message authentication (NMA, Figure 1), the Safety of Life Service (SOL) could provide NMA, and the CS and public regulated service (PRS) could provide access restriction through spreading code and data encryption.
While there are many publications in the GPS and SBAS literature on authentication, Galileo committed early on to implementing authenticated and encrypted navigation channels for the general public. Over the years, several European groups made focused efforts on developing authentication for GNSS and, more specifically, Galileo signals. In their 2005 paper, Wullems et al. suggested two candidate authentication methods for NMA: Timed Efficient Stream Loss-tolerant Authentication (TESLA) and Elliptic Curve Digital Signature Algorithm (ECDSA). These two algorithms would continue to be the main candidates looked at for NMA in the next decade and a half. For the sake of context we’ll take a brief look at the strengths and weaknesses of these algorithms as applied to GNSS authentication.
There are two forms of cryptographic algorithms in general: symmetric and asymmetric. As the name implies, symmetric cryptography involves methods where the sender and receiver both hold the same secret information. We can think of this secret information as a shared secret key. In contrast, asymmetric cryptography involves different information held by the two parties, typically a combination of a public key and a private key. Authentication is the process of verifying the validity of the data being sent as well as the origin of where that data was generated.
As opposed to encryption, authentication does not obfuscate the data. It merely appends what is called a “signature” to the data so that the data can be later verified. In the context of GNSS, a simple vision of how GNSS would be authenticated would be through the use of widely disseminated public keys while the private keys were kept by the service provider.
TESLA and ECDSA
The two algorithms presented by Wullems provide different ways of signing GNSS data. ECDSA is a classic example of an asymmetric authentication method. In ECDSA, the service providers produce a secret key that only they know as well as a corresponding public key. The public key part of that pair is then securely distributed by the service provider. Messages sent over the air are signed using the private key and users apply the locally stored public key to verify the data as it rolls in. Some drawbacks to this algorithm for use in GNSS are that the signatures (448 bits or greater) are large relative to GNSS data rates and the computation time at the receiver to verify a signature can be an intensive task for embedded systems. ECDSA does have the advantage of being standardized as opposed to TESLA.
TESLA reduces the key size by providing asymmetry of information through time with the delayed release of symmetric keys (Figure 2). The TESLA algorithm produces a signature known as a Message Authentication Code (MAC). This signature may be verified by the same key that signed it. Instead of storing the keys at the receiver, the keys are released to the user after the MACs have been sent. The trust for the receiver is that when it received the MAC, it believes that no one except for the service provider had access to the key that created that MAC when that MAC was created.
Two issues arise from this implementation. First is that a receiver must have loose-time synchronization with the GNSS service provider to ensure that the MAC it received could only have been created by that service provider. This poses a potential problem in implementation since GNSS is typically the trusted source of timing for most applications. The second issue is that if the keys are being sent over the same data channel as the signatures, how are the keys going to be verified? The first issue is a problem that may be solved with an independent time source, but luckily the second issue is resolved by the design of the TESLA protocol.
In order to verify the keys, the keys are linked together in a “keychain.” This keychain forms a cryptographic link between the keys in the form of a one-way function. A one-way function is a function that has no easy method of inversion. The keychain is created by doing a recursive set of these one-way functions and the keys themselves are released in the order opposite to that in which they were originally created. In this way, when a receiver obtains a key to verify a MAC, the first step is to perform the one-way function on that key to see if they derive the previous key. If they derive the correct key and they trust this previous key, then the key has been verified and they can use the new key to verify the most recently received MAC against the data that it signed. The last key generated for the keychain (and the first to be released to the public) needs to be verified by an asymmetric scheme like ECDSA.
The advantage of using a scheme like TESLA is that MAC and key combinations can be much smaller than an ECDSA signature (on the order of 110 bits or more). They also provide a computational advantage in that the generation of a MAC is generally a much easier operation than executing elliptic curve cryptographic functions. By some experimental results, an ECDSA signature can take anywhere from 8 to 15 times longer for a CPU to verify than a TESLA MAC. That being said, if the TESLA key verification is not handled properly by the protocol, this verification process can be highly time-consuming.
Key Performance Indicators
Applying either of the above authentication algorithms to GNSS is much more than just signing GNSS data. GNSS signals have a very limited number of available bits that they can broadcast and how these designs are implemented has tradeoffs at every decision. Early on it was recognized that parameterizing the impact some of the authentication solutions put forward would help designers understand the efficacy of their solutions. Metrics to assess behavior later became known as Key Performance Indicators (KPIs) and would be used to help characterize the impact of the different authentication design concepts under consideration. These KPIs have since been built upon and used by the GNSS community to communicate the effectiveness of their GNSS authentication designs.
An example KPI metric is the Time Between Authentications (TBA). How often should a signature be sent? Shorter intervals will give smaller windows for potential spoofers to try and inject bad data, but they also come at a cost in greater required bandwidth. TBA simply communicates how often a receiver can expect to be able to authenticate data.
Another metric is the Authentication Error Rate (AER). What if for some reason the data that is received is incomplete? This may be due to interference, scintillation, obstruction, or other causes. These events would cause a receiver not to be able to authenticate data. The AER helps determine the expected rate at which receivers would not be able to authenticate the full set of required GNSS data.
There are other KPIs that focus more towards cryptographic strength of the algorithms, their key sizes, and how long the public keys have been exposed publicly. Wullems also offered some suggestions as to how to improve the performance with regard to these KPIs such as cross-authentication between GNSS satellites.
SCER Factor
The algorithms that are being considered are known to protect data, but the question remains as to whether data level authentication can also protect the ranging component of the GNSS signals. An attack was posited in 2009 by Pando and refined by Todd Humphreys in 2013, showing how an attacker could attempt to use the same incoming cryptographically secure GNSS data bits while broadcasting false ranging information. Humphreys termed this a Security Code Estimation and Replay (SCER) attack. Its basic concept is that if the spoofer listens to the true GNSS signals in real time, the attacker can attempt to estimate each data bit before it is completely received. If the receiver is successful in estimating each data bit, the receiver can then simply overlay the true GNSS data on their own synthetically created PRN sequence, allowing a spoofer to generate spoofing attacks in the range domain.
Humphreys delivered a sobering message: data-level authentication can protect certain information from some attacks, but it is not a panacea against all forms of spoofing.
The Radionavigation Laboratory under Humphreys’ direction gave strong contributions to the field of GNSS authentication in the early 2010s. These contributions came in the form of authentication designs geared towards the GPS CNAV signal to be offered on L1C. In 2012, Wesson et al. presented a high-level architecture for how a receiver should successfully implement authentication and try to protect itself from these types of SCER attacks. Some of these receiver functions included processes to do timing consistency checks and incorporated SCER detection methods. Both ECDSA and TESLA were approached as possible authentication designs for GPS L1C.
In 2014, Kerns et al. expanded this work and offered an ECDSA/TESLA hybrid approach. This would allow for different classes of user to authenticate the data. The ECDSA and TESLA signatures would be in the same L1C data stream so that users with high confidence in their time synchronization could authenticate the data more often, while those that were less certain could use the ECDSA signatures. This work also gave more detail into how the NMA messages would be incorporated into the CNAV channel and performed a series of analyses that evaluated the efficacy of the designs.
Augmentation Systems
Work was done early on looking at authentication for GNSS augmentation systems as well. In 2010, the Stanford GPS Laboratory looked into the feasibility of incorporating digital signatures on SBAS and GBAS. Naturally the TESLA and ECDSA algorithms played a prominent role in this analysis.
In 2016, Dalla Chiara et al. looked more closely at the feasibility of implementing authentication on SBAS. One concept introduced in this work was that of authenticating SBAS data using the currently unused quadrature channels on the L1 and L5 frequencies. If these channels could be used, new SBAS bandwidth would be created exclusively for authentication, and the pre-existing data on the in-phase channel could be authenticated more often. Dalla Chiara et al. discussed solutions for both data level authentication and public signal level authentication and performed a preliminary analysis using KPIs.
The aggregate body of work discussed here constitutes merely a glance at what has been done up until this point in GNSS authentication. There are 60+ referenced literature sources that address GNSS authentication directly and scores more that look at GNSS spoofing. We set out here to offer a window into where we are today with authentication. The work completed over the past two decades has contributed to authentication development for several upcoming services. Notably, Galileo is working towards an Open Service Navigation Message Authentication service, the Air Force Research Laboratory (AFRL) will test GNSS authentication on the upcoming NTS-3 mission, and members of ICAO are working to standardize an SBAS data authentication solution among all SBAS service providers.
Galileo
In 2016, Galileo released a first signal-in-space specification for its Open Service Navigation Message Authentication (OSNMA) design. This offers a bit-level specification of the service and how the OSNMA message structure is incorporated into the Galileo I/NAV message sequence. OSNMA currently only authenticates navigation data. The protocol used is a TESLA-based sequence with a full specification of how the MACs and keychain are generated and verified. The program is likely to be the first publicly available GNSS authentication system with signal in space testing in 2020 and FOC in the near future.
CHIMERA
AFRL is working on an authentication design known as Chips-Message Robust Authentication (CHIMERA) that incorporates both public signal authentication along with data level authentication (Figure 3). This design finds its roots all the way back in Logan Scott’s original 2003 paper and offers users two authentication variants: slow and fast. For users that have access to third party signals over the internet, authentication information will be passed over the network allowing users to authenticate data at a faster rate. Data and signal authentication will still be available to all other users, over the air through the GPS signals, although the time to authenticate will be larger. In 2019, the AFRL released a signal specification outlining how the cryptographic markers are distributed within the spreading code and how the navigation data signatures are created. The NTS-3 satellite is scheduled to be launched in 2022. The Air Force will then have the ability to test this combined signal and data authentication design.
SBAS Providers
Finally, members of the ICAO Navigation Systems Panel are working together to standardize a solution across all SBAS providers. Implementing authentication on SBAS presents a unique challenge that can leverage the experience gained from the work on core constellations but must also encompass other special considerations. SBAS is primarily a data service, and although some service providers produce a ranging signal, SCER attacks are not as threatening, since a single SBAS ranging signal that is in error can be caught using other integrity methods such as RAIM. TESLA and ECDSA are also being looked at closely for use in SBAS.
While these systems are being put to test and are coming into service, other programs such as BDS and QZSS are considering data and signal level authentication as well. The work referenced in this article captures only snapshots of the progress the field has undergone in the last 20 years. Many other important contributions have been made by groups all over the world that we would like to recognize, but alas, only so much can be shared in one article.
Clearly, while a great amount of work over the past twenty years has led us to this point, much remains to be done.
