Log in

Print Email

Home > GNSS System
Related topics: Expert Advice & Leadership Talks, Insight & Commentary, Opinions

GNSS System

Expert Advice - Location Assurance

July 1, 2007 By: Logan Scott GPS World

Location Assurance Commentary, by Thomas A. Stansell

LOGAN SCOTT is a consultant specializing in RF signal processing and waveform design for communications, navigation, radar, and emitter location. He has more than 29 years of military and civil GPS systems engineering experience. As a senior member of the technical staff at Texas Instruments, he pioneered approaches for building high-performance, jamming-resistant digital receivers. He is currently active in location-based encryption and authentication, high-performance / low-bias adaptive array technologies, and RFID applications. He holds 29 U.S. patents.

The growing use of GPS in civil security and monitoring applications brings with it a vulnerability to criminal enterprises suborning GPS for financial gain. For example, asset tracking, identified as the second-fastest growing GNSS market segment after mapping, uses geofencing to raise the alarm when an asset is not where it is supposed to be. Geofences can be time-dependent and dynamic, so cargo in transit can be monitored as well. The successful theft of an intermodal shipping container could provide ample incentive to develop a GPS signal spoofer to cover criminal activity.

The 2001 Volpe Report, Vulnerability Assessment of the Transportation Infrastructure Relying on GPS, states that “The DOT should coordinate with the DoD to ensure that appropriate anti-spoofing technologies are available to civilian applications, should the need arise. It is important to identify observables that may indicate spoofing in civil safety-critical receivers. In addition, DOT should develop independent information to determine the validity and extent of possible civil spoofing threats.”

Other examples of illicit gain that may encourage spoofing include:

the highly regulated fisheries industry, where an onboard vessel monitoring system (VMS) reports positions in real-time to monitor compliance with regulations. If a fishing vessel can cover its true activity for 30 minutes, it might land an additional $60,000 worth of fish, crabs, or shrimp.
illegal dumping of trash and other hazardous materials, estimated as a $10–$12 billion industry.
theft of private data records. More than 150 million records have been lost or stolen in the last 40 months, potentially enabling identity theft, credit card fraud, voting fraud, and other exploits. Geo-encryption techniques relying on GPS can restrict access to plaintext data based on location, time, and key access. My own Geocodex LLC is currently commercializing this technology with extensive anti-spoofing design elements.

As these examples show, there are strong motivations to compromise GPS location integrity. We have clear financial and ethical reasons to prevent this from happening by securing the location determination process, in what I call location assurance. In this essay, I describe what is involved in developing an effective spoofer given current “open door” civil signal architectures and show how civil vulnerabilities differ greatly from military vulnerabilities. The Internet and software-defined radio (SDR) architectures play a major role in advancing the civil spoofing threat. Finally, I will look at prospects for hardening GPS, Galileo, and Loran signals against spoofing attacks. Navigation signals can be hardened and it is not all that difficult — but it will take an act of national will to do so.

The Evolving Threat

Two primary avenues of attack on the GPS portion of location-based security systems are denial of service (DoS) and spoofing. DoS seeks to deny positioning services by masking GPS signals with noise (jamming) or by preventing the GPS signals from reaching the receiver (shielding). Spoofing’s objective is to convince the receiver that it is at a location and time of the spoofer’s choosing. Three general approaches to spoofing are:

Software code spoofing wherein the victim receiver is uploaded with fraudulent software. This may be the result of a phishing attack, website impersonation, or a deliberate act on the part of the victim (most cargo thefts are inside jobs).

Differential corrections spoofing wherein a substitute set of corrections is provided to the victim receiver. Architectures using non-authenticated, non-ranging links such as the Coast Guard’s MSK beacons, LAAS, and RTCM-SC-104 are vulnerable but the limitation is that only relatively small errors can be created.

GPS signal constellation spoofing wherein a GPS signal generator is used to synthesize a navigationally consistent signal set and overlay or substitute them for the actual satellite generated signals. This is the least physically invasive approach.

Admittedly, spoofing attacks require more sophistication than DoS attacks and the reader might ask, why not jam the GPS receiver? The problem is that disrupting the GPS receiver will raise the alarm. Using a spoofer, everything will appear normal to the monitoring system.

