Previously I have discussed the paper released by Apple and Google covering their own implementation of a Contact Tracing system, known as ExposureNotification. Their approach was both an Operating System level implementation, and an API (accessible by entitlement only). Apple released a beta version of the Framework with iOS 13.5 Beta 3, along with more documentation, sample code, and an Xcode/SDK update for actively using it within apps.

The NHS, or National Health Service for those unaware, had already announced their efforts working on an iOS and Android application for Contact Tracing, however they declared they would not be using Apple and Google’s ExposureNotification, instead opting for their own system. This was met with great skepticism, primarily due to, for example, the Australian Governments app.

NHSx Contact Tracing app.

NHSx Contact Tracing app.

In this post I shall cover the problems faced by the NHS by going their own way, an overview of how the application works, server-side architecture, and differences between the two systems cryptographically. My analysis of the application is focused on iOS. There are some differences between the iOS and Android variants due to iOS being a more restricted, locked-down system compared to Android.

Problems faced by NHSx

The only way feasible way of implementing contact tracing while preserving privacy is Bluetooth. As outlined in Apple and Google’s Cryptographic and Bluetooth whitepaper’s, Bluetooth LE (Low-Energy) Broadcasts can be used to ping small bits of data to nearby devices, which can then collect and store these bits of data which can later allow the device to determine whether a user was exposed to someone potentially infected with COVID-19. That is the basic principle of it.

However, iOS imposes heavy restrictions on how third party applications can use Bluetooth when asleep (in the background), and do not allow any Bluetooth activity from an application when it has been terminated. This, primarily, is to protect both user privacy and battery life. The restrictions are not a problem for Apple as ExposureNotification is integrated into iOS as it’s own API, rather than a simple standalone app that uses the already built-in Bluetooth API. To further add to these restrictions, the ExposureNotification API is also limited in use, and can only be used by organisations granted a specific app Entitlement, in the same way apps must poses an Entitlement for In-App Purchases or Notifications.

iOS Applications also require an Entitlement to operate in the background without severe limitations on functionality. As noted by Aidan Fitzpatrick, developers can submit their application with “Background Modes” selected which, if approved, allows background operation for a number of this, most importantly Bluetooth. For example, the YouTube app has this entitlement to allow the audio of videos to be played when the application is not front and centre.

This does pose a problem and a challenge for the NHSx app. It works perfectly when the app is in the foreground, however once the app enters the background it’s more difficult for the app to detect other devices, send the amount of broadcasts it would in the foreground, be able to detect signal strength which it uses to determine how close and how long your device was exposed, and hinders the ability to detect non-Apple devices.

Analysis

I have several aims with this article. My primary aim is to cover the design of the application, both client and server side and the differences between it and Apple’s ExposureNotification Framework, My secondary aim is begin to cover the workarounds used to bypass most of the restrictions of backgrounded applications, and the reliability of them. This article is aided by the source code for the NHSx app, documentation published by NHSx and NCSC, articles published by Aidan Fitzpatrick and Jamie Bishop for Reincubate, and my own usage and analysis of the app.

The United Kingdom’s National Cyber Security Centre (NCSC) wrote a paper, similar to Apple’s and to coincide with the release of source code, discussing the cryptographic aspects of the design for the application. You can read my analysis of Apple and Google’s approach, ExposureNotification, here. The first aspect of my analysis will be covering this paper, and comparing their design to Apple and Google’s. Essentially, I will cover their paper in a way that may be easier for the general user to understand.

Application Registration (InstallationID)

The NHSx approach is different from the Apple/Google model in that it is centralised, rather than decentralised. Specifically, devices must register with a central NHS server when the app is first opened on the device, where with ExposureNotification, the device does not register with Apple that it is taking part, and no data is shared unless the device owner is confirmed positive.

When the app is downloaded, a registration process is initiated. The first step is for the app to contact Firebase and request a registration token. It appears that the registration toke is generated by Firebase Cloud Messaging, as this is used extensively throughout the app. This is repeated generally for each application restart with a new token being issued only if the application is either reinstalled or the data is erased.

The app will then contact the Sonar Registration Service (Sonar being the codename for the app), and register any newly generated Firebase Tokens. From this, the Registration Service will generate an anonymous random GUID, name the InstallationIDInstallationID, a Symmetric key for authentication, and an Activation Code - these are all stored with the Token sent by the app to the Sonar Registration Service. The InstallationIDInstallationID generation may be modified in the future to include input from both client and server.

