idnits 2.17.1 draft-ietf-privacypass-protocol-01.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 copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (19 February 2021) is 1162 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Outdated reference: A later version (-21) exists of draft-irtf-cfrg-voprf-05 -- Obsolete informational reference (is this intentional?): RFC 7049 (Obsoleted by RFC 8949) -- Obsolete informational reference (is this intentional?): RFC 7159 (Obsoleted by RFC 8259) Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Celi 3 Internet-Draft Cloudflare 4 Intended status: Informational A. Davidson 5 Expires: 23 August 2021 LIP 6 A. Faz-Hernandez 7 Cloudflare 8 19 February 2021 10 Privacy Pass Protocol Specification 11 draft-ietf-privacypass-protocol-01 13 Abstract 15 This document specifies the Privacy Pass protocol. This protocol 16 provides anonymity-preserving authorization of clients to servers. 17 In particular, client re-authorization events cannot be linked to any 18 previous initial authorization. Privacy Pass is intended to be used 19 as a performant protocol in the application-layer. 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 23 August 2021. 38 Copyright Notice 40 Copyright (c) 2021 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 Simplified BSD License text 49 as described in Section 4.e of the Trust Legal Provisions and are 50 provided without warranty as described in the Simplified BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 55 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 56 3. Background . . . . . . . . . . . . . . . . . . . . . . . . . 4 57 3.1. Motivating use-cases . . . . . . . . . . . . . . . . . . 4 58 3.2. Anonymity and security guarantees . . . . . . . . . . . . 5 59 3.3. Basic assumptions . . . . . . . . . . . . . . . . . . . . 5 60 4. Protocol description . . . . . . . . . . . . . . . . . . . . 5 61 4.1. Server setup . . . . . . . . . . . . . . . . . . . . . . 6 62 4.2. Client setup . . . . . . . . . . . . . . . . . . . . . . 6 63 4.3. Issuance phase . . . . . . . . . . . . . . . . . . . . . 6 64 4.4. Redemption phase . . . . . . . . . . . . . . . . . . . . 8 65 4.4.1. Client info . . . . . . . . . . . . . . . . . . . . . 8 66 4.4.2. Double-spend protection . . . . . . . . . . . . . . . 9 67 4.5. Handling errors . . . . . . . . . . . . . . . . . . . . . 9 68 5. Functionality . . . . . . . . . . . . . . . . . . . . . . . . 9 69 5.1. Data structures . . . . . . . . . . . . . . . . . . . . . 9 70 5.1.1. Ciphersuite . . . . . . . . . . . . . . . . . . . . . 9 71 5.1.2. Keys . . . . . . . . . . . . . . . . . . . . . . . . 9 72 5.1.3. CommitRequest . . . . . . . . . . . . . . . . . . . . 10 73 5.1.4. CommitResponse . . . . . . . . . . . . . . . . . . . 10 74 5.1.5. IssuanceInput . . . . . . . . . . . . . . . . . . . . 10 75 5.1.6. IssuanceResponse . . . . . . . . . . . . . . . . . . 10 76 5.1.7. RedemptionToken . . . . . . . . . . . . . . . . . . . 11 77 5.1.8. RedemptionRequest . . . . . . . . . . . . . . . . . . 11 78 5.1.9. RedemptionResponse . . . . . . . . . . . . . . . . . 11 79 5.2. API functions . . . . . . . . . . . . . . . . . . . . . . 12 80 5.2.1. Prepare . . . . . . . . . . . . . . . . . . . . . . . 12 81 5.2.2. Commit . . . . . . . . . . . . . . . . . . . . . . . 12 82 5.2.3. Generate . . . . . . . . . . . . . . . . . . . . . . 12 83 5.2.4. Issue . . . . . . . . . . . . . . . . . . . . . . . . 13 84 5.2.5. Process . . . . . . . . . . . . . . . . . . . . . . . 13 85 5.2.6. Redeem . . . . . . . . . . . . . . . . . . . . . . . 14 86 5.2.7. Verify . . . . . . . . . . . . . . . . . . . . . . . 14 87 5.3. Error types . . . . . . . . . . . . . . . . . . . . . . . 14 88 6. Security considerations . . . . . . . . . . . . . . . . . . . 15 89 6.1. Unlinkability . . . . . . . . . . . . . . . . . . . . . . 15 90 6.2. One-more unforgeability . . . . . . . . . . . . . . . . . 16 91 6.3. Double-spend protection . . . . . . . . . . . . . . . . . 16 92 6.4. Additional token metadata . . . . . . . . . . . . . . . . 17 93 6.5. Maximum number of tokens issued . . . . . . . . . . . . . 17 94 7. VOPRF instantiation . . . . . . . . . . . . . . . . . . . . . 17 95 7.1. Recommended ciphersuites . . . . . . . . . . . . . . . . 17 96 7.2. Protocol contexts . . . . . . . . . . . . . . . . . . . . 18 97 7.3. Functionality . . . . . . . . . . . . . . . . . . . . . . 18 98 7.3.1. Generate . . . . . . . . . . . . . . . . . . . . . . 18 99 7.3.2. Issue . . . . . . . . . . . . . . . . . . . . . . . . 19 100 7.3.3. Process . . . . . . . . . . . . . . . . . . . . . . . 19 101 7.3.4. Redeem . . . . . . . . . . . . . . . . . . . . . . . 19 102 7.3.5. Verify . . . . . . . . . . . . . . . . . . . . . . . 19 103 7.4. Security justification . . . . . . . . . . . . . . . . . 20 104 8. Protocol ciphersuites . . . . . . . . . . . . . . . . . . . . 20 105 8.1. PP(OPRF2) . . . . . . . . . . . . . . . . . . . . . . . . 20 106 8.2. PP(OPRF4) . . . . . . . . . . . . . . . . . . . . . . . . 21 107 8.3. PP(OPRF5) . . . . . . . . . . . . . . . . . . . . . . . . 21 108 9. Extensions framework policy . . . . . . . . . . . . . . . . . 21 109 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 110 10.1. Normative References . . . . . . . . . . . . . . . . . . 22 111 10.2. Informative References . . . . . . . . . . . . . . . . . 22 112 Appendix A. Document contributors . . . . . . . . . . . . . . . 23 113 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23 115 1. Introduction 117 A common problem on the Internet is providing an effective mechanism 118 for servers to derive trust from clients that they interact with. 119 Typically, this can be done by providing some sort of authorization 120 challenge to the client. But this also negatively impacts the 121 experience of clients that regularly have to solve such challenges. 123 To mitigate accessibility issues, a client that correctly solves the 124 challenge can be provided with a cookie. This cookie can be 125 presented the next time the client interacts with the server, instead 126 of performing the challenge. However, this does not solve the 127 problem of reauthorization of clients across multiple domains. Using 128 current tools, providing some multi-domain authorization token would 129 allow linking client browsing patterns across those domains, and 130 severely reduces their online privacy. 132 The Privacy Pass protocol provides a set of cross-domain 133 authorization tokens that protect the client's anonymity in message 134 exchanges with a server. This allows clients to communicate an 135 attestation of a previously authenticated server action, without 136 having to reauthenticate manually. The tokens retain anonymity in 137 the sense that the act of revealing them cannot be linked back to the 138 session where they were initially issued. 140 This document lays out the generic description of the protocol, along 141 with the data and message formats. We detail an implementation of 142 the protocol functionality based on the description of a verifiable 143 oblivious pseudorandom function [I-D.irtf-cfrg-voprf]. 145 This document DOES NOT cover the architectural framework required for 146 running and maintaining the Privacy Pass protocol in the Internet 147 setting. In addition, it DOES NOT cover the choices that are 148 necessary for ensuring that client privacy leaks do not occur. Both 149 of these considerations are covered in a separate document 150 [draft-davidson-pp-architecture]. In addition, 151 [draft-svaldez-pp-http-api] provides an instantiation of this 152 protocol intended for the HTTP setting. 154 2. Terminology 156 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 157 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 158 document are to be interpreted as described in [RFC2119]. 160 The following terms are used throughout this document. 162 * Server: A service that provides the server-side functionality 163 required by the protocol. May be referred to as the issuer. 165 * Client: An entity that seeks authorization from a server that 166 supports interactions in the Privacy Pass protocol. 168 * Key: The secret key used by the server for authorizing client 169 data. 171 We assume that all protocol messages are encoded into raw byte format 172 before being sent. We use the TLS presentation language [RFC8446] to 173 describe the structure of protocol data types and messages. 175 3. Background 177 We discuss the core motivation behind the protocol along with the 178 guarantees and assumptions that we make in this document. 180 3.1. Motivating use-cases 182 The Privacy Pass protocol was originally developed to provide 183 anonymous authorization of Tor users. In particular, the protocol 184 allows clients to reveal authorization tokens that they have been 185 issued without linking the authorization to the actual issuance 186 event. This means that the tokens cannot be used to link the 187 browsing patterns of clients that reveal tokens. 189 Beyond these uses-cases, the Privacy Pass protocol is used in a 190 number of practical applications. See [DGSTV18], [TrustTokenAPI], 191 [PrivateStorage], [OpenPrivacy], and [Brave] for examples. 193 3.2. Anonymity and security guarantees 195 Privacy Pass provides anonymity-preserving authorization tokens for 196 clients. Throughout this document, we use the terms "anonymous", 197 "anonymous-preserving" and "anonymity" to refer to the core security 198 guarantee of the protocol. Informally, this guarantee means that any 199 token issued by a server key and subsequently redeemed is 200 indistinguishable from any other token issued under the same key. 202 Privacy Pass also prohibits clients from forging tokens, as otherwise 203 the protocol would have little value as an authorization protocol. 204 Informally, this means any client that is issued "N" tokens under a 205 given server key cannot redeem more than "N" valid tokens. 207 Section 6 elaborates on these protocol anonymity and security 208 requirements. 210 3.3. Basic assumptions 212 We make only a few minimal assumptions about the environment of the 213 clients and servers supporting the Privacy Pass protocol. 215 * At any one time, we assume that the server uses only one 216 configuration containing their ciphersuite choice along with their 217 secret key data. This ensures that all clients are issued tokens 218 under the single key associated with any given epoch. 220 * We assume that the client has access to a global directory of the 221 current public parts of the configurations used the server. 223 The wider ecosystem that this protocol is employed in is described in 224 [draft-davidson-pp-architecture]. 226 4. Protocol description 228 The Privacy Pass protocol is split into two phases that are built 229 upon the functionality described in Section 5 later. 231 The first phase, "issuance", provides the client with unlinkable 232 tokens that can be used to initiate re-authorization with the server 233 in the future. The second phase, "redemption", allows the client to 234 redeem a given re-authorization token with the server that it 235 interacted with during the issuance phase. The protocol must satisfy 236 two cryptographic security requirements known as "unlinkability" and 237 "unforgeability". These requirements are covered in Section 6. 239 4.1. Server setup 241 Before the protocol takes place, the server chooses a ciphersuite and 242 generates a keypair by running "(pkS, skS) = KeyGen()". This 243 configuration must be available to all clients that interact with the 244 server (for the purpose of engaging in a Privacy Pass exchange). We 245 assume that the server has a public (and unique) identity that the 246 client uses to retrieve this configuration. 248 4.2. Client setup 250 The client initialises a global storage system "store" that allows it 251 store the tokens that are received during issuance. The storage 252 system is a map of server identifiers ("server.id") to arrays of 253 stored tokens. We assume that the client knows the server public key 254 "pkS" ahead of time. The client picks a value "m" of tokens to 255 receive during the issuance phase. In 256 [draft-davidson-pp-architecture] we discuss mechanisms that the 257 client can use to ensure that this public key is consistent across 258 the entire ecosystem. 260 4.3. Issuance phase 262 The issuance phase is a two-round protocol that allows the client to 263 receive "m" anonymous authorization tokens from the server. The 264 first round sees the server generate a commitment. The second round 265 sees the server issue a token to the client. 267 Client(pkS, m, info) Server(skS, pkS) 268 ------------------------------------------------------------ 270 commit_req = Prepare(info) 272 commit_req 273 -------------------> 275 commit_resp = Commit(skS, pkS, commit_req) 277 commit_resp 278 <------------------- 280 cInput = Generate(m, commit_resp) 281 req = cInput.req 283 req 284 -------------------> 286 issueResp = Issue(pkS, skS, req) 288 serverResp 289 <------------------- 291 tokens = Process(pkS, cInput, serverResp) 292 store[server.id].push(tokens) 294 Note that the first round of the protocol is only necessitated for 295 certain ciphersuites that require client and servers commit to some 296 value. When such commitment "commit_resp" is generated and sent to 297 the client, the client returns "commit_resp" with the 298 "IssuanceRequest" message. The server MUST check that the commitment 299 corresponds to "commit_resp" that was previously committed. This 300 requires the commitment to either be a reference to some commitment 301 on the server, or the commitment be an encrypted (and authenticated) 302 blob that the server can use to recover commitment. The mechanism by 303 which servers handle this commitment is implementation specific, and 304 similar to how TLS session resumption state is managed; see [RFC8446] 305 for details. In addition, the "Commit" function is implementation- 306 specific and MUST be defined by the underlying ciphersuite. 308 When the server does not need to generate this commitment, the client 309 instead DOES NOT send the "CommitRequest" message, and runs: 311 cInput = Generate(m, "") 312 A server that is expecting some non-empty "commit_resp" to be passed 313 must abort the protocol on receiving a request containing an empty 314 "commit_resp" value. 316 Note: currently, no ciphersuites are supported that support working 317 with empty commitment messages. 319 4.4. Redemption phase 321 The redemption phase allows the client to anonymously reauthenticate 322 to the server, using data that it has received from a previous 323 issuance phase. 325 Client(info) Server(skS, pkS) 326 ------------------------------------------------------------ 327 token = store[server.id].pop() 328 req = Redeem(token, info) 330 req 331 ------------------> 333 if (dsIdx.includes(req.data)) { 334 raise ERR_DOUBLE_SPEND 335 } 336 resp = Verify(pkS, skS, req) 337 if (resp.success) { 338 dsIdx.push(req.data) 339 } 341 resp 342 <------------------ 343 Output resp 345 4.4.1. Client info 347 The client input "info" is arbitrary byte data that is used for 348 linking the redemption request to the specific session. We RECOMMEND 349 that "info" is constructed as the following concatenated byte-encoded 350 data: 352 len(aux) || aux || len(server.id) || server.id || current_time() 354 where "len(x)" is the length of "x" in bytes, and "aux" is arbitrary 355 auxiliary data chosen by the client. The usage of "current_time()" 356 allows the server to check that the redemption request has happened 357 in an appropriate time window. 359 4.4.2. Double-spend protection 361 To protect against clients that attempt to spend a value "req.data" 362 more than once, the server uses an index, "dsIdx", to collect valid 363 inputs it witnesses. Since this store needs to only be optimized for 364 storage and querying, a structure such as a Bloom filter suffices. 365 The storage should be parameterized to live as long as the server 366 keypair that is in use. See Section 6 for more details. 368 4.5. Handling errors 370 It is possible for the API functions from Section 5.2 to return one 371 of the errors indicated in Section 5.3 rather than their expected 372 value. In these cases, we assume that the entire protocol aborts. 374 5. Functionality 376 This section details the data types and API functions that are used 377 to construct the protocol in Section 4. 379 We provide an explicit instantiation of the Privacy Pass API in 380 Section 7.3, based on the public API provided in 381 [I-D.irtf-cfrg-voprf]. 383 5.1. Data structures 385 The following data structures are used throughout the Privacy Pass 386 protocol and are written in the TLS presentation language [RFC8446]. 387 It is intended that any of these data structures can be written into 388 widely-adopted encoding schemes such as those detailed in TLS 389 [RFC8446], CBOR [RFC7049], and JSON [RFC7159]. 391 5.1.1. Ciphersuite 393 The "Ciphersuite" enum provides identifiers for each of the supported 394 ciphersuites of the protocol. Some initial values that are supported 395 by the core protocol are described in Section 8. Note that the list 396 of supported ciphersuites may be expanded by extensions to the core 397 protocol description in separate documents. 399 5.1.2. Keys 401 We use the following types to describe the public and private keys 402 used by the server. 404 opaque PublicKey<1..2^16-1> 405 opaque PrivateKey<1..2^16-1> 407 5.1.3. CommitRequest 409 The "CommitRequest" struct is simply a fixed message allowing opaque 410 metadata. 412 struct { 413 opaque info<1..2^16-1> 414 } CommitRequest; 416 5.1.4. CommitResponse 418 The "CommitResponse" struct is contains an opaque set of bytes that 419 correspond to some commitment that the server has generated. The 420 structure and format of this value is implementation specific 421 depending on whether the server is stateful. 423 struct { 424 opaque commitment<1..2^16-1> 425 } CommitResponse; 427 5.1.5. IssuanceInput 429 The "IssuanceInput" struct describes the data that is initially 430 generated by the client during the issuance phase. 432 Firstly, we define sequences of bytes that partition the client 433 input. 435 opaque Internal<1..2^16-1> 436 opaque IssuanceRequest<1..2^16-1> 438 These data types represent members of the wider "IssuanceInput" data 439 type. 441 struct { 442 Internal data[m] 443 IssuanceRequest req[m] 444 } IssuanceInput; 446 Note that a "IssuanceInput" contains equal-length arrays of 447 "Internal" and "IssuanceRequest" types corresponding to the number of 448 tokens that should be issued. 450 5.1.6. IssuanceResponse 452 Firstly, the "IssuedToken" type corresponds to a single sequence of 453 bytes that represents a single issued token received from the server. 455 opaque IssuedToken<1..2^16-1> 457 Then an "IssuanceResponse" corresponds to a collection of 458 "IssuedTokens" as well as a sequence of bytes "proof". 460 struct { 461 IssuedToken tokens[m] 462 opaque proof<1..2^16-1> 463 } 465 The value of "m" is equal to the length of the "IssuanceRequest" 466 vector sent by the client. 468 5.1.7. RedemptionToken 470 The "RedemptionToken" struct contains the data required to generate 471 the client message in the redemption phase of the Privacy Pass 472 protocol. 474 struct { 475 opaque data<1..2^16-1>; 476 opaque issued<1..2^16-1>; 477 } RedemptionToken; 479 5.1.8. RedemptionRequest 481 The "RedemptionRequest" struct consists of the data that is sent by 482 the client during the redemption phase of the protocol. 484 struct { 485 opaque data<1..2^16-1>; 486 opaque tag<1..2^16-1>; 487 opaque info<1..2^16-1>; 488 } RedemptionRequest; 490 5.1.9. RedemptionResponse 492 The "RedemptionResponse" struct corresponds to a boolean value that 493 indicates whether the "RedemptionRequest" sent by the client is 494 valid. It can also contain any associated data. 496 struct { 497 boolean success; 498 opaque ad<1..2^16-1>; 499 } RedemptionResponse; 501 5.2. API functions 503 The following functions wrap the core of the functionality required 504 in the Privacy Pass protocol. For each of the descriptions, we 505 essentially provide the function signature, leaving the actual 506 contents to be defined by specific instantiations or extensions of 507 the protocol. 509 5.2.1. Prepare 511 A function run by the client to prepare for a commitment will used 512 during the issuance flow of the Privacy Pass protocol. 514 Inputs: 516 "info": An opaque byte application-specific byte string. 518 Outputs: 520 "commit_req": A "CommitRequest" struct. 522 This function should be implemented by any ciphersuites that require 523 a two-phase issuance protocol ("COMMIT=true"). 525 5.2.2. Commit 527 A function run by the server that generates a commitment in the first 528 phase of the issuance protocol. 530 Inputs: 532 * "skS": A server "PrivateKey". 534 * "pkS": A server "PublicKey". 536 * "commit_req": A "CommitRequest" struct 538 Outputs: 540 * "commit_resp": A "CommitResponse" struct. 542 This function should be implemented by any ciphersuites that require 543 a two-phase issuance protocol ("COMMIT=true"). 545 5.2.3. Generate 547 A function run by the client to generate the initial data that is 548 used as its input in the Privacy Pass protocol. 550 Inputs: 552 * "m": A "uint8" value corresponding to the number of Privacy Pass 553 tokens to generate. 555 Outputs: 557 * "input": An "IssuanceInput" struct. 559 5.2.4. Issue 561 A function run by the server to issue valid redemption tokens to the 562 client. 564 Inputs: 566 * "pkS": A server "PublicKey". 568 * "skS": A server "PrivateKey". 570 * "req": An "IssuanceRequest" struct. 572 Outputs: 574 * "resp": An "IssuanceResponse" struct. 576 Throws: 578 * "ERR_FAILED_COMMITMENT" (Section 5.3) 580 5.2.5. Process 582 Run by the client when processing the server response in the issuance 583 phase of the protocol. 585 Inputs: 587 * "pkS": An server "PublicKey". 589 * "input": An "IssuanceInput" struct. 591 * "resp": An "IssuanceResponse" struct. 593 Outputs: 595 * "tokens": A vector of "RedemptionToken" structs, whose length is 596 equal to length of the internal "ServerEvaluation" vector in the 597 "IssuanceResponse" struct. 599 Throws: 601 * "ERR_PROOF_VALIDATION" (Section 5.3) 603 5.2.6. Redeem 605 Run by the client in the redemption phase of the protocol to generate 606 the client's message. 608 Inputs: 610 * "token": A "RedemptionToken" struct. 612 * "info": An "opaque<1..2^16-1>" type corresponding to data that is 613 linked to the redemption. See Section 4.4.1 for advice on how to 614 construct this. 616 Outputs: 618 * "req": A "RedemptionRequest" struct. 620 5.2.7. Verify 622 Run by the server in the redemption phase of the protocol. 623 Determines whether the data sent by the client is valid. 625 Inputs: 627 * "pkS": An server "PublicKey". 629 * "skS": An server "PrivateKey". 631 * "req": A "RedemptionRequest" struct. 633 Outputs: 635 * "resp": A "RedemptionResponse" struct. 637 5.3. Error types 639 * "ERR_PROOF_VALIDATION": Error occurred when a client attempted to 640 verify the proof that is part of the server's response. 642 * "ERR_DOUBLE_SPEND": Error occurred when a client has attempted to 643 redeem a token that has already been used for authorization. 645 * "ERR_FAILED_COMMITMENT": Error occurs during issuance phase if 646 non-empty commitment does not match the commitment generated in 647 the first round. 649 6. Security considerations 651 We discuss the security requirements that are necessary to uphold 652 when instantiating the Privacy Pass protocol. In particular, we 653 focus on the security requirements of "unlinkability", and 654 "unforgeability". Informally, the notion of unlinkability is 655 required to preserve the anonymity of the client in the redemption 656 phase of the protocol. The notion of unforgeability is to protect 657 against an adversarial client that may look to subvert the security 658 of the protocol. 660 Both requirements are modelled as typical cryptographic security 661 games, following the formats laid out in [DGSTV18] and [KLOR20]. 663 Note that the privacy requirements of the protocol are covered in the 664 architectural framework document [draft-davidson-pp-architecture]. 666 6.1. Unlinkability 668 Formally speaking the security model is the following: 670 * The adversary runs the server setup and generates a keypair "(pkS, 671 skS)". 673 * The adversary specifies a number "Q" of issuance phases to 674 initiate, where each phase "i in range(Q)" consists of "m_i" Issue 675 evaluations. 677 * The adversary runs "Issue" using the keypair that it generated on 678 each of the client messages in the issuance phase. 680 * When the adversary wants, it stops the issuance phase, and a 681 random number "l" is picked from "range(Q)". 683 * A redemption phase is initiated with a single token with index "i" 684 randomly sampled from "range(m_l)". 686 * The adversary guesses an index "l_guess" corresponding to the 687 index of the issuance phase that it believes the redemption token 688 was received in. 690 * The adversary succeeds if "l == l_guess". 692 The security requirement is that the adversary has only a negligible 693 probability of success greater than "1/Q". 695 6.2. One-more unforgeability 697 The one-more unforgeability requirement states that it is hard for 698 any adversarial client that has received "m" valid tokens from the 699 issuance phase to redeem "m+1" of them. In essence, this requirement 700 prevents a malicious client from being able to forge valid tokens 701 based on the Issue responses that it sees. 703 The security model roughly takes the following form: 705 * The adversary specifies a number "Q" of issuance phases to 706 initiate with the server, where each phase "i in range(Q)" 707 consists of "m_i" server evaluation. Let "m = sum(m_i)" where "i 708 in range(Q)". 710 * The adversary receives "Q" responses, where the response with 711 index "i" contains "m_i" individual tokens. 713 * The adversary initiates "m_adv" redemption sessions with the 714 server and the server verifies that the sessions are successful 715 (return true), and that each request includes a unique token. The 716 adversary succeeds in "m_succ =< m_adv" redemption sessions. 718 * The adversary succeeds if "m_succ > m". 720 The security requirement is that the adversarial client has only a 721 negligible probability of succeeding. 723 Note that [KLOR20] strengthens the capabilities of the adversary, in 724 comparison to the original work of [DGSTV18]. In [KLOR20], the 725 adversary is provided with oracle access that allows it to verify 726 that the server responses in the issuance phase are valid. 728 6.3. Double-spend protection 730 All issuing servers should implement a robust, global storage-query 731 mechanism for checking that tokens sent by clients have not been 732 spent before. Such tokens only need to be checked for each server 733 individually. This prevents clients from "replaying" previous 734 requests, and is necessary for achieving the unforgeability 735 requirement. 737 6.4. Additional token metadata 739 Some use-cases of the Privacy Pass protocol benefit from associating 740 a limited amount of metadata with tokens that can be read by the 741 server when a token is redeemed. Adding metadata to tokens can be 742 used as a vector to segment the anonymity of the client in the 743 protocol. Therefore, it is important that any metadata that is added 744 is heavily limited. 746 Any additional metadata that can be added to redemption tokens should 747 be described in the specific protocol instantiation. Note that any 748 additional metadata will have to be justified in light of the privacy 749 concerns raised above. For more details on the impacts associated 750 with segmenting user privacy, see [draft-davidson-pp-architecture]. 752 Any metadata added to tokens will be considered either "public" or 753 "private". Public metadata corresponds to unmodifiable bits that a 754 client can read. Private metadata corresponds to unmodifiable 755 private bits that should be obscured to the client. 757 Note that the instantiation in Section 7 provides randomized 758 redemption tokens with no additional metadata for an server with a 759 single key. 761 6.5. Maximum number of tokens issued 763 Servers SHOULD impose a hard ceiling on the number of tokens that can 764 be issued in a single issuance phase to a client. If there is no 765 limit, malicious clients could abuse this and cause excessive 766 computation, leading to a Denial-of-Service attack. 768 7. VOPRF instantiation 770 In this section, we show how to instantiate the functional API in 771 Section 5 with the VOPRF protocol described in [I-D.irtf-cfrg-voprf]. 772 Moreover, we show that this protocol satisfies the security 773 requirements laid out in Section 6, based on the security proofs 774 provided in [DGSTV18] and [KLOR20]. 776 7.1. Recommended ciphersuites 778 The RECOMMENDED server ciphersuites are as follows: detailed in 779 [I-D.irtf-cfrg-voprf]: 781 * OPRF(decaf448, SHA-512) (ID = 0x0002); 783 * OPRF(P-384, SHA-512) (ID = 0x0004); 784 * OPRF(P-521, SHA-512) (ID = 0x0005). 786 We deliberately avoid the usage of smaller ciphersuites (associated 787 with P-256 and ristretto255) due to the potential to reduce security 788 to unfavourable levels via static Diffie Hellman attacks. See 789 [I-D.irtf-cfrg-voprf] for more details. 791 7.2. Protocol contexts 793 Note that we must run the verifiable version of the protocol in 794 [I-D.irtf-cfrg-voprf]. Therefore the "server" takes the role of the 795 "Server" running in "modeVerifiable". In other words, the "server" 796 runs "ctxtS = SetupVerifiableServer(suite, skS, pkS)"; where "suite" 797 is one of the ciphersuites in Section 7.1, "skS" and "pkS" is the 798 server's secret and public key respectively (generated by calling 799 "KeyGen"). It returns "ctxtS", which is the Server context. 800 Likewise, run "ctxtC = SetupVerifiableClient(suite, pkS)" to generate 801 the Client context. 803 7.3. Functionality 805 We instantiate each functions using the API functions in 806 [I-D.irtf-cfrg-voprf]. Note that we use the framework mentioned in 807 the document to allow for batching multiple tokens into a single 808 VOPRF evaluation. For the explicit signatures of each of the 809 functions, refer to Section 5. 811 7.3.1. Generate 813 The generate functionality generates an initial set of tokens and 814 blinded representation on the client-side. The function also takes 815 an optional (possibly empty) value for a commitment "com" committed 816 to by the server. 818 def Generate(m, com): 819 tokens = [] 820 blindedTokens = [] 821 for i in range(m): 822 x = random_bytes() 823 (token, blindedToken) = Blind(x, com) 824 tokens[i] = token 825 blindedTokens[i] = blindedToken 826 return IssuanceInput { 827 data: tokens, 828 req: blindedTokens, 829 } 831 7.3.2. Issue 833 For this functionality, note that we supply multiple tokens in "req" 834 to "Evaluate". This allows batching a single proof object for 835 multiple evaluations. While the construction in 836 [I-D.irtf-cfrg-voprf] only permits a single input, we follow the 837 advice for providing vectors of inputs. 839 def Issue(pkS, skS, req): 840 elements, proof = Evaluate(skS, pkS, req) 841 return IssuanceResponse { 842 tokens: elements, 843 proof: proof, 844 } 846 7.3.3. Process 848 Similarly to "Issue", we follow the advice for providing vectors of 849 inputs to the "Unblind" function for verifying the batched proof 850 object. 852 Process(pkS, input, resp): 853 unblindedTokens = Unblind(input.data, resp.elements, 854 input.req, pkS, resp.proof) 855 redemptionTokens = [] 856 for bt in unblindedTokens: 857 rt = RedemptionToken { data: input.data, issued: bt } 858 redemptionTokens[i] = rt 859 return redemptionTokens 861 7.3.4. Redeem 863 def Redeem(token, info): 864 tag = Finalize(token.data, token.issued, info) 865 return RedemptionRequest { 866 data: data, 867 tag: tag, 868 info: info, 869 } 871 7.3.5. Verify 873 def Verify(pkS, skS, req): 874 resp = VerifyFinalize(skS, req.data, req.info, req.tag) 875 Output RedemptionResponse { 876 success: resp 877 } 879 7.4. Security justification 881 The protocol devised in Section 4, coupled with the API instantiation 882 in Section 7.3, are equivalent to the protocol description in 883 [DGSTV18] and [KLOR20] from a security perspective. In [DGSTV18], it 884 is proven that this protocol satisfies the security requirements of 885 unlinkability (Section 6.1) and unforgeability (Section 6.2). 887 The unlinkability property follows unconditionally as the view of the 888 adversary in the redemption phase is distributed independently of the 889 issuance phase. The unforgeability property follows from the one- 890 more decryption security of the ElGamal cryptosystem [DGSTV18]. In 891 [KLOR20] it is also proven that this protocol satisfies the stronger 892 notion of unforgeability, where the adversary is granted a 893 verification oracle, under the chosen-target Diffie-Hellman 894 assumption. 896 Note that the existing security proofs do not leverage the VOPRF 897 primitive as a black-box in the security reductions. Instead, it 898 relies on the underlying operations in a non-black-box manner. 899 Hence, an explicit reduction from the generic VOPRF primitive to the 900 Privacy Pass protocol would strengthen these security guarantees. 902 8. Protocol ciphersuites 904 The ciphersuites that we describe for the Privacy Pass protocol are 905 derived from the core instantiations of the protocol (such as in 906 Section 7). 908 In each of the ciphersuites below, the maximum security provided 909 corresponds to the maximum difficulty of computing a discrete 910 logarithm in the group. Note that the actual security level MAY be 911 lower. See the security considerations in [I-D.irtf-cfrg-voprf] for 912 examples. 914 The COMMIT parameter refers to whether the first round of the 915 issuance phase of the protocol is necessary. When this is false, the 916 client ignores the first message and uses an empty value for the 917 commitment parameter to "Generate". 919 8.1. PP(OPRF2) 921 * OPRF2 = OPRF(decaf448, SHA-512) 923 * ID = 0x0001 925 * COMMIT = false 926 * Maximum security provided: 224 bits 928 8.2. PP(OPRF4) 930 * OPRF4 = OPRF(P-384, SHA-512) 932 * ID = 0x0002 934 * COMMIT = false 936 * Maximum security provided: 192 bits 938 8.3. PP(OPRF5) 940 * OPRF5 = OPRF(P-521, SHA-512) 942 * ID = 0x0003 944 * COMMIT = false 946 * Maximum security provided: 256 bits 948 9. Extensions framework policy 950 The intention with providing the Privacy Pass API in Section 5 is to 951 allow new instantiations of the Privacy Pass protocol. These 952 instantiations may provide either modified VOPRF constructions, or 953 simply implement the API in a completely different way. 955 Extensions to this initial draft SHOULD be specified as separate 956 documents taking one of two possible routes: 958 * Produce new VOPRF-like primitives that use the same public API 959 provided in [I-D.irtf-cfrg-voprf] to implement the Privacy Pass 960 API, but with different internal operations. 962 * Implement the Privacy Pass API in a different way to the proposed 963 implementation in Section 7. 965 If an extension requires changing the generic protocol description as 966 described in Section 4, then the change may have to result in changes 967 to the draft specification here also. 969 Each new extension that modifies the internals of the protocol in 970 either of the two ways MUST re-justify that the extended protocol 971 still satisfies the security requirements in Section 6. Protocol 972 extensions MAY put forward new security guarantees if they are 973 applicable. 975 The extensions MUST also conform with the extension framework policy 976 as set out in the architectural framework document. For example, 977 this may concern any potential impact on client anonymity that the 978 extension may introduce. 980 10. References 982 10.1. Normative References 984 [draft-davidson-pp-architecture] 985 Davidson, A., "Privacy Pass: Architectural Framework", 986 n.d., . 989 [draft-svaldez-pp-http-api] 990 Valdez, S., "Privacy Pass: HTTP API", n.d., 991 . 994 [I-D.irtf-cfrg-voprf] 995 Davidson, A., Faz-Hernandez, A., Sullivan, N., and C. 996 Wood, "Oblivious Pseudorandom Functions (OPRFs) using 997 Prime-Order Groups", Work in Progress, Internet-Draft, 998 draft-irtf-cfrg-voprf-05, 2 November 2020, 999 . 1002 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1003 Requirement Levels", BCP 14, RFC 2119, 1004 DOI 10.17487/RFC2119, March 1997, 1005 . 1007 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 1008 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 1009 . 1011 10.2. Informative References 1013 [Brave] "Brave Rewards", n.d., . 1015 [DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously", 1016 n.d., . 1019 [KLOR20] "Anonymous Tokens with Private Metadata Bit", n.d., 1020 . 1022 [OpenPrivacy] 1023 "Token Based Services - Differences from PrivacyPass", 1024 n.d., . 1027 [PrivateStorage] 1028 Steininger, L., "The Path from S4 to PrivateStorage", 1029 n.d., . 1032 [RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object 1033 Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049, 1034 October 2013, . 1036 [RFC7159] Bray, T., Ed., "The JavaScript Object Notation (JSON) Data 1037 Interchange Format", RFC 7159, DOI 10.17487/RFC7159, March 1038 2014, . 1040 [TrustTokenAPI] 1041 WICG, ., "Trust Token API", n.d., 1042 . 1044 Appendix A. Document contributors 1046 * Alex Davidson (alex.davidson92@gmail.com) 1048 * Sofia Celi (cherenkov@riseup.net) 1050 * Christopher Wood (caw@heapingbits.net) 1052 Authors' Addresses 1054 Sofía Celi 1055 Cloudflare 1056 Lisbon 1057 Portugal 1059 Email: sceli@cloudflare.com 1061 Alex Davidson 1062 LIP 1063 Lisbon 1064 Portugal 1066 Email: alex.davidson92@gmail.com 1067 Armando Faz-Hernandez 1068 Cloudflare 1069 101 Townsend St 1070 San Francisco, 1071 United States of America 1073 Email: armfazh@cloudflare.com