Skip to main content

Rate-Limited Token Issuance Protocol
draft-privacypass-rate-limit-tokens-01

The information below is for an old version of the document.
Document Type Active Internet-Draft (individual)
Authors Scott Hendrickson , Jana Iyengar , Tommy Pauly , Steven Valdez , Christopher A. Wood
Last updated 2022-04-05
Stream (None)
Formats plain text html xml htmlized pdfized bibtex
Stream Stream state (No stream defined)
Consensus boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-privacypass-rate-limit-tokens-01
Network Working Group                                     S. Hendrickson
Internet-Draft                                                Google LLC
Intended status: Informational                                J. Iyengar
Expires: 7 October 2022                                           Fastly
                                                                T. Pauly
                                                              Apple Inc.
                                                               S. Valdez
                                                              Google LLC
                                                              C. A. Wood
                                                              Cloudflare
                                                            5 April 2022

                  Rate-Limited Token Issuance Protocol
                 draft-privacypass-rate-limit-tokens-01

Abstract

   This document specifies a variant of the Privacy Pass issuance
   protocol that allows for tokens to be rate-limited on a per-origin
   basis.  This enables origins to use tokens for use cases that need to
   restrict access from anonymous clients.

Discussion Venues

   This note is to be removed before publishing as an RFC.

   Source for this draft and an issue tracker can be found at
   https://github.com/tfpauly/privacy-proxy.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on 7 October 2022.

Hendrickson, et al.      Expires 7 October 2022                 [Page 1]
Internet-Draft             Rate-Limited Tokens                April 2022

Copyright Notice

   Copyright (c) 2022 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.  Code Components
   extracted from this document must include Revised BSD License text as
   described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Revised BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  Motivation  . . . . . . . . . . . . . . . . . . . . . . .   3
     1.2.  Properties and Requirements . . . . . . . . . . . . . . .   4
   2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .   6
   3.  Configuration . . . . . . . . . . . . . . . . . . . . . . . .   8
   4.  Token Challenge Requirements  . . . . . . . . . . . . . . . .   9
   5.  Issuance Protocol . . . . . . . . . . . . . . . . . . . . . .  10
     5.1.  State Requirements  . . . . . . . . . . . . . . . . . . .  10
       5.1.1.  Client State  . . . . . . . . . . . . . . . . . . . .  11
       5.1.2.  Attester State  . . . . . . . . . . . . . . . . . . .  12
       5.1.3.  Issuer State  . . . . . . . . . . . . . . . . . . . .  12
     5.2.  Issuance HTTP Headers . . . . . . . . . . . . . . . . . .  13
     5.3.  Client-to-Attester Request  . . . . . . . . . . . . . . .  13
     5.4.  Attester-to-Issuer Request  . . . . . . . . . . . . . . .  16
     5.5.  Issuer-to-Attester Response . . . . . . . . . . . . . . .  18
     5.6.  Attester-to-Client Response . . . . . . . . . . . . . . .  18
   6.  Encrypting Origin Names . . . . . . . . . . . . . . . . . . .  19
   7.  Anonymous Issuer Origin ID Computation  . . . . . . . . . . .  21
     7.1.  Client Behavior . . . . . . . . . . . . . . . . . . . . .  23
       7.1.1.  Request Key . . . . . . . . . . . . . . . . . . . . .  23
       7.1.2.  Request Signature . . . . . . . . . . . . . . . . . .  23
     7.2.  Attester Behavior (Client Request Validation) . . . . . .  24
     7.3.  Issuer Behavior . . . . . . . . . . . . . . . . . . . . .  25
     7.4.  Attester Behavior (Index Computation) . . . . . . . . . .  25
   8.  Security Considerations . . . . . . . . . . . . . . . . . . .  26
     8.1.  Channel Security  . . . . . . . . . . . . . . . . . . . .  26
     8.2.  Token Request Unlinkability and Unforgeability  . . . . .  26
     8.3.  Information Disclosure  . . . . . . . . . . . . . . . . .  27
   9.  Privacy Considerations  . . . . . . . . . . . . . . . . . . .  28
     9.1.  Client Token State and Origin Tracking  . . . . . . . . .  28
     9.2.  Origin Verification . . . . . . . . . . . . . . . . . . .  29
     9.3.  Client Identification with Unique Keys  . . . . . . . . .  29

Hendrickson, et al.      Expires 7 October 2022                 [Page 2]
Internet-Draft             Rate-Limited Tokens                April 2022

     9.4.  Origin Identification . . . . . . . . . . . . . . . . . .  29
     9.5.  Collusion Among Different Entities  . . . . . . . . . . .  30
   10. Deployment Considerations . . . . . . . . . . . . . . . . . .  30
     10.1.  Token Key Management . . . . . . . . . . . . . . . . . .  30
   11. IANA considerations . . . . . . . . . . . . . . . . . . . . .  30
     11.1.  Token Type . . . . . . . . . . . . . . . . . . . . . . .  31
     11.2.  HTTP Headers . . . . . . . . . . . . . . . . . . . . . .  31
   12. References  . . . . . . . . . . . . . . . . . . . . . . . . .  31
     12.1.  Normative References . . . . . . . . . . . . . . . . . .  31
     12.2.  Informative References . . . . . . . . . . . . . . . . .  33
   Appendix A.  Acknowledgements . . . . . . . . . . . . . . . . . .  34
   Appendix B.  Test Vectors . . . . . . . . . . . . . . . . . . . .  34
     B.1.  Origin Name Encryption Test Vector  . . . . . . . . . . .  34
     B.2.  Anonymous Origin ID Test Vector . . . . . . . . . . . . .  35
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  36

