Decentralized Privacy-Preserving Proximity Tracing crypto made easy

This post will illustrate an easy integration path for the cryptographic scheme documented in the DP-3T documents by Carmela Troncoso and colleagues, whose research is prompted by the urge of the COVID-19 emergency and proposed to the Pan-European Privacy-Preserving Proximity Tracing workgroup (PEPP-PT) as a decentralized solution privacy-preserving solution.

My goal is to make it as easy as possible to develop privacy-aware applications and the tools I’ll use are those we developed in the DECODE project lead by Francesca Bria and myself as technical coordinator.

If you don’t know the Decentralized Privacy-Preserving Proximity Tracing research yet or you are simply not interested in its cryptographic implementation then I recommend you study the DP-3T Whitepaper where the larger picture is well described and debated.

If you are a mobile app developer or a tech-savvy person in general, someone that can read and experiment with a shell script or javascript or someone curious enough to know more how applied cryptography works, then read on and you’ll be surprised how easy this is.

From now on I will dive into the nitty-gritty of DP-3T providing code, data-flows to demonstrate a working implementation of cryptographic components any application can use to implement DP-3T.

the cryptographic computations run in secure isolation from the host on the free and open source Zenroom VM software
results are fully inter-operable across languages and platforms, from bare-metal (compiled byte-code) to in-browser computation (webassembly)
the implementation in Zencode language (prolog-like DSL, dialect of Cucumber BDD) makes it very easy to adopt and customize

DP-3T is a privacy-friendly, decentralized solution that reveals minimal information to the back-end server and relies a lot on end-to-end encryption

In a nutshell

End-to-end encryption means that in this architecture most of the computation needs will be done inside mobile phones and not on a central server. Every phone will be broadcasting and storing “bluetooth low energy” beacons: small 16-byte unique strings found around the ether. Now and then phones will process what they have collected to trace and proof the proximity of devices, therefore the proximity is limited by how far these bluetooth signals can reach.

Processing and storing of observed Ephemeral IDs (artwork by Wouter Lueks)

The proximity tracing process is supported by a back-end server that shares infection information with the app running on each phone, but by means of cryptography it will not know who is who nor will be able to track people.

A mobile app implementing this scheme shall be capable of computing through 3 basic steps:

Setup the secret day key (SK)
Create a list of Ephemeral IDs (EphIDs)
Check the proximity to “infected” devices

The following sections will demonstrate how an application can do that by embedding the Zenroom VM (1MB payload approx.) and using the special “DP3T” Zencode scenario.

To jump-start and run this locally:

git clone https://github.com/decodeproject/zenroom

Then download the binary for your platform from: https://zenroom.org/#downloads
and run the commands

cd test/zencode_dp3t
./run.sh

You can also look here what is inside the run.sh script, which can be tweaked.

Zenroom 📝 Documentation

Zenroom is a portable and independent virtual machine for secure cryptographic operations. Zencode is the name of the language executed by Zenroom: it is simple to understand and can process large data structures while operating cryptographic transformations on them.

(view online)

At the link above you can have a detailed tour of zencode scripts and JSON inputs and outputs of a complete flow for proximity tracing. This implementation is simple to deploy, but also very performant. Zenroom processes a match of 20.000 SK on 9 EphIDs and executes in approximately 2 seconds on a i5 2.4Ghz single core using 4MB of RAM; On a typical ARM based mobile it takes 10 seconds approx.

Compliance test vectors

To help align with other implementations of this protocol I’m sharing my test vectors, aligning with those obtained by other DP-3T developers in this issue:

The vectors are the expected results of the two main cryptographic transformations in DP-3T given known inputs, they are proven correct also considering Zenroom passes FIPS140–2 tests for SHA256 and NIST SP 800–38A tests for AES-CTR (F5.5).

Feedback Welcome

This is a work in progress and feedback is very welcome from people trying this out and building any privacy-preserving proximity-tracing application.

The cryptographic implementation of DP-3T runs on the Zenroom virtual machine and is implemented in portable C99 and readable in Lua: