Introducing GNSS Navigation Message Authentication

Please note that OSNMA functionality is currently available only in the next branch of the upstream repository and will be included in the next stable release of GNSS-SDR.

GNSS signal spoofing has become a frequent and concerning issue, particularly in regions experiencing military conflicts. This phenomenon can be monitored through various online platforms that use ADS-B data to detect and display, in near-real time, instances of aircraft being jammed or spoofed worldwide. In such scenarios, GNSS signal authentication is crucial for mitigating the effects of spoofing. This can be achieved by detecting spoofed signals at various stages of the signal processing chain, depending on the service provided by the system operator and the user’s receiver. If spoofed signals are detected, the receiver can respond by either issuing appropriate warnings to the user or excluding non-authenticated satellite signals from the computation of Position, Velocity, and Time (PVT) solutions.

Galileo, the European GNSS, is currently testing its Open Service Navigation Message Authentication (OSNMA) service. OSNMA is designed to provide a secure, spoof-proof communication channel between satellites and receivers. This service transmits authentication data within the Galileo E1 I/NAV messages, alongside the navigation data used by receivers to compute PVT solutions. By incorporating OSNMA, the resilience of GNSS receivers to spoofing attacks is significantly enhanced, since they can detect spoofed signals and act upon that event.

OSNMA makes use of different keys from a single one-way chain shared by the Galileo satellites through a Timed Efficient Stream Loss-tolerant Authentication (TESLA) protocol.¹

The main idea of the TESLA protocol is that the sender appends a message authentication code (MAC) to each data packet, computed using a key \(K\) known only to the sender. The receiver buffers the received packet without being able to authenticate it immediately. Shortly afterward, the sender discloses \(K\), allowing the receiver to authenticate the packet.

The OSNMA service takes a similar approach: in each I/NAV navigation data subframe of the Galileo E1 OS signal (that is, every 30 seconds), a subset of satellites insert predefined sequences of truncated message authentication codes, which are computed with an undisclosed key \(K_{N}\) and the data to be later authenticated. These truncated message authentication codes are known as tags, and are generally defined as:

where \(\textit{trunc} \left( L, I \right)\) is the truncation function retaining the \(L\) most significant bits (MSB) of the input \(I\), and \(\textit{mac} \left( m, K \right)\) is the MAC function used for the current TESLA key chain, applied to message \(m\) and with key \(K\). The key \(K_{N}\) remains unknown to the receiver at the reception time. In the next subframe (or ten subframes later in some cases), satellites send the key \(K_{N}\) along with the means to verify its authenticity. The receiver can then compute the tags with the previously received data and the newly received key. If they match the received associated tags, the data can be declared authenticated, and hence the GNSS products derived from them, such as Position, Velocity, and Time. This authentication mechanism can refer to the navigation data broadcast by any of the Galileo satellites, even if they are not in the subset broadcasting OSNMA data.

The OSNMA data is broadcast across multiple Galileo satellites, with messages sliced and sent in no predefined order, requiring the receiver to combine the received data from several satellites in order to effectively implement the service. Consequently, the proposed software architecture includes a processing block that asynchronously collects the OSNMA data received from all available Galileo E1 OS processing channels. This block then combines and processes the OSNMA data, and asynchronously transmits the list of authenticated satellites to the PVT computation block, which, based on user configuration, either warns the user or excludes unauthenticated satellites from the PVT solution computation.

Block diagram of the OSNMA integration into the GNSS-SDR flow graph.

From the user perspective, the required steps involve registering and logging on the European GNSS Service Centre website to download the necessary OSNMA Public Key and Merkle Tree root files. The required files are under GSC Products > OSNMA_Publickey (the required file ends with .crt, at the time of writing this note it is named OSNMA_PublicKey_20240115100000_newPKID_1.crt) and GSC Products > OSNMA_Merkletree (the required file ends with .xml, at the time of writing this note it is named OSNMA_MerkleTree_20240115100000_newPKID_1.xml). Once downloaded, the user can set their paths in the GNSS-SDR configuration file:

GNSS-SDR.osnma_public_key=./OSNMA_PublicKey_20240115100000_newPKID_1.crt
GNSS-SDR.osnma_merkletree=./OSNMA_MerkleTree_20240115100000_newPKID_1.xml

The GNSS-SDR receiver can be configured with options such as OSNMA disabled, enabled with warnings, or strict authenticated-only PVT fixes. By default, the ONSMA operation in configured as enabled with warnings if there are channels devoted to the Galileo E1 OS signal (named 1B in GNSS-SDR terminology). This can be disabled by setting:

GNSS-SDR.osnma_enable=false

The strict mode (that is, PVT fixes are computed exclusively from authenticated signals) can be activated by setting:

GNSS-SDR.osnma_mode=strict

Check out the documentation about the OSNMA configuration parameters in GNSS-SDR for more information.

