Also, the privacy and the finding are in direct opposition to each-other, which isn’t always a comfortable system dynamic.
On the one hand, a simple hash of ESSIDs near you, if you take all of them, is highly unlikely to ever match - radio strength varies and you’ll see stuff on the edges of your device pop in and out if you look at radio traces. So you need to limit the list.
However, if you limit the list, to say 3 ESSIDs, you’re well into rainbow table attack territory - if there are 100mm WiFi access points in the world, then you need 100mm^3 hashes - doable - and if you rough geoloc them first so that you’re not hashing out stuff more than a mile away from other APs, you’re down to “very manageable”.
At the same time, the question of “which 3” means that it’s going to be hard to ever get the same list, or at least you’re not in the one 9s territory of loc matching.
To do this without some sort of either trusted server or some sort of group key sharing (and therefore a totally different threat model) you’ll need to get some sort of location-aware hashing together, and I think also you’ll want to be able to get some sort of data from the local APs that’s not easily accessible elsewhere. Not sure what that is off the top of my head, but I bet there’s something in the WPS spec that you could hang off of.
So if you had the ability to be like “my hash puts me somewhere within this square (area) and only those of us here know that the secret salt for this minute is XXX” then I think you’d get back to the original goals of the project.
I bet that’s doable! Looking forward to v2
I thought about geo largely because it radically changes the order of magnitude of work necessary; it lets you segment ‘possible’ subsets of APs down to sets of say 100, not millions, and changes the combinatorics. A side effect is knowing a rough spatial location.
Off the top of my head, I don’t think that epochs alone make a big difference. If I want to see if you’ve been somewhere, or tell you I’m somewhere, why not take the 3-4 networks you mentioned, and forward hash them for the next million epochs?
Or, more ambitiously, why not take 3-4 networks each from the geo indexed clusters available at https://wigle.net/ and do the forward and backward epochs, letting me track where you’ve been and pretend to be near you any time in the future?
Wigle reports 1.7bn networks; a rough look at a suburban street near me shows most places have 10 in a reasonable range boundary; so call it 200mm “locations” with 128 segmented hashes, 250 billion hashes per epoch — I think we’re in the “seconds per epoch” range for a reasonable compute heavy server to cover the entire space.
Upshot - I think the salting needs to be something local / not predictable or stored remotely.
Hopefully these comments hit you right - I like the idea a lot - and I don’t fully understand the system - but as I understand it, the system does not offer privacy — I could replay any phone’s hashes against a system that cost a few dollars to reconstruct your location and time, if my understanding is correct.
Perhaps you might consider a pinsketch in the manner proposed for cryptographic biometric security. https://arxiv.org/abs/cs/0602007
I contributed to a fast implementation of the underlying algorithim: https://github.com/bitcoin-core/minisketch
With it two peers could compare their BSSID environments and learn ~nothing about each other unless they were nearly matching.
I can see how one could use it for location based key agreement for mutual authentication-- not as obvious to me how to apply it to privacy preserving location.
The latter would probably just best be accomplished by downloading the whole database, or (less optimally) using PIR to probe for the locations of single BSSIDs.
Out of curiosity, what's the motivation for Bitcoin-Core? Is it comparing mempool txs?
GPS does not work at all. I've always thought using the WiFi access points that have been installed on the underground could be a great addition to something like Citymapper to figure out where you are located even when there is no GPS.
(disclaimer: I am co-inventor at a previous employer, I don't get royalties for it, just reporting)
It opens you up to legal risk for knowingly infringing patents. If possible you never should look at a patent.
I thought "environmental fingerprints" were referring to something more elaborate, like a fingerprint of the local audio environment, or using the accelerometer to measure the local spacetime curvature.