Most civil GPS receivers are susceptible to GPS signal constellation spoofing since the signals are broadcast in an unencrypted and well-known format. Receiver-autonomous integrity monitoring (RAIM) and fault detection and exclusion (FDE) features designed to detect faults are ineffective in detecting this type of spoofing since the presented spoofing signals are navigationally consistent; there are no bad satellites.

FIGURE 1

FIGURE 1 shows a notional constellation spoofer capable of both absolute and relative position spoofing modes. In many exploits, it is important that the spoofer be capable of generating signals close to the truth so as to merge spoofed position with the victim platform’s true position at the beginning or end of the exploit.

Several sources have argued that this is impractical, requiring lidar or radar systems to determine the victim’s true position. This is likely true for a military platform but in the civil sector, the criminal may use the expedient of placing the spoofer onboard the victim platform, often with the victim’s acquiescence. In the limpet spoofer configuration, an ordinary GPS receiver using true signals determines the platform’s position in real time. As an added benefit, because of its close proximity, the spoofer can transmit using extremely low powers, thereby reducing the probability of detection.

Returning to Figure 1, spoofing signals are generated at a low IF using a software-defined signal generator, D/A converted and then upconverted to L-band. At first glance, this may appear to imply a large and expensive engineering effort on the part of the criminal enterprise but, in fact, most of the parts are available off the shelf. The developmental cost of a limpet spoofer is not prohibitive, given the potential illicit gain, under current state of the art.

In the 5–10 year horizon, the situation deteriorates considerably. Wireless connectivity is becoming ubiquitous and will make access to spoofing (and jamming) much easier. Powerful laptop computers and multipurpose phones increasingly rely on their processors to handle complex RF signal processing and protocol functions. Cellular telephony, GPS, HDTV, Wi-Fi, WiMax, FM radio, and Bluetooth all can and have been reduced to a set of software routines, callable on demand. Using Moore’s law, we can project a 6x to 32x increase in processing power over the next 5 to 10 years, at which point, the RF circuitry in mobile devices will be little more than a multiband RF transducer to interface to the external world. Cognitive radio, reduced cost, increased utility, a need for flexible international interfaces, and an ability to rapidly upgrade are just some of the driving forces behind this trend. The requisite spoofing hardware, a multifunction wireless appliance, will be universally available, and from there it just becomes a question of finding the right software. At that point, even ordinary consumers might be tempted to use spoofing to avoid road use taxes, congestion fees, or confound “pay as you go” insurance schemes.

Hardened Nav Signals

What are the prospects for preventing spoofing? One approach integrates and cross-checks GPS positioning with other navigation sensors; for example Loran, IMUs, electronic compasses, and so on. While valid, such approaches radically increase cost in a very cost-sensitive market. Furthermore, these methods don’t fit well with low duty cycle, battery-powered monitoring applications and/or AGPS paradigms. A way is needed to authenticate a signal as actually being from a GNSS satellite, independent of any other external input. The L1C, L2C, L5, and Galileo signals present a major opportunity to incorporate authentication features into the signals themselves. The satellites have yet to be launched. Benefits would be almost immediate since access to even one authenticatable signal makes signal constellation spoofing much more difficult.

The DoD uses cryptographic techniques to encode spreading sequences for their Y-code and M-code signals. Not only does this deny access to unauthorized users, it serves as the primary signal authentication method since a spoofer would need keys to be able to generate replica signals with a high degree of fidelity. Galileo is considering similar approaches for authenticating their commercial services signals in the E6 band and the Japanese QZSS LEX signal seems likely to follow. While encrypted navigation signal architectures are appropriate for military systems, their use in civil architectures is highly questionable. The core problem is that the user equipments need to hold secrets that, if compromised, can compromise the whole security architecture. Furthermore, any dissemination of secret information, such as keys, would be subject to intercept by the spoofer who could then generate “authenticatable” signals.

Secure civil signal authentication requires an approach very different from military signal authentication; one has to assume that anything provided to the user segment is also available to the spoofer, including keys. Fortunately, cryptographic based authentication algorithms (see sidebar) can be adapted to navigation signals in ways that do not require dissemination of secrets to the user (and spoofer) community. This is not to say there are no secrets; the control segment and space segment have to be trusted entities capable of secret transmission and storage but the user segment can be treated as untrusted, incapable of keeping a secret. How can this be accomplished?

