Video summary

GPS Hidden Messages - Computerphile

Main summary

Key takeaways

Technology

Overview

The video explains how GPS works beyond basic positioning, focusing on the hidden/encoded data portion of GPS signals. By monitoring that portion, the speaker performs traffic analysis—inferring likely operational events in the GPS system, particularly around key distribution / re-keying used by military GPS.

Key technical points about GPS signals and “hidden messages”

Positioning method

  • A GPS receiver measures its distance to satellites.
  • With signals from four satellites, it can compute its position on Earth.

Encoded payload on top of timing/ranging

  • GPS transmits additional data slowly (~500 bits/second).
  • Even at this rate, the data can include satellite-related information—such as where each satellite is “at” at each time.

Additional fields inside the data

The payload can include:

  • Satellite health (whether receivers should pay attention)
  • Satellite type
  • Atmospheric-related correction information

Notable anomaly: “At the discretion of operating command”

  • There appears to be a message field with text-like content, though it isn’t fully documented publicly.
  • These messages are typically not accessible via standard GPS chips/phone receivers.
  • They can be observed with a software-defined GPS receiver (SDR).

Monitoring approach: software-defined receiver + archived data

Equipment and capture method

The speaker uses:

  • A GPS antenna
  • An SDR (software-defined receiver) setup to capture the signal

Why the early data looked “random”

  • The messages initially appeared random, which is unusual because:
    • plaintext real-world data often isn’t random
    • data is often either intentionally randomized or encrypted

Need for lots of messages

To analyze patterns, the speaker needed a large corpus and used:

  • An archive of GPS messages stored since 2007 (from a Potsdam archive)
  • A UCL student previously helped make the archive usable
  • The speaker then took over extraction and analysis

Statistical analysis: compressibility, entropy, and “sentinel” events

Measuring randomness/information

The video describes randomness/information using:

  • Entropy
  • A compression-based test, including mention of PPMD (a predictive, compression-based method)

A “leave-one-out” style idea is also mentioned:

  • Remove one message from the corpus
  • Compress the remaining messages
  • Insert the removed message
  • Measure how much the prediction fails

What the analysis found

  • Most messages look random-like, but not perfectly.
  • Some messages are more predictable than expected.
  • A few are much more surprising than expected.

Special categories of interesting messages

  • “Sentinels”: extremely structured patterns, such as:
    • all zeros
    • all spaces
    • repeating bit patterns like 101010…
  • “Almost previously seen” messages:
    • not identical to earlier data, but similar
    • in theory they should carry less information, yet they still appear surprising in practice

Metadata/rotation behavior

Observations included:

  • About 31 satellites
  • Satellites tend to send the same message simultaneously
  • They rotate to new messages within a relatively short time window
  • The duration of each message changes over time (from ~3.7 days per message to ~1.8 days per message)
  • The speaker used CUSUM (cumulative sum) to validate a suspected change around the end of May 2011

Core hypothesis: military over-the-air re-keying reflected in sentinel content

Why this might be military-specific

The video contrasts:

  • Civilian GPS
    • widely published
    • no encryption keys are required for positioning
  • Military system
    • encrypted data to resist:
      • spoofing (fake signals)
      • jamming (harder without knowing expected signals)

Military keys must be:

  • protected
  • periodically refreshed, traditionally using physical key-loading devices (described as “glorified USB sticks”)

Over-the-air distribution claim

A presentation on over-the-air distribution suggests:

  • re-keying can be broadcast via updates
  • however, the exact key mechanism was unclear publicly

Evidence presented by the speaker (2011 timing)

  • In 2011, GPS message behavior changes in a way matching re-keying timing.
  • On 26 May, satellites appear to stop transmitting the usual “random” payload and instead transmit a sentinel pattern (notably 10101010…).
  • Around midnight at the start of 27 May, they return to “random data,” but rotating faster than before.

Conclusion (traffic analysis)

  • The video concludes there is strong evidence that these special GPS messages likely participate in the re-keying / key distribution mechanism.
  • The speaker is not 100% certain, since other internal events could also produce similar changes.

Why normal GPS users don’t notice

Typical GPS receivers:

  • ignore unknown or unneeded message types because they’re built for:

    • positioning
    • precise timing

  • Some higher-end/debug receivers might reveal extra data,

  • but most consumer devices won’t.

The video also notes that some sentinel patterns can even cause receiver malfunctions/crashes in certain cases because they violate GPS specification rules (e.g., 101010 not being allowed).

Limits and verification

  • The speaker could not decrypt the special messages.
  • By publication time, the relevant keys were no longer valid:
    • keys mentioned as valid for about a week
  • The speaker checked for public announcements from GPS operators during the events and found no documentation describing them.

Main speakers / sources (as mentioned in the video)

  • Primary speaker: The Computerphile presenter (researcher describing GPS monitoring and the Potsdam archive analysis)
  • Referenced sources/entities:
    • UCL student (helped make the Potsdam archive usable)
    • A GPS system presentation (on over-the-air distribution / re-keying)
    • Military / GPS operators (asked by journalists; no immediate response mentioned)

Original video