Rate-Limited Token Issuance Protocol

1.1. Motivation

A client that wishes to keep its IP address private can hide its IP address using a proxy service or a VPN. However, doing so severely limits the client's ability to access services and content, since servers might not be able to enforce their policies without a stable and unique client identifier.¶

Privacy Pass tokens in general allow clients to provide anonymous attestation of various properties. The tokens generated by the basic issuance protocol ([ISSUANCE]) can be used to verify that a client meets a particular bar for attestation, but cannot be used by a redeeming server to rate-limit specific clients. This is because there is no mechanism in the issuance protocol to link repeated client token requests in order to apply rate-limiting.¶

There are several use cases for rate-limiting anonymous clients that are common on the Internet. These routinely use client IP address tracking, among other characteristics, to implement rate-limiting.¶

One example of this use case is rate-limiting website accesses to a client to help prevent abusive behavior. Operations that are sensitive to abuse, such as account creation on a website or logging into an account, often employ rate-limiting as a defense-in-depth strategy. Additional verification can be required by these pages when a client exceeds a set rate-limit.¶

Another example of this use case is a metered paywall, where an origin limits the number of page requests from each unique user over a period of time before the user is required to pay for access. The origin typically resets this state periodically, say, once per month. For example, an origin may serve ten (major content) requests in a month before a paywall is enacted. Origins may want to differentiate quick refreshes from distinct accesses.¶

For some applications, the basic issuance protocol from [ISSUANCE] could be used to implement rate limits. In particular, the 'Joint Attester and Issuer' model from [ARCH] could be used to restrict the number of tokens issued to individual clients over a time window. However, in this deployment model, the Attester and Issuer would learn all origins used by a specific client, thereby coupling sensitive attestation and redemption contexts. In some cases this might be a significant portion of browsing history.¶

1.2. Protocol Overview

The issuance protocol defined in this document decouples sensitive information in the attestation context, such as the client identity, from the information in the redemption context, such as the origin. It does so by employing the 'Split Origin, Attester, Issuer' model. In this model, the Issuer learns redemption information like origin identity (used to determine per-origin rate limit policies), and the Attester learns attestation information like client identity (used to keep track of the previous instances of token issuance).¶

Figure 1 shows how this interaction works for client requests that are within the rate limit. The Client's token request to the Attester (constructed according to Section 5.3, and forwarded to the Issuer according to Section 5.4) contains encrypted information that the Issuer uses to identify the relevant rate limit policy to apply. This rate limit policy is returned to the Attester (according to Section 5.5), which then checks whether or not the Client is within this policy. If yes, the Attester forwards the issuer token response to the Client so that the resulting token can be redeemed by the Origin.¶

                                                     +-----------+
      Client                                         |   Origin  |
        |                    Challenge               |           |
        <-------------------------------------------------+      |
        |                                            |           |
        |          +-------------+                   |           |
        |          |   Attester  |                   |           |
        |          |             |                   |           |
        |          | Attest      |    +----------+   |           |
        +----------------->      |    |  Issuer  |   |           |
        |          |             |    |          |   |           |
        |   TokenRequest         |    |          |   |           |
        |   + Anon Origin ID     |    |          |   |           |
        | [ + Encrypted Origin ] |    |          |   |           |
        +----------------->      |    |          |   |           |
        |          |             |    |          |   |           |
        |          |       TokenRequest          |   |           |
        |          |      [ + Encrypted origin ] |   |           |
        |          |     +------------------->   |   |           |
        |          |             |    |          |   |           |
        |          |             |    |          |   |           |
        |          |       TokenResponse         |   |           |
        |          |      [ + Rate limit ]       |   |           |
        |          |     <-------------------+   |   |           |
        |          |             |    |          |   |           |
        |          |  in limit?  |    |          |   |           |
        |          |     yes     |    |          |   |           |
        |          |             |    |          |   |           |
        |   TokenResponse        |    |          |   |           |
        <-----------------+      |    |          |   |           |
        |          |             |    |          |   |           |
        |          +-------------+    +----------+   |           |
        |                                            |           |
        |                    Redeem                  |           |
        +------------------------------------------------->      |
                                                     |           |
                                                     +-----------+

Figure 2 shows how this interaction works for client requests that exceed the rate limit. The Client's request to the Issuer and the Issuer's response to the Attester are the same. However, in this scenario, the Client is not within the rate limit, so the Attester responds to the Client with an error instead of the issuer's token response.¶

                                                     +-----------+
      Client                                         |   Origin  |
        |                    Challenge               |           |
        <-------------------------------------------------+      |
        |                                            |           |
        |          +-------------+                   |           |
        |          |   Attester  |                   |           |
        |          |             |                   |           |
        |          | Attest      |    +----------+   |           |
        +----------------->      |    |  Issuer  |   |           |
        |          |             |    |          |   |           |
        |   TokenRequest         |    |          |   |           |
        |   + Anon Origin ID     |    |          |   |           |
        | [ + Encrypted Origin ] |    |          |   |           |
        +----------------->      |    |          |   |           |
        |          |             |    |          |   |           |
        |          |       TokenRequest          |   |           |
        |          |      [ + Encrypted origin ] |   |           |
        |          |     +------------------->   |   |           |
        |          |             |    |          |   |           |
        |          |             |    |          |   |           |
        |          |       TokenResponse         |   |           |
        |          |       + Rate limit          |   |           |
        |          |     <-------------------+   |   |           |
        |          |             |    |          |   |           |
        |          |  in limit?  |    |          |   |           |
        |          |      no     |    |          |   |           |
        |          |             |    |          |   |           |
        |        Error           |    |          |   |           |
        <-----------------+      |    |          |   |           |
        |          |             |    |          |   |           |
        |          +-------------+    +----------+   |           |
        X                                            |           |
  issuance failed                                    +-----------+

