Geographic equivilent of RFC 3161 (X.509 PKI Time-stamp Protocol)

The question requires some effort at precise definitions.

Time Stamping is about proving the existence of some information at some date T. Data is just a bunch of 0 and 1, which have been known for millenia, so we need to define what we mean by: "some information which exists". We thus consider the notion of a message: a sequence of bits, with a beginning, an end, and precisely defined contents. A time stamp proves that at some date T, someone was envisioning said sequence as a whole.

In the case of RFC 3161 time stamps, this "envisioning" takes the form of a digest, computed over the message with a cryptographically secure hash function. The time stamping authority (TSA) receives the digest and computes a signature over a structure which contains the digest, and the current date and time (as the TSA knows it). Note the fine print: the TSA does not see the message itself, only a hash thereof; and the TSA has no way of knowing whether the hash value was really obtained from an invocation of the said hash function.

So the precise model is the following: as some date T', a message m and a time stamp are presented; the time stamp contains the date T and h(m) for some hash function h. This proves the existence of m at date T on the assumption that h is pre-image resistant: if h(m) existed at date T then m existed at date T since pre-image resistance means that it is not computationally feasible to find a m which matches a given pre-existing h(m). Also, the TSA must know the current date and time, and hold a private key, in ways which are resistant to tampering.

Location Stamping thus requires a definition of what you mean by "where the data is". In the case of time stamping, we rely on "envisioning" incarnated by the computation of a hash function over the message. Since data can be copied at will, it has no defined unique location, and is not inherently tied to a geographical place.

The GPS protocol is mostly irrelevant here. It is a one-way protocol: the satellites emit, but do not receive; and the sent messages contain no information whatsoever on where anything on Earth is actually located. Location is computed from the time of reception of the messages from several satellites (actually, the precise time lag between messages from pairs of satellites). The only locations that the GPS protocol really defines are those of the satellites themselves. So the information you want to certify, in a TSA-like way, is that you received some GPS messages with a specific lag. But a proof cannot be based on taking your word on it.

Therefore, the best you can hope for, is to have a device which:

• is tamper-resistant;
• knows (in an unforgeable way) its current location, as well as the current date and time;
• stores a private key for a signature algorithm;
• can receive an arbitrary message m;
• computes a signature over a structure which contains the current device location, the current date and time, and h(m) for a given hash function m.

It is important that the device receives m and computes h(m) itself, because you want to prove that the message m itself was at a given location. Also, verification now relies on collision resistance of h, instead of pre-image resistance (with a collision between m and m', the device would receive m and this proves nothing on where m' is at the same time).

There are practical issues. A TSA can be located in a secure environment, e.g. a guarded building; it receives requests and sends responses over some network. A location stamping device, on the other hand, must be "on the spot", and thus much more likely to be in an attacker-controlled environment. In particular, nothing guarantees that it receives real GPS messages at exactly the right time. To change the notion of the current location, the attacker just has to "delay" a bit some of the messages from the GPS satellites; since the GPS protocol is one-way, there is nothing which can be done against that at the protocol level.

Another solution implies using a mesh of base stations which receive a signal from the device you want to locate. The location stamping device would still hash the message, and then sign it, and send the signature to (secured) base stations. This would require a two-way protocol, so that each station could measure the precise time it took for the device to respond to a request. For instance, if the device takes precisely 5.12 ms to compute a signature, and the response from the device took 5.30 ms to be received by the station, then the station knows that the device must be within 27 km of the station (information travel is limited by the speed of light, i.e. 300000 km/s, and a roundtrip of 0.18 ms cannot be achieved if the total distance exceeds 54 km).

A mesh of base stations talking to a device: this looks like a "mobile phone" situation. But this solution requires specific stations able to time things down to the microsecond, for a mediocre final precision.

Summary: this looks hard.

As you say, you cannot change the signal from the GPS.

Actually I did not find any official way of assessing the authenticity of the GPS signal. It is possible, but I can't really know, that the GPS M-signal reserved to military uses, has some functionality to detect tampering of the signal. It is also know as being able to mitigate the risk of jamming.

The Galileo location system should bring authentication of geolocation. But it won't be operational before 2013.

There is other things you can do with the GPS to detect problems. I can't really tell you more about this because of non disclosure agreement. But you can check this page about the FP7 project ATLAS and the GSA page about it.

I should have some public document available. I need to check.