CrowdNotifier explained: tracing COVID-19 contacts with privacy in mind

CrowdNotifier is a secure, decentralized system for notifiying individuals that have been in contact with SARS-CoV-2-positive people in public locations, such as bars, restaurants, venues and other places that can be considered potential sources of contagion.

This article aims to demistify this technology and explain how it works and how does it preserve the privacy of its users.

Overview

In summary, the CrowdNotifier presence-tracing system involves three parties:

• Visitors 🧑: individuals that visit a location at a given point in time.
• Locations 📍: the places visitors stop by.
• Health Authority 🚑: typically, a single governmental agency that will be responsible for determining whether a person has the COVID-19 disease.

When visitors come into a location, they use an app implementing the CrowdNotifier system to scan a QR code provided by the location owner. When they leave, they check out tapping a notification left by the app on their phone.

Location owners can generate these QR codes using a web application.

If the Health Authority concludes the location has been visited by an infected person at a given point in time, other visitors who were there during the same overlapping timespan will be notified through the app.

The security, trust and privacy of the system rely on symmetric, asymmetric and IBE cryptography.

Now let's see how this process actually works!

IMPORTANT! This article oversimplifies IBE by omitting some encryption/decryption and key derivation aspects to make it easier to understand. Cryptographers be warned.

Step 1: QR codes generation

Location owners need to generate two different QR codes: one for the entry (which is public) and another for the trace (which is private).

The entry code is placed at the entrance (or entrances) of the location and is the one scanned by visitors when they come in.

Both codes are generated offline (this means on the client side, without any party except the location owner knowing any secret key-generation material).

The generation process is as follows:

1. Generate two sets of IBE master keys (one for the Location and another for the Health Authority). These sets are made of a Master Public Key (MPK) which is known and a Master Secret Key (MSK) that needs to remaing private.

   $(mpk_L,\, msk_L) \newline (mpk_{HA},\, msk_{HA})$

   MPKs are used to encrypt messages and MSKs can derive decryption keys. If you know the Master Secret Key, then you can decrypt any message (this is partly true, but for the moment just roll with it).

2. Generate the entry QR code. This one contains some public information about the location (i.e. name), both Master Public Keys and a random symmetric key (notifyKey) which is generated on-the-fly.

   

3. Generate the trace QR code. It must be kept secret for now as it contains both Master Secret Keys.

   

   One important detail is the Health Authority's MSK is encrypted using public key cryptography with the HA's asymmetric public key, thus ensuring only the HA can decrypt it.

   As you may have already guessed, we need to know the HA's public key in advance (pk_HA).

Step 2: Record visited locations

This is the part when it starts to get interesting!

The history of visited locations is stored only on the phone of its corresponding visitor and it keeps track of the past 10 days.

Even if the visitor's phone gets hacked no one can know were he/she has been as this information is both hashed and encrypted 🤯. The most an attacker can do is know someone has been in contact with a SARS-CoV-2-positive.

When visitors enter a location they scan the entry QR code to get all the data it contains, and when they leave, the phone app stores a record for each hour interval they have been at the place.

For example, if a visitor enters at 6:36 pm and leaves at 8:01 pm, inmediately after tapping the "leave" button on their phone, the CrowdNotifier app will generate three messages (6pm, 7pm and 8pm) containing the same information but encrypted with a different key for each hour.

As you can see in the figure above, to generate a record we follow these steps:

1. Generate an ID needed for the IBE encryption process. This ID is the result of hashing the location info with the UNIX timestamp of the given hour.

2. "Derive" IBE encryption keys using mpk_L, mpk_HA and the previous ID (not exactly what happens, but close enough).

   These Partial Secret Keys (PSK) are what CrowdNotifier calls "pre-tracing keys".

3. Create a message consisting of the arrival and departure times and the location's notifyKey. Then encrypt it with the material we obtained in the previous step.

   One awesome thing about IBE cryptography is that m_hour can only be decrypted if you have the generated ID and both msk_L and msk_HA, so cooperation between the location owner an the Health Authority is required.

   Remember! Master Public Keys are used to encrypt and Master Secret Keys to decrypt.

4. Store the encrypted message in the visitor's phone.

Step 3: Notifying positives

When the Health Autority detects an infected person, it requests the Location owner the notifyKey, encrypted msk_HA and the location PSKs for a given time interval, tipically from the arrival to the departure of the COVID-19 subject.

To obtain the requested information, the Location owner scans the trace QR code that has been kept private until this very moment and derives all location PSKs for the appropiate time interval using their MSK (msk_L).

The Health Authority receives this information and verifies it. If it passes verification, a set of notification messages are generated and published to a public server (in most cases managed by the HA) where visitors' apps periodically connect to in order to check whether they have been in contact with an infected person.

These notification messages contain both Partial Secret Keys as the two are needed to decrypt the messages stored in the visitors' phones.

Also, the notifyKey is not sent but instead is used to encrypt a random plaintext that is added to the notification.

Step 4: Alerting visitors

This is the last step of the CrowdNotifier workflow.

After notification messages have been published to the public server, the smartphone app downloads them to check if the visitor has been in the same location at an overlapping time with a positive contact.

For every notification, the app extracts the PSKs and tries to decrypt every message stored in device that was previously recorded in Step 2.

If the time intervals overlap and the random value from the notification can be decrypted using the notifyKey obtained after decrypting the message, then an alert is shown to the user (visitor).

If the app cannot decrypt any stored message with any of the PSKs provided in the notification messages, then everything is fine: the user has not been in contact with an infected person.

---

And that's basically how CrowdNotifier works!

If you want to learn more or dig deeper into the cryptography behind this technology, check out the White Paper from their official Github repository.