From: Paul_Koning/US/3Com%3COM@smtp1.isd.3com.com
Date: Sat, 13 Apr 1996 19:59:29 +0800
To: timd@consensus.com
Subject: Re: No matter where you go, there they are.
Message-ID: <9604122226.AA4262@>
MIME-Version: 1.0
Content-Type: text/plain


>While we may disagree with Ms. Denning on a number of political matters,
>she's quite intelligent; I suspect the paper is well-founded.

Yes, that was my initial reaction too, but the content just don't support that.
I suspect this is a case of a person well-qualified in one area (crypto)
working in very different area (GPS) where she is not qualified and does
not understand what is going on.

>GPS receivers are line-of-sight only; only a small portion of the earth can
>see the same satellites.

Well, sort of.  The satellites are up at 11,000 miles, which makes for a large
footprint.  You'd certainly see most of the same satellites from several
states away.

>It might be possible to seperately record the signals from several
>different satellites, delay them each just the right amount of time, and
>then recombine them to simulate being at another nearby location (within
>several hundred miles). 

Right, that's what several of us have been saying.

>However, this might not be possible. Examine the
>following quote from Denning's paper:
>
>:The location signature is virtually impossible to forge at the
>:required accuracy. This is because the GPS observations at any given time
>:are essentially unpredictable to high precision due to subtle satellite
>:orbit perturbations, which are unknowable in real-time, and intentional
>:signal instabilities  (dithering) imposed by the U.S. Department of Defense
>:selective availability (SA) security policy.

Sure, but that is nonsense.  Here's why.

The time delay you need to introduce a 200 mile shift is 1 ms.  The effects
Denning et al. are talking about are LOW FREQUENCY effects.  This is
obvious for orbital perturbations, since we're talking about small motions of
large heavy objects here, and it is also true for the S/A dither. Indeed
it has to be that way, since any high frequency jitter would prevent the
receiver from locking on the spread spectrum code that's at the core of
how GPS works.  In other words, at the millisecond  level, none of those 
effects exist.

Re Hal's comments:
>Note however that Denning did not mention the Internet in her spiel.
>
>I believe her method would be workable across lower latency networks, if such
>exist or eventually exist.  Perhaps direct connections or leased lines would
>provide low enough latency; I don't know.  In any case networks are likely
>to become faster in the future and her method might eventually work.
>Actually the issue is not just latency but whether the latency can be
>lied about, and for some kinds of networks that would be harder.

What a checking system actually observes is: at time T2 it receives
a message that claims to have been generated at time T1 by a system
at location X.  It would accept the authentication as valid if the elapsed
time T2-T1 is small enough to be believable.  How small this is depends
on (a) the transmission latency, (b) the processing delay in X and in
the checker.  

There are two flavors of attack on this:

1. Attacker Y uses the real-time signals from the satellites, delayed as
needed.  It sends those after processing, just as X would have done
(except that X doesn't insert the processing delay).  The elapsed time
seen by the checker differs from the case of X by the sum of the
processing delay and the incremental transmission latency (since Y
is at a different place than X, so its connection to the checker may have
either less or more latency).

This fools the checker if the incremental latency is within its tolerance.
Suppose that I'm using a LAN -- in that case a transmit delay on the
order of 1 ms is plausible.  X and Y would be about the same (of course
it has hard for Y to get on the LAN unobserved...).  If X is less than
20 miles away, the processing delay is under 100 microseconds, which
is "in the noise".

If I'm in a WAN, then the latency is likely to be greater, but even if is is
1 ms, I can be many miles away before it becomes obvious.

The above of course assumes that the signal processing is done in
hardware (or fast DSP) so it can indeed be done in well under 1 ms.
Not a big deal...  That seems to be one Denning mistake, the thinking
only of replay in the sense of long delayed spoofing messages.

2. Attacker Y synchronizes to the satellites but constructs a signal
locally that effectively "anticipates" what the satellite is about to send.
This allows it to get the effect of a negative delay (thus avoiding
the "node in the ground" problem).  Since the signal is entirely
predictable at the few-ms level, this is not difficult, though it requires
a bit more effort than the simple delay approach.  This way Y can
construct a signal acceptable to the checker, even if its transmit latency
to the checker is greater than it is for X.  It simply anticipates by
the difference plus whatever it needs to fake the position.

Finally...

As Hal also pointed out, if the system allows users to have partial
sky view, then the attacker can avoid the need for negative delays
entirely by selecting satellites closer to him than to the legitimate
user.

For anyone interested in an intro to GPS, Trimble (one of the leading
companies in the industry) puts out some skinny paperbacks
with nice clear explanations.  They sometimes are a bit at
the "see Spot run" level, but they do have the correct story.

 paul

!-----------------------------------------------------------------------
! Paul Koning, NI1D, C-24183
! 3Com Corporation, 1-3A, 118 Turnpike Road, Southborough MA 01772 USA
! phone: +1 508 229 1695, fax: +1 508 490 5873
! email: paul_koning@isd.3com.com  or  paul_koning@3mail.3com.com
! Pgp:   27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "Be wary of strong drink.  It can make you shoot at tax collectors
!  -- and miss!"
!                -- Robert A. Heinlein, "The Notebooks of Lazarus Long"
!                   in "Time Enough for Love"