Comparison of COVID19 Tracking of DP3T and Apple/Google

In the last days I followed the DP-3T initiative, which proposes a "Decentralized Privacy-Preserving Proximity Tracing" to fight COVID-19. Yesterday, Apple and Google announced their unusal collaboration and published their cryptographic specification.

As I wondered how privacy-preserving their protocol is compared to the approach of DP-3T I created the following comparison.

I created this to get a better overview, if you find errors or have suggestions feel free to open an issue or a pull request in this repo or write me on twitter @soenke_hu. Furthermore, its not finished yet. This is just the protocol, I also want to compare possible attacks or privacy issues.

Source

DP-3T

I used the version of the whitepaper available on 2020-04-11. I focus on variant 1.

Apple/Google

I used the version published on 2020-04-10.

Notation

For notation similarity, I use the notation of DP-3T, so \(t\) denotes the day and \(n\) denotes an interval of the day. The Google/Apple approach uses slightly more complex notation, but I decided to simplify that for this comparison.

Keys

DP-3T

This design uses 2 different types of keys:

  • Secret Key \(SK_t\)
  • 16-byte ephemeral ids \(EphID_{t,j}\) (broadcasted)
Key Derivation
$$SK_t \leftarrow H( SK_{t-1} )$$

The initial \(SK_t\) is generated at random, afterwards its derived of the previous \(SK_{t-1}\).

$$EphID_{t,1}~||~\dots~||~EphID_{t,n}~\leftarrow~PRG(~HMAC(~SK_t, "\text{broadcast key}"~)~)$$

A set of ephemeral IDs is generated out of the current \(SK_t\). Each is broadcasted in a random order for \(\frac{24 * 60}{n}\) minutes.

Apple/Google

This design uses 3 different types of keys:

  • 32-byte tracing key \(tk\)
  • 16-byte daily tracing key \(dtk_t\)
  • 16-byte Rolling Proximity Identifier \(RPI_{t,n}\) (broadcasted)
Key Derivation
$$tk \leftarrow CRNG(~32~)$$

The tracing key \(tk\) is generated at random

$$dtk_t \leftarrow HKDF(~tk,~NULL,~"CT-DTK"||t,~16)$$

The Daily tracing key is derived daily of \(tk\) and \(t\).

$$RPI_{t,n} \leftarrow \text{TRUNCATE}(~HMAC(~dtk_t,~"CT-RPI" || n~),~16~)$$

Each time the MAC address changes, a new \(RPI_{t,n}\) is generated. Here, \(n\) is incremented on each change. According to the specification, this happens every 10 minutes, so 144 keys are generated each day.

Broadcasting keys

Both solutions broadcast a key for proximity tracing as Bluetooth Low Energy (BLE) beacons which is changing on a certain interval. The device furthermore stores each received beacons. After a user got infected, it uploads data to a central server which can be fetched by all users to check, whether they were in its proximity.

Matching Values

DP-3T

Each user stores:

  • Observed \(EphID\)
  • Estimated proximity
  • Duration
  • Coarse time indication

After infection, a user uploads the pair \(SK_t, t\) for the estimated first day of being contagious.

Other users fetch this information and generate all related \(EphID\)s to compare them to the ones they discoverd and find out whether they have been in proximity.

Apple/Google

Each user stores:

  • Observed \(RPI_{t,n}\)
  • Time window \(n\)

After infection, a user uploads their set of relevant \(dtk_t, t\) pairs from the estimated first day of being contagious.

Other users fetch this information and generate all related \(RPI_{t,n}\) to compare them to the ones they discovered and find out whether they have been in proximity.

After reporting

DP-3T

After reporting its \(SK_t, t\), the user picks a new random key \(SK_t\). This happens, because one can link \(SK_t\) and \(SK_{t+1}\) of the same user as \(SK_{t+1} = H(SK_t)\).

Apple/Google

Nothing changes, as \(dtk_t\) and \(dtk_{t+1}\) are unlinkable.

Similarities & Differences

The overall protocol is quite similar. The keys can be mapped like that:

One important difference is, that in the DP-3T protocol the \(SK_t\) keys are derived from the predecessor, so it must be change after publication.

tbc...