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. Th
