Malicious Issuer with a colluding Origin breaks unlinkability Attesters

[chris-wood]

TL;DR: An attacker can re-use the same OPRF key (Issuer Origin Secret, denoted sk_origin in pseudocode) for each origin to track clients across origins if the attester doesn't implement a security-critical check.

Simplified example

Imagine there are two users, X and Y, each with public key g^x and g^y, respectively. and two origins, O1 and O2. Imagine further that the attacker controlling O1 and O2 colludes with the Issuer and wants to track when a user visits both O1 and O2. Finally, imagine the rate limit to each origin is 1.

Unlinkability asserts that an attacker cannot distinguish between the following scenarios:

1. X visiting O1 and then Y visiting O2
2. X visiting O1 and then X visiting O2

Recall that the anonymous issuer origin ID is computed roughly as Hash(g^x, g^xk), where g^x is a client public key and g^xk is the result of the client's public key evaluated by the issuer OPRF key.

If a malicious issuer uses the same OPRF key k across O1 and O2, then the these two scenarios end up computing the following:

1. Hash(g^x, g^xk), Hash(g^y, g^yk)
2. Hash(g^x, g^xk), Hash(g^x, g^xk)

If the rate limit is 1, then X's second visit in (2) will fail, which is the distinguishing event.

Root of the problem

The root of the problem is that the Issuer's input to the OPRF is unverified. Addressing this either requires we relax the threat model and assume the Issuer is honest-but-curious, which seems like a subpar outcome, or try to fix the protocol. Unfortunately, with the current design, fixing this issue is challenging since any sort of "public verifiability" might open up dictionary attacks by the Attester, which the protocol aims to prevent.

There are likely a couple ways this could be addressed, each with different complexity:

1. Make the Client "stateful," so it can check whether or not the same anonymous issuer origin ID is computed across origins, and fail if this ever occurs. This may be problematic in practice due to the number of distinct origins and keys the client needs to remember.
2. Move the anonymous issuer origin ID computation to the client without any involvement from either Attester or Issuer, using a combination of standard zero-knowledge proofs. This has the benefit of simplifying both Attester and Issuer, and also allowing the Attester to enforce rate limits before querying the Issuer.

We're currently investigating (2) and will report back when we have a better handle on the resulting security analysis and implementation status.

[tfpauly]

For clarity, the OPRF in this case refers to the "Issuer Origin Secret" in the document.

In general, the Attester can enforce what rate limits it allows Issuers to have, since it is the one actually applying various limits. We've discussed having attesters disallow limits of 1 for various reasons. Of course, this same pattern could exist at higher limits, but it becomes more speculative.

I'm also curious how this interacts with the Attester's checks, specifically:

If the "Sec-Token-Origin" is missing, or if the same Anonymous Issuer Origin ID was previously received in a response for a different Anonymous Origin ID within the same policy window, the Attester MUST drop the token and respond to the client with an HTTP 400 status.

The point of that check is to detect a collision between two different origins, where the client says there are two origins, but the issuer says there is only one. Without the details of the attack here, how can the issuer cause a rate limit to be incorrectly applied by the attester without falling afoul of this check?

[dvorak42]

Even with moderate rate limits I think this is still a pretty substantial problem, you'd need something like minimum rate limits of 10+ to mitigate the basic version of this attack (and it seems colluding origin can just always redeem N/2+1 tokens at a time against a total rate limit of N to devolve the issue to the same as the rate limit of 1 case?).

The stateful version might be okay as a stopgap or for certain ecosystems, but I'm not sure it is particularly feasible at web/browser-scale and there's also potential edge cases where if the client fails to complete the privacypass redemption on an origin, it can learn with some probability that the client likely saw a previous origin with the same anon issuer origin ID and learn approximately the same information.

I'm curious about the new design for the client-provided ID, seems like you still need some origin/issuer input to bind the client's anon origin ID to prevent it from pretending the same origin has many different identities, but maybe there's something clever with some known component of the origin and ZKPs you can do?

[tfpauly]

One more question on the proverif model — what was it thinking the Issuer Origin Secret and Anonymous Issuer Origin ID were used for at all? The only thing that should be used for is this enforcement check. The secret leads to the index_key, and then the attester validates the index_key and generates the anon_issuer_origin_id. And that Anonymous Issuer Origin ID value is only used by the attester for enforce the 1:1 check.

To that end, if there is a reused Issuer Origin Secret, I don't see how it could lead to the attack you describe without the client also aligning its origin IDs and lying in the exact same way. The actual buckets for rate limits are not determining by the Anonymous Issue Origin ID, but only the client-supplied Anonymous Origin ID:

For each tuple of (Client Key, Anonymous Origin ID, policy window), the Attester maintains the following state:¶

A counter of successful tokens issued¶
Whether or not a previous request was rejected by the Issuer¶
The previous rate limit provided by the Issuer¶
The last received Anonymous Issuer Origin ID value for this Anonymous Origin ID, if any¶

[chris-wood]

