Serious Security: GPS week rollover and the other sort of “zero day”

I bet you’ve heard of GPS, short for Global Positioning System.

It’s owned and operated by the US government but it’s available for free to anyone in the world – and, boy, is it widely used.

GPS is a fantastic feat of science and engineering that is anything but simple in implementation, but that is fairly simply explained.

A number of orbiting satellites (31 are active at the moment) continuously broadcast both their position in space and the current time.

Radio receivers on earth listen out for these broadcasts, and as long as they can “hear” the signals from three different satellites at the same time, and have their own reliable way of measuring the time, they can solve a system of mathematical equations to compute their own position.

The calculations rely on the fact that the time it takes for the signal to travel from the satellite to the receiver determines its distance, and with three distances you can lock in your position uniquely in three dimensions.

The time from satellite to receiver pinpoints the distance reliably because radio waves travel at a constant speed, and distance = speed × time.

Radio waves, known collectively as EMR, short for electromagnetic radiation, travel at what’s commonly called the speed of light, because light is just a special type of radio wave in the right frequency range to set off the detectors in the human retina. This speed is denoted by c, as in the famous equation E = mc2, and is defined in the GPS standard as 299,792,458 metres per second.

Fascinatingly, GPS positional calculations need to take Einstein’s theories of relativity into account.

The satellites are moving very fast relative to a receiver on earth, which makes their clocks seem to run slowly to us.

So we see the satellites falling behind by 7 millionths of a second each day.

On the other hand, the fact that we’re much closer to the centre of the earth’s gravitational field than the GPS satellites means that our clocks seem slow to them.

So the satellites see us dropping back by 45 millionths of a second a day.

This means that they are effectively gaining 45 microseconds on us due to our gravity, while also losing 7 microseconds to us on account of their speed.

Those daily 38 microseconds of relative time drift (45 – 7) have to be accounted for in the GPS calculations.

Four heads are better than three

GPS receivers actually lock onto four (or more) satellites simultaneously, instead of three, so they can solve equations that compute both their position and the current time, with astonishing accuracy.

This fourth satellite signal means that GPS receivers don’t need their own atomic clocks, so they can be made really small, and because they only need to listen in, never to transmit, they don’t consume a huge amount of power.

Indeed, modern GPS receivers are so small and energy-efficient that they can be packaged into a single chip as small as 5mm x 5mm, so that most modern phones can do GPS, as can bicycle speedos, smart watches, drones, along with lots of other consumer devices.

In fact, given their price, GPS receivers make fantastic reference clocks, even if the receiver is fixed to a building and you don’t care about measuring its position.

Absolute versus relative time

If all you need to know is how many seconds have passed since midnight on the previous Sunday morning, for example, because you can keep track of the date yourself, you never need to worry about numbers bigger than 604,800, which is the number of seconds in a week (60×60×24×7).

But that would mean every GPS receiver would need at least a basic clock of its own, albeit accurate only within half a week, that would keep running even if the receiver itself were powered down.

The GPS signal alone would only have enough information to decode the time relative to the current week.

So GPS includes a Week Number (WN) field that gives an absolute time reference, representing the number of weeks since the hour of midnight that kicked off the day of Sunday 06 January 1980 (1980-01-06T­00:00:00Z).

Thanks to the WN, you can, in theory, denote time absolutely: WN = -5 would start on the second day of December 1979, for example, while WN = +4 is the first week of February 1980.

Your GPS receiver can therefore be self-contained, requiring only the GPS satellites as its external data source, and requiring no writable computer memory (RAM) that’s capable of retaining the date when the power is off.

The tyranny of distance

GPS relies on precise electronic devices, including atomic clocks, that are blasted into, and then operated in, outer space.

By convention, outer space starts just 100km above the surface of our planet; GPS satellites are about 20,000 km up, close to twice the diameter of the earth away.

Space is a hostile environment for computers, so their performance is measured more in terms of durability than speed – there’s no point in having a multi-gigahertz CPU and a multi-megabit network link if they quickly end up running at speeds of zero.

