One of the central goals of the Covid-19 digital contact tracing initiative has been to protect the privacy of individuals as much as possible. From the ground up, exposure notification applications such as Covid Green have been specifically built around this fundamental protection, and the underlying protocols provided by Apple's iOS and Google's Android operating systems have this protection built in.
While full details of the Google-Apple Exposure Notification (GAEN) protocol can be found in the Bluetooth Specifications and published FAQs , we want to focus on one very specific component called the Rolling Proximity Identifier (RPI).
After the contact tracing application is installed and active on your mobile device, the GAEN service will allocate a random Temporary Exposure Key every 24 hours. This key is stored securely on your device and is only shared with the exposure notification system if and when you test positive for Covid-19 and manually choose to anonymously share your diagnosis so others can be notified.
At 15-minute intervals throughout the day, your phone takes that Temporary Exposure Key (TEK) and uses it as part of a function to create a new RPI. Your phone then continuously broadcasts the current RPI over Bluetooth to any other devices in the local vicinity. Neither the TEK nor the RPI contains any information that connects to your phone or you personally in any way.
When a mobile device detects another phone nearby that is broadcasting proximity identifiers, those are recorded and stored securely on the device along with the timestamp of when it was seen.
If a user of the application later tests positive for Covid-19, they open the application and choose to share the list of TEKs their phone has accumulated over the past two weeks. A copy of all uploaded keys is then sent to every phone with the app. When my phone receives the lists of keys, it goes through each, regenerates the associated RPI and checks whether that identifier has been encountered at any time during the past two weeks. If it has, I will get a notification that I may have been exposed.
This system is designed such that none of the keys and identifiers can be correlated with any single individual or device, while still allowing deterministic and algorithmic generation and verification. The HKDF is one of the core mechanisms it uses to accomplish this.
The specific algorithm used in the exposure notification service is straightforward:
teki ← CRNG(16)
RPIKi ← HKDF(teki, NULL, UTF8("EN-RPIK"), 16)
RPIi, j ← AES128(RPIKi , PaddedDataj)
The steps here are essentially: