K_S rotation?

[vaudenay]

If K_S leaks, this is a disaster. It could be wise to be able to rotate it.
By changing K_S, only the next few epochs which are already prepared would be compromised.

If K_S can evolve, the Hello messages would need to say which K_S version they are based on.
This could be done in clear, or like the country code to hide it.

Maybe the same holds for K_G (although it may be less sensitive).

[ramsestom]

I don't really understand the need of a server global KS key to be honnest.
The server could generate each EBID with a unique random KS key each time and store a mapping of EBID<->KS key into a local secured table that he could lookup to decrypt an EBID when needed.
And even with a different KS key each time, I don't really like to have the user permanant ID encrypted into a publicly broacasted EBID. It might make more sense for the server to generate "random" EBID and to only maintain a secured ID<->EBID lookup table rather than decrypting the ID from the EBID...

[ReichertL]

I guess the database would become rather large when doing a direct mapping..

[ramsestom]

I guess the database would become rather large when doing a direct mapping..

Good point.
I made a quick estimation of the ID<-> EBID lookup table size in case of 1 billion users and a 30days EBID storage period (with rotation of user's EBID every 15min) and the table would be ~40Tb. Even if this is a rather generous estimate (there is no country with 1 billion potential users in europe and storing EBIDs for 14d rather than 30 days could be enaugh depending on the maximum duration of infectivity of a COVID-19 patient) I agree that it could be an issue. However, it remains something that is doable. So it might be worth discussing it given the risk of revealing all users' IDs from their EBID if the KS key is leaked (but I agree that the best compromise between security and server capabilities is probably to change the KS key regularly, as suggested by @vaudenay)

[aboutet]

@vaudenay Thanks!
Indeed, K_S rotation could be useful to mitigate the risk in case of leakage of this key.
TEE on a separate node could be also useful to secure this key outside the server, only to generate the EBID or to retrieve the ID from a EBID.

@ramsestom as mentioned, a such database would become too large.
The proposed generation of EBID avoid to maintain a such mapping.