Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

First time poster here, hope to be around more often.

I'm in need of a cryptographically secure 'stamping' system that allows not only time but also location to be attached to data, while still resistant to forgery. However, short of altering the very GPS protocol itself, I can't think of a way to do it!

It may be entirely a lost cause here, but is there a way that I may not have heard of/thought up in which this could be achieved? Maybe something along the lines of how RFC 3161 works?

Your thoughts, comments, even crazy ideas are all much appreciated!

TC

Clarification (as below): Sorry about the question vagueness. I'm meaning for, say, a mobile device to attain a 'geostamping signature' of sorts cryptographically proving that the device was at "lat x long y" coordinates at a specific time T when it sent some message m to a central server, similar to how you can currently prove that m existed in a certain state at time T by hashing it and sending the hash to a timestamping service. I can see how that was badly worded, I'm sorry!

share|improve this question
3  
Interesting topic, but the question feels too vague. Timestamping proves “I know this data at time T”. A big difference between time and space is that you can't send data back in time. Is “I” a device in your problem, or can it be a botnet? Can “I” have accomplices? Are you willing to trust infrastructure (GPS, cell phone towers, …)? Do you trust the device on which the data resides? Do you have some trusted third party under your control? –  Gilles Aug 7 '11 at 10:57
1  
Time-stamping is useful because it can prove for example that a person wrote an essay on a certain day. Alice writes a magazine article on January 1st and has it time stamped. Bob writes a very similar article on January 7th and then publishes the article on January 14th. Alice publishes her article on January 20th. Bob accuses Alice of plagiarism. Alice uses the time-stamp to prove she could not have plagiarized. What problem are you hoping to solve with geographic time stamps? Whay use is proving a certain piece of data was at a certain place at a certain time? –  this.josh Aug 8 '11 at 4:54
    
Hi @TrojanCentaur, welcome to the site, and thanks for this interesting question! –  AviD Aug 9 '11 at 12:38
    
Sorry about the question vagueness. I'm meaning for, say, a mobile device to attain a 'geostamping signature' of sorts cryptographically proving that the device was at "lat x long y" coordinates at a specific time when it sent some message m to a central server, similar to how you can currently prove that m existed in a certain state at time T by hashing it and sending the hash to a timestamping service. We can assume that the device itself isn't trustworthy, but the infrastructure is (likely, they'll be doing the signing). I can see how that was badly worded though, I'm sorry! –  TrojanCentaur Aug 13 '11 at 4:20
add comment

2 Answers

up vote 9 down vote accepted

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.

share|improve this answer
    
Sorry it took so long to get around to reading this! Definitely given me a far greater insight into the problem, and certainly not something I'm going to be able to solve for the ideas I had in mind. The alternate method you specified is probably closest to what I had in mind as a possible solution, but again, clearly infeasible unless in a rather localized area. It has been an extremely interesting read though, something I might muse over for a few days yet! Thank you for such a comprehensive and through response! –  TrojanCentaur Aug 13 '11 at 3:42
add comment

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.

share|improve this answer
    
Actually GPS has Anti-spoofing build into the protocol, but it has been turned off as it is tied to Selective Availability and turning it on would render commercial GPS recievers useless. –  this.josh Aug 8 '11 at 4:43
    
It wasn't so much the authenticity of the GPS signal, more the authenticity of the geographic location of a specific device, for example, making sure a user with, say, a mobile app couldn't simply send false data to a server about their current location. Researching Galileo now though, looks very interesting! Sadly, I'm not sure this will be available anywhere aside from Europe (I myself live in New Zealand)... –  TrojanCentaur Aug 13 '11 at 3:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.