Extraction of OSNMA data from signals in space

According to the Signal-In-Space Interface Control Document,² the Galileo OSNMA protocol data are transmitted within the odd pages of the nominal E1-B I/NAV message. The bits are placed in previously reserved positions:

E1-B I/NAV Nominal Page with bits allocation (from OSNMA SIS-ICD²).

OSNMA data are distributed only by a subset of the Galileo satellites. If a satellite is not part of the above-mentioned subset, the I/NAV OSNMA message will contain a 40-bit sequence of zeros.

The OSNMA field has the following structure:

OSNMA data message (from OSNMA SIS-ICD²).

• The HKROOT (header and root key) section is an 8-bit portion of a 120 bits long message, which is transmitted once every 30 seconds, i.e. within each E1B I/NAV sub-frame. The HKROOT message begins always with an 8-bit NMA Header field, followed by a 112-bit Digital Signature Message (DSM) field, consisting of a DSM Header, followed by a DSM block:

  HKROOT Message (from OSNMA SIS-ICD ²).

  Several DSM blocks, transmitted through successive subframes, form a complete DSM. Different satellites can transmit different blocks of the same DSM at a given sub-frame.

  There are two different types of DSM:

  • DSM-PKR, providing the Public Key for the verification of the root key of the TESLA chain. The Public Key in force, together with its ID and signature algorithm, is provided in the DSM-PKR message every 6 hours (starting at 00:00 GST, 06:00 GST, 12:00 GST and 18:00 GST) for a period of 30 minutes. If the Public Key has not been provided by the user in the GNSS-SDR.osnma_public_key configuration parameter, the receiver will retrieve it from the signals in space.
  • DSM-KROOT, providing a digitally signed root key for the TESLA chain in force, or the one of the next chain, and the means to authenticate those keys using the Public Key in force.

• The MACK (message authentication code and key) section is a 32-bit portion of a 480 bits long message, which is transmitted once every 30 seconds, i.e. within each E1-B I/NAV sub-frame. Each MACK message contains several truncated Message Authentication Codes, or tags, with specific information data associated (Tag-Info), and a TESLA key.

  MACK Message (from OSNMA SIS-ICD²).

Therefore, a 120-bit HKROOT message and a 480-bit MACK message are transmitted every 30 seconds. Both HKROOT and MACK messages are split into 15 portions of equal size (8 or 32 bits) and transmitted within each 40-bit OSNMA data message.

In OSNMA, the MAC algorithm used to authenticate the plain text navigation message can be either HMAC-SHA-256³ or CMAC-AES⁴, the former being used in the Testing phase. The TESLA keys belong to a chain that begins with a random seed key \(K_N\), known only to the sender (in this case, the OSNMA provider), and ends with a root key \(K_0\) that is public and certified through the DSM-KROOT messages. A TESLA key \(K_N\) can be verified against the root key \(K_0\) by computing \(F^N(K_N)\) and comparing the result with \(K_0\). In OSNMA, the function \(F(\cdot)\) is defined in the ICD².

TESLA key chain, where \(K_{n} = F(K_{n+1})\).

The TESLA root key \(K_{0}\) retrieved from the DSM-KROOT message is verified using an Elliptic Curve Digital Signature Algorithm (ECDSA)⁵, by signing the data with a private key known only to the OSNMA provider and verifying it at the receiver with a public cryptographic key. That ECDSA Public Key can be either retrieved from the European GNSS Service Centre website and passed to GNSS-SDR via the GNSS-SDR.osnma_public_key configuration parameter, or from the Signal in Space broadcasted by Galileo satellites. The Public Key in force, together with its ID and signature algorithm, is provided in the DSM-PKR message every 6 hours for a period of 30 minutes, mixed with other DSM-KROOT messages. The receiver must authenticate this reception against a Merkle Tree root \(x_{4, 0}\) (see figure below), using the same hashing algorithm that was employed for tree generation, currently SHA-256⁶. In the future, the system may adopt SHA3-256⁷.

OSNMA Merkle Tree (from OSNMA SIS-ICD²).

Some nodes of the Merkle Tree (among them, the root node \(x_{4, 0}\)) can be retrieved from the European GNSS Service Centre website and passed to GNSS-SDR via the GNSS-SDR.osnma_merkletree configuration parameter. Note that a renewal of the Merkle tree is expected to take place very rarely, typically after more than 10 years, so GNSS-SDR already comes with pre-loaded values that are used in the case that GNSS-SDR.osnma_merkletree is not defined.

Processing of the authentication material

The authentication concept is based on two main principles:

• The use of different keys from a single one-way chain shared by the Galileo satellites through a Timed Efficient Stream Loss-tolerant Authentication (TESLA) protocol.

• The possibility to authenticate satellites which do not transmit OSNMA with the data retrieved from satellites transmitting OSNMA, referred to as cross-authentication.