Time can be a very powerful discriminant in deciding whether a received signal is valid or not. Just about every GPS receiver has an internal timekeeper used to maintain time while the receiver is OFF. Even a simple crystal oscillator (XO) with 2 ppm stability drifts no more than ±63 seconds over a one-year interval. If the received, external GPS time differs from internal watch time by more than its expected drift, then the user should get suspicious — why are the two time sources in disagreement?

In what follows, the core objective is to introduce signal features that make it very difficult for a spoofer to generate valid signals that will pass authentication tests while remaining synchronized with GPS time. Manufacturers may choose to implement only some or none of the authentication methods. To this end, we consider a three-level signal authentication architecture:

No Enhancement. Receivers can ignore signal authentication features and still successfully operate thus maintaining backward compatibility with extant receivers.

Data Message Authentication. Have satellites digitally sign the low-rate 25/50 bits per second (bps) data streams. Authentications can be implemented in software.

Spreading Code Authentication. Interleave low duty cycle cryptographic spreading sequences with normal sequences for later verification. Compatible with AGPS paradigms where user equipments do not read 25/50 bps data directly off the air.

Data Message Authentication

The new L2C and L5 signals use a flexible CNAV message architecture similar in concept to that used in L1 WAAS signals. Currently there are six message types providing clock corrections, satellite ephemeris, almanac, and so on. Adding a new type 7 authentication message, data in the other messages could be authenticated using a public key digital signature algorithm along the lines shown in FIGURE 2. Authentication messages would be sent about once every five minutes.

FIGURE 2

Numerous public key/private key digital signing algorithms are described in the literature, but the core concept is the notion of creating a key pair with two distinct keys, one private and the other public. The private key would be known only to the control segment and space segment and would be used to sign the other message types. The corresponding public key would be made freely available to anyone, including spoofers. It can be used to authenticate the signature in message type 7, but not generate it.

How does data message authentication impede a spoofer? First, he has to use off-the-air data streams since he has no way to produce valid signatures. If the intended victim has been tracking legitimate signals recently, it has precise internal time, and the window of acceptance regarding time is very narrow. Effectively, the spoofer is forced to read the 50 or 25 bps data stream off-the-air in near real time and replay it on his altered pseudorange signals with a small (milliseconds) delay. This is doable but not particularly easy, as it requires near-simultaneous true signal data demodulation and spoofing signal transmission. It is definitely not something an off-the-shelf signal generator does.

For added security, the public key(s) distributed to the user community to check signatures should also be signed by a Certificate Authority (CA) in order to validate the public key to the user community. This keeps a spoofer from publishing a public key of his own. In principle, over-the-air public key distribution and renewal could be part of the type 7 message structure.

Stanford researchers are using a variant level 1 authentication called TESLA, originally developed at UC Berkley for use with Loran’s 9th pulse modulation scheme; Loran station Middletown is already transmitting the prototype version.

Spreading Code Authentication

Relying solely on data stream authentication is problematic for the AGPS community in that many of these receivers do not read data. Receivers are most vulnerable to spoofing when they have been turned off or jammed for a while since they no longer have precise time information. Also, the short, civil spreading codes introduce vulnerabilities in that the spoofer can simply wait an integer number of code periods before imposing the “from the satellite” data stream. The question becomes, how can we more tightly bind data stream timing to code stream timing? Is there a way to make the code period longer than the window of acceptance (internal clock uncertainty) without affecting the desirable aspects of short period codes? One answer lies in interleaving spread spectrum security codes (SSSC) with normal spreading sequences. This also serves the AGPS community since they can grab select SSSC segments and use them for position authentication.

The SSSC concept relies on the fact that the satellite can know what digital signature is going to be sent in a type 7 authentication message several minutes before it is actually sent. This is because it knows exactly what is going to be transmitted in message types 1 through 6, and, it has access to the private key. The as-yet-unsent digital signature can be used as a seed value for generating SSSC spreading sequences.

In FIGURE 3, we use the L5 signal for a more concrete discussion. Here, the SSSC is transmitted on the L5I channel at a chip rate of 10.23 MCh/sec in blocks of 102,300 chips. This does not affect tracking, which uses L5Q pilot channel. On the receiver side, if the receiver is tracking, it knows precisely when SSSC is being received but has no idea of the actual SSSC sequence until it receives the authentication message. Referring to FIGURE 4, during SSSC intervals, the receiver collects carrier phase corrected precorrelation samples off of the I-channel and stores them.

