Privacy Pass Architectural Framework

3.1. Redemption Protocol

The redemption protocol is a simple challenge-response based authorization protocol between Client and Origin. Origins prompt Clients with a token challenge and, if possible, Clients present a valid token for the challenge in response. The challenge controls the type of token that the Origin will accept for the given resource. As described in [HTTP-Authentication], there are a number of ways in which the token may vary, including:¶

• Issuance protocol. The token identifies the type of issuance protocol required for producing the token. Different issuance protocols have different security properties, e.g., some issuance protocols may produce tokens that are publicly verifiable, whereas others may not have this property.¶
• Issuer identity. Tokens identify which issuers are trusted for a given issuance protocol.¶
• Interactive or non-interactive. Tokens can either be interactive or not. An interactive token is one which requires a freshly issued token based on the challenge, whereas a non-interactive token can be issued proactively and cached for future use.¶
• Per-domain or cross-domain. Tokens can be constrained to the Origin for which the challenge originated, or can be used across Origins.¶

Depending on the use case, Origins may need to maintain state to track redeemed tokens. For example, Origins that accept non-interactive, cross-origin tokens SHOULD track which tokens have been redeemed already, since these tokens can be issued and then spent multiple times in response to any such challenge. See Section 5.1 for discussion.¶

Origins that admit cross-origin tokens bear some risk of allowing tokens issued for one Origin to be spent in an interaction with another Origin. If tokens protected with resources are unique to a single Origin, then said Origin MUST NOT admit cross-origin tokens for authorization.¶

3.2. Issuance Protocol

The issuance protocol embodies the core of Privacy Pass. It takes as input a challenge from the redemption protocol and produces a token, as shown in the figure below.¶

  Origin          Client        Attester          Issuer

                  +--------------------------------------\
    Challenge ----> TokenRequest --->                    |
                  |             (attest)                 |
                  |                TokenRequest --->     |
                  |                            (evaluate)|
                  |                   <--- TokenResponse |
      Token  <----+ TokenResponse <---                   |
                  |--------------------------------------/

Each issuance protocol may be different, e.g., in the number and types of participants, underlying cryptographic constructions used when issuing tokens, and even privacy properties.¶

Clients initiate the Token issuance protocol using the challenge, a randomly generated nonce, and public key for the Issuer. The Token issuance protocol itself can be any interactive protocol between Client, Issuer, or other parties that produces a valid authenticator over the Client's input, subject to the following security requirements.¶

1. Unconditional input secrecy. The issuance protocol MUST NOT reveal anything about the Client's private input, including the challenge and nonce. The issuance protocol can reveal the Issuer public key for the purposes of determining which private key to use in producing the issuance protocol. A result of this property is that the redemption flow is unlinkable from the issuance flow.¶
2. One-more forgery security. The issuance protocol MUST NOT allow malicious Clients to forge tokens without interacting with the Issuer directly.¶
3. Concurrent security. The issuance protocol MUST be safe to run concurrently with arbitrarily many Clients.¶

Each Issuance protocol MUST come with a detailed analysis of the privacy impacts of the protocol, why these impacts are justified, and guidelines on changes to the parametrization in Section 6.¶

The mechanism by which clients obtain the Issuer public key is not specified. Clients may be configured with this key or they may discover it via some other form. See [CONSISTENCY].¶

Depending on the use case, issuance may require some form of Client anonymization service similar to an IP-hiding proxy so that Issuers cannot learn information about Clients. This can be provided by an explicit participant in the issuance protocol, or it can be provided via external means, e.g., through the use of an IP-hiding proxy service like Tor. In general, Clients SHOULD minimize or remove identifying information where possible when invoking the issuance protocol.¶

Issuers MUST NOT issue tokens for Clients through untrusted Attesters. This is important because the Attester's role is to vouch for trust in privacy-sensitive Client information, such as account identifiers or IP address information, to the Issuer. Tokens produced by an Issuer that admits issuance for any type of attestation cannot be relied on for any specific property. See Section 3.2.1 for more details.¶

4.1. Metadata Privacy Implications

Any metadata bits of information can be used to further segment the size of the Client's anonymity set. Any Issuer that wanted to track a single Client could add a single metadata bit to Client tokens. For the tracked Client it would set the bit to 1, and 0 otherwise. Adding additional bits provides an exponential increase in tracking granularity similarly to introducing more Issuers (though with more potential targeting).¶

