I never got very far with this idea beyond coming up with it, but whe thinking about unfakable calculable characteristics that could be used for locality verificacion, i could only come up with latency as the key characteristic. Based on some geographical threshold distance the speed of light gives a reasonable estimate of how much latency there ought to be when communicating with someone. So if you could issue a challenge and time the response, you should know someone is local to you or not.
Nearby peer discovery without GPS using environmental fingerprints
11–20 of 27 posts
Re: Nearby peer discovery without GPS using environmental fingerprints
#12Watch out, possibly similar to this patent: https://patentimages.storage.googleapis.com/e4/9b/4e/883a9df... (disclaimer: I am co-inventor at a previous employer, I don't get royalties for it, just reporting)
Thanks for the heads up! Good to know what's out there. Interesting that I independently arrived at something possibly similar.
Re: Nearby peer discovery without GPS using environmental fingerprints
#13TL;DR: it's just using the WiFi networks' names to decide whether you're close or not.
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.
Re: Nearby peer discovery without GPS using environmental fingerprints
#14Shameless plug: More than a decade ago, I wrote a paper [1] on how the random perturbations in the wireless channel between an ambient RF transmitter (FM radio, TV) to the two devices, allow nearby devices to authenticate locality because the perturbations are correlated only if they are nearby (where nearby is relative to the wavelength being monitored)
Re: Nearby peer discovery without GPS using environmental fingerprints
#15There are a couple of difficult cryptographic-type problems with this plan. (Which I like, by the way). I don’t think it’s privacy preserving, and I also don’t think it works well for finding shared locations as currently specified. 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 a…
Thanks for the feedback! Rainbow tables probably won't work here since the epoch (rounded to 5 minutes) salts everything, so precomputed tables would expire constantly. You would use use BSSIDs + SSID in real implementations. The MinHash part creates 128 hash values from the entire observed set, not a subset of 3, then LSH divides these into bands where similar sets collide probabilistically based on Jaccard similari…
Thanks for the detailed response! I completely missed the band division / similarity plan - I’ll read more thoroughly next time.
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.
Re: Nearby peer discovery without GPS using environmental fingerprints
#16[dead]
Re: Nearby peer discovery without GPS using environmental fingerprints
#17Earlier quoted context omitted.
Thanks for the feedback! Rainbow tables probably won't work here since the epoch (rounded to 5 minutes) salts everything, so precomputed tables would expire constantly. You would use use BSSIDs + SSID in real implementations. The MinHash part creates 128 hash values from the entire observed set, not a subset of 3, then LSH divides these into bands where similar sets collide probabilistically based on Jaccard similari…
Thanks for the detailed response! I completely missed the band division / similarity plan - I’ll read more thoroughly next time. 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…
I see, this sheds some new light on your initial concerns. I'm aware an attacker can keep pretending to be inside an environment once they've seen it. I wasn't accounting for a scenario where an attacker has a huge database for queries like coords -> list of wifi networks. I was under the assumption services like Wigle only provided the reverse lookup (wifi -> coords). Indeed an attacker could potentially reverse the LSH tags if it hashed the wifi environment within very small geofences. It's bit of a needle & haystack problem but not an impossible one with enough resources. I wouldn't say it's a perfect system and I don't mind it falling apart under scrutiny, I just found it an interesting idea so I really appreciate you thinking along here.
Edit: Maybe some preshared group hash (kinda beats the point), or combining multiple modalities (eg bluetooth, shared interests) or some kind of proof of work token could help mitigate some of these issues. I guess anything to reduce the time to attack helps in this case? Or anything that really pins down environment + time, like what smath described in his comment. In essence, the core idea of minhash + lsh works and it doesn't limit you to just wifi networks. The key is being able to grab a fingerprint that is unique enough and different enough each epoch. Wifi networks are just easy enough to grab vs something more low level like an APs beacon timing interval jitter or something.
Re: Nearby peer discovery without GPS using environmental fingerprints
#18[dead]
Re: Nearby peer discovery without GPS using environmental fingerprints
#19Watch out, possibly similar to this patent: https://patentimages.storage.googleapis.com/e4/9b/4e/883a9df... (disclaimer: I am co-inventor at a previous employer, I don't get royalties for it, just reporting)
Thanks for the heads up! Good to know what's out there. Interesting that I independently arrived at something possibly similar.
>Good to know what's out there.
It opens you up to legal risk for knowingly infringing patents. If possible you never should look at a patent.
Re: Nearby peer discovery without GPS using environmental fingerprints
#20TL;DR: it's just using the WiFi networks' names to decide whether you're close or not. 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.
It's not limited to WiFi networks and indeed the fingerprints you suggest would be a lot better because they would change significantly over time. The whole WiFi networks idea kinda stuck because it's an obvious an easy thing to grab from the environment using a mobile phone. An audio fingerprint would definitely be doable on mobile.