Security of covid-19 tracing apps (part 5)
In part 3 and part 4 of this series I described a privacy centric covid-19 tracking app protocol. This time I will try to compare it “Part 3+4” with other existing protocols out there.
My aim is to set the bar high for privacy for such apps. If the privacy is proven in the protocol, more people will actually use the system, and the attack/misuse surface of such use is minimal.
I would like to start by categorizing such tracking systems into two categories; type 1 and type 2.
Imagine that Igor (the infected person) meets Bob. Bob needs to hand Igor some information X that he may use later to warn Bob about a possible infection.
For a type 1 system, Bob selects any key he likes. For Igor, the value of X is seemingly random. But Bob will know that it was Igor who received X, and no one else.
For a type 2 system, Bob can’t choose the value of X, rather it is handed to him by the system. A simple system could be forcing Bob to reuse the same id X over and over. If Bob receives a warning about a possible infection, he will not know which of the users he met that issues the warning, unless there was only one rendezvous.
I will prove that any type 1 system is leaking data, namely Bob will always know that Igor is infected by the virus once he receives a warning. There is no encryption that can change this fact — given any encryption scheme, Bob is free to create a new user profile at every rendezvous. By matching a warning with a profile, he will always know that the meeting with Igor was the only place he could have been infected.
With this proof, I would not recommend any system of type 1 to be implemented in a large scale.
Some systems of type 1, not providing best privacy are:
- DP-3T
- TraceTogether / BlueTrace
- Coalition Network
- ITO App protocol
- Covid Watch
- CoEpi
- Covid Trace
- Apple and Google Privacy-Preserving Contact Tracing (1)
(1) Though the Apple/Google is of type 2 in most senses, it falls short by allowing a user to easily generate an identity simply by choosing a random number. I may not be aware of measures they have put in place to restrict a user to a single identity
For the type 2 system, you can actually achieve more privacy using encryption. As Bob is not free to chose X, he can’t create a system to track every rendezvous with an X. For instance, if Bob is forced to use tokens X1, X2, X3 and X4, a warning may be issued stating that either X1, X2, X3 or X4 has issued an infection warning, using encryption.
For any type 2 system, you need to ensure that every user in the system only has one identity. This mandates a central authority that, at the very least, publishes at least one public key for each user of the system. To make sure that each user has only one key, the central authority will need to know the real identity of all users.
Because the values X emitted in a type 2 system are predetermined, an attacker may be able to know what they are. By placing robots at strategic places, you could collect the movements of these X values in time, possibly linking them to a single person. Therefore, it is of great importance that the values X emitted by Bob are difficult to pinpoint to a single person in the system, but still provide some information so that Bob may be warned later.
Some systems of type 2 are:
- “Part 3+4", though not implemented yet
Though Apple and Google’s system is of type 2, it still fall short of hiding Igor’s identity, as it seems to be easy to generate new identities by choosing a random number
I believe at this point that only type 1 or type 2 are the viable options for covid-19 tracking. And I would always prefer a good type 2 system as it does not allow anyone to learn the identity of an infected person. The central authority only needs to be trusted with one task — maintaining exactly one key for each user.