Each Issuer defines a window of time over which Attesters enforce rate limits, defined in the Issuer configuration directory (Section 3). This window might be as long as a month, or as short as an hour, depending on the use case. The window is the same across all Origins that work with the Issuer; if multiple window lengths are needed, then the entity running the Issuer can run multiple Issuers with different Issuer names, one for each window length.¶

The window begins upon a Client's first token request to the Attester for that Issuer and ends after the window time elapses, after which the Client's rate limit state is reset. Issuers indicate which rate limit to use for a given request by parsing the Client's encrypted Origin. Attesters enforce the rate limit based on the value indicated by the Issuer, and maintaining the count of accesses by a client to a corresponding Client's Origin Alias (see Section 2).¶

Along with the rate limit for the Origin, Issuers include a value generated with a per-Origin secret in their responses, which allows Attesters to ensure that the Client's Origin Alias indicated by the Client maps to exactly one Origin as seen by the Issuer; this value that is used to validate the Client's Origin Alias is called the Issuer's Origin Alias (see Section 2). Issuers can rotate the per-Origin secret they use as desired. If a rotation event happens during a Client's active policy window, the Attester would compute a different Issuer's Origin Alias and mistakenly conclude that the Client is accessing a new Origin. To mitigate this, Clients provide a stable Client's Origin Alias in their request to the Attester, which is constant for all requests to that Origin. This allows the Attester to detect when Issuer rotation events occur without affecting Client rate limits.¶

                          Per-Origin
                         secret rotate
Issuer:      -----+------------X----------+------------> Time
                  |         policy        |
Client            |         window        |
Token Requests:   *--------------*--------|
                  |              |        |
                  v              v        |
            Issuer Origin  Issuer Origin  |
                ID x           ID y       |
                  |                       |
            (policy start)          (policy end)

Unlike the basic issuance protocol [ISSUANCE], the rate-limited issuance protocol in this document has additional functional and state requirements for Client, Attester, and Issuer. Section 5.1.2 describes the state that the Attester must track in order to enforce these limits, Section 5.1.1 describes the Client state necessary for successive token requests with the Attester, and Section 5.1.3 describes the state necessary for the Issuer to apply rate limits. The functional description of each participant in this protocol is explained in Section 5¶

1.3. Properties and Requirements

For rate-limited token issuance, the Attester, Issuer, and Origin as defined in [ARCH] each have partial knowledge of the Client's identity and actions, and each entity only knows enough to serve its function (see Section 2 for more about the pieces of information):¶

• The Attester knows the Client's identity and learns the Client's public key (Client Key), the Issuer being targeted (Issuer Name), the period of time for which the Issuer's policy is valid (Issuer Policy Window), the number of tokens the Issuer is willing to issue within the current policy window, and the number of tokens issued to a given Client for the claimed Origin in the policy window. The Attester does not know the identity of the Origin the Client is trying to access (Origin Name), but knows a Client-anonymized identifier for it (Client's Origin Alias).¶

• The Issuer knows a per-Origin secret (Issuer Origin Secret) and policy about client access, and learns the Origin's identity (Origin Name) during issuance. The Issuer does not learn the Client's identity or information about the Client's access pattern.¶

• The Origin knows the Issuer to which it will delegate an incoming Client (Issuer Name), and can verify that any tokens presented by the Client were signed by the Issuer. The Origin does not learn which Attester was used by a Client for issuance.¶

Since an Issuer applies policies on behalf of Origins, a Client is required to reveal the Origin's identity to the delegated Issuer. It is a requirement of this protocol that the Attester not learn the Origin's identity so that, despite knowing the Client's identity, an Attester cannot track and concentrate information about Client activity.¶

An Issuer expects an Attester to verify its Clients' identities correctly, but an Issuer cannot confirm an Attester's efficacy or the Attester-Client relationship directly without learning the Client's identity. Similarly, an Origin does not know the Attester's identity, but ultimately relies on the Attester to correctly verify or authenticate a Client for the Origin's policies to be correctly enforced. An Issuer therefore chooses to issue tokens to only known and reputable Attesters; the Issuer can employ its own methods to determine the reputation of a Attester.¶

An Attester is expected to employ a stable Client identifier, such as an IP address, a device identifier, or an account at the Attester, that can serve as a reasonable proxy for a user with some creation and maintenance cost on the user.¶

For the Issuance protocol, a Client is expected to create and maintain stable and explicit secrets for time periods that are on the scale of Issuer policy windows. Changing these secrets arbitrarily during a policy window can result in token issuance failure for the rest of the policy window; see Section 5.1.1 for more details. A Client can use a service offered by its Attester or a third-party to store these secrets, but it is a requirement of this protocol that the Attester not be able to learn these secrets.¶

The privacy guarantees of this issuance protocol, specifically those around separating the identity of the Client from the names of the Origins that it accesses, are based on the expectation that there is not collusion between the entities that know about Client identity and those that know about Origin identity. Clients choose and share information with Attesters, and Origins choose and share policy with Issuers; however, the Attester is generally expected to not be colluding with Issuers or Origins. If this occurs, it can become possible for an Attester to learn or infer which Origins a Client is accessing, or for an Origin to learn or infer the Client identity. For further discussion, see Section 9.6.¶

5.1. State Requirements

The Issuance protocol requires each participating endpoint to maintain some necessary state, as described in this section.¶

5.2. Issuance HTTP Headers

The Issuance protocol defines four new HTTP headers that are used in requests and responses between Clients, Attesters, and Issuers (see Section 11.2).¶

