Secure Verification of Location Claims
by Naveen Sastry, Umesh Shankar and David Wagner
ACM WiSe 2003

Summary: In this paper, authors propose a lightweight protocol called
the "Echo", to provide in-region verification where the verifier
confirms if a mobile node is located within a region of interest or
not. This capability can be used as the basis of location-based access
control, which is gaining its utility as mobile and ubiquitous
computing keep gaining their ground into our everyday life.
Especially, location-based access control can be used as a very
effective bootstrapping method for further security operations, like
the initial key set-up in duckling paper or Balfanz's paper.

Main idea of the scheme is, first the prover who wishes to be verified
to be present in a region notifies a verifier. Then, the verifier
sends back a nonce to the prover through RF channel, which the prover
will send back right away through ultrasound channel. Based on the
observed time elapsed during the round-trip of the nonce, the verifier
can make an intelligent decision whether the prover is present within
the claimed region or not. The use of sound channel for the second
half is to reduce the error range in distance.  Description of remote
bugging attack for (sound,radio) case was fun!

Authors first presented the most basic scheme with a toy example, and
extended it to include processing delay, transmission delay, and
non-circular region. Then, they extend the protocol to include
multiple verifier to extend the coverage.

Echo protocol does not rely on cryptography, time synchronization, or
any prior agreement between the prover and the verifier like previous
solutions do. This protocol fits very well with the sensor network
environment too. By not relying on cryptography, computation and
storage resource were saved but more importantly Echo does not need
any a priori agreement, therefore perfectly fits baseball stadium app.


Pros:
1) Well written, good flow, clearly mentions assumptions, contributions.
2) Complex problem - they picked a simple solution that is easy to analyze
and extend. Defined metrics based on this, ROA, coverage.
3) Can apply well known results from theory? - bin packing, etc.
4) Very simple and light-weight solution

Cons:
1) Need to see some experiments on how big the ROA actually is for low
computational power devices. A few ms of work would shrink the ROA in
smaller rooms.
2) Proxy attack is not very hard to mount. Should have a countermeasure.
3) ROA is actually spherical rather than circular (rooms below and above)
4) Not really a new idea. e.g. Cricket, Active Badge, etc.
5) Contention for RF and ultrasound channel is not discussed. A very simple
back-off can ruin the whole timing. Is it practical in large areas? 
6) What if RF or ultrasound signals collide?
7) What is the application that suits the proposed approach? Is there any?


Discussion questions:

1. Is this open to a simple DoS attack? What if one makes the region
noisy enough so that the ultrasound will be garbled? Is it even
possible?  Can we force the SNR for the ultrasound to drop below a
certain threshold?

2. Can ultrasound packets(?) collide? Or does a prover have to compete
for the ultrasound channel(?)? What if two different provers wishes to
engage in the protocol at the same time with a same verifier, and with
different verifiers?

3. I don't like the way they covered the processing delay by reducing
the ROA. Any other way to handle it?

4. If delta_p is relatively large compared to a small R, can ROA be
shrunken down to null? What if that happens?

5. I do not understand the guessing attack very well. Say the
adversary guessed right the first N bits, then what? He has to guess
all the way until the full nonce is sent, right? Am I missing
something here?

6. How does a prover choose the verifier to use?

7. Is the "remote actuation" attack really that difficult compared to
remote bugging? Isn't it the other way? Also, isn't it violating their
own assumption of "no adversaries within R?"

9. Any innovative way to cover strangely-shaped regions? Another
interesting topic of study? :)

10. What happens if one of Vs is compromised? Any possible serious
damage?

11. Unless keyed Echo is used, V actually does not know "who" it's
talking to.  Is it really acceptable option?

12. What kind of analysis or evaluation did they miss? Anything else
you want to see before actually deploying this one in the field?

13. Did they miss any potential attacks?

Vote:
Strong Accept: 1
Weak Accept  : 9
Weak Reject  : 5
Strong Reject: 0