Inject false "at risk" status

[vaudenay]

If a malicious A who hates B wants B to get an "at risk" status at his next check, A can catch a Hello_B from B, find someone who got infected C and corrupt him to insert Hello_B in his LocalProximityList before he reports.

[pdehaye]

Actually A would achieve more, since this procedure would tell the authority that B is at risk.

[vaudenay]

If I understand well, the authority does not know who is B. Only B, when he contacts the authority to get his status, would learn his "at risk" status. At the same time he will get his status, his account will self-destroy!

[ramsestom]

To me, this is the most problematic issue with the current ROBERT protocol. Reading the specs, this is the first type of worry I thought of, and it looks like I am not the only one ;-) . The current protocol effectively rests the trust of contact information exclusively on the person who are declared infected and shares their contact list. But one or more attackers could perfectly artificially enlarge this contact list in order to generate a very large number of people notified as "at_risk". To do this, it is sufficient to place HELLO messages capture devices in very busy places (public transport, supermarkets, etc.) or simply to aggregate HELLO messages captured by several users and then add all of these HELLO messages to a person's proximityList before it is declared positive for COVID-19 to generate a large number of false "at_risk" positives. The solution to overcome this problem would be to require proof of contact between two EBIDs and to verify this proof of contact to judge the validity of a HELLO message. To do this, the server could assign a private encryption key to each user and then, when a user A detects the EBID_B of user B, he sends his own EBID_A to B, asking him to encrypt it (with possibly other concatenated info such as a timestamp, a random salt ...) with his private key and to send him back this encrypted proof of contact. This proof of contact could then be associated with the HELLO message to verify that user A was indeed the recipient of the HELLO message received. The problem nevertheless arises of knowing at what level to base the verification of HELLO messages associated with their proof of contact. As this requires having the information of the two entities concerned by the contact (EBID_A and EBID_B), it should be done on the trusted server, before sending HELLO messages to the back-end server, otherwise the HELLO messages should be sent to this one with info on the identity of the receiver, which would expose the "identity" of the infected people to the back-end server and would make the whole proximitylist mixing process useless.

EDIT: a proximityList blockchain approach (see my next comment) would be better as it would not requiere the recipient of a HELLO message (i.e. the ID of an infected person) to be leaked to the server.

[aboutet]

@vaudenay Only replaying the HELLO message is not enough to achieve this attack. During the Infected User Declaration, a HELLO message is only valid if the emission time (present in the HELLO message itself) is coherent with the reception time. Consequently, the adversary has also to tamper it own proximity list (containing the reception time) by modifying the behaviour of the application. However, we are working on mitigating this issue.

[vaudenay]

I'm sorry I was not clear. What I suggested was that A would bribe C to insert Hello_B in his list. C would do it maliciously. He would not dare rejecting because of incoherent time.

[ramsestom]