From a receiver perspective, the process of the OSNMA data can be described at a high level by the following steps:

• The receiver retrieves the navigation data and the corresponding OSNMA data (tag, TESLA chain key and TESLA root key). The tag authenticates the navigation data and is received before its associated TESLA chain key.
• The TESLA root key is authenticated by means of its digital signature using a Public Key that must be available at the receiver.
• The receiver authenticates the TESLA chain key with the TESLA root key or with a previously authenticated key from the TESLA chain.
• The receiver re-generates locally the tag with the verified TESLA chain key and the data, and checks whether it coincides with the received tag.

If the result of all these steps is successful, the user can consider the navigation data as authentic. ⁸

OSNMA processing logic (from the OSNMA Receiver Guidelines⁸).

OSNMA defines different Authentication Data & Key Delay (ADKD) types. Each type authenticates different parts of the I/NAV data transmitted by satellites which is used to generate the associated tag. A tag is defined as a truncated Message Authentication Code. The currently defined types (others could be defined in future versions of the ICD) are:

• Tag ADKD=0 - Galileo I/NAV Ephemeris, Clock and Status: The tag authenticates I/NAV data transmitted in the previous I/NAV sub-frame. The data authenticated are Word Types 1 to 5, retrieved from either E1-B or E5b-I, including: IODnav, Ephemeris, SISA(E1,E5b), SVID, Clock correction, Ionospheric correction, BGDs, HS and DVS flags.

• Tag ADKD=4 - Galileo I/NAV Timing Parameters: The tag authenticates the I/NAV data from the Word Type 6 transmitted one sub-frame earlier and the Word Type 10, transmitted one or two subframes earlier (retrieved from E1-B only). The data authenticated include GST-UTC conversion parameters (Word Type 6) and GST-GPS conversion parameters (Word Type 10).

• Tag ADKD=12 - Slow MAC - Galileo I/NAV Ephemeris, Clock and Status: The tag is generated as per ADKD=0 definition but using a key that is published with an additional 10 sub-frames delay (5 minutes).

The possible sequences of transmitted tags (either for self-authentication or cross-authentication of satellite data) are predefined in a look-up table. In those sequences, some slots are fixed, and others are flexible (not defined in the look-up table) and its content definition (which is found in the Tag-Info data) needs to be authenticated through the corresponding TESLA key.

The truncated Message Authentication Codes, or tags, with specific information data associated (Tag-Info), and the TESLA key are conveyed in the MACK messages described above. Looking into their structure in more detail, there is a MACK header defined as:

MACK message header (from OSNMA SIS-ICD²).

The \(\text{Tag}\_{0}\) field contains a tag obtained by truncating a MAC of type ADKD=0 for the satellite transmitting the OSNMA data, and it is always the first tag of the MACK message. THE MACSEQ field allows the receiver to authenticate the Tag-Info field for the tags whose ADKD type is identified as flexible, and the Data Cut-Off Point (COP) indicates the maximum time lag between the tag and the navigation data it authenticates.

The next field in the MACK message is Tags&Info, defined as a sequence of tags and their corresponding Tag-Info data:

MACK message’s Tags&Info field (from OSNMA SIS-ICD ²).

The tags are obtained by generating a certain MAC, following the specific information within the Tag-Info field, and then truncating it (starting from the MSB) to the length defined by the Tag Size field within the DSM-KROOT of the chain in force.

MACK message’s Tag-Info field (from OSNMA SIS-ICD ²), where the \(\text{PRN}\_{D}\) field identifies the satellite transmitting the navigation data which is authenticated by the tag.

A possible example of received tag sequence, spanning two MACK messages, is:

00S, FLX, 04S, FLX, 12S, 00E, 00S, FLX, 00E, 12S, 00E, 12E

where the first 2 characters define the ADKD and the last character means S for self-authentication, or E for Galileo cross-authentication. For example, 12S means ADKD=12, self-authentication; and 00E means ADKD=0, Galileo cross-authentication. The slots marked as FLX are flexible, as they are not fixed in the look-up table, and their Tag-Info data required to generate them are authenticated via the MACSEQ field.

The OSNMA-equipped receiver must store these sequences of tags. In the next sub-frame (or ten sub-frames later for ADKD=12), it will receive the TESLA key that allows it to compute the MAC and, consequently, the tags. The receiver can then compare the computed tags to the received sequence. If they match, the received data can be declared authenticated.

Implementation of cryptographic functions in GNSS-SDR

The OSNMA protocol requires two secure hash standards (SHA-256 and SHA3-256), two message authentication code functions (HMAC-SHA-256 and CMAC-AES) for tag verification, and two Elliptic Curve Digital Signature Algorithms (ECDSA P-256 and ECDSA P-521) for verifying the TESLA root key, with only one option from each category used at a time. During the testing phase, only SHA-256, HMAC-SHA-256, and ECDSA P-256 are employed, but the others may be utilized in the future.

