A Rust implementation of Galileo OSNMA

Galileo OSNMA (Open Service Navigation Message Authentication) is a protocol that will allow Galileo GNSS receivers to authenticate cryptographically the navigation data that is broadcast by Galileo satellites. The system is currently in a public test phase and according to the roadmap it will begin the initial service in 2023.

This month I have spent some time working in a new Rust library that implements the receiver-side processing of OSNMA. The library is called galileo-osnma. Although there are still some features that are not implemented, and some other future ideas that I have for this library, it has already reached a point where I feel it can be released and used by others. In its present state it is already able to perform all the steps that are needed to check all the OSNMA authentication data that is currently being transmitted by the satellites during the test phase. The library is licensed under a permissive open source license (Apache + MIT, which is common in the Rust ecosystem).

The OSNMA protocol

The basic idea of OSNMA is to send cryptographic signatures together with the navigation data that is transmitted by the Galileo satellites. In this way, a receiver that gets all this data can check the signatures against a public key and ensure that the data really comes from the Galileo constellation, and not from a third parity faking the signals transmitted by the satellites (which in the GNSS community is know as spoofing). However, there is much more to this system than just attaching public key cryptography signatures to the data. Galileo satellites send data at a really low rate (125 bits per second for the E1B signal), so the size of public key cryptography signatures easily becomes prohibitive.

OSNMA uses a cryptographic protocol known as TESLA that reduces the size of the signatures that need to be sent. A detailed explanation of the system is outside of the scope of this post. The basic idea is that instead of using public key cryptography to sign the data, the data is signed using symmetric key cryptography, such as HMACs. These signatures can be quite short. The symmetric keys used to generate these signatures are disclosed by the system some time after the signatures have been broadcast.

The TESLA symmetric keys belong to a chain that has been generated by successively applying a one-way function to the first key in the chain. The keys are used and transmitted in the reverse order in which they were generated. In this way, a receiver cannot predict future keys, but if it already trusts a key, given a new key it can check whether that new key belongs to the same chain, and decide to trust it as well if it does. Some of the keys in the chain are given public key cryptography signatures (Galileo uses ECDSA), so that a receiver that only has the public key can grab one of these keys, check its signature, and start trusting the chain from that point on.

People interested in more details about OSNMA can refer to the series of posts by Bert Hubert (taking note that those posts refer to an older version of the ICD and some details have changed slightly) and to the current version of the ICD and receiver guidelines for the test phase.

An open source implementation of OSNMA

If one takes a look at the OSNMA ICD, it seems reasonably straightforward to implement all the steps that are needed to perform the cryptographic checks that OSNMA requires. The algorithms that are used are quite well known and have many open source implementations. They are SHA-256, SHA3-256, HMAC-SHA-256, CMAC-AES-256, ECDSA P-256 / SHA-256, and ECDSA P-521 / SHA-512.

However, if one takes a more careful look at the details of how all this works, it becomes apparent that subtle bugs can cause security problems. The OSNMA protocol is cryptographically sound, in the sense that if a receiver implements all the checks correctly, it is virtually impossible for an attacker that does not have the private ECDSA key to inject information in the receiver and eventually cause it to give as valid some piece of information that has been generated or modified by the attacker (and doesn’t really come from the Galileo system). By “virtually impossible” I mean something along the lines of “the best the attacker can do is to try to randomly guess signatures”. The papers about TESLA formalize this notion and prove the soundness of the protocol under this assumption.

I think it is not completely trivial to implement everything properly. For instance, the OSNMA ICD makes clear that a receiver should never attempt to check a tag (a symmetric key signature) against a piece of navigation message data that has been transmitted after the tag. Yet handling and housekeeping the navigation message data and the tags can be tricky, since information comes simultaneously from several satellites, some messages can be lost, the same navigation message data can be repeated multiple times or it can change, etc.

All this leads me to the conclusion that having an implementation that is able to do all the checks and works well under nominal conditions does not guarantee having something is 100% secure. Therefore, I believe that an open source reference implementation of OSNMA that can be audited and relied on would be quite helpful to the GNSS community.

It is not unheard of ESA publishing open source reference implementations for the GNSS technologies they use. For instance, NeQuick-G, the model used for ionospheric correction in Galileo has an open source reference implementation that many people use. Nothing like this is available for OSNMA, and I do not know if there are plans within ESA to release such a reference implementation.

I do not claim that my galileo-osnma library is free of bugs (surely it has a few at this early stage!), or that it can be suitable as a reference implementation. I currently lack the time and motivation to check thoroughly that everything is being done properly. However, it might become the seed for such a reference implementation if there is enough interest and support from the community.

One of my motivations for making and releasing this library is to see how the community responds. I would be glad if the library gains some traction in the industry and/or in the hobbyist community, and this leads to a better product for everyone.