The Sonar Registration Service then will send an activate message, containing the previously generated Activation Code, to the device via Firebase Cloud Messaging (FCM) using the generated Firebase Token.

During the application initialisation, providing the app is either newly installed or app data has been erased/corrupted, the app will request the users Postal District, rather than the full Postal Code to further obscure the users identity. This data, along with the device type, Firebase token and Activation code, is submitted to the Sonar Registration Service to confirm the registration.

Once this is completed, the registration service deletes the Activation code from it’s database so it cannot be reused by the same device in the same period. Finally, the Symmetric Key, which was generated earlier, is returned to the device, along with the Server’s Public Key.

This approach is drastically different ExposureNotification. Whereas Apple and Google’s system is almost entirely on-device, with a TracingKeyTracingKey being derrived upon setup, instead of a Client-Server registration process. So unlike Apple-Google’s system, the NHS system keeps a record of the GUID’s of users - however these are regenerated if the app is reinstalled. The likely reason for this increased centralisation and client-server integration is the generation of COVID-19 test reference codes that are to allow the linking of test results to a device.

BroadcastValue

The Sonar central server has a Private key, with associated Public key, based on the curve P256. During the registration process we just discussed, you will know that the Sonar server sends it’s Public key - along with other data - to the device. Like the DailyTracingKeyDailyTracingKey, the BroadcastValueBroadcastValue is derrived every 24 hours, however instead of just an HKDFHKDF hash, the BroadcastValueBroadcastValue is another Public-Private key pair also from the curve P256. We will refer to these values as follows: tt is defined as a 24-hour period, pubServer,privServerpubServer, privServer is defined as Sonar’s key pair and pubDevt,privDevtpubDev^t, privDev^t is defined as the devices key pair.

The device will proceed to calculate a Secret Value (called ZZ) using a simple ECDH agreement, with the Sonar server’s Public key - pubServerpubServer - and the devices Private key generated for the current tt period - privDevtprivDev^t.

Z = ECDH(pubServer, privDevt) Z\ =\ ECDH(pubServer,\ privDev^t)

The app uses the X9.63 KDF (Key Derivation Function) with SHA-256. X9.63 is essentially a function which uses an elliptic curve for key generation, like what was used to generate pubDevtpubDev^t and privDevtprivDev^t, with a particular hashing algorithm. In this case, NHSx chose to use a KDF with SHA-256. Two inputs are given - an existing key, and a number of some sort. The existing key to be given is the devices Public key - pubDevtpubDev^t - and the number given is the ZZ value calculated above.

The result is a Key and IV (Initialisation Vector) like so:

(𝐾, 𝐼𝑉) = 𝐾𝐷𝐹(𝑍, pubDev𝑡) (𝐾,\ 𝐼𝑉)\ =\ 𝐾𝐷𝐹(𝑍,\ pubDev^𝑡)

Now, there is not much point to go to this length for key generation if there isn’t anything to encrypt. So, a plaintext payload is constructed as follows, where || denotes concatenation.

𝑚=(𝑆𝑡𝑎𝑟𝑡𝐷𝑎𝑡𝑒𝐸𝑛𝑑𝐷𝑎𝑡𝑒𝐼𝑛𝑠𝑡𝑎𝑙𝑙𝑎𝑡𝑖𝑜𝑛𝐼𝐷𝐶𝑜𝑢𝑛𝑡𝑟𝑦𝐶𝑜𝑑𝑒) 𝑚 = (𝑆𝑡𝑎𝑟𝑡𝐷𝑎𝑡𝑒||𝐸𝑛𝑑𝐷𝑎𝑡𝑒||𝐼𝑛𝑠𝑡𝑎𝑙𝑙𝑎𝑡𝑖𝑜𝑛𝐼𝐷||𝐶𝑜𝑢𝑛𝑡𝑟𝑦𝐶𝑜𝑑𝑒)

Going left-to-right, StartDateStartDate and EndDateEndDate are 32-bit UNIX epoch’s which are used for anti-replay, InstallationIDInstallationID is the GUID generated for the device’s current installation by the Sonar Registration Service, and the CountryCodeCountryCode is the ISO3166-1 country code.

