How Apple's and Google’s Coronavirus Contact Tracing System Works
@zntfdr
This article is based on the official preliminary technical specifications.
Last Friday Apple and Google have announced a new partnership to fight against the current COVID-19 pandemic.
This partnership comes in two waves:
- Next month, May 2020, the companies will release an API, for each platform, that will enable apps from public health authorities to assist in enabling contact tracing access. This will require users to download such apps from the platform app stores.
- In the coming months both companies will embed a Contact Tracing system at the OS level.
This article focuses on the second point.
If you'd like a less technical article, please refer to this.
Contact Tracing TL;DR
Contact Tracing alerts participants of possible exposure to someone who has been positively diagnosed with corona virus.
In other words, Contact Tracing reports when/if our device has been in the proximity of a person diagnosed with corona virus device.
Technical Details
Inter-Device Communication
Contact Tracing uses Bluetooth LE (Low Energy) for inter-device communication, all iPhones from the iPhone 4S are equipped with it, however I believe Contact Tracing will be released as an iOS 13-only update, which means only iPhones from the iPhone 6s (and 6s Plus) are eligible.
Bluethooth LE has a theoretical maximum distance/range of 100m, however the effective range is far less than that.
Similar to WiFi device discovery, the Contact Tracing is based on advertising, a.k.a. Bluetooth payloads that our device sends out to anyone within reach, and scanning, which is receiving and reading other devices advertisements.
No connection between devices is ever made:
all devices will literally throw messages out in the air and read whatever comes in.
Advertising
Advertisements will happen at a high frequency: the current specification suggests to send out one advertisement every 200-270 milliseconds.
Scanning
While advertisements happen with high frequency, the scanning interval and window only need to have sufficient coverage to discover nearby advertisers within 5 minutes.
Which means that the scanning approach is opportunistic: Contact Tracing scans will piggyback existing device wakes and scan windows (our devices are constantly scanning for WiFi networks and Bluetooth devices), and will do so at least once every 5 minutes.
Advertising Message
The whole system is based on devices Bluetooth advertisements. These advertisements are all the same for all devices of all platforms, the only difference is a traceable key.
Contact Tracing defines three keys:
- Tracing Key An unique key that is generated once per device.
- Daily Tracing Key A key derived from the Tracing Key, that changes every 24 hours.
- Rolling Proximity Identifier A key derived from the Daily Tracing Key, that changes every 10 to 20 minutes.
The Bluetooth advertisement will always only contain the current Rolling Proximity Identifier key.
Why does the system need three keys? It doesn't:Contact Tracing would work fine with one unique key per device. These three levels are there for user privacy and safety: - The Tracing Key never leaves the device. - The Daily (Tracing) Key change is there for user privacy. - The ~15 minutes (Rolling Proximity) Key change is there to prevent wireless tracking.
Scanning Behavior
The scanning part translates into collecting other devices Rolling Proximity Identifier keys:
such keys are stored and processed exclusively on device.
Putting It All Together
What Happens When A User Tests Positive for COVID-19
When a user tests positive, it will let the system know (it's unclear how at this stage, I assume via a new app or via the platform Health app) and the relevant user's device Daily Tracing Keys will be uploaded to a Diagnosis Server, along with the relative days of each key.
This is the only possible way for the Daily Tracing Keys to leave the device.
A Diagnosis Server is a server that aggregates all Daily Tracing Keys from the users who tested positive, and distributes them to all the users devices (of all platforms) who are using Contact Tracing.
Why The Daily Tracing Keys Are Uploaded?
A Rolling Proximity Identifier is derived by its Daily Tracing Key and a 10-minute window (remember that this key changes every 10 to 20 minutes?).
Given a Daily Tracing Key, we can obtain the complete sequence of Rolling Proximity Identifier keys for that day.
Identify Any Exposure
At this point we know that:
- Each device collects all Rolling Proximity Identifiers advertised by other nearby devices.
- Daily Tracing Keys from diagnosed users devices are uploaded to a Diagnosis Server.
- Given a Daily Tracing Key, we can obtain all its associated Rolling Proximity Identifiers.
Every device will frequently (it's unclear how frequent at the moment) fetch the list of Daily Tracing Keys from the Diagnosis Server.
The last step is to compute all Rolling Proximity Identifier sequences for each Daily Tracing Keys fetched from the Diagnosis Server, and try to find a match with the local Rolling Proximity Identifiers collection.
If a match is found, the user will be alerted. The match information never leaves the device.
Conclusions
In this article we've seen how the Coronavirus Contact Tracing works, for more detailed information please refer to the official Bluetooth and Cryptography specifications.
The system is not flawless and can report false positives, albeit chances are low.
For example: Additional validation can be done on the match step to prevent some false positives: if a computed Rolling Proximity Identifier associated with a 11:00 pm - 11:10 pm interval matches a Rolling Proximity Identifier collected at 8:00 am, chances are this is a coincidence and not a real match.
One more concerning aspect of this system is the fact that all the (very good) privacy/security enforcements come with the cost of a moderation-less system: Diagnosis Server do not store any data beside the given keys and dates. Malicious actors may flood the servers with fake cases.
Please let me know if I missed something that would prevent this behavior.
2020/04/14 update: during a press briefing on Monday April 13th the companies have announced that they are "considering working with healthcare operators to incorporate a lockstep test verification", this would solve the issue raised above.
Lastly, this system will work only if everybody does their part:
once the system is available, please opt-in and, more importantly, #stayAtHome.
Thank you for reading and stay tuned for more articles!
References: