News for hackers. Stuff that matters.
Re:Can we stop Covid-19 using Bluetooth? by nexuist on Saturday March 07, 2020 @06:38PM (#22515055)
Not sure OP is the same as the GitHub developer, but I want to applaud whoever took the time to write out this idea in a professional yet understandable manner. I had fun reading the paper.

Unfortunately this idea is (mostly) dead in the water if it sticks with its current implementation. The reason is that both Android and iOS now engage in MAC address randomization specifically to prevent being tracked by their unique IDs. This "feature" was previously commercialized by stores and private surveillance to track people moving around in a city or indoor building.

Fixing this is not impossible. Instead of Bluetooth tracking, the app could simply just record your location every poll update and save it locally. There is no invasion of privacy if the location file is never uploaded to the cloud. When someone tests positive, they could just have their location file uploaded (anonymously) and every device could cross check its location history with the infected person's.

Technology is likely not the barrier here. Notifying and training medical personnel to effectively use the app is, and getting the general public to "buy in" will cost an absolute fortune (in advertising dollars) for little to no return. This is one of those network paradox problems where you need lots of people for the network to be useful, but the network has to be useful to attract lots of people. How do you solve that?

Re:Can we stop Covid-19 using Bluetooth? by thanksforfish on Saturday March 07, 2020 @08:41PM (#22515692)
> they could just have their location file uploaded (anonymously)

Anonymity is going to be hard, even with traditional methods, but I don't think a person's location history can ever be anonymous. Especially when presented with timestamps and spanning days. People generally spend a lot of time, or at least their night, in their home.

> This is one of those network paradox problems where you need lots of people for the network to be useful, but the network has to be useful to attract lots of people. How do you solve that?

Bake it into an existing app that already has the network, I.E. Facebook.

Re:Can we stop Covid-19 using Bluetooth? by georgeam on Sunday March 08, 2020 @12:59AM (#22516578)
In principle it could be installed as a system/default app on Android and iOS by Google and Apple respectively. Even more reach for people that haven't installed Facebook.
Re:Can we stop Covid-19 using Bluetooth? by c22 on Sunday March 08, 2020 @01:40AM (#22516674)
I think you can get around this. Break the physical space up into blocks, say 100' square. Break the time component into 1 hour blocks. Concatenate the space and time components and hash them, then upload the hashes. If someone wants to see if they've potentially been exposed they can just hash their own time/location history and see if it gets a hit against the database.
Re:Can we stop Covid-19 using Bluetooth? by sunemai on Sunday March 08, 2020 @09:37AM (#22517941)
If you are able to check whether you've been in a "dangerous" space-time box yourself, then you are probably also able to check where these boxes are, I suppose? One way would be brute force hashing all possible space-time blocks and comparing with the public hashed list. This mechanism was why I abandoned the space-time box approach to begin with - but if you have an idea for a workaround, please get in touch!
Re:Can we stop Covid-19 using Bluetooth? by c22 on Sunday March 08, 2020 @10:21PM (#22522360)
You could make it a bit more robust by requiring clients to upload a minimum number of unique hashes with their query then respond only with an "exposed" or "not exposed" response. Then you can check for clients that are repeatedly uploading the same hashes to weed out brute forcers.

I think it would be pretty impractical to brute force all possible space-time blocks. Even if you just wanted to look at the state of California over 24 hours you're looking at 1.0952599e+12 hashes [0]. Say your rig can try 500k hashes a second, that's still almost a month. So now you know the rough locations of every infected person in California over the course of one day, you still have to disentangle the movements of overlapping users. You can make this even harder by requiring people to loiter in a space box for a minimum amount of time before creating an entry, so travel by bike/train/plane/automobile wont be tracked at all.

Clearly the scheme is resistant against mass de-anonymization, but if you knew some specific locations where you thought a specific person might go you could target those space-boxes and, assuming there are not many other infected users in the area, get a sense of when that person was at those places.

[0] 163,696 sq miles = 4.563583e+12 sqft = 45,635,830,000 100sqft space boxes * 24 = 1.0952599e+12

Re:Can we stop Covid-19 using Bluetooth? by thanksforfish on Tuesday March 10, 2020 @12:09PM (#22536664)
Ah good point about overlapping location data for sick users, that would add ambiguity.

This approach still puts a lot of trust in the server. Every client needs to upload their hashes to the server, so if the group running the server wanted to reverse the hashes they'd get everyone's location, not just sick people. The server would also know which hashes were popular, indicating that they are crowded areas like a city or event center. From a tracking perspective the fact that two people were in the same location is useful to start making inferences, even if the location isn't known.

Re:Can we stop Covid-19 using Bluetooth? by thanksforfish on Sunday March 08, 2020 @08:11PM (#22521689)
It's a "hash of a small search space" problem.

Here's the best I got:

1. Each client will sha256 hash their space-time box (lat,lon,timestamp each rounded to some suitable size). This is their space-time box hash. 2. Each client takes the first N bytes of their space-time box hash and registers it with a service. This must occur within M hours, to limit after the fact analysis. These are privately stored on the server and deleted after R days (R ~= 14 for corona virus IIRC). 3. Each person can blacklist certain places, like their home from getting reported. When home you probably know who you interact with, and don't need software to help. Also times, most people can probably recall who they sleep with so bedtime->alarm doesn't need to be tracked. 4. Someone gets sick. They can now choose to report and share their fine grained location history with the service. Ideally people choose to report and share for the sake of public health. They (or realistically a trusted healthy person) can shift through the location stats to see if there's any locations to skip (again, at home and sleeping times probably don't need to be reported as most folks recall who was there). 5. The service records the fine grained location data and notifies the app for everyone who reported a space-time hash prefix that matches. This will notify lots of non-matches as we only reported the first N bytes. 6. Each notified client then looks at their space-time hash and sends additional bytes to the service, checking if they match one by one. If a mismatch is found the client stops. The service refuses to allow this type of lookup except from clients that previously registered a matching hash prefix.

Someone needs to do the math to pick a good value for N and others.

This provides some protection from the service deanonymizing people and tries hard to only share matches with clients that were matched.

How's that work?

Re:Can we stop Covid-19 using Bluetooth? by c22 on Sunday March 08, 2020 @09:57PM (#22522246)
I like your added protections. Allowing people to filter their reported data might be enough to convince people to use it even without additional security.

Don't use sha256 for the hash, we need a slow hash like bcrypt or scrypt. Since entries only need to be updated when moving between time boxes or space boxes we can in fact configure this to be quite slow.

Re:Can we stop Covid-19 using Bluetooth? by LyndsySimon on Sunday March 08, 2020 @04:49AM (#22517043)
In a sense urban area, that would help. In small towns, or out in the country? Not a chance.
Re:Can we stop Covid-19 using Bluetooth? by c22 on Sunday March 08, 2020 @08:20AM (#22517665)
Why not? To correlate any meaningful data an attacker would have to reverse a significant portion of the database. The most serious attack I see would be a brute force over time of Bob's location segment. At most this gives Eve retroactive information about when Bob was home after Bob has tested positive and uploaded his data. It still doesn't give any insight into where Bob went when he left except perhaps in extremely sparse areas. Our imaginary service can help reduce the impact of this attack further by rate limiting requests and discarding old data as soon as it's no longer relevant.

This failure mode is probably still less intrusive than the current system of asking people in quarantine to detail all of their recent movements.

Ironically, you might achieve better anonymity by making the time and space boundaries smaller, but at the expense of more false negatives when checking for exposure.

Re:Can we stop Covid-19 using Bluetooth? by jackweirdy on Saturday March 07, 2020 @08:23PM (#22515599)
I’m not sure if Bluetooth MAC randomisation is different, but on iOS WiFi MAC randomisation only happens when location services are disabled: https://9to5mac.com/2014/09/26/more-details-on-how-ios-8s-ma...
Re:Can we stop Covid-19 using Bluetooth? by sunemai on Sunday March 08, 2020 @10:14AM (#22518114)
The "buy in" issue is why I consider using Denmark (which is where I live) as an initial test area before internationalization: Danes are generally well educated, and they have a high trust in public authorities compared to many other countries. The use of open source software is also widespread in Denmark.

So an app/server solution developed with 100% transparency on GitHub could easily be pushed to everybody by public authorities - under the critical assumption that we can both make it work technically, and make it completely anonymous.

Just for reference, the same "scale problem" is also the challenge with ordinary vaccines, as I understand it:

They don't really need to give 100% protection to each individual. The critical point is that if a large enough percentage of the population has the vaccine, the R_0 parameter of the given disease will drop below 1, and the exponential spreading turns into an exponential decline.

Re:Can we stop Covid-19 using Bluetooth? by mycall on Saturday March 07, 2020 @09:56PM (#22516031)
You could do an idea pull request.
Re:Can we stop Covid-19 using Bluetooth? by nexuist on Saturday March 07, 2020 @10:49PM (#22516229)
Good idea. Just did!