The "Sec-Token-Origin-Alias" is an Item Structured Header [RFC8941]. Its value MUST be a Byte Sequence. This header is sent both on Client-to-Attester requests (Section 5.3) and on Issuer-to-Attester responses (Section 5.5). Its ABNF is:¶

    Sec-Token-Origin-Alias = sf-binary

The "Sec-Token-Client" is an Item Structured Header [RFC8941]. Its value MUST be a Byte Sequence. This header is sent on Client-to-Attester requests (Section 5.3), and contains the bytes of Client Key. Its ABNF is:¶

    Sec-Token-Client = sf-binary

The "Sec-Token-Request-Blind" is an Item Structured Header [RFC8941]. Its value MUST be a Byte Sequence. This header is sent on Client-to-Attester requests (Section 5.3), and contains a per-request nonce value. Its ABNF is:¶

    Sec-Token-Request-Blind = sf-binary

The "Sec-Token-Limit" is an Item Structured Header [RFC8941]. Its value MUST be an Integer. This header is sent on Issuer-to-Attester responses (Section 5.5), and contains the number of times a Client can retrieve a token for the requested Origin within a policy window, as set by the Issuer. Its ABNF is:¶

    Sec-Token-Limit = sf-integer

5.3. Client-to-Attester Request

The Client and Attester MUST use a secure and Attester-authenticated HTTPS connection. They MAY use mutual authentication or mechanisms such as TLS certificate pinning, to mitigate the risk of channel compromise; see Section 8 for additional about this channel.¶

https://attester.net/token-request{?issuer}

nonce = random(32)
context = SHA256(challenge)
token_input = concat(0x0003, nonce, context, key_id)
blinded_msg, blind_inv = rsabssa_blind(pkI, token_input)

struct {
  uint8_t token_key_id;
  uint8_t blinded_msg[Nk];
  uint8_t padded_origin_name<0..2^16-1>;
} InnerTokenRequest;

struct {
   uint16_t token_type = 0x0003;
   uint8_t request_key[Npk];
   uint8_t issuer_encap_key_id[32];
   uint8_t encrypted_token_request<1..2^16-1>;
   uint8_t request_signature[Nsig];
} TokenRequest;

:method = POST
:scheme = https
:authority = attester.net
:path = /token-request?issuer=issuer.net
accept = message/token-response
cache-control = no-cache, no-store
content-type = message/token-request
content-length = <Length of TokenRequest>
sec-token-origin-alias = Client's Origin Alias
sec-token-client = Client Key
sec-token-request-blind = request_blind

<Bytes containing the TokenRequest>

5.4. Attester-to-Issuer Request

The Attester and the Issuer MUST use a secure and Issuer-authenticated HTTPS connection for all requests. Also, Issuers MUST authenticate Attesters, either via mutual TLS or another form of application-layer authentication. They MAY additionally use mechanisms such as TLS certificate pinning, to mitigate the risk of channel compromise; see Section 8 for additional about this channel.¶

:method = POST
:scheme = https
:authority = issuer.net
:path = /token-request
accept = message/token-response
cache-control = no-cache, no-store
content-type = message/token-request
content-length = <Length of TokenRequest>

<Bytes containing the TokenRequest>

5.5. Token Issuance Response

blind_sig = rsabssa_blind_sign(skP, InnerTokenRequest.blinded_msg)

:status = 200
content-type = message/token-response
content-length = <Length of blind_sig>
sec-token-origin-alias = index_key
sec-token-limit = Token limit

<Bytes containing the encrypted_token_response>

authenticator = rsabssa_finalize(pkI, token_input, blind_sig, blind_inv)

struct {
    uint16_t token_type = 0x0003
    uint8_t nonce[32];
    uint8_t context[32];
    uint8_t token_key_id[Nid];
    uint8_t authenticator[Nk]
} Token;

5.6. Penalization of Invalid Clients and Issuers

When an Attester encounters incorrect and potentially malicious behavior by either Clients or Issuers, it needs to "penalize" them. This involves keeping state about invalid protocol events, and determining when a particular Client or Issuer has exceeded a threshold for such events.¶

Each category of invalid events can have a different threshold, and can apply to Clients, Issuers, or both. Different penalization events are described below, with suggested thresholds. This list is not exhaustive.¶

• Client Key changing more than once over any two consecutive policy windows for a single Client, based on the Attester's view of Client identity. This is a Client-specific penalization event. A RECOMMENDED threshold for penalizing the Client based on this is one event; a well-behaved Client will never change keys this frequently.¶

• Issuer responses missing the "Sec-Token-Origin-Alias" header on a 2xx response. This is an Issuer-specific penalization event. A RECOMMENDED threshold for penalizing the Issuer based on this is ten events across all Clients; a well-behaved Issuer will never generate such responses, but it can be useful for an Attester to have a small tolerance for errors before penalizing an Issuer entirely.¶

• Issuer's Origin Alias (from Issuer) collision across two Anonymous Origin IDs for a particular Client within a single policy window. This penalization event is applicable for both Clients and Issuers. A RECOMMENDED threshold for penalizing the Issuer is ten events across different Clients. A RECOMMENDED threshold for penalizing the Client is two events across multiple Issuers, or five events with a single Issuer. If many events are seen for a single Issuer, it is likely that the Issuer is compromised or malicious; while if such events are seen for a specific Client, it is likely that the Client is is compromised or malicious.¶

Once a Client or Issuer passes the threshold for penalization, the Attester rejects future requests from that Client or for that Issuer. This SHOULD only be reset after a sufficient period of time (such as at least one policy window), and based on either manual review or another validation process determined by the Attester. Penalization indicates that a Client or Issuer might be malicious or compromised, and so ought not to be trusted until further validation that the error or attack has been mitigated.¶

