What is a GNSS?

GNSS (Global Navigation Satellite System) is a satellite system that is used to pinpoint the geographic location of a user’s receiver anywhere in the world. Four GNSS systems are currently in operation: the United States’ Global Positioning System (GPS), the Russian Federation’s Global Orbiting Navigation Satellite System (GLONASS), China’s BeiDou Navigation Service System (fully operational in 2020) and Europe’s Galileo. Each of the GNSS systems employs a constellation of orbiting satellites working in conjunction with a network of ground stations.

Satellite-based navigation systems use a version of triangulation to locate the user, through calculations involving information from a number of satellites. Each satellite transmits coded signals at precise intervals. The receiver converts signal information into position, velocity, and time estimates. Using this information, any receiver on or near the earth’s surface can calculate the exact position of the transmitting satellite and the distance (from the transmission time delay) between it and the receiver. Coordinating current signal data from four or more satellites enables the receiver to determine its position.

The performance of GNSS is assessed using four criteria:

Accuracy: the difference between a receiver’s measured and real position, speed or time;

Integrity: a system’s capacity to provide a threshold of confidence and, in the event of an anomaly in the positioning data, an alarm;

Continuity: a system’s ability to function without interruption;

Availability: the percentage of time a signal fulfils the above accuracy, integrity and continuity criteria.

Each satellite system is positioned in a specific orbit around earth:

Presentation of GALILEO

Galileo is Europe’s Global Navigation Satellite System (GNSS), providing improved positioning and timing information with significant positive implications for many European services and users. For example:

Galileo allows users to know their exact position with greater precision than what is offered by other available systems.

The products that people use every day, from the navigation device in your car to a mobile phone, benefit from the increased accuracy that Galileo provides.

Critical, emergency response-services benefit from Galileo.

Galileo’s services will make Europe’s roads and railways safer and more efficient.

It boosts European innovation, contributing to the creation of many new products and services, creating jobs and allowing Europe to own a greater share of the EUR 175 billion global GNSS market.

The complete Galileo constellation will comprise satellites spread evenly around three orbital planes inclined at an angle of 56 degrees to the equator. Each satellite will take about 14 hours to orbit the Earth. One satellite in each plane will be a spare, on stand-by should any operational satellite fail.

From most locations, six to eight satellites will always be visible, allowing positions and timing to be determined very accurately to within a few centimeters. Interoperability with the US system of GPS satellites will only increase the reliability of Galileo services.

Navigation Message Authentication (NMA)

During the past two decades, global navigation satellite systems (GNSS) have become an integral part of many critical infrastructures, including energy transmission and distribution, telecommunications, financial services, and transportation. An ever-growing dependence on GNSS inevitably creates incentives for adversaries to target GNSS with the intention of causing damage and disruption or to obtain an illegitimate advantage.

Improving the resiliency of navigation and timing can potentially be achieved through a combination of system and user-level techniques, providing protection of both navigation message and ranging level. The focus is on protection of the navigation message and various schemes for providing assurance of its authenticity and cryptographic integrity. This is commonly referred to as navigation message authentication (NMA).

From here, we will describe more deeply the concept of navigation message encryption.

How does Galileo NMA work?

Message authentication has been referred to as the “second face” of cryptology, and it uses many of the same tools and techniques as the more well-known first face of cryptology: cryptography, or data secrecy. In message authentication, the sender uses a secret key to generate an authentication signature from the original message. Both message and signature are then transmitted to the receiver, which uses a key (potentially different to that used by the transmitter) to verify that the message and authentication signature correspond.

When the received message is authenticated the receiver can conclude that:

The transmitted and received message is the same

Only someone with access to the transmitter’s secret key could have generated the authentication message

There are two different ways to generate authentication signatures:

Using symmetric key techniques in which both transmitter and receiver share a secret key

Using asymmetric key techniques in which the secret key is split into two parts, a “private” key, known only to the transmitter, and a public key which can be distributed publicly. The private key is used to generate the authentication message, while the public key is used in the verification step.

For example, GPS is using Asymmetric NMA, but Galileo uses a combination of Asymmetric and Symmetric keys.

The proposal for Galileo Open Service Navigation Message Authentication (OSNMA) differs from Chimera in that it is based on a hybrid symmetric/ asymmetric key approach known as the Timed Efficient Streamed Loss-Tolerant Authentication (TESLA) scheme.

TESLA addresses the issue of symmetric key distribution as follows. First, a Message Authentication Code (MAC) is generated using the message and the private key. Both the message and the MAC are transmitted and then, sometime later, the private key is broadcast. This delayed release mechanism should ensure that the key used to generate the MAC is not known until after the message and MAC are already received. However, this does not prevent a spoofer from simply generating their own messages, keys and MACs and broadcasting them in a manner compliant with the specifications.

To address this latter issue, TESLA uses the concept of a chain of keys. An initial key K0 is randomly selected. Each subsequent key in the chain Ki+1 is generated from the previous key Ki using a one way function: Ki+1 = f(Ki). A one way function is a mathematical transformation that is easy to compute but very difficult to invert. Thus, given Ki it is easy to compute Ki+1, but given Ki+1 it is computationally infeasible to establish Ki.

In TESLA the system generates a chain of length N, then transmits the Nth key (called the root key) along with a digital signature generated using a standard asymmetric scheme, such as ECDSA. The chain keys are then used in reverse order to generate the MACs. Knowing the one-way function, the receiver can verify that each chain key is from the same chain as the digitally signed root key, but cannot predict “future” chain keys.

Once a TESLA chain has been established by asymmetric cryptographic means, the satellites begin transmitting messages, MACs and keys using the delayed release mechanism. The receiver extracts the messages and MACs and stores them until the key is received. The key is first checked to ensure that it is part of the TESLA chain in force using the known one way function. If the key passes this test, it is then used to verify that the MAC and the message correspond.

There is one absolutely critical assumption that must be made for the TESLA-based scheme to work: the receiver must have an authenticated time synchronization that is at least better than the key delay.

Without this assurance, the receiver cannot be certain that the navigation message has not been generated by a spoofer that has already received the perfectly valid signing key from a live satellite signal.

The OSNMA field is delivered every two seconds of the Galileo E1b I/NAV (a specific frequency) message.

The data are grouped into subframes of 30 seconds duration, and each MAC is only 10 to 32 bits in length, while key sizes range from 80 to 256 bits.

Example of a single E1-B word nominal page structure with the OSNMA field highlighted. I worked my whole internship on this particular field.

The figure above presents the Galileo E1-B I/NAV message structure and highlights the position of the OSNMA field (named as “Res”) within a 30-second subframe

Conclusion

The Galileo program is studying the provision of an open navigation message authentication (NMA) service in the years to come, in order to contribute to the mitigation of GNSS vulnerabilities and provide a differentiator with respect to other GNSS. Different applications could benefit from NMA to protect against certain spoofing attacks, used in isolation or in conjunction with inertial sensors, trusted clocks, or antenna arrays.

This article presents a global introduction of NMA for the Galileo Open Service. It is based on the standard TESLA protocol modified in order to use a single chain of keys for all satellites, to increase robustness to data loss.

Based on the presented results, and notwithstanding any improvements that may be incorporated in the future, we can conclude that Galileo, through its I/NAV E1-B signal, can provide a highly available and robust NMA service.