[guardian-dev] Discovery and user rights

[Yaron Goland]

Guardian Folks,


First off I sincerely apologize if this is the wrong mailing list to bring this issue up on. I know y'all are working in this area and so I was hoping we might share notes. But if this isn't the right place please tell me and I promise to cease and desist.


Right now I'm working on an design for how to use technologies like BLE to enable discovery in ways that respect user rights and don't kill user batteries.


To this end I've written (and will soon publish) a Users Bill of Rights for discovery based on Kim Cameron's Laws of Identity. One of the key rights is the right to decide who can discover you.


For example, imagine that you are part of a group of 100 or 200 people. It's a big discussion list. The contents of the list are being passed around via BLE/Wi-Fi. Specifically, BLE is used to discover people around you and if they aren't people you have sent your post to then you will contact them over Wi-Fi Direct (or Bluetooth or Multi-Peer Connectivity or whatever) to pass the data.


However there is someone in the group who has been harassing you and you don't want them to be able to find you via your telephone. In other words, you don't want your phone to tell them you are "in the area". So you go to your app and say "Exclude person X from notifications".


Now you post to that group of 100 or 200 people. In theory if your phone discovers someone who is a member of the group who you haven't already sent a copy of the post to then your phone should transmit it automatically.


The easiest way to do all of this is to just announce your identity (in our case a public key). That way if you see someone else's public key that you know you haven't updated yet then your device can contact them. But of course the inverse is a big problem. That is, if your phone is constantly advertising your public key then the person you want to exclude will see it and know you are in the area.


In theory the answer to this is to not advertise your key directly but rather to take your key and then encrypt it with the keys of the people you are trying to reach. In other words if you want to send out 200 updates then you would advertise, over BLE, 200 values. Each value is your identity encrypted with each person's key.


Which means that someone receiving your advertisement would see 200 values and have no idea if any of those values are for them. So they would have to try to decrypt each and every one using their private key to see if any match. If they do then they know who is looking for them.


The benefit of this approach is that if someone is advertising out they can simply not advertise to any member of the group they have excluded. Similarly if someone receives an advertisement from someone they excluded then they can just ignore it.


The problem is that this approach will almost certainly end up being a DOS attack on the low bandwidth BLE channel and potentially turn each device into a toaster oven as it tries to process potentially hundreds of tokens from 10 or 20 different sources (depending on how many devices are in range).


BLE is unbelievably slow. In practice I'm told that you aren't going to get much about 35KB/s and that's on a clear channel (which this isn't).


Furthermore we are processing these trial decryptions on battery powered devices. The good news is that modern phones generally use processors that have built in support for encryption operators. But I'm not clear how much of modern crypto software for iOS/Android actually uses those instructions. Even so, performing literally 1000s of public key decryptions over a period of a few hours isn't going to make anyone happy.


So I did think of an optimization. The optimization is that we could try to create pairwise keys between all members of the group. In that case what someone would advertise is some value encrypted with the key shared with that person. We could then use something like AES-128/GCM to do the encryption. This has a couple of benefits. The encrypted value instead of being measured in K as it would with say RSA 4K keys, would instead be around 40 or so bytes. Also the expense of "testing" each value will go way down, especially if we use code that supports the ARM processor's support for AES. [1]


AES-128/GCM/SHA-256 is what higher end TLS implementations use and mobile processors these days are largely optimized to handle it quickly for that reason. But to be fair the performance profile is likely to be very different than TLS because we are talking about large numbers of short encryptions/decryptions and most of those are going to fail. Unexpected results do awful things to desktop processor pipelines, I don't know enough about ARM's architecture to know what to expect. But I suspect it won't be pretty.






[1] Another option would be use to HMAC-SHA256 but I think this would require an initialization vector to make the resulting hash not be invariant and thus act as a beacon. I'm not clear if this would really provide any meaningful savings.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mayfirst.org/pipermail/guardian-dev/attachments/20150420/50fc42d3/attachment.html>