idnits 2.17.1 draft-davidson-pp-architecture-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) == There are 2 instances of lines with non-RFC2606-compliant FQDNs in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (9 March 2020) is 1508 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 701 -- Looks like a reference, but probably isn't: '1' on line 682 -- Looks like a reference, but probably isn't: '2' on line 1852 == Outdated reference: A later version (-21) exists of draft-irtf-cfrg-voprf-02 Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Davidson 3 Internet-Draft Cloudflare Portugal 4 Intended status: Informational 9 March 2020 5 Expires: 10 September 2020 7 Privacy Pass: Architectural Framework 8 draft-davidson-pp-architecture-00 10 Abstract 12 This document specifies the architectural framework for constructing 13 secure and privacy-preserving instantiations of the Privacy Pass 14 protocol (as described in [draft-davidson-pp-protocol]). The 15 framework refers to the entire ecosystem of Privacy Pass clients and 16 servers. This document makes recommendations on how this ecosystem 17 should be constructed to ensure the privacy of clients and the 18 security of all participating entities. 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at https://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on 10 September 2020. 37 Copyright Notice 39 Copyright (c) 2020 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 44 license-info) in effect on the date of publication of this document. 45 Please review these documents carefully, as they describe your rights 46 and restrictions with respect to this document. Code Components 47 extracted from this document must include Simplified BSD License text 48 as described in Section 4.e of the Trust Legal Provisions and are 49 provided without warranty as described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 54 1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 55 1.2. Layout . . . . . . . . . . . . . . . . . . . . . . . . . 5 56 2. Architectural ecosystem assumptions . . . . . . . . . . . . . 6 57 2.1. Servers . . . . . . . . . . . . . . . . . . . . . . . . . 6 58 2.1.1. Long-term signing . . . . . . . . . . . . . . . . . . 7 59 2.2. Clients . . . . . . . . . . . . . . . . . . . . . . . . . 7 60 2.3. Global configuration store . . . . . . . . . . . . . . . 8 61 3. Protocol integration policy . . . . . . . . . . . . . . . . . 8 62 3.1. Recap: Protocol API . . . . . . . . . . . . . . . . . . . 9 63 3.2. Server interfaces . . . . . . . . . . . . . . . . . . . . 9 64 3.2.1. SERVER_KEY_GEN . . . . . . . . . . . . . . . . . . . 9 65 3.2.2. SERVER_STORE_CONFIG . . . . . . . . . . . . . . . . . 10 66 3.2.3. SERVER_CONFIG_RETRIEVAL . . . . . . . . . . . . . . . 11 67 3.2.4. SERVER_HELLO . . . . . . . . . . . . . . . . . . . . 11 68 3.2.5. SERVER_ISSUE . . . . . . . . . . . . . . . . . . . . 12 69 3.2.6. SERVER_REDEEM . . . . . . . . . . . . . . . . . . . . 13 70 3.2.7. SERVER_DOUBLE_SPEND_CHECK . . . . . . . . . . . . . . 13 71 3.2.8. SERVER_DOUBLE_SPEND_STORE . . . . . . . . . . . . . . 14 72 3.3. Client interfaces . . . . . . . . . . . . . . . . . . . . 14 73 3.3.1. CLIENT_CONFIG_RETRIEVAL . . . . . . . . . . . . . . . 14 74 3.3.2. CLIENT_ISSUE_GEN . . . . . . . . . . . . . . . . . . 16 75 3.3.3. CLIENT_ISSUE_FINISH . . . . . . . . . . . . . . . . . 16 76 3.3.4. CLIENT_REDEEM . . . . . . . . . . . . . . . . . . . . 17 77 3.3.5. CLIENT_ISSUE_STORAGE . . . . . . . . . . . . . . . . 18 78 3.3.6. CLIENT_ISSUE_RETRIEVAL . . . . . . . . . . . . . . . 18 79 3.3.7. CLIENT_TOKEN_STORAGE . . . . . . . . . . . . . . . . 18 80 3.3.8. CLIENT_TOKEN_RETRIEVAL . . . . . . . . . . . . . . . 18 81 3.4. Global configuration registry interfaces . . . . . . . . 19 82 3.4.1. GLOBAL_CONFIG_UPDATE . . . . . . . . . . . . . . . . 19 83 3.4.2. GLOBAL_CONFIG_RETRIEVAL . . . . . . . . . . . . . . . 20 84 4. Key management framework . . . . . . . . . . . . . . . . . . 21 85 4.1. Global configuration . . . . . . . . . . . . . . . . . . 22 86 4.2. Configuration structure . . . . . . . . . . . . . . . . . 22 87 4.3. Configuration updates #{config-update} . . . . . . . . . 24 88 4.4. Client retrieval . . . . . . . . . . . . . . . . . . . . 24 89 4.5. Key revocation . . . . . . . . . . . . . . . . . . . . . 25 90 5. Server running modes . . . . . . . . . . . . . . . . . . . . 25 91 5.1. Single-Issuer Single-Verifier . . . . . . . . . . . . . . 25 92 5.2. Single-Issuer Forwarding-Verifier . . . . . . . . . . . . 26 93 5.3. Single-Issue Asynchronous-Verifier . . . . . . . . . . . 26 94 5.4. Bounded-Issuers . . . . . . . . . . . . . . . . . . . . . 27 95 6. Privacy analysis . . . . . . . . . . . . . . . . . . . . . . 27 96 6.1. User segregation . . . . . . . . . . . . . . . . . . . . 28 97 6.1.1. Server configuration rotation . . . . . . . . . . . . 28 98 6.1.2. Large numbers of issuers . . . . . . . . . . . . . . 29 99 6.2. Tracking and identity leakage . . . . . . . . . . . . . . 30 100 6.3. Client incentives for anonymity reduction . . . . . . . . 30 101 7. Security considerations . . . . . . . . . . . . . . . . . . . 31 102 7.1. Double-spend protection . . . . . . . . . . . . . . . . . 31 103 7.2. Configuration rotation . . . . . . . . . . . . . . . . . 31 104 7.3. Token exhaustion . . . . . . . . . . . . . . . . . . . . 32 105 8. Protocol parametrization . . . . . . . . . . . . . . . . . . 32 106 8.1. Justification . . . . . . . . . . . . . . . . . . . . . . 33 107 8.2. Example parameterization . . . . . . . . . . . . . . . . 34 108 9. Recommendations for identifying malicious behavior . . . . . 34 109 10. Extension integration policy . . . . . . . . . . . . . . . . 34 110 11. Existing applications . . . . . . . . . . . . . . . . . . . . 35 111 11.1. Cloudflare challenge pages . . . . . . . . . . . . . . . 35 112 11.2. Trust Token API . . . . . . . . . . . . . . . . . . . . 36 113 11.3. Zero-knowledge Access Passes . . . . . . . . . . . . . . 36 114 11.4. Basic Attention Tokens . . . . . . . . . . . . . . . . . 36 115 11.5. Token Based Services . . . . . . . . . . . . . . . . . . 36 116 12. References . . . . . . . . . . . . . . . . . . . . . . . . . 36 117 12.1. Normative References . . . . . . . . . . . . . . . . . . 36 118 12.2. Informative References . . . . . . . . . . . . . . . . . 37 119 Appendix A. Message formats . . . . . . . . . . . . . . . . . . 38 120 A.1. Server messages . . . . . . . . . . . . . . . . . . . . . 38 121 A.1.1. server_config_store . . . . . . . . . . . . . . . . . 38 122 A.1.2. server_config_retrieve . . . . . . . . . . . . . . . 38 123 A.1.3. server_hello . . . . . . . . . . . . . . . . . . . . 38 124 A.1.4. server_issue_resp . . . . . . . . . . . . . . . . . . 38 125 A.1.5. server_redeem_resp . . . . . . . . . . . . . . . . . 38 126 A.2. Client message formats . . . . . . . . . . . . . . . . . 39 127 A.2.1. client_issue_generation . . . . . . . . . . . . . . . 39 128 A.2.2. client_issue_storage . . . . . . . . . . . . . . . . 39 129 A.2.3. client_issue . . . . . . . . . . . . . . . . . . . . 39 130 A.2.4. client_issue_retrieval . . . . . . . . . . . . . . . 39 131 A.2.5. client_issue_retrieval_resp . . . . . . . . . . . . . 39 132 A.2.6. client_token_storage . . . . . . . . . . . . . . . . 39 133 A.2.7. client_token_retrieval . . . . . . . . . . . . . . . 40 134 A.2.8. client_token_retrieval_resp . . . . . . . . . . . . . 40 135 A.2.9. client_redeem_generation . . . . . . . . . . . . . . 40 136 A.2.10. client_redeem . . . . . . . . . . . . . . . . . . . . 40 137 A.3. Global configuration interfaces . . . . . . . . . . . . . 40 138 A.3.1. config_update . . . . . . . . . . . . . . . . . . . . 40 139 A.3.2. config_retrieval . . . . . . . . . . . . . . . . . . 40 140 A.3.3. config_retrieval_resp . . . . . . . . . . . . . . . . 41 141 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 41 143 1. Introduction 145 The Privacy Pass protocol provides a privacy-preserving mechanism for 146 authorization of clients with servers. The protocol is detailed in 147 [draft-davidson-pp-protocol] and is intended for use in performance- 148 critical settings, such as while browsing the Internet. 150 The way that the ecosystem around the protocol is set up can have 151 significant impacts on the stated privacy and security guarantees of 152 the protocol. For instance, the number of servers issuing Privacy 153 Pass tokens, along with the number of registered clients, determines 154 the privacy budget available to each individual client. This can be 155 further influenced by other factors, such as: the key rotation policy 156 used by each server; and, the number of supported ciphersuites. 157 There are also client-behavior patterns that can reduce the effective 158 security of the server. 160 In this document, we will provide a structural framework for building 161 the ecosystem around the Privacy Pass protocol. Firstly, it will 162 identify a number of common interfaces for integrating the Privacy 163 Pass protocol and the API detailed in [draft-davidson-pp-protocol]. 164 The API in the protocol document represents a basic one-on-one 165 exchange between a client and a server. The interfaces that we 166 describe in this document reproduce this API into the setting where 167 clients and servers are part of a wider ecosystem. 169 On top of this, the document also includes policies for the following 170 considerations: 172 * How server configurations and key material should be stored and 173 rotated in an open and transparent manner. 175 * Compatible server issuance and redemption running modes and 176 associated expectations. 178 * A concrete assessment and parametrization of the privacy budget 179 associated with different settings of the above policies. 181 * Recommendations for identifying malicious server behavior. 183 * Assessment of client incentives for eschewing privacy features. 185 * The incorporation of potential extensions into the wider 186 ecosystem. 188 Finally, we will discuss existing applications that make use of the 189 Privacy Pass protocol, and highlight how these may fit with the 190 proposed framework. 192 1.1. Terminology 194 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 195 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 196 document are to be interpreted as described in [RFC2119]. 198 The following terms are used throughout this document. 200 * Server: A service that provides access to a certain resource 201 (typically denoted S) 203 * Client: An entity that seeks authorization from a server 204 (typically denoted C) 206 * Key: Server's secret key 208 * Config: The server configuration associated with the key material 209 and ciphersuite choices that it makes. 211 We assume that all protocol messages are encoded into raw byte format 212 before being sent. We use the TLS presentation language [RFC8446] to 213 describe the structure of the data that is communicated and stored. 215 1.2. Layout 217 * Section 2: Describes the basic assumptions that we make in this 218 document on the shape and topology of the Privacy Pass ecosystem: 219 the environment in which Privacy Pass supporting clients and 220 servers interact with each other. 222 * Section 3: Describes the policy and framework for building 223 interoperable client and server implementations. Also provides 224 the necessary foundations for interacting with the global 225 configuration registry. 227 * Section 4: Describes the structure of server key configurations 228 and how this configuration is retrieved and updated. 230 * Section 5: Describes the different running modes that are 231 currently expected from Privacy Pass servers. 233 * Section 6: An analysis of the characteristics of the Privacy Pass 234 architecture that have an impact on the privacy of clients 235 participating in the ecosystem. 237 * Section 7: An analysis of the security characteristics of the 238 protocol when viewed as a part of the wider architecture of the 239 protocol ecosystem. Includes discussions of the cases for both 240 servers and clients. 242 * Section 8: Provides an example parametrization of the privacy and 243 security parameters that are associated with the protocol, based 244 on the previous discussions. 246 * Section 9: Recommendations for identifying and highlighting 247 potential malicious behavior by a server. 249 * Section 10: Describes the policy for writing extensions to the 250 Privacy Pass protocol, and how they may be incorporated into the 251 wider architecture. 253 * Section 11: A non-exhaustive list of the applications that make 254 use of the Privacy Pass protocol, or some variant of it. 256 2. Architectural ecosystem assumptions 258 The Privacy Pass ecosystem refers to the global framework in which 259 multiple instances of the Privacy Pass protocol operate. This refers 260 to all servers that support the protocol, or any extension of it, 261 along with all of the clients that may interact with these servers. 262 Moreover, there is a singular public entity known as the 'global 263 configuration registry'. This registry presents the public 264 information related to all supported server key material. This is 265 required to enable the client to process issuance responses from each 266 of the available servers. 268 The ecosystem itself, and the way it is constructed, is critical for 269 evaluating the privacy of each individual client. We assume that a 270 client's privacy refers to fraction of users that it represents in 271 the anonymity set that it belongs to. We discuss this more in 272 Section 6. 274 2.1. Servers 276 Servers in the Privacy Pass ecosystem are entities whose primary 277 function is to undertake the role of the "Server" in 278 [draft-davidson-pp-protocol]. To facilitate this, the server must 279 hold the following data at any given time: 281 * a valid server configuration ("ServerConfig") as specified in 282 [draft-davidson-pp-protocol]; 284 * a long-term signing key pair for a signature scheme "sig_alg"; 285 * storage of Privacy Pass tokens that have been previously redeemed 286 with the server. 288 The server must be available at a specified address (uniquely 289 identified by "server_id") that accepts communications from Privacy 290 Pass clients Section 2.2 on the interfaces defined in Section 3.2. 291 When the server wants to update its configuration, it communicates 292 with the global configuration registry Section 2.3. 294 2.1.1. Long-term signing 296 The long-term signing key pair "(k_sign, k_vrfy)" is used to sign 297 configuration data that is sent to the global configuration registry. 298 The server must prove to the global key configuration registry the 299 veracity of the long-term key-pair that it uses. This key pair is 300 attached to the configuration that it maintains. We assume the 301 following functional API: 303 * "sig = sig_alg.sign(k_sign, data)": produces a signature "sig" 304 using the signing key, "k_sign", over the bytes of "data". 306 * "b = sig_alg.verify(k_vrfy, data, sig)": produces a boolean result 307 "b" indicating that "sig" is a valid signature over "data" using 308 the signing key "k_sign". 310 As per usual, we assume that any signature produced by the ".sign" 311 function produces a result of "true" when verifying using ".verify". 312 Likewise, the scheme should also satisfy the well-known security 313 property of existential unforgeability. Valid instantiations include 314 DSA (and ECDSA) [X9.62]. 316 2.2. Clients 318 Clients in the Privacy Pass ecosystem are entities whose primary 319 function is to undertake the role of the "Client" in 320 [draft-davidson-pp-protocol]. The clients are assumed to only store 321 data related to the tokens that it has been issued by the server. 322 This storage is used for constructing redemption requests, see the 323 "CLIENT_REDEEM" interface (Section 3.3.4) for more details. 325 The clients must also have access to the global config store 326 Section 2.3. This is so that the client can retrieve data related to 327 the configuration of the server that it is communicating with. 329 Each client must be addressed by a unique identifier, given by 330 "client_id". 332 2.3. Global configuration store 334 The global configuration store controls all the configuration data 335 that is used by the servers that are part of the Privacy Pass 336 ecosystem. This data is required to allow clients to verify server 337 issuance responses. The server configuration data corresponds to all 338 the ciphersuites and key fingerprints that have ever been used, by 339 every server in the Privacy Pass ecosystem. 341 The config store is an append-only database that supports revocation 342 of old configurations. This is done by limiting the number of active 343 configurations that a server can use at any given time. It should be 344 available at a publicly-broadcasted address so that both clients and 345 servers can access it. The database should preserve its history in 346 an audit-friendly manner. 348 The way that the config store is implemented can have a dramatic 349 effect on the privacy of the clients in the Privacy Pass protocol. 350 We describe in detail how such a store should be implemented in 351 Section 4. 353 3. Protocol integration policy 355 We provide a number of common interfaces that both the clients and 356 servers implement. These interfaces should be contactable by 357 entities in the ecosystem, and provide a framework for generating and 358 processing data in the Privacy Pass protocol. The framework provides 359 a policy that states that these interfaces be implemented (for 360 example, by clients and servers) to be considered valid entities in 361 the Privacy Pass ecosystem. The interfaces wrap the Privacy Pass API 362 functions detailed in [draft-davidson-pp-protocol] to provide 363 functionality in the many-many ecosystem consisting of clients and 364 servers. 366 The interfaces have three configurable fields. The "Visibility" 367 field indicates that the interface is either contactable externally 368 ("external") or that it is activated internally by the entity at some 369 point ("internal"). The "Input" field determines valid input types 370 of that are received by the interface. The "Returns" field provides 371 the return type of the function. The "Steps" field notes high-level 372 steps to be taken when the interface is contacted. 374 Note: currently we live the implementation of errors up to the 375 implementer. By default, if any internal Privacy Pass protocol 376 function (Section 3.1) throws an error, then the interface should 377 panic. More fine-grained error reporting may be added in future 378 versions of this draft. 380 3.1. Recap: Protocol API 382 The protocol document [draft-davidson-pp-protocol] specifically 383 details a number of public API functions that are used for 384 constructing the generic protocol. These functions can be split into 385 server and client functionality. 387 1. Server functionality: 389 * "PP_Server_Setup": Generates server configuration and keys 391 * "PP_Issue": Run on the contents of the client message in the 392 issuance phase. 394 * "PP_Verify": Run on the contents of the client message in the 395 redemption phase. 397 2. Client functionality: 399 * "PP_Client_Setup": Generates the client configuration based on 400 the configuration used by a given server. 402 * "PP_Generate": Generates public and private data associated 403 with the contents of the client message in the issuance phase. 405 * "PP_Process": Processes the contents of the server response in 406 the issuance phase. 408 * "PP_Redeem": Generates the data that forms the client message 409 in the redemption phase. 411 We will use each of the functions internally in the description of 412 the interfaces that follows. 414 3.2. Server interfaces 416 Any implementation of a Privacy Pass Server MUST implement the 417 following contact points or interfaces. When the Server is contacted 418 on these interfaces with the required input data, it should take the 419 steps detailed. The inputs and responses for each of the interfaces 420 correspond to the data structures defined in 421 [draft-davidson-pp-protocol]. 423 3.2.1. SERVER_KEY_GEN 425 * Visibility: "internal" 426 * Input: a string, "id", corresponding to a ciphersuite identifier 427 (see [draft-davidson-pp-protocol] for valid configurations). 429 * Returns: a boolean "b", indicating success. 431 * Steps: 433 1. Run "(cfg, update) = PP_Server_Setup(id)". 435 2. Construct a "config_update" message. 437 3. The value "" is the unique identifier for the 438 Server. 440 4. The value of "" should be a point in the future 441 within the window of allowed key rotation lengths (for 442 example, those specified in Section 8). 444 5. The value "" is a string used to distinguish between 445 config entries corresponding to the same config, but where 446 the key material has changed (e.g. after a key rotation). 448 6. The value of "" should be set to an octet 449 corresponding to the functionality that is provided. The 450 value "0" indicates that no functionality is supported; "1" 451 indicates that the server supports the issuance phase; "2" 452 indicates support for the redemption phase; and "3" indicates 453 support for both phases. If unspecified, this defaults to 454 "3". 456 7. The value of "" is set to be equal to "update". 458 8. The value "" is computed over the bytes of the 459 rest of message contents, using the Server long-term secret 460 signing key "k_sign". This can be computed by running: 462 data = .. .. .. 463 = sig_alg.sign(k_sign, data) 465 9. Send the "config_update" message to the 466 "GLOBAL_CONFIG_UPDATE" interface. 468 10. Send a "server_config_store" message to the 469 "SERVER_STORE_CONFIG" interface containing the value of 470 "cfg". 472 3.2.2. SERVER_STORE_CONFIG 473 * Visibility: "internal" 475 * Input: a "server_config_store" message "msg" (Appendix A.1.1). 477 * Returns: "null" 479 * Steps: 481 1. Let "ex_cfg" correspond to the existing "ServerConfig" object 482 keyed by "issue". 484 2. Store the bytes of "msg.config" in local storage, against the 485 key "issue". 487 3. Store the bytes of "ex_cfg" in local storage against the key 488 "redeem". 490 3.2.3. SERVER_CONFIG_RETRIEVAL 492 * Visibility: "internal" 494 * Input: an octet "method" in "{1,2,3}". 496 * Returns: A "server_config_retrieve" message "resp" 497 (Appendix A.1.2). 499 * Steps: 501 1. Let "storage" be the ID and the bytes of the server config 502 currently stored in local storage, respectively. 504 2. If "resp.config.supports != method && resp.config.supports != 505 3", then return "null". 507 3. Let "resp" be a "server_config_retrieve" message, where 508 "=[config]" for "config" stored in local storage 509 against "issue". 511 4. If "method == 2", append "ex_config" to "", where 512 "ex_config" is stored in local storage against the key 513 "redeem". 515 5. Return "resp". 517 3.2.4. SERVER_HELLO 519 * Visibility: "external" 520 * Input: a string, "client_addr", corresponding to an address that 521 the client can be contacted on. 523 * Return: "null" 525 * Steps: 527 1. Send an empty message to the internal 528 "SERVER_CONFIG_RETRIEVAL" interface, and let 529 "cfgs=resp.configs" based on the "server_config_retrieve" 530 response "resp". 532 2. Send a "server_hello" message to the "CLIENT_CONFIG_RETRIEVAL" 533 interface for the client at "client_addr". The "server_hello" 534 message must satisfy the following: 536 1. The value "=server_id" is the unique identifier 537 for the Server. 539 2. The value of "" MUST be set to an octet 540 corresponding to the supported methods. 542 3.2.5. SERVER_ISSUE 544 * Visibility: "external" 546 * Input: A "client_issue" message "msg" (Appendix A.2.3) 548 * Returns: A "server_issue_resp" message 550 * Steps: 552 1. Send the message "issue" to the internal 553 "SERVER_CONFIG_RETRIEVAL" interface, and let 554 "ciphersuite=msg.ciphersuites[0]" and "srv_cfg=msg.configs[0]" 555 based on the "server_config_retrieve" response. 557 2. Run the following: 559 issue_resp = PP_Issue(srv_cfg, msg.issue_data) 561 3. Returns a "server_issue_resp" message with "=issue_resp" 562 message back to the caller "CLIENT_ISSUE_GEN" interface of the 563 client associated with "client_issue.client_id". 565 3.2.6. SERVER_REDEEM 567 * Visibility: "external" 569 * Input: A "client_redeem" message "msg" (Appendix A.2.10) 571 * Returns: A "server_redeem_resp" message back to the calling 572 "CLIENT_REDEEM" interface (Appendix A.1.5). 574 * Steps: 576 1. Send the message "redeem" to the internal 577 "SERVER_CONFIG_RETRIEVAL" interface, let "configs" be the 578 returned array. 580 2. Send "msg.message.data" to the "SERVER_DOUBLE_SPEND_CHECK" 581 interface and, if the response is "true", return an 582 unsuccessful "server_redeem_resp" message to the client. 584 3. Run the following: 586 resp = PP_Verify(configs[0],message) 587 if (!resp.success) { 588 resp = PP_Verify(configs[1],message) 589 } 591 4. Send "msg.message.data" to the "SERVER_DOUBLE_SPEND_STORE" 592 interface. 594 5. The Server returns a "server_redeem_resp" message, with 595 "=resp" back to the "CLIENT_REDEEM" interface of the 596 client associated with "client_redeem.client_id". 598 3.2.7. SERVER_DOUBLE_SPEND_CHECK 600 * Visibility: "internal" 602 * Input: A byte string "data" of type "opaque<1..2^32-1>" 603 (Appendix A.2.10). 605 * Returns: A boolean value "b". 607 * Steps: 609 1. Return "true" if "data" exists in the double-spend index, and 610 "false" otherwise. 612 3.2.8. SERVER_DOUBLE_SPEND_STORE 614 * Visibility: "internal" 616 * Input: A byte string "data" of type "opaque<1..2^32-1>" 617 (Appendix A.2.10). 619 * Returns: "null". 621 * Steps: 623 1. Store "data" in the double-spend index. 625 3.3. Client interfaces 627 The following interfaces MUST be implemented for any implementation 628 of a Client in the Privacy Pass ecosystem (Section 2.2). 630 3.3.1. CLIENT_CONFIG_RETRIEVAL 632 * Visibility: "external" 634 * Input: a "server_hello" message type denoted by "msg", 635 (Appendix A.1.3). 637 * Return: a boolean, indicating whether the config was successfully 638 retrieved. 640 * Steps: 642 1. Construct a "config_retrieval" message using 643 "=msg.server_id". 645 2. Send the "config_retrieval" message to the 646 "GLOBAL_CONFIG_RETRIEVAL" interface, and receive a reply 647 "resp" of type "config_retrieval_resp". 649 3. If "success" is set to "false", return "false". 651 4. Parse "resp[0].supports" and check that it includes support 652 for what is specified in "msg.supports", otherwise return 653 false. 655 5. Parse "resp[1].supports" and check that it includes support 656 for what is specified in "msg.supports", otherwise return 657 false. 659 6. The value "" is verified over the bytes of the 660 rest of message contents, using the Server long-term 661 verification key "k_vrfy". This can be computed by running 662 the function below and checking that "ret==true", otherwise 663 returning false. 665 data = .. .. 666 .. .. .. 667 ret = sig_alg.verify(k_vrfy, data, ) 669 7. Construct a "client_token_retrieval" where 671 ciphersuite = resp[0].ciphersuite 672 comm_id = resp[0].comm_id 674 and send it to the "CLIENT_TOKEN_RETRIEVAL" interface. 675 Receive back "token" in a "client_token_retrieval_resp" 676 message. Set "config_idx=0". 678 8. If "token == null", construct a "client_token_retrieval" 679 message where: 681 ciphersuite = resp[1].ciphersuite 682 comm_id = resp[1].comm_id 684 and send it to the "CLIENT_TOKEN_RETRIEVAL" interface. 685 Receive back "token" in a "client_token_retrieval_resp" 686 message. Set "config_idx=1'". 688 9. If: 690 token == null 691 && ( 692 resp[0].supports == 1 693 || resp[0].supports == 3 694 ) 696 construct a "client_issue_generation" message and send it to 697 the "CLIENT_ISSUE_GEN" interface, with: 699 1. " = msg.server_id"; 701 2. " = resp[0].config"; 703 10. If: 705 ~~~ token != null && ( resp[config_type].supports == 2 || 706 resp[config_type].supports == 3 ) ~~~ 707 construct a "client_redeem_generation" message and send it to the 708 "CLIENT_REDEEM" interface. with: 710 1. ` = msg.server_id`; 711 2. ` = token`; 713 1. If neither condition in (7) or (8) is satisfied, return false. 715 2. Return true. 717 3.3.2. CLIENT_ISSUE_GEN 719 * Visibility: "internal" 721 * Input: a message "msg" of type "client_issue_generation" 722 (Appendix A.2.1). 724 * Returns: "null" 726 * Steps: 728 1. The client runs: 730 cli_cfg = PP_Client_Setup(msg.ciphersuite, msg.config) 732 2. The client runs: 734 issue_input = PP_Generate(cli_cfg, m) 736 where "m" is an integer corresponding to the number of tokens 737 that should be generated. 739 3. The client constructs a "client_issue_storage" message and 740 sends it to the "CLIENT_ISSUE_STORAGE" interface, where 741 "=msg.server_id", 742 "=issue_input.client_data". 744 4. The client constructs a "client_issue" message and sends it to 745 the server corresponding to "" with 746 "=issue_input.msg_data". 748 5. Receives a "server_issue_resp" message back from client_data 749 server, and sends this to the "CLIENT_ISSUE_FINISH" interface. 751 3.3.3. CLIENT_ISSUE_FINISH 753 * Visibility: "internal" 754 * Input: a message "msg" of type "server_issue_resp" 755 (Appendix A.1.4). 757 * Returns: "null" 759 * Steps: 761 1. The client sends an empty message to the 762 "CLIENT_ISSUE_RETRIEVAL" interface and receives a 763 "client_issue_retrieval" message "tmp" in response. 765 2. The client sets "cli_cfg=tmp.config". 767 3. The client runs: 769 tokens = PP_Process(cli_cfg,(msg.evals, msg.proof),tmp.g_data) 771 4. The client constructs a "client_token_storage" message and 772 sends it to the "CLIENT_TOKEN_STORAGE" interface, where 773 "=tokens". 775 3.3.4. CLIENT_REDEEM 777 * Visibility: "internal" 779 * Input: a message "msg" of type "client_redeem_generation" 780 (Appendix A.2.9). 782 * Returns: a boolean value "ret" indicating whether the server 783 accepted the redemption, or not. 785 * Steps: 787 1. The client runs: 789 cli_cfg = PP_Client_Setup(msg.ciphersuite, msg.config) 791 2. The client generates arbitrary auxiliary data "aux" and runs: 793 tag = PP_Redeem(cli_cfg, msg.token, aux) 795 3. The client constructs a "client_redeem" message and sends it 796 to the "SERVER_REDEEM" interface of the Server referred to by 797 "", with "=msg.token.data" and "=aux". 799 4. The client returns the value boolean value indicated in the 800 "RedemptionResponse" received in the server's 801 "server_redeem_resp" message. 803 3.3.5. CLIENT_ISSUE_STORAGE 805 * Visibility: "internal" 807 * Input: a "client_issue_storage" message "msg" (Appendix A.2.2). 809 * Returns: "null" 811 * Steps: 813 1. Stores the "ClientIssuanceProcessing" struct represented by 814 "msg.client_data" in local storage, keyed by "server_id", 815 "ciphersuite" and "comm_id". 817 3.3.6. CLIENT_ISSUE_RETRIEVAL 819 * Visibility: "internal" 821 * Input: a "client_issue_retrieval" message "msg" (Appendix A.2.4). 823 * Returns: a "client_issue_retrieval_resp" message (Appendix A.2.5). 825 * Steps: 827 1. Retrieve "client_data" where "msg.server_id", 828 "msg.ciphersuite" and "msg.comm_id". 830 2. Return a "client_issue_retrieval" message containing 831 "client_data" above to the "CLIENT_ISSUE_FINISH" interface. 833 3.3.7. CLIENT_TOKEN_STORAGE 835 * Visibility: "internal" 837 * Input: a "client_token_storage" message "msg" (Appendix A.2.6). 839 * Returns: "null" 841 * Steps: 843 1. Stores the vector of "RedemptionToken" objects in local 844 storage keyed by "server_id", "ciphersuite" and "comm_id". 846 3.3.8. CLIENT_TOKEN_RETRIEVAL 848 * Visibility: "internal" 850 * Input: a "client_token_retrieval" message "msg" (Appendix A.2.7). 852 * Returns: a "client_token_retrieval_resp" message. 854 * Steps: 856 1. Retrieve all the available token "tokens" keyed by 857 "msg.server_id", "msg.ciphersuite" and "msg.comm_id". 859 2. If "tokens != null", let "token = tokens.pop()". 861 3. Store the modified "tokens" object back in local storage by 862 interacting with the "CLIENT_TOKEN_STORAGE" interface. 864 4. Return a "client_token_retrieval" message containing the token 865 value above (or "null" if "tokens == null") to the 866 "CLIENT_CONFIG_RETRIEVAL" interface. 868 3.4. Global configuration registry interfaces 870 3.4.1. GLOBAL_CONFIG_UPDATE 872 * Visibility: "external" 874 * Input: a "config_update" message "msg" (Appendix A.3.1). 876 * Returns: "null" 878 * Steps: 880 1. Creates an entry in the global config registry, keyed by 881 "msg.server_id", "msg.config.ciphersuite" and "msg.comm_id". 882 Therefore, the registry data block takes the form: 884 server_id: msg.server_id 885 ciphersuite: msg.config.ciphersuite 886 comm_id: msg.comm_id 887 config: msg.config 888 expiry: msg.expiry 889 signature: msg.signature 890 supports: msg.supports 892 2. Updates "server_id.previous" to be equal to a structure of the 893 form: 895 struct { 896 Ciphersuite ciphersuite = current.ciphersuite 897 int16 comm_id = current.comm_id 898 } 900 where the "Ciphersuite" struct is described in 901 [draft-davidson-pp-protocol]. 903 3. Updates "server_id.current" to be equal to a structure of the 904 form: 906 struct { 907 Ciphersuite ciphersuite = msg.ciphersuite 908 int16 comm_id = msg.comm_id 909 } 911 4. Appends the current time to the vector of datetime values in 912 "server_id.modified". 914 3.4.2. GLOBAL_CONFIG_RETRIEVAL 916 * Visibility: "external" 918 * Input: a "config_retrieval" message "msg" (Appendix A.3.1). 920 * Returns: a "config_retrieval_resp" message (Appendix A.3.3). 922 * Steps: 924 1. Retrieve the data structure "server_ds" from the global config 925 registry, keyed by "msg.server_id". 927 2. Let "current=server_ds[current.ciphersuite][current.comm_id]" 929 3. Let 930 "previous=server_ds[previous.ciphersuite][previous.comm_id]" 932 4. Return a "config_retrieval_resp" message of the form below, to 933 the querying interface. 935 cfg_0 = config_entry { 936 ciphersuite: current.ciphersuite, 937 comm_id: current.comm_id, 938 config: current.config, 939 expiry: current.expiry, 940 signature: current.signature, 941 supports: current.supports, 942 }; 943 cfg_1 = config_entry { 944 ciphersuite: current.ciphersuite, 945 comm_id: current.comm_id, 946 config: current.config, 947 expiry: current.expiry, 948 signature: current.signature, 949 supports: current.supports, 950 }; 951 resp = config_retrieval_resp { 952 configs: [cfg_0, cfg_1], 953 } 955 4. Key management framework 957 Rather than sending the result of the key initialisation procedure 958 directly to each client, it is preferable for a server to upload its 959 current configurations to a trusted, tamper-proof, history-preserving 960 registry. By trusted, we mean from the perspective of clients that 961 use the Privacy Pass protocol. Any new keys uploaded to the registry 962 should be appended to the list. Any keys that have expired can 963 optionally be labelled as so, but should never be removed. A trusted 964 registry may hold key commitments for multiple Privacy Pass service 965 providers (servers). 967 As we discuss in Section 6, the implementation of the key management 968 policy has a major impact on the privacy properties of the Privacy 969 Pass ecosystem that it belongs to. 971 To prevent unauthorized modification of the trusted registry, 972 server's should be required to identify and authenticate themselves 973 before they can append data to their configuration. Moreover, only 974 parts of the registry that correspond to the servers configuration 975 can be modifiable. 977 We intend for the registry that we describe to be fulfilled by 978 existing frameworks, such as Key Transparency [keytrans] or other 979 similar architectures. 981 4.1. Global configuration 983 As alluded to above, key management for the Privacy Pass ecosystem 984 should be controlled by a single global key configuration registry. 985 This registry must be available at a publicly-known address and MUST 986 hold all of the configuration data for all of the Privacy Pass 987 servers in the ecosystem. Supporting more than one configuration 988 registry could lead to privacy concerns. 990 The registry MUST support the interfaces constructed in Section 3.4. 992 4.2. Configuration structure 994 The global config registry is organized as a key-value store 995 corresponding to all of the configurations supported by all of the 996 recognized servers that are part of the Privacy Pass ecosystem. The 997 structure of the configuration takes the form below. 999 server_id: 1000 verification_key: 1001 current: 1002 previous: 1003 modified: 1004 ciphersuite: 1005 comm_id: 1006 config: 1007 expiry: 1008 supports: 1009 signature: 1011 . 1012 . 1013 . 1015 comm_id: 1016 config: 1017 expiry: 1018 supports: 1019 signature: 1020 . 1021 . 1022 . 1024 ciphersuite: 1025 ... 1026 . 1027 . 1028 . 1030 server_id: 1031 ... 1033 Essentially, each server corresponds to a single "server_id" and 1034 "ciphersuite" corresponds to the different ciphersuites that the 1035 server can use. Each configuration is defined by the data in the 1036 "config", "expiry", "supports" and "signature" fields. The "config" 1037 field contains the data represented in the "ServerUpdate" struct 1038 [draft-davidson-pp-protocol], for example including the public key 1039 "pub_key" of the server, and the value of "max_evals". 1041 Each server defines a separate verification key in the 1042 "verification_key" field corresponding to the long-term signing key 1043 that is used for signing each of the individual configurations and 1044 "comm_id" values that it possesses. 1046 The "current", "previous" and "modified" fields are the only fields 1047 that change during configuration updates. The "current" field refers 1048 to the latest configuration to support token issuance. The 1049 "previous" field is used for a single configuration that still 1050 permits redemption of tokens, this is used for ensuring that key 1051 rotations are smooth for clients. The "modified" field refers to a 1052 vector of all times when the configuration was modified. 1054 4.3. Configuration updates #{config-update} 1056 Whenever a server wants to rotate their current configuration, they 1057 must create a request to append their new configuration to the 1058 trusted registry. This request is handled by the global registry to 1059 update the configuration, see the "GLOBAL_CONFIG_UPDATE" interface. 1061 Each update results in adding a new config underneath an existing 1062 "" with a new "" parameter, or a new 1063 "" entry. The global config registry also updates, the 1064 "current", "previous" and "modified" fields to indicate that the 1065 change has occurred. 1067 For reasons that are addressed more closely in Section 6, the global 1068 configuration registry must ensure that the only configurations that 1069 are used at any given time, are those referred to in "current" and 1070 "previous". This is done to ensure that the server is not able to 1071 serve tokens to clients from multiple different configurations (which 1072 could be used to decrease the size of client anonymity sets). 1074 All fields apart from the three referenced above MUST never be 1075 modified. If a server wants to rotate the long-term 1076 "verification_key" it must create a new server identity. 1078 4.4. Client retrieval 1080 Clients can either choose to: 1082 * poll the trusted registry and import new keys, rejecting any that 1083 throw errors; 1085 * retrieve the commitments for the server at the time at which they 1086 are used, throwing errors if no valid commitment is available. 1088 In the interfaces in Section 3.3 we default to assuming that the 1089 client retrieves the latest configuration as and when it is needed. 1090 See the "CLIENT_CONFIG_RETRIEVAL" interface (Section 3.3.1) for more 1091 details. 1093 The client checks that the configuration is consistent with the data 1094 it receives from the server. It also checks the validity of the 1095 "signature" field on the configuration that it retrieves. Later we 1096 also discuss optionally checking the values in "modified" for trying 1097 to identify malicious server behavior. 1099 4.5. Key revocation 1101 Currently, key revocation is only supported by rotating the current 1102 configuration. In the future, we may consider adding an explicit 1103 mechanism for revoking a specific configuration (for example the 1104 active redemption configuration referred to by "server_id.previous") 1105 without rotating the current issuance key. 1107 5. Server running modes 1109 We provide an overview of some of the possible frameworks for 1110 configuring the way that servers run in the Privacy Pass ecosystem. 1111 In short, servers may be configured to provide symmetric issuance and 1112 redemption with clients. While some servers may be configured as 1113 proxies that accept Privacy Pass data and send it to another server 1114 that actually processes issuance and/or redemption data. 1116 The intention with providing each of these running modes is to cover 1117 the different applications that utilize variants of the Privacy Pass 1118 protocol. We RECOMMEND that any Privacy Pass server implementation 1119 adheres to one of these frameworks. 1121 5.1. Single-Issuer Single-Verifier 1123 The simplest way of considering the Privacy Pass protocol is in a 1124 setting where the same server plays the role of issuer and verifier, 1125 we call this "Single-Issuer Single-Verifier" (SISV). In SISV, we 1126 consider a server S that publishes commitments for their secret key 1127 k, that a client C has access to. 1129 When S wants to issue tokens to C, they invoke the issuance protocol 1130 where C generates their own inputs and S uses their secret key k. In 1131 this setting, C can only perform token redemption with S. When a 1132 token redemption is required, C and S invoke the redemption phase of 1133 the protocol, where C uses an issued token from a previous exchange, 1134 and S uses k as their input again. 1136 In SISV, C proves that S has attested to the honesty of C at some 1137 point in the past (without revealing exactly when). S can use this 1138 information to inform it's own decision-making about C without having 1139 to recompute the trust attestation task again. 1141 5.2. Single-Issuer Forwarding-Verifier 1143 In this setting, each client C obtains issued tokens from a server S 1144 via the issuance phase of the protocol. The difference is that 1145 clients can prove that S has attested to their honesty in the past 1146 with any verifier V. We still only consider S to hold their own 1147 secret key. 1149 When C interacts with V, V can ask C to provide proof that the 1150 separate issuer S has attested to their trust. The first stage of 1151 the redemption phase of the protocol is invoked between C and V, 1152 which sees C send the unused token (x,y,aux) to V. This message is 1153 then used in a redemption exchange between V and S, where V plays the 1154 role of the client. Then S sends the result of the redemption 1155 exchange to V, and V uses this result to determine whether C has the 1156 correct trust attestation. 1158 This configuration is known as "Single-Issuer Forwarding-Verifier" or 1159 SIFV to refer to the verifier V who uses the output of the redemption 1160 phase for their own decision-making. 1162 5.3. Single-Issue Asynchronous-Verifier 1164 This setting is inspired by recently proposed APIs such as [TRUST]. 1165 It is similar to the SIFV configuration, except that the verifiers V 1166 no longer interact with the issuer S. Only C interacts with S, and 1167 this is done asynchronously to the trust attestation request from V. 1168 Hence "Asynchronous-Verifier" (SIAV). 1170 When V invokes a redemption for C, C then invokes a redemption 1171 exchange with S in a separate session. If verification is carried 1172 out successfully by S, S instead returns a Signed Redemption Record 1173 (SRR) that contains the following information: 1175 "result": { 1176 "timestamp":"2019-10-09-11:06:11", 1177 "verifier": "V", 1178 }, 1179 "signature":sig, 1181 The "signature" field carries a signature evaluated over the contents 1182 of "result" using a long-term signing key for the issuer S, of which 1183 the corresponding public key is well-known to C and V. Then C can 1184 prove that their trust attestation from S to V by sending the SRR to 1185 V. The SRR can be verified by V by verifying the signature using the 1186 well-known public key for S. 1188 Such records can be cached to display again in the future. The 1189 issuer can also add an expiry date to the record to determine when 1190 the client must refresh the record. 1192 5.4. Bounded-Issuers 1194 Each of the configurations above can be generalized to settings where 1195 a bounded number of issuers are allowed, and verifiers can invoke 1196 trust attestations for any of the available issuers. Subsequently, 1197 this leads to three new configurations known as BISV, BIFV, BIAV. 1199 As we will discuss later in Section 6, configuring a large number of 1200 issuers can lead to privacy concerns for the clients in the 1201 ecosystem. Therefore, we are careful to ensure that the number of 1202 issuers is kept strictly bounded by a fixed small number M. The 1203 actual issuers can be replaced with different issuers as long as the 1204 total never exceeds M. Moreover, issuer replacements also have an 1205 effect on client privacy that is similar to when a key rotation 1206 occurs, so replacement should only be permitted at similar intervals. 1208 See Section 6 for more details about safe choices of M. 1210 6. Privacy analysis 1212 In the Privacy Pass protocol [draft-davidson-pp-protocol], redemption 1213 tokens intentionally encode no special information into redemption 1214 tokens to prevent a vendor from learning anything about the client. 1215 We also have cryptographic guarantees via the VOPRF construction that 1216 a vendor can learn nothing about a client beyond which issuers trust 1217 it. Still there are ways that malicious servers can try and learn 1218 identifying information about clients that it interacts with. 1220 We discuss a number of privacy considerations relative to the Privacy 1221 Pass ecosystem that we are constructing. In addition, we discuss 1222 considerations arising from the specific ways of using the Privacy 1223 Pass protocol in Section 5. 1225 6.1. User segregation 1227 The goal of the Privacy Pass ecosystem is to construct an environment 1228 where can easily measure (and maximize) relative anonymity of any 1229 client that is part of it. An inherent feature of being part of this 1230 ecosystem is that any client can only remain private relative to the 1231 entire space of users using the protocol. In principle, we would 1232 hope that the server can link any client redemption to any specific 1233 issuance invocation with a probability that is equivalent to 1234 guessing. However, in practice, the server can increase this 1235 probability using a number of techniques that can segregate the user 1236 space into smaller sets. 1238 6.1.1. Server configuration rotation 1240 Techniques to introduce segregation are closely linked to the type of 1241 key schedule that is used by the server. When a server rotates their 1242 key, any client that invokes the issuance protocol shortly afterwards 1243 will be part of a small number of possible clients that can redeem. 1244 To mechanize this attack strategy, a server could introduce a 1245 configuration rotation policy which would force clients into smaller 1246 windows where a given config is valid. This would mean that client 1247 privacy would only have utility with respect to the smaller group of 1248 users that hold redemption data for a particular key window. 1250 We RECOMMEND that great care is taken over key rotations, in 1251 particular server's should only invoke key rotation for fairly large 1252 periods of time such as between 1 and 12 weeks. Key rotations 1253 represent a trade-off between client privacy and continued server 1254 security. Therefore, it is still important that key rotations occur 1255 on a fairly regular cycle to reduce the harmfulness of a server key 1256 compromise. 1258 As we describe in Section 4, a trusted registries for holding Privacy 1259 Pass configurations is required for policing the key schedule that a 1260 server uses. Clients may choose to inspect the history of the 1261 registry before first accepting redemption tokens from the server. 1262 Concrete suggestions include the following: 1264 * If a server has updated the registry with many unexpired keys, or 1265 in very quick intervals a client SHOULD reject the configuration. 1266 The client can check this by checking the list of times when the 1267 server modified their own configuration in the vector "modified". 1268 This prevents a server from segregating clients into smaller 1269 windows using the redemption data that they hold. 1271 * If a server has only recently updated their configuration (within 1272 the last few minutes), then the client SHOULD refuse to use it. 1274 This prevents against a server that may try and deanonymize a 1275 specific client. 1277 6.1.2. Large numbers of issuers 1279 Similarly to the configuration rotation issue raised above, if there 1280 are a large number of issuers, similar user segregation can occur. 1281 In the BISV, BIFV, BIAV configurations of using the Privacy Pass 1282 protocol (Section 5), a verifier OV can trigger redemptions for any 1283 of the available issuers. Each redemption token that a client holds 1284 essentially corresponds to a bit of information about the client that 1285 OV can learn. Therefore, there is an exponential loss in privacy 1286 relative to the number of issuers that there are. 1288 For example, if there are 32 issuers, then OV learns 32 bits of 1289 information about the client. If the distribution of issuer trust is 1290 anything close to a uniform distribution, then this is likely to 1291 uniquely identify any client amongst all other Internet users. 1292 Assuming a uniform distribution is clearly the worst-case scenario, 1293 and unlikely to be accurate, but it provides a stark warning against 1294 allowing too many issuers at any one time. 1296 As we noted in Section 5.4, a strict bound should be applied to the 1297 active number of issuers that are allowed at one time in the 1298 ecosystem. We propose that allowing no more than 4 issuers at any 1299 one time is highly preferable (leading to a maximum of 64 possible 1300 user segregations). However, as highlighted in Section 8, having a 1301 very large user base (> 5 million users), could potentially allow for 1302 larger values (for example, up to 8 issuers). Issuer replacements 1303 should only occur with the same frequency as config rotations as they 1304 can lead to similar losses in privacy if clients still hold 1305 redemption tokens for previously active issuers. 1307 In addition, we RECOMMEND that trusted registries indicate at all 1308 times which issuers are deemed to be active. If a client is asked to 1309 invoke any Privacy Pass exchange for an issuer that is not declared 1310 active, then the client SHOULD refuse to retrieve the server 1311 configuration during the protocol. 1313 6.1.2.1. Single global configuration authority 1315 Any Privacy Pass ecosystem MUST only contain a single global 1316 authority for controlling and managing server configurations. 1318 This prevents servers from posting different configurations to 1319 different global authorities that are all simultaneously trusted by 1320 the clients. In such situations, the deanonymization potential would 1321 be similar to providing multiple active configurations. 1323 6.1.2.2. Maximum number of issuers inferred by client 1325 We RECOMMEND that clients only store redemption tokens for a fixed 1326 number of issuers at any one time. This number would ideally be less 1327 than the number of permitted active issuers. 1329 This prevents a malicious verifier from being able to invoke 1330 redemptions for many issuers since the client would only be holding 1331 redemption tokens for a small set of issuers. When a client is 1332 issued tokens from a new issuer and already has tokens from the 1333 maximum number of issuers, it simply deletes the oldest set of 1334 redemption tokens in storage and then stores the newly acquired 1335 tokens. 1337 6.2. Tracking and identity leakage 1339 While redemption tokens themselves encode no information about the 1340 client redeeming them, problems may occur if too many redemptions are 1341 allowed in a short burst. For instance, in the Internet setting, 1342 this may allow non-terminating verifiers to learn more information 1343 from the metadata that the client may hold (such as first-party 1344 cookies for other domains). Mitigations for this issue are similar 1345 to those proposed in Section 6.1.2 for tackling the problem of having 1346 large number of issuers. 1348 In SIAV, cached SRRs and their associated issuer public keys have a 1349 similar tracking potential to first party cookies in the browser 1350 setting. These considerations will be covered in a separate document 1351 detailing Privacy Pass protocol integration into the wider web 1352 architecture [draft-svaldez-pp-http-api]. 1354 6.3. Client incentives for anonymity reduction 1356 Clients may see an incentive in accepting all tokens that are issued 1357 by a server, even if the tokens fail later verification checks. This 1358 is because tokens effectively represent a form of currency that they 1359 can later redeem for some sort of benefit. The verification checks 1360 that are put in place are there to ensure that the client does not 1361 sacrifice their anonymity. However, a client may judge the 1362 "monetary" benefit of owning tokens to be greater than their own 1363 privacy. 1365 Firstly, none of the interfaces that we have described permit this 1366 type of behavior, as they utilize the underlying Privacy Pass API 1367 that carries out this verification. A client behaving in this way 1368 would not be compliant with the protocol. 1370 Secondly, acting in this way only affects the privacy of the 1371 immediate client. There is an exception if a large number of clients 1372 colluded to accept bad data, then any client that didn't accept would 1373 be part of a smaller anonymity set. However, such an situation would 1374 be identical to the situation where the total number of clients in 1375 the ecosystem is small. Therefore, the privacy impact would be 1376 equivalent; see Section 6.1.2 for more details. 1378 7. Security considerations 1380 We present a number of security considerations that prevent a 1381 malicious actors from abusing the protocol. 1383 7.1. Double-spend protection 1385 All issuing server should implement a robust storage-query mechanism 1386 for checking that tokens sent by clients have not been spent before. 1387 Such tokens only need to be checked for each issuer individually. 1388 But all issuers must perform global double-spend checks to avoid 1389 clients from exploiting the possibility of spending tokens more than 1390 once against distributed token checking systems. For the same 1391 reason, the global data storage must have quick update times. While 1392 an update is occurring it may be possible for a malicious client to 1393 spend a token more than once. 1395 7.2. Configuration rotation 1397 We highlighted previously that short configuration-cycles can be used 1398 to reduce client privacy. However, regular key rotations are still 1399 recommended to maintain good server key hygiene. The key material 1400 that we consider to be important are: 1402 * the Server secret key for issuing Privacy Pass data; 1404 * the signing key used to sign configuration information; 1406 * the signing key used to sign SRRs in the SIAV configuration. 1408 We recommend that Privacy Pass secret keys are rotated from anywhere 1409 between 1 and 12 weeks. With an active user-base, a week gives a 1410 fairly large window for clients to participate in the Privacy Pass 1411 protocol and thus enjoy the privacy guarantees of being part of a 1412 larger group. The low ceiling of 12 weeks prevents a key compromise 1413 from being too destructive. If a server realizes that a key 1414 compromise has occurred then the server should revoke the previous 1415 key in the trusted registry and specify a new key to be used. 1417 For the two signing keys, these should both be well-known keys 1418 associated with the issuer. Issuers may choose to use the same key 1419 for both signing purposes. The rotation schedules for these keys can 1420 be much longer, if necessary. Rotations of these keys results in the 1421 creation of a new server identity. 1423 7.3. Token exhaustion 1425 When a client holds tokens for an issuer, it is possible for any 1426 verifier to invoke that client to redeem tokens for that issuer. 1427 This can lead to an attack where a malicious verifier can force a 1428 client to spend all of their tokens for a given issuer. To prevent 1429 this from happening, methods should be put into place to prevent many 1430 tokens from being redeemed at once. 1432 For example, it may be possible to cache a redemption for the entity 1433 that is invoking a token redemption. In SISV/SIFV, if the verifier 1434 requests more tokens then the client simply returns the cached token 1435 that it returned previously. This could also be handled by simply 1436 not redeeming any tokens for the entity if a redemption had already 1437 occurred in a given time window. 1439 In SIAV, the client instead caches the SRR that it received in the 1440 asynchronous redemption exchange with the issuer. If the same 1441 verifier attempts another redemption request, then the client simply 1442 returns the cached SRR. The SRRs can be revoked by the issuer, if 1443 need be, by providing an expiry date or by signaling that records 1444 from a particular window need to be refreshed. 1446 8. Protocol parametrization 1448 We provide a summary of the parameters that we use in the Privacy 1449 Pass protocol ecosystem. These parameters are informed by both 1450 privacy and security considerations that are highlighted in Section 6 1451 and Section 7, respectively. These parameters are intended as a 1452 single reference point for those implementing the protocol. 1454 Firstly, let U be the total number of users, I be the total number of 1455 issuers. Assuming that each user accept tokens from a uniform 1456 sampling of all the possible issuers, as a worst-case analysis, this 1457 segregates users into a total of 2^I buckets. As such, we see an 1458 exponential reduction in the size of the anonymity set for any given 1459 user. This allows us to specify the privacy constraints of the 1460 protocol below, relative to the setting of A. 1462 +------------------------------------------+--------------+ 1463 | parameter | value | 1464 +==========================================+==============+ 1465 | Minimum anonymity set size (A) | 5000 | 1466 +------------------------------------------+--------------+ 1467 | Recommended key lifetime (L) | 2 - 24 weeks | 1468 +------------------------------------------+--------------+ 1469 | Recommended key rotation frequency (F) | L/2 | 1470 +------------------------------------------+--------------+ 1471 | Maximum allowed issuers (I) | log_2(U/A)-1 | 1472 +------------------------------------------+--------------+ 1473 | Maximum active issuance configurations | 1 | 1474 +------------------------------------------+--------------+ 1475 | Maximum active redemption configurations | 2 | 1476 +------------------------------------------+--------------+ 1477 | Minimum cryptographic security parameter | 128 bits | 1478 +------------------------------------------+--------------+ 1480 Table 1 1482 8.1. Justification 1484 We make the following assumptions in these parameter choices. 1486 * Inferring the identity of a user in a 5000-strong anonymity set is 1487 difficult 1489 * After 2 weeks, all clients in a system will have rotated to the 1490 new key 1492 The maximum choice of I is based on the equation 1/2 * U/2^I = A. 1493 This is because I issuers lead to 2^I segregations of the total user- 1494 base U. By reducing I we limit the possibility of performing the 1495 attacks mentioned in Section 6.1. 1497 We must also account for each user holding issued data for more then 1498 one possible active keys. While this may also be a vector for 1499 monitoring the access patterns of clients, it is likely to 1500 unavoidable that clients hold valid issuance data for the previous 1501 key epoch. This also means that the server can continue to verify 1502 redemption data for a previously used key. This makes the rotation 1503 period much smoother for clients. 1505 For privacy reasons, it is recommended that key epochs are chosen 1506 that limit clients to holding issuance data for a maximum of two 1507 keys. By choosing F = L/2 then the minimum value of F is a week, 1508 since the minimum recommended value of L is 2 weeks. Therefore, by 1509 the initial assumption, then all users should only have access to 1510 only two keys at any given time. This reduces the anonymity set by 1511 another half at most. 1513 Finally, the minimum security parameter size is related to the 1514 cryptographic security offered by the protocol that is run. This 1515 parameter corresponds to the number of operations that any adversary 1516 has in breaking one of the security guarantees in the Privacy Pass 1517 protocol [draft-davidson-pp-protocol]. The existing protocol 1518 document contains an instantiation based on verifiable oblivious 1519 pseudorandom functions (VOPRFs) [I-D.irtf-cfrg-voprf]. Careful 1520 attention should be paid to whether the available ciphersuites for a 1521 protocol instantiation meets this criteria. 1523 8.2. Example parameterization 1525 Using the specification above, we can give some example 1526 parameterizations. For example, the current Privacy Pass browser 1527 extension [PPEXT] has over 150,000 active users (from Chrome and 1528 Firefox). As a result, log_2(U/A) is approximately 5 and so the 1529 maximum value of I should be 4. 1531 If the value of U is much bigger (e.g. 5 million) then this would 1532 permit I = log_2(5000000/5000)-1 = 8 issuers. 1534 9. Recommendations for identifying malicious behavior 1536 TODO: Come up with an effective deterrent for server's that are 1537 deemed to misbehave by a client. Could we have a separate consensus 1538 where clients can upload misbehavior references for servers that they 1539 deem to be malicious? 1541 10. Extension integration policy 1543 The Privacy Pass protocol and ecosystem are both intended to be 1544 receptive to extensions that expand the current set of functionality. 1545 In [draft-davidson-pp-protocol], some points are made about how 1546 implementing the Privacy Pass API can be instantiated using different 1547 underlying primitives. The interfaces described in Section 3 utilize 1548 the API in such a way that internal changes should result in no 1549 visible change to implementers of the Privacy Pass protocol. 1551 As specified in [draft-davidson-pp-protocol], all extensions to the 1552 Privacy Pass protocol SHOULD be specified as separate documents that 1553 modify the content of this document in some way. We provide guidance 1554 on the type of modifications that are possible in the following. 1556 Aside from the underlying protocol, extensions MAY modify the 1557 protocol interfaces from the definition in this document. Such 1558 extensions MUST document exactly which interfaces are changed and any 1559 new message formats that arise. Any such extension should also come 1560 with a detailed analysis of the privacy impacts of the extension, why 1561 these impacts are justified, and guidelines on changes to the 1562 parametrization in Section 8. Similarly, extensions MAY also add new 1563 Server running modes, if applicable, to those that are documented in 1564 Section 5. 1566 We RECOMMEND that any extension to the Privacy Pass architecture does 1567 not add new interfaces to those that are listed in Section 3. We 1568 expect that any extension is expressible using the interfaces 1569 themselves and reimplementing the existing functionality, if need be. 1570 Abiding by this policy maintains a simplified execution chain that is 1571 easy to reason about. 1573 Extensions MUST NOT modify the format and/or structure of the global 1574 configuration registry, other than specifying the data format of each 1575 of the fields that are used. If an extension requires a modified 1576 configuration registry, then such a change is interpreted to lie 1577 outside of the Privacy Pass ecosystem, and is thus not supported. 1579 11. Existing applications 1581 The following is a non-exhaustive list of applications that currently 1582 make use of the Privacy Pass protocol, or some variant of the 1583 underlying functionality. 1585 11.1. Cloudflare challenge pages 1587 Cloudflare uses an implementation of the Privacy Pass protocol for 1588 allowing clients that have previously interacted with their Internet 1589 challenge protection system to bypass future challenges [PPSRV]. 1590 These challenges can be expensive for clients, and there have been 1591 cases where bugs in the implementations can severely degrade client 1592 accessibility. 1594 Clients must install a browser extension [PPEXT] that acts as the 1595 Privacy Pass client in an exchange with Cloudflare's Privacy Pass 1596 server, when an initial challenge solution is provided. The client 1597 extension stores the issued tokens and presents a valid redemption 1598 token when it sees future Cloudflare challenges. If the redemption 1599 token is verified by the server, the client passes through the 1600 security mechanism without completing a challenge. 1602 11.2. Trust Token API 1604 The Trust Token API [TRUST] has been devised as a generic API for 1605 providing Privacy Pass functionality in the browser setting. The API 1606 is intended to be implemented directly into browsers so that server's 1607 can directly trigger the Privacy Pass workflow. 1609 11.3. Zero-knowledge Access Passes 1611 The PrivateStorage API developed by Least Authority is a solution for 1612 uploading and storing end-to-end encrypted data in the cloud. A 1613 recent addition to the API [PrivateStorage] allows clients to 1614 generate Zero-knowledge Access Passes (ZKAPs) attesting to the fact 1615 that the client has paid for the storage space that it is using. The 1616 ZKAP protocol is based heavily on the Privacy Pass redemption 1617 mechanism. The client receives ZKAPs when it pays for storage space, 1618 and redeems the passes when it interacts with the PrivateStorage API. 1620 11.4. Basic Attention Tokens 1622 The browser Brave uses Basic Attention Tokens (BATs) to provide the 1623 basis for a privacy-preserving rewards scheme [Brave]. The BATs are 1624 essentially Privacy Pass redemption tokens that are provided by a 1625 central Brave server when a client performs some action that triggers 1626 a reward event (such as watching an advertisement). When the client 1627 amasses BATs, it can redeem them with the Brave central server for 1628 rewards. 1630 11.5. Token Based Services 1632 Similarly to BATs, a more generic approach for providing anonymous 1633 peers to purchase resources from anonymous servers has been proposed 1634 [OpenPrivacy]. The protocol is based on a variant of Privacy Pass 1635 and is intended to allow clients purchase (or pre-purchase) services 1636 such as message hosting, by using Privacy Pass redemption tokens as a 1637 form of currency. This is also similar to how ZKAPs are used. 1639 12. References 1641 12.1. Normative References 1643 [draft-davidson-pp-protocol] 1644 Davidson, A., "Privacy Pass: The Protocol", n.d., 1645 . 1648 [draft-svaldez-pp-http-api] 1649 Valdez, S., "Privacy Pass: HTTP API", n.d., 1650 . 1653 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1654 Requirement Levels", BCP 14, RFC 2119, 1655 DOI 10.17487/RFC2119, March 1997, 1656 . 1658 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 1659 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 1660 . 1662 [X9.62] Institute, A.N.S., "Public Key Cryptography for the 1663 Financial Services Industry: The Elliptic Curve Digital 1664 Signature Algorithm (ECDSA)", ANSI X9.62-2005 , November 1665 2005. 1667 12.2. Informative References 1669 [Brave] "Brave Rewards", n.d., . 1671 [I-D.irtf-cfrg-voprf] 1672 Davidson, A., Sullivan, N., and C. Wood, "Oblivious 1673 Pseudorandom Functions (OPRFs) using Prime-Order Groups", 1674 Work in Progress, Internet-Draft, draft-irtf-cfrg-voprf- 1675 02, 4 November 2019, . 1678 [keytrans] "Security Through Transparency", n.d., 1679 . 1682 [OpenPrivacy] 1683 "Token Based Services - Differences from PrivacyPass", 1684 n.d., . 1687 [PPEXT] "Privacy Pass Browser Extension", n.d., 1688 . 1691 [PPSRV] Sullivan, N., "Cloudflare Supports Privacy Pass", n.d., 1692 . 1695 [PrivateStorage] 1696 Steininger, L., "The Path from S4 to PrivateStorage", 1697 n.d., . 1700 [TRUST] WICG, ., "Trust Token API", n.d., 1701 . 1703 Appendix A. Message formats 1705 We detail an exhaustive list of the different message types used in 1706 the Privacy Pass protocol. These messages are sent and received by 1707 the interfaces detailed in Section 3. We intend for the messages to 1708 be compatible typical message expression formats such as JSON. 1710 A.1. Server messages 1712 A.1.1. server_config_store 1714 struct { 1715 ServerConfig configs[2]; 1716 } server_config_store 1718 A.1.2. server_config_retrieve 1720 struct { 1721 uint8 method; 1722 ServerConfig configs[2]; 1723 } server_config_retrieve 1725 A.1.3. server_hello 1727 struct { 1728 opaque server_id<0..255>; 1729 uint8 supports; 1730 } server_hello 1732 A.1.4. server_issue_resp 1734 struct { 1735 IssuanceResponse data; 1736 } server_issue_resp 1738 A.1.5. server_redeem_resp 1740 struct { 1741 RedemptionResponse data; 1742 } server_redeem_resp 1744 A.2. Client message formats 1746 A.2.1. client_issue_generation 1748 struct { 1749 opaque server_id<0..255>; 1750 ServerUpdate config; 1751 } client_issue_generation 1753 A.2.2. client_issue_storage 1755 struct { 1756 opaque server_id<0..255> 1757 Ciphersuite ciphersuite; 1758 opaque comm_id<0..2^16-1>; 1759 ClientIssuanceProcessing client_data; 1760 } client_issue_storage 1762 A.2.3. client_issue 1764 struct { 1765 opaque client_id<0..2^16-1>; 1766 IssuanceMessage issue_data; 1767 } client_issue 1769 A.2.4. client_issue_retrieval 1771 struct { 1772 opaque server_id<0..255>; 1773 Ciphersuite ciphersuite; 1774 opaque comm_id<0..2^16-1>; 1775 } client_issue_retrieval 1777 A.2.5. client_issue_retrieval_resp 1779 struct { 1780 ClientIssuanceProcessing client_data; 1781 } client_issue_retrieval_resp 1783 A.2.6. client_token_storage 1785 struct { 1786 opaque server_id<0..255>; 1787 Ciphersuite ciphersuite; 1788 opaque comm_id<0..2^16-1>; 1789 RedemptionToken tokens[m]; 1790 } client_token_storage 1792 A.2.7. client_token_retrieval 1794 struct { 1795 opaque server_id<0..255>; 1796 Ciphersuite ciphersuite; 1797 opaque comm_id<0..2^16-1>; 1798 } client_token_retrieval 1800 A.2.8. client_token_retrieval_resp 1802 method: "client_token_retrieval_resp" 1803 struct { 1804 RedemptionToken token; 1805 } client_token_retrieval_resp 1807 A.2.9. client_redeem_generation 1809 struct { 1810 opaque server_id<0..255>; 1811 ServeUpdate config; 1812 RedemptionToken token; 1813 } client_redeem_generation 1815 A.2.10. client_redeem 1817 struct { 1818 opaque client_id<0..2^16-1>; 1819 RedemptionMessage message; 1820 } client_redeem 1822 A.3. Global configuration interfaces 1824 A.3.1. config_update 1826 struct { 1827 opaque server_id<0..255>; 1828 opaque comm_id<0..2^16-1>; 1829 ServerUpdate config; 1830 datetime expiry; 1831 opaque signature<1..2^32-1>; 1832 } config_update 1834 A.3.2. config_retrieval 1836 struct { 1837 opaque server_id<0..255>; 1838 } config_retrieval 1840 A.3.3. config_retrieval_resp 1842 struct { 1843 Ciphersuite ciphersuite; 1844 opaque comm_id<0..2^16-1>; 1845 ServerUpdate config; 1846 datetime expiry; 1847 opaque signature<1..2^32-1>; 1848 uint8 supports; 1849 } config_entry 1851 struct { 1852 config_entry configs[2]; 1853 } config_retrieval_resp 1855 Author's Address 1857 Alex Davidson 1858 Cloudflare Portugal 1859 Largo Rafael Bordalo Pinheiro 29 1860 Lisbon 1861 Portugal 1863 Email: alex.davidson92@gmail.com