CoronaTracing

Other person's broadcast history

The following history lists all which were broadcasted by on during particular time slots of that day. The are renewed every minutes.

Click on an entry in the list to simulate what would have happened if Alice had contact during that time slot with .

Time slot
Alice's contact list

Alice's app stores all gathered via Bluetooth on contact with other persons' apps in her private contact list.

This list is not available to anyone else.

DayDuration
List of infections on public server

The public server stores a list of voluntarily reported by infected persons.

The data is anonymous (no connection can be made between them and an actual person).

Day
Matching public server entry against contact list

Select an entry from the public server to look, whether it's in Alice's contact list.

Here all are shown, which Alice's app derived from the of one server entry (for DP-3T, these are 96 EphIDs per day, and that for all days starting from the day of the key).

Each entry in this generated list (day and ) is matched against Alice's contact list in order to find out whether a contact with an infected person occured.

Number of matches with Alice's contact list:

Day
Other person's broadcast history

The following history lists all which were broadcasted by on during particular time slots of that day. The are renewed every minutes.

Click on an entry in the list to simulate what would have happened if Alice had contact during that time slot with .

Time slot
Alice's contact list

Alice's app stores all gathered via Bluetooth on contact with other persons' apps in her private contact list.

This list is not available to anyone else.

DayDuration
List of infections on public server

The public server stores a list of voluntarily reported by infected persons.

The data is anonymous (no connection can be made between them and an actual person).

Day
Matching public server entry against contact list

Select an entry from the public server to look, whether it's in Alice's contact list.

Here all are shown, which Alice's app derived from the of one server entry (for Exposure Notification, these are 144 temporary exposure keys for the day of the key).

Each entry in this generated list (day and ) is matched against Alice's contact list in order to find out whether a contact with an infected person occured.

Number of matches with Alice's contact list:

Day

The Corona Tracing page on CrypTool-Online (CTO) demonstrates and performs two different cryptographic protocols used for decentralized app-based proximity tracing.

In addition to this page, we suggest to also visit the CrypTool Corona-Tracing visualization page [1], which contains a nice end-user animation, while this CTO demonstration focuses more on the protocols in the background.

The visualization page [1] uses the same implementation of the protocols as this CTO demonstration.

Introduction

The purpose of proximity tracing is to reveal risks of infection with the coronavirus caused by contact with an already infected person. With decentralized protocols, those goals are reached by sending the minimum-viable and only anonymous data to a public authority.

Tracing apps on different user's smartphones are automatically exchanging information as soon as they are within a certain physical range to one another. Technically, this is achieved by letting each smartphone constantly broadcast information via Bluetooth, which can be received within a limited distance by other smartphones. The details of the Bluetooth transfer are not in the demonstration scope of this page. Instead, this page focuses on the details of the used cryptographic protocols.

Privacy goals

The decentralized protocols were designed in a way that they neither reveal to the public nor to a central authority that two users were in contact. Only the apps of the two users will be aware of the contact incident but only based on non-personalized data. Furthermore, location detection (for example via GPS) does not play any role at all, because contacts are purely traced by local Bluetooth exchange.

As long as a user is not infected, there is no need for him or her to send any data at all to a central instance. In fact, it would be technically feasible to allow usage of the app without requiring the user to register for use.

Due to the fact that users need to learn about contact with infected users, the protocols require some kind of information disclosure. However, this is done in a completely non-personalized way, so that infected persons cannot be identified by anyone. This is achieved by the use of cryptographic methods.

Privacy attacks based on evaluating huge data flows received locally via Bluetooth should be prevented, even if those recordings occur within larger areas or in many areas at once. One example of such an attack to be prevented would be the creation of movement or interaction graphs, even if the persons in the graph would stay anonymous.

Privacy attacks based on impersonating another user should also be prevented.

Using the demonstration

The scenario of the demonstration is built from the view of Alice, who is not infected yet and meets different people.

The two light green areas "Alice's contact list" and "Matching public server entry against contact list" represent processes that run locally on Alice's smartphone.

Clicking the button "Start tour" in the welcome area (on the top) starts closely guiding you through all areas of the page. In contrast, clicking the button "Start walkthrough" in the welcome area starts the walkthrough which just gives you hints and instructions for all functional aspects of the protocol demonstration.

It is recommended to use the tour and the walkthrough when you first enter the site. Afterwards you can also simply use the animation directly.

For the first walkthrough step, please actively click on an entry in the first rectangular area ("Other person's broadcast history"). This click then simulates that Alice was in contact with that person and receives his/her broadcast message.

You can leave the tour and the walkthrough at any time by clicking the close cross (top right in each case) in the dialogs or in the instructions window above.


References

[1] CrypTool Corona-Tracing visualization page: https://corona-tracing.cryptool.org/

Protocol details

The decentralized approach requires the tracing app of each user to locally store lists of contact incidents with other users' apps. The crucial data which is stored here is the one that was received via Bluetooth from other users' apps. The main content of the broadcasted data is a non-durable identifier (broadcast ID) of the user who sent it, which does not reveal any information about the user.

The app will renew the outgoing broadcast ID every few minutes in order to prevent any receiving party to associate different contact incidents with the same person. New broadcast IDs can only be created from the user's daily secret key, which prevents impersonation attacks. Furthermore, it is not even possible for someone who records lots of broadcast IDs to create non-personalized movement or interaction graphs of users, because he/she will not be able to associate different broadcast IDs with the same user.

