Saturday, September 26, 2015

Distance bounding protocols and physical layer security

Yesterday at the Summer School on Secure and Trustworthy Computing Srdjan Capkun gave an interesting talk on physical layer security and distance bounding protocols. I'll try to give some insights of why I found this talk particularly interesting.

Bounding the distance between two devices is becoming an increasingly important problem. Think of you contactless card, your car key. Crypto alone can not answer this questions. Indeed, this is a property of the underlying physical space, not of abstract data/identities. To solve that question, distance bounding protocols have been using time of flight measurements (mixed with some more classical crypto). The intuition is that if you know that the signal can travel from A to B in time less than t, then A and B are at distance at most t*speed of light. The talk wasn't so much about how to study formally such protocols (see [BCSS11] for example of such an analysis), but on the physical properties of the underlying systems needed for these protocols to actually work as intended.

The main assumption is that an adversary can not transmit information faster than the speed of light. This looks like quite a reasonable assumption, as the theory of relativity seems to be a hard problem to break 1. However, as the talk made quite clear, the situation is more complex. Outputing a bit on a channel is not an instantaneous operation, and time matters a lot here. A nano-light-second is about 15cm, and usually transmitting a bit takes micro/milli seconds...  This can practically be used in attacks where the adversary guesses the bit you're trying to send based on only part of the transmission. As a consequence it becomes essential for the length of a bit in that setting to be as low as possible. The technical details were somewhat lost on me, but, according to the speaker, it is possible to reduce this time to a few nano-seconds. This reduces the time of flight uncertainty to less than a meter[under the assumption that FTL travel is not possible], which is pretty good.

The second unusual problem tackled by this talk is as follows: assume that the machine that wants to prove its proximity to you is adversarial, can we still bound the distance? Distance measurement between A and B is done by A sending some signal to B and B answering a processed version of this signal back to A. A then computes the distance: (total time - processing time)*c/2. An adversarial machine can not cheat on the time of flight part, but it can cheat on the processing time. In the end, not only do we need short bits, we also need extremely short processing time. This means that for this approach to become practical, we need to build systems that receive, process and send signal in the span of nano-seconds. This talk provided with an example of such extremely efficient, completely analog computing/transmiting node. Interestingly this also entails that the kind of computations you can do in that framework is quite limited, making the problem extra interesting.

The talk was concluded by a fun use case: secure positioning. In a world where drones and self driving cars are getting more and more comon, the ability for someone to make your system believe it's in the wrong location, this might well become a real problem. GPS positioning is far from secure (see https://en.wikipedia.org/wiki/Iran%E2%80%93U.S._RQ-170_incident), and there is little hope that any similar non-interactive system will ever yield the integrity guarantees we need. This nicely justifies the need for secure distance bounding protocols with the appropriate architecture.

All in all, after this talk my impression is that the interactions between the physical layer and the protocol layer might very well be the key for future developements of secure distance bounding.

1 I guess that if you break it, distance bounding will anyway be the least of your problems