idnits 2.17.00 (12 Aug 2021) /tmp/idnits38163/draft-ietf-privacypass-architecture-03.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: ---------------------------------------------------------------------------- == There is 1 instance of lines with non-ascii characters in the document. 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.) Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document date (7 March 2022) is 68 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'RFC8446' is defined on line 969, but no explicit reference was found in the text == Outdated reference: A later version (-04) exists of draft-ietf-privacypass-protocol-02 -- Obsolete informational reference (is this intentional?): RFC 6962 (Obsoleted by RFC 9162) Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Davidson 3 Internet-Draft LIP 4 Intended status: Informational J. Iyengar 5 Expires: 8 September 2022 Fastly 6 C. A. Wood 7 Cloudflare 8 7 March 2022 10 Privacy Pass Architectural Framework 11 draft-ietf-privacypass-architecture-03 13 Abstract 15 This document specifies the architectural framework for constructing 16 secure and anonymity-preserving instantiations of the Privacy Pass 17 protocol. It provides recommendations on how the protocol ecosystem 18 should be constructed to ensure the privacy of clients, and the 19 security of all participating entities. 21 Status of This Memo 23 This Internet-Draft is submitted in full conformance with the 24 provisions of BCP 78 and BCP 79. 26 Internet-Drafts are working documents of the Internet Engineering 27 Task Force (IETF). Note that other groups may also distribute 28 working documents as Internet-Drafts. The list of current Internet- 29 Drafts is at https://datatracker.ietf.org/drafts/current/. 31 Internet-Drafts are draft documents valid for a maximum of six months 32 and may be updated, replaced, or obsoleted by other documents at any 33 time. It is inappropriate to use Internet-Drafts as reference 34 material or to cite them other than as "work in progress." 36 This Internet-Draft will expire on 8 September 2022. 38 Copyright Notice 40 Copyright (c) 2022 IETF Trust and the persons identified as the 41 document authors. All rights reserved. 43 This document is subject to BCP 78 and the IETF Trust's Legal 44 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 45 license-info) in effect on the date of publication of this document. 46 Please review these documents carefully, as they describe your rights 47 and restrictions with respect to this document. Code Components 48 extracted from this document must include Revised BSD License text as 49 described in Section 4.e of the Trust Legal Provisions and are 50 provided without warranty as described in the Revised BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 55 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 56 3. Architecture . . . . . . . . . . . . . . . . . . . . . . . . 5 57 3.1. Redemption Protocol . . . . . . . . . . . . . . . . . . . 5 58 3.2. Issuance Protocol . . . . . . . . . . . . . . . . . . . . 6 59 3.2.1. Attester Role . . . . . . . . . . . . . . . . . . . . 7 60 3.2.2. Issuer Role . . . . . . . . . . . . . . . . . . . . . 8 61 3.2.3. Metadata . . . . . . . . . . . . . . . . . . . . . . 10 62 3.2.4. Issuance Protocol Extensibility . . . . . . . . . . . 10 63 4. Deployment Considerations . . . . . . . . . . . . . . . . . . 11 64 4.1. Shared Origin, Attester, Issuer . . . . . . . . . . . . . 11 65 4.2. Joint Attester and Issuer . . . . . . . . . . . . . . . . 12 66 4.3. Joint Origin and Issuer . . . . . . . . . . . . . . . . . 13 67 4.4. Split Origin, Attester, Issuer . . . . . . . . . . . . . 14 68 5. Privacy Considerations . . . . . . . . . . . . . . . . . . . 15 69 5.1. Metadata Privacy Implications . . . . . . . . . . . . . . 15 70 5.2. Issuer Key Rotation . . . . . . . . . . . . . . . . . . . 15 71 5.3. Large Number of Issuers . . . . . . . . . . . . . . . . . 16 72 5.3.1. Allowing More Issuers . . . . . . . . . . . . . . . . 17 73 6. Security Considerations . . . . . . . . . . . . . . . . . . . 18 74 6.1. Double-spend Protection . . . . . . . . . . . . . . . . . 18 75 6.2. Token Exhaustion . . . . . . . . . . . . . . . . . . . . 19 76 7. Protocol Parameterization . . . . . . . . . . . . . . . . . . 19 77 7.1. Justification . . . . . . . . . . . . . . . . . . . . . . 20 78 7.2. Example parameterization . . . . . . . . . . . . . . . . 21 79 7.3. Allowing more Issuers . . . . . . . . . . . . . . . . . . 21 80 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 21 81 8.1. Normative References . . . . . . . . . . . . . . . . . . 21 82 8.2. Informative References . . . . . . . . . . . . . . . . . 22 83 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 23 84 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23 86 1. Introduction 88 Privacy Pass is a protocol for authorization based on anonymous- 89 credential authentication mechanisms. Typical approaches for 90 authorizing clients, such as through the use of long-term cookies, 91 are not privacy-friendly since they allow servers to track clients 92 across sessions and interactions. Privacy Pass takes a different 93 approach: instead of presenting linkable state carrying information 94 to servers, e.g., whether or not the client is an authorized user or 95 has completed some prior challenge, clients present unlinkable proofs 96 that attest to this information. 98 The most basic Privacy Pass protocol provides a set of cross-origin 99 authorization tokens that protect the client's anonymity during 100 interactions with a server. This allows clients to communicate an 101 attestation of a previously authenticated server action, without 102 having to reauthenticate manually. The tokens retain anonymity in 103 the sense that the act of revealing them cannot be linked back to the 104 session where they were initially issued. 106 At a high level, Privacy Pass is composed of two protocols: issuance 107 and redemption. 109 The issuance protocol runs between a Client and two network functions 110 in the Privacy Pass architecture: Attestation and Issuance. These 111 two network functions can be implemented by the same protocol 112 participant, but can also be implemented separately. The Issuer is 113 responsible for issuing tokens in response to requests from Clients. 114 The Attester is responsible for attesting properties about the Client 115 for which tokens are issued. The Issuer needs to be trusted by the 116 server that later redeems the token. Attestation can be performed by 117 the Issuer or by an Attester that is trusted by the Issuer. Clients 118 might prefer to select different Attesters, separate from the Issuer, 119 to be able to use preferred authentication methods or improve privacy 120 by not directly communicating with an Issuer. Depending on the 121 attestation, Attesters can store state about a Client, such as the 122 number of overall tokens issued thus far. As an example of an 123 Issuance protocol, in the original Privacy Pass protocol [PPSRV], 124 tokens were only issued to Clients that solved CAPTCHAs. In this 125 context, the Attester attested that some client solved a CAPTCHA and 126 the resulting token produced by the Issuer was proof of this fact. 128 The redemption protocol runs between Client and Origin (server). It 129 allows Origins to challenge Clients to present one or more tokens for 130 authorization. Depending on the type of token, e.g., whether or not 131 it is cross-origin or per-origin, and whether or not it can be 132 cached, the Client either presents a previously obtained token or 133 invokes the issuance protocol to acquire one for authorization. 135 The issuance and redemption protocols operate in concert as shown in 136 the figure below. 138 Origin Client Attester Issuer 139 /-------------------------------------------------------------------- 140 | /-----------------------------------------\ 141 | Challenge ----> Attest ---> | 142 | | TokenRequest ---------------> | 143 | Redemption | (validate) | Issuance 144 | Flow | (evaluate) | Flow 145 | | <------------------- TokenResponse | 146 | <--- Response | | 147 | \-----------------------------------------/ 148 \-------------------------------------------------------------------- 150 Figure 1: Privacy Pass Architectural Components 152 This document describes requirements for both issuance and redemption 153 protocols. This document also describes ecosystem considerations 154 that impact the stated privacy and security guarantees of the 155 protocol. 157 2. Terminology 159 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 160 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 161 "OPTIONAL" in this document are to be interpreted as described in 162 BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all 163 capitals, as shown here. 165 The following terms are used throughout this document. 167 * Client: An entity that seeks authorization to an Origin. 169 * Origin: An entity that challenges Clients for tokens. 171 * Issuer: An entity that issues tokens to Clients for properties 172 attested to by the Attester. 174 * Attester: An entity that attests to properties of Client for the 175 purposes of token issuance. 177 3. Architecture 179 The Privacy Pass architecture consists of four logical entities -- 180 Client, Origin, Issuer, and Attester -- that work in concert as shown 181 in Section 1 for token issuance and redemption. This section 182 describes the purpose of token issuance and redemption and the 183 requirements therein on the relevant participants. 185 3.1. Redemption Protocol 187 The redemption protocol is a simple challenge-response based 188 authorization protocol between Client and Origin. Origins prompt 189 Clients with a token challenge and, if possible, Clients present a 190 valid token for the challenge in response. The context in which an 191 Origin challenges a Client for a token is referred to as the 192 redemption context. This context includes all information associated 193 with the redemption event, such as the timestamp of the event, Client 194 visible information (including the IP address), and the Origin name. 196 The challenge controls the type of token that the Origin will accept 197 for the given resource. As described in [HTTP-Authentication], there 198 are a number of ways in which the token may vary, including: 200 * Issuance protocol. The token identifies the type of issuance 201 protocol required for producing the token. Different issuance 202 protocols have different security properties, e.g., some issuance 203 protocols may produce tokens that are publicly verifiable, whereas 204 others may not have this property. 206 * Issuer identity. Tokens identify which issuers are trusted for a 207 given issuance protocol. 209 * Interactive or non-interactive. Tokens can either be interactive 210 or not. An interactive token is one which requires a freshly 211 issued token based on the challenge, whereas a non-interactive 212 token can be issued proactively and cached for future use. 214 * Per-origin or cross-origin. Tokens can be constrained to the 215 Origin for which the challenge originated, or can be used across 216 Origins. 218 Depending on the use case, Origins may need to maintain state to 219 track redeemed tokens. For example, Origins that accept non- 220 interactive, cross-origin tokens SHOULD track which tokens have been 221 redeemed already, since these tokens can be issued and then spent 222 multiple times in response to any such challenge. See Section 6.1 223 for discussion. 225 Origins that admit cross-origin tokens bear some risk of allowing 226 tokens issued for one Origin to be spent in an interaction with 227 another Origin. If tokens protected with resources are unique to a 228 single Origin, then said Origin MUST NOT admit cross-origin tokens 229 for authorization. 231 3.2. Issuance Protocol 233 The issuance protocol embodies the core of Privacy Pass. It takes as 234 input a challenge from the redemption protocol and produces a token, 235 as shown in the figure below. 237 Origin Client Attester Issuer 239 +--------------------------------------\ 240 Challenge ----> TokenRequest ---> | 241 | (attest) | 242 | TokenRequest ---> | 243 | (evaluate)| 244 | <--- TokenResponse | 245 Token <----+ TokenResponse <--- | 246 |--------------------------------------/ 248 Figure 2: Issuance Overview 250 Clients interact with the Attester and Issuer to produce a token in 251 response to a challenge. The context in which an Attester vouches 252 for a Client during issuance is referred to as the attestation 253 context. This context includes all information associated with the 254 issuance event, such as the timestamp of the event and Client visible 255 information, including the IP address or other information specific 256 to the type of attestation done. 258 Each issuance protocol may be different, e.g., in the number and 259 types of participants, underlying cryptographic constructions used 260 when issuing tokens, and even privacy properties. 262 Clients initiate the Token issuance protocol using the challenge, a 263 randomly generated nonce, and public key for the Issuer. The Token 264 issuance protocol itself can be any interactive protocol between 265 Client, Issuer, or other parties that produces a valid authenticator 266 over the Client's input, subject to the following security 267 requirements. 269 1. Unconditional input secrecy. The issuance protocol MUST NOT 270 reveal anything about the Client's private input, including the 271 challenge and nonce, to the Attester or Issuer. The issuance 272 protocol can reveal the Issuer public key for the purposes of 273 determining which private key to use in producing the issuance 274 protocol. A result of this property is that the redemption flow 275 is unlinkable from the issuance flow. 277 2. One-more forgery security. The issuance protocol MUST NOT allow 278 malicious Clients or Attesters (acting as Clients) to forge 279 tokens without interacting with the Issuer directly. 281 3. Concurrent security. The issuance protocol MUST be safe to run 282 concurrently with arbitrarily many Clients. 284 Each Issuance protocol MUST come with a detailed analysis of the 285 privacy impacts of the protocol, why these impacts are justified, and 286 guidelines on changes to the parametrization in Section 7. 288 The mechanism by which clients obtain the Issuer public key is not 289 specified. Clients may be configured with this key or they may 290 discover it via some other form. See [CONSISTENCY]. 292 Depending on the use case, issuance may require some form of Client 293 anonymization service similar to an IP-hiding proxy so that Issuers 294 cannot learn information about Clients. This can be provided by an 295 explicit participant in the issuance protocol, or it can be provided 296 via external means, e.g., through the use of an IP-hiding proxy 297 service like Tor. In general, Clients SHOULD minimize or remove 298 identifying information where possible when invoking the issuance 299 protocol. 301 Issuers MUST NOT issue tokens for Clients through untrusted 302 Attesters. This is important because the Attester's role is to vouch 303 for trust in privacy-sensitive Client information, such as account 304 identifiers or IP address information, to the Issuer. Tokens 305 produced by an Issuer that admits issuance for any type of 306 attestation cannot be relied on for any specific property. See 307 Section 3.2.1 for more details. 309 3.2.1. Attester Role 311 Attestation is an important part of the issuance protocol. 312 Attestation is the process by which an Attester bears witness to, 313 confirms, or authenticates a Client so as to verify a property about 314 the Client that is required for Issuance. Examples of attestation 315 properties include, though are not limited to: 317 * Capable of solving a CAPTCHA. Clients that solve CAPTCHA 318 challenges can attest to this capability for the purposes of being 319 ruled out as a bot or otherwise automated Client. 321 * Client state. Clients can be associated with state and the 322 attester can attest to this state. Examples of state include the 323 number of issuance protocol invocations, the client's geographic 324 region, and whether the client has a valid application-layer 325 account. 327 * Trusted device. Some Clients run on trusted hardware that are 328 capable of producing device-level attestation statements. 330 Each of these attestation types have different security properties. 331 For example, attesting to having a valid account is different from 332 attesting to be running on trusted hardware. In general, Attesters 333 should accept a limited form of attestation formats. 335 Each attestation format also has an impact on the overall system 336 privacy. For example, the number of users in possession of a single 337 class of trusted device might be lesser than the number of users that 338 can solve CAPTCHAs. Similarly, requiring a conjunction of 339 attestation types could decrease the overall anonymity set size. For 340 example, the number of Clients that have solved a CAPTCHA in the past 341 day, have a valid account, and are running on a trusted device is 342 lesser than the number of Clients that have solved a CAPTCHA in the 343 past day. Attesters should not admit attestation types that result 344 in small anonymity sets. 346 3.2.2. Issuer Role 348 Issuers MUST be uniquely identifiable by all Clients with a 349 consistent identifier. In a web context, this identifier might be 350 the Issuer host name. As discussed later in Section 5, ecosystems 351 that admit a large number of Issuers can lead to privacy concerns for 352 the Clients in the ecosystem. Therefore, in practice, the number of 353 Issuers should be bounded. The actual Issuers can be replaced with 354 different Issuers as long as the total never exceeds these bounds. 355 Moreover, Issuer replacements also have an effect on client anonymity 356 that is similar to when a key rotation occurs. See Section 5 for 357 more details about maintaining privacy with multiple Issuers. 359 3.2.2.1. Key Management 361 To facilitate issuance, the Issuer MUST hold an Issuance key pair at 362 any given time. The Issuer public key MUST be made available to all 363 Clients in such a way that key rotations and other updates are 364 publicly visible. The key material and protocol configuration that 365 an Issuer uses to produce tokens corresponds to a number of different 366 pieces of information. 368 * The issuance protocol in use; and 369 * The public keys that are active for the Issuer. 371 The way that the Issuer publishes and maintains this information 372 impacts the effective privacy of the clients; see Section 5 for more 373 details. The fundamental requirement for key management and 374 discovery is that Issuers must be unable to target specific clients 375 with unique keys without detection. There are a number of ways in 376 which this might be implemented: 378 * Servers use a verifiable, tamper-free registry from which clients 379 discover keys. Similar to related mechanisms and protocols such 380 as Certificate Transparency [RFC6962], this may require external 381 auditors or additional client behavior to ensure the registry 382 state is consistent for all clients. 384 * Clients use an anonymity-preserving tool such as Tor to discover 385 keys from multiple network vantage points. This is done to ensure 386 consistent keys to seemingly different clients. 388 * Clients embed Issuer keys into software. 390 As above, specific mechanisms for key management and discovery are 391 out of scope for this document. 393 3.2.2.2. Key Rotation 395 Token issuance associates all issued tokens with a particular choice 396 of key. If an Issuer issues tokens with many keys, then this may 397 harm the anonymity of the Client. For example, they would be able to 398 map the Client's access patterns by inspecting which key each token 399 they possess has been issued under. 401 To prevent against this, Issuers MUST only use one private key for 402 issuing tokens at any given time. Servers MAY use one or more keys 403 for redemption to allow Issuers for seamless key rotation. 405 Servers may rotate keys as a means of revoking tokens issued under 406 old or otherwise expired keys. Alternatively, Issuers may include 407 expiration information as metadata alongside the token; See 408 Section 3.2.3 for more discussion about metadata constraints. Both 409 techniques are equivalent since they cryptographically bind 410 expiration to individual tokens. 412 Key rotations should be limited in frequency for similar reasons. 413 See Section 7 for guidelines on what frequency of key rotations are 414 permitted. 416 3.2.3. Metadata 418 Certain instantiations of the issuance protocol may permit public or 419 private metadata to be cryptographically bound to a token. As an 420 example, one trivial way to include public metadata is to assign a 421 unique issuer public key for each value of metadata, such that N keys 422 yields log2(N) bits of metadata. The total amount of metadata bits 423 included in a token is the sum of public and private metadata bits. 424 See Section 7 for discussion about metadata limits. 426 Public metadata is that which clients can observe as part of the 427 token issuance flow. Public metadata can either be transparent or 428 opaque. For example, transparent public metadata is a value that the 429 client either generates itself, or the Issuer provides during the 430 issuance flow and the client can check for correctness. Opaque 431 public metadata is metadata the client can see but cannot check for 432 correctness. As an example, the opaque public metadata might be a 433 "fraud detection signal", computed on behalf of the Issuer, during 434 token issuance. In normal circumstances, clients cannot determine if 435 this value is correct or otherwise a tracking vector. 437 Private metadata is that which clients cannot observe as part of the 438 token issuance flow. Such instantiations may be built on the Private 439 Metadata Bit construction from Kreuter et al. [KLOR20] or the 440 attribute-based VOPRF from Huang et al. [HIJK21]. 442 Metadata may also be arbitrarily long or bounded in length. The 443 amount of permitted metadata may be determined by application or by 444 the underlying cryptographic protocol. 446 3.2.4. Issuance Protocol Extensibility 448 The Privacy Pass protocol and ecosystem are both intended to be 449 receptive to extensions that expand the current set of 450 functionalities through new issuance protocols. Each issuance 451 protocol SHOULD come with a detailed analysis of the privacy impacts 452 of the extension, why these impacts are justified, and guidelines on 453 changes to the parametrization in Section 7. Any extension to the 454 Privacy Pass protocol MUST adhere to the guidelines specified in 455 Section 3.2.2 for managing Issuer public key data. 457 4. Deployment Considerations 459 Client uses Privacy Pass to separate attestation context and 460 redemption context. Linking or combining these contexts can reveal 461 sensitive information about the Client, including their identity or 462 browsing history. Depending on the deployment model, separating 463 these contexts can take different forms. The Origin, Attester, and 464 Issuer portrayed in Figure 1 can be instantiated and deployed in a 465 number of different ways. This section covers some expected 466 deployment models and their corresponding security and privacy 467 considerations. The discussion below assumes non-collusion between 468 entities when operated by separate parties. Mechanisms for enforcing 469 non-collusion are out of scope for this architecture. 471 4.1. Shared Origin, Attester, Issuer 473 In this model, the Origin, Attester, and Issuer are all operated by 474 the same entity, as shown in the figure below. 476 +------------------------------------------+ 477 Client | Attester Issuer Origin | 478 | | | 479 | | Challenge | 480 <----------------------------------------------+ | 481 | | Attest | 482 +-----------------> | 483 | | TokenRequest | 484 +--------------------------------> | 485 | | TokenResponse | 486 <--------------------------------+ | 487 | | Redeem | 488 +----------------------------------------------> | 489 +------------------------------------------+ 491 Figure 3: Shared Deployment Model 493 This model represents the initial deployment of Privacy Pass, as 494 described in [PPSRV]. In this model, the Attester, Issuer, and 495 Origin share the attestation and redemption contexts. As a result, 496 attestation mechanisms that can uniquely identify a Client, e.g., 497 requiring that Clients authenticate with some type of application- 498 layer account, are not appropriate, as they could be used to learn or 499 reconstruct a Client's browsing history. 501 Attestation and redemption context unlinkability requires that these 502 events be separated over time, e.g., through the use of non- 503 interactive tokens that can be issued without a fresh Origin 504 challenge, or over space, e.g., through the use of an anonymizing 505 proxy when connecting to the Origin. 507 4.2. Joint Attester and Issuer 509 In this model, the Attester and Issuer are operated by the same 510 entity that is separate from the Origin, as shown in the figure 511 below. 513 +-----------+ 514 Client | Origin | 515 | Challenge | | 516 <-----------------------------------------------+ | 517 | | | 518 | +---------------------------+ | | 519 | | Attester Issuer | | | 520 | | | | | 521 | | Attest | | | 522 +-----------------> | | | 523 | | TokenRequest | | | 524 +--------------------------------> | | | 525 | | TokenResponse | | | 526 <--------------------------------+ | | | 527 | +---------------------------+ | | 528 | | | 529 | Redeem | | 530 +-----------------------------------------------> | 531 | | 532 +-----------+ 534 Figure 4: Joint Attester and Issuer Deployment Model 536 This model is useful if an Origin wants to offload attestation and 537 issuance to a trusted entity. In this model, the Attester and Issuer 538 share attestation context for the Client, which can be separate from 539 the Origin's redemption context. 541 For certain types of issuance protocols, this model separates 542 attestation and redemption contexts. However, Issuance protocols 543 that require the Issuer to learn information about the Origin, such 544 as that which is described in [rate-limited], are not appropriate 545 since they could link attestation and redemption contexts through the 546 Origin name. 548 4.3. Joint Origin and Issuer 550 In this model, the Origin and Issuer are operated by the same entity, 551 separate from the Attester, as shown in the figure below. 553 +--------------------------+ 554 Client | Issuer Origin | 555 | Challenge | | 556 <-----------------------------------------------+ | 557 | | | 558 | +-----------+ | | 559 | | Attester | | | 560 | | | | | 561 | | Attest | | | 562 +-----------------> | | | 563 | | | | | 564 | | TokenRequest | 565 +--------------------------------> | 566 | | | | | 567 | | TokenResponse | 568 <--------------------------------+ | 569 | | | | | 570 | +-----------+ | | 571 | | | 572 | Redeem | | 573 +-----------------------------------------------> | 574 +--------------------------+ 576 Figure 5: Joint Origin and Issuer Deployment Model 578 This model is useful for Origins that require Client-identifying 579 attestation, e.g., through the use of application-layer account 580 information, but do not otherwise want to learn information about 581 individual Clients beyond what is observed during the token 582 redemption, such as Client IP addresses. 584 In this model, attestation and redemption contexts are separate. As 585 a result, any type of attestation is suitable in this model. 586 Moreover, any type of token challenge is suitable assuming there is 587 more than one Origin involved, since no single party will have access 588 to the identifying Client information and unique Origin information. 589 If there is only a single Origin, then per-Origin tokens are not 590 appropriate in this model, since the Attester can learn the 591 redemption context. (Note, however, that the Attester does not learn 592 whether a token is per-Origin or cross-Origin.) 594 4.4. Split Origin, Attester, Issuer 596 In this model, the Origin, Attester, and Issuer are all operated by 597 different entities, as shown in the figure below. 599 +-----------+ 600 Client | Origin | 601 | Challenge | | 602 <-----------------------------------------------+ | 603 | | | 604 | +-----------+ | | 605 | | Attester | | | 606 | | | | | 607 | | Attest | +----------+ | | 608 +-----------------> | | Issuer | | | 609 | | | | | | | 610 | | TokenRequest | | | 611 +--------------------------------> | | | 612 | | | | | | | 613 | | TokenResponse | | | 614 <--------------------------------+ | | | 615 | | | | | | | 616 | +-----------+ +----------+ | | 617 | | | 618 | Redeem | | 619 +-----------------------------------------------> | 620 | | 621 +-----------+ 623 Figure 6: Split Deployment Model 625 This is the most general deployment model, and is necessary for some 626 types of issuance protocols where the Attester plays a role in token 627 issuance; see [rate-limited] for one such type of issuance protocol. 628 In this model, the Attester, Issuer, and Origin have a separate view 629 of the Client: the Attester sees potentially sensitive Client 630 identifying information, such as account identifiers or IP addresses, 631 the Issuer sees only the information necessary for Issuance, and the 632 Origin sees token challenges, corresponding tokens, and Client source 633 information, such as their IP address. As a result, attestation and 634 redemption contexts are separate, and therefore any type of token 635 challenge is suitable in this model assuming there is more than a 636 single Origin. As in the Joint Origin and Issuer model in 637 Section 4.3, if there is only a single Origin, then per-Origin tokens 638 are not appropriate. 640 5. Privacy Considerations 642 Client uses Private Pass to separate attestation context and 643 redemption context. Depending on the deployment model, this can take 644 different forms. For example, any Client can only remain private 645 relative to the entire space of other Clients using the protocol. 646 Moreover, by owning tokens for a given set of keys, the Client's 647 anonymity set shrinks to the total number of clients controlling 648 tokens for the same keys. 650 In the following, we consider the possible ways that Issuers can 651 leverage their position to try and reduce the anonymity sets that 652 Clients belong to (or, user segregation). For each case, we provide 653 mitigations that the Privacy Pass ecosystem must implement to prevent 654 these actions. 656 5.1. Metadata Privacy Implications 658 Any metadata bits of information can be used to further segment the 659 size of the Client's anonymity set. Any Issuer that wanted to track 660 a single Client could add a single metadata bit to Client tokens. 661 For the tracked Client it would set the bit to 1, and 0 otherwise. 662 Adding additional bits provides an exponential increase in tracking 663 granularity similarly to introducing more Issuers (though with more 664 potential targeting). 666 For this reason, the amount of metadata used by an Issuer in creating 667 redemption tokens must be taken into account -- together with the 668 bits of information that Issuer's may learn about Clients otherwise. 669 Since this metadata may be useful for practical deployments of 670 Privacy Pass, Issuers must balance this against the reduction in 671 Client privacy. In general, Issuers should permit no more than 32 672 bits of metadata, as this can uniquely identify each possible user. 673 We discuss this more in Section 7. 675 5.2. Issuer Key Rotation 677 Techniques to introduce Client "segregation" can be used to reduce 678 Client anonymity. Such techniques are closely linked to the type of 679 key schedule that is used by the Issuer. When an Issuer rotates 680 their key, any Client that invokes the issuance protocol in this key 681 cycle will be part of a group of possible clients owning valid tokens 682 for this key. To mechanize this attack strategy, an Issuer could 683 introduce a key rotation policy that forces Clients into small key 684 cycles. Thus, reducing the size of the anonymity set for these 685 Clients. 687 Issuers SHOULD invoke key rotation for a period of time between 1 and 688 12 weeks. Key rotations represent a trade-off between Client privacy 689 and continued Issuer security. Therefore, it is still important that 690 key rotations occur on a regular cycle to reduce the harmfulness of 691 an Issuer key compromise. 693 With a large number of Clients, a minimum of one week gives a large 694 enough window for Clients to participate in the issuance protocol and 695 thus enjoy the anonymity guarantees of being part of a larger group. 696 A maximum of 12 weeks limits the damage caused by a key compromise. 697 If an Issuer realizes that a key compromise has occurred then the 698 Issuer should generate a new key and make it available to Clients. 699 If possible, it should invoke any revocation procedures that may 700 apply for the old key. 702 5.3. Large Number of Issuers 704 Similarly to the Issuer rotation dynamic that is raised above, if 705 there are a large number of Issuers, and Origins accept all of them, 706 segregation can occur. For example, if Clients obtain tokens from 707 many Issuers, and Origins later challenge a Client for a token from 708 each Issuer, Origins can learn information about the Client. Each 709 per-Issuer token that a Client holds essentially corresponds to a bit 710 of information about the Client that Origin learn. Therefore, there 711 is an exponential loss in anonymity relative to the number of Issuers 712 that there are. 714 For example, if there are 32 Issuers, then Origins learn 32 bits of 715 information about the Client if a valid token is presented for each 716 one. If the distribution of Issuer trust is anything close to a 717 uniform distribution, then this is likely to uniquely identify any 718 Client amongst all other Internet users. Assuming a uniform 719 distribution is clearly the worst-case scenario, and unlikely to be 720 accurate, but it provides a stark warning against allowing too many 721 Issuers at any one time. 723 In cases where clients can hold tokens for all Issuers at any given 724 time, a strict bound SHOULD be applied to the active number of 725 Issuers in the ecosystem. We propose that allowing no more than 4 726 Issuers at any one time is highly preferable (leading to a maximum of 727 64 possible user segregations). However, as highlighted in 728 Section 7, having a very large user base (> 5 million users), could 729 potentially allow for larger values. Issuer replacements should only 730 occur with the same frequency as config rotations as they can lead to 731 similar losses in anonymity if clients still hold redemption tokens 732 for previously active Issuers. 734 In addition, we RECOMMEND that trusted registries indicate at all 735 times which Issuers are deemed to be active. If a Client is asked to 736 invoke any Privacy Pass exchange for an Issuer that is not declared 737 active, then the client SHOULD refuse to retrieve the Issuer public 738 key during the protocol. 740 5.3.1. Allowing More Issuers 742 The bounds on the numbers of Issuers that this document proposes 743 above are very restrictive. This is because this document considers 744 a situation where a Client could be challenged (and asked to redeem) 745 tokens for any Issuer. 747 An alternative system is to ensure a robust strategy for ensuring 748 that Clients only possess redemption tokens for a similarly small 749 number of Issuers at any one time. This prevents a malicious 750 verifier from being able to invoke redemptions for many Issuers since 751 the Client would only be holding redemption tokens for a small set of 752 Issuers. When a Client is issued tokens from a new Issuer and 753 already has tokens from the maximum number of Issuers, it simply 754 deletes the oldest set of redemption tokens in storage and then 755 stores the newly acquired tokens. 757 For example, if Clients ensure that they only hold redemption tokens 758 for 4 Issuers, then this increases the potential size of the 759 anonymity sets that the Client belongs to. However, this doesn't 760 protect Clients completely as it would if only 4 Issuers were 761 permitted across the whole system. For example, these 4 Issuers 762 could be different for each Client. Therefore, the selection of 763 Issuers they possess tokens for is still revealing. Understanding 764 this trade-off is important in deciding the effective anonymity of 765 each Client in the system. 767 5.3.1.1. Redemption Partitions 769 Another option to allow a large number of Issuers in the ecosystem, 770 while preventing the joining of a number of different tokens is for 771 the Client to maintain sharded "redemption partitions". This would 772 allow the Client to redeem the tokens it wishes to use in a 773 particular context, while still allowing the Client to maintain a 774 large variety of tokens from many Issuers. Within a redemption 775 partition, the Client limits the number of different Issuers used to 776 a small number to maintain the privacy properties the Client 777 requires. As long as each redemption partition maintains a strong 778 privacy boundary with each other, the verifier will only be able to 779 learn a number of bits of information up to the limits within that 780 "redemption partitions". 782 To support this strategy, the client keeps track of a partition which 783 contains the set of Issuers that redemptions have been attempted 784 against. An empty redemption is returned when the limit has been 785 hit: 787 Client(partition, issuer) Issuer(skS, pkS) 788 ------------------------------------------------------------ 789 if issuer not in partition { 790 if partition.length > REDEEM_LIMIT { 791 Output {} 792 return 793 } 794 partition.push(issuer) 795 } 796 token = store[issuer.id].pop() 797 req = Redeem(token, info) 799 req 800 ------------------> 802 if (dsIdx.includes(req.data)) { 803 raise ERR_DOUBLE_SPEND 804 } 805 resp = Verify(pkS, skS, req) 806 if resp.success { 807 dsIdx.push(req.data) 808 } 810 resp 811 <------------------ 812 Output resp 814 6. Security Considerations 816 We present a number of security considerations that prevent malicious 817 Clients from abusing the protocol. 819 6.1. Double-spend Protection 821 When applicable for non-interactive tokens, all Origins SHOULD 822 implement a robust storage-query mechanism for checking that tokens 823 sent by clients have not been spent before. Such tokens only need to 824 be checked for each Origin individually. But all Origins must 825 perform global double-spend checks to avoid clients from exploiting 826 the possibility of spending tokens more than once against distributed 827 token checking systems. For the same reason, the global data storage 828 must have quick update times. While an update is occurring it may be 829 possible for a malicious client to spend a token more than once. 831 6.2. Token Exhaustion 833 When a Client holds tokens for an Issuer, it is possible for any 834 verifier to invoke that client to redeem tokens for that Issuer. 835 This can lead to an attack where a malicious verifier can force a 836 Client to spend all of their tokens from a given Issuer. To prevent 837 this from happening, tokens can be scoped to single Origins such that 838 they can only be redeemed within for a single Origin. 840 If tokens are cross-Origin, Clients should use alternate methods to 841 prevent many tokens from being redeemed at once. For example, if the 842 Origin requests an excess of tokens, the Client could choose to not 843 present any tokens for verification if a redemption had already 844 occurred in a given time window. 846 7. Protocol Parameterization 848 This section provides a summary of the parameters used in the Privacy 849 Pass protocol ecosystem. These parameters are informed by both 850 privacy and security considerations that are highlighted in Section 5 851 and Section 6, respectively. These parameters are intended as a 852 single reference point for those implementing the protocol. 854 Firstly, let U be the total number of Clients (or users), I be the 855 total number of Issuers. We let M be the total number of metadata 856 bits that are allowed to be added by any given Issuer. Assuming that 857 each user accept tokens from a uniform sampling of all the possible 858 Issuers, as a worst-case analysis, this segregates Clients into a 859 total of 2^I buckets. As such, we see an exponential reduction in 860 the size of the anonymity set for any given user. This allows us to 861 specify the privacy constraints of the protocol below, relative to 862 the setting of A. 864 +==========================================+==================+ 865 | parameter | value | 866 +==========================================+==================+ 867 | Minimum anonymity set size (A) | 5000 | 868 +------------------------------------------+------------------+ 869 | Recommended key lifetime (L) | 2 - 24 weeks | 870 +------------------------------------------+------------------+ 871 | Recommended key rotation frequency (F) | L/2 | 872 +------------------------------------------+------------------+ 873 | Maximum additional metadata bits (M) | 1 | 874 +------------------------------------------+------------------+ 875 | Maximum allowed Issuers (I) | (log_2(U/A)-1)/2 | 876 +------------------------------------------+------------------+ 877 | Maximum active issuance keys | 1 | 878 +------------------------------------------+------------------+ 879 | Maximum active redemption keys | 2 | 880 +------------------------------------------+------------------+ 881 | Minimum cryptographic security parameter | 128 bits | 882 +------------------------------------------+------------------+ 884 Table 1 886 7.1. Justification 888 We make the following assumptions in these parameter choices. 890 * Inferring the identity of a user in a 5000-strong anonymity set is 891 difficult. 893 * After 2 weeks, all Clients in a system will have rotated to the 894 new key. 896 In terms of additional metadata, the only concrete applications of 897 Privacy Pass that use additional metadata require just a single bit. 898 Therefore, we set the ceiling of permitted metadata to 1 bit for now, 899 this may be revisited in future revisions. 901 The maximum choice of I is based on the equation 1/2 * U/2^(2I) = A. 902 This is derived from the fact that permitting I Issuers lead to 2^I 903 segregations of the total user-base U. Moreover, if we permit M = 1, 904 then this effectively halves the anonymity set for each Issuer, and 905 thus we incur a factor of 2I in the exponent. By reducing I, we 906 limit the possibility of performing the attacks mentioned in 907 Section 5. 909 We must also account for each user holding issued data for more then 910 one possible active keys. While this may also be a vector for 911 monitoring the access patterns of Clients, it is likely to 912 unavoidable that Clients hold valid issuance data for the previous 913 key epoch. This also means that the Issuer can continue to verify 914 redemption data for a previously used key. This makes the rotation 915 period much smoother for Clients. 917 For privacy reasons, it is recommended that key epochs are chosen 918 that limit Clients to holding issuance data for a maximum of two 919 keys. By choosing F = L/2 then the minimum value of F is a week, 920 since the minimum recommended value of L is 2 weeks. Therefore, by 921 the initial assumption, then all users should only have access to 922 only two keys at any given time. This reduces the anonymity set by 923 another half at most. 925 Finally, the minimum security parameter size is related to the 926 cryptographic security offered by the protocol that is run. This 927 parameter corresponds to the number of operations that any adversary 928 has in breaking one of the security guarantees in the Privacy Pass 929 protocol [I-D.ietf-privacypass-protocol]. 931 7.2. Example parameterization 933 Using the specification above, we can give some example 934 parameterizations. For example, the current Privacy Pass browser 935 extension [PPEXT] has nearly 300000 active users (from Chrome and 936 Firefox). As a result, log_2(U/A) is approximately 6 and so the 937 maximum value of I should be 3. 939 If the value of U is much bigger (e.g. 5 million) then this would 940 permit I = (log_2(5000000/5000)-1)/2 ~= 4 Issuers. 942 7.3. Allowing more Issuers 944 Using the recommendations in Section 5.3.1, it is possible to 945 tolerate larger number of Issuers if Clients in the ecosystem ensure 946 that they only store tokens for a small number of them. In 947 particular, if Clients limit their storage of redemption tokens to 948 the bound implied by I, then prevents a malicious verifier from 949 triggering redemptions for all Issuers in the ecosystem. 951 8. References 953 8.1. Normative References 955 [HTTP-Authentication] 956 "The Privacy Pass HTTP Authentication Scheme", n.d., 957 . 960 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 961 Requirement Levels", BCP 14, RFC 2119, 962 DOI 10.17487/RFC2119, March 1997, 963 . 965 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 966 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 967 May 2017, . 969 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 970 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 971 . 973 8.2. Informative References 975 [CONSISTENCY] 976 Davidson, A., Finkel, M., Thomson, M., and C. A. Wood, 977 "Key Consistency and Discovery", Work in Progress, 978 Internet-Draft, draft-wood-key-consistency-02, 4 March 979 2022, . 982 [HIJK21] Huang, S., Iyengar, S., Jeyaraman, S., Kushwah, S., Lee, 983 C. K., Luo, Z., Mohassel, P., Raghunathan, A., Shaikh, S., 984 Sung, Y. C., and A. Zhang, "PrivateStats: De-Identified 985 Authenticated Logging at Scale", January 2021, 986 . 990 [I-D.ietf-privacypass-protocol] 991 Celi, S., Davidson, A., Faz-Hernandez, A., Valdez, S., and 992 C. A. Wood, "Privacy Pass Issuance Protocol", Work in 993 Progress, Internet-Draft, draft-ietf-privacypass-protocol- 994 02, 31 January 2022, 995 . 998 [KLOR20] Kreuter, B., Lepoint, T., OrrĂ¹, M., and M. Raykova, 999 "Anonymous Tokens with Private Metadata Bit", Advances in 1000 Cryptology - CRYPTO 2020 pp. 308-336, 1001 DOI 10.1007/978-3-030-56784-2_11, 2020, 1002 . 1004 [PPEXT] "Privacy Pass Browser Extension", n.d., 1005 . 1008 [PPSRV] Sullivan, N., "Cloudflare Supports Privacy Pass", n.d., 1009 . 1012 [RFC6962] Laurie, B., Langley, A., and E. Kasper, "Certificate 1013 Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013, 1014 . 1016 Appendix A. Acknowledgements 1018 The authors would like to thank Scott Hendrickson, Tommy Pauly, 1019 Benjamin Schwartz, Steven Valdez and other members of the Privacy 1020 Pass Working Group for many helpful contributions to this document. 1022 Authors' Addresses 1024 Alex Davidson 1025 LIP 1026 Lisbon 1027 Portugal 1028 Email: alex.davidson92@gmail.com 1030 Jana Iyengar 1031 Fastly 1032 Email: jri@fastly.com 1034 Christopher A. Wood 1035 Cloudflare 1036 101 Townsend St 1037 San Francisco, 1038 United States of America 1039 Email: caw@heapingbits.net