1.  Introduction

   This document specifies a variant of the Privacy Pass issuance
   protocol (as defined in [ARCH]) that allows for tokens to be rate-
   limited on a per-origin basis.  This enables origins to use tokens
   for use cases that need to restrict access from anonymous clients.

   The base Privacy Pass issuance protocol [ISSUANCE] defines stateless
   anonymous tokens, which can either be publicly verifiable or not.

   This variant build upon the publicly verifiable issuance protocol
   that uses RSA Blind Signatures [BLINDSIG], and allows tokens to be
   rate-limited on a per-origin basis.  This means that a client will
   only be able to receive a limited number of tokens associated with a
   given origin server within a fixed period of time.

   This issuance protocol registers the Rate-Limited Blind RSA token
   type (Section 11.1), to be used with the PrivateToken HTTP
   authentication scheme defined in [AUTHSCHEME].

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.

Hendrickson, et al.      Expires 7 October 2022                 [Page 3]
Internet-Draft             Rate-Limited Tokens                April 2022

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

   For some applications, the basic issuance protocol from
   [BASIC-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 participating client.
   In some cases this might be a significant portion of browsing
   history.  The issuance protocol defined in this document employs the
   'Split Origin, Attester, Issuer' model to combat this, where the
   issuer would know all per-origin policies, and the attester would
   mantain per-client state without knowing all origins a client visits.

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

Hendrickson, et al.      Expires 7 October 2022                 [Page 4]
Internet-Draft             Rate-Limited Tokens                April 2022

      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.

Hendrickson, et al.      Expires 7 October 2022                 [Page 5]
Internet-Draft             Rate-Limited Tokens                April 2022

   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.5.

2.  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "OPTIONAL" in this document are to be interpreted as described in
   BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
   capitals, as shown here.

   Unless otherwise specified, this document encodes protocol messages
   in TLS notation from [TLS13], Section 3.

   This draft includes pseudocode that uses the functions and
   conventions defined in [HPKE].

   Encoding an integer to a sequence of bytes in network byte order is
   described using the function "encode(n, v)", where "n" is the number
   of bytes and "v" is the integer value.  The function "len()" returns
   the length of a sequence of bytes.

   The following terms are defined in [ARCH] and are used throughout
   this document:

   *  Client: An entity that provides authorization tokens to services
      across the Internet, in return for authorization.

   *  Issuer: An entity that produces Privacy Pass tokens to clients.

   *  Attester: An entity that can attest to properties about the
      client, including previous patterns of access.

   *  Origin: The server from which the client can redeem tokens.

   *  Issuance Protocol: The protocol exchange that involves the client,
      attester, and issuer, used to generate tokens.

Hendrickson, et al.      Expires 7 October 2022                 [Page 6]
Internet-Draft             Rate-Limited Tokens                April 2022

   The following terms are defined in [AUTHSCHEME], which defines the
   interactions between clients and origins:

   *  Issuer Name: The name that identifies the Issuer, which is an
      entity that can generate tokens for a Client using one or more
      issuance protocols.

   *  Token Key: Keying material that can be used with an issuance
      protocol to create a signed token.

   *  Origin Name: The name that identifies the Origin, as included in a
      TokenChallenge.

   Additionally, this document defines several terms that are unique to
   the rate-limited issuance protocol:

   *  Issuer Policy Window: The period over which an Issuer will track
      access policy, defined in terms of seconds and represented as a
      uint64.  The state that the Attester keeps for a Client is
      specific to a policy window.  The effective policy window for a
      specific Client starts when the Client first sends a request
      associated with an Issuer.

   *  Origin Name Key: The public key used to encrypt values such as
      Origin Name in requests from Clients to the Issuer, so that
      Attesters cannot learn the Origin Name value.  Each Origin Name
      Key is used across all requests on the Issuer, for different
      Origins.

   *  Anonymous Origin ID: An identifier that is generated by the Client
      and marked on requests to the Attester, which represents a
      specific Origin anonymously.  The Client generates a stable
      Anonymous Origin ID for each Origin Name, to allow the Attester to
      count token access without learning the Origin Name.

   *  Client Key: A public key chosen by the Client and shared only with
      the Attester; see Section 8.2 for more details about this
      restriction.

   *  Client Secret: The secret key used by the Client during token
      issuance, whose public key (Client Key) is shared with the
      Attester.

   *  Issuer Origin Secret: A per-origin secret key used by the Issuer
      during token issuance, whose public key is not shared with anyone.

Hendrickson, et al.      Expires 7 October 2022                 [Page 7]
Internet-Draft             Rate-Limited Tokens                April 2022

   *  Anonymous Issuer Origin ID: An identifier that is generated by
      Issuer based on an Issuer Origin Secret that is per-Client and
      per-Origin.  See Section 5.6 for details of derivation.

3.  Configuration

   Issuers MUST provide three parameters for configuration:

   1.  Issuer Policy Window: a uint64 of seconds as defined in
       Section 2.

   2.  Issuer Request URI: a token request URL for generating access
       tokens.  For example, an Issuer URL might be
       https://issuer.example.net/token-request.  This parameter uses
       resource media type "text/plain".

   3.  Origin Name Key: a NameKey structure as defined below to use when
       encrypting the Origin Name in issuance requests.  This parameter
       uses resource media type "application/issuer-name-key".  The Npk
       parameter corresponding to the HpkeKdfId can be found in [HPKE].

   opaque HpkePublicKey[Npk]; // defined in RFC9180
   uint16 HpkeKemId;          // defined in RFC9180
   uint16 HpkeKdfId;          // defined in RFC9180
   uint16 HpkeAeadId;         // defined in RFC9180

   struct {
     uint8 key_id;
     HpkeKemId kem_id;
     HpkePublicKey public_key;
     HpkeKdfId kdf_id;
     HpkeAeadId aead_id;
   } NameKey;

   The Issuer parameters can be obtained from an Issuer via a directory
   object, which is a JSON object whose field names and values are raw
   values and URLs for the parameters.

Hendrickson, et al.      Expires 7 October 2022                 [Page 8]
Internet-Draft             Rate-Limited Tokens                April 2022

     +======================+=======================================+
     | Field Name           | Value                                 |
     +======================+=======================================+
     | issuer-policy-window | Issuer Policy Window as a JSON number |
     +----------------------+---------------------------------------+
     | issuer-request-uri   | Issuer Request URI resource URL as a  |
     |                      | JSON string                           |
     +----------------------+---------------------------------------+
     | origin-name-key-uri  | Origin Name Key URI resource URL as a |
     |                      | JSON string                           |
     +----------------------+---------------------------------------+

                                 Table 1

   As an example, the Issuer's JSON directory could look like:

    {
       "issuer-token-window": 86400,
       "issuer-request-uri": "https://issuer.example.net/token-request"
       "origin-name-key-uri": "https://issuer.example.net/name-key",
    }

   Issuer directory resources have the media type "application/json" and
   are located at the well-known location /.well-known/token-issuer-
   directory.

4.  Token Challenge Requirements

   Clients receive challenges for tokens, as described in [AUTHSCHEME].

   For the rate-limited token issuance protocol described in this
   document, the name of the origin is sent in an encrypted message from
   the Client to the Issuer.  If the TokenChallenge.origin_info field
   contains a single origin name, that origin name is used.  If the
   origin_info field contains multiple origin names, the client selects
   the single origin name that presented the challenge.  If the
   origin_info field is empty, the encrypted message is the empty string
   "".

   The HTTP authentication challenge also SHOULD contain the following
   additional attribute:

   *  "origin-name-key", which contains a base64url encoding of a
      NameKey as defined in Section 3 to use when encrypting the Origin
      Name in issuance requests.

Hendrickson, et al.      Expires 7 October 2022                 [Page 9]
Internet-Draft             Rate-Limited Tokens                April 2022

5.  Issuance Protocol

   This section describes the Issuance protocol for a Client to request
   and receive a token from an Issuer.  Token issuance involves a
   Client, Attester, and Issuer, with the following steps:

   1.  The Client sends a token request containing a token request,
       encrypted origin name, and one-time-use public key and signature
       to the Attester

   2.  The Attester validates the request contents, specifically
       checking the request signature, and proxies the request to the
       Issuer

   3.  The Issuer validates the request against the signature, and
       processes its contents, and produces a token response sent back
       to the Attester

   4.  The Attester verifies the response and proxies the response to
       the Client

   The Issuance protocol is designed such that Client, Attester, and
   Issuer learn only what is necessary for completing the protocol; see
   Section 8.3 for more details.

   The Issuance protocol has a number of underlying cryptographic
   dependencies for operation:

   *  RSA Blind Signatures [BLINDSIG], for issuing and constructing
      Tokens.  This support is the same as used in the base publicly
      verifiable token issuance protocol [ISSUANCE]

   *  [HPKE], for encrypting the origin server name in transit between
      Client and Issuer across the Attester.

   *  [ECDSA] signatures with key blinding, as described in
      [KEYBLINDING], for verifying correctness of Client requests.

   Clients and Issuers are required to implement all of these
   dependencies, whereas Attesters are required to implement ECDSA
   signature with key blinding support.

5.1.  State Requirements

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

Hendrickson, et al.      Expires 7 October 2022                [Page 10]
Internet-Draft             Rate-Limited Tokens                April 2022

5.1.1.  Client State

   A Client is required to have the following information, derived from
   a given TokenChallenge:

   *  Origin Name, a hostname referring to the Origin [RFC6454].  This
      is the name of the Origin that issued the token challenge.  One or
      more names can be listed in the TokenChallenge.origin_info field.
      Rate-limited token issuance relies on the client selecting a
      single origin name from this list if multiple are present.

   *  Token Key, a blind signature public key corresponding to the
      Issuer identified by the TokenChallenge.issuer_name.

   *  Origin Name Key, a public key used to encrypt request information
      corresponding to the Issuer identified by
      TokenChallenge.issuer_name.

   Clients maintain a stable Client Key that they use for all
   communication with a specific Attester.  Client Key is a public key,
   where the corresponding private key Client Secret is known only to
   the client.

   If the client loses this (Client Key, Client Secret), they may
   generate a new tuple.  The Attester will enforce if a client is
   allowed to use this new Client Key. See Section 5.1.2 for details on
   this enforcement.

   Clients also need to be able to generate an Anonymous Origin ID value
   that corresponds to the Origin Name, to send in requests to the
   Attester.

   Anonymous Origin ID MUST be a stable and unpredictable 32-byte value
   computed by the Client.  Clients MUST NOT change this value across
   token requests for the same Origin Name.  Doing so will result in
   token issuance failure (specifically, when an Attester rejects a
   request upon detecting two Anonymous Origin ID values that map to the
   same Origin).

   One possible mechanism for implementing this identifier is for the
   Client to store a mapping between the Origin Name and a randomly
   generated Anonymous Origin ID for future requests.  Alternatively,
   the Client can compute a PRF keyed by a per-client secret (Client
   Secret) over the Origin Name, e.g., Anonymous Origin ID =
   HKDF(secret=Client Secret, salt="", info=Origin Name).

Hendrickson, et al.      Expires 7 October 2022                [Page 11]
Internet-Draft             Rate-Limited Tokens                April 2022

5.1.2.  Attester State

   An Attester is required to maintain state for every authenticated
   Client.  The mechanism of identifying a Client is specific to each
   Attester, and is not defined in this document.  As examples, the
   Attester could use device-specific certificates or account
   authentication to identify a Client.

   Attesters must enforce that Clients don't change their Client Key
   frequently, to ensure Clients can't regularily evade the per-client
   policy as seen by the issuer.  Attesters MUST NOT allow Clients to
   change their Client Key more than once within a policy window, or in
   the subsequent policy window after a previous Client Key change.
   Alternative schemes where the Attester stores the encrypted (Client
   Key, Client Secret) tuple on behalf of the client are possble but not
   described here.

   Attesters are expected to know the Issuer Policy Window for any
   Issuer Name to which they allow access.  This information can be
   retrieved using the URIs defined in Section 3.

   For each Client-Issuer pair, an Attester maintains a policy window
   start and end time for each Issuer from which a Client requests a
   token.

   For each tuple of (Client Key, Anonymous Origin ID, policy window),
   the Attester maintains the following state:

   *  A counter of successful tokens issued

   *  Whether or not a previous request was rejected by the Issuer

   *  The last received Anonymous Issuer Origin ID value for this
      Anonymous Origin ID, if any

5.1.3.  Issuer State

   Issuers maintain a stable Issuer Origin Secret that they use in
   calculating values returned to the Attester for each origin.  If this
   value changes, it will open up a possibility for Clients to request
   extra tokens for an Origin without being limited, within a policy
   window.  See Section 10.1 for details about generating and rotating
   the Issuer Origin Secret.

   Issuers are expected to have the private key that corresponds to
   Origin Name Key, which allows them to decrypt the Origin Name values
   in requests.

Hendrickson, et al.      Expires 7 October 2022                [Page 12]
Internet-Draft             Rate-Limited Tokens                April 2022

   Issuers also need to know the set of valid Token Key public keys and
   corresponding private key, for each Origin Name that is served by the
   Issuer.  Origins SHOULD update their view of the Token Key regularly
   to ensure that Client requests do not fail after Token Key rotation.

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.

Hendrickson, et al.      Expires 7 October 2022                [Page 13]
Internet-Draft             Rate-Limited Tokens                April 2022

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

Hendrickson, et al.      Expires 7 October 2022                [Page 14]
Internet-Draft             Rate-Limited Tokens                April 2022

   *  "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.

   *  "origin_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.

Hendrickson, et al.      Expires 7 October 2022                [Page 15]
Internet-Draft             Rate-Limited Tokens                April 2022

   The Attester also checks to validate that the origin_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.

Hendrickson, et al.      Expires 7 October 2022                [Page 16]
Internet-Draft             Rate-Limited Tokens                April 2022

   :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.origin_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.
      This name might be the empty string "", as described in Section 6,
      in which case the Issuer applies a cross-origin policy if
      supported.  If a cross-origin policy is not supported, this
      condition is not met.

   *  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.

Hendrickson, et al.      Expires 7 October 2022                [Page 17]
Internet-Draft             Rate-Limited Tokens                April 2022

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_key.

   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_key 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.  This limit SHOULD
   NOT be unique to a specific Origin, such that the Attester could use
   the value to infer which Origin the Client is accessing (see
   Section 9).

   :status = 200
   content-type = message/token-response
   content-length = <Length of blind_sig>
   sec-token-origin = index_key
   sec-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.

Hendrickson, et al.      Expires 7 October 2022                [Page 18]
Internet-Draft             Rate-Limited Tokens                April 2022

   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;

6.  Encrypting Origin Names

   Given a NameKey (Origin Name Key), Clients produce
   encrypted_origin_name and authenticate the contents of the
   TokenRequest 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, and origin_name_key_id.

Hendrickson, et al.      Expires 7 October 2022                [Page 19]
Internet-Draft             Rate-Limited Tokens                April 2022

   Together, these are used to encapsulate Origin Name (origin_name) and
   produce Encrypted Origin Name (encrypted_origin).

   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_origin from origin_name 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.  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_origin_name.

   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, "TokenRequest")
   aad = concat(encode(1, keyID),
                encode(2, kemID),
                encode(2, kdfID),
                encode(2, aeadID),
                encode(2, token_type),
                encode(1, token_key_id),
                encode(Nk, blinded_msg),
                encode(49, request_key),
                encode(32, origin_name_key_id))
   ct = context.Seal(aad, pad(origin_name))
   encrypted_origin_name = concat(enc, ct)

