Abstract
As time goes on, quantum computing has become more of a reality, bringing several cybersecurity challenges. Modern cryptography is based on the computational complexity of specific mathematical problems; however, as new quantum-based computers are developed, classical methods might not be sufficient to secure communications. In this paper, we analyze the state of the Galileo open service navigation message authentication (OSNMA) to overcome these new threats. This analysis and its assessment have been performed using OSNMA documentation, where we have reviewed the available post-quantum cryptography (PQC) algorithms competing in the National Institute of Standards and Technology standardization process and assessed the possibility of OSNMA implementation in the Galileo service. The main barrier to adopting PQC approaches is the size of both the signature and the key. This analysis shows that OSNMA is not yet capable of facing quantum threats and that significant changes are required. This work concludes by assessing different transitory countermeasures that can be implemented to sustain the system’s integrity in the short term.
1 INTRODUCTION
Galileo is a global navigation satellite system (GNSS) developed by the European Union (EU) to provide positioning and timing information worldwide. Galileo provides Europe with sovereignty over its navigation capabilities, avoiding any dependence on other available GNSSs, namely, the Global Positioning System (GPS) (United States), GLONASS (Russia), and BeiDou (China) (Langley et al., 2017). Galileo is the only GNSS under civil control and, in addition to its well-known open service (OS), which is public and free of charge, offers other innovative services. Regarding security, the most relevant service is the OS navigation message authentication (OSNMA), as currently no other GNSS service offers a similar capability. OSNMA is freely accessible to all Galileo users and protects against spoofing attacks intending to fake the real position and time of the receiver. For this purpose, OSNMA authenticates the data transmitted in Galileo OS navigation messages (I/NAV), ensuring that the data come from the system itself and have not been modified. This authentication is accomplished by transmitting authentication-specific data in previously reserved fields of the I/NAV message.
The OSNMA service is based on two building blocks:
Time-efficient stream loss-tolerant authentication (TESLA) (Perrig et al., 2005): A protocol that enables message authentication via symmetric keys, as long as the keys do not become disclosed in a defined period of time.
Public-key cryptography (PKC): A method for secure authentication of TESLA keys, establishing a root of trust over the long term.
Although the trade-offs of TESLA have been discussed in other works (Neish et al., 2018), the security of TESLA depends on the correct selection of parameters (Fernández-Hernández et al., 2021), and bootstrapping is required via PKC (Fries and Tschofenig, 2006). In this context, the reliability of OSNMA is crucial, as there are plans for OSNMA to support other Galileo services, such as assisted commercial authentication service (Fernandez-Hernandez, Cancela, et al., 2022; Fernandez-Hernandez, Winkel, et al., 2023).
However, with the evolution of quantum computers capable of running algorithms such as Shor’s algorithm (Shor, 1994), “classical” PKC systems (e.g., relying on mathematical problems such as discrete logarithms, integer factorization, etc.) will no longer be secure. In particular, if a future quantum computer is built with the capability to implement these algorithms, the PKC system used in OSNMA (i.e., elliptic curves) would become vulnerable (Chen et al., 2023), putting the whole system at risk (Eledlebi et al., 2022).
All of the dependent symmetric cryptography elements would be weakened by other quantum computing algorithms, such as Grover’s algorithm (Grover, 1996), which is capable of searching preimages in an asymptotic square root time. This situation would arise, for instance, for message authentication code (MAC) functions, whose primitive security (i.e., hash functions) could be degraded to half of their current strength (Preston, 2022).
To face the threats of quantum computing, several entities are developing cryptographic algorithms resistant against quantum adversaries. The most widely recognized standardization process is the post-quantum cryptography (PQC) competition hosted by the National Institute of Standards and Technology (NIST) (National Institute of Standards and Technology, 2017a). Other projects have also addressed the transition to quantum-safe cryptography (Dahmen-Lhuissier, n.d.).
According to Mosca’s theorem (Mosca, 2018), to ensure the security of information systems, one must consider not only the time until the maturity of quantum computers but also the period required for the update of current information systems. It is also important to note that today’s confidentiality of information will also be at risk against the “store-now, decrypt-later” strategy (Joseph et al., 2022). The development of post-quantum capabilities is essential for preventing vulnerabilities in communication networks (Lopez et al., 2022), but this transition is not trivial and raises conflicts over the requirements of information systems, e.g., resource consumption, size of cryptographic data (Westerbaan, 2021), etc. The security of emerging PQC algorithms has not yet been sufficiently tested, and the required changes can collide with current standards.
Furthermore, some applications, such as timestamp digital signatures or certificates emitted by certificate authorities (CAs), should remain trustable for decades. However, the keys employed for these purposes face the risk of becoming insecure within this period. For example, the Global Sign Root CA certificate must remain valid for 30 years, from 1/9/1998 to 28/1/2028, and there exist transport layer security (TLS) root certificates valid up to 2060 (GlobalSign, 2022). The EU has evidenced that space-based development solutions have reached a high level of implementation in society, and their degradation could result in a threat to civil security. Although this risk may seem remote, developing security strategies to address the implications of space-related risks is strategic to achieve resiliency (European Commission, n.d.). This research aims to provide an assessment of options for implementing PQC in Galileo’s OSNMA service, setting a foundation for adopting these findings in other EU space projects.
1.1 Research Questions
The present research aims to answer the following questions:
Is it possible to make OSNMA quantum-resistant, assuming its current design?
What is the maximum size available for a public key in the OSNMA message?
If it stands as a limitation, is over-the-air rekeying expendable?
What is the maximum size available for tags/signatures in the OSNMA message?
Will it be necessary to change the design of OSNMA in a post-quantum scenario?
Could OSNMA be implemented in a full public-key system (e.g., without TESLA)?
1.2 Objectives
The main objective of our work is to analyze the possibilities for implementing secure PQC algorithms in OSNMA and to establish a framework for analyzing and discussing future Galileo system builds and other projects with similar characteristics (e.g., satellite-based, low bandwidth, limited resources, etc.). We aim to accomplish the following:
Review and document the current OSNMA design, as knowledge support for future research
Select OSNMA parameters that would make a cryptographic agility strategy feasible
Identify limitations of PQC implementations regarding satellite communication channels
1.3 Outline
This paper is structured as follows:
Section 2 documents background information related to the Galileo system, the OSNMA service, and PQC.
Section 3 explains the methodology designed to fulfill our objectives and answer our research questions.
In Section 4, we perform an overview of the OSNMA processing logic and the PQC algorithms that are being selected for standardization, to identify the key elements that may impact the transition process.
In Section 5, we analyze the system’s elements, evaluating the characteristics, requisites, and constraints of the OSNMA system.
Section 6 presents a discussion of our results, leading to an assessment of how PQC could be implemented.
Section 7 concludes the document by summarizing our findings and raising open questions that could lead to future lines of research.
2 BACKGROUND
2.1 Galileo
Galileo, the European GNSS program, declared its initial services in December 2016. Since then, the performance of Galileo has been gradually improving thanks to the addition of satellites to the constellation, the evolution of the ground segment infrastructure, and the deployment of new services. Upon completion, users will benefit from its full first-class performance, reliability, and coverage, with the following services (European Union, 2021b):
OS: “Open and free of charge service, interoperable with its other GNSS counterparts (Gaglione et al., 2015), for positioning and timing provision” (EUSPA, n.d.).
OSNMA: “Free access service complementing the OS by delivering authenticated data, assuring users that the received Galileo navigation message is coming from the system itself and has not been modified.”
Public regulated service: “Service restricted to government-authorised users, for sensitive applications that require a high level of service continuity” (Parliament, 2011).
High-accuracy service: “A free access service complementing the OS by delivering high accuracy data and providing better-ranging accuracy, enabling users to achieve sub-meter level positioning accuracy” (Fernandez-Hernandez, Chamorro-Moreno, et al., 2022).
Commercial authenticated service: “A service complementing the OS, providing a controlled access and authentication function to users” (EUSPA, 2024).
Search and rescue service (SAR): “Europe’s contribution to the international satellite-based search and rescue distress alert detection system COSPAS-SARSAT” (Zurabov et al., 1998), which enhances the coverage of the system and includes a return link.
The Galileo OS navigation message I/NAV, described in the signal-in-space (SiS) interface control document (ICD) (European Union, 2021a), is broadcasted through the E1 (E1-B signal) and E5b (E5b-I signal) bands and encoded in the following format (see Figure 1):
Pages are the basic elements of the I/NAV. There are two types of pages, even and odd, which are transmitted every 2 s, with each comprising 120 bits. The OSNMA information is transmitted only in the odd pages of the E1-B signal, specifically via a 40-bit reserved field.
A subframe is transmitted every 30 s and is composed of 15 pages. Each subframe contains a complete OSNMA message.
The full OS message is broadcasted in frames (decomposed into 24 subframes) every 720 s.
2.2 Galileo OSNMA
With OSNMA, Galileo provides an authentication mechanism that can not only validate its own OS messages but can also function for other satellite navigation systems, such as NAVSTAR GPS (Nicola et al., 2021). OSNMA is implemented by taking advantage of the 40-bit reserved field available in the OS I/NAV message, as shown in Figure 2. This cross-validation relies on a hybrid cryptosystem (i.e., using both symmetric and asymmetric cryptography).
The key generation process in TESLA (Perrig et al., 2005) consists of a chain of subkeys derived by a one-way function. These keys feed, in reverse order, a symmetric-key-based authentication function that signs the message. The signing operation in OSNMA is performed using hash-based MACs (HMACs) (Krawczyk et al., 1997), and the resulting MAC is truncated to obtain a short-length tag.
The root key (i.e., the last element derived in the chain generation, as shown in Figure 3) acts as a validation key that is securely distributed at the beginning of a chain period, signed with the public elliptic curve key (Pornin, 2013). This root key is never used to sign messages. Rather, future keys are to be hashed, using the TESLA chain generation algorithm, until the user reaches the root key again. This one-way mechanism prevents present keys from revealing any information that compromises future keys, allowing forward validation.
The elliptic curves used in the current OSNMA implementation are ECDSA P-256 and ECDSA P-521, and the corresponding public keys are verifiable through a Merkle tree publicly available on the program webpage (European Union, 2021c).
2.3 Galileo OSNMA Message
As described earlier, a complete authentication message is split among several OS pages, taking advantage of a reserved 40-bit field. The OSNMA message is documented in its own SiS ICD (European Union, 2022) at both page and subframe levels (i.e., joining 15 pages). This message would be broadcast by several satellites at the same time, but not by the whole constellation.
Each subframe contains two types of OSNMA information, evenly distributed throughout the pages (as shown in Table 4).
Header and root key (HKROOT): Distributes the asymmetric cryptographic material needed to validate authentication information and TESLA keys.
Message authentication code (MAC) and key (MACK): Distributes the information needed to validate the I/NAV and previous OSNMA messages (i.e., TESLA keys).
Therefore, although the information will not be reliable until the validation keys are broadcasted 30 s later, the user would retrieve almost all of the information needed to authenticate the I/NAV.
2.3.1 HKROOT (per subframe)
Every HKROOT message contains, in turn, a data signature message (DSM) block. The DSM will distribute the root key of the TESLA chain in force (DSM-KROOT) or the elliptic curve public keys for its authentication (DSM-PKR). In the “NMA header” (see Table 1), there are two relevant fields: “Chain ID,” which is updated every time the TESLA chain in force changes, and “Chain and Public Key Status” (CPKS), which indicates when there is a change in any cryptographic asset.
The DSM ID field specifies which type of DSM is being broadcasted. To build the complete DSM, several DSM blocks must be retrieved; however, because the DSM block ID parameter that is present in the HKROOT DSM header is 4 bits long, all of the information must be allocated in 16 DSM blocks at most.
On one hand, the DSM-PKR message, with a length of lDP bits (for clarity, Appendix A contains a summary of the variables used in OSNMA), has two fields that are relevant to our study:
NPKT (4 bit): Specifies the new public key type. Only 1, 3, and 4 are assigned; thus, the 13 remaining values, marked as reserved in the ICD, could be used.
NPK (lNPK bit): The actual new public key broadcasted.
On the other hand, the DSM-KROOT (lDK bit) message contains the following information:
HF (2 bit): Hash function used for building the TESLA chain, which could be either SHA-256 or SHA3-256.
MF (2 bit): MAC function used for signing the navigation information, to be chosen between HMAC-SHA256 or CMAC-AES.
KS (4 bit): An integer that specifies lK, i.e., the length of the chain keys. Values from 9 to 15 are reserved, so that they can be used later.
TS (4 bit): An integer that specifies the size of the message signature lT (i.e., tags). Values from 0 to 4 and from 10 to 15 are also reserved.
KROOT (lK bit): Root key of the TESLA chain in force.
DS (lDS bit): Digital signature of KROOT.
The selection of specific algorithms and parameters applied to a message are specified using the MAC look-up table (MACLT) field. This field is present in DSM-KROOT but is not documented here because of its lack of relevance to our study. The strategy specified by MACLT is known as “authentication data and key delay” (ADKD) and is eventually materialized into the MACK message.
2.3.2 MACK (per subframe)
With the cryptographic elements provided by the DSM in our possession, we must now validate the signatures of the navigation message. The information needed for this authentication process is broadcasted within the MACK message. As shown in Table 2, MACK will contain the signatures and keys necessary to validate previous distributed signatures, ensuring, with this delay, protection against spoofing.
The tag section contains nT signatures followed by some metadata. More precisely, each tag would contain the signature (i.e., HMAC) of the part of the navigation message specified, either by KROOT’s MACLT or by a specific ADKD value set up in the tag information field. ADKD indicates whether ephemeris, time, or other data are being authenticated and should be coherent with MACLT. Moreover, the tag contains a field (i.e., data cut-off point) that indicates the elapsed time between the signature and the authenticated data.
Finally, the key is the element used to generate the preceding MACK message signatures. There is usually a delay of one MACK message (i.e., 30 s) between the tags and the key used to generate them. However, a special dedicated ADKD strategy can also be employed, in which the offset consists of 10 subframes to allow for a slow validation (i.e., after 5 min).
2.4 PQC
Cryptographic security relies on the computational complexity of some mathematical problems. This complexity is usually expressed as the asymptotic time required by a computer to solve a problem as the size of the problem grows (e.g., when increasing the number of bits of a number that must be factorized). If the problem cannot be solved in polynomial time, this serves as a proof of hardness that enables its usage for cryptographic algorithms. However, the conventional complexity classes that characterize this hardness are linked to the classical computational paradigm and are not always sufficiently resistant against new quantum-based computers.
To face this threat, there are several mathematical problems that have now proven to present enough complexity against classical and quantum adversaries. A secure algorithm relies on the assumption that breaking its encryption mechanism is equivalent to solving one of these hard mathematical problems. In this sense, the most relevant primitives for our study are the following:
Lattice-based problems: The most prolific approach, in terms of the number of proposed post-quantum algorithms (National Institute of Standards and Technology, 2022), is based on hardness assumptions over discrete vector spaces, e.g., the shortest vector problem, learning with errors, etc. These problems have received attention because of their usefulness in the homomorphic cryptography field (Lyubashevsky et al., 2013).
Hash-based problems: These problems comprise algorithms supported by one-way functions; thus, they are particularly focused on digital signatures. Constraints exist in relation to the number of times that a single key can be used; thus, in some schemes, keeping track of the operations performed is mandatory. Therefore, this family of problems is divided into two categories: stateful and stateless algorithms. The first category has been addressed in a separate competition by NIST (National Institute of Standards and Technology, 2018), and the extended Merkle signature scheme (XMSS) (Huelsing et al., 2018) and Leighton-Micali signature scheme (LMS) (McGrew et al., 2019) were approved as secure post-quantum algorithms. However, in contrast with some stateless proposals, the stateful approaches do not fit with performance requirements, and they have not been included in the PQC competition.
There are also promising families of problems based on multivariate polynomials (for Information Security (Federal Office for Information Security, 2022) and on isogenies of elliptic curves (Galbraith and Vercauteren, 2018). Still, none of the proposals have stood the test of time, and some have even failed against classical computers (Castryck and Decru, 2022).
PQC is used to implement these quantum-resistant problems, and the most acknowledged process of PQC standardization is the process that has been developed by NIST since 2017 (National Institute of Standards and Technology, 2017a). We can segregate this process into two families of algorithms: key encryption mechanisms (KEMs) and digital signature algorithms (DSAs).
Even though new proposals are still being sought (National Institute of Standards and Technology, 2017b), some algorithms have already been selected for standardization (National Institute of Standards and Technology, 2017c). In this regard, the DSAs accepted by NIST are as follows:
CRYSTALS-Dilithium (Bai et al., 2021): Together with its KEM counterpart (i.e., CRYSTALS-Kyber (Avanzi et al., 2021)), this scheme works under the hardness assumptions of lattice-based problems (Lyubashevsky, 2009).
Falcon (Fouque et al., 2020): Based on the well-known lattice scheme NTRU (Hoffstein et al., 1998), this algorithm stands out for its speed and compactness.
SPHINCS+ (Aumasson et al., 2022): This hash-based scheme makes use of Winternitz one-time signatures (Hülsing, 2017) combined with hypertrees to obtain a stateless signature system.
One of the major challenges of these schemes, apart from security, is usability. Although the cryptographic management remains similar to that of classic public key schemes, the size of cryptographic messages (e.g., signatures) has increased and is too large for the boundaries of most current applications.
2.5 PQC Challenges
Replacing classical cryptographic algorithms with new quantum-resistant algorithms is not a trivial task. Regardless of the standardization and testing process, once an algorithm proves to be reliable, there is always the possibility of finding new vulnerabilities. The mathematical areas of the current proposals are too complex for a wide understanding; thus, their audit is restricted to certain individuals with a strong mathematical background. For this reason, the consensus proposes the use of hybrid approaches (Stebila et al., 2023) (i.e., combining classical and PQC schemes) and the implementation of a dynamic selection of algorithms in the protocols, referred to as “cryptographic agility” (Ott et al., 2019). Moreover, regardless of the initiatives for avoiding implementation failures, especially related to the selection of parameters (e.g., CIRCL (Faz-Hernández and Kwiatkowski, 2019), Open Quantum Safe (Open Quantum Safe, n.d.), etc.), one must consider that other types of issues, such as side-channel attacks (Lou et al., 2021), could arise.
However, the main challenges of the transition to PQC are related to fitting the cryptographic elements into the protocols most commonly used today. The cryptographic elements proposed in PQC algorithms are significantly larger than those in the old protocols (Westerbaan, 2021), and not all network protocols support these elements, e.g., the use of the “maximum segment size” or “maximum transfer unit” fields of the transmission control protocol (TCP) (Celi, 2022), the fields in X. 509 public key certificates (Boeyen et al., 2008), etc.
Computational resource consumption is another element to consider when implementing PQC in a server, as the demands of multiple clients must be met in a finite time. Some researchers have addressed the implementation of PQC in the internet’s building blocks (Stebila and Mosca, n.d.) and the most commonly used secure protocols, such as TLS (Stebila et al., 2023) or secure shell (SSH) (Sikeridis et al., 2020), validating the suitability of standardized PQC algorithms but always focusing on endowing the protocols of cryptographic agility through hybridization on cryptographic controls. From the industry side, Google and Cloudflare have conducted experiments in this regard, showing that it is feasible to implement PQC in public-testing environments (Kwiatkowski and Valenta, 2019).
In the field of key exchange, alternative approaches are available, such as quantum key distribution (Alvaro et al., 2022; Ntanos et al., 2023), but currently, the software transition is a priority (for Information Security (Federal Office for Information Security, 2022). Particularly in the establishment of security parameters for tunneling a connection (e.g., IKEv2 on IPsec, one of the most powerful enabler protocols for building secure architectures), there exist successful proposals for implementing PQC (Pazienza et al., 2022).
3 METHODOLOGY
This assessment requires the analysis of several technologies and documents that cover diverse areas of the OSNMA system: from the highest levels of the protocol, to the roots of the cryptographic primitives. To perform our study, the next steps will be followed:
Develop an analysis of the relevant fields of the OSNMA message, to detect which fields could suffer the most impact due to the implementation of PQC. For this task, we will analyze the official documentation for both OS and OSNMA, particularly the OSNMA SiS ICD (European Union, 2022). Aligned with the first research objective, this task allows us to identify the OSNMA message fields susceptible to holding PQC material and to answer research questions 1(a) and 1(b).
Review available PQC algorithms and their characteristics. Once we have identified which algorithms have been formally tested and are widely accepted, we will analyze the technical specifications of each algorithm. This process allows us to obtain the basic information necessary to evaluate how the algorithms fit in the previously analyzed ONSMA fields, covering the second research objective.
Relate the results of the previous analysis steps to perform an assessment and discuss the key findings that lead to conclusions about how PQC can be implemented, or not, within the current design of OSNMA. This step will cover the third objective of the present paper and provide answers to research question 2.
4 TRADE-OFFS
4.1 OSNMA Characteristics
Evaluating the different approaches available for implementing PQC at OSNMA requires previous analyses of the authentication life cycles, considering the constraints to which they could be subjected. The process for authenticating navigation messages has a different life cycle (see Figure 5) depending on the cryptographic material of interest, namely, the Merkle tree, elliptic curve, TESLA key chain root key, and TESLA key.
At the beginning of the OSNMA project, 16 elliptic curve key pairs were generated. These keys, which, in nominal conditions, should never be changed, act as leaves for building the Merkle tree. If an incident requires the keys to be revoked, there is a mechanism for notifying the clients through the SiS, using a CPKS special value.
Both the Merkle tree and elliptic curve keys can be retrieved from the Galileo Service Centre (GSC) portal, as shown in Figure 6. Whereas the Merkle tree must be installed manually into the receivers (i.e., navigation devices), the elliptic curve keys would be distributed through the SiS.
When the elliptic curve keys are broadcasted over the air, into the DSM-PKR message, they can be validated using the previously downloaded Merkle tree information. This dissemination occurs every 6 h, for a duration of 30 min. The elliptic curve keys can be in force for several years, and when they must be updated, this update is indicated in the CPKS field.
Once the public key material is generated, the basis for the symmetric key authentication is set up. With a minimum period of once per day and a maximum of once per hour, a new TESLA key chain is generated and the change is also informed by the CPKS. The new key chain root key is distributed into the DSM-KROOT message, being signed with the elliptic curve key in force.
Depending on the ADKD value, part of the navigation message is signed using HMAC (or the function specified at that time point) and the correspondent key K from the TESLA chain, as illustrated in Figure 5. The signature is truncated to fit lT and distributed into a MACK message. This key K, used for generating the signature, is distributed in the subsequent MACK message 30 s later. Finally, any Ki can be verified using another Kj that had been previously authenticated (i.e., following the key chain) until the key chain root key is obtained.
Thus, as the constraints present in ONSMA are mainly motivated by the bandwidth, at the time of this analysis, there are two main aspects to consider: the size of the keys and the duration that they remain in the SiS (i.e., periodicity, the sum of necessary messages to encode all of the data, etc.). Table 3 provides a summary of these elements to clarify our later discussion.
4.2 Cryptographic Specifications
Depending on the desired level of security confidence, among other considerations, the parameters of cryptographic primitives can be tuned. Although, in some cases, the selection of these parameters is related to mathematical properties (Rivest and Silverman, 2001; Steinfeld and Zheng, 2004) or implementation techniques (Nemec et al., 2017), the last step usually moves the discussion to a trade-off between security and size.
The current system uses two different public key algorithms to sign the TESLA root keys, which are both based on elliptic curve cryptography: ECDSA P-256/SHA-256 and ECDSA P-521/SHA-512. The security of these algorithms relies on two NIST-selected curves (i.e., P-256 and P-521), and depending on the selection, the length of the signature is 512 or 1056 bits, respectively. This signature is settled in the digital signature field of the DSM-KROOT message.
On the PQC side, all of the algorithms selected by NIST, and the vast majority of proposed algorithms, suffer from the same problem: both the signature and public keys are larger than their classic counterparts. The documentation of NIST finalists specifies their parameters attending to NIST security levels (National Institute of Standards and Technology, 2016). For each of the previously referenced algorithms, Table 4 shows the minimum size requirements of their least-demanding specification, namely, Dilith2 for the NIST level-2 approach of Dilithium, Falcon-512 for Falcon level 1, and SPHINCS+-128s for the SPHINCS+ security-level-1 parameter set.
On the other side, the stateful hash-based alternatives have even larger sizes, either for the signature or the public keys. Although this family of algorithms has been recognized by NIST as secure against quantum computers, the management complexity necessary to achieve security using these algorithms discourages their use and has led to their standardization in an independent project (National Institute of Standards and Technology, 2018). Regardless of their security level, for illustrative purposes, Table 5 presents the parameter combinations that achieve shorter signatures and keys in XMSS and LMS schemes.
4.3 Synthesis Recapitulation
In Figure 7, we aim to provide the reader with a high-level view of how ONSMA operates. This figure illustrates the cryptographic relation between the most important elements of the NMA: the navigation data, the HMAC tag that authenticates these data, the TESLA key used to generate HMAC tags, the TESLA root key that validates all of the TESLA chain, and the public key used to authenticate the TESLA root key. A security breach in the I/NAV authentication protocol is feasible at three key points:
Authentication Tag
The navigation message is distributed with an authentication tag, which allows one to verify that the navigation data have been generated in a genuine satellite. A vulnerability in the function used to sign the navigation data, both in the implementation and the relying hash function, would lead to a collision. The current implementation relies on the fact that a user will receive the signed navigation message before an adversary obtains the signing key so that a spoofing attack can be detected. However, if these tags are not sufficiently long, an exhaustive attack (i.e., where a fake message with several tags is sent until a collision is found) may be possible. These tags also do not protect against meaconing or offline recordings.
TESLA Chain
Each authentication tag consists of generated hashing navigation data with a key. This key is not distributed along with the tag but in a later message. As Figure 3 shows, a user can verify that any key is part of the current TESLA chain by using the TESLA derivation function well until a previously known key or the proper TESLA root key is found. A vulnerability in the TESLA chain generation would imply a vulnerability of the hash function in use.
PKC
Finally, TESLA bootstrapping authenticates the root key using PKC in two steps: (1) an elliptic curve public key authenticates the TESLA root key, and (2) this public key is authenticated by a Merkle tree. Consequently, a failure in the PKC component would imply a failure of the entire authentication process. An eventual quantum or classical computing vulnerability in PKC would make feasible the distribution of false public keys (i.e., if a vulnerability was found in the Merkle tree cryptography) or would give an adversary access to the elliptic curve private keys, allowing the adversary to create false TESLA key chains.
5 ANALYSIS
Although there is still room for scientific contributions (Hosoyamada and Sasaki, 2018), the quantum algorithms available for breaking the security of symmetric key schemes do not currently represent a threat. Merkle tree cryptography relies on hash-based principles and thus is also safe against quantum computers (Buchmann et al., 2008). However, elliptic curves would be deeply vulnerable to Shor’s algorithm, acting as a link that would risk the entire authentication chain. If an adversary had access to a stable quantum computer with enough resources to implement Shor’s algorithm, the adversary could retrieve OSNMA private keys from the public keys. Novel research has also addressed the implementation of this algorithm over noisy equipment (Gidney and Ekerå, 2021). This would lead an adverary to forge a navigation message that would be valid in terms of authentication, placing users in a spoofing-risk scenario.
Regarding the taxonomy proposed by Celi (2022), the main challenge for OSNMA is the limited available bandwidth and the implications it would have if a user had to wait for a larger key or signature. Additionally, a major change in the protocol or the fields of the message would render inoperative many critical or embedded devices that make use of OSNMA but cannot be easily updated. Thus, any proposed upgrade must fit with the current configuration of the SiS.
Finally, in the absence of specific requirements, the computational overload of the cryptographic operations is not a major concern for system performance. The main issue in the protocols documented earlier (e.g., TLS, SSH, etc.) is that the servers act as meeting points of several clients at the same time, but the satellites’ workload does not depend on the number of receivers.
Regarding cryptographic agility, the use of new cryptographic methods raises additional risks. As discussed in Fernandez-Hernandez, Hirokawa, et al. (2023), vulnerabilities due to a lack of testing or even failures in the implementation can emerge over these novel approaches. Through cryptographic agility, these risks can be mitigated. This mitigation can be accomplished by designing the systems so that they can dynamically switch the set of algorithms and cryptographic primitives in use. To achieve this goal in OSNMA, the NPKT field of the DSM could be used, assigning the currently free values (i.e., 0, 2, and 5–15) to different combinations of algorithms.
The most popular approach for achieving cryptographic agility is hybridization (i.e., combining and overlapping classic and quantum-resistant algorithms), but the key point in OSNMA is the optimization of the bandwidth. Here, the constraint is that any proposed algorithm must be characterized and mapped with the currently available fields of the message. For this reason, the size of the new public keys is relevant, but the size of the TESLA root key signatures is more important. Whereas the public keys are rarely updated and can ultimately be sent by other means (e.g., over the internet), the TESLA root keys are updated frequently.
As Figure 8 shows, PQC keys are quite large compared with classical approaches (e.g., the larger RSA approach recommended by NIST is 3072 bits long (Barker and Dang, 2015)). With regard to key and signature sizes, the average smallest PQC implementation is Falcon, which almost doubles the key size compared with its elliptic curve predecessors. SPHINCS+ keys are shorter than any other keys, but this approach has an issue with signatures.
As shown in Table 4, SPHINCS+ signatures are approximately 238 times larger than ECDSA P-264 signatures; thus, for clarity, these signatures are not included in Figure 9, where both elliptic curve and PQC signatures are presented. Regarding signatures, Falcon is again the best quantum-resistant approach in terms of size, yet its signature is nearly five-fold larger than that of ECDSA P-521. Moreover, the Falcon keys exceed the ECDSA P-521 keys by approximately 13-fold.
6 DISCUSSION
Considering the OSNMA design, there is the option of taking advantage of the 13 free values of the NPKT field of the DSM-PKR message to implement several authentication schemes. Therefore, it is unnecessary to modify the protocol to provide cryptographic agility.
A cryptographic failure could allow an adversary to take advantage of the users’ confidence in the genuine system: even though the presence of the Merkle tree signature ensures the authenticity of elliptic curve keys, if these keys were broken by future quantum techniques, a new fake TESLA chain could be generated and loaded in the users’ devices through the DSM-KROOT message, for at least an hour.
Besides these two general findings, two specific findings have also been obtained as explained below.
6.1 TESLA Implementation Drawbacks
The MACK message contains several tags that authenticate different parts of the message and even cross-authenticate the information of other GNSSs. Because the bandwidth is limited, sending more than one tag has the following drawbacks: a) it enforces the truncation of the tag, weakening the signature, and b) it limits the likelihood of implementing other approaches (e.g., public-key-based signatures). In particular, as argued in Section 4.3, the possibility of setting tag lengths to 20 bits raises many concerns about the feasibility of an exhaustive search attack (i.e., brute-force search until a valid tag is found for a false message).
Regarding quantum resistance, the implementation of Grover’s algorithm could weaken the hash algorithms, allowing the complete TESLA key chain to be retrieved from the root key. Nevertheless, this algorithm is not as effective against symmetric cryptography, as Shor’s algorithm works against asymmetric cryptography; thus, doubling the key length would neutralize quantum adversaries.
If the space reserved for several tags was reserved only for one public key signature, the approach would be less versatile but more secure, and the message could be self-authenticated without depending on information from a future message. There are several fields, such as the HF or MF of the DSM-KROOT message, which would not be necessary if the full system were implemented via PKC (i.e., without TESLA). Any change in the protocol should take this fact into account, as it could allow one to improve the bandwidth.
In addition, it must be noted that the open distribution of TESLA keys makes them inappropriate for other long-term uses not related to live navigation. For instance, any process based on analyzing a signal recording (e.g., to authenticate logs recorded in a digital tachograph) would be vulnerable to a forged signal with false navigation data.
6.2 PQC Implementation
Given the criticism of PKC in the OSNMA protocol, as analyzed in Section 4.3, and the presence of algorithms susceptible to being broken by quantum computers (e.g., elliptic curves), the PQC transition should be prioritized. According to the literature (Sosnowski et al., 2023), we should focus on the bandwidth, as the performance should not decrease.
The fourth round of the NIST PQC competition includes the evaluation of KEM algorithms; thus, the standardization of a new quantum-resistant DSA is not foreseeable in the short term. Therefore, even while NIST considers other algorithms, the characterization documented in Section 2.4 will remain valid.
Stateful hash-based algorithms are not valid for the system because of signature size issues. It would be possible to use the XMSS configuration documented in Table 5 for the message signature, as it would be only four times longer than the current elliptic curve signatures. However, as a stateful hash-based algorithm, its public keys must be updated frequently, and the time needed to transfer that GB of data over the air would be unacceptable.
6.3 Assessment Conclusion
In conclusion, the most suitable algorithm for replacing elliptic curves would be Falcon. However, Falcon’s elements do not meet the requirements for transmission over the air, for the distribution of public keys, or for the broadcasting of signatures. Starting from the assumption that the 4-bit field reserved for the DSM block ID (which admits the transmission of only 16 DSM blocks, each with a length of 104 bits), we have 1664 bits available for the two following use cases:
Use case 1: Transmission of new public keys in DSM-PKR
Discarding the 16 bits of metadata, 1632 bits are available for cryptographic material. As the Merkle signature fills 1024 bits, there are 608 free bits for the public key (i.e., 32 bits per DSM block). Currently, the Merkle signature is the lightest quantum-resistant signature that can be implemented. If we dispensed with the Merkle signature, we would save 10 DSM blocks, but we would lose the possibility for authenticating new public keys. The shortest Falcon public keys take 7176 bits, and thus, they would need 71 DSM blocks to be transmitted.
Use case 2: Signature of the TESLA root key in DSM-KROOT
Using the larger TESLA keys, which are 256 bits long, and discarding the 104 bits of metadata, the maximum space available for the data signature field (i.e., the field that holds the TESLA root key signature) would be 1727 bits, corresponding to 79 bits per DSM block. As the shortest Falcon signature is 5328 bits long, 67 DSM blocks would be needed to cover the full authentication.
To increase the size of the public key (i.e., lNPK), it would be necessary to increase the number of blocks that comprise the DSM-PKR, which would also impact the bits necessary to identify these blocks at the DSM header. The same situation arises for increasing the signatures of DSM-KROOT. The only feasible solution would be to enlarge the block ID to 7 bits, with the possibility of sending DSMs up to 13312 bits long, so the 4 bits needed to extend the block ID could be subtracted from the DSM block itself. However, in this case, the transmission of the complete message would last 142 s instead of 30 s; moreover, as this transmission is performed at the DSM, it will not have any overload for authenticating the navigation data, transmitted through the MACK message.
In any case, the transmission of digital signatures (i.e., the data signature of DSM-KROOT) must be prioritized over the public keys themselves (i.e., NPK at DSM-PKR). The TESLA digital signatures are sent frequently, whereas the public keys do not usually change and can be updated using out-of-band channels, such as the internet. However, in a full PQC approach, i.e., where the navigation message is signed using PKC instead of TESLA, there would also be an impact on the MACK message, making it longer.
In conclusion, the only quantum-resistant approach that is currently feasible, without a need to modify the OSNMA SiS specification, is out-of-band message authentication. The transmission of large signatures or public keys (i.e., belonging to the documented PQC algorithms) could be performed through the internet or alternative channels, as is currently done with the Merkle tree, so there could exist a reliable source for validating navigation messages. Receivers would perform the authentication as before, but using the new PQC schemas. Although authentication would not be implemented in disconnected devices, this approach could open the door to mitigate cryptographic risks in connected devices.
7 CONCLUSION AND FUTURE WORK
In this paper, an analysis of the OSNMA authentication procedures has been developed to provide an assessment of how these procedures can be made quantum-resistant. We have analyzed both OSNMA specifications and the current state of the art of PQC, providing, as an indirect contribution, a well-documented summary of the entire OSNMA authentication process from different perspectives. This analysis has led to findings related to weaknesses of the system, such as those related to TESLA implementation.
Our study reveals that although the current OSNMA design has elements that could enable cryptographic agility, it is not ready for implementing the currently available PQC algorithms. One of the most critical points is the size of the new keys and signatures, which would slow down key distribution, but not the authentication process, as it is performed using TESLA. However, the data fields available in the current system do not have enough capacity (Shannon, 1956) to cover the number of messages necessary to broadcast these new elements. Although this approach could be applied with some slight changes, these modifications might be highly disruptive for the current requirements of Galileo and would thus be unfeasible.
Nevertheless, until major changes can be performed in the system, there exist alternatives for mitigating quantum risks. For instance, some signatures could be delivered to receivers by an alternative channel (e.g., over the internet). In addition, although the state of standardization processes must still be considered, new PQC algorithms that are more efficient in terms of size could be developed in the near future.
In any case, a transition to a quantum-resistant design is needed. If such a transition is not implemented within a few years, as stated by the National Quantum Programs (Petrenko et al., 2021), this would pose an unacceptable risk for the system and result in the de facto nullification of OSNMA.
This research opens the door to new research on PQC implementation and on the prevention of flaws detected in the current design:
Any change in the state of the art of PQC could provide opportunities for implementing a quantum-resistant scheme following the characterization performed in our study. Furthermore, the assessment of algorithms not covered by the NIST competition or dismissed for reasons not related to size or security requirements could also provide valid alternatives.
Although the TESLA approach is a clever method for overcoming the Galileo bandwidth limitations, as it has been already exposed, TESLA introduces weaknesses in the system, and findings regarding the signing key can be a barrier for use cases in which long-term authentication is necessary (e.g., when authenticated audit logs must be preserved (Baldini et al., 2018)). Therefore, replacement by a full quantum-resistant public key system should be assessed.
Some OSNMA configurations seem to be insufficient to provide a robust authentication (e.g., the 20-bit tags could be found through brute force). Research in this direction could help to clarify the level of risk entailed by this issue.
HOW TO CITE THIS ARTICLE
Junquera-Sánchez, J., Hernando-Ramiro, C., Gamallo-Palomares, O., & Gómez-Sánchez, J.-A. (2024). Assessment of cryptographic approaches for quantum-resistant Galileo OSNMA. NAVIGATION, 71(2). https://doi.org/10.33012/navi.648
APPENDICES A OSNMA VARIABLES
Table 6 presents a summary of the OSNMA variables used in this article.
This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited.