To find a pattern in random messages, compress them and test each one

A computer security researcher at University College London, who has spent years studying encrypted traffic on the Tor project, turned the same traffic-analysis trick on a set of mysterious GPS messages that looked random. He found they were almost random, but not quite, and the exceptions raised questions about what the system was doing.

He started with a large collection. A handful of the special messages, captured at his house with a software-defined receiver that can read GPS pages ordinary phones ignore, was not enough for traffic analysis or crypto analysis. He turned instead to an archive of GPS messages stored in Potsdam since 2007, and pulled out every example of one rarely sent page of data. GPS organizes its broadcast into frames, subframes, and pages, and he studied one particular page. The messages looked random within the limited set of characters the GPS specification allows.

He then tested each message for surprise. The principle is that information content, randomness, and compressibility go together. Researchers measure that information as entropy, the average surprise per symbol, counted in bits. He used a method called PPMD, which predicts each symbol from the few symbols before it. He compressed the whole collection with one message left out, then restored that missing message and measured the increase in compressed size. A small increase meant the message held little new information and could have been guessed from what came before. A sharp increase meant the message was surprising and dense with information.

He plotted the results in a histogram and looked at the edges. Most of his GPS messages fell where randomly selected data should fall. A few fell far outside. The most surprising ones, which he called sentinels, were all zeros, all spaces, or the binary pattern 101010. The most predictable ones were messages that shared characters with messages sent before. He had already removed exact duplicates, so he was looking only at unique messages. Truly random, or perfectly encrypted, data should never produce near copies like that, so he suggested those near matches might have been errors, or reflected some urgent situation that led the system to send messages almost the same as before.

He also counted the changeovers. About 31 satellites broadcast an identical message in unison, then switch together to a new one, at first about every 3.7 days. When that rate appeared to shift around May 26, 2011, he applied a statistical check called cumulative sum, which tells when something changed about the data from before to afterwards. It showed the change was real: rotation went from about every 3.7 days to about every 1.8 days after late May 2011. Those odd near copies might reflect an error or an emergency.