It is fair to mention that, to my knowledge, there is already another open source implementation of OSNMA, which is osnma_core and osnma-receiver by Github user Algafix. However, this is a Python library. I am really interested in seeing OSNMA running on small embedded platforms using microcontrollers, and Python is not really an option for this. Moreover, osnma_core is licensed under the GPLv3, which not all people may like, especially in industry applications.

Using Rust for OSNMA

I think that Rust is a good choice for an OSNMA library, for several reasons. First, it is a relatively low-level language that is suitable for embedded and other constrained applications. Second, there is very good support for cryptography from the Rust Crypto team (though an implementation for the P-521 elliptic curve is not yet available). And third, it contains a number of features that make it safer and more suitable for the development of secure software than C or C++.

As an example of this, I’m using Rust’s type system to keep track of whether the trust in a particular TESLA key has been already traced all the way to the ECDSA public key or not. The type system will prevent at compile time mistakes such as attempting to check a tag using a key we really shouldn’t trust yet.

Additionally, Rust has other nice features, such as good handling of dependencies, cross-compilation and unit tests with cargo, good documentation with rustdoc (and good documentation is the norm for Rust crates, and the galileo-osnma library strives no less), helpful error messages in the compiler, and a wonderful community. The machine code generated by the Rust compiler (which uses LLVM) is quite performant. Often similar or better to C or C++.

All this doesn’t leave out other programming languages. In the future I’m planning to make a C API at least for the top-level functionality of the library (since some of the concepts used in the internal functions of the library may not translate that well to C), and also a Python API using PyO3 (even though I think that an OSNMA library should not be made in Python, I also know that many people, including myself, would want to use it from Python).

A demo using Galmon

I am using the tools from the Galmon project to get data to test my implementation. In particular, I am using a LimeNET-Micro board, because I already have it sitting around and it has a uBlox-M8 GNSS receiver and a Raspberry Pi compute module. The ubxtool application from Galmon can run on the LimeNET-Micro and store all the data produced by the uBlox receiver in a file using packets that are based on Protocol Buffers. At this point I have collected weeks worth of data.

I have added support for the Galmon transport protocol in galileo-osnma right from the start, so I can directly read these files with my library and process the OSNMA data. There are some instructions about how to process data using a simple tool that reads data in the Galmon format from the standard input and uses the galileo-osnma library to process the OSNMA data and log all the events that happen. If you want to test this and you do not have a GNSS receiver at hand, you can use this file, which is part of the data I have been collecting. You will need to obtain the OSNMA ECDSA public key for the public test phase as described in the README (I think I am not allowed to redistribute this key).

When we run this tool with the file linked above and the environment variable RUST_LOG=info, we see that it starts logging something like the following:

INFO  galileo_osnma::subframe] starting collection of new subframe (GST Gst { wn: 1176, tow: 120927 })
INFO  galileo_osnma::subframe] starting collection of new subframe (GST Gst { wn: 1176, tow: 120931 })
INFO  galileo_osnma::dsm] new DSM id = 2 (had id = 0). resetting
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::subframe] starting collection of new subframe (GST Gst { wn: 1176, tow: 120961 })
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::subframe] starting collection of new subframe (GST Gst { wn: 1176, tow: 120991 })
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::subframe] starting collection of new subframe (GST Gst { wn: 1176, tow: 121021 })
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::subframe] starting collection of new subframe (GST Gst { wn: 1176, tow: 121051 })
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::osnma] no valid TESLA key yet. unable to validate MACK key
INFO  galileo_osnma::subframe] starting collection of new subframe (GST Gst { wn: 1176, tow: 121081 })
INFO  galileo_osnma::dsm] completed DSM with id = 2, size = 104 bytes
INFO  galileo_osnma::osnma] verified KROOT
INFO  galileo_osnma::osnma] initializing TESLA key to Key { data: [132, 30, 29, 228, 212, 88, 192, 233, 132, 36, 118, 224, 4, 102, 108, 243, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], chain: Chain { status: Test, id: 1, hash_function: Sha256, mac_function: HmacSha256, key_size_bytes: 16, tag_size_bits: 40, maclt: 33, alpha: 41590689997730 }, gst_subframe: Gst { wn: 1176, tow: 118770 }, _validated: Validated }

At first, the library doesn’t have a valid TESLA key, so even though it is collecting data, it cannot do much with it yet. At some point (after ~6 subframes, which is 3 minutes) it completes a DSM-KROOT message, which contains a TESLA key with an ECDSA signature. It checks the signature against the public key, obtaining it first valid key.

Then it continues getting new TESLA keys and validating them using the keys it already trusts. It uses these keys to check the tags, which sign the navigation message data. When enough keys have been checked, the navigation data for some of the satellites is declared as authenticated.