I do find it rather strange they would settle on using ISO3166-1, which would simply result in “GB” for essentially all cases. Considering that the application is intended for use only within the United Kingdom, using ISO3166-2 which provides county-specific codes, such as “GB-HRT” for Hertfordshire, would make more sense.

We can now encrypt the plaintext mm. We compute CC and ICVICV, where CC is the Ciphertext, and ICVICV is an Integrity Check Value. This uses AES in Galois Counter Mode, or GCM.

(𝐶, 𝐼𝐶𝑉) = 𝐴𝐸𝑆𝐺𝐶𝑀𝐸𝑁𝐶𝐾(𝑚, 𝐼𝑉) (𝐶,\ 𝐼𝐶𝑉)\ =\ 𝐴𝐸𝑆𝐺𝐶𝑀𝐸𝑁𝐶𝐾(𝑚,\ 𝐼𝑉)

Looking at this, we see two inputs are given. mm, the plaintext payload we want to encrypt, and IVIV the Integrity Check value generated from our X9.63 KDF.

Finally, the actual BroadcastValueBroadcastValue which is sent over Bluetooth to other devices is constructed by concatenating the ISO3166-1 CountryCodeCountryCode, public key for the current tt period and the ciphertext with it’s corresponding Integrity Check Value.

𝐵𝑉 = (𝐶𝑜𝑢𝑛𝑡𝑟𝑦𝐶𝑜𝑑𝑒pubDev𝑡,𝐶𝐼𝐶𝑉) 𝐵𝑉\ =\ (𝐶𝑜𝑢𝑛𝑡𝑟𝑦𝐶𝑜𝑑𝑒||pubDev^𝑡,||𝐶||𝐼𝐶𝑉)

This is our final data, 856-bits in size, which is sent with each Bluetooth LE broadcast payload for the current tt period. Once 24-hours have passed since the derivation of this BroadcastValueBroadcastValue, this process is repeated.

If you’d like to learn more about the cryptography-related aspects we’ve discussed here, I suggest reading the following articles, and obtaining an @zistooshort.

Proximity Event Logging

Like ExposureNotification, the application advertises over Bluetooth LE (Low-Energy) using a Service Identifier which allows other devices using the app to connect to each other. This identifier is ideally exclusive only to the NHS app, however it is possible to “pretend”, or spoof, being the Contact Tracing app.

Once the app has verified that the connection uses this service identifier, a connection can be established. The BLE Broadcast payload is not simply the BroadcastValueBroadcastValue. Instead another value, PP is constructed by concatenating (denoted ||) the BroadcastValueBroadcastValue and a few other properties:

𝑃 = (𝐵𝑉𝑇𝑥𝑃𝑜𝑤𝑒𝑟𝑇𝑥𝑇𝑖𝑚𝑒𝐴𝑢𝑡h) 𝑃\ =\ (𝐵𝑉||𝑇𝑥𝑃𝑜𝑤𝑒𝑟||𝑇𝑥𝑇𝑖𝑚𝑒||𝐴𝑢𝑡ℎ)

After the Broadcast Value, TxPowerTxPower is the BLE transmit power in dBm, TxTimeTxTime is the UNIX epoch the device constructs this payload, and AuthAuth is a 16-byte truncation of an HMAC hash - however it’s not clear what makes up this hash.

After the connection has been made, every 8 seconds (currently), the Received Signal Strength Indicator, or RSSI, is recorded from the Bluetooth Low-Energy stack. Eventually the connection should fail, due to the device going out of range. Upon this occurring, an event is logged containing the local time the connection failed and subsequently the encounter ends, the received BLE payload[s], BLE transmit power (TxPowerTxPower) and time (TxTimeTxTime), AuthAuth, which binds the time, power and BroadcastValueBroadcastValue to a particular device, r0...rnr_0...r_n, which is basically a tuple of RSSI values, and the total time elapsed during the encounter. These event logs are stored on-device and subject to local storage policy, and are deleted after 28 days as that is determined as a point where any interactions are not a risk to the user.

When a user is diagnosed, the logs are are, with permission, sent to the central Sonar server. This event log is encrypted with the shared symmetric key collected during registration, integrity checked and sent to the server TLS-protected.

Re-deriving BroadcastValue (Server-side)

