Lack of clock synchronization can be exploited by a weak adversary to trigger (targeted) false positive

[LCBH]

Once #12 has been fixed (see PR #13), the reference implementation (and the specification from the white paper) suffers from a different attack when phones' clocks are not perfectly synchronized.

An attacker can then trigger a false positive in a target phone's victim by broadcasting some EphID he has computed himself from infected SKs. This timing of the different actions is really important, which makes it hard to carry it out. But I guess an attacker could retry until this works. I don't know exactly how to assess the practical implication of this attack.

Details are in the PoC you can find there: https://github.com/LCBH/reference_implementation/blob/PoC_desynch/testAttack.py
Just type python3 testAttack.py with LoCostDP3T.py in the same folder. Here is the output that should be self-explanatory:

Current time: 2020-04-01 00:00:01.
Day 0: Alice, Bob, and Isidor do not have contact. Isidor SK: [ce5fd1a1...]. Current Isidor's date: [2020-04-01 00:00:01].
   + New day for Isidor
   + New day for Alice
Day 1: Alice, Bob, and Isidor do not have contact. Isidor SK: [568d5efa...]. Current Isidor's date: [2020-04-02 00:00:01].
   + New day for Isidor
   + New day for Alice
Day 2: Alice, Bob, and Isidor do not have contact. Isidor SK: [00bb2c63...]. Current Isidor's date: [2020-04-03 00:00:01].
   + New day for Isidor
   + New day for Alice
Day 3: Alice, Bob, and Isidor do not have contact. Isidor SK: [6150c529...]. Current Isidor's date: [2020-04-04 00:00:01].
   + New day for Isidor
   + New day for Alice

Day 4: Isidor is tested positive and publish SK_t[day-2]=[00bb2c63...] with infectious time=[2020-04-03 00:00:01]. Current SK is [9a30016a...]. So far, not a single entity has received an EphID. Current Isidor's date: [2020-04-05 00:00:01].

 --> Step 1. Attacker fetches Isidor's infected SK_t at time [2020-04-05 00:00:01] and compute a valid EphID corresponding to time [2020-04-04 23:59:59].
     Fake EphID: [c293f5fc...] for SK=[6150c529...].

 --> Step 2. Alice's internal clock is 2 minutes ahead of time [2020-04-04 23:57:49] and receives the fake EphID multiple times.

 --> Step 3. After a while (next day, but it does not really matter), Alice checks if she is at risk. She is not but DP-3T concludes that she is:
   + New day for Isidor
   + New day for Alice
At risk, observed c293f5fcdacb77c3b8e62a4f4003a225 on day (2020-04-05)-1 day(s) for 126 seconds

It seems that a more conservative choice of the time window for which EphIDs have to be computed could be necessary (in the specification). The current check consider a fixed window (instead of a moving window), which makes it discontinuous, hence the attack.

[wouterl]

Good point! I don't think this is fixed in the rewritten implementation, although we tried to be much more careful with how batches of keys are released, this boundary condition is still present.

I believe the fix would be to delay releasing a batch of keys by a few minutes. So they keys that are valid up to 16:00h would be released at 16:10h for example. Then even if Alice's clock is 10 minutes slow, she will receive all adversarially broadcasted EphIDs after 16:00h and will therefore not consider them.

Does this work?