3rd-ways-for-EU-exposure-notification / project-DESIRE

Inria 3rd-way proposal for a European Exposure Notification System

Other

12 stars 0 forks source link

Hey,

Thanks for this version, there are many things that seem interesting improvements compared to Robert :)

There is something I don't really understand: What is the point of EK_A? As I understand, you use it to encrypt (and authenticate ideally (footnote 12)) the data in IDTable_A .

In Exposure Status Request

The server decrypts using EK_A, and continues. At this step, an "implicit" authentication might be interesting, so i think your footnote 12 is important. (I'd have a comment, iAssuming the server deletes EK_A if he is nothing but 100% trustworthy (not even HBC) is very strong... but oddly i think it's not necessarily useful)

Section 3 Risk Analysis

You say that encryption is here in case of data breach. From my understanding, there are 4 things in IDTable_A: The "connections", SRE_A, and UN_A (and LPEM_A).

SRE_A, is the last epoch someone sent a Status Request, hard to find a use if it's anonymous
UN_A is a bit saying whether the user had an alert. While sensitive, ID_A is supposed to be an anonymous of A.
The rest are data that concerns the social graph, but here whatever attacks appear in case of data breach, also exists in case of malicious server, and as this data (mostly) only concerns the social graph (DH + ROM clearly hides the rest), either the server can do it, either he cannot...
There is also LPEM but it is never updated (the exposure time is sent by the sick users for example)

So it seems really strange to have an encryption, with facultative authentication.

If I am an adversary interested in the social graph, my attacks are (at best) the same as the server If I want to deanonymize data, same.

However, i might be interested in causing a mess. So i send request for random ID_A, Q=EK'_A If ID_A exist, the server will "decrypt" the data, and without authentication will then rencrypt it and cause a mess:

(ECB) If each element is Encrypted just with the normal key K=EK_A, it's likely that everything will stay the same, except SRE_A that'll become pure random (DEC_K(ENC_Q(time)) is likely close to random)
(CBC/CFB/CTR) If elements are encrypted with key derivation according to their position, and preivous then editing the list will likely change the position of elements, and completety derp the reencryption of those after. So if SRE_A is at the start...
If it's a global encryption, the automatic edition of the SRE_A will also derps everything

Authentication seems really important, to avoid DOS against someone, and (oddly) encryption is probably superfluous if you consider the social graph to be protected against malicious server. (Authentication could be as trivial as the server checking that the decryption has indeed x leading zeros)

Did I miss something? Of course, the space in which ID lives could be huge, making a collision highly unlikely. In this case neither auth or enc would even be required, and it would reduce the server load (which with millions of daily users would likely be happy to avoid several enc/dec for each for them) :)

Hello @oblazy. We are happy to see you recognize improvements compared to ROBERT. Great.

1- Small comment regarding the (supposedly) "very strong assumption"

this measure (EK_A encryption) is meant to protect against external attackers who may succeed to connect to the server, not against the authority, so this latter has no reason not to erase EK_A. And if we assume a collusion, then the adversary model is even stronger than our honest but curious one.

2- About the fact the server cannot derive any social graph:

I really don’t know why you mention « the social graph »? In fact:

the server keeps only « a global list, EList, of all exposed (token,day,t) tuples (coming from all infected users) » (p.10, top). Hard to derive any social graph as this list is populated by all the uploaded PET tokens of all users tested positive. If you assume (as we do) that the various PET tokens of a user are mixed with that of other users, there’s little you can deduce. And during the declaration, the ID_A of the user tested positive is not uploaded (fortunately). Hard to derive any social graph here.
the server keeps for each app (i.e., behind an ID_A), the « LEPM_A (“List of Exposed PET Metadata”) » (p. 6, bottom). This list is only composed of a couple <day of encounter, duration of encounter>. There’s nothing else. The PET token is not stored in the LEPM_A. Hard to derive any social graph here also.
additionally, a PET token identifies a single encounter, and the server cannot link a PET token back to any EBID nor anything that could be attached to a user.
finally the use of the two lists within the app prevents the authority to create any link between what PET tokens are uploaded during a status request and what PET tokens are uploaded during an infected node declaration. That’s why we introduced these two lists. Even if the authority tries to compare these PET tokens, it won’t go anywhere.
during an upload of PET tokens of a status request, the app can easily upload fake PET tokens. Pretty easy and undistinguishable by the server: there won’t be any match in the EList, that’s all. And it will prevent the authority to know how many encounters this user had that day.

We really took great care in « preventing by design » any graph inference, not just by assuming the server is honest but curious. That’s a great improvement of DESIRE.

Do you agree or is there anything I’ve missed? It does not answer your question but this is essential since you suggest the opposite.

3- About a DOS if the attacker targets random ID_A with erroneous EK_A

Indeed, it could be an issue, which is why « we recommend the use of an authenticated encryption scheme. » But this claim is in that case too weak and the footnote should be changed. I can also imagine another protection. We’ll discuss internally and come back to you.

Thank you for your valuable feedback. Cheers.