For this reason, the amount of metadata used by an Issuer in creating redemption tokens must be taken into account -- together with the bits of information that Issuer's may learn about Clients otherwise. Since this metadata may be useful for practical deployments of Privacy Pass, Issuers must balance this against the reduction in Client privacy. In general, Issuers should permit no more than 32 bits of metadata, as this can uniquely identify each possible user. We discuss this more in Section 6.¶

4.2. Issuer key rotation

Techniques to introduce Client "segregation" can be used to reduce Client anonymity. Such techniques are closely linked to the type of key schedule that is used by the Issuer. When an Issuer rotates their key, any Client that invokes the issuance protocol in this key cycle will be part of a group of possible clients owning valid tokens for this key. To mechanize this attack strategy, an Issuer could introduce a key rotation policy that forces Clients into small key cycles. Thus, reducing the size of the anonymity set for these Clients.¶

Issuers SHOULD invoke key rotation for a period of time between 1 and 12 weeks. Key rotations represent a trade-off between Client privacy and continued Issuer security. Therefore, it is still important that key rotations occur on a regular cycle to reduce the harmfulness of an Issuer key compromise.¶

With a large number of Clients, a minimum of one week gives a large enough window for Clients to participate in the issuance protocol and thus enjoy the anonymity guarantees of being part of a larger group. A maximum of 12 weeks limits the damage caused by a key compromise. If an Issuer realizes that a key compromise has occurred then the Issuer should generate a new key and make it available to Clients. If possible, it should invoke any revocation procedures that may apply for the old key.¶

4.3. Large numbers of Issuers

Similarly to the Issuer rotation dynamic that is raised above, if there are a large number of Issuers and Origins accept all of them segregation can occur. For example, if Clients obtain tokens from many Issuers, and Origins later challenge a Client for a token from each Issuer, Origins can learn information about the Client. Each per-Issuer token that a Client holds essentially corresponds to a bit of information about the Client that Origin learn. Therefore, there is an exponential loss in anonymity relative to the number of Issuers that there are.¶

For example, if there are 32 Issuers, then Origins learns 32 bits of information about the Client. If the distribution of Issuer trust is anything close to a uniform distribution, then this is likely to uniquely identify any Client amongst all other Internet users. Assuming a uniform distribution is clearly the worst-case scenario, and unlikely to be accurate, but it provides a stark warning against allowing too many Issuers at any one time.¶

In cases where clients can hold tokens for all Issuers at any given time, a strict bound SHOULD be applied to the active number of Issuers in the ecosystem. We propose that allowing no more than 4 Issuers at any one time is highly preferable (leading to a maximum of 64 possible user segregations). However, as highlighted in Section 6, having a very large user base (> 5 million users), could potentially allow for larger values. Issuer replacements should only occur with the same frequency as config rotations as they can lead to similar losses in anonymity if clients still hold redemption tokens for previously active Issuers.¶

In addition, we RECOMMEND that trusted registries indicate at all times which Issuers are deemed to be active. If a Client is asked to invoke any Privacy Pass exchange for an Issuer that is not declared active, then the client SHOULD refuse to retrieve the Issuer public key during the protocol.¶

  Client(context, issuer)                     Issuer(skS, pkS)
  ------------------------------------------------------------
  if issuer not in context {
    if context.length > REDEEM_LIMIT {
      Output {}
      return
    }
    context.push(issuer)
  }
  token = store[issuer.id].pop()
  req = Redeem(token, info)

                               req
                        ------------------>

                               if (dsIdx.includes(req.data)) {
                                 raise ERR_DOUBLE_SPEND
                               }
                               resp = Verify(pkS, skS, req)
                               if resp.success {
                                 dsIdx.push(req.data)
                               }

                                resp
                        <------------------
  Output resp

4.4. Partitioning of Issuer key material

If there are multiple key registries, or if a key registry colludes with an Issuer, then it is possible to provide a split-view of an Issuer's key material to different Clients. This would involve posting different key material in different locations, or actively modifying the key material at a given location.¶

Key registries should operate independently of Issuers in the ecosystem, and within the guidelines stated in Section 3.2.2. Any Client should follow the recommendations in Section 4 for determining whether an Issuer and its key material should be trusted.¶

4.5. Tracking and identity leakage

Privacy losses may be encountered if too many redemptions are allowed in a short burst. For instance, in the Internet setting, this may allow Origins to learn more information from the metadata that the Client may hold (such as first-party cookies for other origins). Mitigations for this issue are similar to those proposed in Section 4.3 for tackling the problem of having large number of Issuers.¶

