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 base 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.¶

There are several common 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 fraud. Operations that are sensitive to fraud, 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.¶

1.2. 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 (Anonymous Origin ID).¶
• The Issuer knows the Origin's 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 enforces 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.4.¶

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" 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 = 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.¶

Requests to the Attester need to indicate the Issuer Name to which issuance requests will be forwarded. Attesters SHOULD provide Clients with a URI template that contains one variable that contains the Issuer Name, "issuer", using Level 3 URI template encoding as defined in Section 1.2 of [RFC6570].¶

An example of an Attester URI templates is shown below:¶

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

Attesters and Clients MAY agree on other mechanisms to specify the Issuer Name in requests.¶

The Client first creates an issuance request message for a random value nonce using the input TokenChallenge challenge and the Issuer key identifier key_id as follows:¶

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

The Client then uses Client Key to generate its one-time-use request public key request_key and blind request_blind as described in Section 7.1.¶

The Client then encrypts the origin name using Origin Name Key, producing encrypted_origin_name as described in Section 6.¶

Finally, the Client uses Client Secret to produce request_signature as described in Section 7.1.2.¶

The Client then constructs a TokenRequest structure. This TokenRequest structure is based on the publicly verifiable token issuance path in [ISSUANCE], adding fields for the encrypted origin name and request signature.¶

struct {
   uint16_t token_type = 0x0003;
   uint8_t token_key_id;
   uint8_t blinded_msg[Nk];
   uint8_t request_key[49];
   uint8_t name_key_id[32];
   uint8_t encrypted_origin_name<1..2^16-1>;
   uint8_t request_signature[96];
} TokenRequest;

The structure fields are defined as follows:¶

• "token_type" is a 2-octet integer, which matches the type in the challenge.¶
• "token_key_id" is the least significant byte of the Token Key key ID, which is generated as SHA256(public_key), where public_key is a DER-encoded SubjectPublicKeyInfo object carrying Token Key.¶
• "blinded_msg" is the Nk-octet request defined above.¶
• "request_key" is computed as described in Section 7.1.1.¶
• "name_key_id" is a collision-resistant hash that identifies the Origin Name Key, generated as SHA256(NameKey).¶
• "encrypted_origin_name" is an encrypted structure that contains Origin Name, calculated as described in Section 6.¶
• "request_signature" is computed as described in Section 7.1.2.¶

The Client then generates an HTTP POST request to send through the Attester to the Issuer, with the TokenRequest as the body. The media type for this request is "message/token-request". The Client includes the "Sec-Token-Origin" header, whose value is Anonymous Origin ID; the "Sec-Token-Client" header, whose value is Client Key; and the "Sec-Token-Request-Blind" header, whose value is request_blind. The Client sends this request to the Attester's proxy URI. An example request is shown below, where Nk = 512, the Issuer Name is "issuer.net", and the Attester URI template is "https://attester.net/token-request{?issuer}"¶

: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 = Anonymous Origin ID
sec-token-client = Client Key
sec-token-request-blind = request_blind

<Bytes containing the TokenRequest>

If the Attester detects a token_type in the TokenRequest that it does not recognize or support, it MUST reject the request with an HTTP 400 error.¶

The Attester also checks to validate that the name_key_id in the client's TokenRequest matches a known Origin Name Key public key for the Issuer. For example, the Attester can fetch this key using the API defined in Section 3. This check is done to help ensure that the Client has not been given a unique key that could allow the Issuer to fingerprint or target the Client. If the key does not match, the Attester rejects the request with an HTTP 400 error. Note that this can lead to failures in the event of Issuer Origin Name Key rotation; see Section 9 for considerations.¶

The Attester finally validates the Client's stable mapping request as described in Section 7.2. If this fails, the Attester MUST return an HTTP 400 error to the Client.¶

If the Attester accepts the request, it will look up the state stored for this Client. It will look up the count of previously generate tokens for this Client using the same Anonymous Origin ID. See Section 5.1.2 for more details.¶

If the Attester has stored state that a previous request for this Anonymous Origin ID was rejected by the Issuer in the current policy window, it SHOULD reject the request without forwarding it to the Issuer.¶

If the Attester detects this Client has changed their Client Key more frequently than allowed as described in Section 5.1.2, it SHOULD reject the request without forwarding it to the Issuer.¶

5.4. Attester-to-Issuer Request

Assuming all checks in Section 5.3 succeed, the Attester generates an HTTP POST request to send to the Issuer with the Client's TokenRequest as the body. The Attester MUST NOT add information that will uniquely identify a Client, or associate the request with a small set of possible Clients. Extensions to this protocol MAY allow Attesters to add information that can be used to separate large populations, such as providing information about the country or region to which a Client belongs. An example request is shown below.¶

: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>

The Attester and the Issuer MUST use a secure and Issuer-authenticated HTTPS connection. 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.¶

Upon receipt of the forwarded request, the Issuer validates the following conditions:¶

• The TokenRequest contains a supported token_type¶
• The TokenRequest.token_key_id and TokenRequest.name_key_id correspond to known Token Keys and Origin Name Keys held by the Issuer.¶
• The TokenRequest.encrypted_origin_name can be decrypted using the Issuer's private key (the private key associated with Origin Name Key), and matches an Origin Name that is served by the Issuer¶
• The TokenRequest.blinded_msg is of the correct size¶

If any of these conditions is not met, the Issuer MUST return an HTTP 400 error to the Attester, which will forward the error to the client.¶

