Galileo's Proposed Authentication Algorithm: Part 2

Posted on

Recapping from part 1: Galileo will soon add cryptographic signatures to the navigation messages. These cryptographic signatures are made with symmetric cryptography, which means clever techniques are required to prevent receivers from impersonating the network.

The key to the technique is first signing messages, and only later disclosing the key used for the signatures, thus invalidating it for further use. Receivers can however verify that earlier signatures were indeed made with that key.

Periodically a key is signed using regular asymmetric public key cryptography. This can’t be done too often as it uses a lot of bandwidth.

Keys meanwhile are constructed so each key can be used to derive all previous keys. In this way, a new key can be ’taken backward’ until a key is found for which there is an actual public key signature on file.

In this way, the “TESLA” encryption algorithm chosen to underpin Galileo OSNMA, manages to provide useful signatures that can be trusted, using mostly symmetric cryptography.

In part 1 I covered the basics of TESLA. In this part 2, I describe how OSNMA makes unique use of the nature of Galileo to fit in the crypto bits.

Note that OSNMA is a challenging protocol to describe, and can’t fully make sense of all parts of the OSNMA 1.1 draft. If you find any of the likely mistakes, please let me know urgently on bert@hubertnet.nl or @GalileoSats.

Also, even though I make some critical remarks about OSNMA in this post, I am aware everyone is doing their best and trying to get as much functionality as possible out of the available bandwidth and connectivity.

Finally, even more so than usual, I’d like to thank the many people who contributed to this post, even though all mistakes remain mine. Several (anonymous) experts have contributed suggestions and clarifications, for which I am very grateful. Not for the first time, I’d like to thank Daniel Estévez for his solid work on improving my posts.

Galileo page, subframe, frame structure

Now, the Galileo terminology is somewhat confusing, but it is important to align to it from hereon as otherwise the OSNMA spec will never make sense.

What we have called a ‘message’ up to now is actually a nominal page, which in turn consists of an even and an odd page (just to mess with you). Fifteen of such pages make up a ‘subframe’. A page is confusingly also called a ‘word’, but then this sometimes refers to only a part of a page.

The fifteen pages of a subframe tell you everything there is to know about a single satellite, and also tells you about a selection of the other satellites. The information about other satellites is the so called “almanac”, and it is spread out over subframes.

Once 24 subframes have been received, we say one full frame has been transmitted. In every subframe of 30 seconds we got updated about a single satellite (and learned of a selection of the rest). After 24 subframes, we’ve gathered together the entire almanac, and we know details about all satellites.

This takes 720 seconds (12 minutes). Subframes are transmitted back to back, as are frames.

Visually this looks like this:

Transmission starts at the upper left and goes to the right, and then goes to the next subframe (the next row). Pages 3 and 4 are different over time and contain the almanac.

So to sum it up, a frame contains 24 subframes, and each subframe has 15 pages, for total of 360 (full) pages.

The structure of a Galileo E1 page (or “word”) is as follows:

Here it can be seen that 40 bits per page are dedicated to OSNMA, with 8 bits labeled ‘HKROOT’ and 32 bits called ‘MACK’.

In stark contrast to the simplified explanation from part 1 of this series, the MACK field has zero relation to the page in which it is being broadcast. So to clarify, even though something is called ‘MACK’ in the page layout, that does not contain the MAC of this page (well, it could, but that would be by accident).

Main data types

OSNMA carries two main data types. The HKROOT is the part that is signed with a real public key signature, and it contains a TESLA key that can be trusted. In addition, it has all the parameters we need to interpret the rest of the data. This is clever because this means that not only do we get a signed key, we also get signed configuration details. HKROOT stands for Headers and Root Key. The data we actually care about is called Digital Signature Message (DSM).

The second part is called MACK, and it does indeed contain MAC signatures, but it also carries new (unsigned) keys (that is the ‘K’ in ‘MACK’). It also carries a complicated description of what the MAC signatures actually represent.

The OSNMA designers have bravely decided that not only should OSNMA sign Galileo navigation messages, it should also sign bundles of them, and it should also sign navigation messages for GPS (and later BeiDou). And in fact, one Galileo satellite should also sign messages for other Galileo satellites. There are reasons for all this, but it makes for a complicated protocol.

