Hacker News Reader

Comment by echoangle | Hacker News Reader

I don’t really understand how the protocol can ensure that the server can’t identify the client.

As far as I understand, the client sends some information A to the server, the server applies some private key X and returns the output B to the client, which then generates tokens C from the output.

If the server uses a different X for every user and then when verifying just checks the X of every user to see which one is valid, couldn’t the server know who created the token?

View on HN

Here's a resource I found that walks through the ideas of the protocol, starting with simple implementations that have a problem, and then solving the problem one by one: https://privacypass.github.io/protocol/

I think that's the best conceptual overview of a crypto protocol I've ever seen.

That is an excellent explanation of how the protocol works. Thank you for bringing it to the discussion!

I really love this style of explanation. There was another one I saw recently (OIDC, I think?) that I wish I'd bookmarked but I forgot to

See section 5.5 of the linked paper https://petsymposium.org/popets/2018/popets-2018-0026.php. I'm not sure if/how Kagi implemented this, but the idea is that Kagi's "public" component can be committed to publicly (e.g., in the browser extension itself).

Thanks for looking it up, that makes sense.

[I implemented this at Kagi]

And you can validate this, if you try to issue a Privacy Pass search without a private token, you'll get a `WWW-Authenticate` header that kicks off the handshake, and that should be the same for all users for a given epoch (month). E.g.

    curl -v -H 'X-Kagi-PrivacyPass-Client: true' 'https://kagi.com/search?q=test'

But how do I validate that I’m actually getting the same value as everyone else? Is the value I should get published somewhere (in a verifiable and not editable way) so I can see that I’m not being tracked?

Or does the extension validate this and the correct value is hardcoded in the extension like stebalien suggested?

There's no auth required at this stage of the handshake, so you can test from any number of devices/locations/networks/etc and confirm you get the same value. We could publish it, but it will change every epoch/month. Plus, if you don't trust the service to not issue special key pairs to track you, you probably won't trust us to not do the same when publishing the key material. There are schemes involving third-parties we could employ, but it's trust and turtles all the way down.

A malicious server could maintain separate key pairs for users it wanted to track, but you can't do it for every user because 1) it'd be clear from the WWW-Authenticate header changing, and 2) you'd have to validate tokens against every key, which would quickly get too slow to work.

Makes sense in general, but to make sure I understand it:

> Plus, if you don't trust the service to not issue special key pairs to track you, you probably won't trust us to not do the same publishing the key material.

You could publish it on some sort of blockchain to make sure it can’t be changed and is public for everyone, right?

> A malicious server could maintain separate key pairs for users it wanted to track, but you can't do it for every user because 1) it'd be clear from the WWW-Authenticate header changing, and 2) you'd have to validate tokens against every key, which would quickly get too slow to work.

Makes sense, thanks for explaining!

> You could publish it on some sort of blockchain to make sure it can’t be changed and is public for everyone, right?

Your understanding is correct, that's definitely something we could do. It is also something anyone else could do to keep us honest :)

While it's relatively trivial to run something like:

  fetch(new Request("https://kagi.com/search?q=test", { method: "GET", headers: new Headers({ "X-Kagi-PrivacyPass-Client": true })})).then((r) => console.log(r.headers.get("www-authenticate")))

A simple response in the body to something like <https://kagi.com/privacypass> would be easier to check.

And you answered someone else:

> It is also something anyone else could do to keep us honest :)

While true I believe for such a feature making it as easy as possible for your users to check independently is just better.

Could you jam the bits into dummy ssl cert signing requests, then stick the result in the certificate transparency log?

In the simplest terms, the token generation process B->C is done with the user's private key. So even if the server knows A,X,B they can't link it to the token C.

But if the server is allowed to vary X, it can basically act like different servers to each client, and can then when given a token check for which server would have been valid. The solution I got from the other replies is to make sure that the server uses the same X for everyone by verifying it as a client.

It appears that the public side of X is sent as the first part of the handshake, without any login info yet, and can be verified as part of B, thus a varying X would be easy to detect... I think.

Reply on news.ycombinator.com