Hendrickson, et al.      Expires 7 October 2022                [Page 20]
Internet-Draft             Rate-Limited Tokens                April 2022

   Issuers reverse this procedure to recover the (padded) Origin Name by
   computing the AAD as described above and decrypting
   encrypted_origin_name with their private key skI (the private key
   corresponding to pkI), and stripping off padding bytes.  In
   pseudocode, this procedure is as follows:

   enc, ct = parse(encrypted_origin_name)
   aad = concat(encode(1, keyID),
                encode(2, kemID),
                encode(2, kdfID),
                encode(2, aeadID),
                encode(2, token_type),
                encode(1, token_key_id),
                encode(Nk, blinded_msg),
                encode(49, request_key),
                encode(32, origin_name_key_id))
   enc, context = SetupBaseR(enc, skI, "TokenRequest")
   origin_name, error = context.Open(aad, ct)

   The resulting value of origin_name is used by the Issuer to determine
   which rate-limit values to send to the Attester for enforcement.  If
   the decrypted origin_name is the empty string "", the Issuer applies
   a cross-origin rate-limit policy, if supported.  If the decrypted
   origin_name is the empty string "" and the Issuer does not support
   cross-origin rate limiting, then it MUST abort the protocol as
   described in Section 5.4.

7.  Anonymous Issuer Origin ID Computation

   This section describes the Client, Attester, and Issuer behavior in
   computing Anonymous Issuer Origin ID, the stable mapping based on
   client identity and origin name.  At a high level, this functionality
   computes y = F(x, k), where x is a per-Client secret and k is a per-
   Origin secret, subject to the following constraints:

   *  The Attester only learns y if the Client in possession of x
      engages with the protocol;

   *  The Attester prevents a Client with private input x from running
      the protocol for input x' that is not equal to x;

   *  The Issuer does not learn x, nor does it learn when two requests
      correspond to the same private value x; and

   *  Neither the Client nor Attester learn k.

   The interaction between Client, Attester, and Issuer in computing
   this functionality is shown below.