The Issuer determines the correct Issuer Key by using the decrypted Origin Name value and TokenRequest.token_key_id. If there is no Token Key whose truncated key ID matches TokenRequest.token_key_id, the Issuer MUST return an HTTP 401 error to Attester, which will forward the error to the client. The Attester learns that the client's view of the Origin key was invalid in the process.¶

5.5. Issuer-to-Attester Response

If the Issuer is willing to give a token to the Client, the Issuer decrypts TokenRequest.encrypted_origin_name to discover "origin". If this fails, the Issuer rejects the request with a 400 error. Otherwise, the Issuer validates and processes the token request with Issuer Origin Secret corresponding to the designated Origin as described in Section 7.3. If this fails, the Issuer rejects the request with a 400 error. Otherwise, the output is index_result.¶

The Issuer completes the issuance flow by computing a blinded response as follows:¶

blind_sig = rsabssa_blind_sign(skP, TokenRequest.blinded_msg)

skP is the private key corresponding to Token Key, known only to the Issuer.¶

The Issuer generates an HTTP response with status code 200 whose body consists of blind_sig, with the content type set as "message/token-response", the index_result set in the "Sec-Token-Origin" header, and the limit of tokens allowed for a Client for the Origin within a policy window set in the "Sec-Token-Limit" header.¶

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

<Bytes containing the blind_sig>

5.6. Attester-to-Client Response

Upon receipt of a successful response from the Issuer, the Attester extracts the "Sec-Token-Origin" header, and uses the value to determine Anonymous Issuer Origin ID as described in Section 7.4.¶

If the "Sec-Token-Origin" is missing, or if the same Anonymous Issuer Origin ID was previously received in a response for a different Anonymous Origin ID within the same policy window, the Attester MUST drop the token and respond to the client with an HTTP 400 status. If there is not an error, the Anonymous Issuer Origin ID is stored alongside the state for the Anonymous Origin ID.¶

The Attester also extracts the "Sec-Token-Limit" header, and compares the limit against the previous count of accesses for this Client for the Anonymous Origin ID. If the count is greater than or equal to the limit, the Attester drops the token and responds to the client with an HTTP 429 (Too Many Requests) error.¶

For all other cases, the Attester forwards all HTTP responses unmodified to the Client as the response to the original request for this issuance.¶

When the Attester detects successful token issuance, it MUST increment the counter in its state for the number of tokens issued to the Client for the Anonymous Origin ID.¶

Upon receipt, the Client handles the response and, if successful, processes the body as follows:¶

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

If this succeeds, the Client then constructs a token as described in [AUTHSCHEME] as follows:¶

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;

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 = ECDSA-KeyGen()
blinded_key = ECDSA-BlindPublicKey(pk_sign, sk_blind)
request_key = ECDSA-SerializePublicKey(blinded_key)
request_blind = ECDSA-SerializePrivatekey(sk_blind)

context = concat(0x0003, // token_type
                 token_key_id,
                 blinded_msg,
                 request_key,
                 name_key_id,
                 encrypted_origin_name)
request_signature = ECDSA-BlindKeySign(sk_sign, sk_blind, context)

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 ECDSA public key. If this fails, abort.¶
2. Check that request_blind is a valid ECDSA 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 = ECDSA-DeserializePublicKey(request_key)
sk_blind = ECDSA-DeserializePrivatekey(request_blind)
pk_blind = ECDSA-BlindPublicKey(pk_sign, sk_blind)
if pk_blind != blind_key:
  raise InvalidParameterError

context = parse(request[..len(request)-96]) // this matches context computed during signing
valid = ECDSA-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 ECDSA 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 = ECDSA-DeserializePublicKey(request_key)
context = parse(request[..len(request)-96]) // this matches context computed during signing
valid = ECDSA-Verify(blind_key, context, request_signature)
if not valid:
  raise InvalidSignatureError

evaluated_key = ECDSA-BlindPublicKey(request_key, sk_origin)
index_key = ECDSA-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 Anonymous Issuer Origin ID computation as follows:¶

1. Check that index_key is a valid ECDSA 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 SHA-384 using the index result as the secret, Client Key pk_sign as the salt, and ASCII string "anon_issuer_origin_id" as the info string, yielding Anonymous Issuer Origin ID.¶

In pseudocode, this is as follows:¶

evaluated_key = ECDSA-DeserializePublicKey(request_key)
unblinded_key = ECDSA-UnblindPublicKey(evaluated_key, sk_blind)

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

anon_issuer_origin_id = HKDF-SHA384(secret=index_result,
                                    salt=pk_encoded,
                                    info="anon_issuer_origin_id")

8.1. 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.2. 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, Attesters learn only the Anonymous Issuer Origin ID 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 learn the origin name associated with a given token request.¶

The Issuer only learns the Attester that vouches for a particular Client's token request and the origin name associated with a token request. The Issuer does not learn the Anonymous Issuer Origin ID or any per-Client information used when creating a token request.¶

The Client learns the output token. It does not learn the Anonymous Issuer Origin ID.¶

8.3. 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.¶

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 origin_name presented in the TokenChallenge structure ([AUTHSCHEME]) matches the origin that is providing the HTTP authentication challenge, 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 Keys

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

To mitigate the risk of a targeted Origin Name Key, the Attester can observe and validate the token_key_id presented by the Client to the Issuer. As described in Section 5, Attesters MUST validate that the token_key_id in the Client's TokenRequest matches a known 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. 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 a new (Token Key, Issuer Origin Secret) 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:¶

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        |   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 |
    +-------------------------+----------+--------+---------------+