Lack of clock synchronization can be exploited by a weak adversary to trigger (targeted) false positive #14
Description
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.