GPS 'Text Message' Field Reveals Military Rekeying Scheme

GPS, or Global Positioning System, relies on measuring the distance between a receiver and at least four satellites to determine a position on Earth. Beyond basic positioning, GPS signals also carry encoded data. This data, transmitted at a slow rate of 500 bits per second, provides crucial information such as the precise location of each satellite at any given time, satellite health, and atmospheric conditions for correction.

The Enigmatic "Text Message"

One particular data field, labeled "text message" and described as being "at the discretion of operating command," stands out because its content is not typically made available on standard GPS chips or smartphones. However, with a software-defined receiver, this data can be accessed. Initial observations of these messages revealed what appeared to be random data, which is unusual in nature unless it's intentionally randomized or encrypted. This sparked an investigation, drawing parallels to traffic analysis techniques used to understand encrypted data by examining patterns rather than content.

GPS Data Structure and Analysis

GPS data is organized into frames, subframes, and pages. The "text message" data is found on one of these pages, meaning it's transmitted relatively infrequently, typically changing once a day or less. To analyze these messages, a software-defined receiver was initially used, but for robust traffic analysis, a large dataset is required. An archive of GPS messages dating back to 2007 from Potsdam was utilized for this purpose.

Randomness and Information Content

Upon initial inspection, the messages appeared random, although the GPS specification limits the allowed characters. To scientifically assess randomness, statistical methods were employed, specifically measuring the information content (entropy) using a technique called PPMD. This method involves compressing a corpus of messages, leaving one out, and then re-inserting it to see how much the compressed size increases. A small increase indicates low information content and high predictability, while a large increase suggests high information content and surprise.

The analysis showed that most messages were distributed as expected for randomly selected data, but with notable exceptions: - Predictable Messages: Some messages were much more predictable than expected, often containing characters from previously sent messages, suggesting a non-random generation process. - Surprising Messages (Sentinels): A few messages were much more surprising, including patterns like all zeros, all spaces, or the binary sequence 101010. These "sentinels" were particularly significant.

The 2011 Event: A Shift in Message Frequency and Content

Further analysis involved tracking how often the messages changed. Initially, the entire constellation of approximately 31 satellites would send the same message, then collectively switch to a new one. The period for which a message was sent varied, starting at about 3.7 days per message.

A significant change was observed around May 26, 2011. Statistical tests using cumulative sum confirmed a robust shift in the data pattern. After this date, messages began rotating much more rapidly, with a period of about 1.8 days per message.

This change coincided with a presentation from a GPS system developer discussing "over-the-air distribution and rekeying" for the military's encrypted GPS system.

Military GPS and Rekeying

The military uses the same GPS satellites but with encrypted data for two main reasons: 1. Anti-Spoofing: Public GPS signals are weak and predictable. A small transmitter can easily overpower them, allowing for spoofing (broadcasting false signals to deceive receivers). Encrypted military signals require a decryption key, making spoofing much harder. 2. Anti-Jamming: Knowing the signal's characteristics makes jamming easier. Encryption makes it harder to develop precise jamming technology.

Distributing these encryption keys securely is a challenge. Historically, keys were loaded physically onto devices using "glorified USB sticks." This labor-intensive process required regular updates due to the short lifespan of keys (e.g., a week) and changes in alliances.

The "over-the-air distribution rekeying scheme" proposed a method to distribute keys wirelessly. While the presentation didn't detail the mechanism (e.g., which satellites or frequencies), the timing of its advertisement in 2011 strongly correlated with the observed changes in the "text message" data.

The Sentinel Event of May 26, 2011

On May 26, 2011, all GPS satellites stopped transmitting their usual "random" data in the "text message" field and instead broadcast the 101010 binary pattern. At exactly midnight on May 27, they switched back to transmitting random data, but at the new, faster rotation rate. This "sentinel event" was a major, coordinated change in the GPS system.

This strong correlation between the observed data patterns and the announced over-the-air rekeying system suggests that the "text message" field in GPS is likely the mechanism for distributing and rekeying encryption keys for military use.

Implications and Secrecy

This event would have been invisible to standard GPS receivers, as they are designed to ignore messages not relevant to positioning or timing. While some high-end receivers might show debugging information, the data would still be disregarded. Interestingly, the 101010 pattern is a violation of GPS specifications, and similar sentinel patterns in other GPS fields have caused receivers to crash.

No public announcement was made by GPS operators regarding this specific event, despite their daily updates on system status. This lack of transparency further supports the hypothesis that the "text message" field is used for classified military operations.

While the exact nature of the data remains unconfirmed by military sources, the evidence from traffic analysis is compelling. The keys used for military GPS have a short lifespan (e.g., a week), so any information gleaned from past events would be irrelevant for current operations.

The system likely involves multiple layers of encryption. Keys for decrypting the military signal might themselves be encrypted with other keys, allowing for flexible distribution to different allied groups. This enables the military to control access to the encrypted signal by selectively distributing the necessary decryption keys, even revoking access from former allies by simply not providing them with the updated keys.