A decade has passed since the first GNSS system-level authentication protocols were proposed, and yet the current ongoing discussion is still, “Do we really need GNSS signal authentication?” Indeed, the current argument is whether we need authentication at the system level (the satellite broadcast service) or whether user-based authentication (anti-spoofing) is sufficient for a number of application requirements.
A decade has passed since the first GNSS system-level authentication protocols were proposed, and yet the current ongoing discussion is still, “Do we really need GNSS signal authentication?” Indeed, the current argument is whether we need authentication at the system level (the satellite broadcast service) or whether user-based authentication (anti-spoofing) is sufficient for a number of application requirements.
Risk analysis for every application should produce security requirements that would allow us to discriminate determine the actual need of either user-based or system-based techniques. For instance, if the likelihood of a spoofing attack on your favorite car navigator is quite low and the resulting effect would be negligible, car navigators probably will not require use of encrypted signals with security module for authentication. Some simple checks on the receiver time bias and carrier-to-noise power density (C/N0) will do the job to fulfill these requirements.
On the other hand, unfortunately, we expect a growing number of threats and cyber-attacks in the future: the Internet has three billion users today, and the annual impact of attacks on the global economy has risen to $445 billion. With GNSS having more than two billion devices in operation today and seven billion predicted for 2020, a number of GNSS safety and financial critical applications will demand more and more security and trust.
This article will take up the problem of GNSS signal authentication, beginning with the definition and classification of requirements and presenting a categorization of applicable schemes. We will provide an extensive summary on state-of-the-art, data-level authentication schemes, based on well-established broadcast authentication protocols that can be exploited for providing efficient navigation data authentication. In particular, we introduce a novel scheme for open signal authentication using supersonic codes.
Foundations of Signal Authenticity
GNSS authentication is a complex multi-domain problem. A receiver estimates its own position and time by calculating ranges and time bias from satellites, with satellite positions and system time obtained from the same source. This leads to the conclusion that GNSS authentication is achieved by:
- the level of trust in the range estimation
- the level of trust in satellite position and system time information
- the level of trust in the component equipment that calculates position, time, and velocity from the foregoing factors.
Various branches of science and engineering help us address these three problems, particularly, signal estimation theory, information source authentication and non-repudiation, and physical and software security.
As physical and software security pertains to receiver design requirements, we will focus on range estimation and data authentication and trust for the system-level aspects. One complexity in GNSS signal authentication design is that the use of data-level authentication does not necessarily fulfill the trust requirement for range estimation, and trust in range estimation does not satisfy the trust requirement for the authenticity of satellite data.
Another crucial point to discuss in requirements analysis is the need for source authentication or non-repudiation, the ability to ensure that a party to a communication cannot deny its authenticity. For example, in cryptography source authentication can be achieved with a message authentication code (MAC). “Alice” sends information with an attached MAC to “Bob,” and Bob can verify the source authentication. However, MAC does not achieve satisfy the need for non-repudiation, as an impartial third party cannot verify the origin of the message because both Alice and Bob own the secret key to generate the MAC.
In GNSS non-repudiation could be a requirement worth considering. For example, as illustrated in Figure 1 (for Figures 1 – 4, see inset photo, above right), a ship might be navigating in water from Country B, and Country A might challenge its position as being within Country A’s territorial boundary. The ship’s crew might reply that the ship position only appears to be in Country A because of a spoofed signal, but it actually did not cross the borderline. Country C would be the impartial third party that has the capability to verify if Country B used authentic signals.
We can summarize the requirements for GNSS authentication in terms of the following factors:
- navigation data integrity, source authentication, non-repudiation and/or position/velocity/time (PVT) authentication
- performance, such as time to authentication (TTA) and accuracy of authentic position
- probability of failure
- robustness
- interoperability.
Time to authentication refers to the time required by the system to detect an anomaly and respond to it. In signal authentication, TTA is an important requirement, as the receiver time and dynamics will be compromised from the beginning of a spoofing attack until its detection. Therefore, these effects need to be minimized quickly and appropriately, based on application requirements.
Probability of failure refers to the trust that one can give to the authentication scheme. This includes the probabilities of missed detection and false alarm, and is fundamental for the determination of the integrity risk in safety-critical applications. For example, if we want to use an authenticated signal in a safety-of-life (SoL) application with an integrity risk requirement of 3.5 x 10–7 over 150 seconds, these requirement constraints are expected to represent the lower bound for the probability of failure of the authentication protocol.
Robustness refers to the capability to mitigate a number of known attacks. For example, some application may require protection from replay attacks, while others may not.
Finally, interoperability refers to the capability of the authentication scheme to be used by a number of different applications in various environmental contexts, and to be transparent to legacy equipment. For example, providing support to L1 frequency without compromising other navigation service performance represents an important interoperability requirement.
Authentication Domains
To date, GNSS authentication protocols have been proposed in three domains: data level, signal level, and hybrid level (data + signal).
Data-level authentication schemes refer to the implementation of cryptographic protocols in the navigation data. In simple words, such approaches can be seen as “digitally signing” the navigation data in order to authenticate the source of the data generator and ensure the integrity of the received message.
In a 2005 paper by C. Wullems et alia (listed in the Additional Resources section near the end of this article), we introduced the concept of data-only authentication, calling the technique “navigation message authentication” (NMA). NMA has the advantage of having a low system impact, as it requires only upgrades of the GNSS satellites’ navigation data generation subsystem along with a low-cost implementation on the receiver side. NMA can be implemented through various schemes that we will discuss later in this article.
Disadvantages of NMA include TTA performance, which is limited to the specific implementation (e.g., digital signatures, block hashing, hash chaining, etc.), as well as the required bandwidth to implement NMA. The probability of failure for an NMA scheme depends on the number of bits included in the authentication function and on the size of the authentication payload. For instance, if 30 seconds of data are authenticated, a single bit error not detected by the channel-coding scheme would result in a false alarm. On the other hand, a missed detection in nominal conditions (not under attack) is unlikely with a well-designed NMA scheme.
Unfortunately, NMA is exposed to replay attacks if the spreading codes are public and available to everyone for the estimation and replay of the symbols. This forces the receiver to integrate a trusted clock in order to increase robustness.
Signal-level schemes tackle the vulnerability to replay attacks by exploiting the properties of spread spectrum signals, which in GNSS are below the thermal noise. For an attacker, with standard equipment and without knowledge of the secret code, it is therefore very difficult to demodulate the signal. Only the knowledge of the secret code, in fact, allows the signal de-spreading to perform ranging and data demodulation.
This article will discuss the state of the art in data-level authentication, and a new approach for signal-based authentication capable of carrying high data rate needed to achieve an efficient hybrid authentication scheme (data+signal authentication).
GNSS Data-Level Authentication
In the field of broadcast authentication, GNSS data authentication seeks to provide a set of security properties, including data integrity, data authentication, and possibly non-repudiation. In particular, GNSS data authentication aims at providing source authentication, that is, at ensuring that a legitimate GNSS satellite actually generated the navigation data received by generic user equipment.
The simplest broadcast data authentication schemes are based on standard applications of authentication solutions, such as message authentication codes (MACs) and digital signatures (DSs), including variations such as hash-based MACs and cipher-based MACs. In general, MACs provide data integrity and data authentication together with bandwidth and computational efficiency but cannot ensure non-repudiation. Moreover, they require secure use and storage of symmetric keys (e.g., via smartcards) in order to prevent a malicious user from compromising the security of the entire authentication service by disclosing the secret keys.
Digital signatures, on the other hand, address all the required security properties (integrity, authentication, and non-repudiation). Unfortunately, they result in high computational and per-packet communication overheads.
More elaborate broadcast data authentication schemes leverage the aforementioned standard authentication solutions and trade-off the following features: computation and communication overhead, buffer space requirements, authentication delay, verification probability, and loss tolerance as opposed to reliable delivery. In the following, three main families of broadcast authentication schemes are considered: block hashing, hash chaining, and MAC-based source authentication schemes. Figure 2 depicts the taxonomy of the broadcast authentication schemes considered.
Block hashing schemes follow the paradigm of spreading the cost of the signature operation among a number of blocks by using the properties of hash functions. The main idea is that, for each set of blocks, a single signature is transmitted together with the hashes of each block. This allows the receiver to verify the authenticity of all blocks, by checking the consistency of each hash with the digital signature.
Block hashing can use either a star or a tree-based approach, depending on the hierarchy of the authenticated blocks. This type of hashing leverages the reduced size of hashes as compared with digital signatures in order to minimize both the bandwidth and the computational requirements. In the context of GNSS authentication, blocks could be identified either with corresponding portions of data (e.g., the same pages) sent by different satellites, or with different navigation message chunks in each satellite (e.g., different pages in a sub-frame).
Hash chaining is a further technique for authenticating streaming data, based on a hash chain commitment via digital signature. The hash chaining can be either “forward” (signature follows data packets, thus resulting in a delayed authentication) or “backward” (signature is transmitted first, thus allowing immediate authentication).
Hash chaining schemes require the sender to know the entire data stream in advance (and is therefore applicable to GNSS ground segment design). In its standard application, however, hash chaining does not tolerate packet loss. Because of this, its application in GNSS authentication is limited, as the bit error rate rapidly degrades with lower satellite visibility at the receiver.
Variations of standard hash chaining have been proposed to address this issue, based on multiple hash chains and resulting in a higher per-packet communication and computational overhead. Efficient multi-chained stream signature (EMSS) is an example of such an authentication protocol, supporting loss-resilient and probabilistic authentication verification. EMSS is based on hash chains of degree k, meaning that each packet’s hash is sent in k different packets, with random chaining sequences leading to a higher probability of verification. Augmented chaining is another strategy that, based on the transmission of redundant hashes, provides resiliency against errors burst. Finally, the piggybacking scheme deals with the case where data carried by different packet has more or less importance from the point of view of the application level.
Various levels of priorities could be assigned to data packets, so that the higher the priority of a packet, the more redundant will be the hash chaining of packets belonging to that class. This approach allows tailoring the robustness of packets against bursty losses as a function of their priority. In the context of GNSS such a technique could be used for maximizing the robustness of the authentication scheme for some selected data (e.g., time of week (TOW), ephemerides, and so on) as compared with less critical types (e.g., the almanacs).
MAC-based source authentication schemes are hybrid solutions that jointly use MACs and digital signatures in order to provide broadcast authentication. More precisely, these schemes are based on four main ingredients: one-way hash chains, (loose) time synchronization, MACs, and digital signatures for the source verification of hash chain commitments.
A remarkable example of MAC-based source authentication is the timed efficient stream loss-tolerant authentication (TESLA) protocol and its extensions, including instant authentication, management of concurrent instances, and increased robustness to denial-of-service attacks. It is worth mentioning that the authors of TESLA also presented another protocol, BiBa (bins and balls signature), that falls in none of the previous three families of authentication schemes. BiBa is based on one-way hash functions without a trapdoor: to sign a message, the signer uses the message to seed a random process, which throws a set of balls into bins. The balls represent SElf-Authenticating Values or SEALs, random numbers generated in a way that the receivers can instantly authenticate them with the public key. The bins correspond to the range of the hash function. When enough balls fall into the same bin, the combination of those balls constitutes a signature.
As a conclusion to this overview, we should note that the robustness of any data-level authentication protocol to transmission errors could also be increased — that is, the probability of authentication failure could be decreased — by using forward error correction (FEC) schemes.
In this context, as described in the paper by M. Canale et alia (Additional Resources), we have tested two different solutions for enhancing the data-level authentication with FEC on the Galileo Commercial Service. The first solution employs a common and effective code concatenation: the inner convolutional code (already available in Galileo) is coupled with an outer Reed-Solomon (RS) block code. These two codes respectively combine good performance in the presence of random and bursty errors. The second solution is based on the nested use of convolutional encoding and interleaving, achieving a double time diversity of the data broadcasting, while keeping the same end-to-end delay of a block interleaver.
Figure 3 shows the performance of the proposed schemes with various parameters in terms of bit error rate (BER) and carrier-to-noise density ratio (C/N0) when a second layer of FEC is applied. The top panel (a) shows convolutional code and interleaving (CC) for various lengths of the input data stream, e.g., two seconds for a single E1 page. The bottom panel (b) illustrates the performance of Reed-Solomon codes with rates 1/2, 2/3, and 0.82 Note that the length of the input data stream has little effect on the E6 BER.
Even though these schemes are proposed in order to compensate the gap between the Galileo Open Service and the Galileo Commercial Service in terms of bit error rate, their use could be extended to an arbitrary data-level authentication scenario. (Due to the E6 SIS design, however, the BER on the CS navigation messages is considerably higher than the one measured on the E1 Open Service for the same signal-to-noise ratio.)
GNSS Signal-Level Authentication
A known technique to provide signal authentication as well as access control is the full encryption of the spreading code. This approach, however, lacks the interoperability property and requires time knowledge (time fix) for the acquisition of the signal.
The first signal-level authentication proposal that allowed interoperability was presented in a 2003 paper by L. Scott (Additional Resources) with a scheme called spread spectrum security codes (SSSCs), which also proposed a data-supporting infrastructure. A similar approach was proposed in 2004 by M. G. Kuhn. Later, in the paper by O. Pozzobon et alia (2010) we proposed a concept based on the dissemination of encrypted chips with a scheme called signal authentication sequences (SAS). A drawback of all these signal-based authentication schemes is a weakness in TTA. They also require an aiding channel or a dedicated bandwidth as chips are transmitted in the navigation data.
One interesting approach that Qascom has investigated is the transmission of secret codes multiplexed with open codes, to achieve what is also known as “signal watermarking.” This led us to the concept of supersonic GNSS authentication codes[18], a solution that provides hybrid authentication achieving both data-only, signal-only, or combined data- and signal-level authentication. The scenic term “supersonic” derives from the fact that authentication could be achieved faster than the symbol speed.
We designed the protocol in order to fulfill the previously mentioned requirements for signal authentication. Particularly, we considered these main drivers:
- Low probability of failure in nominal conditions. The protocol can define the code length in order to satisfy the desired probability of failure requirements.
- Legacy hardware support via combination with an open signal (multiplexing). The main idea is to transmit the supersonic codes multiplexed with open codes (such as GPS C/A or Galileo OS) to allow interoperability with open services and support mass-market applications.
- Based on symmetric cryptographic schemes. This is required for signal-level authentication.
- Based on block ciphers. The supersonic codes are block ciphered and in code phase with open codes, and the same code is repeated for a predefined security period. This allows direct authentication without time dependency, as opposed to stream-cipher-based solutions.
- High data rate capability to support the transmission of data authentication schemes such as block hashing digital signatures or hash chains as discussed before.
- Comprises two stages, for achieving different security levels based on robustness requirements and/or receiver constraints.
High-Level Protocol Description
As an introduction to the proposed authentication scheme, the following section provides a high-level description of supersonic code generation.
The proposed protocol assumes that the supersonic codes are multiplexed with an open code, and that they are synchronized to it. This scheme is based on the block-cipher encryption of the open code, resulting in an encrypted code valid for a predetermined crypto-period Tcrypto (Figure 4). When a crypto-period expires, a new initialization vector (IV) is provided as input to the block cipher and a new encrypted spreading code is generated. In the following discussion, we refer to the encrypted code as “fundamental code.”
This strategy allows a receiver that knows the IVs (for example, through previous transmission via navigation data) to select the IV to be used with a loose system time synchronization of the receiver and without a time fix. For example, a receiver clock with poor performance (e.g., 10–5 seconds in a one-second drift) could guess a five-minute window after one year. So, a receiver lacking a time fix can still acquire the supersonic code based on a rough estimate of time.
The fundamental code is then modulated with a code-shift-keying (CSK) modulation, where the CSK shifts are generated by time-dependent unpredictable symbols. This ensures that the scheme is not vulnerable to an attack based on coherent integration and forces an adversary to continuously read the CSK shifting in order to perform a signal-based replay attack, by making the attack very complex and unlikely.
As a further benefit, GNSS signal design is looking to CSK as a new opportunity to increase the bit rate of GNSS signal data components and extend the possibility of adding new services. Indeed, with the introduction of new dataless (pilot) signal components that enables receivers to achieve precise synchronization on the pilot channel alone removes the need to adopt BPSK modulation for the data.
Supersonic Codes: An Analytical Description
We will now describe the process of generation of the supersonic codes with an analytical approach. First, we will detail the signal generation process, then describe the estimation at the receiver, and follow up with an explanation of the procedure for verifying signal authentication.
Signal Generation. Let p and c0 be the open and a fundamental code, respectively, and Lp and Lc the corresponding number of chips. In addition, let Tp and Tc be their respective chip period, so that the fundamental code duration Ts is defined as Ts = Tc • Lc, corresponding to a symbol-rate of Rs = 1/Ts.
In order to allow synchronization, the number of chips of the fundamental code c0 shall be chosen such that:
Lp = N ⋅ Lc (1)
where N is integer and Tp = Tc. Note that this also ensures that the signal carrying the secure code has the same chipping rate as the open code.
The first step of the supersonic authentication scheme consists of the generation of a fundamental crypto-code c0 that is used as a baseline for a subsequent CSK modulation. This secret code c0 is valid for a crypto-period Tcrypto >> Ts, and is then renewed; the time slots associated with each crypto-period are denoted by j, so that the fundamental code for the j-th slot is denoted by c0(j).
More precisely, the fundamental code is generated for each crypto-period as follows:
c0(j) = Ek₁‚(p,IV(j)) (2)
with Ek₁ being a block cipher (e.g., AES-CBC) indexed with a secret key k1, and IV1(j) representing the initialization vector. Note that (2) takes into account neither the truncation nor the padding that may be required for meeting the synchronization condition (1). Such parameters depend both on the specific block cipher used for the encryption and on Lp. For the sake of readability, in the following discussion, the dependency of the fundamental code on j is omitted in the notation.
From a security perspective, the fundamental code described in (2) ensures that c0 is not known to an adversary who does not have access to the secret key k1. In principle, this should ensure that the attacker is not able to despread the signal. However, as mentioned earlier, the scheme is vulnerable to a coherent integration attack, and this vulnerability is the main driver for the design of the second step.
The second step of the supersonic authentication scheme, in fact, addresses this security issue by leveraging the CSK modulation, that is, by circularly shifting the fundamental code c0 for every time slot of duration Ts (in the following, each of these time slots is indexed with i).
The CSK shift is chosen by means of a cryptographic data authentication function in the symbols modulation. This ensures its unpredictability for the adversary and prevents coherent integration. The alphabet of possible CSK shifts is denoted by δ and is a sampled sub-set of {0,1 … , Lc – 1} with cardinality M; each shift can therefore be uniquely identified by B = log2(M) bits . . .
(For the complete story, including equations and figures, please download the PDF using the link at the top of the page.)
Acknowledgments
The authors wish to thank Dr. José Angel Ávila Rodriguez, Dr. Massimo Crisci, and Dr. Rigas T. Ioannides from the European Space Agency for the fruitful discussions on signal design, Ignacio Fernándex Hernández from the European Commission for the important considerations on data schemes, and Prof. Vincent Rijmen from KU Leuven University for his insightful support on cryptographic features.
Additional Resources
[1] Bellare, M., and R. Canetti, and H. Krawczyk, “Keying Hash Functions for Message Authentication,” Advances in Cryptology, CRYPTO ’96 (Vol. 1109), Springer-Verlag, 1996
[2] Canale, M., and S. Fantinato, and O. Pozzobon, Qascom S.r.l, “Performance Comparison of Different Data Authentication Solutions for the Galileo CS”, in NAVITEC 2014 Conference Proceedings, Noordwijk, Netherlands
[3] Dworkin, M. J., Recommendation for Block Cipher Modes of Operation: the CMAC Mode for Authentication, Special Publication 800-38B, National Institute of Standards and Technology, 2005
[4] Fernández-Hernández, I., “GNSS Authentication: Design Parameters and Service Concepts,” Proceedings of European Navigation Conference GNSS 2014
[5] Garcia-Peña, A., “Analysis of Different CSK Configurations in a Urban Environment When Using Non-coherent Demodulation,” Proceedings of Navitec 2014
[6] Garcia-Pena, A., and D. Salos, O. Julien, L. Ries, and T. Grelier, “Analysis of the Use of CSK for Future GNSS Signals,” 26th International Technical Meeting of the Institute of Navigation Satellite Division, (ION GNSS+ 2013), Nashville, Tennessee USA
[7] Gennaro, R., and P. Rohatgi (1997), “How to Sign Digital Streams,” Advances in Cryptology, CRYPTO’97, 1997
[8] Gennaro, R., and P. Rohatgi (2001), “How to Sign Digital Streams,” Information and Computation, 165(1):100–116, February 2001
[9] Golle, P., and N. Modadugu, “Authenticating Streamed Data in the Presence of Random Packet Loss,” NDSS’01: The Network and Distributed System Security Symposium, 2001
[10] Humphreys, T., “Detection Strategy for Cryptographic GNSS Anti-Spoofing,” IEEE Transactions on Aerospace and Electronics Systems, vol. 49, no. 2, pp. 1073–1090, April 2013
[11] Kuhn, M. G., “An Asymmetric Security Mechanism for Navigation Signals”, in 6th Information Hiding Workshop. LNCS 3200, Springer-Verlag, pp. 239-252, 2004
[12] Merkle, R. C. “Advances in Cryptology — CRYPTO ‘87,” Lecture Notes in Computer Science 293, p. 369, 1988
[13] Miner, S., and J. Staddon, “Graph-Based Authentication of Digital Streams,” IEEE Symposium on Security and Privacy, 2001
[14] Paonni, M., and M. Bavaro, M. Anghileri, and B. Eissfeller, “On the Design of a GNSS Acquisition Aiding Signal,” Proceedings of ION GNSS+ 2013, Nashville, Tennessee USA
[15] Park, J-M., and E. KP. Chong, and H. Siegel, “Efficient Multicast Packet Authentication Using Signature Amortization,” Proceedings of the 2002 IEEE Symposium on Security and Privacy
[16] Perrig, A., and R. Canetti, J. D. Tygar, and D. Song “The TESLA broadcast authentication protocol,” CryptoBytes, Volume 5, No. 2 (Summer/Fall 2002), RSA Laboratories, EMC Corporation, Hopkinton Massachusetts USA
[17] Perrig, A., and R. Canetti, D. Song, and J. D. Tygar, “Efficient and secure source authentication for multicast.” Network and Distributed System Security Symposium, NDSS. Vol. 1. 2001.
[18] Perrig, A., “The BiBa One-Time Signature and Broadcast Authentication Protocol,” Proceedings of the 8th ACM conference on Computer and Communications Security, 2001
[19] Pozzobon, O. (2010), and L. Canzian, M. Danieletto, and A. D. Chiara, “Anti-spoofing and open GNSS signal authentication with signal authentication sequences,” 5th ESA Workshop on Satellite Navigation Technologies and European Workshop on GNSS Signals and Signal Processing (NAVITEC), Noordwijk, Netherlands, 2010
[20] Pozzobon, O. (2014), and G. Gamba, M. Canale, and S. Fantinato, Qascom S.r.l., “Supersonic GNSS Authentication Codes,” Proceedings of the 27th International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS+ 2014), Tampa, Florida USA
[21] Scott, L., “Anti-Spoofing and Authenticated Signal Architectures for Civil Navigation Systems,” Proceeding of ION GPS/GNSS 2003, Institute of Navigation, Portland, Oregon, 2003, pp. 1542–1552
[22] Sun, and G. Bi, Y. Guan, and Y. Shi, “Performance analysis of M-ary CSK Based Transform Domain Communication System,” Proceedings of the 2nd International Conference on Circuits, Systems, Control, Signals (CSCS 2011)
[23] Wullems, C., and O.Pozzobon, and K.Kubik, “Signal Authentication and Integrity Schemes for Next Generation Global Navigation Satellite Systems,” Proceedings of the European Navigation Conference GNSS 2005, Munich, Germany
