The EU vaccine passport compromise and how to (maybe) fix it

Posted by ekr on 29 Oct 2021

Bleeping Computer reports that there has been some compromise of the EU COVID-19 vaccination certificate system. As I wrote, the EU system depends on digital signatures, with each jurisdiction having its of set of private keys.

What Happened? #

It's currently a bit unclear what has happened here, but the situation appears to be:

• There are multiple bogus appearing certificates floating around for names such as Adolf Hitler, Spongebob Squarepants, and the always popular Joe Mama.

• These certificates are signed with several different private keys (mostly Macedonia, but also France and Poland).

• These certificates also have country indications (i.e., they claim to be from countries) that are different than the jurisdiction associated with the signing key.

• We are seeing online offers to generate bogus passports for people for 300 euros.

[The above is largely based on this analysis by denysvitali.]

It's clear from this that something is wrong, but the question is what? The first major possibility is one or more private keys has actually leaked. This is consistent with what we're seeing, but so far nobody has published it. The most I've seen is this screenshot (from Bleeping Computer) that alleges to be a partial key. However, I do not believe that this partial a key is sufficient to verify the key is valid.^[1]

The other possibility is that someone has compromised one of the systems used to issue certificates rather than the key itself. This would also allow them to issue new certificates with fake information but would be far more recoverable, for reasons I'll discuss below. At present, we don't have enough information to distinguish these cases, though as denysvatili points out, if we saw a validly signed credential that was clearly semantically invalid (e.g., had a date far in the past) then that would be suggestive of key compromise because the signing systems probably have some mechanisms to prevent (mostly accidental) signing of such credentials.

Recovering from Compromise #

Whatever the cause, it seems likely that:

1. The attacker(s) have the ongoing capability to generate new bogus certificates. This capability needs to be disabled.

2. There are existing certificates for non-obviously bogus names. These certificates should be invalidated.

In general, this kind of PKI system isn't designed to smoothly recover from this kind of system compromise. People typically just assume that you'll revoke the signing key and reissue certificates. This will obviously work but is a large burden on existing users; for people who are using one of the official apps, the EU can just issue an update that makes it automatically retrieve a new certificate, but this won't work for people who have printed the certificate or stored it in something like Apple Wallet. Even for app users, you have to worry about people who are offline for a while or about bugs which cause automatic issuance to fail. For that reason, it's worth asking if we can do better, though exactly what we can do depends a lot on the system design and the nature of the compromise.

System Compromise #

If the signing system has been compromised but the key has not been, then it's possible to remove the attacker's ability to generate new certificates by fixing the compromise. In the short term, whatever system actually does the issuance can be taken completely offline. This will prevent issuance of both bogus and valid certificates, and so it's also necessary to close whatever avenues were used to compromise the system (and whatever new avenues the attackers have created). It may simply be easier to deploy a new uncompromised system.

This leaves us with the problem of invalidating the bogus certificates that already exist. As noted above, one traditional approach here would be to just revoke the signing key and force everyone to get new certificates, but that's not ideal.

If you can identify the invalid issued certificates, then it is better to somehow individually revoke them, thus avoiding disturbing valid users. Whether this is possible depends on what kinds of records you have kept. In an ideal world, a system like this would keep a copy of every certificate it issued (possibly publishing them to something like a Certificate Transparency log). You should be able to combine this with the records you used for the original issuance (you have those, right?) to identify which certificates were actually valid. This is the best case scenario and then you just publish a list of the invalid certs (or their hashes) to the app, which can reject them.

One complication here is that the EU system does not appear to contain a revocation mechanism for individual credentials, so you'll probably need an app update to ship that. As long as everyone uses the EU's verification app, this is probably not a big deal, but if they don't, then things get complicated fast.

It's also possible you only have partial records (e.g., just a list of the valid certificates). Your options here depend on the information you have an the structure of the certificates. For instance:

• If you have a list of valid certificates and all certificates have sequential sequence numbers then you can discover the invalid ones by elimination and revoke those.

• If you just have a list of valid certificates, you can have apps check aganst that list (see below for more details on this).

• If you just know when the period of compromise occurred, you can have the app reject certificates in that date range; this will inconvenience some valid users but not most.^[2]

Note that the latter two options require changing the verification app, but as noted above, in this case it looks like any revocation would require changing the app.

Depending on how many bogus certificates were issued, this may all be more trouble than it's worth. A system like this can survive a modest amount of fraud -- especially because vaccination doesn't confer perfect immunity anyway -- so if it's just a few certificates, it may be easier to just ignore the problem, especially if the alternative is inconveniencing a lot of legitimate users. On the other hand, if compromised certificates are widespread you probably need to do something.

Note that in this case, you may actually not even need to revoke and reissue the signing key, as long as you're sure it wasn't compromised. On the other hand, it might be logistically easier if, for instance, you need to set up a parallel system.

Key Compromise #

The situation with key compromise is quite a bit worse because the attacker can make as many certificates as they want with any contents they want. This makes it impossible to revoke all the invalid certificates. The only real option here to contain the compromise is to revoke and reissue the signing key.

Unfortunately, this invalidates all existing certificates. Naively, you would need to reissue all of them with the new signing key, but if you kept copies of all the valid certificates, then it might be possible to do better. One obvious approach would be to stand up a service (a la OCSP) which tells whether a given certificate is valid or not. The obvious problem here is that this creates a tracking vector: the server now knows where each user is because of which apps ask about them.

An alternative approach is just to publish hashes of all of the valid certificates.^[3] This is practical if the list is small, but Poland has a population of nearly 40 million. If we use 16 byte hashes^[4], then this is hundreds of megabytes which have to be sent to the application. Naively you might think you could trim this down to just certificates issued inside the window of compromise, but remember that this attacker can issue keys with any date. The same problem applies to listing valid serial numbers. Thus, given the size of this database, this probably isn't workable either.

While there's no perfect solution, there are a number of ways to improve these basic designs. One is to use the "hash prefix" approach used by Safe Browsing. When the app sees a certificate C it computes the hash H(C) and sends the first 10 or so bits of H(C) to the server: the server then sends all hashes with that hash prefix and the app can then check the hash against that list. This is a privacy/bandwidth tradeoff: it improves privacy because the server only knows that one of a thousand or so people presented their credential, though it's still possible to make some inferences about behavior. It improves bandwidth because the app only needs to download a fraction of the database for each user (and only once). Of course, if the app has to verify a lot of users it will quickly end up downloading the whole database anyway.

Another potential design is to just proxy the requests: this would tell the server every time a user presented their credential so it would know how often you were validated, but in theory not where. This is really placing a lot of trust in the proxy though, and you would also need to be very sure that the app itself wasn't leaking its identity on repeated queries (see here for more on using proxies safely).

An alternative design is to use a real Private Information Retrieval (PIR) system. These allow people to retrieve informatio from servers without the server learning what information is being retrieved. Checklist by Kogan and Corrigan-Gibbs is a PIR system designed for Safe Browsing type applications which might be possible to repurpose for this kind of application.

Summary #

It's arguable that I'm overthinking this. After all, we could just reissue everyone's certificates. But that's obviously very disruptive and so it's worth thinking about how we could do better. Also, it's not that uncommon to run into situations where something goes really wrong and the recovery mechanisms built into your system aren't really adequate and you have to get clever to fix things, so it's worth getting some practice in that. Moreover, as you can see from the above, there's a bunch of overlap with other problems, so a solution to one might give you some useful traction on others. Even better, of course, would be to have a system which didn't get compromised in this way.