Furthermore, GPS was invented and built during the 1970s and 1980s, when even terrestrial modems did well to send data at 1200 bits per second.

The GPS downlinks, therefore, send data to the billions of GPS receivers around the world at just 50 bits per second.

So every bit counts, and nothing can be wasted.

There’s no “pad this variable to the next 64-bit boundary” or “store this single character in a 32-bit DWORD” stuff going on in the GPS protocol.

As a result, the GPS standard had to make some storage compromises, one of which was that the WN field was allocated only 10 bits, so it can represent numbers from 0 to 1023, after which it wraps back to 0 and the count begins again.

1024 weeks is just under 20 years, and given that the GPS epoch – as such things are quaintly called in techie circles – started in 1980, GPS had its very own Y2K-type moment back in 1999.

In the simplest terms, the GPS “earth time” that immediately follows 1999-08-21T­23:59:59Z is not, as you might expect, 1999-08-22T­00:00:00Z.

Zero day revisited

At the rollover, the time advanced naturally enough, from one minute to midnight forward to midnight itself, but the date wrapped around back to “zero day”, 06 January 1980, when the GPS epoch started.

Of course, you can program around this, up to a point, as some people did for Y2K, for example by assuming that the years 00 to 49 denoted AD2000 to AD2049, while the years 50 and onwards covered AD1950 to AD1999.

But for that sort of compromise to work, you have to be certain that you will never need to represent AD1949, because you can’t.

Wherever you redirect your Y2K zero day, you’re still stuck with an epoch that can’t last more than 100 years.

Similarly, you’re stuck with a maximum of 1024 weeks in GPS. (The most recent flavour of GPS will extend this to 13 bits, which covers 2¹³ = 8192 weeks, which is more than 150 years, but there’s still a hard limit on the epoch length.)

A trick you can use in GPS receivers that can’t receive data from anywhere but the satellites, and that don’t have any non-volatile RAM (memory that can survive a power outage), is to treat the release date of the product as an offset into the epoch, so you get 19.7 years of WN range from your own starting point.

Given that you can’t run your firmware code before you compile it, you can reliably burn the compile date into your firmware image and use it as a convenient epoch extender.

As long as you get a firmware update out to all your users at some point in the next 19 years, you can reset and re-run your own adjusted epoch again and again, and you’ll never make a mistake when converting raw GPS data into absolute earthly timestamps.

Déjà vu all over again

Guess what?

If you go forward another 1024 weeks, or 19.7 years, from GPS’s 1999 rollover moment, you end up at the stroke of midnight that divides…

…tomorrow from Sunday!

That’s when Saturday 06 April 2019 turns into Sunday 07 April 2019.

What to do?

Should you panic?

Will your {bike computer, car satnav, mobile phone, drone, insert name of device here} go haywire on Sunday morning?

The answer is, “Very unlikely.”

Unless you have a GPS device that is very old and can’t get firmware updates, or you have a device that is more recent but you’ve never updated it, ever, you ought to be OK.

Time can’t go backwards, so any correctly programmed GPS device running firmware compiled after 1999 already knows that the date can’t suddenly rewind to 1999, and can detect and adjust for the rollover automatically.

Networked computers that synchronise their clocks from external sources aren’t likely to go haywire, either.

Firstly, most modern computers (with the notable popular exception of the Raspberry Pi series of computers, which always reboot in 1970) have backup clocks that are accurate enough to detect external time sources that are unreliably incorrect, and ignore them.

Secondly, most modern computers keep their clocks accurate using a protocol called NTP (short for Network time Protocol) that doesn’t depend on any single time source.

So you are unlikely to wake up and find Limp Bizkit on the radio, the Spice Girls on TV, and Apple stock at $1.50 (as splendid as at least one of those outcomes would be).

Still, you might as well check for satnav or other GPS-enabled device updates right now, just in case…

…and you might as well make sure you have your flux capacitor with you on Saturday night.