6.1. Client to Issuer Encapsulation

Given a EncapsulationKey (Issuer Encapsulation Key), Clients produce encrypted_token_request using the following values:¶

• the one octet key identifier from the Name Key, keyID, with the corresponding KEM identified by kemID, the public key from the configuration, pkI, and;¶

• a selected combination of KDF, identified by kdfID, and AEAD, identified by aeadID.¶

Beyond the key configuration inputs, Clients also require the following inputs defined in Section 5.3: token_key_id, blinded_msg, request_key, origin_name, and issuer_encap_key_id.¶

Together, these are used to encapsulate an InnerTokenRequest and produce an encrypted token request (encrypted_token_request).¶

origin_name contains the name of the origin that initiated the challenge, as taken from the TokenChallenge.origin_info field. If the TokenChallenge.origin_info field is empty, origin_name is set to the empty string "".¶

The process for generating encrypted_token_request from blinded_msg, request_key, and origin_name values is as follows:¶

1. Compute an [HPKE] context using pkI, yielding context and encapsulation key enc.¶

2. Construct associated data, aad, by concatenating the values of keyID, kemID, kdfID, aeadID, and all other values of the TokenRequest structure.¶

3. Pad origin_name with N zero bytes, where N = 31 - ((L - 1) % 32) and L is the length of origin_name. If L is 0, N = 32. Denote this padding process as the function pad.¶

4. Encrypt (seal) the padded origin_name with aad as associated data using context, yielding ciphertext ct.¶

5. Concatenate the values of aad, enc, and ct, yielding encrypted_token_request.¶

Note that enc is of fixed-length, so there is no ambiguity in parsing this structure.¶

In pseudocode, this procedure is as follows:¶

enc, context = SetupBaseS(pkI, "InnerTokenRequest")
aad = concat(encode(1, keyID),
             encode(2, kemID),
             encode(2, kdfID),
             encode(2, aeadID),
             encode(2, token_type),
             encode(Npk, request_key),
             encode(32, issuer_encap_key_id))
padded_origin_name = pad(origin_name)
inner_token_request_enc = concat(encode(1, token_key_id),
                                 encode(Nk, blinded_msg),
                                 encode(2, len(padded_origin_name)),
                                 encode(len(padded_origin_name), padded_origin_name))
ct = context.Seal(aad, inner_token_request_enc)
encrypted_token_request = concat(enc, ct)

Issuers reverse this procedure to recover the InnerTokenRequest value by computing the AAD as described above and decrypting encrypted_token_request with their private key skI (the private key corresponding to pkI). The origin_name value is recovered from InnerTokenRequest.padded_origin_name by stripping off padding bytes. In pseudocode, this procedure is as follows:¶

enc, ct = parse(encrypted_token_request)
aad = concat(encode(1, keyID),
             encode(2, kemID),
             encode(2, kdfID),
             encode(2, aeadID),
             encode(2, token_type),
             encode(Npk, request_key),
             encode(32, issuer_encap_key_id))
context = SetupBaseR(enc, skI, "TokenRequest")
inner_token_request_enc, error = context.Open(aad, ct)

The InnerTokenRequest.blinded_msg, InnerTokenRequest.token_key_id, and unpadded origin_name values are used by the Issuer as described in Section 5.4.¶

6.2. Issuer to Client Encapsulation

Given an HPKE context context computed in Section 6.1, Issuers encapsulate their token response blind_sig, yielding an encrypted token response encrypted_token_response, to the Client as follows:¶

1. Export a secret secret from context, using the string "OriginTokenResponse" as context. The length of this secret is max(Nn, Nk), where Nn and Nk are the length of AEAD key and nonce associated with context.¶

2. Generate a random value of length max(Nn, Nk) bytes, called response_nonce.¶

3. Extract a pseudorandom key prk using the Extract function provided by the KDF algorithm associated with context. The ikm input to this function is secret; the salt input is the concatenation of enc (from enc_request) and response_nonce¶

4. Use the Expand function provided by the same KDF to extract an AEAD key key, of length Nk - the length of the keys used by the AEAD associated with context. Generating key uses a label of "key".¶

5. Use the same Expand function to extract a nonce nonce of length Nn - the length of the nonce used by the AEAD. Generating nonce uses a label of "nonce".¶

6. Encrypt blind_sig, passing the AEAD function Seal the values of key, nonce, empty aad, and a pt input of request, which yields ct.¶

7. Concatenate response_nonce and ct, yielding an Encapsulated Response enc_response. Note that response_nonce is of fixed-length, so there is no ambiguity in parsing either response_nonce or ct.¶

In pseudocode, this procedure is as follows:¶

secret = context.Export("OriginTokenResponse", Nk)
response_nonce = random(max(Nn, Nk))
salt = concat(enc, response_nonce)
prk = Extract(salt, secret)
aead_key = Expand(prk, "key", Nk)
aead_nonce = Expand(prk, "nonce", Nn)
ct = Seal(aead_key, aead_nonce, "", blind_sig)
encrypted_token_response = concat(response_nonce, ct)

Clients decrypt encrypted_token_response by reversing this process. That is, they first parse enc_response into response_nonce and ct. They then follow the same process to derive values for aead_key and aead_nonce.¶

The client uses these values to decrypt ct using the Open function provided by the AEAD. Decrypting might produce an error, as follows:¶

blind_sig, error = Open(aead_key, aead_nonce, "", ct)

7.1. Client Behavior

This section describes the Client behavior for generating an one-time-use request key and signature. Clients provide their Client Secret as input to the request key generation step, and the rest of the token request inputs to the signature generation step.¶