Implementing cryptographic functions from scratch in C++ is often unnecessary and inefficient. Instead, leveraging well-known, reliable, and actively maintained open-source libraries ensures more robust and secure implementations. These libraries undergo continuous testing and updates, benefiting from scrutiny by a large, diverse user base. In the GNSS-SDR implementation, the goal was to enable the OSNMA service across the widest possible range of hardware and software environments, covering diverse setups such as embedded SoC/FPGA-based platforms, the Raspberry Pi 5, older or less powerful x86-64-based personal computers, and even Apple’s cutting-edge M3 silicon processors running in a macOS environment. The required open-source dependency options, which are transparent to the user and automatically picked up by the build configuration system upon availability, are:

• OpenSSL is a robust, commercial-grade, full-featured toolkit for general-purpose cryptography and secure communication. Versions 1.x were published under a dual-license scheme that was incompatible with the GPLv3.0 license, preventing the library from being a mandatory dependency for GNSS-SDR in most GNU/Linux distributions. OpenSSL 1.1.1, released on September 11, 2018, had already implemented all the cryptographic functions required by the OSNMA protocol. The licensing issue was resolved in OpenSSL version 3.0.0, which transitioned to the Apache License 2.0, fully compatible with GPLv3.0. Released on September 7, 2021, OpenSSL 3.0.0 and its subsequent updates support the cryptographic functions required by OSNMA and have been incorporated into major GNU/Linux distributions released since 2022. For instance, in Debian/Ubuntu-based distributions, it can be installed with sudo apt install libssl-dev.

• GnuTLS is used as a fallback if OpenSSL is not found on the host system when building GNSS-SDR. You can force linking against GnuTLS even if OpenSSL is installed by using the -DENABLE_GNUTLS=ON configuration option. This Transport Layer Security library, published under the GNU Lesser General Public License (LGPL), is available even in older GNU/Linux distributions. However, some operating systems may omit the optional (but necessary) SSL module. For instance, in Debian/Ubuntu-based distributions, it can be installed with sudo apt install libgnutls-openssl-dev. This library has implemented all the cryptographic functions required by OSNMA since version 3.6.13, released on April 24, 2020.

Usage of OSNMA data in GNSS-SDR

To use the OSNMA service in GNSS-SDR, users need to perform the following steps:

1. Register on the Galileo Service Center (GSC) website.
2. Download the public key and Merkle Tree files (.crt and .xml formats, respectively).
3. Specify their locations in the GNSS-SDR configuration file using the GNSS-SDR.osnma_public_key and GNSS-SDR.osnma_merkletree configuration parameters.

If your configuration includes 1B channels (Galileo E1 OS), the OSNMA service will be enabled by default. In this mode, all OSNMA-related events will be logged, and corresponding messages will be displayed in the terminal. If a negative authentication occurs, warning messages will be shown, but the receiver will continue to operate normally.

For PVT (Position, Velocity, and Time) solutions based solely on authenticated signals, you can enable strict mode by setting GNSS-SDR.osnma_mode=strict in your configuration file. In this mode, any non-authenticated signals will be disregarded.

Please note that, in strict mode, the OSNMA protocol requires the receiver’s internal clock to be synchronized with the Galileo System Time, allowing a tolerance of ±30 seconds. Therefore, it is essential to ensure that the system date and time on the computer running GNSS-SDR are set within this margin. This mode can only be used when processing GNSS signals in real-time via a RF front-end, but not in post-processing mode (that is, a signal source reading from a file).

Other open-source OSNMA implementations

Apart from the work presented in this page, there are other very interesting open-source implementations of the OSNMA protocol:

• OSNMAlib is an open-source Python library that can be used for research purposes or be integrated into existing receivers (among them, GNSS-SDR via the UDP NavDataMonitor output) and applications to incorporate navigation message authentication to the positioning process.⁹ The authors have made relevant contributions to the OSNMA protocol itself,¹⁰ and proposed techniques for shortening the Time To First Authenticated Fix.¹¹

• galileo-osnma is a Rust implementation of the OSNMA protocol that can be used in some embedded microcontrollers.

• FGI-OSNMA is an open-source Python library implementing the OSNMA protocol, and it is delivered by the National Land Survey of Finland. At the moment it only supports the Septentrio Binary Format (SBF), though the SBF can be read from either a file, network socket, or serial port.

Conclusions

The OSNMA service, in general, and the described GNSS-SDR integration, in particular, represent significant steps forward in enhancing GNSS receiver reliability in scenarios with potential spoofing attacks. The open-source nature of the presented solutions allows for the early adoption of the OSNMA service and promotes its continuous scrutiny, maintenance, discussion, and potential improvements.

References