Should requests be assumed to be linkable by the browser?

[bvandersloot-mozilla]

When building a privacy model, selective disclosure is a key feature of the lower protocols and formats being used by this API. However, the properties of that selective disclosure are not well understood. For example, even a minimally disclosed mDoc presentation can be deanonymized to a unique holder by the issuer. The utility of selective disclosure is also challenged by user understanding, the real cost of balking, and the user's perceived cost of balking.

[npdoty]

My understanding has been that meaningful selective disclosure depends on unlinkable presentation (at least, unlinkable between presentations of claims to different origins). If selective disclosure of age or country or some not inherently linkable information also includes a cross-origin unique identifier, enabling trivial collusion and tracking, then I think we couldn't explain it to users with any metaphors like only the age or date of birth part of your license and nothing else.

If we think all presentations will be inherently linkable, then I think we should radically reconsider the framing of this API and just describe it as presenting your whole document, including permanent unique tracking identifiers.

I don't think making presentations unlinkable is easy at all, or that it's possible to make claims with complete certainty, but I think we should have clarity on whether this is a feature for providing selective disclosure and unlinkable presentations, or if it's not.

[martinthomson]

Virtually any selective disclosure system is capable of delivering verifier-verifier unlinkability. That is where two different sites can't tell that a credential is from the same person. This is trivially achieved by having the issuer produce completely separate credentials. Most signature-based systems either include a randomized component, or can be modified to include randomness, such that two credentials cannot be linked.

The bigger challenge is verifier-issuer unlinkability. There, you need to use zero knowledge in some way, either at the point of issuance (the issuer uses a blind signature, with the client proving that the input is correct) or at the point of redemption (the client proves that they have a signature over the indicated properties). The latter being the typical arrangement.

However, despite the tools providing good properties, when composed into a complete system things can get worse.

That is because all of this assumes of course that the attributes that are disclosed do not in themselves enable linkability. Selectively disclosing a globally unique identifier is probably not going to work well. But even non-unique attributes can be correlated with other attributes to form a fingerprint that might be sufficient for linking a person across sites.

A particularly concerning aspect of the current design is that the verifier is able to select issuers. Thus, even a zero-knowledge proof will either point to a single issuer or the set that the site chooses (this will depend on what we do). That could lead to interesting potential attacks.

Let's say that a site wants to know whether someone has a credential from a particular issuer. They can ask for just that issuer and see if they get a credential. That's one more bit of information.

More interesting is querying which issuer from a set of issuers has credentials. Firstly, a site might ask for a credential from the entire set to see if there is any credential at all. Then, if there is a credential, they fake a failure of some sort and ask again, but this time with only half of the set of issuers. That will tell them which half has the credential, from which they can iterate until they know which issuer had a credential.

That is an $O(\log{N})$ attack for $O(\log{N})$ bits of information if there is just one issuer with credentials. If there are more credentials available, there is more work, but also more information to gain. This is very effective if the browser automatically supplies a credential if a site asks a second time and there is just one credential present, and fails quickly otherwise. It probably tests user patience in other cases, as lots of prompts might be annoying.

All of which is to say that the parameters here need to be calibrated to avoid creating an exploitable information leak.

[npdoty]

I'm not as confident as you are that, at least in practice, verifier-verifier unlinkability will be trivially achieved. Basic verifier-verifier unlinkability should be considered a pre-requisite for selective disclosure, but I'm not sure that's how existing deployments work today, given the use of device/authentication keys and revocation status lists.

While it's hard to provide strong guarantees about verifier-issuer unlinkability as well, or even for verifier-verifier unlinkability when selectively disclosing several properties from a credential, it does still seem possible for a user to distinguish between inherently unlinkable information (like a unique ID number) and less linkable information (over-18-ness, or having a degree from a college).

Implementers thus far have suggested that any selected credentials, even with selective disclosure, would also reveal the public key of which issuer signed the credential. So while the concern about some information revelation from which issuer in a set of issuers might have signed a credential is meaningful, I think a larger and more immediate concern is that credentials would just reveal many bits of information (and potentially data disclosure of other sensitive characteristic of the user's affiliations) from the issuer's signature. We should probably have a separate issue tracking what's necessary to hide the issuer in a group of issuers.

[martinthomson]

Oh, I have no illusions here. The gap between theory and reality is often the point where things fall through.

I am concerned that issuer identity will be abused if it is not eliminated from selective disclosure examples, so I have opened #139.

[Sakurann]

trying to understand the real issue here. is there anything specific to unlinkability when browser is involved in the interaction between RP-Wallet? Everything being said on RP-RP unlinkability and issuer-RP unlinkability is true even without digital credentials browser API. Meaning RP-RP unlinkability is achievable with batch issuance of credentials that use selective disclosure mechanism that does not simultaneously provide unlinkability. issuer-RP unlinkability would require some kind of zero knowledge scheme). I believe this has been relatively well-documented by protocols/credential formats intended to be used with this browser API.

meaningful selective disclosure depends on unlinkable presentation

selective disclosure and unlinkability are different properties. selective disclosure can be achieved without unlinkability, but not selective disclosure mechanisms also provide unlinkability property at the same time, but often can be combined with unlinkability mechanisms to achieve both properties at the same time.

[ad-Orange]

@Sakurann
SD without unlinkability doesn’t make any sense in general.

There might be exceptions in specific cases but if you are in a general situation where there is no unlinkability, selective disclosure doesn’t make any sense as the full profile could be rebuilt from linking multiple presentations together.

[Sakurann]

@ad-Orange my question is still unanswered: "is there anything specific to unlinkability when browser is involved in the interaction between RP-Wallet? " selective disclosure/unlinkability is a discussion at the credential format layer, and probably not the digital credentials API level (a little bit at the presentation protocol layer, since the query language needs to support that credential format, selective disclosure, etc.)