sk_blind = BKS-BlindKeyGen()
ctx = concat(encode(2, token_type)), "ClientBlind")
blinded_key = BKS-BlindPublicKey(pk_sign, sk_blind, ctx)
request_key = BKS-SerializePublicKey(blinded_key)
request_blind = BKS-SerializePrivatekey(sk_blind)

message = concat(token_type,
                 request_key,
                 issuer_encap_key_id,
                 encode(2, len(encrypted_token_request)),
                 encrypted_token_request)
ctx = concat(encode(2, token_type)), "ClientBlind")
request_signature = BKS-BlindKeySign(sk_sign, sk_blind, ctx, message)

7.2. Attester Behavior (Client Request Validation)

Given a TokenRequest request containing request_key, request_signature, and request_blind, as well as Client Key pk_blind, Attesters verify the signature as follows:¶

1. Check that request_key is a valid public key. If this fails, abort.¶

2. Check that request_blind is a valid private key. If this fails, abort.¶

3. Blind the Client Key pk_sign by blind sk_blind, yielding a blinded key. If this does not match request_key, abort.¶

4. Verify request_signature over the contents of the request, excluding the signature itself, using request_key. If signature verification fails, abort.¶

In pseudocode, this is as follows:¶

blind_key = BKS-DeserializePublicKey(request_key)
sk_blind = BKS-DeserializePrivatekey(request_blind)
ctx = concat(encode(2, token_type)), "ClientBlind")
pk_blind = BKS-BlindPublicKey(pk_sign, sk_blind, ctx)
if pk_blind != blind_key:
  raise InvalidParameterError

context = parse(request[..len(request)-Nsig]) // this matches context computed during signing
valid = BKS-Verify(blind_key, context, request_signature)
if not valid:
  raise InvalidSignatureError

7.3. Issuer Behavior

Given an Issuer Origin Secret (denoted sk_origin) and a TokenRequest, from which request_key and request_signature are parsed, Issuers verify the request signature and compute a response as follows:¶

1. Check that request_key is a valid public key. If this fails, abort.¶

2. Verify request_signature over the contents of the request, excluding the signature itself, using request_key. If signature verification fails, abort.¶

3. Blind request_key by Issuer Origin Secret, sk_origin, yielding an index key.¶

4. Output the index key.¶

In pseudocode, this is as follows:¶

blind_key = BKS-DeserializePublicKey(request_key)
context = parse(request[..len(request)-Nsig]) // this matches context computed during signing
valid = BKS-Verify(blind_key, context, request_signature)
if not valid:
  raise InvalidSignatureError

ctx = concat(encode(2, token_type)), "IssuerBlind")
evaluated_key = BKS-BlindPublicKey(request_key, sk_origin, ctx)
index_key = BKS-SerializePublicKey(evaluated_key)

7.4. Attester Behavior (Index Computation)

Given an Issuer response index_key, Client blind sk_blind, and Client Key (denoted pk_sign), Attesters complete the Issuer's Origin Alias computation as follows:¶

1. Check that index_key is a valid public key. If this fails, abort.¶

2. Unblind the index_key using the Client blind sk_blind, yielding the index result.¶

3. Run HKDF [RFC5869] with the hash function corresponding to the BKS scheme, using the index result as the secret, Client Key pk_sign as the salt, and ASCII string "IssuerOriginAlias" as the info string, yielding Issuer's Origin Alias.¶

In pseudocode, this is as follows:¶

evaluated_key = BKS-DeserializePublicKey(index_key)
ctx = concat(encode(2, token_type)), "ClientBlind")
unblinded_key = BKS-UnblindPublicKey(evaluated_key, sk_blind, ctx)

index_result = BKS-SerializePublicKey(unblinded_key)
pk_encoded = BKS-SerializePublicKey(pk_sign)

issuer_origin_alias = HKDF-Hash(secret=index_result,
  salt=pk_encoded, info="IssuerOriginAlias")

8.1. Client Secret Use

The Client Secret key is used for two purposes in this protocol: (1) computing request signatures and (2) computing the Issuer's Origin Alias (with the corresponding public key). This is necessary to ensure the client associated with the Issuer's Origin Alias is the same client that produced a corresponding request. In general, using the same cryptographic key for two distinct purposes is considered bad practice. However, analysis of this protocol demonstrates that it is safe in this context. The Client Secret MUST NOT be used for any purpose outside of this protocol.¶

8.2. Custom Token Request Encapsulation

The protocol in this document uses [HPKE] directly to encrypt token request information to the issuer while also authenticating information exposed to the attester. Oblivious HTTP [OHTTP], which is a protocol built on top of HPKE for request encapsulation, is not suitable for this purpose since it does not allow clients to additionally authenticate application-layer information that is visible to intermediaries, which is the case for the data visible to the Attester.¶

8.3. Channel Security

An attacker that can act as an intermediate between Attester and Issuer communication can influence or disrupt the ability for the Issuer to correctly rate-limit token issuance. All communication channels use server-authenticated HTTPS. Some connections, e.g., between an Attester and an Issuer, require mutual authentication between both endpoints. Where appropriate, endpoints MAY use further enhancements such as TLS certificate pinning to mitigate the risk of channel compromise.¶

8.4. Token Request Unlinkability and Unforgeability

Client token requests are constructed such that an Issuer cannot distinguish between any two token requests from the same Client and two requests from different Clients. We refer to this property as issuance unlinkability. This property is achieved by the way the tokens are constructed. In particular, TokenRequest.request_key and TokenRequest.request_signature are the only value in a TokenRequest that is derived from per-Client information, i.e., the Client Secret.¶

