[atemerev]

Would it be possible to upgrade GPS satellites so the signal would contain digital signatures, while retaining backwards compatibility? GPS uses NMEA data messages, which are plaintext.

Perhaps there is some reserved field, or usually ignored message, that can be used to insert digital signatures. The DoD will keep the master key, so the signatures could be easily verified, but spoofing them would be nearly impossible.

[heavenlyblue]

Look here: https://news.ycombinator.com/item?id=19652414

Tl;dr: nope.

[atemerev]

All modern digital signature systems protect against replay attacks (by signing sequential counters, timestamps or other state information, or using cypher block chaining).

[jhayward]

All of those things require some alternate source of ground truth, e.g., a trusted clock.

There is no such thing in GNSS systems. They are the ground truth. There is no way to combat a replay attack without some second source which would obviate much of what a GNSS delivers.

[atemerev]

GPS time is monotonously increasing. If you ignore all messages with timestamps lower than the last one received, and check their digital signatures, you should be protected against replay attacks at least until the next cold restart (or GPS time counter reset, which is once in 20 years).

There are other possibilities (CTR/CFB encryption modes, relying on increasing counter and/or previous messages contents).

Or am I missing something? Could you please describe the attack vector with these assumptions?

[jhayward]

TLDR: you essentially never see repeated time stamps.

GPS time is broadcast in the very low bit rate (50 BPS) NAV message, once every 6 seconds. In between the receiver counts at the chip rate (1023 kHz) just counting signal transitions.

A rebroadcast attack happens at the speed of light. A signal is received at Moscow airport and is beamed to the Kremlin via some alternate transport path. At the Kremlin the signal is broadcast immediately at higher power than is possible for the direct signal. This happens at the speed of light.

There is nothing you can do about this without access to a clock that is at least as precise as the GPS satellite's multi-million-dollar onboard clock, which you then somehow keep correctly synchronized at all times.

There are some things that can be done to detect rebroadcast in the RF domain by looking at time of arrival across an antenna array, but again, that's not going to happen in a cell phone or wrist appliance.

There are some techniques that are used to discern direct path signals from multipath ones which involve tracking the lower power level signals, but rebroadcasters make sure they are radiating enough power to put that technique outside the dynamic range of the receiver.

[pps43]

Back of the envelope. The distance between Vnukovo airport and Kremlin is 30 km, speed of light is 300,000 km/s, time delay is 10^-4 seconds. Let's say it takes the moving car 100 seconds to get from outside the jamming area to inside. So receiver clock has to drift less than that. A year is pi * 10^7 seconds, so in a year receiver clock should drift by less than pi*10^(7-4-2), or approximately 30 seconds. My wristwatch can do better.

[lostmsu]

Why not? Is the original signal is somehow not going through? If it does, it does not matter the other is stronger. It will arrive later with the same timestamp.

[atemerev]

Makes sense, thank you. I will think more about the problem.