Incorrect IV Initialisation for AES-256-GCM and Constraints on the Number of Invocations

[harrison-tc]

The current implementation does not follow NIST Special Publication 800-38D, in particular Section 8.2 IV Constructions and 8.3 Constraints on the Number of Invocations regarding the secret key.

To mitigate 8.2: IVs can be converted to deterministic construction per 8.2.1.
To mitigate 8.3: Temporary IDs should use an ephemeral key derived from the secret key and uid values, so that the same key is not used for more than 2^32 operations.

The current implementation may permit an adversary to fabricate IDs or Upload Tokens, if they collect duplicated IVs or more than 2^32 encryption operations are performed against the same key.

[loganaden]

I think that the specification may need to be reviewed:

https://bluetrace.io/static/bluetrace_whitepaper-938063656596c104632def383eb33b3c.pdf

symmetrically with AES-256-GCM and then Base64 encoded
[Figure 2]. Only the health authority holds the
secret key to encrypt and decrypt TempIDs. Each TempID
is generated with a random Initialisation Vector
(IV).

I would suggest adding text along the lines of:
Each TempID should be generated with a unique Initialisation Vector.

[qtangs]

@harrison-tc , thanks for raising the issue. We have carefully reviewed the concerns. Here is our response:

• Regarding 8.2: we use a RBG-based construction of IV with a random-field length of 128 bits, satisfying the length criteria. The instantiations of the RBGs are performed on cloud-based virtual machines running on different physical hardware servers, hence they are expected to be independent.
• Regarding 8.3: we apply key rotations in our implementation and would recommend all implementations to apply the same measure. This ensures the same set of secret key + IV is not used for more than 2^32 operations.

[harrison-tc]

Gotcha on 8.2.

8.3 is a general limit on invocations with a unique key, rather than a key + IV.

At 2^32 operations, this leaves OpenTrace with ~1B "user/hours" or about 1.5M users over a 30 day period if it runs all the time, since the vast majority of operations will be the generation of TempIDs. Since they're pre-generated, it would run out at some point before that limit, but without knowing how efficiently TempIDs are utilised, I'm not sure what that difference would be.

It also may be possible for an adversarial client to exhaust this pool prematurely by requesting TempIDs excessively, depending on what rate limits Firebase imposes on the Cloud Function.

[loganaden]

@qtangs can the spec be uploaded on MD format instead of PDF so that we can at least send PRs ?

[harrison-tc]

Assigned CVE-2020-11872

[harrison-tc]

Should be noted that this breaks some of the protections in Section 8 of the standards paper in the spec, as the ability to counterfeit authentication could ultimately allow someone to generate temporary IDs with altered start and end times that would pass authentication checks.

[harrison-tc]

I saw the update on Readme, am I correct in assuming that it doesn't appear to be possible to rotate the key in this implementation, as invalid tempIDs from the old key will persist until they have expired, and subsequent attempts to decrypt IDs that were gathered prior to rotation with the built in functions would not be successful?