idnits 2.17.1 draft-davidson-pp-protocol-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 a Security Considerations section. ** 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 ---------------------------------------------------------------------------- == Outdated reference: A later version (-16) exists of draft-irtf-cfrg-hash-to-curve-05 == Outdated reference: A later version (-21) exists of draft-irtf-cfrg-voprf-02 -- 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: 2 errors (**), 0 flaws (~~), 4 warnings (==), 3 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: The Protocol 8 draft-davidson-pp-protocol-00 10 Abstract 12 This document specifies the Privacy Pass protocol for privacy- 13 preserving authorization of clients to servers. The privacy 14 requirement is that client re-authorization events cannot be linked 15 to any previous initial authorization. Privacy Pass is intended to 16 be used as a performant protocol in the Internet setting. 18 Status of This Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at https://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on 10 September 2020. 35 Copyright Notice 37 Copyright (c) 2020 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents (https://trustee.ietf.org/ 42 license-info) in effect on the date of publication of this document. 43 Please review these documents carefully, as they describe your rights 44 and restrictions with respect to this document. Code Components 45 extracted from this document must include Simplified BSD License text 46 as described in Section 4.e of the Trust Legal Provisions and are 47 provided without warranty as described in the Simplified BSD License. 49 Table of Contents 51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 52 1.1. Layout . . . . . . . . . . . . . . . . . . . . . . . . . 4 53 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 5 54 2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 55 2.2. Basic assumptions . . . . . . . . . . . . . . . . . . . . 5 56 3. Privacy Pass functional API . . . . . . . . . . . . . . . . . 6 57 3.1. Data structures . . . . . . . . . . . . . . . . . . . . . 6 58 3.1.1. Ciphersuite . . . . . . . . . . . . . . . . . . . . . 6 59 3.1.2. ServerConfig . . . . . . . . . . . . . . . . . . . . 6 60 3.1.3. ServerUpdate . . . . . . . . . . . . . . . . . . . . 7 61 3.1.4. ClientConfig . . . . . . . . . . . . . . . . . . . . 7 62 3.1.5. ClientIssuanceInput . . . . . . . . . . . . . . . . . 7 63 3.1.6. IssuanceMessage . . . . . . . . . . . . . . . . . . . 8 64 3.1.7. IssuanceResponse . . . . . . . . . . . . . . . . . . 8 65 3.1.8. RedemptionToken . . . . . . . . . . . . . . . . . . . 8 66 3.1.9. RedemptionMessage . . . . . . . . . . . . . . . . . . 9 67 3.1.10. RedemptionResponse . . . . . . . . . . . . . . . . . 9 68 3.2. API functions . . . . . . . . . . . . . . . . . . . . . . 9 69 3.2.1. PP_Server_Setup . . . . . . . . . . . . . . . . . . . 9 70 3.2.2. PP_Client_Setup . . . . . . . . . . . . . . . . . . . 10 71 3.2.3. PP_Generate . . . . . . . . . . . . . . . . . . . . . 10 72 3.2.4. PP_Issue . . . . . . . . . . . . . . . . . . . . . . 10 73 3.2.5. PP_Process . . . . . . . . . . . . . . . . . . . . . 11 74 3.2.6. PP_Redeem . . . . . . . . . . . . . . . . . . . . . . 11 75 3.2.7. PP_Verify . . . . . . . . . . . . . . . . . . . . . . 12 76 3.3. Error types . . . . . . . . . . . . . . . . . . . . . . . 12 77 4. Generalized protocol overview . . . . . . . . . . . . . . . . 12 78 4.1. Key initialisation phase . . . . . . . . . . . . . . . . 13 79 4.2. Issuance phase . . . . . . . . . . . . . . . . . . . . . 14 80 4.3. Redemption phase . . . . . . . . . . . . . . . . . . . . 14 81 4.3.1. Double-spend protection . . . . . . . . . . . . . . . 15 82 4.4. Handling errors . . . . . . . . . . . . . . . . . . . . . 16 83 5. Security requirements . . . . . . . . . . . . . . . . . . . . 16 84 5.1. Unlinkability . . . . . . . . . . . . . . . . . . . . . . 16 85 5.2. One-more unforgeability . . . . . . . . . . . . . . . . . 17 86 5.3. Double-spend protection . . . . . . . . . . . . . . . . . 18 87 6. VOPRF instantiation . . . . . . . . . . . . . . . . . . . . . 18 88 6.1. VOPRF conventions . . . . . . . . . . . . . . . . . . . . 18 89 6.1.1. Ciphersuites . . . . . . . . . . . . . . . . . . . . 18 90 6.1.2. Prime-order group conventions . . . . . . . . . . . . 19 91 6.2. API instantiation . . . . . . . . . . . . . . . . . . . . 19 92 6.2.1. PP_Server_Setup . . . . . . . . . . . . . . . . . . . 20 93 6.2.2. PP_Client_Setup . . . . . . . . . . . . . . . . . . . 20 94 6.2.3. PP_Generate . . . . . . . . . . . . . . . . . . . . . 20 95 6.2.4. PP_Issue . . . . . . . . . . . . . . . . . . . . . . 21 96 6.2.5. PP_Process . . . . . . . . . . . . . . . . . . . . . 21 97 6.2.6. PP_Redeem . . . . . . . . . . . . . . . . . . . . . . 22 98 6.2.7. PP_Verify . . . . . . . . . . . . . . . . . . . . . . 22 99 6.3. Security justification . . . . . . . . . . . . . . . . . 23 100 7. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 23 101 8. Extensions framework policy . . . . . . . . . . . . . . . . . 24 102 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 24 103 9.1. Normative References . . . . . . . . . . . . . . . . . . 24 104 9.2. Informative References . . . . . . . . . . . . . . . . . 25 105 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 26 107 1. Introduction 109 A common problem on the internet is providing an effective mechanism 110 for servers to derive trust from the clients that it interacts with, 111 without hampering the accessibility of honest clients. Typically, 112 this can be done by providing some sort of authorization challenge to 113 the client. A client providing a correct solution to the challenge 114 can be provided with a cookie. This cookie can be presented the next 115 time it interacts with the server. The resurfacing of this cookie 116 allows the server to see that the client passed the authorization 117 check in the past. Consequently, the server can re-authorize the 118 client again immediately, without the need for the client to complete 119 a new challenge. 121 In scenarios where clients need to identify themselves, the 122 authorization challenge usually take the form of some sort of login 123 procedure. Otherwise, the server may just want to verify that the 124 client demonstrates some particular facet of behavior (such as being 125 human). Such cases may only require a lightweight form of challenge 126 (such as completing a CAPTCHA). 128 In both cases, if a server issues cookies on successful completion of 129 challenges, then the client can use this cookie to bypass future 130 challenges for the lifetime of the cookie. The downside of this 131 approach is that it provides the server with the ability to link all 132 of the client's interactions that it witnesses. In these situations, 133 the client's effective privacy is dramatically reduced. 135 The Privacy Pass protocol was initially introduced as a mechanism for 136 authorizing clients that had already been authorized in the past, 137 without compromising their privacy [DGSTV18]. The protocol works by 138 providing client's with privacy-preserving re-authentication tokens 139 for a particular server. The tokens are "privacy-preserving" in the 140 sense that they cannot be linked back to the previous session where 141 they were issued. 143 The Internet performance company Cloudflare has already implemented 144 server-side support for an initial version of the Privacy Pass 145 protocol [PPSRV], and client-side implementations also exist [PPEXT]. 146 More recently, a number of applications have been built upon the 147 protocol, or slight variants of it; see: [TRUST], [OpenPrivacy], 148 [PrivateStorage]. The protocol can be instantiated using a 149 cryptographic primitive known as a verifiable oblivious pseudorandom 150 function (VOPRF) for implementing the authorization mechanism. Such 151 VOPRF protocols can be implemented already in prime-order groups, and 152 constructions are currently being drafted in separate standardization 153 processes [I-D.irtf-cfrg-voprf]. 155 The Privacy Pass protocol is split into three stages. The first 156 stage, initialisation, produces the global server configuration that 157 is broadcast to (and stored by) all clients. The "issuance" phase 158 provides the client with unlinkable tokens that can be used to 159 initiate re-authorization with the server in the future. The 160 redemption phase allows the client to redeem a given re-authorization 161 token with the server that it interacted with during the issuance 162 phase. In addition, the protocol must satisfy two cryptographic 163 security requirements known as "unlinkability" and "unforgeability". 165 This document will lay out the generic description of the protocol, 166 along with a secure implementation based on the VOPRF primitive. It 167 will also describe the structure of protocol messages, and the 168 framework for characterizing possible extensions to the protocol 169 description. 171 This document DOES NOT cover the architectural framework required for 172 running and maintaining the Privacy Pass protocol in the Internet 173 setting. In addition, it DOES NOT cover the choices that are 174 necessary for ensuring that client privacy leaks do not occur. Both 175 of these considerations are covered in a separate document 176 [draft-davidson-pp-architecture]. 178 1.1. Layout 180 * Section 2: Describes the terminology and assumptions adopted 181 throughout this document. 183 * Section 3: Describes the internal functions and data structures 184 that are used by the Privacy Pass protocol. 186 * Section 4: Describes the generic protocol structure, based on the 187 API provided in Section 3. 189 * Section 5: Describes the security requirements of the generic 190 protocol description. 192 * Section 6: Describes an instantiation of the API in Section 3 193 based on the VOPRF protocol described in [I-D.irtf-cfrg-voprf]. 195 * Section 7: Describes ciphersuites for use with the Privacy Pass 196 protocol based on the instantiation in Section 6. 198 * Section 8: Describes the policy for implementing extensions to the 199 Privacy Pass protocol. 201 2. Preliminaries 203 2.1. Terminology 205 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 206 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 207 document are to be interpreted as described in [RFC2119]. 209 The following terms are used throughout this document. 211 * Server: A service that provides the server-side functionality 212 required by the protocol documented here (typically denoted S). 214 * Client: An entity that seeks authorization from a server that 215 supports interactions in the Privacy Pass protocol (typically 216 denoted C). 218 * Key: The secret key used by the Server for authorizing client 219 data. 221 * Commitment: Alternative name for Server's public key corresponding 222 to the secret key that they hold. 224 We assume that all protocol messages are encoded into raw byte format 225 before being sent. We use the TLS presentation language [RFC8446] to 226 describe the structure of protocol data types and messages. 228 2.2. Basic assumptions 230 We make only a few minimal assumptions about the environment that the 231 clients and servers that support the Privacy Pass protocol. 233 * At any one time, we assume that the Server uses only one 234 configuration containing their ciphersuite choice along with their 235 secret key data. 237 * We assume that the client has access to a global directory of the 238 current configurations used by all Privacy Pass servers. 240 The wider ecosystem that this protocol is employed in is described in 241 [draft-davidson-pp-architecture]. 243 3. Privacy Pass functional API 245 Before describing the protocol itself in Section 4, we describe the 246 underlying functions that are used in substantiating the protocol 247 itself. Instantiating this set of functions, along with meeting the 248 security requirements highlighted in Section 5, provides an 249 instantiation of the wider protocol. 251 We provide an explicit instantiation of the Privacy Pass API, based 252 on the public API provided in [I-D.irtf-cfrg-voprf]. 254 3.1. Data structures 256 The following data structures are used throughout the Privacy Pass 257 protocol and written in the TLS presentation language [RFC8446]. It 258 is intended that any of these data structures can be written into 259 widely-adopted encoding schemes such as those detailed in TLS 260 [RFC8446], CBOR [RFC7049], and JSON [RFC7159]. 262 3.1.1. Ciphersuite 264 The "Ciphersuite" enum describes the ciphersuite that is used for 265 instantiating the Privacy Pass protocol. The values that we provide 266 here are described further in Section 7. 268 enum { 269 p384_hkdf_sha512_sswu_ro(0) 270 p521_hkdf_sha512_sswu_ro(1) 271 curve448_hkdf_sha512_ell2_ro(2) 272 (255) 273 } Ciphersuite; 275 3.1.2. ServerConfig 277 The "ServerConfig" struct describes and maintains the underlying 278 configuration that is used by the server. 280 struct { 281 opaque id<0..2^16-1> 282 Ciphersuite ciphersuite; 283 SecretKey key<1..2^32-1>; 284 PublicKey pub_key<1..2^32-1>; 285 opaque max_evals<0..255>; 286 } ServerConfig; 287 The "SecretKey" and "PublicKey" types are just wrappers around byte 288 arrays. 290 opaque SecretKey<1..2^32-1>; 291 opaque PublicKey<1..2^32-1>; 293 3.1.3. ServerUpdate 295 The "ServerUpdate" struct contains the public information related to 296 the creation of a new "ServerConfig" message. This is sent either 297 directly to clients, or indirectly via an update process. 299 struct { 300 opaque id<0..2^16-1> 301 Ciphersuite ciphersuite; 302 PublicKey pub_key<1..2^32-1>; 303 opaque max_evals<0..255>; 304 } ServerUpdate; 306 3.1.4. ClientConfig 308 The "ClientConfig" struct describes and maintains the underlying 309 configuration that is used by the client. 311 struct { 312 ServerUpdate s; 313 } ClientConfig; 315 3.1.5. ClientIssuanceInput 317 The "ClientIssuanceInput" struct describes the data that is generated 318 by the client, that is necessary in sending to and processing 319 issuance data received from the server. 321 struct { 322 ClientIssuanceProcessing client_data; 323 ClientIssuanceElement msg_data; 324 } ClientIssuanceInput; 326 The struct contains two internal structs, described below. 328 struct { 329 opaque client_data<1..2^32-1>; 330 opaque gen_data<1..2^32-1>; 331 } ClientIssuanceProcessing; 332 struct { 333 opaque issue_data<1..2^32-1>; 334 } ClientIssuanceElement; 336 3.1.6. IssuanceMessage 338 The "IssuanceMessage" struct corresponds to the message that the 339 client sends to the server during the issuance phase of the protocol 340 (Section 4.2). 342 struct { 343 ClientIssuanceElement issue_element<1..n> 344 } IssuanceMessage; 346 In the above, "issue_element" is a vector of length "n", where "n" is 347 some value that must satisfy "n =< m" for "m = max_evals" that is 348 specified in the "ServerConfig". 350 3.1.7. IssuanceResponse 352 The "IssuanceResponse" struct describes the data that returned by the 353 server, derived from the issuance message that is sent by the client. 355 struct { 356 ServerEvaluation evaluation<1..n>; 357 ServerProof proof; 358 } IssuanceResponse; 360 The value of "n" is determined by the length of the 361 "ClientIssuanceElement" vector in the "IssuanceMessage" struct. The 362 internal data types are described below. 364 struct { 365 opaque data<1..2^32-1>; 366 } ServerEvaluation; 368 struct { 369 opaque data<1..2*(2^32)-1>; 370 } ServerProof; 372 3.1.8. RedemptionToken 374 The "RedemptionToken" struct contains the data required to generate 375 the client message in the redemption phase of the Privacy Pass 376 protocol. This data is generated in the issuance phase of the 377 protocol, after receiving the "IssuanceResponse" message. 379 struct { 380 opaque data<1..2^32-1>; 381 opaque issued<1..2^32-1>; 382 } RedemptionToken; 384 3.1.9. RedemptionMessage 386 The "RedemptionMessage" struct consists of the data that is sent by 387 the client during the redemption phase of the protocol (Section 4.3). 389 struct { 390 opaque data<1..2^32-1>; 391 opaque tag<1..2^32-1>; 392 opaque aux<1..2^16-1>; 393 } RedemptionMessage; 395 3.1.10. RedemptionResponse 397 The "RedemptionResponse" struct corresponds a boolean value 398 indicating whether the "RedemptionMessage" sent by the client is 399 valid, along with any associated data. 401 struct { 402 boolean success; 403 opaque additional_data<1..2^32-1>; 404 } RedemptionResponse; 406 3.2. API functions 408 The following functions wrap the core of the functionality required 409 in the Privacy Pass protocol. For each of the descriptions, we 410 essentially provide the function signature, leaving the actual 411 contents to be provided by specific instantiations or extensions. 413 3.2.1. PP_Server_Setup 415 Run by the Privacy Pass server to generate its configuration. The 416 key-pair used in the server configuration are generated fresh on each 417 invocation. 419 Inputs: 421 * "id": A unique identifier corresponding to the setting of 422 "ServerConfig.id". 424 Outputs: 426 * "cfg": A "ServerConfig" struct (Section 3.1.2). 428 * "update": A "ServerUpdate" struct. 430 Throws: 432 * "ERR_UNSUPPORTED_CONFIG" (Section 3.3) 434 3.2.2. PP_Client_Setup 436 Run by the Privacy Pass client to generate its configuration. The 437 input public key "pub_key" in the client configuration MUST 438 correspond to a valid server public key. 440 Inputs: 442 * "id": A unique identifier corresponding to the setting of 443 "ServerConfig.id". 445 * "update": A "ServerUpdate" struct. 447 Outputs: 449 * "cfg": A "ClientConfig" struct (Section 3.1.4). 451 Throws: 453 * "ERR_UNSUPPORTED_CONFIG" (Section 3.3) 455 3.2.3. PP_Generate 457 A function run by the client to generate the initial data that is 458 used as its input in the Privacy Pass protocol. 460 Inputs: 462 * "cli_cfg": A "ClientConfig" struct. 464 * "m": A "uint8" value corresponding to the number of Privacy Pass 465 tokens to generate. 467 Outputs: 469 * "issuance_data": A "ClientIssuanceInput" struct. 471 3.2.4. PP_Issue 473 A function run by the server to issue valid redemption tokens to the 474 client. 476 Inputs: 478 * "srv_cfg": A "ServerConfig" struct. 480 * "issuance_message": A "IssuanceMessage" struct. 482 Outputs: 484 * "issuance_response": A "IssuanceResponse" struct. 486 Throws: 488 * "ERR_MAX_EVALS" (Section 3.3) 490 3.2.5. PP_Process 492 Run by the client when processing the server response in the issuance 493 phase of the protocol. The output of this function is an array of 494 "RedemptionToken" objects that are unlinkable from the server's 495 computation in "PP_Issue". 497 Inputs: 499 * "cli_cfg": A "ClientConfig" struct. 501 * "issuance_response": A "IssuanceResponse" struct. 503 * "processing_data": A "ClientIssuanceProcessing" struct. 505 Outputs: 507 * "tokens": A vector of "RedemptionToken" structs, length equal to 508 the length of the "ServerEvaluation" vector in the 509 "IssuanceResponse" struct. 511 Throws: 513 * "ERR_PROOF_VALIDATION" (Section 3.3) 515 3.2.6. PP_Redeem 517 Run by the client in the redemption phase of the protocol to generate 518 the client's message. 520 Inputs: 522 * "cli_cfg": A "ClientConfig" struct. 524 * "token": A "RedemptionToken" struct. 526 * "aux": An "opaque<1..2^32-1>" type corresponding to arbitrary 527 auxiliary data. 529 Outputs: 531 * "message": A "RedemptionMessage" struct. 533 3.2.7. PP_Verify 535 Run by the server in the redemption phase of the protocol. 536 Determines whether the data sent by the client is valid. 538 Inputs: 540 * "srv_cfg": A "ServerConfig" struct. 542 * "message": A "RedemptionMessage" struct. 544 Outputs: 546 * "response": A "RedemptionResponse" struct. 548 3.3. Error types 550 * "ERR_UNSUPPORTED_CONFIG": Error occurred when trying to recover 551 configuration with unknown identifier 553 * "ERR_MAX_EVALS": Client attempted to invoke server issuance with 554 number of inputs that is larger than server-specified max_evals 555 value. 557 * "ERR_PROOF_VALIDATION": Client unable to verify proof that is part 558 of the server response. 560 * "ERR_DOUBLE_SPEND": Indicates that a client has attempted to 561 redeem a token that has already been used for authorization. 563 4. Generalized protocol overview 565 In this document, we wan to provide a client (C) with the capability 566 to authenticate itself in a lightweight manner to a server (S). The 567 authorization mechanism should not reveal to the server anything 568 about the client; in addition, the client should not be able to forge 569 valid credentials in situations where it does not possess any. These 570 requirements are covered in Section 5. 572 In this section, we will give a broad overview of how the Privacy 573 Pass protocol functions in achieving these goals. The generic 574 protocol can be split into three phases: initialisation, issuance and 575 redemption. These three phases are built upon the Privacy Pass API 576 in Section 3. We show later (Section 6) that this API can be 577 implemented using an underlying VOPRF protocol. We provide this 578 extra layer of abstraction to allow building extensions into the 579 Privacy Pass protocol that go beyond what is specified in 580 [I-D.irtf-cfrg-voprf]. 582 4.1. Key initialisation phase 584 In the initialisation phase, the server generates the configuration 585 that it will use for future instantiations of the protocol. It MUST 586 broadcast the configuration that it generates, along with the public 587 key, so that clients are aware of which configuration to use when 588 interacting with the server. 590 In situations where the number of clients are small, it could do this 591 by sending the data to the client directly. But in situations where 592 there is a large number of clients, the best way of doing is likely 593 to be via posting this information to a public bulletin board. We 594 assume that the server only has a single configuration in place at 595 any one time. There are privacy restrictions related to this that 596 are described in more detail in the architectural document 597 [draft-davidson-pp-architecture]. 599 We give a diagrammatic representation of the initialisation phase 600 below. 602 C(cfgs) S(cfg_id) 603 ------------------------------------------------------------------- 604 (cfg, update) = PP_Server_Setup(cfg_id) 606 update 607 <------------------- 609 c_cfg = PP_Client_Setup(cfg_id,update) 610 cfgs.set(update.id,c_cfg) 612 In the following (and as above), we will assume that the server "S" 613 is uniquely identifiable by an internal attribute "id". We assume 614 the same internal attribute exists for the public key 615 "s_cfg.pub_key". This can be obtained, for example, by hashing the 616 contents of the object - either the name or underlying contained 617 bytes - using a collision-resistant hash function, such as SHA256. 619 Note that the client stores their own configuration in the map "cfgs" 620 for future Privacy Pass interactions with "S". 622 4.2. Issuance phase 624 The issuance phase allows the client to construct "RedemptionToken" 625 object resulting from an interaction with a server "S" that it has 626 previously interacted with. We give a diagrammatic overview of the 627 protocol below. 629 C(cfgs,store,m) S(s_cfg) 630 ------------------------------------------------------------------- 631 S.id 632 <------------------ 634 c_cfg = cfgs.get(S.id) 635 issue_input = PP_Generate(c_cfg, m) 636 msg = issue_input.msg_data 637 process = issue_input.client_data 639 msg 640 -------------------> 642 issue_resp = PP_Issue(s_cfg,c_dat) 644 issue_resp 645 <------------------- 647 tokens = PP_Process(c_cfg,issue_resp,process) 648 store[S.id].push(tokens) 650 In the diagram above, the client MUST know the supported server 651 configuration before it interacts with the Privacy Pass API. The 652 client input "store" is used for appending redemption tokens that are 653 linked to the server id "S.id". 655 4.3. Redemption phase 657 The redemption phase allows the client to reauthenticate to the 658 server, using data that it has received from a previous issuance 659 phase. We lay out the security requirements in Section 5 that 660 establish that the client redemption data is not linkable to any 661 given issuance session. 663 C(cfgs,store,aux) S(s_cfg,ds_idx) 664 ------------------------------------------------------------------- 665 S.id 666 <------------------ 668 c_cfg = cfgs.get(S.id) 669 token = store[S.id].pop() 670 msg = PP_Redeem(c_cfg,token,aux) 672 msg 673 ------------------> 675 if (ds_idx.includes(data)) { 676 panic(ERR_DOUBLE_SPEND) 677 } 678 resp = PP_Verify(srv_cfg,data,tag,aux) 679 if (resp.success) { 680 ds_idx.push(data) 681 } 683 resp 684 <------------------ 685 Output resp 687 The client input "aux" is arbitrary byte data that is used for 688 linking the redemption request to the specific session. We RECOMMEND 689 that "aux" is constructed as the following concatenated byte-encoded 690 data: 692 ${C.id} .. ${S.id} .. ${current_time()} .. ${requested_resource()} 694 The usage of "current_time()" allows the server to check that the 695 redemption request has happened in an appropriate time window. The 696 function "requested_resource()" is an optional suffix that relates to 697 any specific resources that the client has requested from the server, 698 in order to trigger the authorization request. 700 4.3.1. Double-spend protection 702 To protect against clients that attempt to spend a value "data" more 703 than once, the server uses an index, "ds_idx", to collect valid 704 inputs and then check against in future protocols. Since this store 705 needs to only be optimized for storage and querying, a structure such 706 as a Bloom filter suffices. Importantly, the server MUST only eject 707 this storage after a key rotation occurs since all previous client 708 data will be rendered obsolete after such an event. 710 4.4. Handling errors 712 It is possible for the API functions from Section 3.2 to return one 713 of the errors indicated in Section 3.3 rather than their expected 714 value. In these cases, we assume that the entire protocol execution 715 panics with the value of the error. 717 If a panic occurs during the server's operations for one of the 718 documented errors, then the server returns an error response 719 indicating the error that occurred. 721 5. Security requirements 723 We discuss the security requirements that are necessary to uphold 724 when instantiating the Privacy Pass protocol. In particular, we 725 focus on the security requirements of "unlinkability", and 726 "unforgeability". Informally, the notion of unlinkability is 727 required to preserve the privacy of the client in the redemption 728 phase of the protocol. The notion of unforgeability is to protect 729 against adversarial clients that look to subvert the security of the 730 protocol. 732 Since these are cryptographic security requirements we discuss them 733 with respect to a polynomial-time algorithm known as the adversary 734 that is looking to subvert the security guarantee. More details on 735 both security requirements can be found in [DGSTV18] and [KLOR20]. 737 Note that the privacy requirements of the protocol are covered in the 738 architectural framework document [draft-davidson-pp-architecture]. 740 5.1. Unlinkability 742 Informally, the "unlinkability" requirement states that it is 743 impossible for an adversarial server to link the client's message in 744 a redemption session, to any previous issuance session that it has 745 encountered. 747 Formally speaking the security model is the following: 749 * The adversary runs "PP_Server_Setup" and generates a key-pair "(k, 750 pk)". 752 * The adversary specifies a number "Q" of issuance phases to 753 initiate, where each phase "i in 1..Q" consists of "m_i" server 754 evaluations. 756 * The adversary runs "PP_Issue" using the key-pair that it generated 757 on each of the client messages in the issuance phase. 759 * When the adversary wants it stops the issuance phase, and a random 760 number "l" is picked from "1..Q". 762 * A redemption phase is initiated with a single token with index "i" 763 randomly sampled from "1..m_l". 765 * The adversary guesses an index "l_guess" corresponding to the 766 index of the issuance phase that it believes the redemption token 767 was received in. 769 * The adversary succeeds if "l == l_guess". 771 The security requirement is that the adversary has only a negligible 772 probability of success greater than "1/Q". 774 5.2. One-more unforgeability 776 The one-more unforgeability requirement states that it is hard for 777 any adversarial client that has received "m" valid tokens from a 778 server to redeem "m+1" of them. In essence, this requirement 779 prevents a malicious client from being able to forge valid tokens 780 based on the server responses that it sees. 782 The security model takes the following form: 784 * A server is created that runs "PP_Server_Setup" and broadcasts the 785 "ServerUpdate" message "update". 787 * The adversary runs "PP_Client_Setup" on "update". 789 * The adversary specifies a number "Q" of issuance phases to 790 initiate with the server, where each phase "i in 1..Q" consists of 791 "m_i" server evaluations. Let "m = sum(m_i)" where "i in 1..Q". 793 * The client receives Q responses, where the response with index "i" 794 contains "m_i" individual tokens. 796 * The adversary initiates "m_adv" redemption sessions with the 797 server and the server verifies that the sessions are successful 798 (return true), and that each request includes a unique token. The 799 adversary succeeds in "m_succ =< m_adv" redemption sessions. 801 * The adversary succeeds if "m_succ > m". 803 The security requirement is that the adversarial client has only a 804 negligible probability of succeeding. 806 Note that [KLOR20] strengthens the capabilities of the adversary, in 807 comparison to the original work of [DGSTV18]. In [KLOR20], the 808 adversary is provided with oracle access that allows it to verify 809 that the server responses in the issuance phase are valid. 811 5.3. Double-spend protection 813 All issuing servers should implement a robust, global storage-query 814 mechanism for checking that tokens sent by clients have not been 815 spent before. Such tokens only need to be checked for each issuer 816 individually. This prevents clients from "replaying" previous 817 requests, and is necessary for achieving the unforgeability 818 requirement. 820 6. VOPRF instantiation 822 In this section, we show how to instantiate the functional API in 823 Section 3 with the VOPRF protocol described in [I-D.irtf-cfrg-voprf]. 824 Moreover, we show that this protocol satisfies the security 825 requirements laid out in Section 5, based on the security proofs 826 provided in [DGSTV18] and [KLOR20]. 828 6.1. VOPRF conventions 830 The VOPRF ciphersuite [I-D.irtf-cfrg-voprf] that is used determines 831 the member functions and prime-order group used by the protocol. We 832 detail a number of specific conventions here that we use for 833 interacting with the specific ciphersuite. 835 6.1.1. Ciphersuites 837 Let "F" denote a generic VOPRF API function as detailed in 838 [I-D.irtf-cfrg-voprf] (Section TODO), and let "ciph" denote the 839 ciphersuite that is used for instantiating the VOPRF. In this 840 document, we explicitly write "ciph.F" to show that "F" is explicitly 841 evaluated with respect to "ciph". 843 In addition, we define the following member functions associated with 844 the ciphersuite. 846 * "recover_ciphersuite_from_id(id)": Takes a string identifier "id" 847 as input, and outputs a VOPRF ciphersuite. Returns "null" if "id" 848 is not recognized. 850 * "group()": Returns the prime-order group associated with the 851 ciphersuite. 853 * "H1()": The function "H1()" defined in [I-D.irtf-cfrg-voprf] 854 (Section TODO). This function allows deterministically mapping 855 arbitrary bytes to a random element of the group. In the elliptic 856 curve setting, this is achieved using the functions defined in 857 [I-D.irtf-cfrg-hash-to-curve]. 859 6.1.2. Prime-order group conventions 861 We detail a few functions that are required of the prime-order group 862 "GG" used by the VOPRF in [I-D.irtf-cfrg-voprf]. 864 Let "p" be the order of the Galois field "GF(p)" associated with the 865 group "GG". We expose the following functions associated with "GG". 867 * "GG.generator()": Returns the fixed generator associated with the 868 group "GG". 870 * "GG.scalar_field()": Provides access to the field "GF(p)". 872 * "GG.scalar_field().random()": Samples a scalar uniformly at random 873 from GF(p). This can be done by sampling a random sequence of 874 bytes that produce a scalar "r", where "r < p" is satisfied (via 875 rejection-sampling). 877 We also use the following functions for transitioning between 878 different data types. 880 * "as_bytes()": For a scalar element of "GG.scalar_field()", or an 881 element of "GG"; the "as_bytes()" functions serializes the element 882 into bytes and returns this array as output. 884 * "as_scalar()": Interprets a sequence of bytes as a scalar value in 885 "GG.scalar_field()". For an array of byte arrays, we define the 886 function "as_scalars()" to individually deserialize each of the 887 individual byte arrays into a scalar and output a new array 888 containing each scalar value. 890 * "as_element()": Interprets a sequence of bytes as a group element 891 in "GG". For an array of byte arrays, we define the function 892 "as_elements()" to individually deserialize each of the individual 893 byte arrays into a single group element and output a new array 894 containing each of these elements. 896 6.2. API instantiation 898 For the explicit signatures of each of the functions, refer to 899 Section 3.2. 901 6.2.1. PP_Server_Setup 903 1. ciph = recover_ciphersuite_from_id(id) 904 2. if ciph == null: panic(ERR_UNSUPPORTED_CONFIG) 905 3. (k,Y,GG) = ciph.VerifiableSetup() 906 4. key = k.as_bytes() 907 5. pub_key = Y.as_bytes() 908 6. cfg = ServerConfig { 909 id: id 910 ciphersuite: ciph, 911 key: key, 912 pub_key: pub_key, 913 max_evals: max_evals 914 } 915 7. update = ServerUpdate { 916 id: id 917 ciphersuite: ciph, 918 pub_key: pub_key, 919 max_evals: max_evals 920 } 921 8. Output (cfg, update) 923 6.2.2. PP_Client_Setup 925 1. ciph = recover_ciphersuite_from_id(id) 926 2. if ciph == null: panic(ERR_UNSUPPORTED_CONFIG) 927 3. cfg = ClientConfig { 928 s: update 929 } 930 4. Output cfg 932 6.2.3. PP_Generate 933 1. ciph = cli_cfg.s.ciphersuite 934 2. GG = ciph.group() 935 3. c_data = [] 936 4. i_data = [] 937 5. g_data = [] 938 6. for i in 0..m: 939 1. c_data[i] = GG.scalar_field().random().as_bytes() 940 7. (blinds,group_elems) = ciph.VerifiableBlind(c_data) 941 8. for i in 0..m: 942 1. i_data[i] = group_elems[i].as_bytes() 943 2. g_data[i] = blinds[i].as_bytes() 944 9. Output ClientIssuanceInput { 945 ClientIssuanceProcessing { 946 client_data: c_data, 947 gen_data: g_data, 948 }, 949 ClientIssuanceElement { 950 msg_data: i_data, 951 } 952 } 954 6.2.4. PP_Issue 956 1. ciph = srv_cfg.ciphersuite 957 2. pk = srv_cfg.pub_key.as_element() 958 3. GG = ciph.group() 959 4. m = msg_data.length 960 5. if m > max_evals: panic(ERR_MAX_EVALS) 961 6. G = GG.generator() 962 7. elts = msg_data.as_elements(); 963 8. Z,D = ciph.VerifiableEval(key.as_scalar(),G,pk,elts) 964 9. evals = [] 965 10. for i in 0..m: 966 1. eval[i] = ServerEvaluation { 967 data: Z[i].as_bytes(); 968 } 969 11. proof = ServerProof { 970 data: D.as_bytes() 971 } 972 12. Output IssuanceResponse { 973 evaluations: eval, 974 proof: proof, 975 } 977 6.2.5. PP_Process 978 1. ciph = cli_cfg.s.ciphersuite 979 2. GG = ciph.group() 980 3. G = GG.generator() 981 4. pk = cli_cfg.s.pub_key.as_element() 982 5. M = i_data.as_elements() 983 6. Z = evals.as_elements() 984 7. r = g_data.as_scalars() 985 8. N = ciph.VerifiableUnblind(G,pk,M,Z,r,proof) 986 9. if N == "error": panic(ERR_PROOF_VALIDATION) 987 10. tokens = [] 988 11. for i in 0..m: 989 1. issued = N[i].as_bytes() 990 2. rt = RedemptionToken { data: c_data[i], issued: issued } 991 3. tokens[i] = rt 992 12. Output tokens 994 6.2.6. PP_Redeem 996 1. ciph = cli_cfg.s.ciphersuite 997 2. GG = ciph.group() 998 3. token = store[S.id].pop(); 999 4. data = token.data 1000 5. issued = token.issued.as_element(); 1001 6. tag = ciph.VerifiableFinalize(data,issued,aux) 1002 7. Output RedemptionMessage { 1003 data: data, 1004 tag: tag, 1005 aux: aux, 1006 } 1008 6.2.7. PP_Verify 1010 1. ciph = srv_cfg.ciphersuite 1011 2. GG = ciph.group() 1012 3. key = srv_cfg.key 1013 4. T = ciph.H1(msg.data) 1014 5. N' = ciph.Eval(key,T) 1015 6. tag' = ciph.Finalize(msg.data,N',msg.aux) 1016 7. Output RedemptionResponse { 1017 success: (msg.tag == tag') 1018 } 1020 Note: at this stage we use the non-verifiable VOPRF API functions 1021 rather than the verifiable equivalents ("Eval" rather than 1022 "VerifiableEval"), as we do not need to recompute the proof data that 1023 is used for producing verifiable outputs at this stage. 1025 6.3. Security justification 1027 The protocol that we devise in Section 4, coupled with the API 1028 instantiation in Section 6.2, are equivalent to the protocol 1029 description in [DGSTV18]. In [DGSTV18], it is proven that this 1030 protocol satisfies the security requirements of unlinkability 1031 (Section 5.1) and unforgeability (Section 5.2). 1033 The unlinkability property follows unconditionally as the view of the 1034 adversary in the redemption phase is distributed independently of the 1035 issuance phase. The unforgeability property follows from the one- 1036 more decryption security of the ElGamal cryptosystem [DGSTV18]. In 1037 [KLOR20] it is also proven that this protocol satisfies the stronger 1038 notion of unforgeability, where the adversary is granted a 1039 verification oracle, under the chosen-target Diffie-Hellman 1040 assumption. 1042 Note that the existing security proofs do not leverage the VOPRF 1043 primitive as a black-box in the security reductions. Instead it 1044 relies on the underlying operations in a non-black-box manner. 1045 Hence, an explicit reduction from the generic VOPRF primitive to the 1046 Privacy Pass protocol would strengthen these security guarantees. 1048 7. Ciphersuites 1050 The Privacy Pass protocol essentially operates as a wrapper around 1051 the instantiation of the VOPRF that is used in Section 6. There is 1052 no extra cryptographic machinery used on top of what is established 1053 in the VOPRF protocol. Therefore, the ciphersuites that we support 1054 are the transitively exposed from the underlying VOPRF functionality, 1055 we detail these below. Each of the ciphersuites is detailed in 1056 [I-D.irtf-cfrg-voprf]. 1058 * VOPRF-P384-HKDF-SHA512-SSWU-RO 1060 - maximum security parameter: 192 bits 1062 * VOPRF-curve448-HKDF-SHA512-ELL2-RO 1064 - maximum security parameter: 224 bits 1066 * VOPRF-P521-HKDF-SHA512-SSWU-RO 1068 - maximum security parameter: 256 bits 1070 When referring to the 'maximum security parameter' size above, we are 1071 referring to the _maximum_ effective key length of the ciphersuite, 1072 as specified in [NIST]. The reason that this is the maximum length 1073 is because there may be attacks that serve to lower the actual value 1074 of the security parameter. See [I-D.irtf-cfrg-voprf] for more 1075 details. 1077 Note than any extension to the Privacy Pass protocol that modifies 1078 either VOPRF instantiation, or the way that the Privacy Pass API is 1079 implemented, MUST specify its own ciphersuites. 1081 8. Extensions framework policy 1083 The intention with providing the Privacy Pass API in Section 3 is to 1084 allow new instantiations of the Privacy Pass protocol. These 1085 instantiations may provide either modified VOPRF constructions, or 1086 simply implement the API in a completely different way. 1088 Extensions to this initial draft SHOULD be specified as separate 1089 documents taking one of two possible routes: 1091 * Produce new VOPRF-like primitives that use the same public API 1092 provided in [I-D.irtf-cfrg-voprf] to implement the Privacy Pass 1093 API, but with different internal operations. 1095 * Implement the Privacy Pass API in a different way to the proposed 1096 implementation in Section 6. 1098 If an extension requires changing the generic protocol description as 1099 described in Section 4, then the change may have to result in changes 1100 to the draft specification here also. 1102 Each new extension that modifies the internals of the protocol in 1103 either of the two ways MUST re-justify that the extended protocol 1104 still satisfies the security requirements in Section 5. Protocol 1105 extensions MAY put forward new security guarantees if they are 1106 applicable. 1108 The extensions MUST also conform with the extension framework policy 1109 as set out in the architectural framework document. For example, 1110 this may concern any potential impact on client privacy that the 1111 extension may introduce. 1113 9. References 1115 9.1. Normative References 1117 [draft-davidson-pp-architecture] 1118 Davidson, A., "Privacy Pass: Architectural Framework", 1119 n.d., . 1122 [I-D.irtf-cfrg-hash-to-curve] 1123 Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and 1124 C. Wood, "Hashing to Elliptic Curves", Work in Progress, 1125 Internet-Draft, draft-irtf-cfrg-hash-to-curve-05, 2 1126 November 2019, . 1129 [I-D.irtf-cfrg-voprf] 1130 Davidson, A., Sullivan, N., and C. Wood, "Oblivious 1131 Pseudorandom Functions (OPRFs) using Prime-Order Groups", 1132 Work in Progress, Internet-Draft, draft-irtf-cfrg-voprf- 1133 02, 4 November 2019, . 1136 [NIST] "Keylength - NIST Report on Cryptographic Key Length and 1137 Cryptoperiod (2016)", n.d., 1138 . 1140 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1141 Requirement Levels", BCP 14, RFC 2119, 1142 DOI 10.17487/RFC2119, March 1997, 1143 . 1145 [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol 1146 Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, 1147 . 1149 9.2. Informative References 1151 [DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously", 1152 n.d., . 1155 [KLOR20] "Anonymous Tokens with Private Metadata Bit", n.d., 1156 . 1158 [OpenPrivacy] 1159 "Token Based Services - Differences from PrivacyPass", 1160 n.d., . 1163 [PPEXT] "Privacy Pass Browser Extension", n.d., 1164 . 1167 [PPSRV] Sullivan, N., "Cloudflare Supports Privacy Pass", n.d., 1168 . 1171 [PrivateStorage] 1172 Steininger, L., "The Path from S4 to PrivateStorage", 1173 n.d., . 1176 [RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object 1177 Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049, 1178 October 2013, . 1180 [RFC7159] Bray, T., Ed., "The JavaScript Object Notation (JSON) Data 1181 Interchange Format", RFC 7159, DOI 10.17487/RFC7159, March 1182 2014, . 1184 [TRUST] WICG, ., "Trust Token API", n.d., 1185 . 1187 Author's Address 1189 Alex Davidson 1190 Cloudflare Portugal 1191 Largo Rafael Bordalo Pinheiro 29 1192 Lisbon 1193 Portugal 1195 Email: alex.davidson92@gmail.com