The model currently uses the Anonymous Issuer Origin ID as the index for book keeping, not the Anonymous Origin ID. I think using the latter would prevent the issue, too, which is a good observation!

[nikitaborisov]

It's not clear to me that using the Anonymous Origin ID entirely solves the problem. In @chris-wood's example, with a rate limit of 1, we would want the two situations to be indistinguishable. But with the malicious issuer, the first situation succeeds at getting a token for both accesses, whereas the second situation fails. Without the anonymous origin check, it will fail because of the rate limit; with the check, it will fail because the origins do not match, but either way it will fail and that is observable.

Maybe you can use this check to detect a misbehaving issuer? You can't immediately assume that the issuer is compromised if the anonymous origin id check fails, because the client could simply use the same origin ID for two different origins. But perhaps in that case you could ask the origin to provide a verifiable decryption of the HPKE messages from the client to show that the client is misbehaving.

[nikitaborisov]

Incidentally, I find the phrase Anonymous Issuer Origin ID confusing; first because it's a complicated word easily confused with Anonymous Origin ID, and second because I think of a stable mapping as a pseudonym, whereas anonymity to me suggests full unlinkability.

[chris-wood]

Without the anonymous origin check, it will fail because of the rate limit; with the check, it will fail because the origins do not match, but either way it will fail and that is observable.

@nikitaborisov I don't think this is true. Notice in the example that the rate limits aren't actually exceeded. In (1), X and Y make two separate visits, whereas in (2) X makes two visits to two distinct origins. The limit is never exceeded by X or Y.

[nikitaborisov]

Let me try to clarify:

• Honest issuer: (1) and (2) both succeed at issuing tokens
• Malicious issuer, no anonymous origin ID check: (1) succeeds because the anonymous issuer ID is different across two visits (b/c X and Y have different public keys), (2) fails because the anonymous issuer ID is the same across both visits and the rate limit is hit
• Malicious issuer, with anonymous origin ID check: (1) succeeds because the check is never applied on the first visit by a client, (2) fails because the anonymous issuer ID is the same and the collision is detected by the attester.

[chris-wood]

Right, but we have to assume that exceeding the rate limit is a distinguishing event, i.e., there's nothing that can be done about that, regardless of how the issuance protocol works. So the interesting case here seems to be how a distinguishing event can arise in the absence of rate limit exceeded events.

[tfpauly]

@nikitaborisov the attester as described in the protocol uses does not use the anonymous issuer origin ID for anything other than the check. Thus, the entire premise of a malicious issuer can only interfere with this check, because the rate limit buckets that are enforced by the attester are based on the anonymous origin ID presented by the Client. The issue in this issue was that the model was thinking the attester bases its bucket on the issuer-provided values.

As such, the "malicious issuer" really ends up causing the attester to fail some requests as invalid — which doesn't even get to the rate limiting logic yet.

[chris-wood]

What's problematic here is that the spec is not clear on what the right bucket value should be -- the editors aren't even in agreement! The spec says this:

The Anonymous Issuer Origin ID is used to track and enforce the Client rate limit

It also says this:

For each tuple of (Client Key, Anonymous Origin ID, policy window), the Attester maintains the following state:

We were operating under a different understanding of the protocol. Nevertheless, we need to make clear what is used for what purpose, and we should use this opportunity to seriously consider if there aren't simpler and less fragile variants of this protocol.

[tfpauly]

Yes, I agree this is something that needs to be made more clear in the spec. Also if there are ways to simplify that uphold the same properties, that's good.

[tfpauly]

@chris-wood to fix up the document now: https://github.com/ietf-wg-privacypass/draft-ietf-privacypass-rate-limit-tokens/pull/7

Apologies for not catching this in the original review of https://github.com/tfpauly/privacy-proxy/pull/216. That's my bad.

[chris-wood]

Coming back to @nikitaborisov's comment (I'm getting myself really confused here)...

It is true that in the two cases he described -- one with the check and one without -- there is a distinguishing event because one visit will succeed and one will fail. In one case, the failure is caused by exceeding the rate limit, and in the other case the failure is caused by the attester enforcing the check. Thus, as @nikitaborisov I think was trying to point out, the event exists with or without the check in place.

[nikitaborisov]

Thanks @tfpauly for the clarification! So if I understand: the client's ID is used as the index for the rate-limit state and the OPRF is used to make sure the client does not use two different indices for the same origin.

As @chris-wood stated just above, the issue remains that the malicious issuer can cause this check to fail when a single client visits two distinct sites, but not in any other cases. You can even target this attack by origin (e.g., I want to collude with foo.com and bar.com to cause an error whenever a single person tries to visit both). This seems like an undesirable linkability problem.

[tfpauly]

@nikitaborisov correct: the client's ID is used as the index for rate-limiting, and the OPRF is used to validate that the client does not use different values for one origin.

I do see your point now, that the malicious issuer can cause the validation check to fire. I think it's something that the attester in practice would easily detect if used at any kind of scale — if all of sudden, many checks started failing across many clients, that would be a strong indicator that we have a compromised or malicious issuer. But I agree that a way to avoid that need for enforcement is nice.