4 ms·

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

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?

stebalien 2y ago
See section 5.5 of the linked paper https://petsymposium.org/popets/2018/popets-2018-0026.php 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).
- echoangle 2y ago
  Thanks for looking it up, that makes sense.
- abound 2y ago
  [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'
  - echoangle 2y ago
    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?
    - abound 2y ago
      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.
      - echoangle 2y ago
        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!
        abound 2y ago
        > 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 :)
      - Timshel 2y ago
        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 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.
jerf 2y ago
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/ https://privacypass.github.io/protocol/ I think that's the best conceptual overview of a crypto protocol I've ever seen.
- dan353hehe 2y ago
  That is an excellent explanation of how the protocol works. Thank you for bringing it to the discussion!
- kayson 2y ago
  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
wasabi991011 2y ago
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.
- echoangle 2y ago
  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.
  - faeranne 2y ago
    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.

stebalien 2y ago

See section 5.5 of the linked paper https://petsymposium.org/popets/2018/popets-2018-0026.php 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).

echoangle 2y ago
Thanks for looking it up, that makes sense.
abound 2y ago
[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'
- echoangle 2y ago
  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?
  - abound 2y ago
    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.
    - echoangle 2y ago
      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!
      - abound 2y ago
        > 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 :)
    - Timshel 2y ago
      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 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.

jerf 2y ago

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/ https://privacypass.github.io/protocol/ I think that's the best conceptual overview of a crypto protocol I've ever seen.

dan353hehe 2y ago
That is an excellent explanation of how the protocol works. Thank you for bringing it to the discussion!
kayson 2y ago
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

wasabi991011 2y ago

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.

echoangle 2y ago
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.
- faeranne 2y ago
  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.