Specified per-SHC revocation

[christianpaquin]

We are starting to hear interest in revocation schemes from jurisdictions that are detecting fraud in their own issuance history. In order to promote interoperability, the framework should specify an optional mechanism to enable this.

See related discussion in #204.

The proposed way is to add the SHA-256 digest of the card's JWS to a per-kid revocation list; this results in a unique string that can be recognized by verifiers. Associating the lists with the corresponding issuing key limits the size of the card revocation list as there will be an upper max limit when the key is rotated.

After further analysis, the approached specified here will not work. Due to ECDSA malleability, hash(JWS) cannot be used as a revocation identifier, as it can be evaded.

[jdkizer9]

Does this require that issuers manage a hash list for all issued SHCs (or at least be able to regenerate them) so they could potentially revoke them at a later point?

EDIT: Nevermind, I see:

If individual revocation of SMART Health Cards is not possible (because the issued JWS were not recorded, or if the affected set is unknown), then an issuer SHOULD revoke its issuing key, and allow users to obtain new Health Cards

[christianpaquin]

Does this require that issuers manage a hash list for all issued SHCs (or at least be able to regenerate them) so they could potentially revoke them at a later point?

EDIT: Nevermind, I see: [...]

Still, it's worth noting that to enable this, digests (or data used to calculate them, such as the JWS or QR code) indeed need to be stored by issuers, because the final, signed JWS can't be regenerated from the FHIR bundle: ECDSA is a randomized algorithm, so a fresh signature on the same data will be different, and therefore have a different digest. We considered revoking on the basis of other immutable data, but this would mean that all future SHC issued for this data would be invalid; e.g., someone gets a QR code by mistake (or fraudulently), issuer wants to revoke that particular one, but later the user gets an official valid SHC with the same FHIR data; this new one should have a different revocation handle.

[jmandel]

We considered revoking on the basis of other immutable data, but this would mean that all future SHC issued for this data would be invalid

Formally the revocation could be "for these immutable data and a nbfs prior to XXX" if that was the main concern. (But I think incorporating non-opaque individual-level data elements in a revocation scheme is its own concern.)

[pvillela]

An alternative to computing the SHA-256 digest of the JWS could be to use the r (random number component) of the card's digital signature's (r, s) pair. That would also be 256 bits long but would not require additional computation. The r component is essentially guaranteed to be unique as a collision of r values poses a threat of discovery of the private key.

[pvillela]

An alternative to posting a list of revoked identifiers on a per-kid basis is to use a cryptographic accumulator. We can either use a single accumulator to represent the revocation set across all kids or use a per-kid accumulator. We could consider including the per-kid accumulator as an additional optional field in each public key object in the existing jwks.json file. The significant advantage of using accumulators is that the revocation information does not grow in size as revocations are added over time. This can be especially advantageous for storage-constrained mobile devices. Instead of having to retrieve and cache a potentially unbounded list of identifiers, the verifier only needs to retrieve and cache a single accumulator or one accumulator per kid. By the way, revocations in the Sovrin network are implemented with accumulators.

[christianpaquin]

An alternative to computing the SHA-256 digest of the JWS could be to use the r (random number component) of the card's digital signature's (r, s) pair.