TokenRequest.request_key is computed using a freshly generated blind for each token request. As a result, the value of TokenRequest.request_key in one token request is statistically independent from Client Key. Similarly, TokenRequest.request_signature is computed using the same freshly generated blind as TokenRequest.request_key for each token request, and the resulting signature is therefore independent from signatures produced using Client Secret. More details about this unlinkability property can be found in [KEYBLINDING].¶

This unlinkability property is only intended for requests observed by the Issuer. In contrast, the Attester is required to link requests from the same Client together for the purposes of enforcing rate limits. This Attester does this by observing the Client Key. Importantly, the Client Key is not sent to the Issuer during the issuance flow, as doing this would allow the Issuer to trivially link two requests to the same Client.¶

The token request signature is also required to be unforgeable. Informally, unforgeability means that no entity can produce a valid (message, signature) pair for any blinding key without access to the private signing key. Importantly, the means the Attester cannot forge signatures on behalf of a given Client in an attempt to learn the origin name.¶

8.5. Information Disclosure

The protocol in this document is designed such that information pertaining to issuance of a token is limited to parties that need it for completing the protocol. In particular, honest-but-curious Attesters learn only the Issuer's Origin Alias as described in Section 7, any per-Client information necessary for attestation, and the target Issuer for a given token request. The Attester does not directly learn the origin name associated with a given token request, though it does learn the distribution of tokens across Client interactions. This auxiliary information could be used to infer the Origin for a given token. For example, if an Issuer has only two configured Origins, each with a different token request pattern, then the distribution of Client tokens might reveal the Origin associated with a given token.¶

Malicious or otherwise compromised Attesters can choose to not follow the protocol described in this specification, allowing, for example, Clients to bypass rate limits imposed by Origins. Moreover, malicious Attesters could reveal the per-request blind (request_blind) to Issuers, breaking the unlinkability property described in Section 8.4.¶

Honest-but-curious Issuers only learn the Attester that vouches for a particular Client's token request and the origin name associated with a token request. Issuers do not learn the Issuer's Origin Alias or any per-Client information used when creating a token request.¶

Conversely, malicious Issuers that do not follow the protocol can choose to not validate the token request signature, thereby allowing others to forge token requests in an attempt to learn the origin name. Malicious Issuers can also rotate token signing keys or Issuer Origin Secret values frequently in an attempt to bypass Attester-enforced rate limits. Both of these are detectable by the Attester, though. Issuers can also lie about per-origin rate limits without detection, e.g., by increasing the limit to a value well beyond any configured limit by an Origin, or return different limits for different origins to the Attester.¶

Clients learn the output token. They do not learn the Issuer's Origin Alias, though the security of the protocol does not depend on keeping this value secret from Clients. Moreover, even malicious Clients cannot tamper with per-Client state stored on the Attester for other Clients, as doing so requires knowledge of their unique Client Secret.¶

8.6. Rate Limit Enforcement

Since the purpose of this token variant is to allow rate limits to be enforced on token issuance to Clients, the accuracy of the rate limit is an important part of evaluating the efficacy and security of a given deployment.¶

The rate limit is enforced by the Attester based on state about the Client that only the Attester holds, where the state is kept on a per-Issuer and per-Origin basis. This means that the selection of both the Issuer and the Attester determines the state for the rate limit. As such, Origins SHOULD only send challenges for a single Issuer within a given period of time, in order to ensure that a Client is not able to get tokens across multiple Issuers and exceed the rate limit. Similarly, Issuers need to be selective in which Attesters they allow, to ensure that a single Client cannot trivially work with many Attesters in order to exceed the rate limit.¶

Since the effectiveness of the rate limit requires a bounded set of Attesters for any particular use case, deployments need to consider the impact on centralization in order to ensure that new Attesters can still join the overall ecosystem. See the discussion on centralization in [ARCH].¶

9.1. Client Token State and Origin Tracking

Origins SHOULD only generate token challenges based on client action, such as when a user loads a website. Clients SHOULD ignore token challenges if an Origin tries to force the client to present tokens multiple times without any new client-initiated action. Failure to do so can allow malicious origins to track clients across contexts. Specifically, an origin can abuse per-user token limits for tracking by assigning each new client a random token count and observing whether or not the client can successfully redeem that many tokens in a given context. If any token redemption fails, then the origin learns information about how many tokens that client had previously been issued.¶

By rejecting repeated or duplicative challenges within a single context, the origin only learns a single bit of information: whether or not the client had any token quota left in the given policy window.¶

9.2. Origin Verification

Rate-limited tokens are defined in terms of a Client authenticating to an Origin, where the "origin" is used as defined in [RFC6454]. In order to limit cross-origin correlation, Clients MUST verify that the name of the origin that is providing the HTTP authentication challenge is present in the TokenChallenge.origin_info list ([AUTHSCHEME]), where the matching logic is defined for same-origin policies in [RFC6454]. Clients MAY further limit which authentication challenges they are willing to respond to, for example by only accepting challenges when the origin is a web site to which the user navigated.¶

9.3. Client Identification with Unique Encapsulation Keys

Client activity could be linked if an Origin and Issuer collude to have unique keys targeted at specific Clients or sets of Clients.¶

As with the basic issuance protocol [ISSUANCE], the token_key_id is truncated to a single octet to mitigate the risk of unique keys per client.¶

Clients SHOULD check encapsulation key consistency to help mitigate targeting attacks. Consistency for Privacy Pass resources such as Issuer directories and token keys is described in [CONSISTENCY]. [CONSISTENCY-MIRROR] describes a specific approach in which Clients can check the consistency of a key using a mirror server. Since encapsulation keys are available in the Issuer well-known configuration (Section 3), the Client can fetch the configuration via a mirror to perform a consistency check.¶