Hendrickson, et al.      Expires 7 October 2022                [Page 21]
Internet-Draft             Rate-Limited Tokens                April 2022

   Client               Attester                Issuer
       (request, signature)
     ---------------------->
                              (request, signature)
                            ---------------------->
                                   (response)
                            <----------------------

   The protocol for computing this functionality is divided into
   sections for each of the participants.  Section 7.1 describes Client
   behavior for initiating the computation with its per-Client secret,
   Section 7.2 describes Attester behavior for verifying Client
   requests, Section 7.3 describes Issuer behavior for computing the
   mapping with its per-Origin secret, and Section 7.4 describes the
   final Attester step for computing the client-origin index.

   The index computation is based on ECDSA [ECDSA] instantiated with
   P-384 and SHA-384 and extended with key blinding support as described
   in [KEYBLINDING].  It uses the following functions:

   *  ECDSA-KeyGen(): Generate a random ECDSA private and public key
      pair (sk, pk).

   *  ECDSA-BlindPublicKey(pk, r): Produce a blinded public key based on
      the input public key pk and blind r according to [KEYBLINDING],
      Section 6.1.

   *  ECDSA-Verify(pk, msg, sig): Verify the DER-encoded [X690] ECDSA-
      Sig-Value signature sig over input message msg against the ECDSA
      public key pk, producing a boolean value indicating success.

   *  ECDSA-BlindKeySign(sk_sign, sk_blind, msg): Sign input message msg
      with signing key sk_sign and blind sk_blind according to
      [KEYBLINDING], Section 6.2, and serializes the resulting signature
      pair (r, s) in "raw" form, i.e., as the concatenation of two
      48-byte, big endian scalars.

   *  ECDSA-SerializePrivatekey(sk): Serialize an ECDSA private key
      using the Field-Element-to-Octet-String conversion according to
      [SECG].

   *  ECDSA-DeserializePrivatekey(buf): Attempt to deserialize an ECDSA
      private key from a 48-byte string buf using Octet-String-to-Field-
      Element from [SECG].  This function can fail if buf does not
      represent a valid private key.