Let’s start with the HKROOT.

HKROOT

The HKROOT section includes the global headers and the Digital Signature Message (DSM).

Per Galileo page we get 8 bits of HKROOT. The first two pages of a subframe contain HKROOT metadata.

The first page (1) gives us 7 bits of general status: is NMA on, should we use it (2 bits), what is the “chain ID” (2 bits), and the status of this chain (3 bits). There is also one bit of padding.

Page 2 of a subframe tells us where the bits contained in the next 13 pages go. Page 2 does this by telling us the DSM ID (4 bits), but also which ‘block’ (4 bits) this subframe will fill.

So a single subframe tells us the status of OSNMA, which Digital Signature Message will follow, and also which part of that DSM follows in the final 13 pages of the subframe.

We should take note that a DSM also has an ID, so a new one might start to appear while we’re still using the old one.

Digital Signature Message details

After we have seen enough subframes, we should have a full DSM. DSMs are variable length, but the length is specified (indirectly) in block 0. This is ok since every DSM will at least have 1 block, and we know we won’t have a complete DSM if we haven’t seen block 0.

Within the DSM-KROOT (as it is also called), we find the public key ID in use. With some luck this corresponds to “the Galileo Public Key” distributed earlier.

The DSM also contains or describes:

  • the size of the MACK block
  • the hash function used
  • the MAC function employed
  • the size of the symmetric keys
  • how many MAC bits will be broadcast (the MAC is truncated to this size)
  • a timestamp
  • some random bits to enhance the hashing (salt)
  • AN ACTUAL SYMMETRIC KEY! (the KROOT)
  • A digital signature
  • Some padding

Note that it is indeed very important that the whole DSM gets signed. It would otherwise be possible to reconfigure a receiver to use 1 bit keys, which would make it trivial to break security.

A typical DSM might be around 1000 bits long, which means it would take around 5 minutes to receive (at 8 bits per page). But since the DSM is a shared Galileo property, a receiver can gather bits from different satellites, and if things are timed cleverly (they are), a DSM might be in way earlier (or perhaps it still takes 5 minutes, even in the face of packet loss from lower elevation satellites, but that is still a win).

These few minutes are not a problem however, since a DSM is expected to be stable for very long periods, so a receiver can get to work with a DSM it received earlier.

So recapping, the DSM is broadcast in the HKROOT field and we need many subframes before we have a full one. Once the DSM is complete, we have a symmetric key we can trust, and we are assured we have received the right configuration parameters.

MAC

Now this is where it starts to get complicated. OSNMA is simultaneously a compromise but also extremely ambitious within the given constraints. Let us start with some constraints. Galileo satellites appear to be extremely reliable. Except for some clock hiccups, the space segment seems to be remarkably robust.

One way to make (space) hardware extremely reliable is to make it as dumb as a brick.

I have no proprietary insights, but it appears the Galileo designers took this brick approach. As far as I can tell, the ground segment uplinks a frame of data to transmit to a Galileo satellite, and then the satellite will play that frame for the next three hours. And that’s it.

(Ok not quite - the satellite does insert new timestamp fields. Also, for backup purposes, 7 additional ‘batches’ of data are uplinked, so the satellite can do its thing standalone for 24 hours).

Now, for normal operations this is fine, the frame can repeat identically for hours on end. OSNMA however requires dynamic signatures that change all the time. The Galileo satellite, being of a masonry nature, is not going to calculate hashes for us.

In a visionary moment, the Galileo designers saw this one coming, and allocated 40 bits of every full page for “External Data Broadcast Service”. In the EDBS field, bytes can be broadcast that are uplinked from external data, in a “bent pipe” fashion. In other words, you can send a stream of bytes from the ground segment, and it will be included in the pages that go out. Nice.

This does mean however that a Galileo satellite can only do OSNMA when it is in active ground communications.

Allow me to rant for a bit. Doing cryptography is hard enough already, even without arbitrary extra constraints. Even though 10 billion euros have already been invested in my beloved Galileo satellites, there are not enough satellite dishes available to talk to all Galileo satellites at the same time.

