OSNMA and TESLA key chains
Galileo Open Service Navigation Message Authentication: how a 20 bit/s side channel and a hash chain disclosed on a delay let a billion receivers verify a broadcast none of them can hold a key for.
OSNMA (Open Service Navigation Message Authentication) is Galileo's answer to the fact that a legacy GNSS navigation message is an unsigned public broadcast. It lets a receiver decide whether the navigation data it just used came from the Galileo ground segment, using a TESLA hash chain rather than a per-message signature. Its public observation test phase opened in November 2021 and the service has been operational since 2023, making it the first civil GNSS navigation-message authentication to reach that state.
Why not just sign the message
Three constraints kill the obvious answer, and understanding them is most of the entry.
- The link is tiny. A Galileo E1-B page carries a handful of spare bits. An ECDSA P-256 signature is 64 bytes; at the rate the reserved field affords, one signature per message is not remotely affordable.
- The receivers are cheap and numerous. Anything shipped to every receiver is public, so a symmetric key everyone holds authenticates nothing: an attacker buys a receiver and dumps its flash.
- A tag you can verify on arrival is replayable. If the receiver can check the tag the moment it lands, so can an attacker who rebroadcasts it. Verifiability on arrival proves origin, never freshness.
How TESLA breaks the deadlock
Generate a chain of keys backwards from a random seed: K(n), then K(n-1) = H(K(n)), and so on down to K(0). Publish K(0), the root, once, signed with a real asymmetric signature. Then disclose the chain forwards, one key per interval, in the opposite order to how it was built.
The asymmetry is free: hashing forwards from a disclosed key to the root is one cheap operation any receiver can do, and inverting the hash to predict the next key is infeasible. So a receiver can verify a key it just received against a root it trusts, and an attacker cannot produce tomorrow's key today.
The security condition is the whole scheme: a receiver may only accept a tag if it is sure the key that authenticates it was not yet public when the tagged data arrived. That makes loose clocks a security parameter, not a nuisance. A receiver whose time is wrong by more than the disclosure delay can be fed a tag by an attacker who already holds the key.
Where it lives in the signal
OSNMA adds no new signal. It occupies 40 reserved bits of each nominal E1-B I/NAV page, split into two logical channels:
| Channel | Rate | Per 30 s subframe | Carries |
|---|---|---|---|
| HKROOT | 8 bits/page | 15 bytes | NMA header, DSM header, 13-byte DSM block |
| MACK | 32 bits/page | 60 bytes | tags, then one 128-bit disclosed key |
A page is 2 s and a subframe is 15 pages, so the field is 600 bits per 30 s subframe, exactly 20 bit/s. The HKROOT channel drips a Digital Signature Message 13 bytes at a time; its header names the DSM and the block index, so a receiver that tunes in mid-cycle collects blocks in any order and knows when it has the set. Reassembled, the DSM yields the chain root KROOT plus a real signature over it, verified against a public key the receiver obtained out of band from the GNSS Service Centre.
MACK carries a run of truncated MAC tags followed by the key for an earlier subframe. The first tag is 40 bits and needs no tag-info because it is defined to cover this satellite's own data; each further tag costs 40 bits plus 16 bits of tag-info naming the satellite and the ADKD, the authentication data type. ADKD 0 covers this satellite's ephemeris, clock and status, ADKD 4 covers Galileo-to-UTC timing parameters, and ADKD 12 is the same data as 0 with a longer key delay for receivers with loose clocks. Because tag-info names a satellite, one OSNMA-transmitting satellite can authenticate another's data, which is cross-authentication and is why the whole constellation does not have to carry the field.
What it deliberately does not do
OSNMA authenticates the navigation data. It says nothing about the ranging signal the receiver actually measures time of arrival against. So meaconing defeats it without touching a bit: receive the genuine signal, amplify, rebroadcast a few hundred metres away. Every tag verifies, every key hashes to the signed root, and the fix is still wrong, because what changed is arrival time. One microsecond of repeater delay is 299.8 m of range error and hides comfortably inside a 30 s disclosure window. The checks that catch it read no bits at all: carrier-to-noise spread across tracked satellites, a clock-bias jump, angle of arrival with multiple antennas.
Working with it
The open-source reference is Daniel Estevez's galileo-osnma Python package (pip install galileo-osnma). It consumes I/NAV pages from a real receiver, typically a Septentrio binary log or GNSS-SDR telemetry, and it needs the GNSS Service Centre's published public key and Merkle tree root loaded before it can validate anything. Two documents are the ground truth and are worth having open: the OSNMA Signal-in-Space Interface Control Document for the bit-level field widths, and the OSNMA Receiver Guidelines for what a receiver is meant to do with them.
Pitfalls
- OSNMA is on E1-B only, and only on satellites that carry it. Absence of the field is not evidence of spoofing.
- A tag verified out of order proves nothing. Accepting a tag whose key was already public is the single implementation bug that voids the entire scheme.
- The root is a bootstrap problem, not a solved one. The public key and Merkle root arrive out of band; if you fetch them over an unauthenticated channel you have moved the trust, not established it.
- Authentication does not defeat jamming, which never needs to be believed to be effective.