INFO  galileo_osnma::osnma] new TESLA key Key { data: [25, 88, 231, 118, 111, 180, 8, 203, 214, 168, 222, 252, 228, 199, 213, 102, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], chain: Chain { ssh_function: Sha256, mac_function: HmacSha256, key_size_bytes: 16, tag_size_bits: 40, maclt: 33, alpha: 41590689997730 }, gst_subframe: Gst { wn: 1176, tow: 121080 }, _validated: Validated } succeey { data: [132, 30, 29, 228, 212, 88, 192, 233, 132, 36, 118, 224, 4, 102, 108, 243, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], chain: Chain { status: Test, id: 1, hash_function: Sha256, ma, key_size_bytes: 16, tag_size_bits: 40, maclt: 33, alpha: 41590689997730 }, gst_subframe: Gst { wn: 1176, tow: 118770 }, _validated: Validated }
INFO  galileo_osnma::navmessage] E19 InavCed at Gst { wn: 1176, tow: 121050 } tag0 correct (auth by E19)
INFO  galileo_osnma::navmessage] E27 InavCed at Gst { wn: 1176, tow: 121050 } tag1 correct (auth by E19)
INFO  galileo_osnma::navmessage] E18 InavCed at Gst { wn: 1176, tow: 121050 } tag4 correct (auth by E19)
INFO  galileo_osnma::navmessage] E21 InavCed at Gst { wn: 1176, tow: 121050 } tag0 correct (auth by E21)
INFO  galileo_osnma::navmessage] E27 InavCed at Gst { wn: 1176, tow: 121050 } tag1 correct (auth by E21)
INFO  galileo_osnma::navmessage] E18 InavCed at Gst { wn: 1176, tow: 121050 } tag2 correct (auth by E21)
INFO  galmon_osnma] new CED and status for E18 authenticated (authbits = 80, GST = Gst { wn: 1176, tow: 121020 })
INFO  galmon_osnma] new CED and status for E27 authenticated (authbits = 80, GST = Gst { wn: 1176, tow: 121020 })

At this point, an application might ask galileo-osnma for the authenticated data and use it for whatever purpose (typically, to compute the receiver’s position and time).

A demo with embedded hardware

As I said, I am really interested in seeing OSNMA running in small embedded applications. Currently there are many applications that use a GNSS receiver that would benefit from OSNMA (although it is clear that at some point OSNMA will be implemented in these inexpensive GNSS receivers, which are also a small embedded platform on themselves).

To show that galileo-osnma can fit in a small embedded microcontroller, I have prepared a demo of the library running in a Longan nano board, which has a GD32VF103 RISC-V RV32IMAC microcontroller with 128 KB of flash and 32 KB of RAM. I like this board because it is really cheap and small and it is RISC-V.

The details of the demo are described in its README. The software running on the microcontroller uses the UART to communicated with a small tool running on a PC. The tool on the PC reads a file using the Galmon format and sends the INAV and OSNMA data to the microcontroller through the UART. The microcontroller replies through the UART confirming the reception of the data and informing of which data it has managed to authenticate using OSNMA.

This shows an example of the UART output of the microcontroller, which is receiving the data for satellites E19 and E18 and informing that it has managed to authenticate navigation data for E27 and the Galileo constellation timing parameters (which are referred to by ADKD=4 in the OSNMA documentation).

E19 WN 1176 TOW 121139 INAV
AUTH ADKD=4 TOW 121050
AUTH ADKD=0 E27 TOW 121050
READY
E19 WN 1176 TOW 121139 OSNMA
AUTH ADKD=4 TOW 121050
AUTH ADKD=0 E27 TOW 121050
READY
E18 WN 1176 TOW 121139 INAV
AUTH ADKD=4 TOW 121050
AUTH ADKD=0 E27 TOW 121050
READY
E18 WN 1176 TOW 121139 OSNMA
AUTH ADKD=4 TOW 121050
AUTH ADKD=0 E27 TOW 121050
READY

How to collaborate?

If you want to collaborate with the development of the galileo-osnma library, first and foremost, use it. I am interested in feedback about what works well and what does not, as well as what new features would be helpful (besides those already identified) or whether some things would improve if being done differently.

I could also really use some help having another pair of eyes looking at the documentation and the code (especially the documentation). Feedback about whether the API makes sense, the documentation is good and sufficient, etc., is more than welcome.

There are already some small API changes and improvements I have though about. For instance, rather than using usize to represent the SVNs, and having functions panic when the value of this usize is not between 1 and 36, we could have a specific Svn type that guarantees its value to be between 1 and 36 (and the error would only happen when one attempts to construct an Svn starting from an integer). There are probably many other improvements I have not thought about and that other people could come up with.

Finally, we could have more unit test coverage. There are already tests for all the low-level cryptographic functionalities and the parsing of messages. For this, I have used the data I have collected to build some kind of “test vectors”. I have avoided using the test vectors in Annex 1 of the OSNMA receiver guidelines to avoid any potential legal problems (these documents have a large number of legal conditions I do not fully understand). However, some parts of the code have no unit tests yet.