4.6. Client incentives for anonymity reduction

Clients may see an incentive in accepting all tokens that are issued by an Issuer, even if the tokens fail later verification checks. This is because tokens effectively represent a form of currency that they can later redeem for some sort of benefit. The verification checks that are put in place are there to ensure that the Client does not sacrifice their anonymity. However, a Client may judge the "monetary" benefit of owning tokens to be greater than their own privacy.¶

Firstly, a Client behaving in this way would not be compliant with the protocol, as laid out in [I-D.ietf-privacypass-protocol].¶

Secondly, acting in this way only affects the privacy of the immediate Client. There is an exception if a large number of Clients colluded to accept bad data, then any Client that didn't accept would be part of a smaller anonymity set. However, such a situation would be identical to the situation where the total number of Clients in the ecosystem is small. Therefore, the reduction in the size of the anonymity set would be equivalent; see Section 4.3 for more details.¶

5.1. Double-spend protection

When applicable for non-interactive tokens, all Origins SHOULD implement a robust storage-query mechanism for checking that tokens sent by clients have not been spent before. Such tokens only need to be checked for each Origin individually. But all Origins must perform global double-spend checks to avoid clients from exploiting the possibility of spending tokens more than once against distributed token checking systems. For the same reason, the global data storage must have quick update times. While an update is occurring it may be possible for a malicious client to spend a token more than once.¶

5.2. Token exhaustion

When a Client holds tokens for an Issuer, it is possible for any verifier to invoke that client to redeem tokens for that Issuer. This can lead to an attack where a malicious verifier can force a Client to spend all of their tokens from a given Issuer. To prevent this from happening, tokens can be scoped to single Origins such that they can only be redeemed within for a single Origin.¶

If tokens are cross-Origin, Clients should use alternate methods to prevent many tokens from being redeemed at once. For example, if the Origin requests an excess of tokens, the Client could choose to not present any tokens for verification if a redemption had already occurred in a given time window.¶

6.1. Justification

We make the following assumptions in these parameter choices.¶

• Inferring the identity of a user in a 5000-strong anonymity set is difficult.¶
• After 2 weeks, all Clients in a system will have rotated to the new key.¶

In terms of additional metadata, the only concrete applications of Privacy Pass that use additional metadata require just a single bit. Therefore, we set the ceiling of permitted metadata to 1 bit for now, this may be revisited in future revisions.¶

The maximum choice of I is based on the equation 1/2 * U/2^(2I) = A. This is derived from the fact that permitting I Issuers lead to 2^I segregations of the total user-base U. Moreover, if we permit M = 1, then this effectively halves the anonymity set for each Issuer, and thus we incur a factor of 2I in the exponent. By reducing I, we limit the possibility of performing the attacks mentioned in Section 4.¶

We must also account for each user holding issued data for more then one possible active keys. While this may also be a vector for monitoring the access patterns of Clients, it is likely to unavoidable that Clients hold valid issuance data for the previous key epoch. This also means that the Issuer can continue to verify redemption data for a previously used key. This makes the rotation period much smoother for Clients.¶

For privacy reasons, it is recommended that key epochs are chosen that limit Clients to holding issuance data for a maximum of two keys. By choosing F = L/2 then the minimum value of F is a week, since the minimum recommended value of L is 2 weeks. Therefore, by the initial assumption, then all users should only have access to only two keys at any given time. This reduces the anonymity set by another half at most.¶

Finally, the minimum security parameter size is related to the cryptographic security offered by the protocol that is run. This parameter corresponds to the number of operations that any adversary has in breaking one of the security guarantees in the Privacy Pass protocol [I-D.ietf-privacypass-protocol].¶

6.2. Example parameterization

Using the specification above, we can give some example parameterizations. For example, the current Privacy Pass browser extension [PPEXT] has nearly 300000 active users (from Chrome and Firefox). As a result, log_2(U/A) is approximately 6 and so the maximum value of I should be 3.¶

If the value of U is much bigger (e.g. 5 million) then this would permit I = (log_2(5000000/5000)-1)/2 ~= 4 Issuers.¶

6.3. Allowing more Issuers

Using the recommendations in Section 4.3.1, it is possible to tolerate larger number of Issuers if Clients in the ecosystem ensure that they only store tokens for a small number of them. In particular, if Clients limit their storage of redemption tokens to the bound implied by I, then prevents a malicious verifier from triggering redemptions for all Issuers in the ecosystem.¶