As of August 2020, the Galileo ground segment struggles to reach every satellite every hour (the nominal update frequency). Almost every week a few satellites do not get updated at the nominal rate.

The OSNMA designers already had a tough job, but their work has been complicated because they had to find a way to provide authentication for satellites that currently can not be reached.

So instead of every satellite sending out authentication only for its own data, the protocol has been expanded so satellites can send out MAC signatures for the rest as well.

Once that was a requirement, the OSNMA people decided to go for a lap of honour, and expanded their authentication capabilities to not only service out of reach Galileo satellites but to also include GPS and (potentially) BeiDou and GLONASS satellites. Yes.

Now, because there aren’t that much bits available, to save bandwidth, Galileo pages aren’t signed individually. Instead bundles of pages are. So for example, the five pages representing the satellite orbit (ephemeris) receive one combined signature.

Note that although this does add some complication, there are significant advantages. Such bundled signatures are a lot shorter, so they can be transmitted more often, which helps against packet loss.

Because it hasn’t quite been figured out what bits to sign from GPS and BeiDou messages, a whole layer of indirection has been added, so that OSNMA can broadcast signatures that cover arbitrary collections of data from any GNSS.

In the interest of retaining our sanity, discussion of this subject is postponed to part 3. But I will leave you with this gem to feast your mind on:

“The 12-bit MACSEQ field provides a MAC for the concatenation of the MAC-Info fields for the MACs of the MACK section whose ADKD type is flexible and to be dynamically allocated as per applicable MAC sequence (see MACLT field, section 3.3.9), so the receiver can verify their authenticity.”

Actual symmetric signatures and keys

Recall that Galileo transmits 15 full pages per subframe, and that each page has 32 bits of room for ‘MACK’. This means there are 480 bits in total. For MACK data, the subframe is the right level to think about - no MACK data will straddle two subframes.

To assemble the MACK data, simply concatenate all 15*32 bits from a subframe in the order in which they were received. The MAC data is made up of several MACK blocks. Depending on the chosen parameters (from the DSM-KROOT), a MACK block is either 480, 240 or 160 bits long. Or, stated differently, one whole subframe can contain 1, 2 or 3 MACK blocks.

In a MACK block we find several MAC signatures, plus descriptions of what they sign, plus a key.

So a typical MACK block might contain “I sign my own satellite orbit (ephemeris data), and here is the signature” (also known as “MAC0”), followed by “And the ephemeris data of satellite E01 has the following signature”. At the end of a MACK block, a symmetric key is disclosed.

The IOD field in there refers to the Galileo (and GPS) “Issue of Data” field, a number that is changed whenever new orbit data is transmitted. By matching the signature to the right IOD, we know we are verifying the right thing.

Note that the layout of the MACKs is very regular. This means that even if a page from a subframe is missing, signatures and keys can still be extracted from what did arrive.

Galileo broadcasts other things than orbit data as well, so there are also signature types defined for the almanac (all other satellite data), for the Galileo System Time Offset numbers, and for Search And Rescue (SAR) return link messages.

In the second row of the MACK block above, we see a PRN and ADKD field. The first describes a satellite for which this data is signed, while ADKD (“Authentication Data & Key Delay”) specifies what is being signed. If ADKD is 0, this signifies a signature on the basic orbit details (similar to MAC0, but then for another satellite). If ADKD is 2, the signature covers the entire subframe. Other numbers are also defined, and some have specific meanings for GPS, for example.

Finally there is a key in the MACK block - this is the key that was used to create all the MACs within this block. Note that there is nothing to signify what the id of this key is.

Actually verifying things

Now might be a good time to skim part 1 again to refresh your memory of the TESLA process.

In short, every Galileo signature is made with a key that is disclosed some time after the message has been transmitted. Practically speaking, the signature and the associated key are both to be found in the MACK block.

In part 1 we described how TESLA implements a key chain, where every key can be calculated back to ‘id 0’. And this id 0 key is then signed with an actual public key signature.

For OSNMA, this root key can be found in the DSM which is transmitted in the HKROOT stream.