Interesting idea. I think the hash of the overall card entropy however provides a better identifier; it protects against implementation errors (faulty random generators with collision risks) and potential DoS attacks (an issuer issuing a SHC with a matching r and revoking it, in order to invalidate someone else's SHC). Also, I'd prefer not overly rely on the fact that ECDSA is currently hardcoded. We can imagine the SHC framework to expend and support more signature algs (e.g., post-quantum), relying on an alg-specific value would require re-designing the revocation mechanim.

[christianpaquin]

An alternative to posting a list of revoked identifiers on a per-kid basis is to use a cryptographic accumulator.

Another interesting suggestion; accumulators indeed provide interesting characteristics. My experience with them has been that they are complex; do you have a specific scheme in mind that you think would be somewhat easily implemented and deployed? We have one advantage (wrt revocation) over other credential types: SHC don't have private keys; revocation is therefore a mean to invalidate wrongly issued cards vs. compromised ones (presumably a rarer event). Moreover, issuers are in control of their CRL's size; if it gets too big (according to a given criteria), they can simply rotate their key.

[pvillela]

An alternative to posting a list of revoked identifiers on a per-kid basis is to use a cryptographic accumulator.

Another interesting suggestion; accumulators indeed provide interesting characteristics. My experience...

I don't have a specific scheme in mind. I don't have direct experience with accumulators but I know they are effectively used for revocations in the Sovrin network. We would be using accumulators only as a compact technique for set membership determination purposes. As long as the solution has a very low probability of false positives and false negatives, other security attributes of accumulators are not important.

Optimizing the size and access to revocation lists is particularly important for verifier apps running on storage-constrained mobile devices that need to cache the revocation lists to operate offline and with fast response times. The alternative of having verifiers check revocations in real time and not cache the revocation lists is impractical for such verifier apps.

One relevant consideration is the desirability of keeping the representation of the revocation lists to a reasonable bounded size. Keep in mind that rotating a key does not really solve the problem as SHC revocations for a given key are quite possible after the key is rotated.

Another advantage, when using an optional accumulator field within each key object in the jwks.json file, is that a verifier can cache revocation lists by simply caching the jwks.jason files and does not have to periodically hit the https://<Issuer URL>/.well-known/revoked-shcs-by/kid/<kid>.json URLs for all possible kid values.

[pvillela]

I withdraw my suggestion to use accumulators to represent revocation lists. I was motivated by their ability to provide a compact representation of sets and their use for revocations in the Sovrin network. As I explored further how accumulators are used in the Sovrin network, it became apparent that the Sovrin use case involves a great deal of complexity (in line with @christianpaquin's comment) and is very different from what I was hoping accumulators could be used for in our case.

Having said that, I still think we should try to address some requirements that are not ideally met by the currently proposed solution:

• Optimizing the size and access to revocation lists is particularly important for verifier apps running on storage-constrained mobile devices that need to cache the revocation lists to operate offline and with fast response times. The alternative of having verifiers check revocations in real time and not cache the revocation lists is impractical for such verifier apps.
• It is desirable to keep the representation of the revocation lists to a reasonable bounded size. There may not be an ideal solution but perhaps a more compact representation of revocation lists can be defined. Keep in mind that rotating a key does not really solve the problem as SHC revocations for a given key are quite possible after the key is rotated.
• It is desirable to limit the time that a verifier who caches revocation lists would need to spend to download all the revocation lists. The current solution would require such a verifier to periodically hit the https://<Issuer URL>/.well-known/revoked-shcs-by/kid/<kid>.json URLs for all possible kid values. Possible mitigations might be:
  • Support the passing of a query parameter with the SHA-256 hash or publication timestamp or last download timestamp for the currently cached list for the given kid so that a new download can be avoided in case there was no change to the revocation list. The number of URLs to be hit would remain the same but access would be sped-up.
  • Use a single per-issuer URL instead of a per-kid URL. In addition, support the passing of a query parameter with the last publication timestamp or last download timestamp, in which case only SHCs revoked since that time would be downloaded.

[jmandel]

Support the passing of a query parameter with the SHA-256 hash or publication timestamp or last download timestamp for the currently cached list for the given kid so that a new download can be avoided

Yes, ETags are a good HTTP solution for this, which hosting and CDN services (including GH Pages) should support out of the box. When you get a file, you get an ETag header, and when you request a file you can say If-None-Match to indicate "I only need a response body if things have changed.

(There's a similar story with If-Modified-Since.)

[christianpaquin]

Dynamic updates would indeed be interesting. One design goal is to keep things simple to deploy for issuers. So far, their identity infrastructure is simple enough (static jwks files), so I’d like to avoid requiring them to setup a live endpoint. A version number or timestamp (surfaced as an etag) could be a good way to version the CRL. We could RECOMMEND only sending the delta CRL if a version/timestamp is requested. X.509 CRLs have a "next update" time, to inform verifiers when to download it next, but that might be too rigid for "emergency" revocation. The presence of a CRL and its version could be advertised in the issuer’s jwks.

As far as size goes, cutting the digest in half to 128-bit (16 bytes) is a no brainer, for security. Cutting it more is possible, but would require more analysis, if we consider adversarial attacks (vs. accidental collisions, which are very unlikely).

I'll take some time to update the proposal with some of these ideas.

[pvillela]

Dynamic updates would indeed be interesting. One design goal is to keep things simple to deploy for issuers ...

I think the following ideas mentioned by @christianpaquin would address my performance concerns related to offline verifier apps:

1. If there is a CRL for a given kid, the issuer MUST advertise the existence of the CRL and its version number by including an optional attribute (e.g., "crlVer") in the corresponding public key object in the jwks.json file.
2. We could RECOMMEND only sending the delta for a kid's CRL if a version number is specified as a query parameter.

In my view, item 1 above is the most important from a verifier's performance perspective. If an issuer implements only item 1 (and not 2) they can have a 100% static implementation of per-kid revocation lists.

[christianpaquin]

I updated this proposal based on comments so far. I added a counter value for the CRL (advertised in an issuer's JWK), which inform verifiers on 1) the revocation support, and 2) the need to re-download.

I haven't addressed the "delta" update yet; I wanted to gauge interest in this functionality first. If desirable, I was thinking of the following: every time the CRL is updated, the issuer updates the kid.json file, but also creates a sibling kid-ctr.json file with ctr being the counter value, containing only the newly revoked digests.

This way, a verifier could either request the full CRL, or only the deltas since the last ctr it saw. I was thinking of this approach (vs. query params and etag discussed above) to simplify the issuer implementation (static files only).

[jmandel]

We could also consider a scheme using append-only CRL files (e.g., a list of kids separated by newlines) and servers could optionally support https://developer.mozilla.org/en-US/docs/Web/HTTP/Range_requests (which many static hosting services support out of the box).

The jwks.json could advertise the current file length + hash, and clients could request a range to catch up.

[jmandel]

As an example, say the revocation list looks like https://gist.github.com/jmandel/4826077d4e192065199a030e3dc10500

After first update

• revocation list looks like this
• JWKS advertises: "crl": {"bytes": 64, "hash": "ceb2ff3dc4806c01..."}
• Client can

  $ curl https://gist.githubusercontent.com/jmandel/4826077d4e192065199a030e3dc10500/raw/b7908dc23321767f268bf20cc03467ce848dde46/revoked-for-kid-3Kfdg-XwP-7gXyywtUfUADwBumDOPKMQx-iELL11W9s.txt \
  -H 'Range: bytes=0-64'
  28dbefb0554ec0c6d8cfd71b51d5d75866ce9c02afd785e8f16ced034535cd4d

After second update:

• revocation list looks like this
• JWKS advertises: "crl": {"bytes": 129, "hash": "860b4abd59930760..."}
• Client can

$ curl https://gist.githubusercontent.com/jmandel/4826077d4e192065199a030e3dc10500/raw/b7908dc23321767f268bf20cc03467ce848dde46/revoked-for-kid-3Kfdg-XwP-7gXyywtUfUADwBumDOPKMQx-iELL11W9s.txt \
-H 'Range: bytes=65-'
ff0ebe7bd075b68164509d755ea1ddafcbb82d2dd2c785776001b387bf5b4a3f

[jmandel]

Note: the story for compressed content encoding together with bytes isn't great though. In this scheme, the better format for the append-only revocation files would be binary files where each revoked SHC is represented by the first 16 bytes of its sha256 hash (or whatever proxy identifier we define), so no compression is required/needed and each revoked SHC spans a (n*16, (n+1)*16) range.

[christianpaquin]

Interesting idea. The higher-bit decision we have to make is if we want to make the scheme dynamic or static on the issuer side. If static, then we have a few ideas expressed in this thread to consider. This PR discussion is getting lengthy, so I'll summarize the various options in a stand-alone doc, and share on zulip to hopefully get more engagement from SHC issuers.

[jmandel]

Sounds good. We should keep in mind that we don't necessarily need to solve the efficiency problem for all clients in order to establish a system that works efficiently. I.e., i publishers have an easy path to correctness, we can think about downstream services that really optimize the client experience on top of that (for example, an org like VCI interleaving revocation data we consume from multiple issuers and offering an API for downloading diffs of the whole set in one call -- this could be done dynamically or perhaps even statically with a big old matrix of files).

[christianpaquin]

I'll summarize the various options in a stand-alone doc

See #204

[christianpaquin]

We are converging on a design. I'd like to have a discussion next week with those interested, to mark this PR as "ready for review". Those who can't make it will have the opportunity to comment on the final proposal before it is merged. Please let me know of your availability here: https://www.when2meet.com/?13543272-5VH8Z

[christianpaquin]

Tuesday Nov 9th at 2:30pm Eastern Time is the only availability that everyone can make; let's meet then. Teams meeting link sent to those with known email addresses; for others (@pvillela), use this link.

[pmccabensds]

Hi Everyone.. jumping onto the bandwagon a bit late. However I wanted to clarify my understanding on what is being proposed.

Can somebody please confirm if the proposed SHA-256 Hash would contain a date related to the issuance, ie. the nbf element.

If this is indeed the case, for Nova Scotia, we do not currently restrict how many QR codes one can download, meaning that any revocation scheme that involves a hash including an issuance date would not be feasible as we may have several dozen or hundred PVCs with the same data, just a different nbf date.

If I understand the proposal by @pvillela - this would better solve the problem for our use case as we would only have to revoke a single set of data, regardless of the nbf date.

Thanks, Patrick

[christianpaquin]

if the proposed SHA-256 Hash would contain a date related to the issuance, ie. the nbf element.

The current proposal (changes to the spec proposed in this PR) does not involve a timestamp (nbf); the SHA-256 digest identifies a particular issued SHC (i.e., a QR code). A newly issued QR code with a different nbf would have in a different digest that would need to be added to the CRL.

A time-based approach has been discussed on this thread; and it seems that it would better serve your situation.

[pmccabensds]

Thanks Christian. This is exactly what I'm getting at.. "A newly issued QR code with a different nbf would have in a different digest that would need to be added to the CRL."

In our case, since we could technically have a fraudulent user create 10, 000 QR codes (and we didn't see that as a problem previously) I would much prefer to be able to revoke all of those using a single hash, instead of 10K hashes just for scalability reasons alone.

I haven't really dug into the details of the time-based approach to see if that's a better fit. As mentioned, something along the lines of what @pvillela is suggesting where the hash does not include the NBF date seems like it would address this problem as well.

I'm unfortunately double booked for your meeting this afternoon, would have liked to join to add to the discussion. However, hoping that our use case can help to influence the direction as I don't think the current proposal can scale, especially where we might already have many thousands of copies already floating around.

[jmandel]

As mentioned, something along the lines of what @pvillela is suggesting where the hash does not include the NBF date seems like it would address this problem as well.

We have not yet identified a way to accomplish this which is both safe (from a privacy perspective) and implementable without some issuance-time tracking of issued artifacts. We will certainly bring this up in our call and can include notes on this point.

[bradhead]

Thanks Christian. This is exactly what I'm getting at.. "A newly issued QR code with a different nbf would have in a different digest that would need to be added to the CRL."

In our case, since we could technically have a fraudulent user create 10, 000 QR codes (and we didn't see that as a problem previously) I would much prefer to be able to revoke all of those using a single hash, instead of 10K hashes just for scalability reasons alone.

I haven't really dug into the details of the time-based approach to see if that's a better fit. As mentioned, something along the lines of what @pvillela is suggesting where the hash does not include the NBF date seems like it would address this problem as well.

I'm unfortunately double booked for your meeting this afternoon, would have liked to join to add to the discussion. However, hoping that our use case can help to influence the direction as I don't think the current proposal can scale, especially where we might already have many thousands of copies already floating around.

In British Columbia, we use the same model... The citizen acquires their SHC self-service and we may issue new nbf, so same concern here, so would be interested in digging in on the time based model. Our preference in a utopia would be to revoke the individual FHIR immunization record contained in the SHC, but I realize that is very challenging.

[christianpaquin]

Our preference in a utopia would be to revoke the individual FHIR immunization record contained in the SHC, but I realize that is very challenging.

We've been hearing this more and more (many issuers have not recorded their issued QR, so wouldn't be able to revoke existing cards). A time-constrained revocation digest that takes as input the FHIR data might (per @pvillela suggestion) might be the most practical approach.

[pmccabensds]

As mentioned, something along the lines of what @pvillela is suggesting where the hash does not include the NBF date seems like it would address this problem as well.

We have not yet identified a way to accomplish this which is both safe (from a privacy perspective) and implementable without some issuance-time tracking of issued artifacts. We will certainly bring this up in our call and can include notes on this point.

Thanks @jmandel

Regarding the privacy comment. If I understand correctly, is the concern that one could in theory brute force the their way to knowing that a given set of data was revoked ? Basically, one could try millions of combinations of names, dob, vaccine information, etc, create the SHA-256 hash and compare against the list ?

If that understanding is correct, can you help me understand the actual risk here ?

[AndrewSmith247]

Further to the meeting, I am still thinking that signing of the CRL adds value. In an organization like the Province of Nova Scotia, there are many people that have access to the servers hosting our JWKS.json and soon to be CRL but the intersect of those people with parties that have access to the private key is minimal. If a person on a server team wanted to spite someone, they need only hash the FHIR data for a person (captured or built) and inject it into the CRL. They wouldn’t want to know, change or want to change the public key as they want the particular individual to be affected and not people en masse. While I am sure this is an edge case, this sort of targeted attack would be hard to identify but easy to have prevented.

I also feel that we have been making assumptions on the hashing algorithm for the CRL hashes and this information needs to be identified somewhere, perhaps within the CRL. We assume SHA-256 which is the minimum acceptable hashing function for interoperability according to NIST (https://csrc.nist.gov/projects/hash-functions/nist-policy-on-hash-functions) and in the future this may change. Providing the algorithm would also assist other jurisdictions consume our CRL.

[christianpaquin]

many people that have access to the servers hosting our JWKS.json and soon to be CRL

If the host is not secure, then someone could replace the jwks.json file and forge all sorts of SHCs (not with the real private key, but with a fake one corresponding to the "new" public key). Protection of these resources are critical, but I don't think CRLs are more important than jwks.json.

I also feel that we have been making assumptions on the hashing algorithm for the CRL hashes and this information needs to be identified somewhere, perhaps within the CRL.

The SHC framework already makes hard-coded cryptographic choices; SHA-256 is already used for kid calculation and in the ECDSA P256 signature. It is proposed to use the same for CRL.

[christianpaquin]

Tuesday Nov 9th at 2:30pm Eastern Time is the only availability that everyone can make; let's meet then.

We had a productive meeting with many folks from across the board. In order to inform the next steps and propose an update, we’d like to get more information regarding the capabilities of issuers wrt the proposed options. I’ll create a questionnaire tomorrow and invite issuers to answer it.

[christianpaquin]

In order to inform the next steps and propose an update, we’d like to get more information regarding the capabilities of issuers wrt the proposed options. I’ll create a questionnaire tomorrow and invite issuers to answer it.

Here it is: I'd invite issuers to answer this questionnaire.

[christianpaquin]

See new revocation proposal in PR #205, superseding this one.