Hendrickson, et al.      Expires 7 October 2022                [Page 22]
Internet-Draft             Rate-Limited Tokens                April 2022

   *  ECDSA-SerializePublicKey(pk): Serialize an ECDSA public key using
      the compressed Elliptic-Curve-Point-to-Octet-String method
      according to [SECG].

   *  ECDSA-DeserializePublicKey(buf): Attempt to deserialize a public
      key using the compressed Octet-String-to-Elliptic-Curve-Point
      method according to [SECG], and then performs partial public-key
      validation as defined in section 5.6.2.3.4 of [KEYAGREEMENT].
      This validation includes checking that the coordinates are in the
      correct range, that the point is on the curve, and that the point
      is not the point at infinity.

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.

7.1.1.  Request Key

   Clients produce request_key by masking Client Key and Client Secret
   with a randomly chosen blind.  Let pk_sign and sk_sign denote Client
   Key and Client Secret, respectively.  This process is done as
   follows:

   1.  Generate a random ECDSA private key, sk_blind.

   2.  Blind pk_sign with sk_blind to compute a blinded public key,
       request_key.

   3.  Output the blinded public key.

   In pseudocode, this is as follows:

   sk_blind = ECDSA-KeyGen()
   blinded_key = ECDSA-BlindPublicKey(pk_sign, sk_blind)
   request_key = ECDSA-SerializePublicKey(blinded_key)
   request_blind = ECDSA-SerializePrivatekey(sk_blind)

