Galileo OSNMA (Open Service Navigation Message Authentication) is a service in the Galileo GNSS that allows receivers to authenticate cryptographically the navigation data transmitted in the Open Service signal. This is one of the mechanisms to avoid spoofing that are being deployed in Galileo. Currently, OSNMA is in its Public Observation Test Phase. Two years ago I presented a Rust library called galileo-osnma that implements OSNMA and includes some demo software for a small microcontroller, and also a PC CLI application. Since then, some breaking changes have happened in the format of the OSNMA signal-in-space, which have required updates in galileo-osnma. I have also implemented some new features. This post is an update about the current status of my galileo-osnma library and the OSNMA test phase.
ICD and cyrptographic material updates
The initial release of galileo-osnma that I made in March 2022 was based on the Galileo OSNMA User ICD for Test Phase v1.0, which was the latest ICD at the time and matched the signal-in-space. In December 2022, a new ICD, the Galileo OSNMA SIS ICD v1.0 was published. This contained some breaking changes with respect to the previous ICD. Below I will outline some of the changes. The signal-in-space was updated to follow this ICD in August 2023. Since some of the ICD changes interfered with the operation of galileo-osnma, I did some updates in August to fix the largest problems.
Yet another new ICD, the Galileo OSNMA SIS ICD v1.1 was published in October 2023. This was a smaller change compared to the previous one, but still had some breaking changes. New entries in the MAC lookup-table were defined, and some of these included FLX (flexible) entries, which is a feature that was defined in previous ICDs, but not exercised before. In December 2023 the OSNMA parameters of the signal-in-space were updated to use the MAC lookup-table ID 34, which only appeared in the v1.1 ICD. In January 2024 I have made the updates to galileo-osnma required for the v1.1 ICD and also added several new features.
Besides updates in the ICDs, there have also been changes in the cryptographic material. In August 2023, together with the update of the signal-in-space to the SIS ICD v1.0, there was a full change in the cryptographic material. A new Merkle tree was published, together with a new ECDSA public key with ID 1 belonging to that tree. In December 2023 there was a public key revocation exercise. As a consequence of this exercise, the key was changed to a new ECDSA public key with ID 2, belonging to the same Merkle tree. I recorded the OSNMA data for a few days around this exercise, and I will be showing some results below. In January 2024 all the cryptographic material, including the Merkle tree, has been changed again, coinciding with some updates in documentation about key distribution.
Changes in SIS ICD v1.0
Compared to the previous ICD, the SIS ICD v1.0, which began its applicability in August 2023, had a large number of changes. Some of these changes seem to have been intended to solve some shortcomings and corner cases that were present in OSNMA. I had mentioned some of these problems when speaking about my tests with galileo-osnma in 2022. Here I will outline the main changes.
A new COP field was added to the MACK Header, as shown here.
The COP field stands for Data Cut-Off-Point parameter. Briefly speaking, this parameter indicates how many 30 second intervals have passed since the last time that the data that is authenticated by this tag changed. It is used as a hint for receivers to determine whether they have the most recent version of the navigation data. If a receiver is not decoding INAV pages from some satellite because of low signal quality, it will still have stored the navigation data from that satellite that it managed to receive earlier. This data can be authenticated against the currently transmitted tags as long as the navigation data has not changed (because the tags always authenticate the most recent version of the navigation data).
Before the introduction of the COP field, there was really no way for a receiver to know whether the navigation data it had was the latest version, other than simply trying to authenticate it against the current tags. If the authentication failed, it wasn’t possible to tell if this was because the data was stale or because the data was spoofed.
Using the COP field in galileo-osnma required a partial rewrite of the module that stores the navigation data. The COP field allows to remove all the heuristics to determine when several words of the navigation message can be put together to form a set of navigation data. Before this field existed, words that have an IODnav could be checked for consistency, but the IODnav wasn’t present in all the words. Now that the COP field exists, it is possible to keep track of the “age” of each word separately (the number of 30 second intervals elapsed since a copy of this word was last received). When trying to authenticate the navigation data against a tag, if no word has an age greater than the COP, we know that these words form a matching and current set that can be authenticated against the tag.
Another important change was in the definition of the ADKD=4. This was actually the main breaking change of this ICD, since a receiver that ignored the COP field would continue to work. The ADKD=4 data refers to the Galileo constellation timing parameters, which are the GST-UTC and GST-GPST conversion parameters. These parameters are supposed to be global for all the constellation, so the older ICD defined the PRND associated with the parameters as 255. The navigation data for these global parameters could be received from any satellite, since it is assumed that all the satellites are broadcasting the same values for these parameters.
However, in practice this is not the case. It is not rare to see that different satellites are transmitting different values for these parameters simultaneously. In the tests that I did with galileo-osnma, this occasionally caused authentication failures for ADKD=4, specially when using the live data from Galmon, which includes the data for all the satellites in the constellation, instead of only the ones in view for a particular receiver.
Rather than fixing the root cause of the problem, which is having satellites transmitting contradicting information for the timing parameters, what the OSNMA SIS ICD v1.0 has done is to embrace the problem and now make the ADKD=4 data satellite dependent, in the same way that the ephemeris and satellite clock is also satellite dependent. This means that now the constellation timing parameters must be collected and stored separately for each satellite, instead of globally, just in case there are some satellites transmitting different versions of this data.
Implementing this change has increased somewhat the memory footprint of galileo-osnma. Most of the footprint is caused by the storage of the navigation message data. After implementing this change, the application still fits in the 32 KiB RAM microcontroller that I’m using as a demo, but it is a pity that the system has solved the problem in this way (which potentially also requires more time to authenticate the navigation data) instead of solving the root cause of the problem.
Changes in SIS ICD v1.1
The main change of SIS ICD v1.1 with respect to v1.0 is the addition of new entries to the MAC look-up table. The table for v1.0 had only 4 entries.
In v1.1, 8 entries are added, for a total of 12. Many of these new entries have FLX (flexible) slots, which means that the type of the tag transmitted in the slot is not fixed by the table.
Whereas with a 4-table entry it was reasonable to implement the table as a match statement that exploited the regularities of the table, with a much larger 12-table entry a much better solution is to encode the table itself in some form as read-only data. This is what I have done.
Besides the need for a change in the implementation approach, which is more of an anecdote than anything else, I would like to take this ICD change as an example of what I believe to be somewhat of a culture problem in the Galileo system engineering. In this and other occasions interacting with the system, I have felt that there is a strong tendency to include too many options for the sake of flexibility. Often, many of these options are too similar to offer real advantages, and since there are many, most of them never get exercised in practice, and receivers don’t get all the testing they should. The designers seem to be willing to take this approach in several aspects of the system instead of making studies to decide which configuration is the best (or at least, good enough). This reminds me of a friend of mine, who says “if you can’t make it perfect, make it adjustable”. This is a great principle in engineering, but it can only go so far.
The MAC look-up-table in the ICD v1.1 is the most clear example of this situation in OSNMA. To me, this table looks a bit ridiculous because I just fail to see the point of having 12 different entries, with many of these entries having FLX slots (which are like joker cards). However, it is important to remember that this is not the only flexible aspect of OSNMA. The ICD specifies two cryptographic algorithms for each of the functions: ECDSA P-256 vs ECDSA P-521, SHA-256 vs SHA3-256, and HMAC-SHA-256 vs CMAC-AES (maybe the thinking was that if one of the algorithms gets broken, the system can immediately switch to the other one), and variable size for the TESLA keys and the MAC tags. If I remember correctly, only one choice of each of these options has been used so far.
New features in galileo-osnma
In January I have also implemented some features that were missing in the initial release. These are listed here.
ECDSA P-521 support
Two years ago I didn’t include this because there wasn’t a suitable implementation of this elliptic curve in Rust. Since March 2023 there is the p521 crate, which has made implementing this as easy as ECDSA P-256. However, P-521 support is still marked as experimental, because so far the signal-in-space has only used P-256, and there are no test vectors for P-521 published.
Additionally, P-521 support is gated behind a feature (which is enabled by default). The reason is that including this makes the size of the osnma-longan-nano firmware larger than 128 KiB flash size of the microcontroller used for this demo. Therefore, since P-521 isn’t used currently (and maybe it never will), it makes sense to make this optional, for the sake of code size in small embedded applications.
DSM-PKR and Merkle tree
The DSM-PKR message is used to transmit a new public key, which is authenticated against the Merkle tree root. I didn’t implement this in my initial release, because the most common way of operating an OSNMA receiver is to load a trusted public key directly. DSM-PKR messages are only transmitted every 6 hours or when the public key changes. Since I wanted to test the December 2023 public key revocation scenario, I needed to have this feature working, so I have implemented it.
Non-nominal scenarios
Non-nominal scenarios includes public key renewal, public key revocation, chain renewal, chain revocation, Merkle tree change, and alert message. I have updated galileo-osnma to handle all these situations correctly. In order to handle renewal scenarios seamlessly, two cryptographic elements need to be stored. This is a TESLA key for the current chain, and a TESLA key for the next chain, as well as the current public key and the next public key. By doing this, when the change takes place, the new cryptographic material is already present in the receiver.
December 2023 public key revocation exercise
The public key revocation exercise was done on 2023-12-13. I recorded INAV data with an uBlox receiver at home between 2023-12-12 and 2023-12-15 using Galmon‘s tools. I have published this data in the dataset “Galileo INAV data for OSNMA public key revocation exercise in December 2023” in Zenodo.
The following diagram from the ICD shows how a public key revocation should look like.
The Merkle tree root corresponding to this exercise was
0E63F552C8021709043C239032EFFE941BF22C8389032F5F2701E0FBC80148B8
The ECDSA public key in force at the beginning of the exercise had ID 1 and was
-----BEGIN PUBLIC KEY-----
MFkwEwYHKoZIzj0CAQYIKoZIzj0DAQcDQgAEdKklz6D/GAXlxaWP26Mb8BRdW1vi
8GLT+Lsu6Y8PbbCBqF1dQK+JP+3Ss8YUnBSSGfDcEp9YCpRYO8lZE3fSqQ==
-----END PUBLIC KEY-----
Running the galmon-osnma tool in galileo-osnma v0.7.0 with RUST_LOG=info and this cryptographic material shows that on 2023-12-12 the DSM-KROOT was signed with public key ID 1 and the TESLA chain parameters were
Chain {
id: 0, hash_function: Sha256,
mac_function: HmacSha256, key_size_bytes: 16,
tag_size_bits: 40, maclt: 34,
alpha: 250728117155926 }
The DSM-PKR was transmitting public key ID 1 at the appropriate times (00:00, 06:00, 12:00 and 18:00 GST).
On 2023-12-13, at TOW 299131 (11:05:31 GST), a DSM-PKR for public key ID 2 is first transmitted:
verified public key in DSM-PKR: DsmPkr { number_of_blocks:
Some(13), message_id: 1, intermediate_tree_node_0:
[229, 83, 10, 51, 213, 203, 96, 201, 80, 22, 184, 174, 199,
69, 147, 219, 205, 242, 113, 29, 57, 158, 162, 72, 105, 23,
60, 162, 41, 55, 154, 21], intermediate_tree_node_1:
[49, 111, 169, 40, 95, 90, 30, 68, 4, 36, 19, 189, 175, 24,
170, 60, 246, 132, 114, 51, 151, 215, 184, 50, 90, 236, 161,
235, 202, 159, 15, 100], intermediate_tree_node_2:
[153, 5, 66, 76, 190, 72, 42, 26, 50, 176, 16, 100, 248, 93,
12, 54, 223, 3, 142, 82, 206, 18, 142, 126, 197, 243, 35, 225,
101, 177, 130, 167], intermediate_tree_node_3:
[21, 55, 189, 176, 16, 151, 46, 180, 163, 185, 11, 170, 205,
20, 148, 30, 244, 13, 162, 203, 43, 130, 211, 120, 179, 21,
192, 8, 222, 206, 253, 142], new_public_key_type:
EcdsaKey(P256Sha256), new_public_key_id: 2, new_public_key:
Some([3, 53, 120, 229, 199, 17, 169, 195, 189, 221, 28, 164,
238, 133, 247, 197, 27, 54, 120, 151, 203, 64, 184, 133, 104,
160, 200, 151, 218, 48, 239, 183, 195]),
padding: Some([36, 224, 34, 44, 144, 128]) }
The same DSM-PKR continues to be transmitted periodically.
At TOW 299371 (11:09:31 GST), step 1 begins. The NMA status and CPKS change to don’t use and public key revoked, indicating that the current public key has been revoked. The chain ID in the NMA header is still 0. At the same moment, the DSM-KROOT starts to be signed by public key ID 2. The chain ID of this DSM-KROOT is 1 (it was 0 previously). The remaining parameters of the chain do not change. The OSNMA ICD indicates that under these circumstances the receiver must discard the TESLA key corresponding to the chain ID in the NMA header. galileo-osnma does this, and since this point it is not able to authenticate MAC tags.
This situation continues until TOW 306541 (13:09:01 GST), when step 2 begins. The NMA status changes to test. The CPKS is still public key revoked, so this indicates that the past key has been revoked. The chain ID in the NMA header is now 1. In this situation galileo-osnma can authenticate the TESLA key transmitted in this subframe using the KROOT with TOW 305970 (12:59:30 GST) that it had received previously in the DSM-KROOTs for chain ID 1 (signed with public key ID 2). galileo-osnma can now check the MAC tags transmitted in the previous subframe, and from this point on it continues authenticating MAC tags successfully.
The CPKS continues indicating public key revoked until TOW 385291 (2023-12-14 11:01:31 UTC), when it changes to nominal. This the beginning of step 3, and thus the end of the public key revocation process. After this point, OSNMA operates normally.
The data I collected during this exercise indicates that the signal-in-space followed what the ICD describes during the public key revocation and that galileo-osnma processes the revocation correctly. It discards the public key and TESLA key when the revocation begins, and is not able to authenticate MAC tags during step 1. When step 2 begins, galileo-osnma immediately can begin authenticating MAC tags again using the KROOT for the new chain received during step 1.
State of OSNMA open-source implementations
In my post presenting the initial release of galileo-osnma I mentioned that I believed that it was important to have an open-source implementation of OSNMA. Even if the cryptographic algorithms are correctly implemented and secure, subtle bugs in the logic of an OSNMA implementation can cause security issues, so having an open-source implementation with many eyes looking at it is a good way of improving the security. Since there was no OSNMA reference implementation provided by Galileo, I implemented galileo-osnma in Rust, which is a relatively safe systems programming language that is suitable for embedded, and released it under a permissive open-source license, so that it could be integrated in any kind of commercial projects. My intention was to try to see if this would attract any interest from the industry and if all together we could have a common OSNMA implementation that is better, specially in terms of security.
Nothing like this has happened. I haven’t seen too much interest in my galileo-osnma implementation (though it is always difficult to judge the impact of open-source projects), and haven’t heard any feedback from industry. I guess that each company working on OSNMA is rolling their own implementation, much to the detriment of everyone (as the saying goes, “don’t roll your own cryptography”). Probably OSNMA is still a very niche topic, since it is in a test phase and it only provides a very specialized feature related to the security of just one particular GNSS system. So I still have good hopes for the future of galileo-osnma.
In the post I wrote two years ago I also did an overview of other open-source implementations of OSNMA. I mentioned osnma_core and osnma-receiver by Aleix Galán. Apparently, in April 2022 these projects were refactored into OSNMAlib, which forms part of Aleix’s ongoing PhD thesis at KU Leuven. OSNMAlib looks very capable and well maintained.
OSNMAlib has some additional features to recover cryptographic material from partially missing data. Citing from the README, “OSNMAlib implements several optimizations in the cryptographic material extraction and in the process of linking navigation data to tags. None of these optimizations imply trial-and-error on the verification process, any authentication failure should be assumed as spoofing.” As an example of these techniques, OSNMAlib is able to use the tags in the MACK sections that were received, even if some sections of the MACK message are missing. It is also able to piece together the TESLA key from MACK sections transmitted by different satellites, since all the satellites transmit the same key. These techniques can be very helpful when some INAV words are lost because of bad signal quality. However, it would be interesting to review if they don’t really impact the security of the OSNMA protocol.
OSNMAlib is licensed under the EUPL-1.2, which is a copyleft license (the former project osnma_core was GPLv3). This limits its applicability in commercial projects. Additionally, it is written in Python, which is not suitable for small embedded systems.
As part of the OSNMAlib project there is a very nice webpage in osnmalib.eu that contains a real-time view of the status OSNMA. Currently it gives a view of the data from a Septentrio receiver at KU Leuven, and also of the data collected by Galmon. The webpage works by using a logging feature of OSNMAlib that dumps the state of the OSNMA receiver every 30 seconds. This dump is converted to a simple static HTML, which is rendered with some nice CSS. The HTML page is refreshed when this happens by some Javascript. The approach is simple, but effective. Unfortunately, at the moment it seems that none of the code related to this webpage is publicly available.
I’m interested in this kind of webpage because it is something like Galmon but for OSNMA. When I released galileo-osnma, I had in mind to integrate it with Galmon so that the OSNMA status could show up in Galmon’s webpage. However, I lacked the time and motivation to do this. Nowadays it seems that Galmon is somewhat unmaintained, and even basic PRs are open for many months without merging. Bert Hubert, the project lead, seems to have moved on to some other equally interesting and great projects.
If the code used to produce the osnmalib.eu webpage was released as open-source, this would give me an easy way to display the status of galileo-osnma in a webpage. I could probably adapt the galmon-osnma demo application to output the same kind of logging dump as OSNMAlib. At the moment, the galileo-osnma API doesn’t have the features required to get the detailed information about the OSNMA data that is being received, which is what is needed for this webpage. All that the high-level API provides is the most current navigation data that is successfully authenticated. This is really the only thing that a GNSS receiver cares about, unless it intends to do detailed monitoring of OSNMA.
I have thought of maybe adding some callbacks to the galileo-osnma API defined through a Rust trait. This would allow external applications to provide custom behaviour at compile time that would run whenever some piece of data is received or some event happens, and there would be no cost if this feature is not used. With this callback idea it would be simple to output the data required for osnmalib.eu, or to log all the OSNMA data to InfluxDB or Redis.
Another OSNMA implementation in Python is osnmaPython, by Marc Cortés-Fragas. The first commit on this repository was in December 2021 and it was last updated in November 2022, so it doesn’t follow the current signal ICDs and is perhaps abandoned. The project has no license.
Yet another Python implementation is py-osnma-parser, by hmk3r. He says that this was part of his MSc at ETH Zurich, and that he proposed some attack concepts against OSNMA, which is quite interesting. The first commit on this repository was in April 2022, and the last code update was in September 2022. The repository has been updated more recently (September 2023) to include some documents and to update the README to say that the code is currently broken due to the signal-in-space changes in August 2023. Since the project was part of a finished MSc program, it seems that it is now abandoned. Yet again, this project has no license.
Finally, there is fgi-osnma. This is relatively new (first commit in September 2023), but it comes from the Finnish Geospatial research Institute, which is a well-known institution in the GNSS community. The project was presented in ION-GNSS+ 2023 and seems active (last update on November 2023). It is implemented in Python and released under the GPLv3 license.
My conclusions from this quick survey of a Github repository search by the name “osnma” is that Python is a prevalent language in open-source implementations of OSNMA, perhaps because these implementations are mainly focused on research. It is also somewhat alarming the fact that two of the implementations have no license. The two projects that do have a license are under copyleft licenses.
Therefore, I think that even though I have spent long periods without updating galileo-osnma, it still holds an important position in the open-source OSNMA scene. First and more importantly, because it is the only implementation done in a systems programming language. An implementation that is not written in a compiled language such as C, C++, Rust, or similar is probably not going to find its way into an embedded GNSS receiver. Second, and also importantly, because it is the only implementation that is released under a permissive open-source license. This makes it possible to use it in all sorts of commercial applications, and might result in an implementation that is better and more secure for everyone, if the project manages to gain some more traction.
One comment