Clients can also detect inconsistency if the encapsulation key changes across multiple challenges (indicating that an Origin might be trying to target Clients, but did not recognize the Client across two requests). Encapsulation key changes within a short period of time can indicate that the Origin is attempting to target the Client.¶

The Attester can also help ensure consistency with an in-band check, which conforms to the approach in [CONSISTENCY-INBAND]. The Attester can observe and validate the issuer_encap_key_id presented by the Client to the Issuer. As described in Section 5.3, Attesters MUST validate that the issuer_encap_key_id in the Client's TokenRequest matches a known Issuer Encapsulation Key public key for the Issuer. The Attester needs to support key rotation, but ought to disallow very rapid key changes, which could indicate that an Origin is colluding with an Issuer to try to rotate the key for each new Client in order to link the client activity.¶

9.4. Client Identification with Unique Per-Origin Token Keys

Client activity could also be linked if an Origin and Issuer collude to use a unique per-origin Token Key.¶

Since Attesters do not see per-origin identities that can be correlated across Clients, Attesters cannot perform in-band consistency checks.¶

Clients SHOULD check encapsulation key consistency to help mitigate targeting attacks. Consistency for Privacy Pass resources such as Issuer directories and token keys is described in [CONSISTENCY]. [CONSISTENCY-MIRROR] describes a specific approach in which Clients can check the consistency of a key using a mirror server. Since per-origin token keys are available in the Issuer well-known configuration (Section 3), the Client can fetch the configuration via a mirror to perform a consistency check.¶

Clients can detect inconsistency if the token key for an Origin-Issuer pair changes across multiple challenges (indicating that an Origin might be trying to target Clients, but did not recognize the Client across two requests). Token key changes within a short period of time can indicate that the Origin is attempting to target the Client.¶

9.5. Origin Identification

As stated in Section 1.3, the design of this protocol is such that Attesters cannot learn the identity of origins that Clients are accessing. The Origin Name itself is encrypted in the request between the Client and the Issuer, so the Attester cannot directly learn the value. However, in order to prevent the Attester from inferring the value, additional constraints need to be added:¶

• Each Issuer SHOULD serve tokens to a large number of Origins. A one-to-one relationship between Origin and Issuer would allow an Attester to infer which Origin is accessed simply by observing the Issuer identity.¶

• Issuers SHOULD NOT return rate-limit values that are specific to Origins, such that an Attester can infer which Origin is accessed by observing the rate limit. This can be mitigated by having many Origins share the same rate-limit value.¶

• If an Issuer changes the rate-limit values for a single Origin, that change occurring at the same time across multiple Clients could allow Attesters to recognize an Origin in common across Clients. To mitigate this, Issuers either can change the limits for multiple Origins simultaneously, or have an Origin switch to a separate Issuer.¶

Some deployments MAY choose to relax these requirements, such as in cases where the origins being accessed are ubiquitous or do not correspond to user-specific behavior.¶

9.6. Collusion Among Different Entities

Collusion among the different entities in the Privacy Pass architecture can result in exposure of a client's per-origin access patterns.¶

For this issuance protocol, Issuers and Attesters should be run by mutually distinct organizations to limit information sharing. A single entity running an Issuer and Attester for a single token issuance flow can view the origins being accessed by a given client. Running the Issuer and Attester in this 'single Issuer/Attester' fashion reduces the privacy promises of no one entity being able to learn Client browsing patterns. This may be desirable for a redemption flow that is limited to specific Issuers and Attesters, but should be avoided where hiding origin names from the Attester is desirable.¶

If a Attester and Origin are able to collude, they can correlate a client's identity and origin access patterns through timestamp correlation. The timing of a request to an Origin and subsequent token issuance to a Attester can reveal the Client identity (as known to the Attester) to the Origin, especially if repeated over multiple accesses.¶

10.1. Token Key Management

Issuers SHOULD generate new (Token Key, Issuer Origin Secret) values regularly, and SHOULD maintain old and new secrets to allow for graceful updates. The RECOMMENDED rotation interval is two times the length of the policy window for that information. During generation, issuers must ensure the token_key_id (the 8-bit prefix of SHA256(Token Key)) is different from all other token_key_id values for that Origin currently in rotation. One way to ensure this uniqueness is via rejection sampling, where a new key is generated until its token_key_id is unique among all currently in rotation for the Origin.¶

11.1. Token Type

This document updates the "Token Type" Registry ([AUTHSCHEME]) with the following value:¶

The details of the signature scheme with key blinding and unblinding functions for each token type above are described in the following sections.¶

11.2. HTTP Headers

This document registers four new headers for use on the token issuance path in the "Permanent Message Header Field Names" <https://www.iana.org/assignments/message-headers>.¶

    +-------------------------+----------+--------+---------------+
    | Header Field Name       | Protocol | Status |   Reference   |
    +-------------------------+----------+--------+---------------+
    | Sec-Token-Origin-Alias  |   http   |  std   | This document |
    +-------------------------+----------+--------+---------------+
    | Sec-Token-Client        |   http   |  std   | This document |
    +-------------------------+----------+--------+---------------+
    | Sec-Token-Request-Blind |   http   |  std   | This document |
    +-------------------------+----------+--------+---------------+
    | Sec-Token-Limit         |   http   |  std   | This document |
    +-------------------------+----------+--------+---------------+

B.1. Origin Name Encryption Test Vector

The test vector below for the procedure in Section 6 lists the following values:¶

• origin_name: The Origin Name to encrypt, represented as a hexadecimal string.¶

• kem_id, kdf_id, aead_id: The HPKE algorithms comprising the ciphersuite DHKEM(X25519, HKDF-SHA256), HKDF-SHA256, AES-128-GCM.¶