In addition to the broadcast ID, the local contact list will also store the day and the intensity of the contact. In this demo, the intensity is only stored by means of the duration of the contact, which is in line with the DP-3T protocol. Other intensity measures, like the level of proximity (measured by the Bluetooth signal) could be stored as well.

When a user learns through a medical test about the fact that he was infected several days ago with the virus, he will be authorized to voluntarily report himself as infected in his app. By doing so, he will send cryptographic keys (his first relevant day key in the DP-3T protocol; and all his temporary exposure keys corresponding to infected day in the Exposure Notification protocol) to a public server. These keys can be used to derive all broadcast IDs that he broadcasted throughout the infection interval. Prior to the reporting, these keys were a secret piece of information, only stored on the user's local smartphone. By making that information public, all other users will be able to match their local contact list against all broadcast IDs which could have been broadcasted by infected persons.

Each user's app will be able to sum up the overall intensity of contact with infected persons. The user will then only be warned in case a certain predetermined intensity threshold has been exceeded. This threshold is determined by the app developers and not in the scope of this demonstration.

The app user is the only instance that is warned by his tracing app about his infection risks. This risk information will not be revealed to anyone else.

Protocol differences

The CTO page demonstrates the two protocols DP-3T [1] (suggested by European scientists) and Exposure Notification [2] by Apple and Google (based on specification 1.2).

The terminology of both protocols differs in some ways. The CTO page will reflect the specific terms.

Function Term in "DP-3T" Term in "Exposure Notification"
Broadcast ID Ephemeral identifier
(short: EphID)
Rolling proximity identifier
Secret key to derive daily broadcast IDs Day key Temporary exposure key
Renew interval for broadcast IDs 15 minutes 10 minutes

The cryptographic details of these two protocols differ in some ways, as described in their specification [1] [2]. The crucial difference lies in the approach of how broadcast IDs are derived from secret keys:

  • In DP-3T, all EphIDs of one day are derived from one day key, with the day key for the next day being derivable from the last day key, using a SHA256 hash function.
  • In Exposure Notification, all rolling proximity identifiers of one day are derived from one temporary exposure key, which is a purely random key. There is exactly one such key for every day. There are no relations between temporary exposure keys of different days.

The implication of this is, that in DP-3T it is only necessary to report a single day key from the day on which the infection started. In contrast, in Exposure Notification, the temporary exposure keys of all infection days need to be reported. This requires more bandwidth because all reported keys need to be downloaded by the apps of all users. The theoretical advantage is, that it is not possible to find out whether rolling proximity identifiers received on several days belong to the same (anonymous) person. This gives Exposure Notification a minor (mostly theoretical) advantage on the security aspect. The lower bandwidth requirement is the reason why the showcased DP-3T variant is called "low-cost".

In DP-3T, all EphIDs of one day are shuffled before being broadcasted, which is why the order of the EphIDs shown in the areas "Other person's broadcast history" and "Matching public server entry against contact list" differ. This is not the case for Exposure Notification.

It is also important to mention that the Exposure Notification protocol provides an additional mechanism to broadcast additional metadata along with the broadcast ID. This metadata is also stored in the contact list of receivers. The metadata is encrypted in a way, that it can only be decrypted after the user reports himself as infected. The purpose of this is to transfer additional information like the protocol version number to the receiver. This mechanism is not in the scope of this page's demonstration.

Cryptographical details

The security of both protocols is based on combining several simple cryptographic mechanisms (hashing, HMACs, stream ciphers) in order to deterministically derive secret daily keys and broadcast IDs.

DP-3T

When a user starts using a tracing app with a DP-3T implementation, an initial day key SK0 will be created as a 32 byte random value from a cryptographic random number generator.

The day keys of all subsequent days will be derived from it recursively using a cryptographic hash function (SHA-256):

  • SK t = H(SK t-1 )
One 32 byte day key can be used to derive all EphIDs for one day from them:
  • EphID1 || ... || EphID n = PRG(PRF(SK t , ASCII("broadcast key")))
  • n = (24 * 60) / 15
  • PRF: deterministic pseudo-random function (HMAC-SHA256)
  • PRG: stream cipher ( AES256 in counter mode)
Each EphID has a size of 16 bytes. In total, there will be exactly 96 EphIDs for each day, resulting into renew intervals of 15 minutes. The derived EphIDs of one day are broadcasted in a randomized order.

Exposure Notification

When using Exposure Notification, the temporary exposure keys are generated individually for each day as 16 byte values from a cryptographic random number generator.

The key teki for day i will then be used to generate the rolling proximity identifier key RPIKi for the same day by using this formula:

  • RPIKi = HKDF(teki, NULL, UTF8("EN-RPIK"), 16)
  • HKDF(key, salt, info, output length): deterministic pseudo-random function based on HMAC-SHA256
This rolling proximity identifier key will then be used to derive all rolling proximity identifiers RPI i,j for the corresponding day. The variable j refers to a specific time slot:
  • RPIi,j = AES128(RPIKi, UTF8("EN-RPI") || 0x000000000000 || TimeSlotID(j))
  • TimeSlotID(j) = Unix epoch time of any point in time within the slot j, divided by (60 x 10)
The 16 byte RPIi,j values will be broadcasted during the corresponding time slots, which have a length of 10 minutes.


References

[1] DP-3T protocol specification: https://github.com/DP-3T/documents
[2] Exposure Notification protocol specification: https://www.apple.com/covid19/contacttracing/


Print