FIGURE 3

FIGURE 4

Once the digital signature is received in an authentication message, the receiver generates the security spreading code reference signal and despreads the previously collected and stored A/D samples. If the SSSC and its correlation features are not detected at the correct power level, the signal is not authenticated. For AGPS receivers, the type 7 authentication message might be sent via SATCOM or cellular to permit local authentication without passing around stored A/D samples.

How does this protect against spoofing? If the type 7 authentication message is sent once every five minutes, user segment receivers can look as far as 5 minutes back in the signal for valid SSSCs with strong assurances that a spoofer had no capability to generate them using the digital signature. Without access to the digital signature, the spoofer must read the SSSC directly from the transmitted signal. This is difficult since the SSSC is a spread spectrum signal buried below thermal noise and so a multiple beam, steerable, high-gain antenna is needed to successfully read the SSSC chips directly.

Conclusions

As GPS finds wider application in security and monitoring paradigms, it will become a more tempting target for attack by spoofing in a variety of exploits where the primary objective is financial gain. Arguments that spoofing is impractical or too complicated tend to be part of the accumulated wisdom from the dawn of GPS when the focus was mainly on the military threat. A reexamination of these arguments in light of a civil threat and with current technology shows that spoofing is not impractical and that a credible spoofer could be developed for less than $10,000 using off-the-shelf parts. Looking towards the future, it seems probable that wireless connectivity appliances could reduce the criminal’s problem to finding the right software off the Internet.

The current open-door approach to civil navigation signal security is not in the national interest. Workable signal security schemes have been proposed here, and to signal definition committees, that give the user segment the option to lock the door. The L1C signal in particular is a strong candidate for hardening since the signal definition has not been finalized.

The time is now, before the next generation of satellites is launched. Adding security in a post hoc fashion can be a Herculean task. Just ask Microsoft.

For a more technical discussion of GPS signal authentication, see the author’s ION GPS 2003 paper entitled “Anti-Spoofing and Authenticated Signal Architectures for Civil Navigation Systems.”

---------------------------------------------------------

A Short Tutorial on Encryption and Authentication Algorithms

Encryption algorithms can be divided into two categories: symmetric algorithms and asymmetric algorithms. Referring to FIGURE B1, symmetric algorithms use the same key for encrypting and decrypting plaintext. Numerous, very fast symmetric algorithms are in widespread use, including DES & Triple-DES and the Advanced Encryption Standard (AES) . Keeping the key private is essential to maintaining security and therein lies a crucial question: how to share keys securely. Numerous techniques have been developed and the interested reader is directed to Bruce Schneier’s, “Applied Cryptography, 2nd ed.” for further discussion.

FIGURE B1 FIGURE B2

Asymmetric algorithms are comparatively new on the scene with the first published description in 1976. Also known as Public Key algorithms, these algorithms have distinct keys for encryption and decryption as is shown in FIGURE B2. Here, Key_E can be used to encipher the plaintext but not to decipher it. A separate key (Key_D) is needed to perform this function.

In principle, to securely convey the plaintext, the intended recipient could generate a key pair (Key_E, Key_D) and send Key_E, the public key, to the originator via unsecured channels. This would allow the originator (or anyone else) to encrypt plaintext for transmittal to the recipient who uses Key_D, the private key, to decrypt the plaintext. RSA, named after its creators Rivest, Shamir, and Adleman, is perhaps the most popular asymmetric algorithm in use today.

A message’s provenance can be established using an authentication algorithm along the lines shown in FIGURE B3. Here, the sender creates a message digest derived from the message using a Secure Hash Algorithm (SHA). This is a one-way function and there is no associated key. In a sense it is like a CRC parity generation algorithm, except highly non-linear so it is difficult to create a second message having the same message digest. The sender creates a digital signature by encrypting the message digest using his private key which is known only to him. The sender then conveys the message and the digital signature to the recipient. Note that the message itself can be sent in the clear. Our objective is not to hide the message, simply to establish provenance.

FIGURE B3

The recipient authenticates the message by generating a message digest from the received message using the same SHA as the sender and then compares it with the decrypted digital signature. If they agree, then the recipient can be confident that the sender has the corresponding private key and that the message has been received without error or alteration.