Unfortunately I can't see a solution to this issue without affecting the proximityList mixing protection. One solution would be to have the proximityList of a user A encoded as a blockchain, with one bloc constituted by a HELLO message and encoded by each emitter of this HELLO message. So when user A receive a new HELLO_B message from user B, he send him back its previous proximityList bloc signature and ask B to create a new bloc with it by adding HELLO_B and signing it with its own private key_B. This way, when receiving a proximityList (that could no longer be automatically mixed with a mixnet approach, which is another issue), the server would be able to check the integrity of this list without even having to know the identity (A) of the owner of this proximityList. This integrity check procedure would have to be done on a trusted server though as this can't be done at the indivudal bloc/HELLO message level (so this server must have access to the full proximityList blockchain, he can't receive each bloc or HELLO message one by one).

[vaudenay]

Maybe the solution would be to have an interactive protocol between encounters. C would need a proof of having encountered B to list it. But it could generate a privacy issue too. Probably, B does not want its app to give to C a proof of encounter.

[ramsestom]

This is how I see it:

when A receive an EBID_B from B, he compute a hash H_i where H_i = HASH(EBID_B|H_i-1|timestamp)

A send H_i to B

B sign H_i with his private key SB (known by himself and the back-end server) and return it (H_i_SB) to A

A write H_i in his contacts blockchain (the chain of H_i) and store it with H_i_SB and the matching HELLO message (EBID_B + timestamp...)

When A is diagnosed as infected, he gives his proximityList (the H_i chain with their matching H_i_SB + HELLO message) to the trusted server (the hospital server)

The trusted server ensure the integrity of the A blockchain (= his proximityList) by verifying that H_i = HASH(EBID_B|H_i-1|timestamp) and that the timestamps from the H_i chain are in chronological order

If the list do not seems forged, The trusted server send each HELLO message of the list to the backend-server with the matching H_i and H_i_SB

The back_end server ensure that H_i_SB match H_i given the known SB and reject the HELLO message if not the case

This way:

• the trusted server do not have to know the private key SB of each contact to check the integrity of the proximityList
• A can no longer forge its proximityList and add some fake contacts HELLO messages to it
• the trusted server can still mix and send HELLO messages individually to the the backend-server
• the backend server only has to know the identity of the emitter of the HELLO message (B) to check that it was a real contact. He keeps having no information from A

[aboutet]

an interactive protocol also requires to change the BLE communication mode (from a broadcasting mode to a connected mode)

[ramsestom]

No it would be from scaning mode to connected mode (A is in scanning mode and B is in broadcasting one in my example. When A detect the EBID of B he write a characteristic to some B service that reply to him)

[PRIVATICS-Inria]

Thank you for your question, @vaudenay.

If a malicious A who hates B wants B to get an "at risk" status at his next check, A can catch a Hello_B from B, find someone who got infected C and corrupt him to insert Hello_B in his LocalProximityList before he reports.

This is indeed possible and the issue of replaying messages is common to any system in which messages are broadcasted.

Our scheme mitigates this threat through a timestamp in the hello message and a limited validity period. When receiving a message, an app will verify its timestamp and will discard it if not valid (see step 3 of 5.2. HELLO Message Collection). It is not possible to modify the timestamp in a Hello message without knowing the secret key K_a. Therefore, it is possible to replay a message, but this has to be done during the same epoch the message was originally emitted. We envision an epoch of duration of 15 mins but this parameter can be adjusted.

[vaudenay]

Thanks for the comment. Sorry to insist. I am not sure we understood each other.

I understand that A replaying the HELLO_B message from B to C is defeated by a timestamp which is rejected by the honest app of C.

Is it clear that A could bribe C to modify C's app to make it accept the replayed HELLO_B message and report it?

Maybe one way to fix is to prove to the server that app_C is honest by running it in an enclave.

[Matioupi]

What is the expected/intended timeslot validity ? It's pretty easy to acquire RF data with SDR in none place (let say next to a disease test center) stream it thought internet and broadcast it again with another SDR, all that with really small latency. In order to prevent that scenario which is achievable with actual on the shelf legal means, the timeslot validity would need to be very tight which may be an issue for the regular nominal use case if both phone clocks are not well synced. Typical phone clocks will be within +/- 250 ms to actual UTC time. The timeslot should be at least twice + some margin which allows the attack.

[vaudenay]

To prevent the replay from far away, the location can be used in a similar way as Pietrzak https://eprint.iacr.org/2020/418 but there is a problem with plausible deniability. Someone could use the HELLO_B message as a proof that B was at a given location at a given time to be verified by a nasty authority.

[Matioupi]

@vaudenay and I think that app editor would have a bad time explaining people that the app does not trace their location, but GPS/location service needs to be enabled .

Back to the timeslot length, I missed another point which is the software delay on both platforms which I guess is far from hard real time and I have no idea how long it may take from the local clock query to the actual RF broadcast.

[PRIVATICS-Inria]

Thanks for the comment. Sorry to insist. I am not sure we understood each other.

I understand that A replaying the HELLO_B message from B to C is defeated by a timestamp which is rejected by the honest app of C.

Is it clear that A could bribe C to modify C's app to make it accept the replayed HELLO_B message and report it?

Maybe one way to fix is to prove to the server that app_C is honest by running it in an enclave.

Thanks for the clarification. Indeed, at the moment we have no solution to prevent a modified app from polluting the system this way. A secure enclave could be a solution. Concerning the timing aspects, let’s be clear, our timestamps are in seconds, not fractions of seconds. A tolerance in the range of 10 seconds, could be enough.

[Matioupi]

10 seconds definetly allows for relay attack with simple hardware.

[PRIVATICS-Inria]

Sure, a motivated attacker equiped with the appropriate hardware won't be stopped. However it will avoid other replay attacks that require the attacker to move to a different place and replay EBIDs there.

In any case, with only 16 bytes, you'll have problems including sub-second timestamps (too large). And with general public smartphones where you cannot make any strong assumption regarding their time-synchronisation, you'll have problems for sub-second replay protection too.

[Matioupi]

Do you have an idea/inputs about the legal status of such a replay attack attack (in France) ?

Thanks for pointing out the 16 bits only timestamp in the Hello message. This will also allow the relay attack with a 1 rollover period (~18h12 in the ROBERT v1.0 protocol)