Keeping the Spoofs Out
Signal Authentication Services for Future GNSS
A growing number of applications require that GNSS receivers are not processing false signals—or being "spoofed." The article assesses the navigation message authentication concept of signal security, discusses its limitations and proposes a new approach based on signal authentication sequences that can be integrated into GNSS systems. The method works on systems that provide an open and encrypted service on the same frequency and would require minimum changes to the system.
The demand for techniques capable of authenticating the GNSS signals and detecting simulation attacks (spoofing) has increased exponentially in the last years, mainly targeted to financial and safety critical applications.
Associated proposals and developments addressing these issues focused on two different approaches: user segment authentication services that leveraged existing services in order to detect signal spoofing and that integrated signal authentication services into the GNSS system itself.
Although the first approach can work with existing GNSS systems and those under development that do not provide a signal authentication services — such as the GPS C/A-code and Galileo E1B signals — the latter approach requires a new system design and/or modification of existing system architecture.
This article focuses on the integration of authentication services into future GNSSes, first explaining the architecture design for the various components of ground, space, and user segments. The article concludes with a discussion of the anticipated performance of the proposed authentication scheme and a comparison of different deployment architectures.
Authentication: Signals or Messages?
Spreading code encryption (SCE) is the preferred option to limit access to a GNSS signal and, therefore, to the system’s positioning and time functions. However, if the only objective of a service is to provide signal authentication (robustness against signal spoofing), NMA and SAS are preferable as they can reduce the cost of the receiver, providing full navigation access to users who have no access to the authentication infrastructure.
The first attempt to integrate an authentication mechanism for open signals in GNSS was introduced by L. Scott in a 2003 paper (see Additional Resources for full citation). Scott based his concept on secret spreading sequences, called spread spectrum security codes (SSSCs), that were modulated in the signal for 10 milliseconds every 1 second of modulation with a known spreading sequence. SSSCs are transmitted in the navigation messages and used for correlation with the received signal in order to verify the authenticity. In his proposal Scott also outlined a scheme for authenticating the data.
One limitation of such an approach is the need to modify an existing modulation scheme, which has significant consequences involving alterations in the system infrastructure. Furthermore, introducing noise (the receiver can’t track the code during the 10 milliseconds of SSSC modulation could create implications in some delay locked loop (DLL) and phase locked loop (PLL) receiver designs. A similar SSSC concept was described the following year in a paper by M.G. Kuhn.
An authentication scheme based on navigation messages only was proposed later in the paper by C. Wullems et alia and further explained in articles by G. Hein et alia (see Additional Resources).
A fundamental parameter in the design of NMA schemes is to include in the cryptographic integrity scheme at least the message transmission time reference — time of week (TOW) and week number (WN) — and the satellite ephemerides, as they are used to help determine the pseudorange.
However, because the time is repeated over the weeks, leaving the ephemeris the only unpredictable information, the introduction of unpredictable information such as a secure random number is required in order to avoid so-called “replay attacks” in which a valid data transmission is maliciously or fraudulently repeated or delayed.
Figure 1 shows a hypothetical NMA scheme in which a “nonce” is introduced through a secure random number–generation function in order to increase the stochastic property of the data. In cryptography, a nonce is a value that is used only once within a specified context. For example, as described in the Galileo Open Service Signal in Space Interface Control Document (OS-SIS-ICD), Galileo F/NAV messages Page Type 1 has 26 spare bits that could be used for inserting a nonce.
The nonce entropy and size are typically designed with respect to the probability that a system will experience a “brute force attack,” which quantifies the likelihood that an attacker will have to guess the entire message and reuse the authentication message.
In such an authentication scheme, the NMA messages could be generated on the ground (where the ground control center knows the ephemerides and the keys, and can generate all the NMA for the various time slots). In this case, the satellite only needs to synchronize the insertion of the nonce in the correct subframe or page (i.e., no encryption operation on the satellites). NMA data could also be advanced in time in order to allow a faster “time-to-authentication.”
An NMA scheme is vulnerable to three types of attacks:
Figure 2 shows the “spoofable” areas in this kind of attack: Zone A is the unpredictable area, in which a spoofer could not predict the authenticated navigation messages in the signals traveling through space.
Zone B is an area where some satellites could be spoofed, but this can be detected by anti-spoofing receiver autonomous integrity monitoring (AS-RAIM) algorithms, as the position solution obtained from different satellites would contain inconsistencies due to the positive delay contribution in the pseudoranges.
Zone C is the only practical area of spoofing in this type of attack, as the position solution could still be projected in order to appear consistent after AS-RAIM verification.
However, in most of the scenarios with six to eight satellites in view at low elevation, this area would be practically reduced to a vertical range, and the security function might be designed to support only some particular geometries obtained only by SVs above some degree of elevation, because high elevation SVs could deceive the system while low elevation would be detected by the AS-RAIM.
For road applications a receiver could verify its position with a digital elevation model (DEM) in order to verify the consistency. Further research is needed in this domain to study which geometries could provide sufficient security for NMA.
However, GNSS satellite navigation payloads typically spread message data over long codes (e.g., 4,092 chips for Galileo E1B) or repeated sequences (20 x 1,023 chips for GPS C/A-code) in order to reduce the bit error rate. An attacker can attempt to integrate a shorter time or correlate a subset of the code in order to detect the bits and replay the data with the intended delay in order to create and transmit a negative delay in the pseudorange.
The probability of success for such attacks is dependent on the carrier-to-noise (C/N0) ratio. The paper by D. H. Arze Pando listed in Additional Resources discusses this method of attack and provides some statistical results.
Figure 4 shows the normalized auto-correlation function (ACF) of a Galileo E1B code of 4,092 chips (green line) assuming a four megahertz filter. The figure shows graphically that a subset of the code (1,023 chips, blue line) could still be detected by a discriminator function, while a shorter code (102 chips, red line) would not be sufficient. A 1,023-chip code could be used to introduce negative delays in the pseudorange of up to three milliseconds (resulting in a 900-kilometer ranging error).
Architecture of Signal Authentication Sequences
Signal-level access control requires the encryption of the ranging codes. A direct block cipher encryption of the code is typically not a preferred design option because a time-limited code can be captured with a high-gain directional antenna.
A more robust approach is the use of a stream cipher, as the code never repeats. A stream cipher is a symmetric key cipher where plain bits are combined with a pseudorandom cipher bit stream (keystream), typically by an exclusive-or (xor) operation. In order to encrypt a pseudorandom noise (PRN) sequence, the plain sequence is modulo 2–summed with the stream cipher, resulting in an encrypted PRN sequence.
For the purpose of the concept demonstration, we assumed a BPSK signal with an open code modulated in-phase and an encrypted code modulated in quadrature. The transmitted signal (neglecting signal amplitude) will be generated as follows:
where N is the number of visible satellites, Oak and Obk are the publicly known spreading codes for every K satellite, SCk is the stream cipher, and Dk is the transmitted data. The same concept can be applied to a coherent adaptive subcarrier modulation (CASM) in which multiple channels are multiplied together.
One design factor of interest is the frequency of the stream cipher versus the chipping frequency of the PRN sequence. For our analysis we define this variable as a binary stream-cipher carrier (BSC):
where FSC is the stream cipher SCk frequency, FC is the non-encrypted code Obk chipping frequency, and m = FC / FSC, n = FC / Fref, and Fref = 1,023 Mcps comprise a set of terms describing the GPS C/A reference code. For example, a signal with a Obk chipping rate of 10.23 megahertz and a stream cipher SCk frequency of 1 megahertz will be encrypted with a BSC(10,10).
The objective of our proposed system is to authenticate the open GNSS signal. The proposed security architecture can be integrated into GNSSes that use direct-sequence spread spectrum (DSSS) as their modulation technique. This approach can provide on the same frequency an open signal service, where the spreading code is publicly released, and an encrypted service where the spreading code is ciphered.
The security concept is based on the unpredictability of the encrypted PN sequence, which is assumed to be generated a priori by a secure function. The concept is as follows: the stream cipher SCk is observed in a predetermined period. As shown in Figure 5, a portion of the binary sequence is extracted with the SAS epoch time reference for a specific time frame, e.g., SCk [0:5000, n0] if 5,000 chips are observed at the discrete time n0.
The sequence is processed and transmitted in the open-service navigation messages together with an authentication and/or encryption scheme. This message is defined as the signal authentication sequence (SAS) defined as follows:
where l is the length of the SAS code and n0 is the first chip of the SCk observation time.
During the open-service data decoding process and after authentication verification or decryption, the receiver obtains the SAS, generates the PN sequence for that specific epoch, and correlates it with samples of the encrypted code. The correlation result is fed to a security algorithm that determines the signal security state based on an estimated threshold.
The SAS messages are transmitted in the open signal and received by the user receiver, which verifies the integrity and/or decrypts the data content. The user receiver also acquires the encrypted message at the predefined epoch and verifies the signal’s authenticity with an algorithm, which we will describe later.
Message Overhead and SAS Data Truncation. A number of navigation data must be received by the receiver with a certain priority, such as time of week (TOW), clock corrections, and ephemeris data. Therefore, SAS messages shall be transmitted in order to not interfere with such data.
Depending on the channel bit rate and spare available data, the designer of the system can decide to transmit the entire SAS sequence or to truncate it in sub-messages. The SAS size is determined by a number of factors, including encryption scheme and modulation type, signal power, and expected receiver noise floor.
SAS Advance/Delay Approach. There are two approaches to SAS transmission: advance the SAS in time with respect to the encrypted signal or delay the transmission. Delaying the SAS would reduce the risk that an attacker regenerates the sequence. The time to alert (TTA) would be proportional to the frequency of SAS transmissions.
Preventing Fake Encryption. The SAS message should integrate authentication and encryption so that an attacker cannot generate a fake encrypted signal at the precise SAS epoch.
Timing. The SAS time reference could be set with two approaches. A predetermined recurring time slot (for example, the first code phase of the first subframe) or randomized in order to increase the security. (In the latter case the SAS message should indicate the precise epoch in which to perform the correlation search.) The timing of the epoch for the correlation search should be projected in order to avoid a bit transition.
where e(n) is the thermal noise introduced in the sampling process.
Doppler frequency wipe off as well as code and phase locks are assumed to be performed on the open code Oak. The receiver will attempt to store the encrypted signal at the discrete time [n0: n0 + l] as defined by the protocol. After the carrier removal by multiplication with sin(ωIFn) and after application of a low-pass filter cut downconvert the received 2ωIF frequency to intermediate frequency (IF), the remaining signal is:
The receiver can generate the spreading sequence as the modulo 2 sum of the SAS code defined in equation (3) and the public spreading code, resulting in a short, local security code replica (SCR):
where j is the specific satellite code.
A security processing function will evaluate the correlation value Cj defined in equation (7) of the encrypted signal and the local replica based on a threshold for every k satellite.
This security processing function will determine the signal authentication state based on a threshold that can be set as parameter in the receiver. Figure 8 shows a hypothetical example of SAS receiver.
The SAS transmission block simulates a BSC(m,n) signal, where the spreading code has a 10.23 megahertz chipping rate, a BOC modulation, and the stream cipher frequency m and number of satellites n can be set in the software. A subset of the stream cipher is used to generate the SAS, that is stored simulating a transmission in the open signal. The spreading code and stream cipher are modulo 2 summed, obtaining the final modulation code. The software correlates the SAS with the encrypted code in the predetermined period and performs analysis on the correlation results.
The idea is that a correlation peak indicates a correspondence between the SAS and the unpredictable encrypted code, resulting in a high confidence that the signal is authentic. (As mentioned previously, the security is based on the fact that an attacker could not generate the encrypted signal.) A low correlation value means that the SAS is different from the encrypted code, indicating a possible spoofing attack.
The simulation incorporated the following parameters:
Detecting Spoofed Signals
In Figure 10 we have spoofed SV 3. The software generated a random PRN code instead of the original encrypted sequence, simulating a single-SV signal spoofing (such as might be performed with a receiver-spoofer) or by buffering and retransmission (with delay) of the original signal. The results show that all the satellites are authenticated except SV 3 where the code replica SCR3 had a noticeably low correlation with the spoofed sentence.
Figure 11 shows the case where all satellites are spoofed. The correlation at the SAS epoch is lower (<0.1 norm.).
False Positives & Negatives
Varying the SAS length and the threshold, two plots are shown. Figure 12 shows the false positive variation. It can be seen that increasing the SAS length decreases the probability of false positives. False negatives, however, do not seem to be significantly affected by the length of the signal authentication sequence within the plot range of 500 to 5,000 chips (See Figure 13). (Note that the labeling of the graph axes is reversed in the two figures.)
The correlation threshold also affects the two plots differently: increasing the threshold produces more false positives while false negatives decrease. This is because the correlation value must be higher in order to pass the security threshold, and a threshold too high might exclude even satellites that are authentic.
From this analysis, we can conclude that a good compromise would be an SAS length of 5,000 chips and a correlation threshold of 2. With these values we obtain the following probabilities:
NMA and SAS Operating Modes
The user-based signal authentication (Mode A) refers to the authentication of only the signal and assumes a context where the user derives no benefit from compromising the receiver. The second mode (Mode B) refers to the same context, but data is sent to a remote service that will verify the authenticity of the signal.
The third mode (Mode C) refers to a context in which the user is not trusted (could benefit from spoofing the receiver, e.g., in a road tolling scheme) and could tamper with the data and receiver; therefore, the PVT output needs to be authenticated.
Figure 14 portrays Mode A. Navigation message authentication or signal authentication sequence data are received either via space or via ground communication (authentication service provider). In an NMA scheme, the receiver passes the navigation data (or a hash of it) and the NMA sentence to an authentication security module (ASM) for verification.
In the SAS scheme, the receiver passes an encrypted signal sample and the encrypted SAS message to the ASM. The authentication security module will decrypt the SAS message, generate the security code replica, attempt to correlate the codes and satellite signals, and return the authentication state. The ASM can support both symmetric and public key cryptography.
The remote authentication mode (Figure 15) foresees a receiver that sends data to an authentication service provider for a post-processing verification. In the NMA scheme, the receiver will send the navigation data (or a hash of it) and pseudorange to the authentication provider, which will verify the consistency of the message and the position solution. In the SAS scheme the receiver will transmit a sample of the encrypted signal (in a precise epoch) to the authentication provider, which will verify the authenticity of the signal with the SAS messages.
The user-based signal authentication and PVT integrity mode (Mode C) has the same architecture as mode A but foresees a context where the attacker will attempt to tamper with the receiver. Therefore, the ASM must be integrated in a tamper-resistant portion of the user equipment, otherwise an attacker will attempt to tamper with the communication between the receiver and the ASM. The article by O. Pozzobon et alia (1) discusses aspects of tamper-resistant GNSS receivers.
Test results indicate that the signal authentication sequences concept can be used for authentication in systems that provide both open and encrypted signals, achieving a higher security level compared to navigation message authentication schemes (see Table 2), and that the security achievable with SAS with respect to spoofing attacks is comparable to that achievable with spreading code encryption, both being based on the security of the encrypted signal.
Copyright © 2017 Gibbons Media & Research LLC, all rights reserved.