Review of New Apple and Google Contact Tracing Protocol

On April 24th 2020 Apple & Google have announced a new version of the Apple & Google Contact Tracing Protocol which they programmed in a joint effort. Now it’s to be called “Exposure Notification Technology”, since this name better describes the nature of the protocol.

On 29th of April Apple released the first iOS 13.5 beta implementation of the protocol. This beta version targets developers for API testing and collecting feedback. The access to the API will be limited to apps authorised by public health authorities.

This update is a reaction to the criticism (most of which was baseless) as well as several technical changes implemented in versions 1.1 and 1.2 of this protocol. We are going to discuss these changes in this article.

Name change

As it is often noted by Apple & Google, contact tracing is only a part of this protocol, nevertheless a very important one.

The main idea behind this effort is to decelerate the spread of COVID-19 by notifying potentially infected individuals in advance.

As illustrated in the infographic above, after one person infects several others, then, by the time the COVID-19 diagnosis of the first person is confirmed (as its incubation period is about 14 days), most of the recently infected people will most likely not yet feel any of its symptoms. Instead they will be infecting others.

If we can manage to inform such symptom-free carriers at the moment of diagnosis of the person who had infected them, we can prevent a chain reaction. Thus drastically reducing spread of infection.

This approach can help to at least partially remove quarantine restrictions. Implementing this simple idea might save economies in many countries, and Apple & Google have united in this task for a good reason.

We shall now have a look into the way the old protocol functioned and how the new one is supposed to work. Later on other differences between the old and the new protocol shall be discussed in more detail.

Old Protocol Operation Procedure

An app is installed on a smartphone with iOS or Android that launches contact tracing via Apple & Google Contact Tracing API.

1. Randomised Private Tracing Key is generated.
2. This key is used to generate Daily Tracing Key as HKDF from Tracing Key joined with the number of the day.
3. Randomised Private Tracing Key is generated.
4. This key is used to generate Daily Tracing Key as HKDF from Tracing Key joined with the number of the day.
5. Every 10 minutes, this key is used to generate a temporary Rolling Proximity ID as HMAC of Daily Tracing Key joined with a time interval number. This temporary key is broadcasted using Bluetooth Low Energy. Other smartphones that read this key store it locally afterwards.
6. Once someone is infected, their last 14 daily keys are published, and all other devices, after downloading these 14 daily keys, generate Rolling Proximity IDs for all the 14 days and compare them to locally stored Rolling Proximity IDs.

If there is a match, you’ve had a contact with an infected person.

You can find a more detailed description inthe previous article we published about the topic.

New Protocol Operation Procedure

1. Every day a new random 16-byte daily Exposure Key is generated. It is used for generation of an encryption key for temporary identifiers (Rolling Proximity Key, or RPIKey), as well as metadata encryption key (Associated Encrypted Metadata Key, or AEMKey):
   

   RPIKey = HKDF(ExpKey, NULL, UTF8(“EN-RPIK”),16)
   AEMKey = HKDF(ExpKey, NULL, UTF8(“EN-AEMK”),16) 
   

   where
   - HKDF(Key, Salt, Info, OutputLength) designates the HKDF function as defined by IETF RFC 5869 , using the SHA-256 hash function.
   - NULL stands for salt that is not used.
   - UTF8(“EN-RPIK”) is a byte array that corresponds with the EN-RPIK string in UTF8.
2. BLE specifications assume changing MAC address every 15–20 minutes to avoid device tracing.
   Every time a MAC address is changed, a new temporary Rolling Proximity ID (RPID) key is generated.
   

   RPID = AES128(RPIKey, UTF8(“EN-RPI”) || 0x000000000000 || Ti)
   

   where
   AES128(Key, Data) is for AES crypto function with 128-bit key.
   - Key is RPIKey or Rolling Proximity Key generated at first step.
   - Data is concatenation (||-symbol designates concatenation) of the following:
   - UTF8(“EN-RPI”) is a 6-byte array corresponding with the EN-RPI line encoded in UTF8.
   - 0x000000000000 is six zero bytes (to get one 128-bit block in total).
   - Ti — 4-byte number of 10-minute temporary interval, calculated as
   unix_timestamp div (60 * 10) , whereas div stands for integer division.
   Next, 4 bytes of Associated Encrypted Metadata (AEM) are encoded.
   It is not disclosed in specification, how exactly this metadata is compiled. Probably, it was done to leave options to expand the protocol.
   We’ll talk about metadata in more detail later in the article.
   AEM = AES128−CTR(AEMKey, RPID, Metadata) ,
   where
   - AES128−CTR(Key, IV, Data) is for AES-CTR crypto-function, and AEMKey is 128-bit key.
   Data-out size matches data-in size, so there is no need to add anything to match block size.
   Rolling Proximity Key is used as input vector IV .
   Next, temporary identifier Rolling Proximity ID is combined with Associated Encrypted Metadata, and this is what BLE Payload looks like:

This batch is broadcast via Bluetooth Low Energy. Devices that read it and store it locally afterwards.

3. Once someone is infected, their last 14 daily keys are published, and all other devices, after downloading these 14 daily keys, generate Rolling Proximity IDs for all the 14 days and compare them to locally stored Rolling Proximity IDs.

What has changed and why

Name

People have been calling Apple & Google “Big Brother” for a while.

Since the release of the first version of this protocol, news headlines were informing everyone about a new protocol for tracing contacts that was developed by Apple & Google. After reading headlines only, most readers got an impression of yet another tracking system, and nothing (neither anonymity nor encryption nor local data storage) could dissuade them.

