Subject: [Privacy-pass] support for adoption of privacy pass documents

From: Subodh Iyengar <[email-masked]>
Date: Tue, 15 Sep 2020 20:31:38 +0000

I’ve read the protocol, architecture and VOPRF documents and support adoption of these documents. I’d also like to offer feedback from operational experience. At Facebook, we have multiple applications that are using blind signatures for anonymous fraud resistant data processing. These use our own custom APIs and algorithms (e.g. https://engineering.fb.com/security/partially-blind-signatures/). We’ve successfully prototyped changing our custom APIs and algorithms to the APIs specified in the privacy pass protocol document (draft-davidson-pp-protocol-00). We also found some cases where the specification could be improved to better work with our deployments.

The use of Privacy Pass has mostly been discussed in the context of interaction between untrusted parties, however we see it as useful to have a standardized approach that can be used even in a first-party context, i.e. cases where both the client and server and controlled by the same party where the client opts into anonymous data collection, for example a mobile application for the service logging data anonymously to minimize data collection.

We also have some high-level feedback on some decisions this document has made.

#Architectural feedback

  *   The basic assumptions of “1 key at a time only” which changed from -00 to -01 adds an operational burden. As a result, servers may only have one key active at a time. However, this policy is too restrictive. For example, we have encountered cases where a service might want to experiment with different private key generation policies at the same time and don’t want break existing clients. Perhaps a different way to think about it might be to have an application specific profile with a key policy for each profile which could specify a different config id size that it tolerates. Applications can also specify how often they change their keys and parties can verify that parties conform to the policy and can discuss what a good policy is per application. We can also make the config generation verifiable as well so that tracking information cannot be used.
  *   Our deployment of blind signatures / privacy-pass is a split server model where the application “server” is different from the credential server that handles the private key material. This is done to be able to handle multiple applications. I would like to see some discussion of a split server model in the document. In our system, we minimize data-sharing between the application server and the credential server by only sharing the final MAC validation key rather than all the message data.

Protocol feedback

#Double spend protection

  *   In most use cases we've been using blind signature / Privacy Pass-based tokens, strict un-linkability between redemption requests is not required. Additionally, it is also seen as a tradeoff between reliability / anonymity. Application profiles should be allowed to specify the number of max redemptions for each token.
  *   A bloom filter is insufficient to provide double spend protection in a multi-server environment. Instead of being too prescriptive here, we could specify these as properties of a double spent prevention system, for example an api like testAndSet() and atomicity requirements of such a system. We should mention the challenges in a multi-server environment and recommendations. These problems are challenging enough that I think smaller applications using privacy pass will want to be able to use tokens more than once.

# Protocol feedback

  *   In our own uses we found that we wanted to experiment with different config id generation schemes when experimenting with different public key generation schemes, and having a configuration id parameter was very helpful in being able to experiment without breaking existing clients.
  *   An option for making proofs optional would be great, in a first-party context applications, a proof is not necessarily always required for every token issuance. A client could challenge the server randomly, and this proof validation policy could be specified by the application.
  *   The Dleq Proof is specified as opaque blob of data. Is this to accommodate different proof types? There is currently no mechanism specified to serialize the Dleq proofs specifically the schnorr style proofs in the VOPRF documents.

#Security considerations
The security considerations could use a lot of work

  *   Maximum tokens issued: Here the security considerations talk about how many tokens to issue to a client at once, however I think what is more important here is the tokens that are issued to a client over the lifetime of the server key and how we can keep that dynamic.
  *   Risks for reusing / transferring tokens: Depending on the application profile there are different risks to allowing token reuse or transferability of tokens and some of these risks could be mentioned here.
  *   Key Rotation: I would love to see this mentioned as a security mechanism. Rotating the key is the only way to invalidate the previous tokens and reset a token limit.
  *   Anonymity set reduction: This could use a discussion as well. What are the parameters that govern the size of the anonymity set and how should they be selected? For example, if a server manages multiple server configs at the same time with different key types, or rotates keys too frequently, it could reduce the anonymity sets for the user. Care should also be taken such that other metadata about the redemption request cannot be used to de-anonymize a user like IP addresses.
  *   Application profiles: I think the documents could go into more detail as to what types of applications are appropriate and what are not appropriate uses of the privacy pass architecture.

We are very interested in the standardization of privacy pass and encouraging its wider use across the industry. I would personally like to see it used in first party applications and built into platforms like Android / iOS and browsers to facilitate easier use by applications.

Subodh Iyengar

---

From: Michele Orrù <[email-masked]>
Date: Wed, 16 Sep 2020 04:55:12 +0200

Dear Subodh,

thanks a lot for your email. I have a couple of questions regarding your
high-level feedback:

- When you say «Our deployment of blind signatures / privacy-pass is a
split server model […W]e minimize data-sharing between the application
server and the credential server by only sharing the final MAC validation
key rather than all the message data. », I don't understand what's your
setup (even after your blogpost):
Are you issuing blind signatures (are they deterministic?) and then using
them as a MAC key for authentication of a particular resource?
Are you suggesting that in the Privacy Pass standard there is a «split
server model» where an oracle provides the MAC key for the «application
server» (the server running the verification algorithm)?
I'd be very interested in knowing more in detail your solution, and I
believe it would be of interest for the whole standardization process.

- Could you please motivate your sentence «In most use cases we've been
using blind signature / Privacy Pass-based tokens, strict un-linkability
between redemption requests is not required.»?
I'm not sure I understand what your scenario is. If I can track users
across all servers except the one providing issuance, what's the point? It
seems to me that it completely breaks anonymity in the Tor/Cloudflare use
case for instance, or same-origin policy in the web. What's your use-case?

- You seem to suggest that in the Privacy Pass standard, the verifiers keep
a counter for each nonce, to allow for re-use of tokens. Have you already
thought about what are the tradeoffs between using a counter-based solution
like yours (with the associated problems in my previous question) or a
multi-use token (e.g. Algebraic MACs) that are active only for a certain
window of time?

If you want to avoid sending zk proofs to the client, I'm not sure that
challenging the server randomly is the way to go (to get a soundness error
of 10% you'd have to ask for a proof 90% of the time?), and we have much
better solutions already out there
<https://slides.com/micheleorru/anonymous-tokens/#/26> (
https://link.springer.com/chapter/10.1007/978-3-030-56784-2_11).

--
Michele.

---

From: Steven Valdez <[email-masked]>
Date: Wed, 16 Sep 2020 00:08:37 -0400

I guess one mea-question to sort out is to what extent things are moved to
being application profile specified, rather than part of the core protocol
design, privacy/securiy considerations.

For supporting multiple configurations, there's a few potential layers to
separate an issuer at, at one side is having in-protocol an issuer support
multiple configurations and having clients have to negotiate which
configuration it uses (though there's some care to not let the
configuration negotiation partition the anonymity set), on the other side
is treating the different (server, configuration) pairs as completely
separate entities.

For token reuse, are you mostly imagining the trade-offs being for the
reliability of maintaining double-spend protection vs the risks with a
token being used multiple times? (In which case good acting clients would
never be reusing tokens, but the security properties are resilient to bad
acting clients reusing tokens without global double-spend protection to
stop it)? Or are you more imagining supporting good clients using the same
token multiple times (if they've run out of tokens, or something else)? The
latter case introduces direct links between token redemptions, and if its
just for the sake of not running out of tokens, I wonder if some scheme to
get more tokens when you're about to run out would work better.

Agreed that we probably want to support cases where double-spend protection
isn't needed from the server's perspective, and letting certain
applications drop the requirement seems reasonable.

I think there are tradeoffs between dropping the ZKP and having to
introduce probabilistic verification of proofs, though if there's a decent
approach, looking at integrating other underlying schemes seems reasonable
and figuring out what sorts of guarantees we can get out of those schemes +
random verification would be interesting. @Michele The non-ZKP variant in
that paper still requires the client to challenge the server randomly if it
wants to prevent bad acting issuers from using 'invalid tokens' to create a
new anonymity set (users in the no token bucket vs invalid token bucket
(which can be forged, but good users are unlikely to forge them) vs valid
token bucket).

I also wonder if there's some better structure for the privacy/security
considerations since a lot of them are actually in conflict or overlap with
each other and it would be nice to more clearly layout both sides (key
rotation means better security, but splits anonymity sets and lowers
privacy, reuse is both a security and privacy issue, transferability is
required for the underlying privacy pass considerations, but has a bunch of
security problems, etc).

I'm not sure if we should be describing what is appropriate/not appropriate
for application profiles built on PrivacyPass, versus describing what
properties PrivacyPass takes as fundamental to the protocol
development/model (and that the security/privacy considerations/data in the
docs is built on top of).

On Tue, Sep 15, 2020 at 10:55 PM Michele Orrù <[email-masked]> wrote:

> - You seem to suggest that in the Privacy Pass standard, the verifiers
> keep a counter for each nonce, to allow for re-use of tokens. Have you
> already thought about what are the tradeoffs between using a counter-based
> solution like yours (with the associated problems in my previous question)
> or a multi-use token (e.g. Algebraic MACs) that are active only for a
> certain window of time?
>
> Privacy-pass mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/privacy-pass
>

-- 

Steven Valdez |  Chrome Privacy Sandbox |  [email-masked] |
 210-692-4742

---

From: Subodh Iyengar <[email-masked]>
Date: Thu, 17 Sep 2020 01:43:07 +0000

Ooh that's a lot of questions 🙂. I'll try to do them justice while keeping responses brief.
I'm happy to talk about the general patterns of use but hopefully over the next few months I can reveal more specifics of the applications.

> Our deployment of blind signatures / privacy-pass is a split server model

We have 2 entities that participate in token issuance / redemption. One is the application server. This is the front-end that the mobile app talks to over HTTP / other protocols over the internet. The front-end then forwards token requests to a backend service which manages the private keys for the tokens which is accessible only internally. The backend server is multi-tenant in that it manages keys for issuances from different application servers and is access controlled etc..

Privacy pass currently requires the message to be authenticated while redeeming the token. The message is normally accessible to the front-end application server. It doesn't need to be accessible to the backend server. To do this the front-end server forwards the token only (without the message), to the backend. The backend validates the token, checks number of uses of the token, and then computes the MAC key and returns it to the application server. The application server then uses the MAC key to validate the message.

> In most use cases we've been using blind signature / Privacy Pass-based tokens, strict un-linkability between redemption requests is not required

In general terms, one of our applications takes some existing logging (like performance data etc.) from mobile apps that is currently logged with user identifiers and makes it be possible to log it without user identifiers and anonymously. This allows aggregate metrics to be computed without needing user specific identifiers while preventing non-users from polluting these metrics. In addition to other mechanisms, blinded tokens are used to make sure that the data is coming from legitimate users. However, for analytics, we also want to compute statistics like unique user count etc. To be able to do this we have another rotating identifier which is logged with the blinded token during redemption. Thus, there is some implicit linkability in the data we're logging. Thus, we can use a token for some time, but not forever, to be able to prevent infinite uses of it. Another use is in fetching data anonymously. While I understand these is a very high-level description of the problem, and not enough detail, we'll hopefully be revealing more details over the next few months.

> You seem to suggest that in the Privacy Pass standard, the verifiers keep a counter for each nonce, to allow for re-use of tokens. Have you already thought about what are the tradeoffs between using a counter-based solution like yours (with the associated problems in my previous question) or a multi-use token (e.g. Algebraic MACs) that are active only for a certain window of time?

Not entirely certain about the specific tradeoffs you're asking about here. Our tokens are valid only for a certain period, and we invalid the tokens by rotating the key. Does that answer that question?

> For token reuse, are you mostly imagining the trade-offs being for the reliability of maintaining double-spend protection vs the risks with a token being used multiple times?  Or are you more imagining supporting good clients using the same token multiple times?

I'm imagining a good client might use the same token multiple times if there was no castatrophic outcome to the application by doing that. For example, CF would not reuse their token, however we might.

> I also wonder if there's some better structure for the privacy/security considerations since a lot of them are actually in conflict or overlap with each other and it would be nice to more clearly layout both sides (key rotation means better security, but splits anonymity sets and lowers privacy, reuse is both a security and privacy issue, transferability is required for the underlying privacy pass considerations, but has a bunch of security problems, etc).

Some sort of NxN matrix representation might help, of how one property affects other properties.

> I'm not sure if we should be describing what is appropriate/not appropriate for application profiles built on PrivacyPass, versus describing what properties PrivacyPass takes as fundamental to the protocol development/model

I think it's fine if privacy pass says that we will only function in a mode that is completely unlinkable and that configs can only be used once. However, that would impact the applicability of the protocol. Is that what you mean?  I've found that most of the questions when applying this to an existing system is whether the reliability of the system is affected, and being able to provide a path of migration where you can start in a mode where you go from non-anonymous -> less-linkable (token reuse) -> non-linkable helps move the conversation along. Hopefully, we'll have data soon on the number of times tokens are reused on average.

Subodh

________________________________
From: Steven Valdez <svaldez=[email-masked]>
Sent: Tuesday, September 15, 2020 9:08 PM
To: Michele Orrù <[email-masked]>
Cc: Subodh Iyengar <[email-masked]>; [email-masked] <[email-masked]>
Subject: Re: [Privacy-pass] support for adoption of privacy pass documents

I guess one mea-question to sort out is to what extent things are moved to being application profile specified, rather than part of the core protocol design, privacy/securiy considerations.

For supporting multiple configurations, there's a few potential layers to separate an issuer at, at one side is having in-protocol an issuer support multiple configurations and having clients have to negotiate which configuration it uses (though there's some care to not let the configuration negotiation partition the anonymity set), on the other side is treating the different (server, configuration) pairs as completely separate entities.

For token reuse, are you mostly imagining the trade-offs being for the reliability of maintaining double-spend protection vs the risks with a token being used multiple times? (In which case good acting clients would never be reusing tokens, but the security properties are resilient to bad acting clients reusing tokens without global double-spend protection to stop it)? Or are you more imagining supporting good clients using the same token multiple times (if they've run out of tokens, or something else)? The latter case introduces direct links between token redemptions, and if its just for the sake of not running out of tokens, I wonder if some scheme to get more tokens when you're about to run out would work better.

Agreed that we probably want to support cases where double-spend protection isn't needed from the server's perspective, and letting certain applications drop the requirement seems reasonable.

I think there are tradeoffs between dropping the ZKP and having to introduce probabilistic verification of proofs, though if there's a decent approach, looking at integrating other underlying schemes seems reasonable and figuring out what sorts of guarantees we can get out of those schemes + random verification would be interesting. @Michele The non-ZKP variant in that paper still requires the client to challenge the server randomly if it wants to prevent bad acting issuers from using 'invalid tokens' to create a new anonymity set (users in the no token bucket vs invalid token bucket (which can be forged, but good users are unlikely to forge them) vs valid token bucket).

I also wonder if there's some better structure for the privacy/security considerations since a lot of them are actually in conflict or overlap with each other and it would be nice to more clearly layout both sides (key rotation means better security, but splits anonymity sets and lowers privacy, reuse is both a security and privacy issue, transferability is required for the underlying privacy pass considerations, but has a bunch of security problems, etc).

I'm not sure if we should be describing what is appropriate/not appropriate for application profiles built on PrivacyPass, versus describing what properties PrivacyPass takes as fundamental to the protocol development/model (and that the security/privacy considerations/data in the docs is built on top of).

On Tue, Sep 15, 2020 at 10:55 PM Michele Orrù <[email-masked]<mailto:[email-masked]>> wrote:
Dear Subodh,

thanks a lot for your email. I have a couple of questions regarding your high-level feedback:

- When you say «Our deployment of blind signatures / privacy-pass is a split server model […W]e minimize data-sharing between the application server and the credential server by only sharing the final MAC validation key rather than all the message data. », I don't understand what's your setup (even after your blogpost):
Are you issuing blind signatures (are they deterministic?) and then using them as a MAC key for authentication of a particular resource?
Are you suggesting that in the Privacy Pass standard there is a «split server model» where an oracle provides the MAC key for the «application server» (the server running the verification algorithm)?
I'd be very interested in knowing more in detail your solution, and I believe it would be of interest for the whole standardization process.

- Could you please motivate your sentence «In most use cases we've been using blind signature / Privacy Pass-based tokens, strict un-linkability between redemption requests is not required.»?
I'm not sure I understand what your scenario is. If I can track users across all servers except the one providing issuance, what's the point? It seems to me that it completely breaks anonymity in the Tor/Cloudflare use case for instance, or same-origin policy in the web. What's your use-case?

- You seem to suggest that in the Privacy Pass standard, the verifiers keep a counter for each nonce, to allow for re-use of tokens. Have you already thought about what are the tradeoffs between using a counter-based solution like yours (with the associated problems in my previous question) or a multi-use token (e.g. Algebraic MACs) that are active only for a certain window of time?

If you want to avoid sending zk proofs to the client, I'm not sure that challenging the server randomly is the way to go (to get a soundness error of 10% you'd have to ask for a proof 90% of the time?), and we have much better solutions already out there<https://slides.com/micheleorru/anonymous-tokens/#/26> (https://link.springer.com/chapter/10.1007/978-3-030-56784-2_11<https://link.springer.com/chapter/10.1007/978-3-030-56784-2_11>).

--
Michele.
--
Privacy-pass mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/privacy-pass<https://www.ietf.org/mailman/listinfo/privacy-pass>

--

Steven Valdez |  Chrome Privacy Sandbox |        [email-masked]<mailto:[email-masked]> |         210-692-4742

---

From: Steven Valdez <[email-masked]>
Date: Thu, 17 Sep 2020 10:14:01 -0400

On Wed, Sep 16, 2020 at 9:43 PM Subodh Iyengar <subodh=
[email-masked]> wrote:

> I'm happy to talk about the general patterns of use but hopefully over the
> next few months I can reveal more specifics of the applications.
>
> We have 2 entities that participate in token issuance / redemption. One is
> the application server. This is the front-end that the mobile app talks to
> over HTTP / other protocols over the internet. The front-end then forwards
> token requests to a backend service which manages the private keys for the
> tokens which is accessible only internally. The backend server is
> multi-tenant in that it manages keys for issuances from different
> application servers and is access controlled etc..
>
> Privacy pass currently requires the message to be authenticated while
> redeeming the token. The message is normally accessible to the front-end
> application server. It doesn't need to be accessible to the backend server.
> To do this the front-end server forwards the token only (without the
> message), to the backend. The backend validates the token, checks number of
> uses of the token, and then computes the MAC key and returns it to the
> application server. The application server then uses the MAC key to
> validate the message.
>

Ah, I wonder if one generic solution to this is to have info as passed into
Redeem/Verify be some sort of hash of the message, so that the application
server can pass the raw RedemptionRequest along to the back-end server, and
then itself verify the message against the hash to validate the message?

> In most use cases we've been using blind signature / Privacy Pass-based
> tokens, strict un-linkability between redemption requests is not required
>
> In general terms, one of our applications takes some existing logging
> (like performance data etc.) from mobile apps that is currently logged with
> user identifiers and makes it be possible to log it without user
> identifiers and anonymously. This allows aggregate metrics to be computed
> without needing user specific identifiers while preventing non-users from
> polluting these metrics. In addition to other mechanisms, blinded tokens
> are used to make sure that the data is coming from legitimate users. However,
> for analytics, we also want to compute statistics like unique user count
> etc. To be able to do this we have another rotating identifier which is
> logged with the blinded token during redemption. Thus, there is some
> implicit linkability in the data we're logging. Thus, we can use a token
> for some time, but not forever, to be able to prevent infinite uses of it.
> Another use is in fetching data anonymously. While I understand these is a
> very high-level description of the problem, and not enough detail, we'll
> hopefully be revealing more details over the next few months.
>
> > You seem to suggest that in the Privacy Pass standard, the verifiers
> Not entirely certain about the specific tradeoffs you're asking about
> here. Our tokens are valid only for a certain period, and we invalid the
> tokens by rotating the key. Does that answer that question?
>
> token being used multiple times?  Or are you more imagining supporting
> good clients using the same token multiple times?
>
> I'm imagining a good client might use the same token multiple times if
> there was no castatrophic outcome to the application by doing that. For
> example, CF would not reuse their token, however we might.
>

Ah okay, in that system I can see why reusing tokens is reasonable, not
sure what the right way to support token reuse is though, assuming
single-use tokens does simplify the protocol and security/privacy
considerations, though maybe we can make it a application profile specified
thing that defaults to 1 and we have a section about what will need to be
considered if an application profile sets it to a different number (both
architecturally and security/privacy-wise).

> > I'm not sure if we should be describing what is appropriate/not
> appropriate for application profiles built on PrivacyPass, versus
> describing what properties PrivacyPass takes as fundamental to the protocol
> development/model
>
> I think it's fine if privacy pass says that we will only function in a
> mode that is completely unlinkable and that configs can only be used once.
> However, that would impact the applicability of the protocol. Is that
> what you mean?  I've found that most of the questions when applying this
> to an existing system is whether the reliability of the system is affected,
> and being able to provide a path of migration where you can start in a mode
> where you go from non-anonymous -> less-linkable (token reuse) ->
> non-linkable helps move the conversation along. Hopefully, we'll have data
> soon on the number of times tokens are reused on average.
>

Was a reply to your last point under security considerations, not about any
of the proposed changes in the email. More that I think the docs should be
talking about the range of properties/modes (what it takes as a non-mutable
property, what is left unspecified and left to the profile, what is assumed
by default in PrivacyPass but can be overwritten by application profiles),
rather than talking about whether specific applications are appropriate.

>
> Subodh
>
> ------------------------------
> *From:* Steven Valdez <svaldez=[email-masked]>
> *Sent:* Tuesday, September 15, 2020 9:08 PM
> *To:* Michele Orrù <[email-masked]>
> *Cc:* Subodh Iyengar <[email-masked]>; [email-masked] <
> [email-masked]>
> *Subject:* Re: [Privacy-pass] support for adoption of privacy pass
> documents
>
> Agreed that we probably want to support cases where double-spend
> protection isn't needed from the server's perspective, and letting certain
> I'm not sure if we should be describing what is appropriate/not
> appropriate for application profiles built on PrivacyPass, versus
> describing what properties PrivacyPass takes as fundamental to the protocol
> 210-692-4742 <(210)%20692-4742>
>

-- 

Steven Valdez |  Chrome Privacy Sandbox |  [email-masked] |
210-692-4742 <(210)%20692-4742>