7.1.2.  Request Signature

   Clients produce signature of their request based on the following
   inputs defined in Section 5.3: token_key_id, blinded_msg,
   request_key, name_key_id, encrypted_origin_name.  This process
   requires the blind value sk_blind produced during the Section 7.1.1
   process.  As above, let pk and sk denote Client Key and Client
   Secret, respectively.  Given these values, this signature process

Hendrickson, et al.      Expires 7 October 2022                [Page 23]
Internet-Draft             Rate-Limited Tokens                April 2022

   works as follows:

   1.  Concatenate all signature inputs to yield a message to sign.

   2.  Compute an ECDSA signature with the blind sk_blind over the input
       message using Client Secret, sk_sign as the signing key.

   3.  Output the signature.

   In pseudocode, this is as follows:

   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:

Hendrickson, et al.      Expires 7 October 2022                [Page 24]
Internet-Draft             Rate-Limited Tokens                April 2022

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.

Hendrickson, et al.      Expires 7 October 2022                [Page 25]
Internet-Draft             Rate-Limited Tokens                April 2022

   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(index_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.  Security Considerations

   This section describes security considerations relevant to the use of
   this protocol.

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

Hendrickson, et al.      Expires 7 October 2022                [Page 26]
Internet-Draft             Rate-Limited Tokens                April 2022

   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.3.  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 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
   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.2.

Hendrickson, et al.      Expires 7 October 2022                [Page 27]
Internet-Draft             Rate-Limited Tokens                April 2022

   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 Anonymous Issuer Origin ID
   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 Anonymous
   Issuer Origin ID, 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.

9.  Privacy Considerations

   This section describes privacy considerations relevant to use of this
   protocol.

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.

Hendrickson, et al.      Expires 7 October 2022                [Page 28]
Internet-Draft             Rate-Limited Tokens                April 2022

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 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.  Origin Identification

   As stated in Section 1.2, 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.

Hendrickson, et al.      Expires 7 October 2022                [Page 29]
Internet-Draft             Rate-Limited Tokens                April 2022

   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.5.  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.  Deployment Considerations

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.  IANA considerations

Hendrickson, et al.      Expires 7 October 2022                [Page 30]
Internet-Draft             Rate-Limited Tokens                April 2022

11.1.  Token Type

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

   +======+=============+==========+========+========+===+===+=========+
   |Value |Name         |Publicly  |Public  |Private |Nk |Nid|Reference|
   |      |             |Verifiable|Metadata|Metadata|   |   |         |
   +======+=============+==========+========+========+===+===+=========+
   |0x0003|Rate-Limited |Y         |N       |N       |512|32 |This     |
   |      |Blind RSA    |          |        |        |   |   |document |
   +------+-------------+----------+--------+--------+---+---+---------+

                            Table 2: Token Types

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

                      Figure 1: Registered HTTP Header

12.  References

12.1.  Normative References

   [ARCH]     Davidson, A., Iyengar, J., and C. A. Wood, "Privacy Pass
              Architectural Framework", Work in Progress, Internet-
              Draft, draft-ietf-privacypass-architecture-03, 7 March
              2022, <https://datatracker.ietf.org/doc/html/draft-ietf-
              privacypass-architecture-03>.

   [AUTHSCHEME]
              Pauly, T., Valdez, S., and C. A. Wood, "The Privacy Pass
              HTTP Authentication Scheme", Work in Progress, Internet-

Hendrickson, et al.      Expires 7 October 2022                [Page 31]
Internet-Draft             Rate-Limited Tokens                April 2022

              Draft, draft-ietf-privacypass-auth-scheme-02, 4 April
              2022, <https://datatracker.ietf.org/doc/html/draft-ietf-
              privacypass-auth-scheme-02>.

   [BLINDSIG] Denis, F., Jacobs, F., and C. A. Wood, "RSA Blind
              Signatures", Work in Progress, Internet-Draft, draft-irtf-
              cfrg-rsa-blind-signatures-03, 2 February 2022,
              <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-
              rsa-blind-signatures-03>.

   [ECDSA]    American National Standards Institute, "Public Key
              Cryptography for the Financial Services Industry - The
              Elliptic Curve Digital Signature Algorithm (ECDSA)",
              ANSI ANS X9.62-2005, November 2005.

   [HPKE]     Barnes, R., Bhargavan, K., Lipp, B., and C. Wood, "Hybrid
              Public Key Encryption", RFC 9180, DOI 10.17487/RFC9180,
              February 2022, <https://www.rfc-editor.org/rfc/rfc9180>.

   [ISSUANCE] Celi, S., Davidson, A., Faz-Hernandez, A., Valdez, S., and
              C. A. Wood, "Privacy Pass Issuance Protocol", Work in
              Progress, Internet-Draft, draft-ietf-privacypass-protocol-
              04, 5 April 2022, <https://datatracker.ietf.org/doc/html/
              draft-ietf-privacypass-protocol-04>.

   [KEYAGREEMENT]
              Barker, E., Chen, L., Roginsky, A., Vassilev, A., and R.
              Davis, "Recommendation for pair-wise key-establishment
              schemes using discrete logarithm cryptography", National
              Institute of Standards and Technology report,
              DOI 10.6028/nist.sp.800-56ar3, April 2018,
              <https://doi.org/10.6028/nist.sp.800-56ar3>.

   [KEYBLINDING]
              Denis, F., Eaton, E., and C. A. Wood, "Key Blinding for
              Signature Schemes", Work in Progress, Internet-Draft,
              draft-dew-cfrg-signature-key-blinding-01, 7 March 2022,
              <https://datatracker.ietf.org/doc/html/draft-dew-cfrg-
              signature-key-blinding-01>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/rfc/rfc2119>.

Hendrickson, et al.      Expires 7 October 2022                [Page 32]
Internet-Draft             Rate-Limited Tokens                April 2022

   [RFC5869]  Krawczyk, H. and P. Eronen, "HMAC-based Extract-and-Expand
              Key Derivation Function (HKDF)", RFC 5869,
              DOI 10.17487/RFC5869, May 2010,
              <https://www.rfc-editor.org/rfc/rfc5869>.

   [RFC6454]  Barth, A., "The Web Origin Concept", RFC 6454,
              DOI 10.17487/RFC6454, December 2011,
              <https://www.rfc-editor.org/rfc/rfc6454>.

   [RFC6570]  Gregorio, J., Fielding, R., Hadley, M., Nottingham, M.,
              and D. Orchard, "URI Template", RFC 6570,
              DOI 10.17487/RFC6570, March 2012,
              <https://www.rfc-editor.org/rfc/rfc6570>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

   [RFC8941]  Nottingham, M. and P-H. Kamp, "Structured Field Values for
              HTTP", RFC 8941, DOI 10.17487/RFC8941, February 2021,
              <https://www.rfc-editor.org/rfc/rfc8941>.

   [SECG]     "Elliptic Curve Cryptography, Standards for Efficient
              Cryptography Group, ver. 2", 2009,
              <https://secg.org/sec1-v2.pdf>.

   [TLS13]    Rescorla, E., "The Transport Layer Security (TLS) Protocol
              Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
              <https://www.rfc-editor.org/rfc/rfc8446>.

   [X690]     ITU-T, "Information technology - ASN.1 encoding Rules:
              Specification of Basic Encoding Rules (BER), Canonical
              Encoding Rules (CER) and Distinguished Encoding Rules
              (DER)", ISO/IEC 8824-1:2021 , February 2021.

12.2.  Informative References

   [BASIC-ISSUANCE]
              Celi, S., Davidson, A., Faz-Hernandez, A., Valdez, S., and
              C. A. Wood, "Privacy Pass Issuance Protocol", Work in
              Progress, Internet-Draft, draft-ietf-privacypass-protocol-
              04, 5 April 2022, <https://datatracker.ietf.org/doc/html/
              draft-ietf-privacypass-protocol-04>.

Hendrickson, et al.      Expires 7 October 2022                [Page 33]
Internet-Draft             Rate-Limited Tokens                April 2022

Appendix A.  Acknowledgements

   The authors of this document would like to acknowledge feedback from
   contributors to the Privacy Pass working group for their help in
   improving this document.  The authors also thank Frank Denis and
   David Schinazi for their contributions.

Appendix B.  Test Vectors

   This section includes test vectors for Origin Name encryption in
   Section 6 and Anonymous Origin ID computation in Section 7.  Test
   vectors for the token request and response protocol can be found in
   [ISSUANCE].

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.

   *  origin_name_key_seed: The seed used to derive the private key
      corresponding to Origin Name Key via the DeriveKeyPair function as
      defined in Section 7.1.3. of [HPKE], represented as a hexadecimal
      string.

   *  origin_name_key: The public Origin Name Key, represented as a
      hexadecimal string.

   *  token_type: The type of the protocol specified in this document,
      0x0003.

   *  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.

   *  origin_name_key_id: The Origin Name Key ID computed as in
      Section 5.3, represented as a hexadecimal string.

Hendrickson, et al.      Expires 7 October 2022                [Page 34]
Internet-Draft             Rate-Limited Tokens                April 2022

   *  encrypted_origin_name: The encrypted Origin Name, represented as a
      hexadecimal string.

origin_name: 746573742e6578616d706c65
kem_id: 32
kdf_id: 1
aead_id: 1
origin_name_key_seed:
ccc9e9744e7461acc6f3967757e7564b78f04ae5c9cd33f8c0c9b51ddff61f4f
origin_name_key: 010020c9a7a358ab74c0664b0cffd11a5f7090108086153d77e2824
72d254991fdbe1b00010001
token_type: 3
token_key_id: 104
blinded_msg: 01a7031dbbcca4ac6acaa4650219406fd9fbceb8c264e2b3be22823a679
6571230f29ec01fe2dd633bbd4c208addfa0a6dbb149aeb4aca9070bafe849301076a40b
442469066ef78525f16a4e8cb3596ac0c548932aa421d7294d98e86187100598e9b8a968
c56d2c0277132c3efdc04b6030b9800642db686254784927cfd941f8a3a1f71893e33af4
d73f71403108c882afed2129b050663839d77bbd38f9479e7242a2d31f2fbce72259aab4
acecf7da7168347a214c6e9bb77974812b363355ac8bf4703085de54e2af85e970a3a83e
2ee3d658951167fae57ab313569dcb7551c916cb0bda9c6293843fe75849eb6a33953145
43bccb7e5146b618c637ffe8fc1bae2fddb102ce6d9a9c5eee0d267849a9bfb12e633fbf
ffc80b76b017ae16f70ee6c3d841b9a4b1bf88264a2d62ae564941f943001ed95b869d2f
d81e82efc399507a0ed5450be2832076a40ce1dbd1e555fb0cf360e65c4087d101d87919
9180dfcecdd0a3a2340b893fd130e5d6ece273b4a646f157b344f110973403a14a5f46d3
b2ec4457e2164ce850fc395c71d4adeab69f7ec617b6b062c1afb8da558970dfea3196e9
b2acb58dcfd23f54fc2084373cd9a78f7c84047c6f64e7464999597267e9b6a0f95bf13f
634c2a23f861fc83a09d08309ad00af4abf8cf48f1f7d286f65750f20faa1310849e8aee
44c4ec6abb1c846a16a222116ad94
request_key: 8a9ffd91064e498f0b14b4b82d65255b2859da8d349e2bb362ca7c8211e
23fcd5cd01813ef6eb4b994d532c3520e1aa89e
origin_name_key_id:
590ef89ec14ebd7cd0598c7c1e045838e7c484713265c10d923d314fa1ef433f
encrypted_origin_name: b9d946ee16d9114b6d42524a1fe1e5fae9768c45d4b48ce13
2e758d614911c31c3c1b73a90b63735a0c53f5b94cf176c1a00392618dac727bc287d18

B.2.  Anonymous Origin ID 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.

Hendrickson, et al.      Expires 7 October 2022                [Page 35]
Internet-Draft             Rate-Limited Tokens                April 2022

   *  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.

   *  anon_issuer_origin_id: The anon_issuer_origin_id value computed in
      Section 7.4, represented as a hexadecimal string.

sk_sign: a04e2a1c1a58ed8ca09419fe937507964b640981de40c6c05c14bb547b17830
d5b18c1acf236482234f0e4ed8a6a36e5
pk_sign: 03edf9e62abec27bd25f7171dcf24aeb163fbb026381cb634a8c41058b70b74
083a704177d0aee92a9be2740fd627fa3a4
sk_origin: abc3bbe04e44502bb3549551a87f4f843b7d6ba2fb789bd82ccebe7e304f0
77f52125a4829747bd5c68a8942500d898c
request_blind: 0d19ff14f8d24f7cceb377a0f54b27295e270624814293493d264d967
c541b490d7e95ff1fbb40e4f89dfdd9e25ad997
request_key: 02031027dcbe5e5607749fc6e4e0967cca89d591545c0badc640febc682
50199b87f3e60112a40425a03b9e8ac58d5bb77
index_key: 03878a9ff9e8bc58c05f8b6e71374d14f81a113f2a6828c4fa482e2d3ea50
04c0d790022a71d6437f905fb5d5daf036f52
anon_issuer_origin_id: 3edd83377d6a22f5726dac066ee1864f2c0424cd4868f994b
2e16ec270f4cc4e382a5b0730ca378797171fa2aec8222f

Authors' Addresses

   Scott Hendrickson
   Google LLC
   Email: scott@shendrickson.com

   Jana Iyengar
   Fastly
   Email: jri@fastly.com

   Tommy Pauly
   Apple Inc.
   One Apple Park Way
   Cupertino, California 95014,
   United States of America
   Email: tpauly@apple.com

   Steven Valdez
   Google LLC
   Email: svaldez@chromium.org

Hendrickson, et al.      Expires 7 October 2022                [Page 36]
Internet-Draft             Rate-Limited Tokens                April 2022

   Christopher A. Wood
   Cloudflare
   Email: caw@heapingbits.net

Hendrickson, et al.      Expires 7 October 2022                [Page 37]