• issuer_encap_key_seed: The seed used to derive the private key corresponding to Issuer Encapsulation Key via the DeriveKeyPair function as defined in Section 7.1.3. of [HPKE], represented as a hexadecimal string.¶

• issuer_encap_key: The public Issuer Encapsulation Key, represented as a hexadecimal string.¶

• token_type: The type of the protocol specified in this document.¶

• token_key_id: The ID of Token Key computed as in Section 5.3, a single octet.¶

• blinded_msg: A random blinded_msg value, represented as a hexadecimal string.¶

• request_key: A random request_key value, represented as a hexadecimal string.¶

• issuer_encap_key_id: The Issuer Encapsulation Key ID computed as in Section 5.3, represented as a hexadecimal string.¶

• encrypted_token_request: The encrypted InnerTokenRequest, represented as a hexadecimal string.¶

origin_name: 746573742e6578616d706c65
kem_id: 32
kdf_id: 1
aead_id: 1
issuer_encap_key_seed:
d2653816496f400baec656f213f1345092f4406af4f2a63e164956c4c3d240ca
issuer_encap_key: 010020d7b6a2c10e75c4239feb9897e8d23f3f3c377d78e7903611
53167736a24a9c5400010001
token_type: 3
token_key_id: 125
blinded_msg: 89da551a48270b053e53c9eb741badf89e43cb7e66366bb936e11fb2aa0
d30866986a790378bb9fc6a7cf5c32b7b7584d448ffa4ced3be650e354b3136428a52ec0
b27c4103c5855c2b9b4f521ad0713c800d7e6925b6c62e1a6f58b31d13335f468cf509b7
46a16e79b23862d277d0880706c3fb84b127d94faf8d6d2f3e124e681994441b19be084e
c5c159bcd0abab433bbc308d90ea2cabdf4216e1b07155be66a048d686e383ca1e517ab8
0025bb4849d98beb8c3d05d045c1167cb74f4451d8f85695babb604418385464f21f9a81
5fb850ed83fd16a966130427e5637816501f7a79c0010e06adeba55781ceb50f56eae152
ebd06f3cef80dc7ab121d
request_key: 0161d905e4e37f515cb61f863b60e5896aa9e4a17dbe238e752a144c64a
5412e244f0b1f75e010831e185cac023d33cb20
issuer_encap_key_id:
dd2c6de3091f1873643233d229a7a0e9defe0f9fe43f6a7c42ae3a6b16f77837
encrypted_token_request: 82ef7c068506bcabc27d068a51c7ead2cbaf600b76a15e4
d9df99a0da676da5a073fcc8f5ac77b25064d7379037b4e1b186977cface31eceb611978
c73c9aef38c9a0e8ae846881624fa6d454523a0a91d22b02b022891d0469deebd66a912a
a1ab3391b203e92e0a681f0a10c2a2d59b668daf1e5219ed16227d707fa0e8e29188bd58
7ab38b3584564ce9b6538ba82e301cfed4231a2fa4f64a67285a1b9bf648e25f3eb1644c
88d43552bdea6e4bfcbaef0de3ac245e0432be6b019494927fde0743b775f9efe8ca5fef
afbf2048890d54618d408a6001fc8fb276f6828c46f4fe1381e9775eec72ee47593df738
95d18952440d33756d78caea4bd8218950d35afa6c46c535211eda39da277260cb8dab7c
00c6840a745e8150a6ee4893e72b6a51382f877f8c05a15e891a2bde07049760f0f09879
78d78b97e47ecaf90a44996d724dd3720e308abbbf04f672bc5a4db573291986be191b06
03ff521accb6fa081c151c758f3092a89fc6ef591934ff4bc860896c57f83a31b237dd1b
803516c

B.2. Issuer's Origin Alias Test Vector

The test vector below for the procedure in Section 7 lists the following values:¶

• sk_client: Client Secret, serialized and represented as a hexadecimal string.¶

• pk_client: Client Key, serialized and represented as a hexadecimal string.¶

• sk_origin: Origin Secret, serialized and represented as a hexadecimal string.¶

• request_blind: The request_blind value computed in Section 7.1.1, represented as a hexadecimal string.¶

• index_key: The index_key value computed in Section 7.3, represented as a hexadecimal string.¶

• issuer_origin_alias: The issuer_origin_alias value computed in Section 7.4, represented as a hexadecimal string.¶

sk_sign: f7a8996bfd0d4ef9af88b3eab73d9e05a2d8c557407236aa15e67b4c
8972bc57afb6562f0341dcc5e80fbb71811b9bbe
pk_sign: 032d276595b188b428e954f0cf61bebea9663a7d6678042a54bdb177
8fc88df7f03b83f7e2c15b14147f3487363f9dbd7a
sk_origin: 337d87ad143b414e05e7f764df402b8af14c20c34dc727dca027aa
87a5e1099f3760985813549a451ec42b0d7a377fdf
request_blind: 7444e18d84cad471dc07d8210b714493254776ff897f040feb
6e97a9a5f90f21d940ea7c50f8a5e3d9d8998c45ab7d42
request_key: 02168f9ec10377781d0b16370e7e97b02755741ad0e66e089696
080b4412ce56e933d47c22ff08a5d5da1474aa6b899b0a
index_key: 0284e8d968c696e57194db7b7a37814a1d7c9c2216106530561d07
adc87ff1b6b9c8b911711f5be66c165bbe90c280befb
issuer_origin_alias: ee475b7c158ff52a89ae21e7178ce572124ba6012a58
ba4124f0c691ffe4b40099637964891316264e8442f5f17aa5af