In our description in part 1 every key was labeled with an identifier, so we knew what to do, Galileo OSNMA leaves determining this identifier as an exercise for the receiver.

The trick is that the DSM has a timestamp embedded in it, which describes when this chain began. Every subframe meanwhile lasts 30.000000000 seconds (really). In addition, the DSM also tells us how many MACK blocks are in every subframe. So based on this, for any given timestamp, we can calculate how many keys have been generated previously.

For example, if there are 2 MACK blocks per subframe, we know each MACK block took 15.000000000 seconds, and we can divide the age by 15 to get the position of this key in the chain. This position corresponds to the ‘id’ as we described it in part 1.

Once the position is known, key validation can proceed by calculating back from the key we just saw to one for which a asymmetric signature was provided in the DSM (as described in part 1).

Summarising

The two main OSNMA data structures (HKROOT, which carries the DSM, and MACK blocks) are both transmitted in the OSNMA field of Galileo pages. 15 pages make up one subframe.

DSM data is transmitted over multiple subframes, but MACK blocks are strictly localized to a subframe. Each subframe can carry 1, 2 or 3 MACK blocks. Even though a MACK block carries a signature and a key, this signature and key are unlikely to refer to the subframe that contains that MACK block.

Or more generally, there is no direct relation to the OSNMA data carried in a subframe to that subframe itself. Even though one field in the I/NAV page diagram is called ‘MACK’, it does not carry a MAC for that page.

The DSM provides a signed set of parameters that describe how the TESLA protocol is configured for OSNMA use. It also provides a signed symmetric key that anchors the TESLA key chain, and a timestamp to which that key corresponds.

MACK blocks provide MACs for both the transmitting satellite (‘MAC0’) and for other satellites. Every MACK block uses up one key. Because MACK blocks are transmitted at a very precise rate, whenever one is received, we can calculate how many keys have been generated since the last signed key from the DSM.

This allows us to verify our key by calculating our way back to the key for which a signature was provided in the DSM.

Next up

Sadly, the complexity does not stop here. As noted, OSNMA has decided to add a measure of flexibility by making it possible to describe arbitrary new signature bundles (“MACSEQ”).

In addition, to prevent cross-satellite replay attacks, actually calculating the key id (chain position) can also depend on a new parameter ‘NS’. If ‘NS’ is 36, every satellite operates its own chain. The NS value will be a protocol property and is not configurable.

Furthermore, the OSNMA specification contains words that create further distance between signatures and messages. This is called ‘SLOW MAC’. SLOW MAC is important to allow receivers with clocks that are not quite set correctly to safely bootstrap themselves.

In addition, there are ways to ‘offset’ the distribution of MACK blocks so chances increase to see a signature earlier, because different satellites will not transmit the same signatures at the same time.

Finally, the DSM is signed using “the” Galileo Public Key. However, it may be necessary to upgrade the public key to a new one. The specification provides a way to perform such an upgrade using a Merkle tree.

I originally promised to describe all these things in part 3 of this series, but I have been somewhat overwhelmed by the complexity of OSNMA. MACSEQ, NS and SLOW MAC are exceptionally thinly described in version 1.1 of the OSNMA draft. Writing up a description in blog post form might require significant amounts of imagination beyond the draft.

Version 1.1 of the OSNMA draft specification also states that the eventual official OSNMA standard might not contain everything that is in the draft. I hear it is possible the eventual standard might be simpler than the draft, which would be very welcome.

Part 3 of this series will only cover some of the details I skipped over, like how OSNMA uses some additional measures to prevent replay attacks, which I think forms an interesting enhancement of the TESLA protocol. In addition, SLOW MAC is important, and will be covered.

Part 4 of the series with some thoughts on the role of OSNMA in preventing jamming or spoofing will however go ahead, as this is a super fascinating subject.

Notes on version 1.1 of the draft

3.2.2 notes that the highest numbered PKID is the one that is in force. Only 4 bits are allocated to the PKID, limiting the number of new keys to only 15?

3.3.9 “Annex C provides the MAC Lookup Table” - this should be Annex B.

References