The Crypto on the NHSX COVID-19 App is a Thing of Maths Beauty

The Crypto on the NHSX COVID-19 App is a Thing of Maths Beauty

Forget the Apple/Google API method for rolling IDs, and using boring only hashing methods. The cryptography used in the NHSX app is a thing of real maths beauty and integrates symmetric key encryption, public key encryption and elliptic curves. The method involved uses ECIES (Elliptic Curve Integrated Encryption Scheme) with AES, and you can find out more here. Its main focus is to preserve the privacy of the identities involved around a contact, and in stopping replay attacks.

Introduction

The spread of COVID-19 is likely to be contained with the usage of contract tracing, and where carriers will be traced for those who they have been in contact with. In some countries of the world, broadcast methods have been used, and where carriers are traced on a map:

In this way, it is possible for those who are in close proximity that they are near a carrier. While this is highly effective in terms of containing the spread, it has significant problems in terms of breaching the rights of privacy:

Some of my patients were more afraid of being blamed than dying of the virus

Lee Su-young, Psychiatrist at Myongji Hospital, South Korea

In the UK, a new NHSX App is being trialled this week in the Isle of Wright. At its core are a number of objectives:

• There is very little personal information gathered, with active user consent for data collection.
• Not possible to trace a user or device from Bluetooth beacons (other than being in near proximity to Bob, and we can see beacons from him).
• Not possible to spoof data for another user.
• Not possible to see if the user of a phone which has sent a beacon is a carrier.
• Robust against malicious users, including for replay information about proximity.

An overview of the system is shown in Figure 1. Initially, the user (Bob) installs the App, and the Infrastructure Provider (and which runs in the public cloud) sends back: the Health Authority public key; an InstallationID (which is unique for Bob), and a symmetric key (that will be used for signing Bluetooth broadcasts). These are stored on Bob’s phone, and the details registered with the Infrastructure Provider, along with half of Bob’s postcode.

When Bob comes in contact with Carol, the contact is stored in a log on Bob’s phone with signal strength and a risk score. When the risk score is high enough, it the log is then sent through Firefox Firebase to the Infrastructure Provide (stored in the public cloud). The NHS then has direct access to the information stored.

Broadcast Value

The values broadcasted by Bob (BroadcastValues) uses the public key sent within the registration process. Each day the device creates a new ephemeral private key on an elliptic curve (P256):

PrivKeyD (daily) = r

PubKeyD (daily) = rG

and where G is the base point on the P-256 elliptic curve. The secret is then:

Z = ECDH (PubServer, PrivKeyD)

This is the elliptic curve Diffie Hellman and creates a key exchange. Next, a key is generated using X9.63 KDF and SHA-256 to give two 128-bit values (and where we split the result into two parts (Key and IV):

Key, IV = KDF(Z,rG)

The payload for the message is then:

m = (Start Date) || (End Date) || (InstallationID) || (Country Code)

and where InstallationID is a 128-bit unique identifier for the person. It is then encrypted with AES (GCM) to give:

Cipher, IntCheck = AES(m,IV)

where IV is the initialisation vector (salt) used, and IntCheck is the integrity check. The broadcast value to the device is then:

BV=(Country Code||PubKeyD||C|| ICV)

and where || is a concatenation. This gives a 856-bit broadcast value. This broadcast value will change every day, and where the daily secret is stored on the server:

Only the server has the private key for the public key (PublickeyS), and only it (and Bob) will be able to determine Z.

When the BV is received by Alice and is based onto the central server. The central server will take the public key (PublicKeyD) and then derive Z, and then generate the same encryption key that Bob used. We thus generate a BV every day and a new PublicKeyD. When there is a connection, Bob sends:

P = (BV || TxPower || TxTime || Auth)

and where TxPower is the power of the sender in dBm, TxTime is the transmission time stamp, and Auth is the HMAC relates to he other contents in the payload and keyed using the sending device’s symmetric authentication key. When received, the server can then extract the daily public key (PubKeyD) and then use this with the ECDH method to derive the shared secret (Z). Once we have this, we can then determine the key used to encrypt the message:

Within the log of the phone, the events are automatically aged out after 28 days.

The method we have outlined here is the Elliptic Curve Integrated Encryption Scheme (ECIES) with AES. If you want to see how it works:

Conclusions

There are risks involved with every contact tracing system. The crypto used for the broadcast key is nicely defined, but obviously there are risks, such as in the loss of the private key, and in the linking of Bob to the InstallationID. The great thing is that the code will also go open source, and will other others to review. While it doesn't have the 10–15 min rolling ID, it is a smart way to exchange the daily private key. A major risk of the NHSX system is for the private key of the server to be leaked, and which would then reveal ALL of the IDs and contacts.

The greatest weakness is possibly one of user adoption, and where there needs to be at least 60% of the population installing the App for it to properly work in containment.

Here is an outline implementation: