LoKI: Location-based PKI for Social Networks Randy Baden Introduction Decentralized online social networks (OSNs), if they seek to provide cryptographic security and privacy, have several fundamental key distribution problems. Even a system like Persona ends up falling back on the assumption that there exists a public key infrastructure (PKI), that is, that each user has a publicly known key that identifies her. For many systems, a PKI can be realized with a trusted third party called a certificate authority (CA), who issues certificates attesting to the validity of keys. This solution adequate for something like the world wide web, where it is (comparatively) easy to verify the identities of major companies. OSNs present a remarkable challenge here: no trusted third party will be able to verify every user of the OSN. Instead we rely on users to identify their immediate friends, as we did in Bond Breaker. We can connect these one-hop identity verifications in a graph to identify still more users, effectively bootstrapping a PKI for our network. This notion of one-hop exchanges is not new, but in the past it relied on manual, in-person key exchanges which did not lead to widespread adoption. Our goal with Bond Breaker, and with LoKI, is to provide technical means for users to easily and securely exchange keys over an insecure channel such as the Internet. Bond Breaker relies on shared knowledge between pairs of users, where one user will ask a question that they think only the other user can answer; if the user can answer, the identification is successful. This idea forms the basis for LoKI. The limitations of Bond Breaker are two-fold: it can be difficult for users to come up with a question to which no attacker can guess the question, and it can be difficult for users to come up with a question at all for acquaintances. What Bond Breaker lacks in security and completeness, LoKI attempts to provide. If two users who would want to friend each other on the OSN are carrying mobile phones, we can exchange secrets between their devices during real world meetings that can later be used as shared knowledge along the lines of Bond Breaker. By reducing the problem to concrete pieces of data instead of potentially ambiguous English questions and answers, the technique becomes much more accurate and secure, and we have a clear understanding of how hard it is for an attacker to guess the secret. Our solution replaces the questions and answers from Bond Breaker with the user's recollection of when real-world meetings occurred, which we believe is much easier for users to handle. If you're like us, then you likely have some questions at this point about the practicality of LoKI: How often do OSN friends really meet up in real life? This is a question that we're trying to answer with the Locus project. Our hypothesis is that it is common for a fraction of a user's friends in general. What resources will this use on my phone if I have to run this all the time? To approximate this, we are looking at mobile trace data to estimate how many mobile devices a typical phone is nearby during normal usage. This will give us an idea of how many secrets the phone will need to store for how long, how much space that will consume, and what the power costs are for communicating with each of these devices periodically. How do I tell the difference between two people I met at the same time, especially if one of them is an attacker? Currently our best solution to this is to use multiple meeting times, enough to ensure uniqueness. We are considering other ways of using the phone's sensors to attempt to reconstruct the scene at the time, so the user can have more information about which device is which. For instance, the phone could advertise that it received a phone call a few minutes ago when it shares its secret, and the user might remember that her friend took a phone call during their meeting. We will update this page when the results are in. There are other problems to consider though... High-Level Design of LoKI Unfortunately, though it sounds like it should be easy to just swap secrets between two general mobile devices, there are many complications. We have been focusing primarily on the Android platform, though we believe that similar constraints exist for the iOS platform as well. Since we want to have phones communicate when they are near each other, Bluetooth seems like the obvious choice of communication technology. It uses lower power than the alternatives and it is a physical means of verifying proximity. The Android API, however, does not allow phones to enter Bluetooth discoverable mode without user confirmation, for security reasons. Since we want the application to run continuously in the background even on non-rooted phones, this presents a dilemma: neither phone can find the other. The problem ultimately boils down to having one device discover the Bluetooth MAC address of the other device; once this is done, communication can be established and the secrets can be shared using either the newer versions of the public Android API or some Java hacks (that do not require rooting) for older versions. After considering the capabilities of the Android phones, we dismissed Bluetooth and Wifi broadcasts as the channel over which to announce Bluetooth MAC addresses, instead settling on a rendezvous service somewhere in the cloud. This service listens for (cryptographically hidden) reports of location tags corresponding to Bluetooth MAC addresses, returning all of the encrypted MAC addresses that should be nearby the given device. The device can reconstruct the MAC address only if they know the correct location tags. Due to the limitations of the Android platform, the only location tags that we found to be usable for our purposes are the MAC addresses of nearby Wifi access points and of nearby discoverable Bluetooth devices. The ultimate system looks something like Figure 1. Figure 1: Overview of the LoKI system. Two devices are thought to be nearby if they observe the same MAC addresses.