Lack of a Primary Key

A primary private Tracing Key that was used before for Daily Tracing Keys generation has been removed.

In the new version, each Exposure Key (Daily Tracing Key earlier) is randomly generated, so it is impossible to establish a link between them even in theory.

This approach is used in DP-3T Protocol, developed by the scientific community. You can read about this protocol in more detail in one of our previous articles dealing with this protocol in more detail.

Thus, Apple & Google reaction to criticism was to protect the protocol from two possible attacks:

1. Should an intruder find an old backup of a smartphone, they could extract Daily Tracing Key, and this was enough to generate fresh daily keys and broadcast fake new contacts.
2. If an intruder manages to find linked keys or even, if they have access to a vast amount of time and computer power, guess a Tracing Key (after someone gets infected and publishes Daily Tracing Keys), they can deduce movements of infected with the help of previously installed BLE beacons, or they can create fake new contacts (in case they have managed to calculate Tracing Key).

AES instead of HMAC-SHA-256

To improve performance, the encryption was changed to AES from HMAC-SHA-256.

Generating a temporary key every 10 minutes is not a problem, however, this might come into play with keys downloaded from the server.

For example, one day in some big country 10.000 people have reported new infections. This would create 140 thousand daily keys, or 140K*144 ~ 20 million temporary keys (144 temporary keys are created every day, 24*60/10) that a smartphone needs to generate. It is possible to optimise matchmaking by making a comparison and going through all daily keys for a contact’s day number, instead of generating all the possible temporary keys. In this case, if you had around 10 contacts per day, i.e. 140 contacts per two weeks, your phone would need to make 140*10K=1.4M operations, which is quite a considerable number.

Many modern smartphones support hardware acceleration for AES encryption, which allows them to match contacts faster and to use less battery power.

MAC and RPI Change synchronisation

A mistake in timing the temporary key generation was fixed.

In the first version of specifications, a temporary identifier Rolling Proximity Identifier was being generated every 10 minutes. At the same time, Bluetooth Low Energy MAC changes every 15 to 20 minutes with different intervals.

Since RPI and MAC change was not synchronised, it was possible to associate new MAC with old RPI or new RPI with old MAC. This mistake could allow to track users movements, for example, in trading centres, with BLE beacons.

New version of protocol has MAC and RPI changes synchronised. To quote:

“The key schedule is fixed and defined by operating system components, preventing applications from including static or predictable information that could be used for tracking.”

Protocols which do not work on system level but on app level cannot synchronise MAC and RPI changes this way. Thus, DP-3T protocol and OpenCovidTrace generate temporary identifiers at the moment of access to BLE service, and these identifiers are not broadcast.

Associated Metadata

The appearance of encrypted metadata is the most enigmatic change in specifications. It is not clarified what it will contain and who will have access to it, so let’s try to guess.

What do we know about this metadata:

1. It is generated and encrypted on our device every 15 to 20 minutes and is only 4 bytes in size.
   It could be one of the following:
   1) Information about our device;
   2) Time;
   3) Location (not precise, since it’s limited to 4 bytes);
   4) Time zone;
   5) Organisation that published this particular application;
   6) Possibly, an ID assigned to you by the organisation that published this app.
2. It is broadcasted to all nearby devices (although it’s encrypted) and no one else possesses this information. In case of infection, this data is not uploaded to the server.
   So, only devices that you were in contact with get this data. It would be logical to assume that this is some sort of data your contact does not possess, which makes time and location options unlikely. Although, even if this data is not used in this protocol, some developers might use it as an extension of sorts.
   There is a high probability that additional data about you exists.
3. This data can only be decrypted after one of its users gets infected and shares their daily key that can be used to generate a key and initialization vector to decrypt this data.
   Consequently, this data must be only important in case of infection.

Thus, this data can consist of the following three bullet points:

• Phone model, code or the power of the Bluetooth transmitter which is necessary to calculate distance of contact.
• Code of the application, or the organisation or the country that has published this application, so that it is possible to know who has confirmed the diagnosis.
• Worst case scenario, this could be some internal ID that would allow developers of apps that make use of this protocol to make them not anonymous, despite everything that was declared by this protocol in the first place.
  In their databases, developers can use ID in metadata to link data of every user with anonymous identifiers protocol uses.
  In case of an infection it could be possible to find out the ID of the user who could have infected you and request this information.

In Conclusion

Apple & Google have demonstrated that they can take criticism and promptly react to it.

Changes in protocol have removed several security issues, improved performance when matching infected contacts and added new options to app developers.

However, the main issue, which is distrust from users towards IT giants when it comes to privacy of their contacts and movement data is unlikely to disappear. It cannot be solved simply by changing the protocol’s name.

We at OpenCovidTrace are certain that projects of this social importance must be implemented as open source, and that safety and privacy of our user’s data needs to be confirmed by a professional community.

This is why we’re working on an open source platform OpenCovidTrace that supports DP-3T protocol and implements Apple & Google protocol with some changes caused by iOS limitations.

Join us on Github! Your input and feedback will help our project’s development and together we’ll be able to quench coronavirus outbreaks after the quarantine is lifted.

You can also help OpenCovidTrace by sharing our project via social networks.

Thank you for your attention and stay healthy!

OpenCovidTrace Team

Links:

https://www.apple.com/covid19/contacttracing — Apple & Google protocol documentation

https://github.com/DP-3T/ — Github repository for DP-3T, a contact-tracing protocol developed by european scientific community.

https://opencovidtrace.org — our open-source project

https://github.com/OpenCovidTrace — our Github repository