OSNMA: what is it and why it is used in GAMMS?
By Filipe Carvalho, GNSS Engineer at DEIMOS
GAMMS is a Horizon2020 project enabling the exploitation of space data for surveying and mapping. Its objective is to develop an Autonomous Terrestrial Mobile Mapping System (AMMS), based on the tight integration of Autonomous Vehicle (AV), navigation/geodetic, and Artificial Intelligence (AI) technologies.
More specifically, GAMMS is developing a mapping robot for geodata acquisition and an AI-based highly automated mapping software to produce HD maps from the MMS remote sensing data. DEIMOS is tasked with providing its G3 GNSS receiver for satellite-assisted navigation.
The GNSS (Global Navigation Satellite Systems) receiver used in GAMMS will make use of new features and services provided by the Galileo constellation, namely, the OSNMA.
The OSNMA – Galileo Open Service Navigation Message Authentication – is a service that is expected to be operational by 2023, which aims at assuring receivers that the received Galileo navigation message (I/NAV) is coming from the system itself and has not been modified. OSNMA data is transmitted within the Galileo E1 I/NAV messages, together with the navigation data used by the receiver to compute a PVT (Position, Velocity and Time) solution, as shown in Figure 1, improving the resilience of receivers to spoofing attacks.
In this context, spoofing consists of the (intentional or unintentional) transmission of signals which are interpreted by a receiver as legitimate, but containing misleading data. With the increased use of GNSS in civil society, disruption of this service becomes ever more impactful. In parallel, spoofing devices are becoming cheaper and more accessible, furthering the need for improved resilience against spoofing attacks.
The OSNMA protocol addresses this issue by providing a means for GNSS receivers to authenticate data transmitted by supposed Galileo constellation signals. In other words, the receivers that make use of OSNMA can know if the navigation data they are receiving is indeed provided by Galileo satellites or by some spoofing device. This is particularly important for sensitive applications, such as autonomous vehicle navigation, used in GAMMS, since disruption to the navigation system could potentially result in accidents and loss of life.
Figure 1 - OSNMA scheme
OSNMA data is transmitted within the E1-B I/NAV message which the receiver can use to verify the authenticity of the message sender. The figure is taken from Galileo OSNMA Info Note, by EUSPA.
In the digital world, authentication of information can be done with the use of Digital Signatures, which are patterns generated with a given set of information and a secret combination only known by the signer. This secret combination is called a “Private Key”, which is used exclusively to sign a set of data. The counterpart of a Private Key is the “Public Key”, which is generated from the former. This second key is not secret, on the contrary: it is distributed to the users, which can use it to verify if any signature has been generated with its corresponding Private Key, to verify the legitimacy of the signer. It is also important to point out that it is not at all easy to compute a Private Key from its corresponding Public Key, signatures and corresponding data, making this a relatively secure and viable technique for the authentication of data and entities.
The OSNMA protocol makes use of this cryptographic technique to authenticate data from satellites. Each receiver must have a Public Key, which is used to analyse the signatures broadcast by the Galileo constellation and thus authenticate its data. There are, however, added challenges to this. Galileo I/NAV navigation messages have a relatively low data rate (120 useful bits per second), and few bits left on the navigation message dedicated to OSNMA, which makes the use of Digital Signatures to sign each navigation message impractical (the largest signature is 1042-bit long). Signing each navigation message also makes it impractical for cross–authentication to be done, where one satellite can authenticate data from another satellite (which might not be broadcasting OSNMA data).
To solve this problem, the TESLA (Timed Efficient Stream Loss-tolerant Authentication) protocol is used. It consists of the broadcast of pairs of TESLA keys (which are unrelated to the aforementioned Private and Public Keys) and Message Authentication Codes (MACs). These codes are generated with a TESLA key and a navigation message, and allow the receiver to authenticate the data they refer to.
The TESLA keys are generated recursively on each other, in a chain, using one-way functions. These functions make it so that it is easy and quick to generate a key B from a key A, but difficult, resource and time-consuming to compute key A from key B. This makes the backbone of the OSNMA authentication: because the TESLA keys are broadcast in the reverse order of their generation chain, a Digital Signature is used to authenticate the last TESLA key of the chain, and the TESLA keys can be authenticated based on each other. So for example, consider a chain as depicted in Figure 2, where key A is used to generate key B, which generates key C. If key C is authenticated with a Digital Signature algorithm, when key B is broadcast (after key C) it can be checked if it generates key C or not. If yes, key B is valid. The same process happens to key A, broadcast after key B: it is checked if it generates key B and if so, it is also valid.
Figure 2 - TESLA Key chain
It is simple to generate key B from key A and key C from key B, but resource and time-consuming to generate key A from key B and key B from key C. Broadcasting the chain in reverse order (right to left) makes it difficult for spoofers to compute and anticipate the next TESLA key (up in the chain) to be broadcast, but easy for receivers to verify any received TESLA key by computing the keys down in the chain (left to right) and comparing the results with any previously authenticated TESLA key.
The last step in the verification process is to use a validated TESLA key and check if the Message Authentication Codes associated with it are correct. The TESLA keys are broadcast with a delay with regard to their associated MACs and navigation data, making it difficult for spoofers to anticipate this system and falsify data. MACs and TESLA keys can be used to validate data from other Galileo satellites (cross-authentication) that are not broadcasting OSNMA, making it possible to validate data from all visible satellites.
In summary, as shown in IMAGE- Figure 3:
- A Digital Signature is broadcast by the Galileo constellation, together with the last TESLA key of the TESLA chain (called the root key; in Figure 2 this would be key C); upon reception, the Digital Signature is verified by the receiver, thus validating the TESLA root key, and other relevant parameters;
- In parallel, TESLA keys further up in the chain and MACs are broadcast by Galileo satellites; the TESLA keys are validated with the previously authenticated TESLA keys or root key;
- MACs and navigation data are validated with their corresponding TESLA keys, which have a delay in broadcast, to make it so that the MACs and data could not have easily been falsified.
Figure 3 - OSNMA processing logic.
Note: for the OSNMA protocol, Message Authentication Codes (MACs) are shortened (truncated) to smaller codes to reduce the amount of data needed to be transmitted for each MAC. These truncated MACs are referred to as “Tags”. Figure taken from Galileo OSNMA Info Note, by EUSPA.
This system will allow the GNSS receiver developed by DEIMOS and used in GAMMS to operate with an assurance that its navigation data is authentic and therefore reliable for mapping purposes. Additionally, it provides safer navigation of the autonomous vehicle, since a successful spoofing attack against such a target can potentially have disastrous effects.