Contact Tracing with Android/iPhone

How the new Google/Apple partnership may help us get back to our normal routine

by Joe Honton Apr 12, 2020

A recent Twitter post from Tectonix GEO shows how the Covid-19 virus might have spread after an unnamed Ft. Lauderdale beach party dispersed and party-goers returned home from spring break.

On the face of it, the one minute video is educational. Surely if the party-goers had seen this beforehand, they would have behaved differently.

But beyond that, the tweet points to an alarming and creepy new understanding that our surveillance society is far more advanced that we ever thought.

So when Apple and Google announced a joint venture last week, to develop a new contact tracing protocol, many people were immediately suspicious. The goal of the venture is to automate the important field work that epidemiologists perform when they try to trace who may be a vector for the virus, and who may be in danger. To achieve that goal, the effort will enlist the voluntary data collection efforts of anyone with a smartphone.

Superficially this appears to be similar to other smartphone tracking apps, but underneath the covers is a brand new approach, one that guarantees anonymity and complete user control over their data.

In a nutshell, it works like this. When two people with contact tracing smartphones come in close proximity to each other, they seamlessly exchange information about the encounter via Bluetooth technology. Later when someone is diagnosed with the virus, their heath care provider, with the consent of the patient, releases that information, and anyone who has come in contact with the patient in the past two week is alerted to the fact. Potentially exposed people may then take proactive steps to get tested and self-isolate.

All of this happens anonymously via encrypted data. There is no master data key. No central database of encounters. No backdoors. No potential for nefarious usage.

For the skeptics, we can dig deeper into the spec, to see exactly how this level of privacy is ensured.

Data collection scenario

Consider a scenario where I take an Uber to the grocery store to buy some toilet paper. Here is the fictional timeline of events for May 15, 2020 (all times are PDT):

4:21 p.m. The Uber driver picks me up and we both have our smartphone's contact tracing enabled as we drive to the nearby Safeway.
4:51 p.m. I brush past a nearby shopper in the paper goods isle. Both of us have our smartphone's contact tracing enabled.
5:06 p.m. While waiting in the checkout line, the stranger behind me is close enough to potentially trigger an exchange of data, but that person has not enabled the feature on their smartphone.
5:11 p.m. The store clerk and I exchange pleasantries as my purchase is rung up. Both of us have our smartphone's contact tracing enabled.

For each of the three Bluetooth exchanges, my cellphone's contact tracing app computes a rolling proximity identifier (RPI), offering it to the Uber driver, the nearby shopper, and the store clerk. Each of their cellphones capture my RPI, saving it together with the date and time of the encounter.

The date and time is an important part of the algorithm, and one of the ways the protocol prevents abuse.

Data exchange protocol

Let's walk through the steps followed to create the data exchange.

There are several parts to it.

When the tracing app is installed the cellphone generates a cryptographically random 32-byte number, which becomes the device's tracing key (tk). It is securely stored, and never leaves the device.
Each day the app use the tracing key (tk) and the day number (Dᵢ) to generate a daily tracing key (dtkᵢ). The result is a one-way hash of those two inputs, truncated to a 16-byte number.
Every 10 minutes the app updates its time interval number (TINⱼ). The result is a number from 0 to 143.
The tracing app computes a new rolling proximity identifier (RPIᵢⱼ) from the daily tracing key and the time interval number. The resulting hash-based message authentication code is truncated to 16-bytes and broadcast over Bluetooth LE to nearby cellphones.
Nearby phones capture and save the broadcasted RPIᵢⱼ. Simultaneously, each of those phones compute their own RPIᵢⱼ — using their own dtkᵢ — which is then captured and saved by the original user's tracing app.

JavaScript implementation

Here's the cryptography algorithm for the contact tracing protocol coded in JavaScript. Very soon both Android and iOS will directly implement this functionality within their respective operating systems, so this is for demonstration purposes only. You can experiment with the JavaScript code to understand how the protocol works.

https://gist.github.com/joehonton/0d77c05038f3ae171c70b58c37d23d98

Timezones, day numbers & time intervals

All date and time calculations within the protocol are performed using UTC.

In the fictional scenario, the encounters occur on May 15, 2020 in the Pacific Daylight Timezone (UTC-7). When translated to UTC, half the encounters occur on May 15 and the other half on May 16.

Day numbers are determined as the number of days since the start of the Unix epoch (January 1, 1970). This is a straightforward calculation:

    May 15, 2020 = day number 18397
    May 16, 2020 = day number 18398

Time intervals are calculated as the number of 10-minute time slices that have occurred since midnight. Normalizing to UTC, the four encounters in the scenario have these time interval numbers:

    Uber driver    23:21 = time interval 140
    Nearby shopper 23:51 = time interval 143
    Stranger       00:06 = time interval 0
    Store clerk    00:11 = time interval 1

With these two numbers we can now assemble the inputs to daily tracing key and the rolling proximity identifier:

                    daily       rolling proximity
                 tracing key        identifier
                 -----------    -----------------
Uber driver      CT-DTK18397        CT-RPI140
Nearby shopper   CT-DTK18397        CT-RPI143
Stranger         CT-DTK18398        CT-RPI0
Store clerk      CT-DTK18398        CT-RPI1

Rolling proximity identifiers

Applying these two inputs and my private tracing key to the rollingProximityIdentifier function yields these results.

     dtkᵢ              RPIᵢⱼ             person
----------------  ----------------  ----------------
e6e1a1eab432a9a0  61280d0cf52f5fd7  Uber driver
e6e1a1eab432a9a0  86b64cd283740664  Nearby shopper
41fca0006c33e515  4538a72df59ec2f8  Stranger
41fca0006c33e515  f5f99b941a42b8c3  Store clerk

The output from this script demonstrates how my identity is anonymized, by date and time, before being broadcast to nearby cellphones, thereby masking who I am and where I've been.

Because the RPI is encrypted with a one-way HMAC, there is no way for anyone to invert the process or to trace my path throughout the day, even if my daily tracing key is compromised.

No other data is captured: no participant name, no IP address, no MAC address, and no GPS location.

Furthermore, each participant in the protocol has complete control over the data that they collect during random encounters. Nothing leaves their cellphone without their consent. And consent is only requested when a healthcare professional determines that someone that they came in contact with has tested positive. Even then, the data is anonymous. The only thing the health care provider can learn is whether or not you've encountered a Covid-19 positive patient during the past 14 days.

Apple and Google are still working out the final details of the protocol. More information will be coming soon.