Apple and Google Contact Tracing - Part 2

April 11, 2020

This is part 2 - continuing from yesterday’s post about the implementation choice of bluetooth. This part 2 post is specifically to discuss a breakdown of the encryption implementation.

I thought it was pretty interesting that Google chose to use homomorphic encrpytion. First time I have seen that from them.

Here is a great breakdown of how it works from Moxie Marlinspike - creator of Signal:

3) Your device keeps track of all "proximity IDs" it sees.

4) If someone tests positive, they choose to publish their (previously secretly) "daily tracing keys."

5) Your device frequently DLs all published daily tracing keys and KDFs to see if they match recorded proximity IDs.
— Moxie Marlinspike (@moxie) April 10, 2020

The “daily tracing key”

The “daily tracing key” is used to create fingerprints for your device every 15 minutes. That fingerprint is known as a proximity identifier… You will leave your fingerprint wherever you go as you move around throughout your day. You will fingerprint other people’s apps as we all become a distributed data-collection center. If someone tests positive, then they will need to publish their “daily tracing keys” which will now be broadcasted to all other devices to let them know if they came into contact with that unknown person.

So first obvious caveat is that this is "private" (or at least not worse than BTLE), *until* the moment you test positive.

At that point all of your BTLE mac addrs over the previous period become linkable. Why do they change to begin with? Because tracking is already a problem.
— Moxie Marlinspike (@moxie) April 10, 2020

So it takes BTLE privacy a ~step back. I don't see why all of the existing beacon tracking tech wouldn't incorporate this into their stacks.

At that point adtech (at minimum) probably knows who you are, where you've been, and that you are covid+.
— Moxie Marlinspike (@moxie) April 10, 2020

“Privacy”

As soon as someone tests positive, they are essentially giving up all privacy about where they went and who they saw… Additionally, there will be beacons put up by stores, governments, and even independent researchers to gather fingerprints as people move about public spaces.

Second caveat is that it seems likely location data would have to be combined with what the device framework gives you.

Published keys are 16 bytes, one for each day. If moderate numbers of smartphone users are infected in any given week, that's 100s of MBs for all phones to DL.
— Moxie Marlinspike (@moxie) April 10, 2020

That seems untenable. So to be usable, published keys would likely need to be delivered in a more 'targeted' way, which probably means... location data.
— Moxie Marlinspike (@moxie) April 10, 2020

Third caveat is that it seems likely some kind of PII would have to be combined with what the device framework gives you.

Keys published by a device have to then be in turn "published" to *all* devices in the world. That's a major DoS vector!
— Moxie Marlinspike (@moxie) April 10, 2020

If anyone can anonymously blast up keys, they can create a situation where there's GBs of data for all devices in the world to retrieve and compute. There would likely need to be some kind of rate limiting on a combination of stable IDs (phone number, IP, etc) to prevent it.
— Moxie Marlinspike (@moxie) April 10, 2020

Not to mention the "prank" aspect of being able to light up everyone you've been near's devices with "you've been exposed to covid" (without them knowing you're the culprit) at any time, without some kind of pretty heavy manual ID/result verification at the moment of reporting.
— Moxie Marlinspike (@moxie) April 10, 2020

All that aside, these APIs are novel in terms of what becomes possible from the app layer.

I'm not super optimistic about opt-in contact tracing becoming a major factor, but I do kind of anticipate that someone will end up using this for some other interesting thing.
— Moxie Marlinspike (@moxie) April 10, 2020