An important area of Apple and Google’s system I discussed in my last post was the re-deriviation of Rolling Proximity Identifiers, essentially the equivalent to the BroadcastValueBroadcastValue discussed here. The key differences is that the RPI is simply generated using a hash of the device’s unique TracingKeyTracingKey - similar to the InstallationIDInstallationID - and a number generated from the time epoch every ten minutes. The NHSx method makes use of Public and Private key pairs and interaction with a remote server - ExposureNotification only interacts with a server once the user has been diagnosed with SARS-Cov-2.

Both systems rely on re-deriving the data sent in Bluetooth LE Broadcasts. The ExposureNotification method is, I would say, more complicated and not as easy to follow through, so I suggest having a read of it here.

The BroadcastValueBroadcastValue is, critically, constructed using the Sonar server’s Public key and the devices Private key (for the specific 24-hour window, denoted tt). When the server receives a set of BroadcastValueBroadcastValue’s, it will also extract the corresponding Public key from the device for the particular day the broadcast was received.

The server can then use it’s public key, and the corresponding device private key, to derive ZZ. That can then be used, like shown above, with the device public key, to derive the KK and IVIV values.

(K, IV) = KDF(Z, pubDevt) (K,\ IV)\ =\ KDF(Z,\ pubDev^t)

Once the IVIV is re-derived, the server then utilises the Ciphertext (CC) and Integrity Check Value (ICVICV), which make up the BroadcastValueBroadcastValue to recover the original plaintext message. See the following, where 𝐴𝐸𝑆𝐺𝐶𝑀𝐷𝐸𝐶𝐾𝐴𝐸𝑆𝐺𝐶𝑀𝐷𝐸𝐶𝐾 is AES GCM decryption mode.

𝑚 = 𝐴𝐸𝑆𝐺𝐶𝑀𝐷𝐸𝐶𝐾(𝐶𝐼𝐶𝑉, 𝐼𝑉) 𝑚\ =\ 𝐴𝐸𝑆𝐺𝐶𝑀𝐷𝐸𝐶𝐾(𝐶||𝐼𝐶𝑉,\ 𝐼𝑉)

This leaves us with the original variables used to makeup the plaintext value. The most important value in this is the InstallationIDInstallationID as the Sonar server can now send a notification to all the corresponding devices for the submitted event logs by the diagnosed user.

In comparison, this re-deriviation of keys is done on-device with ExposureNotification, rather than with a server.

Client-Server functionality

As we have already mentioned, the NHSx app makes use of a centralised design. This means that a central server plays a significant role in the overall operation of the Contact Tracing system. Whereas by comparison, with Exposure Notification, the role of a central server is limited to collecting and distributing diagnosis keys from the devices of confirmed cases.

The overall diagram for the design of the application shows the flow of the system. The system makes use of both Firebase for notifications and initial registration, and an in-house Sonar Service server for handling databases, diagnosis and notifying Firebase for Push Notifications.

Overall Design Diagram.

Overall Design Diagram.

So, the (brief) overall flow of the application is as follows:

The user will initially download the application from either the App Store, or Google Play Store. The first time the app is opened, or after some corruption of local data, the app registers with the central Sonar Registration Service server, and Firebase Cloud Messaging. The app generates it’s first BroadcastValue, and will continue to do so every 24-hour period.

The device will attempt to connect to other devices, with the app installed using it’s unique identifier, over Bluetooth Low Energy (BLE) using a series of broadcasts. The connection, when established, is continuously monitored - specifically the signal strength - which is used to determine the distance between the two devices. When the connection eventually fails, the encounter is recorded (Proximity Event Logging). This can handle multiple connections at once, However, a workaround is required to keep this working when the app is in the background. This is done via a series of keepAlives.

When a user begins to experience symptoms, the user should open the app, follow the prompts through asking for different symptoms and select the date on which they first began to experience those symptoms. The app uses this to determine when the user first became infectious, and the logs for those days are submitted to the Sonar Service with the express permission then and there of the user.

A test would then be booked for the user, and a reference code given to them. This reference code is given at the testing point, and will stay with the users swab sample. The diagnostician, according to the diagram, manually uses an internal web page to mark the reference code as either Negative or Positive. This connects to the Sonar Service and notifies the user of their test result, and notifies their contacts and those they came into close proximity with of the exposure.

Summary

I hope you found this post interesting. Unfortunately a mountain of personal and family issue impeded the progress and resulted in it being both late and shorter than I planned. If you have any feedback, please let me know on either Twitter (@h3adsh0tzz), or email me (me@h3adsh0tzz.com).