[aspensmonster]

Seeing as I'm not getting any traction in the fediverse (https://tenforward.social/@aspensmonster/113999217587309328), maybe I can ask here instead.

=================================

From their blog:

>As standardized in [2 - 4], the Privacy Pass protocol is able to accommodate many “architectures.” Our deployment model follows the original architecture presented by Davidson et al. [1], called “Shared Origin, Attester, Issuer” in § 4 of [2].

From [2] RFC 9576 § 3.3 "Privacy Goals and Threat Model" :

>Clients explicitly trust Attesters to perform attestation correctly and in a way that does not violate their privacy. In particular, this means that Attesters that may be privy to private information about Clients are trusted to not disclose this information to non-colluding parties. Colluding parties are assumed to have access to the same information; see Section 4 for more about different deployment models and non-collusion assumptions. However, Clients assume that Issuers and Origins are malicious.

And From [2] RFC 9576 § 4.1 "Shared Origin, Attester, Issuer" :

>As a result, attestation mechanisms that can uniquely identify a Client, e.g., requiring that Clients authenticate with some type of application-layer account, are not appropriate, as they could lead to unlinkability violations.

Womp womp :(

This is not genuinely private in any meaningful sense of the term. Kagi plays the role of all three parties, and even relies on the very thing section 4.1 says is not appropriate: to use mechanisms that can uniquely identify a client. They utilize a client's session token: "In the case of Kagi’s users, this can be done by presenting their Kagi session cookie to the server."

Frankly, that blog post is disingenuous at best, and malicious at worst.

=================================

I want to be wrong here. Where am I wrong? What am I missing?

[jorams]

From [2] RFC 9576 § 4.1 "Shared Origin, Attester, Issuer", right before the sentence you quoted:

> In this model, the Attester, Issuer, and Origin share the attestation, issuance, and redemption contexts.

I haven't read the RFC in detail, but I believe this is where the nuance is: When you enable the privacy pass setting in the extension/browser the redemption context is changed relative to the attestation context by removing the session cookie, to just the information sent by the browser for someone who is not logged in. What remains is your IP address and browser fingerprinting, which can be countered by using Tor.

[nulld3v]

This would definitely seem like a big concern if you were just looking at the RFC, but the key here is that Kagi's system has a different set of security/privacy/functional requirements and therefore the issues mentioned in the RFC do not necessarily apply.

In the RFC's architecture, the request flow is like so:

1. CLIENT sends anonymous request to ORIGIN

2. ORIGIN sends token challenge to CLIENT

3. CLIENT uses its identity to request token from ISSUER/ATTESTER

4. ISSUER/ATTESTER issues token to CLIENT

5. CLIENT sends token to ORIGIN

You can see how the ISSUER/ATTESTER can identify the client as the source of the "anonymous request" to the ORIGIN because the ISSUER, ATTESTER and ORIGIN are the same entity, so it can use a timing attack to correlate the request to the ORIGIN (1.) with the request to the ISSUER/ATTESTER (3.).

However you can also see that if a lot of time passes between steps (1.) and (3.), then such an attack would be infeasible. Reading past your quote from RFC 9576 § 4.1., it states:

> Origin-Client, Issuer-Client, and Attester-Origin unlinkability requires that issuance and redemption events be separated over time, such as through the use of tokens that correspond to token challenges with an empty redemption context (see Section 3.4), or that they be separated over space, such as through the use of an anonymizing service when connecting to the Origin.

In Kagi's architecture, the "time separation" requirement is met by making the client generate a large batch of tokens up front, which are then slowly redeemed over a period of 2 months. The "space separation" requirement is also satisfied with the introduction of the Tor service.

There is some more discussion in RFC 9576 § 7.1. "Token Caching" and RFC 9577 § 5.5. "Timing Correlation Attacks".

One question you may have is: Why wasn't this solution used in the RFC?

This can be understood if you look at the mentions of "cross-ORIGIN" in the RFC. This RFC was written by Cloudflare, who envisioned it's use across the whole Internet. Different ORIGINs would trust different ISSUERs, tokens from one ORIGIN<->ISSUER network might not work in another ORIGIN<->ISSUER network. This made it infeasible for clients to mass-generate tokens in advance, as a client would need to generate tokens across many different ISSUERS.

Of course, adoption was weak and there ended up being only one ISSUER - Cloudflare, so they adopted the same architecture as Kagi where clients would batch generate tokens in advance (batch size was only 30 tokens though).

RFC 9576 § 7.1. also mentions a "token hoarding" attack, which Cloudflare felt particularly threatened by. Cloudflare's Privacy Pass system worked in concert with CAPTCHAs. Users could trade a completed CAPTCHA for a small batch of tokens, allowing a single CAPTCHA completion to be split into multiple redemptions across a longer time period.

However, rudimentary "hoarding"-like attacks were already in use against CAPTCHAs through "traffic exchanges". Opening up another avenue for hoarding through Privacy Pass would have only exacerbated the problem.

[aspensmonster]

>3. CLIENT uses it's identity to request token from ISSUER/ATTESTER

The ISSUER and ATTESTER are different roles. As previously quoted, "Clients explicitly trust Attesters to perform attestation correctly and in a way that does not violate their privacy." The RFC is explicit that, when all of the roles are held by the same entity, the attestation should not rely on unique identifiers. But that's exactly what a session cookie is.

>You can see how the ISSUER/ATTESTER can identify the client as the source of the "anonymous request" to the ORIGIN because the ISSUER, ATTESTER and ORIGIN are the same entity, and therefore it can use a timing attack to correlate the request to the ORIGIN (1.) with the request to the ISSUER/ATTESTER (3.).

No timing or spacing attack is needed here. If I have to provide Kagi with a valid session cookie in order to get the tokens, then they already have a unique identifier for me. There is no guarantee that Kagi is not keeping a 1-to-1 mapping of session cookies to ISSUER keypairs, or that Kagi could not, if compelled, establish distinct ISSUER keypairs for specific session cookies.