Network Working Group A. Davidson Internet-Draft Cloudflare Portugal Intended status: Informational 9 March 2020 Expires: 10 September 2020 Privacy Pass: Architectural Framework draft-davidson-pp-architecture-00 Abstract This document specifies the architectural framework for constructing secure and privacy-preserving instantiations of the Privacy Pass protocol (as described in [draft-davidson-pp-protocol]). The framework refers to the entire ecosystem of Privacy Pass clients and servers. This document makes recommendations on how this ecosystem should be constructed to ensure the privacy of clients and the security of all participating entities. 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 10 September 2020. Copyright Notice Copyright (c) 2020 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 Simplified BSD License text Davidson Expires 10 September 2020 [Page 1] Internet-Draft PP architecture March 2020 as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Layout . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Architectural ecosystem assumptions . . . . . . . . . . . . . 6 2.1. Servers . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1. Long-term signing . . . . . . . . . . . . . . . . . . 7 2.2. Clients . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3. Global configuration store . . . . . . . . . . . . . . . 8 3. Protocol integration policy . . . . . . . . . . . . . . . . . 8 3.1. Recap: Protocol API . . . . . . . . . . . . . . . . . . . 9 3.2. Server interfaces . . . . . . . . . . . . . . . . . . . . 9 3.2.1. SERVER_KEY_GEN . . . . . . . . . . . . . . . . . . . 9 3.2.2. SERVER_STORE_CONFIG . . . . . . . . . . . . . . . . . 10 3.2.3. SERVER_CONFIG_RETRIEVAL . . . . . . . . . . . . . . . 11 3.2.4. SERVER_HELLO . . . . . . . . . . . . . . . . . . . . 11 3.2.5. SERVER_ISSUE . . . . . . . . . . . . . . . . . . . . 12 3.2.6. SERVER_REDEEM . . . . . . . . . . . . . . . . . . . . 13 3.2.7. SERVER_DOUBLE_SPEND_CHECK . . . . . . . . . . . . . . 13 3.2.8. SERVER_DOUBLE_SPEND_STORE . . . . . . . . . . . . . . 14 3.3. Client interfaces . . . . . . . . . . . . . . . . . . . . 14 3.3.1. CLIENT_CONFIG_RETRIEVAL . . . . . . . . . . . . . . . 14 3.3.2. CLIENT_ISSUE_GEN . . . . . . . . . . . . . . . . . . 16 3.3.3. CLIENT_ISSUE_FINISH . . . . . . . . . . . . . . . . . 16 3.3.4. CLIENT_REDEEM . . . . . . . . . . . . . . . . . . . . 17 3.3.5. CLIENT_ISSUE_STORAGE . . . . . . . . . . . . . . . . 18 3.3.6. CLIENT_ISSUE_RETRIEVAL . . . . . . . . . . . . . . . 18 3.3.7. CLIENT_TOKEN_STORAGE . . . . . . . . . . . . . . . . 18 3.3.8. CLIENT_TOKEN_RETRIEVAL . . . . . . . . . . . . . . . 18 3.4. Global configuration registry interfaces . . . . . . . . 19 3.4.1. GLOBAL_CONFIG_UPDATE . . . . . . . . . . . . . . . . 19 3.4.2. GLOBAL_CONFIG_RETRIEVAL . . . . . . . . . . . . . . . 20 4. Key management framework . . . . . . . . . . . . . . . . . . 21 4.1. Global configuration . . . . . . . . . . . . . . . . . . 22 4.2. Configuration structure . . . . . . . . . . . . . . . . . 22 4.3. Configuration updates #{config-update} . . . . . . . . . 24 4.4. Client retrieval . . . . . . . . . . . . . . . . . . . . 24 4.5. Key revocation . . . . . . . . . . . . . . . . . . . . . 25 5. Server running modes . . . . . . . . . . . . . . . . . . . . 25 5.1. Single-Issuer Single-Verifier . . . . . . . . . . . . . . 25 5.2. Single-Issuer Forwarding-Verifier . . . . . . . . . . . . 26 5.3. Single-Issue Asynchronous-Verifier . . . . . . . . . . . 26 5.4. Bounded-Issuers . . . . . . . . . . . . . . . . . . . . . 27 6. Privacy analysis . . . . . . . . . . . . . . . . . . . . . . 27 Davidson Expires 10 September 2020 [Page 2] Internet-Draft PP architecture March 2020 6.1. User segregation . . . . . . . . . . . . . . . . . . . . 28 6.1.1. Server configuration rotation . . . . . . . . . . . . 28 6.1.2. Large numbers of issuers . . . . . . . . . . . . . . 29 6.2. Tracking and identity leakage . . . . . . . . . . . . . . 30 6.3. Client incentives for anonymity reduction . . . . . . . . 30 7. Security considerations . . . . . . . . . . . . . . . . . . . 31 7.1. Double-spend protection . . . . . . . . . . . . . . . . . 31 7.2. Configuration rotation . . . . . . . . . . . . . . . . . 31 7.3. Token exhaustion . . . . . . . . . . . . . . . . . . . . 32 8. Protocol parametrization . . . . . . . . . . . . . . . . . . 32 8.1. Justification . . . . . . . . . . . . . . . . . . . . . . 33 8.2. Example parameterization . . . . . . . . . . . . . . . . 34 9. Recommendations for identifying malicious behavior . . . . . 34 10. Extension integration policy . . . . . . . . . . . . . . . . 34 11. Existing applications . . . . . . . . . . . . . . . . . . . . 35 11.1. Cloudflare challenge pages . . . . . . . . . . . . . . . 35 11.2. Trust Token API . . . . . . . . . . . . . . . . . . . . 36 11.3. Zero-knowledge Access Passes . . . . . . . . . . . . . . 36 11.4. Basic Attention Tokens . . . . . . . . . . . . . . . . . 36 11.5. Token Based Services . . . . . . . . . . . . . . . . . . 36 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 36 12.1. Normative References . . . . . . . . . . . . . . . . . . 36 12.2. Informative References . . . . . . . . . . . . . . . . . 37 Appendix A. Message formats . . . . . . . . . . . . . . . . . . 38 A.1. Server messages . . . . . . . . . . . . . . . . . . . . . 38 A.1.1. server_config_store . . . . . . . . . . . . . . . . . 38 A.1.2. server_config_retrieve . . . . . . . . . . . . . . . 38 A.1.3. server_hello . . . . . . . . . . . . . . . . . . . . 38 A.1.4. server_issue_resp . . . . . . . . . . . . . . . . . . 38 A.1.5. server_redeem_resp . . . . . . . . . . . . . . . . . 38 A.2. Client message formats . . . . . . . . . . . . . . . . . 39 A.2.1. client_issue_generation . . . . . . . . . . . . . . . 39 A.2.2. client_issue_storage . . . . . . . . . . . . . . . . 39 A.2.3. client_issue . . . . . . . . . . . . . . . . . . . . 39 A.2.4. client_issue_retrieval . . . . . . . . . . . . . . . 39 A.2.5. client_issue_retrieval_resp . . . . . . . . . . . . . 39 A.2.6. client_token_storage . . . . . . . . . . . . . . . . 39 A.2.7. client_token_retrieval . . . . . . . . . . . . . . . 40 A.2.8. client_token_retrieval_resp . . . . . . . . . . . . . 40 A.2.9. client_redeem_generation . . . . . . . . . . . . . . 40 A.2.10. client_redeem . . . . . . . . . . . . . . . . . . . . 40 A.3. Global configuration interfaces . . . . . . . . . . . . . 40 A.3.1. config_update . . . . . . . . . . . . . . . . . . . . 40 A.3.2. config_retrieval . . . . . . . . . . . . . . . . . . 40 A.3.3. config_retrieval_resp . . . . . . . . . . . . . . . . 41 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 41 Davidson Expires 10 September 2020 [Page 3] Internet-Draft PP architecture March 2020 1. Introduction The Privacy Pass protocol provides a privacy-preserving mechanism for authorization of clients with servers. The protocol is detailed in [draft-davidson-pp-protocol] and is intended for use in performance- critical settings, such as while browsing the Internet. The way that the ecosystem around the protocol is set up can have significant impacts on the stated privacy and security guarantees of the protocol. For instance, the number of servers issuing Privacy Pass tokens, along with the number of registered clients, determines the privacy budget available to each individual client. This can be further influenced by other factors, such as: the key rotation policy used by each server; and, the number of supported ciphersuites. There are also client-behavior patterns that can reduce the effective security of the server. In this document, we will provide a structural framework for building the ecosystem around the Privacy Pass protocol. Firstly, it will identify a number of common interfaces for integrating the Privacy Pass protocol and the API detailed in [draft-davidson-pp-protocol]. The API in the protocol document represents a basic one-on-one exchange between a client and a server. The interfaces that we describe in this document reproduce this API into the setting where clients and servers are part of a wider ecosystem. On top of this, the document also includes policies for the following considerations: * How server configurations and key material should be stored and rotated in an open and transparent manner. * Compatible server issuance and redemption running modes and associated expectations. * A concrete assessment and parametrization of the privacy budget associated with different settings of the above policies. * Recommendations for identifying malicious server behavior. * Assessment of client incentives for eschewing privacy features. * The incorporation of potential extensions into the wider ecosystem. Finally, we will discuss existing applications that make use of the Privacy Pass protocol, and highlight how these may fit with the proposed framework. Davidson Expires 10 September 2020 [Page 4] Internet-Draft PP architecture March 2020 1.1. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. The following terms are used throughout this document. * Server: A service that provides access to a certain resource (typically denoted S) * Client: An entity that seeks authorization from a server (typically denoted C) * Key: Server's secret key * Config: The server configuration associated with the key material and ciphersuite choices that it makes. We assume that all protocol messages are encoded into raw byte format before being sent. We use the TLS presentation language [RFC8446] to describe the structure of the data that is communicated and stored. 1.2. Layout * Section 2: Describes the basic assumptions that we make in this document on the shape and topology of the Privacy Pass ecosystem: the environment in which Privacy Pass supporting clients and servers interact with each other. * Section 3: Describes the policy and framework for building interoperable client and server implementations. Also provides the necessary foundations for interacting with the global configuration registry. * Section 4: Describes the structure of server key configurations and how this configuration is retrieved and updated. * Section 5: Describes the different running modes that are currently expected from Privacy Pass servers. * Section 6: An analysis of the characteristics of the Privacy Pass architecture that have an impact on the privacy of clients participating in the ecosystem. * Section 7: An analysis of the security characteristics of the protocol when viewed as a part of the wider architecture of the Davidson Expires 10 September 2020 [Page 5] Internet-Draft PP architecture March 2020 protocol ecosystem. Includes discussions of the cases for both servers and clients. * Section 8: Provides an example parametrization of the privacy and security parameters that are associated with the protocol, based on the previous discussions. * Section 9: Recommendations for identifying and highlighting potential malicious behavior by a server. * Section 10: Describes the policy for writing extensions to the Privacy Pass protocol, and how they may be incorporated into the wider architecture. * Section 11: A non-exhaustive list of the applications that make use of the Privacy Pass protocol, or some variant of it. 2. Architectural ecosystem assumptions The Privacy Pass ecosystem refers to the global framework in which multiple instances of the Privacy Pass protocol operate. This refers to all servers that support the protocol, or any extension of it, along with all of the clients that may interact with these servers. Moreover, there is a singular public entity known as the 'global configuration registry'. This registry presents the public information related to all supported server key material. This is required to enable the client to process issuance responses from each of the available servers. The ecosystem itself, and the way it is constructed, is critical for evaluating the privacy of each individual client. We assume that a client's privacy refers to fraction of users that it represents in the anonymity set that it belongs to. We discuss this more in Section 6. 2.1. Servers Servers in the Privacy Pass ecosystem are entities whose primary function is to undertake the role of the "Server" in [draft-davidson-pp-protocol]. To facilitate this, the server must hold the following data at any given time: * a valid server configuration ("ServerConfig") as specified in [draft-davidson-pp-protocol]; * a long-term signing key pair for a signature scheme "sig_alg"; Davidson Expires 10 September 2020 [Page 6] Internet-Draft PP architecture March 2020 * storage of Privacy Pass tokens that have been previously redeemed with the server. The server must be available at a specified address (uniquely identified by "server_id") that accepts communications from Privacy Pass clients Section 2.2 on the interfaces defined in Section 3.2. When the server wants to update its configuration, it communicates with the global configuration registry Section 2.3. 2.1.1. Long-term signing The long-term signing key pair "(k_sign, k_vrfy)" is used to sign configuration data that is sent to the global configuration registry. The server must prove to the global key configuration registry the veracity of the long-term key-pair that it uses. This key pair is attached to the configuration that it maintains. We assume the following functional API: * "sig = sig_alg.sign(k_sign, data)": produces a signature "sig" using the signing key, "k_sign", over the bytes of "data". * "b = sig_alg.verify(k_vrfy, data, sig)": produces a boolean result "b" indicating that "sig" is a valid signature over "data" using the signing key "k_sign". As per usual, we assume that any signature produced by the ".sign" function produces a result of "true" when verifying using ".verify". Likewise, the scheme should also satisfy the well-known security property of existential unforgeability. Valid instantiations include DSA (and ECDSA) [X9.62]. 2.2. Clients Clients in the Privacy Pass ecosystem are entities whose primary function is to undertake the role of the "Client" in [draft-davidson-pp-protocol]. The clients are assumed to only store data related to the tokens that it has been issued by the server. This storage is used for constructing redemption requests, see the "CLIENT_REDEEM" interface (Section 3.3.4) for more details. The clients must also have access to the global config store Section 2.3. This is so that the client can retrieve data related to the configuration of the server that it is communicating with. Each client must be addressed by a unique identifier, given by "client_id". Davidson Expires 10 September 2020 [Page 7] Internet-Draft PP architecture March 2020 2.3. Global configuration store The global configuration store controls all the configuration data that is used by the servers that are part of the Privacy Pass ecosystem. This data is required to allow clients to verify server issuance responses. The server configuration data corresponds to all the ciphersuites and key fingerprints that have ever been used, by every server in the Privacy Pass ecosystem. The config store is an append-only database that supports revocation of old configurations. This is done by limiting the number of active configurations that a server can use at any given time. It should be available at a publicly-broadcasted address so that both clients and servers can access it. The database should preserve its history in an audit-friendly manner. The way that the config store is implemented can have a dramatic effect on the privacy of the clients in the Privacy Pass protocol. We describe in detail how such a store should be implemented in Section 4. 3. Protocol integration policy We provide a number of common interfaces that both the clients and servers implement. These interfaces should be contactable by entities in the ecosystem, and provide a framework for generating and processing data in the Privacy Pass protocol. The framework provides a policy that states that these interfaces be implemented (for example, by clients and servers) to be considered valid entities in the Privacy Pass ecosystem. The interfaces wrap the Privacy Pass API functions detailed in [draft-davidson-pp-protocol] to provide functionality in the many-many ecosystem consisting of clients and servers. The interfaces have three configurable fields. The "Visibility" field indicates that the interface is either contactable externally ("external") or that it is activated internally by the entity at some point ("internal"). The "Input" field determines valid input types of that are received by the interface. The "Returns" field provides the return type of the function. The "Steps" field notes high-level steps to be taken when the interface is contacted. Note: currently we live the implementation of errors up to the implementer. By default, if any internal Privacy Pass protocol function (Section 3.1) throws an error, then the interface should panic. More fine-grained error reporting may be added in future versions of this draft. Davidson Expires 10 September 2020 [Page 8] Internet-Draft PP architecture March 2020 3.1. Recap: Protocol API The protocol document [draft-davidson-pp-protocol] specifically details a number of public API functions that are used for constructing the generic protocol. These functions can be split into server and client functionality. 1. Server functionality: * "PP_Server_Setup": Generates server configuration and keys * "PP_Issue": Run on the contents of the client message in the issuance phase. * "PP_Verify": Run on the contents of the client message in the redemption phase. 2. Client functionality: * "PP_Client_Setup": Generates the client configuration based on the configuration used by a given server. * "PP_Generate": Generates public and private data associated with the contents of the client message in the issuance phase. * "PP_Process": Processes the contents of the server response in the issuance phase. * "PP_Redeem": Generates the data that forms the client message in the redemption phase. We will use each of the functions internally in the description of the interfaces that follows. 3.2. Server interfaces Any implementation of a Privacy Pass Server MUST implement the following contact points or interfaces. When the Server is contacted on these interfaces with the required input data, it should take the steps detailed. The inputs and responses for each of the interfaces correspond to the data structures defined in [draft-davidson-pp-protocol]. 3.2.1. SERVER_KEY_GEN * Visibility: "internal" Davidson Expires 10 September 2020 [Page 9] Internet-Draft PP architecture March 2020 * Input: a string, "id", corresponding to a ciphersuite identifier (see [draft-davidson-pp-protocol] for valid configurations). * Returns: a boolean "b", indicating success. * Steps: 1. Run "(cfg, update) = PP_Server_Setup(id)". 2. Construct a "config_update" message. 3. The value "" is the unique identifier for the Server. 4. The value of "" should be a point in the future within the window of allowed key rotation lengths (for example, those specified in Section 8). 5. The value "" is a string used to distinguish between config entries corresponding to the same config, but where the key material has changed (e.g. after a key rotation). 6. The value of "" should be set to an octet corresponding to the functionality that is provided. The value "0" indicates that no functionality is supported; "1" indicates that the server supports the issuance phase; "2" indicates support for the redemption phase; and "3" indicates support for both phases. If unspecified, this defaults to "3". 7. The value of "" is set to be equal to "update". 8. The value "" is computed over the bytes of the rest of message contents, using the Server long-term secret signing key "k_sign". This can be computed by running: data = .. .. .. = sig_alg.sign(k_sign, data) 9. Send the "config_update" message to the "GLOBAL_CONFIG_UPDATE" interface. 10. Send a "server_config_store" message to the "SERVER_STORE_CONFIG" interface containing the value of "cfg". 3.2.2. SERVER_STORE_CONFIG Davidson Expires 10 September 2020 [Page 10] Internet-Draft PP architecture March 2020 * Visibility: "internal" * Input: a "server_config_store" message "msg" (Appendix A.1.1). * Returns: "null" * Steps: 1. Let "ex_cfg" correspond to the existing "ServerConfig" object keyed by "issue". 2. Store the bytes of "msg.config" in local storage, against the key "issue". 3. Store the bytes of "ex_cfg" in local storage against the key "redeem". 3.2.3. SERVER_CONFIG_RETRIEVAL * Visibility: "internal" * Input: an octet "method" in "{1,2,3}". * Returns: A "server_config_retrieve" message "resp" (Appendix A.1.2). * Steps: 1. Let "storage" be the ID and the bytes of the server config currently stored in local storage, respectively. 2. If "resp.config.supports != method && resp.config.supports != 3", then return "null". 3. Let "resp" be a "server_config_retrieve" message, where "=[config]" for "config" stored in local storage against "issue". 4. If "method == 2", append "ex_config" to "", where "ex_config" is stored in local storage against the key "redeem". 5. Return "resp". 3.2.4. SERVER_HELLO * Visibility: "external" Davidson Expires 10 September 2020 [Page 11] Internet-Draft PP architecture March 2020 * Input: a string, "client_addr", corresponding to an address that the client can be contacted on. * Return: "null" * Steps: 1. Send an empty message to the internal "SERVER_CONFIG_RETRIEVAL" interface, and let "cfgs=resp.configs" based on the "server_config_retrieve" response "resp". 2. Send a "server_hello" message to the "CLIENT_CONFIG_RETRIEVAL" interface for the client at "client_addr". The "server_hello" message must satisfy the following: 1. The value "=server_id" is the unique identifier for the Server. 2. The value of "" MUST be set to an octet corresponding to the supported methods. 3.2.5. SERVER_ISSUE * Visibility: "external" * Input: A "client_issue" message "msg" (Appendix A.2.3) * Returns: A "server_issue_resp" message * Steps: 1. Send the message "issue" to the internal "SERVER_CONFIG_RETRIEVAL" interface, and let "ciphersuite=msg.ciphersuites[0]" and "srv_cfg=msg.configs[0]" based on the "server_config_retrieve" response. 2. Run the following: issue_resp = PP_Issue(srv_cfg, msg.issue_data) 3. Returns a "server_issue_resp" message with "=issue_resp" message back to the caller "CLIENT_ISSUE_GEN" interface of the client associated with "client_issue.client_id". Davidson Expires 10 September 2020 [Page 12] Internet-Draft PP architecture March 2020 3.2.6. SERVER_REDEEM * Visibility: "external" * Input: A "client_redeem" message "msg" (Appendix A.2.10) * Returns: A "server_redeem_resp" message back to the calling "CLIENT_REDEEM" interface (Appendix A.1.5). * Steps: 1. Send the message "redeem" to the internal "SERVER_CONFIG_RETRIEVAL" interface, let "configs" be the returned array. 2. Send "msg.message.data" to the "SERVER_DOUBLE_SPEND_CHECK" interface and, if the response is "true", return an unsuccessful "server_redeem_resp" message to the client. 3. Run the following: resp = PP_Verify(configs[0],message) if (!resp.success) { resp = PP_Verify(configs[1],message) } 4. Send "msg.message.data" to the "SERVER_DOUBLE_SPEND_STORE" interface. 5. The Server returns a "server_redeem_resp" message, with "=resp" back to the "CLIENT_REDEEM" interface of the client associated with "client_redeem.client_id". 3.2.7. SERVER_DOUBLE_SPEND_CHECK * Visibility: "internal" * Input: A byte string "data" of type "opaque<1..2^32-1>" (Appendix A.2.10). * Returns: A boolean value "b". * Steps: 1. Return "true" if "data" exists in the double-spend index, and "false" otherwise. Davidson Expires 10 September 2020 [Page 13] Internet-Draft PP architecture March 2020 3.2.8. SERVER_DOUBLE_SPEND_STORE * Visibility: "internal" * Input: A byte string "data" of type "opaque<1..2^32-1>" (Appendix A.2.10). * Returns: "null". * Steps: 1. Store "data" in the double-spend index. 3.3. Client interfaces The following interfaces MUST be implemented for any implementation of a Client in the Privacy Pass ecosystem (Section 2.2). 3.3.1. CLIENT_CONFIG_RETRIEVAL * Visibility: "external" * Input: a "server_hello" message type denoted by "msg", (Appendix A.1.3). * Return: a boolean, indicating whether the config was successfully retrieved. * Steps: 1. Construct a "config_retrieval" message using "=msg.server_id". 2. Send the "config_retrieval" message to the "GLOBAL_CONFIG_RETRIEVAL" interface, and receive a reply "resp" of type "config_retrieval_resp". 3. If "success" is set to "false", return "false". 4. Parse "resp[0].supports" and check that it includes support for what is specified in "msg.supports", otherwise return false. 5. Parse "resp[1].supports" and check that it includes support for what is specified in "msg.supports", otherwise return false. Davidson Expires 10 September 2020 [Page 14] Internet-Draft PP architecture March 2020 6. The value "" is verified over the bytes of the rest of message contents, using the Server long-term verification key "k_vrfy". This can be computed by running the function below and checking that "ret==true", otherwise returning false. data = .. .. .. .. .. ret = sig_alg.verify(k_vrfy, data, ) 7. Construct a "client_token_retrieval" where ciphersuite = resp[0].ciphersuite comm_id = resp[0].comm_id and send it to the "CLIENT_TOKEN_RETRIEVAL" interface. Receive back "token" in a "client_token_retrieval_resp" message. Set "config_idx=0". 8. If "token == null", construct a "client_token_retrieval" message where: ciphersuite = resp[1].ciphersuite comm_id = resp[1].comm_id and send it to the "CLIENT_TOKEN_RETRIEVAL" interface. Receive back "token" in a "client_token_retrieval_resp" message. Set "config_idx=1'". 9. If: token == null && ( resp[0].supports == 1 || resp[0].supports == 3 ) construct a "client_issue_generation" message and send it to the "CLIENT_ISSUE_GEN" interface, with: 1. " = msg.server_id"; 2. " = resp[0].config"; 10. If: ~~~ token != null && ( resp[config_type].supports == 2 || resp[config_type].supports == 3 ) ~~~ Davidson Expires 10 September 2020 [Page 15] Internet-Draft PP architecture March 2020 construct a "client_redeem_generation" message and send it to the "CLIENT_REDEEM" interface. with: 1. ` = msg.server_id`; 2. ` = token`; 1. If neither condition in (7) or (8) is satisfied, return false. 2. Return true. 3.3.2. CLIENT_ISSUE_GEN * Visibility: "internal" * Input: a message "msg" of type "client_issue_generation" (Appendix A.2.1). * Returns: "null" * Steps: 1. The client runs: cli_cfg = PP_Client_Setup(msg.ciphersuite, msg.config) 2. The client runs: issue_input = PP_Generate(cli_cfg, m) where "m" is an integer corresponding to the number of tokens that should be generated. 3. The client constructs a "client_issue_storage" message and sends it to the "CLIENT_ISSUE_STORAGE" interface, where "=msg.server_id", "=issue_input.client_data". 4. The client constructs a "client_issue" message and sends it to the server corresponding to "" with "=issue_input.msg_data". 5. Receives a "server_issue_resp" message back from client_data server, and sends this to the "CLIENT_ISSUE_FINISH" interface. 3.3.3. CLIENT_ISSUE_FINISH * Visibility: "internal" Davidson Expires 10 September 2020 [Page 16] Internet-Draft PP architecture March 2020 * Input: a message "msg" of type "server_issue_resp" (Appendix A.1.4). * Returns: "null" * Steps: 1. The client sends an empty message to the "CLIENT_ISSUE_RETRIEVAL" interface and receives a "client_issue_retrieval" message "tmp" in response. 2. The client sets "cli_cfg=tmp.config". 3. The client runs: tokens = PP_Process(cli_cfg,(msg.evals, msg.proof),tmp.g_data) 4. The client constructs a "client_token_storage" message and sends it to the "CLIENT_TOKEN_STORAGE" interface, where "=tokens". 3.3.4. CLIENT_REDEEM * Visibility: "internal" * Input: a message "msg" of type "client_redeem_generation" (Appendix A.2.9). * Returns: a boolean value "ret" indicating whether the server accepted the redemption, or not. * Steps: 1. The client runs: cli_cfg = PP_Client_Setup(msg.ciphersuite, msg.config) 2. The client generates arbitrary auxiliary data "aux" and runs: tag = PP_Redeem(cli_cfg, msg.token, aux) 3. The client constructs a "client_redeem" message and sends it to the "SERVER_REDEEM" interface of the Server referred to by "", with "=msg.token.data" and "=aux". 4. The client returns the value boolean value indicated in the "RedemptionResponse" received in the server's "server_redeem_resp" message. Davidson Expires 10 September 2020 [Page 17] Internet-Draft PP architecture March 2020 3.3.5. CLIENT_ISSUE_STORAGE * Visibility: "internal" * Input: a "client_issue_storage" message "msg" (Appendix A.2.2). * Returns: "null" * Steps: 1. Stores the "ClientIssuanceProcessing" struct represented by "msg.client_data" in local storage, keyed by "server_id", "ciphersuite" and "comm_id". 3.3.6. CLIENT_ISSUE_RETRIEVAL * Visibility: "internal" * Input: a "client_issue_retrieval" message "msg" (Appendix A.2.4). * Returns: a "client_issue_retrieval_resp" message (Appendix A.2.5). * Steps: 1. Retrieve "client_data" where "msg.server_id", "msg.ciphersuite" and "msg.comm_id". 2. Return a "client_issue_retrieval" message containing "client_data" above to the "CLIENT_ISSUE_FINISH" interface. 3.3.7. CLIENT_TOKEN_STORAGE * Visibility: "internal" * Input: a "client_token_storage" message "msg" (Appendix A.2.6). * Returns: "null" * Steps: 1. Stores the vector of "RedemptionToken" objects in local storage keyed by "server_id", "ciphersuite" and "comm_id". 3.3.8. CLIENT_TOKEN_RETRIEVAL * Visibility: "internal" * Input: a "client_token_retrieval" message "msg" (Appendix A.2.7). Davidson Expires 10 September 2020 [Page 18] Internet-Draft PP architecture March 2020 * Returns: a "client_token_retrieval_resp" message. * Steps: 1. Retrieve all the available token "tokens" keyed by "msg.server_id", "msg.ciphersuite" and "msg.comm_id". 2. If "tokens != null", let "token = tokens.pop()". 3. Store the modified "tokens" object back in local storage by interacting with the "CLIENT_TOKEN_STORAGE" interface. 4. Return a "client_token_retrieval" message containing the token value above (or "null" if "tokens == null") to the "CLIENT_CONFIG_RETRIEVAL" interface. 3.4. Global configuration registry interfaces 3.4.1. GLOBAL_CONFIG_UPDATE * Visibility: "external" * Input: a "config_update" message "msg" (Appendix A.3.1). * Returns: "null" * Steps: 1. Creates an entry in the global config registry, keyed by "msg.server_id", "msg.config.ciphersuite" and "msg.comm_id". Therefore, the registry data block takes the form: server_id: msg.server_id ciphersuite: msg.config.ciphersuite comm_id: msg.comm_id config: msg.config expiry: msg.expiry signature: msg.signature supports: msg.supports 2. Updates "server_id.previous" to be equal to a structure of the form: struct { Ciphersuite ciphersuite = current.ciphersuite int16 comm_id = current.comm_id } Davidson Expires 10 September 2020 [Page 19] Internet-Draft PP architecture March 2020 where the "Ciphersuite" struct is described in [draft-davidson-pp-protocol]. 3. Updates "server_id.current" to be equal to a structure of the form: struct { Ciphersuite ciphersuite = msg.ciphersuite int16 comm_id = msg.comm_id } 4. Appends the current time to the vector of datetime values in "server_id.modified". 3.4.2. GLOBAL_CONFIG_RETRIEVAL * Visibility: "external" * Input: a "config_retrieval" message "msg" (Appendix A.3.1). * Returns: a "config_retrieval_resp" message (Appendix A.3.3). * Steps: 1. Retrieve the data structure "server_ds" from the global config registry, keyed by "msg.server_id". 2. Let "current=server_ds[current.ciphersuite][current.comm_id]" 3. Let "previous=server_ds[previous.ciphersuite][previous.comm_id]" 4. Return a "config_retrieval_resp" message of the form below, to the querying interface. Davidson Expires 10 September 2020 [Page 20] Internet-Draft PP architecture March 2020 cfg_0 = config_entry { ciphersuite: current.ciphersuite, comm_id: current.comm_id, config: current.config, expiry: current.expiry, signature: current.signature, supports: current.supports, }; cfg_1 = config_entry { ciphersuite: current.ciphersuite, comm_id: current.comm_id, config: current.config, expiry: current.expiry, signature: current.signature, supports: current.supports, }; resp = config_retrieval_resp { configs: [cfg_0, cfg_1], } 4. Key management framework Rather than sending the result of the key initialisation procedure directly to each client, it is preferable for a server to upload its current configurations to a trusted, tamper-proof, history-preserving registry. By trusted, we mean from the perspective of clients that use the Privacy Pass protocol. Any new keys uploaded to the registry should be appended to the list. Any keys that have expired can optionally be labelled as so, but should never be removed. A trusted registry may hold key commitments for multiple Privacy Pass service providers (servers). As we discuss in Section 6, the implementation of the key management policy has a major impact on the privacy properties of the Privacy Pass ecosystem that it belongs to. To prevent unauthorized modification of the trusted registry, server's should be required to identify and authenticate themselves before they can append data to their configuration. Moreover, only parts of the registry that correspond to the servers configuration can be modifiable. We intend for the registry that we describe to be fulfilled by existing frameworks, such as Key Transparency [keytrans] or other similar architectures. Davidson Expires 10 September 2020 [Page 21] Internet-Draft PP architecture March 2020 4.1. Global configuration As alluded to above, key management for the Privacy Pass ecosystem should be controlled by a single global key configuration registry. This registry must be available at a publicly-known address and MUST hold all of the configuration data for all of the Privacy Pass servers in the ecosystem. Supporting more than one configuration registry could lead to privacy concerns. The registry MUST support the interfaces constructed in Section 3.4. 4.2. Configuration structure The global config registry is organized as a key-value store corresponding to all of the configurations supported by all of the recognized servers that are part of the Privacy Pass ecosystem. The structure of the configuration takes the form below. Davidson Expires 10 September 2020 [Page 22] Internet-Draft PP architecture March 2020 server_id: verification_key: current: previous: modified: ciphersuite: comm_id: config: expiry: supports: signature: . . . comm_id: config: expiry: supports: signature: . . . ciphersuite: ... . . . server_id: ... Essentially, each server corresponds to a single "server_id" and "ciphersuite" corresponds to the different ciphersuites that the server can use. Each configuration is defined by the data in the "config", "expiry", "supports" and "signature" fields. The "config" field contains the data represented in the "ServerUpdate" struct [draft-davidson-pp-protocol], for example including the public key "pub_key" of the server, and the value of "max_evals". Each server defines a separate verification key in the "verification_key" field corresponding to the long-term signing key that is used for signing each of the individual configurations and "comm_id" values that it possesses. Davidson Expires 10 September 2020 [Page 23] Internet-Draft PP architecture March 2020 The "current", "previous" and "modified" fields are the only fields that change during configuration updates. The "current" field refers to the latest configuration to support token issuance. The "previous" field is used for a single configuration that still permits redemption of tokens, this is used for ensuring that key rotations are smooth for clients. The "modified" field refers to a vector of all times when the configuration was modified. 4.3. Configuration updates #{config-update} Whenever a server wants to rotate their current configuration, they must create a request to append their new configuration to the trusted registry. This request is handled by the global registry to update the configuration, see the "GLOBAL_CONFIG_UPDATE" interface. Each update results in adding a new config underneath an existing "" with a new "" parameter, or a new "" entry. The global config registry also updates, the "current", "previous" and "modified" fields to indicate that the change has occurred. For reasons that are addressed more closely in Section 6, the global configuration registry must ensure that the only configurations that are used at any given time, are those referred to in "current" and "previous". This is done to ensure that the server is not able to serve tokens to clients from multiple different configurations (which could be used to decrease the size of client anonymity sets). All fields apart from the three referenced above MUST never be modified. If a server wants to rotate the long-term "verification_key" it must create a new server identity. 4.4. Client retrieval Clients can either choose to: * poll the trusted registry and import new keys, rejecting any that throw errors; * retrieve the commitments for the server at the time at which they are used, throwing errors if no valid commitment is available. In the interfaces in Section 3.3 we default to assuming that the client retrieves the latest configuration as and when it is needed. See the "CLIENT_CONFIG_RETRIEVAL" interface (Section 3.3.1) for more details. Davidson Expires 10 September 2020 [Page 24] Internet-Draft PP architecture March 2020 The client checks that the configuration is consistent with the data it receives from the server. It also checks the validity of the "signature" field on the configuration that it retrieves. Later we also discuss optionally checking the values in "modified" for trying to identify malicious server behavior. 4.5. Key revocation Currently, key revocation is only supported by rotating the current configuration. In the future, we may consider adding an explicit mechanism for revoking a specific configuration (for example the active redemption configuration referred to by "server_id.previous") without rotating the current issuance key. 5. Server running modes We provide an overview of some of the possible frameworks for configuring the way that servers run in the Privacy Pass ecosystem. In short, servers may be configured to provide symmetric issuance and redemption with clients. While some servers may be configured as proxies that accept Privacy Pass data and send it to another server that actually processes issuance and/or redemption data. The intention with providing each of these running modes is to cover the different applications that utilize variants of the Privacy Pass protocol. We RECOMMEND that any Privacy Pass server implementation adheres to one of these frameworks. 5.1. Single-Issuer Single-Verifier The simplest way of considering the Privacy Pass protocol is in a setting where the same server plays the role of issuer and verifier, we call this "Single-Issuer Single-Verifier" (SISV). In SISV, we consider a server S that publishes commitments for their secret key k, that a client C has access to. When S wants to issue tokens to C, they invoke the issuance protocol where C generates their own inputs and S uses their secret key k. In this setting, C can only perform token redemption with S. When a token redemption is required, C and S invoke the redemption phase of the protocol, where C uses an issued token from a previous exchange, and S uses k as their input again. In SISV, C proves that S has attested to the honesty of C at some point in the past (without revealing exactly when). S can use this information to inform it's own decision-making about C without having to recompute the trust attestation task again. Davidson Expires 10 September 2020 [Page 25] Internet-Draft PP architecture March 2020 5.2. Single-Issuer Forwarding-Verifier In this setting, each client C obtains issued tokens from a server S via the issuance phase of the protocol. The difference is that clients can prove that S has attested to their honesty in the past with any verifier V. We still only consider S to hold their own secret key. When C interacts with V, V can ask C to provide proof that the separate issuer S has attested to their trust. The first stage of the redemption phase of the protocol is invoked between C and V, which sees C send the unused token (x,y,aux) to V. This message is then used in a redemption exchange between V and S, where V plays the role of the client. Then S sends the result of the redemption exchange to V, and V uses this result to determine whether C has the correct trust attestation. This configuration is known as "Single-Issuer Forwarding-Verifier" or SIFV to refer to the verifier V who uses the output of the redemption phase for their own decision-making. 5.3. Single-Issue Asynchronous-Verifier This setting is inspired by recently proposed APIs such as [TRUST]. It is similar to the SIFV configuration, except that the verifiers V no longer interact with the issuer S. Only C interacts with S, and this is done asynchronously to the trust attestation request from V. Hence "Asynchronous-Verifier" (SIAV). When V invokes a redemption for C, C then invokes a redemption exchange with S in a separate session. If verification is carried out successfully by S, S instead returns a Signed Redemption Record (SRR) that contains the following information: "result": { "timestamp":"2019-10-09-11:06:11", "verifier": "V", }, "signature":sig, The "signature" field carries a signature evaluated over the contents of "result" using a long-term signing key for the issuer S, of which the corresponding public key is well-known to C and V. Then C can prove that their trust attestation from S to V by sending the SRR to V. The SRR can be verified by V by verifying the signature using the well-known public key for S. Davidson Expires 10 September 2020 [Page 26] Internet-Draft PP architecture March 2020 Such records can be cached to display again in the future. The issuer can also add an expiry date to the record to determine when the client must refresh the record. 5.4. Bounded-Issuers Each of the configurations above can be generalized to settings where a bounded number of issuers are allowed, and verifiers can invoke trust attestations for any of the available issuers. Subsequently, this leads to three new configurations known as BISV, BIFV, BIAV. As we will discuss later in Section 6, configuring a large number of issuers can lead to privacy concerns for the clients in the ecosystem. Therefore, we are careful to ensure that the number of issuers is kept strictly bounded by a fixed small number M. The actual issuers can be replaced with different issuers as long as the total never exceeds M. Moreover, issuer replacements also have an effect on client privacy that is similar to when a key rotation occurs, so replacement should only be permitted at similar intervals. See Section 6 for more details about safe choices of M. 6. Privacy analysis In the Privacy Pass protocol [draft-davidson-pp-protocol], redemption tokens intentionally encode no special information into redemption tokens to prevent a vendor from learning anything about the client. We also have cryptographic guarantees via the VOPRF construction that a vendor can learn nothing about a client beyond which issuers trust it. Still there are ways that malicious servers can try and learn identifying information about clients that it interacts with. We discuss a number of privacy considerations relative to the Privacy Pass ecosystem that we are constructing. In addition, we discuss considerations arising from the specific ways of using the Privacy Pass protocol in Section 5. Davidson Expires 10 September 2020 [Page 27] Internet-Draft PP architecture March 2020 6.1. User segregation The goal of the Privacy Pass ecosystem is to construct an environment where can easily measure (and maximize) relative anonymity of any client that is part of it. An inherent feature of being part of this ecosystem is that any client can only remain private relative to the entire space of users using the protocol. In principle, we would hope that the server can link any client redemption to any specific issuance invocation with a probability that is equivalent to guessing. However, in practice, the server can increase this probability using a number of techniques that can segregate the user space into smaller sets. 6.1.1. Server configuration rotation Techniques to introduce segregation are closely linked to the type of key schedule that is used by the server. When a server rotates their key, any client that invokes the issuance protocol shortly afterwards will be part of a small number of possible clients that can redeem. To mechanize this attack strategy, a server could introduce a configuration rotation policy which would force clients into smaller windows where a given config is valid. This would mean that client privacy would only have utility with respect to the smaller group of users that hold redemption data for a particular key window. We RECOMMEND that great care is taken over key rotations, in particular server's should only invoke key rotation for fairly large periods of time such as between 1 and 12 weeks. Key rotations represent a trade-off between client privacy and continued server security. Therefore, it is still important that key rotations occur on a fairly regular cycle to reduce the harmfulness of a server key compromise. As we describe in Section 4, a trusted registries for holding Privacy Pass configurations is required for policing the key schedule that a server uses. Clients may choose to inspect the history of the registry before first accepting redemption tokens from the server. Concrete suggestions include the following: * If a server has updated the registry with many unexpired keys, or in very quick intervals a client SHOULD reject the configuration. The client can check this by checking the list of times when the server modified their own configuration in the vector "modified". This prevents a server from segregating clients into smaller windows using the redemption data that they hold. * If a server has only recently updated their configuration (within the last few minutes), then the client SHOULD refuse to use it. Davidson Expires 10 September 2020 [Page 28] Internet-Draft PP architecture March 2020 This prevents against a server that may try and deanonymize a specific client. 6.1.2. Large numbers of issuers Similarly to the configuration rotation issue raised above, if there are a large number of issuers, similar user segregation can occur. In the BISV, BIFV, BIAV configurations of using the Privacy Pass protocol (Section 5), a verifier OV can trigger redemptions for any of the available issuers. Each redemption token that a client holds essentially corresponds to a bit of information about the client that OV can learn. Therefore, there is an exponential loss in privacy relative to the number of issuers that there are. For example, if there are 32 issuers, then OV learns 32 bits of information about the client. If the distribution of issuer trust is anything close to a uniform distribution, then this is likely to uniquely identify any client amongst all other Internet users. Assuming a uniform distribution is clearly the worst-case scenario, and unlikely to be accurate, but it provides a stark warning against allowing too many issuers at any one time. As we noted in Section 5.4, a strict bound should be applied to the active number of issuers that are allowed at one time in the ecosystem. We propose that allowing no more than 4 issuers at any one time is highly preferable (leading to a maximum of 64 possible user segregations). However, as highlighted in Section 8, having a very large user base (> 5 million users), could potentially allow for larger values (for example, up to 8 issuers). Issuer replacements should only occur with the same frequency as config rotations as they can lead to similar losses in privacy if clients still hold redemption tokens for previously active issuers. In addition, we RECOMMEND that trusted registries indicate at all times which issuers are deemed to be active. If a client is asked to invoke any Privacy Pass exchange for an issuer that is not declared active, then the client SHOULD refuse to retrieve the server configuration during the protocol. 6.1.2.1. Single global configuration authority Any Privacy Pass ecosystem MUST only contain a single global authority for controlling and managing server configurations. This prevents servers from posting different configurations to different global authorities that are all simultaneously trusted by the clients. In such situations, the deanonymization potential would be similar to providing multiple active configurations. Davidson Expires 10 September 2020 [Page 29] Internet-Draft PP architecture March 2020 6.1.2.2. Maximum number of issuers inferred by client We RECOMMEND that clients only store redemption tokens for a fixed number of issuers at any one time. This number would ideally be less than the number of permitted active issuers. This prevents a malicious verifier from being able to invoke redemptions for many issuers since the client would only be holding redemption tokens for a small set of issuers. When a client is issued tokens from a new issuer and already has tokens from the maximum number of issuers, it simply deletes the oldest set of redemption tokens in storage and then stores the newly acquired tokens. 6.2. Tracking and identity leakage While redemption tokens themselves encode no information about the client redeeming them, problems may occur if too many redemptions are allowed in a short burst. For instance, in the Internet setting, this may allow non-terminating verifiers to learn more information from the metadata that the client may hold (such as first-party cookies for other domains). Mitigations for this issue are similar to those proposed in Section 6.1.2 for tackling the problem of having large number of issuers. In SIAV, cached SRRs and their associated issuer public keys have a similar tracking potential to first party cookies in the browser setting. These considerations will be covered in a separate document detailing Privacy Pass protocol integration into the wider web architecture [draft-svaldez-pp-http-api]. 6.3. Client incentives for anonymity reduction Clients may see an incentive in accepting all tokens that are issued by a server, even if the tokens fail later verification checks. This is because tokens effectively represent a form of currency that they can later redeem for some sort of benefit. The verification checks that are put in place are there to ensure that the client does not sacrifice their anonymity. However, a client may judge the "monetary" benefit of owning tokens to be greater than their own privacy. Firstly, none of the interfaces that we have described permit this type of behavior, as they utilize the underlying Privacy Pass API that carries out this verification. A client behaving in this way would not be compliant with the protocol. Davidson Expires 10 September 2020 [Page 30] Internet-Draft PP architecture March 2020 Secondly, acting in this way only affects the privacy of the immediate client. There is an exception if a large number of clients colluded to accept bad data, then any client that didn't accept would be part of a smaller anonymity set. However, such an situation would be identical to the situation where the total number of clients in the ecosystem is small. Therefore, the privacy impact would be equivalent; see Section 6.1.2 for more details. 7. Security considerations We present a number of security considerations that prevent a malicious actors from abusing the protocol. 7.1. Double-spend protection All issuing server should implement a robust storage-query mechanism for checking that tokens sent by clients have not been spent before. Such tokens only need to be checked for each issuer individually. But all issuers must perform global double-spend checks to avoid clients from exploiting the possibility of spending tokens more than once against distributed token checking systems. For the same reason, the global data storage must have quick update times. While an update is occurring it may be possible for a malicious client to spend a token more than once. 7.2. Configuration rotation We highlighted previously that short configuration-cycles can be used to reduce client privacy. However, regular key rotations are still recommended to maintain good server key hygiene. The key material that we consider to be important are: * the Server secret key for issuing Privacy Pass data; * the signing key used to sign configuration information; * the signing key used to sign SRRs in the SIAV configuration. We recommend that Privacy Pass secret keys are rotated from anywhere between 1 and 12 weeks. With an active user-base, a week gives a fairly large window for clients to participate in the Privacy Pass protocol and thus enjoy the privacy guarantees of being part of a larger group. The low ceiling of 12 weeks prevents a key compromise from being too destructive. If a server realizes that a key compromise has occurred then the server should revoke the previous key in the trusted registry and specify a new key to be used. Davidson Expires 10 September 2020 [Page 31] Internet-Draft PP architecture March 2020 For the two signing keys, these should both be well-known keys associated with the issuer. Issuers may choose to use the same key for both signing purposes. The rotation schedules for these keys can be much longer, if necessary. Rotations of these keys results in the creation of a new server identity. 7.3. Token exhaustion When a client holds tokens for an issuer, it is possible for any verifier to invoke that client to redeem tokens for that issuer. This can lead to an attack where a malicious verifier can force a client to spend all of their tokens for a given issuer. To prevent this from happening, methods should be put into place to prevent many tokens from being redeemed at once. For example, it may be possible to cache a redemption for the entity that is invoking a token redemption. In SISV/SIFV, if the verifier requests more tokens then the client simply returns the cached token that it returned previously. This could also be handled by simply not redeeming any tokens for the entity if a redemption had already occurred in a given time window. In SIAV, the client instead caches the SRR that it received in the asynchronous redemption exchange with the issuer. If the same verifier attempts another redemption request, then the client simply returns the cached SRR. The SRRs can be revoked by the issuer, if need be, by providing an expiry date or by signaling that records from a particular window need to be refreshed. 8. Protocol parametrization We provide a summary of the parameters that we use in the Privacy Pass protocol ecosystem. These parameters are informed by both privacy and security considerations that are highlighted in Section 6 and Section 7, respectively. These parameters are intended as a single reference point for those implementing the protocol. Firstly, let U be the total number of users, I be the total number of issuers. Assuming that each user accept tokens from a uniform sampling of all the possible issuers, as a worst-case analysis, this segregates users into a total of 2^I buckets. As such, we see an exponential reduction in the size of the anonymity set for any given user. This allows us to specify the privacy constraints of the protocol below, relative to the setting of A. Davidson Expires 10 September 2020 [Page 32] Internet-Draft PP architecture March 2020 +------------------------------------------+--------------+ | parameter | value | +==========================================+==============+ | Minimum anonymity set size (A) | 5000 | +------------------------------------------+--------------+ | Recommended key lifetime (L) | 2 - 24 weeks | +------------------------------------------+--------------+ | Recommended key rotation frequency (F) | L/2 | +------------------------------------------+--------------+ | Maximum allowed issuers (I) | log_2(U/A)-1 | +------------------------------------------+--------------+ | Maximum active issuance configurations | 1 | +------------------------------------------+--------------+ | Maximum active redemption configurations | 2 | +------------------------------------------+--------------+ | Minimum cryptographic security parameter | 128 bits | +------------------------------------------+--------------+ Table 1 8.1. Justification We make the following assumptions in these parameter choices. * Inferring the identity of a user in a 5000-strong anonymity set is difficult * After 2 weeks, all clients in a system will have rotated to the new key The maximum choice of I is based on the equation 1/2 * U/2^I = A. This is because I issuers lead to 2^I segregations of the total user- base U. By reducing I we limit the possibility of performing the attacks mentioned in Section 6.1. We must also account for each user holding issued data for more then one possible active keys. While this may also be a vector for monitoring the access patterns of clients, it is likely to unavoidable that clients hold valid issuance data for the previous key epoch. This also means that the server can continue to verify redemption data for a previously used key. This makes the rotation period much smoother for clients. For privacy reasons, it is recommended that key epochs are chosen that limit clients to holding issuance data for a maximum of two keys. By choosing F = L/2 then the minimum value of F is a week, since the minimum recommended value of L is 2 weeks. Therefore, by the initial assumption, then all users should only have access to Davidson Expires 10 September 2020 [Page 33] Internet-Draft PP architecture March 2020 only two keys at any given time. This reduces the anonymity set by another half at most. Finally, the minimum security parameter size is related to the cryptographic security offered by the protocol that is run. This parameter corresponds to the number of operations that any adversary has in breaking one of the security guarantees in the Privacy Pass protocol [draft-davidson-pp-protocol]. The existing protocol document contains an instantiation based on verifiable oblivious pseudorandom functions (VOPRFs) [I-D.irtf-cfrg-voprf]. Careful attention should be paid to whether the available ciphersuites for a protocol instantiation meets this criteria. 8.2. Example parameterization Using the specification above, we can give some example parameterizations. For example, the current Privacy Pass browser extension [PPEXT] has over 150,000 active users (from Chrome and Firefox). As a result, log_2(U/A) is approximately 5 and so the maximum value of I should be 4. If the value of U is much bigger (e.g. 5 million) then this would permit I = log_2(5000000/5000)-1 = 8 issuers. 9. Recommendations for identifying malicious behavior TODO: Come up with an effective deterrent for server's that are deemed to misbehave by a client. Could we have a separate consensus where clients can upload misbehavior references for servers that they deem to be malicious? 10. Extension integration policy The Privacy Pass protocol and ecosystem are both intended to be receptive to extensions that expand the current set of functionality. In [draft-davidson-pp-protocol], some points are made about how implementing the Privacy Pass API can be instantiated using different underlying primitives. The interfaces described in Section 3 utilize the API in such a way that internal changes should result in no visible change to implementers of the Privacy Pass protocol. As specified in [draft-davidson-pp-protocol], all extensions to the Privacy Pass protocol SHOULD be specified as separate documents that modify the content of this document in some way. We provide guidance on the type of modifications that are possible in the following. Aside from the underlying protocol, extensions MAY modify the protocol interfaces from the definition in this document. Such Davidson Expires 10 September 2020 [Page 34] Internet-Draft PP architecture March 2020 extensions MUST document exactly which interfaces are changed and any new message formats that arise. Any such extension should also come with a detailed analysis of the privacy impacts of the extension, why these impacts are justified, and guidelines on changes to the parametrization in Section 8. Similarly, extensions MAY also add new Server running modes, if applicable, to those that are documented in Section 5. We RECOMMEND that any extension to the Privacy Pass architecture does not add new interfaces to those that are listed in Section 3. We expect that any extension is expressible using the interfaces themselves and reimplementing the existing functionality, if need be. Abiding by this policy maintains a simplified execution chain that is easy to reason about. Extensions MUST NOT modify the format and/or structure of the global configuration registry, other than specifying the data format of each of the fields that are used. If an extension requires a modified configuration registry, then such a change is interpreted to lie outside of the Privacy Pass ecosystem, and is thus not supported. 11. Existing applications The following is a non-exhaustive list of applications that currently make use of the Privacy Pass protocol, or some variant of the underlying functionality. 11.1. Cloudflare challenge pages Cloudflare uses an implementation of the Privacy Pass protocol for allowing clients that have previously interacted with their Internet challenge protection system to bypass future challenges [PPSRV]. These challenges can be expensive for clients, and there have been cases where bugs in the implementations can severely degrade client accessibility. Clients must install a browser extension [PPEXT] that acts as the Privacy Pass client in an exchange with Cloudflare's Privacy Pass server, when an initial challenge solution is provided. The client extension stores the issued tokens and presents a valid redemption token when it sees future Cloudflare challenges. If the redemption token is verified by the server, the client passes through the security mechanism without completing a challenge. Davidson Expires 10 September 2020 [Page 35] Internet-Draft PP architecture March 2020 11.2. Trust Token API The Trust Token API [TRUST] has been devised as a generic API for providing Privacy Pass functionality in the browser setting. The API is intended to be implemented directly into browsers so that server's can directly trigger the Privacy Pass workflow. 11.3. Zero-knowledge Access Passes The PrivateStorage API developed by Least Authority is a solution for uploading and storing end-to-end encrypted data in the cloud. A recent addition to the API [PrivateStorage] allows clients to generate Zero-knowledge Access Passes (ZKAPs) attesting to the fact that the client has paid for the storage space that it is using. The ZKAP protocol is based heavily on the Privacy Pass redemption mechanism. The client receives ZKAPs when it pays for storage space, and redeems the passes when it interacts with the PrivateStorage API. 11.4. Basic Attention Tokens The browser Brave uses Basic Attention Tokens (BATs) to provide the basis for a privacy-preserving rewards scheme [Brave]. The BATs are essentially Privacy Pass redemption tokens that are provided by a central Brave server when a client performs some action that triggers a reward event (such as watching an advertisement). When the client amasses BATs, it can redeem them with the Brave central server for rewards. 11.5. Token Based Services Similarly to BATs, a more generic approach for providing anonymous peers to purchase resources from anonymous servers has been proposed [OpenPrivacy]. The protocol is based on a variant of Privacy Pass and is intended to allow clients purchase (or pre-purchase) services such as message hosting, by using Privacy Pass redemption tokens as a form of currency. This is also similar to how ZKAPs are used. 12. References 12.1. Normative References [draft-davidson-pp-protocol] Davidson, A., "Privacy Pass: The Protocol", n.d., . [draft-svaldez-pp-http-api] Valdez, S., "Privacy Pass: HTTP API", n.d., Davidson Expires 10 September 2020 [Page 36] Internet-Draft PP architecture March 2020 . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, . [X9.62] Institute, A.N.S., "Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)", ANSI X9.62-2005 , November 2005. 12.2. Informative References [Brave] "Brave Rewards", n.d., . [I-D.irtf-cfrg-voprf] Davidson, A., Sullivan, N., and C. Wood, "Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups", Work in Progress, Internet-Draft, draft-irtf-cfrg-voprf- 02, 4 November 2019, . [keytrans] "Security Through Transparency", n.d., . [OpenPrivacy] "Token Based Services - Differences from PrivacyPass", n.d., . [PPEXT] "Privacy Pass Browser Extension", n.d., . [PPSRV] Sullivan, N., "Cloudflare Supports Privacy Pass", n.d., . [PrivateStorage] Steininger, L., "The Path from S4 to PrivateStorage", Davidson Expires 10 September 2020 [Page 37] Internet-Draft PP architecture March 2020 n.d., . [TRUST] WICG, ., "Trust Token API", n.d., . Appendix A. Message formats We detail an exhaustive list of the different message types used in the Privacy Pass protocol. These messages are sent and received by the interfaces detailed in Section 3. We intend for the messages to be compatible typical message expression formats such as JSON. A.1. Server messages A.1.1. server_config_store struct { ServerConfig configs[2]; } server_config_store A.1.2. server_config_retrieve struct { uint8 method; ServerConfig configs[2]; } server_config_retrieve A.1.3. server_hello struct { opaque server_id<0..255>; uint8 supports; } server_hello A.1.4. server_issue_resp struct { IssuanceResponse data; } server_issue_resp A.1.5. server_redeem_resp struct { RedemptionResponse data; } server_redeem_resp Davidson Expires 10 September 2020 [Page 38] Internet-Draft PP architecture March 2020 A.2. Client message formats A.2.1. client_issue_generation struct { opaque server_id<0..255>; ServerUpdate config; } client_issue_generation A.2.2. client_issue_storage struct { opaque server_id<0..255> Ciphersuite ciphersuite; opaque comm_id<0..2^16-1>; ClientIssuanceProcessing client_data; } client_issue_storage A.2.3. client_issue struct { opaque client_id<0..2^16-1>; IssuanceMessage issue_data; } client_issue A.2.4. client_issue_retrieval struct { opaque server_id<0..255>; Ciphersuite ciphersuite; opaque comm_id<0..2^16-1>; } client_issue_retrieval A.2.5. client_issue_retrieval_resp struct { ClientIssuanceProcessing client_data; } client_issue_retrieval_resp A.2.6. client_token_storage struct { opaque server_id<0..255>; Ciphersuite ciphersuite; opaque comm_id<0..2^16-1>; RedemptionToken tokens[m]; } client_token_storage Davidson Expires 10 September 2020 [Page 39] Internet-Draft PP architecture March 2020 A.2.7. client_token_retrieval struct { opaque server_id<0..255>; Ciphersuite ciphersuite; opaque comm_id<0..2^16-1>; } client_token_retrieval A.2.8. client_token_retrieval_resp method: "client_token_retrieval_resp" struct { RedemptionToken token; } client_token_retrieval_resp A.2.9. client_redeem_generation struct { opaque server_id<0..255>; ServeUpdate config; RedemptionToken token; } client_redeem_generation A.2.10. client_redeem struct { opaque client_id<0..2^16-1>; RedemptionMessage message; } client_redeem A.3. Global configuration interfaces A.3.1. config_update struct { opaque server_id<0..255>; opaque comm_id<0..2^16-1>; ServerUpdate config; datetime expiry; opaque signature<1..2^32-1>; } config_update A.3.2. config_retrieval struct { opaque server_id<0..255>; } config_retrieval Davidson Expires 10 September 2020 [Page 40] Internet-Draft PP architecture March 2020 A.3.3. config_retrieval_resp struct { Ciphersuite ciphersuite; opaque comm_id<0..2^16-1>; ServerUpdate config; datetime expiry; opaque signature<1..2^32-1>; uint8 supports; } config_entry struct { config_entry configs[2]; } config_retrieval_resp Author's Address Alex Davidson Cloudflare Portugal Largo Rafael Bordalo Pinheiro 29 Lisbon Portugal Email: alex.davidson92@gmail.com Davidson Expires 10 September 2020 [Page 41]