Network Working Group A. Davidson Internet-Draft Cloudflare Portugal Intended status: Informational 9 March 2020 Expires: 10 September 2020 Privacy Pass: The Protocol draft-davidson-pp-protocol-00 Abstract This document specifies the Privacy Pass protocol for privacy- preserving authorization of clients to servers. The privacy requirement is that client re-authorization events cannot be linked to any previous initial authorization. Privacy Pass is intended to be used as a performant protocol in the Internet setting. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on 10 September 2020. Copyright Notice Copyright (c) 2020 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/ license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Davidson Expires 10 September 2020 [Page 1] Internet-Draft PP protocol March 2020 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Layout . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. Basic assumptions . . . . . . . . . . . . . . . . . . . . 5 3. Privacy Pass functional API . . . . . . . . . . . . . . . . . 6 3.1. Data structures . . . . . . . . . . . . . . . . . . . . . 6 3.1.1. Ciphersuite . . . . . . . . . . . . . . . . . . . . . 6 3.1.2. ServerConfig . . . . . . . . . . . . . . . . . . . . 6 3.1.3. ServerUpdate . . . . . . . . . . . . . . . . . . . . 7 3.1.4. ClientConfig . . . . . . . . . . . . . . . . . . . . 7 3.1.5. ClientIssuanceInput . . . . . . . . . . . . . . . . . 7 3.1.6. IssuanceMessage . . . . . . . . . . . . . . . . . . . 8 3.1.7. IssuanceResponse . . . . . . . . . . . . . . . . . . 8 3.1.8. RedemptionToken . . . . . . . . . . . . . . . . . . . 8 3.1.9. RedemptionMessage . . . . . . . . . . . . . . . . . . 9 3.1.10. RedemptionResponse . . . . . . . . . . . . . . . . . 9 3.2. API functions . . . . . . . . . . . . . . . . . . . . . . 9 3.2.1. PP_Server_Setup . . . . . . . . . . . . . . . . . . . 9 3.2.2. PP_Client_Setup . . . . . . . . . . . . . . . . . . . 10 3.2.3. PP_Generate . . . . . . . . . . . . . . . . . . . . . 10 3.2.4. PP_Issue . . . . . . . . . . . . . . . . . . . . . . 10 3.2.5. PP_Process . . . . . . . . . . . . . . . . . . . . . 11 3.2.6. PP_Redeem . . . . . . . . . . . . . . . . . . . . . . 11 3.2.7. PP_Verify . . . . . . . . . . . . . . . . . . . . . . 12 3.3. Error types . . . . . . . . . . . . . . . . . . . . . . . 12 4. Generalized protocol overview . . . . . . . . . . . . . . . . 12 4.1. Key initialisation phase . . . . . . . . . . . . . . . . 13 4.2. Issuance phase . . . . . . . . . . . . . . . . . . . . . 14 4.3. Redemption phase . . . . . . . . . . . . . . . . . . . . 14 4.3.1. Double-spend protection . . . . . . . . . . . . . . . 15 4.4. Handling errors . . . . . . . . . . . . . . . . . . . . . 16 5. Security requirements . . . . . . . . . . . . . . . . . . . . 16 5.1. Unlinkability . . . . . . . . . . . . . . . . . . . . . . 16 5.2. One-more unforgeability . . . . . . . . . . . . . . . . . 17 5.3. Double-spend protection . . . . . . . . . . . . . . . . . 18 6. VOPRF instantiation . . . . . . . . . . . . . . . . . . . . . 18 6.1. VOPRF conventions . . . . . . . . . . . . . . . . . . . . 18 6.1.1. Ciphersuites . . . . . . . . . . . . . . . . . . . . 18 6.1.2. Prime-order group conventions . . . . . . . . . . . . 19 6.2. API instantiation . . . . . . . . . . . . . . . . . . . . 19 6.2.1. PP_Server_Setup . . . . . . . . . . . . . . . . . . . 20 6.2.2. PP_Client_Setup . . . . . . . . . . . . . . . . . . . 20 6.2.3. PP_Generate . . . . . . . . . . . . . . . . . . . . . 20 6.2.4. PP_Issue . . . . . . . . . . . . . . . . . . . . . . 21 6.2.5. PP_Process . . . . . . . . . . . . . . . . . . . . . 21 Davidson Expires 10 September 2020 [Page 2] Internet-Draft PP protocol March 2020 6.2.6. PP_Redeem . . . . . . . . . . . . . . . . . . . . . . 22 6.2.7. PP_Verify . . . . . . . . . . . . . . . . . . . . . . 22 6.3. Security justification . . . . . . . . . . . . . . . . . 23 7. Ciphersuites . . . . . . . . . . . . . . . . . . . . . . . . 23 8. Extensions framework policy . . . . . . . . . . . . . . . . . 24 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 24 9.1. Normative References . . . . . . . . . . . . . . . . . . 24 9.2. Informative References . . . . . . . . . . . . . . . . . 25 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 26 1. Introduction A common problem on the internet is providing an effective mechanism for servers to derive trust from the clients that it interacts with, without hampering the accessibility of honest clients. Typically, this can be done by providing some sort of authorization challenge to the client. A client providing a correct solution to the challenge can be provided with a cookie. This cookie can be presented the next time it interacts with the server. The resurfacing of this cookie allows the server to see that the client passed the authorization check in the past. Consequently, the server can re-authorize the client again immediately, without the need for the client to complete a new challenge. In scenarios where clients need to identify themselves, the authorization challenge usually take the form of some sort of login procedure. Otherwise, the server may just want to verify that the client demonstrates some particular facet of behavior (such as being human). Such cases may only require a lightweight form of challenge (such as completing a CAPTCHA). In both cases, if a server issues cookies on successful completion of challenges, then the client can use this cookie to bypass future challenges for the lifetime of the cookie. The downside of this approach is that it provides the server with the ability to link all of the client's interactions that it witnesses. In these situations, the client's effective privacy is dramatically reduced. The Privacy Pass protocol was initially introduced as a mechanism for authorizing clients that had already been authorized in the past, without compromising their privacy [DGSTV18]. The protocol works by providing client's with privacy-preserving re-authentication tokens for a particular server. The tokens are "privacy-preserving" in the sense that they cannot be linked back to the previous session where they were issued. The Internet performance company Cloudflare has already implemented server-side support for an initial version of the Privacy Pass Davidson Expires 10 September 2020 [Page 3] Internet-Draft PP protocol March 2020 protocol [PPSRV], and client-side implementations also exist [PPEXT]. More recently, a number of applications have been built upon the protocol, or slight variants of it; see: [TRUST], [OpenPrivacy], [PrivateStorage]. The protocol can be instantiated using a cryptographic primitive known as a verifiable oblivious pseudorandom function (VOPRF) for implementing the authorization mechanism. Such VOPRF protocols can be implemented already in prime-order groups, and constructions are currently being drafted in separate standardization processes [I-D.irtf-cfrg-voprf]. The Privacy Pass protocol is split into three stages. The first stage, initialisation, produces the global server configuration that is broadcast to (and stored by) all clients. The "issuance" phase provides the client with unlinkable tokens that can be used to initiate re-authorization with the server in the future. The redemption phase allows the client to redeem a given re-authorization token with the server that it interacted with during the issuance phase. In addition, the protocol must satisfy two cryptographic security requirements known as "unlinkability" and "unforgeability". This document will lay out the generic description of the protocol, along with a secure implementation based on the VOPRF primitive. It will also describe the structure of protocol messages, and the framework for characterizing possible extensions to the protocol description. This document DOES NOT cover the architectural framework required for running and maintaining the Privacy Pass protocol in the Internet setting. In addition, it DOES NOT cover the choices that are necessary for ensuring that client privacy leaks do not occur. Both of these considerations are covered in a separate document [draft-davidson-pp-architecture]. 1.1. Layout * Section 2: Describes the terminology and assumptions adopted throughout this document. * Section 3: Describes the internal functions and data structures that are used by the Privacy Pass protocol. * Section 4: Describes the generic protocol structure, based on the API provided in Section 3. * Section 5: Describes the security requirements of the generic protocol description. Davidson Expires 10 September 2020 [Page 4] Internet-Draft PP protocol March 2020 * Section 6: Describes an instantiation of the API in Section 3 based on the VOPRF protocol described in [I-D.irtf-cfrg-voprf]. * Section 7: Describes ciphersuites for use with the Privacy Pass protocol based on the instantiation in Section 6. * Section 8: Describes the policy for implementing extensions to the Privacy Pass protocol. 2. Preliminaries 2.1. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. The following terms are used throughout this document. * Server: A service that provides the server-side functionality required by the protocol documented here (typically denoted S). * Client: An entity that seeks authorization from a server that supports interactions in the Privacy Pass protocol (typically denoted C). * Key: The secret key used by the Server for authorizing client data. * Commitment: Alternative name for Server's public key corresponding to the secret key that they hold. We assume that all protocol messages are encoded into raw byte format before being sent. We use the TLS presentation language [RFC8446] to describe the structure of protocol data types and messages. 2.2. Basic assumptions We make only a few minimal assumptions about the environment that the clients and servers that support the Privacy Pass protocol. * At any one time, we assume that the Server uses only one configuration containing their ciphersuite choice along with their secret key data. * We assume that the client has access to a global directory of the current configurations used by all Privacy Pass servers. Davidson Expires 10 September 2020 [Page 5] Internet-Draft PP protocol March 2020 The wider ecosystem that this protocol is employed in is described in [draft-davidson-pp-architecture]. 3. Privacy Pass functional API Before describing the protocol itself in Section 4, we describe the underlying functions that are used in substantiating the protocol itself. Instantiating this set of functions, along with meeting the security requirements highlighted in Section 5, provides an instantiation of the wider protocol. We provide an explicit instantiation of the Privacy Pass API, based on the public API provided in [I-D.irtf-cfrg-voprf]. 3.1. Data structures The following data structures are used throughout the Privacy Pass protocol and written in the TLS presentation language [RFC8446]. It is intended that any of these data structures can be written into widely-adopted encoding schemes such as those detailed in TLS [RFC8446], CBOR [RFC7049], and JSON [RFC7159]. 3.1.1. Ciphersuite The "Ciphersuite" enum describes the ciphersuite that is used for instantiating the Privacy Pass protocol. The values that we provide here are described further in Section 7. enum { p384_hkdf_sha512_sswu_ro(0) p521_hkdf_sha512_sswu_ro(1) curve448_hkdf_sha512_ell2_ro(2) (255) } Ciphersuite; 3.1.2. ServerConfig The "ServerConfig" struct describes and maintains the underlying configuration that is used by the server. struct { opaque id<0..2^16-1> Ciphersuite ciphersuite; SecretKey key<1..2^32-1>; PublicKey pub_key<1..2^32-1>; opaque max_evals<0..255>; } ServerConfig; Davidson Expires 10 September 2020 [Page 6] Internet-Draft PP protocol March 2020 The "SecretKey" and "PublicKey" types are just wrappers around byte arrays. opaque SecretKey<1..2^32-1>; opaque PublicKey<1..2^32-1>; 3.1.3. ServerUpdate The "ServerUpdate" struct contains the public information related to the creation of a new "ServerConfig" message. This is sent either directly to clients, or indirectly via an update process. struct { opaque id<0..2^16-1> Ciphersuite ciphersuite; PublicKey pub_key<1..2^32-1>; opaque max_evals<0..255>; } ServerUpdate; 3.1.4. ClientConfig The "ClientConfig" struct describes and maintains the underlying configuration that is used by the client. struct { ServerUpdate s; } ClientConfig; 3.1.5. ClientIssuanceInput The "ClientIssuanceInput" struct describes the data that is generated by the client, that is necessary in sending to and processing issuance data received from the server. struct { ClientIssuanceProcessing client_data; ClientIssuanceElement msg_data; } ClientIssuanceInput; The struct contains two internal structs, described below. struct { opaque client_data<1..2^32-1>; opaque gen_data<1..2^32-1>; } ClientIssuanceProcessing; Davidson Expires 10 September 2020 [Page 7] Internet-Draft PP protocol March 2020 struct { opaque issue_data<1..2^32-1>; } ClientIssuanceElement; 3.1.6. IssuanceMessage The "IssuanceMessage" struct corresponds to the message that the client sends to the server during the issuance phase of the protocol (Section 4.2). struct { ClientIssuanceElement issue_element<1..n> } IssuanceMessage; In the above, "issue_element" is a vector of length "n", where "n" is some value that must satisfy "n =< m" for "m = max_evals" that is specified in the "ServerConfig". 3.1.7. IssuanceResponse The "IssuanceResponse" struct describes the data that returned by the server, derived from the issuance message that is sent by the client. struct { ServerEvaluation evaluation<1..n>; ServerProof proof; } IssuanceResponse; The value of "n" is determined by the length of the "ClientIssuanceElement" vector in the "IssuanceMessage" struct. The internal data types are described below. struct { opaque data<1..2^32-1>; } ServerEvaluation; struct { opaque data<1..2*(2^32)-1>; } ServerProof; 3.1.8. RedemptionToken The "RedemptionToken" struct contains the data required to generate the client message in the redemption phase of the Privacy Pass protocol. This data is generated in the issuance phase of the protocol, after receiving the "IssuanceResponse" message. Davidson Expires 10 September 2020 [Page 8] Internet-Draft PP protocol March 2020 struct { opaque data<1..2^32-1>; opaque issued<1..2^32-1>; } RedemptionToken; 3.1.9. RedemptionMessage The "RedemptionMessage" struct consists of the data that is sent by the client during the redemption phase of the protocol (Section 4.3). struct { opaque data<1..2^32-1>; opaque tag<1..2^32-1>; opaque aux<1..2^16-1>; } RedemptionMessage; 3.1.10. RedemptionResponse The "RedemptionResponse" struct corresponds a boolean value indicating whether the "RedemptionMessage" sent by the client is valid, along with any associated data. struct { boolean success; opaque additional_data<1..2^32-1>; } RedemptionResponse; 3.2. API functions The following functions wrap the core of the functionality required in the Privacy Pass protocol. For each of the descriptions, we essentially provide the function signature, leaving the actual contents to be provided by specific instantiations or extensions. 3.2.1. PP_Server_Setup Run by the Privacy Pass server to generate its configuration. The key-pair used in the server configuration are generated fresh on each invocation. Inputs: * "id": A unique identifier corresponding to the setting of "ServerConfig.id". Outputs: * "cfg": A "ServerConfig" struct (Section 3.1.2). Davidson Expires 10 September 2020 [Page 9] Internet-Draft PP protocol March 2020 * "update": A "ServerUpdate" struct. Throws: * "ERR_UNSUPPORTED_CONFIG" (Section 3.3) 3.2.2. PP_Client_Setup Run by the Privacy Pass client to generate its configuration. The input public key "pub_key" in the client configuration MUST correspond to a valid server public key. Inputs: * "id": A unique identifier corresponding to the setting of "ServerConfig.id". * "update": A "ServerUpdate" struct. Outputs: * "cfg": A "ClientConfig" struct (Section 3.1.4). Throws: * "ERR_UNSUPPORTED_CONFIG" (Section 3.3) 3.2.3. PP_Generate A function run by the client to generate the initial data that is used as its input in the Privacy Pass protocol. Inputs: * "cli_cfg": A "ClientConfig" struct. * "m": A "uint8" value corresponding to the number of Privacy Pass tokens to generate. Outputs: * "issuance_data": A "ClientIssuanceInput" struct. 3.2.4. PP_Issue A function run by the server to issue valid redemption tokens to the client. Davidson Expires 10 September 2020 [Page 10] Internet-Draft PP protocol March 2020 Inputs: * "srv_cfg": A "ServerConfig" struct. * "issuance_message": A "IssuanceMessage" struct. Outputs: * "issuance_response": A "IssuanceResponse" struct. Throws: * "ERR_MAX_EVALS" (Section 3.3) 3.2.5. PP_Process Run by the client when processing the server response in the issuance phase of the protocol. The output of this function is an array of "RedemptionToken" objects that are unlinkable from the server's computation in "PP_Issue". Inputs: * "cli_cfg": A "ClientConfig" struct. * "issuance_response": A "IssuanceResponse" struct. * "processing_data": A "ClientIssuanceProcessing" struct. Outputs: * "tokens": A vector of "RedemptionToken" structs, length equal to the length of the "ServerEvaluation" vector in the "IssuanceResponse" struct. Throws: * "ERR_PROOF_VALIDATION" (Section 3.3) 3.2.6. PP_Redeem Run by the client in the redemption phase of the protocol to generate the client's message. Inputs: * "cli_cfg": A "ClientConfig" struct. Davidson Expires 10 September 2020 [Page 11] Internet-Draft PP protocol March 2020 * "token": A "RedemptionToken" struct. * "aux": An "opaque<1..2^32-1>" type corresponding to arbitrary auxiliary data. Outputs: * "message": A "RedemptionMessage" struct. 3.2.7. PP_Verify Run by the server in the redemption phase of the protocol. Determines whether the data sent by the client is valid. Inputs: * "srv_cfg": A "ServerConfig" struct. * "message": A "RedemptionMessage" struct. Outputs: * "response": A "RedemptionResponse" struct. 3.3. Error types * "ERR_UNSUPPORTED_CONFIG": Error occurred when trying to recover configuration with unknown identifier * "ERR_MAX_EVALS": Client attempted to invoke server issuance with number of inputs that is larger than server-specified max_evals value. * "ERR_PROOF_VALIDATION": Client unable to verify proof that is part of the server response. * "ERR_DOUBLE_SPEND": Indicates that a client has attempted to redeem a token that has already been used for authorization. 4. Generalized protocol overview In this document, we wan to provide a client (C) with the capability to authenticate itself in a lightweight manner to a server (S). The authorization mechanism should not reveal to the server anything about the client; in addition, the client should not be able to forge valid credentials in situations where it does not possess any. These requirements are covered in Section 5. Davidson Expires 10 September 2020 [Page 12] Internet-Draft PP protocol March 2020 In this section, we will give a broad overview of how the Privacy Pass protocol functions in achieving these goals. The generic protocol can be split into three phases: initialisation, issuance and redemption. These three phases are built upon the Privacy Pass API in Section 3. We show later (Section 6) that this API can be implemented using an underlying VOPRF protocol. We provide this extra layer of abstraction to allow building extensions into the Privacy Pass protocol that go beyond what is specified in [I-D.irtf-cfrg-voprf]. 4.1. Key initialisation phase In the initialisation phase, the server generates the configuration that it will use for future instantiations of the protocol. It MUST broadcast the configuration that it generates, along with the public key, so that clients are aware of which configuration to use when interacting with the server. In situations where the number of clients are small, it could do this by sending the data to the client directly. But in situations where there is a large number of clients, the best way of doing is likely to be via posting this information to a public bulletin board. We assume that the server only has a single configuration in place at any one time. There are privacy restrictions related to this that are described in more detail in the architectural document [draft-davidson-pp-architecture]. We give a diagrammatic representation of the initialisation phase below. C(cfgs) S(cfg_id) ------------------------------------------------------------------- (cfg, update) = PP_Server_Setup(cfg_id) update <------------------- c_cfg = PP_Client_Setup(cfg_id,update) cfgs.set(update.id,c_cfg) In the following (and as above), we will assume that the server "S" is uniquely identifiable by an internal attribute "id". We assume the same internal attribute exists for the public key "s_cfg.pub_key". This can be obtained, for example, by hashing the contents of the object - either the name or underlying contained bytes - using a collision-resistant hash function, such as SHA256. Davidson Expires 10 September 2020 [Page 13] Internet-Draft PP protocol March 2020 Note that the client stores their own configuration in the map "cfgs" for future Privacy Pass interactions with "S". 4.2. Issuance phase The issuance phase allows the client to construct "RedemptionToken" object resulting from an interaction with a server "S" that it has previously interacted with. We give a diagrammatic overview of the protocol below. C(cfgs,store,m) S(s_cfg) ------------------------------------------------------------------- S.id <------------------ c_cfg = cfgs.get(S.id) issue_input = PP_Generate(c_cfg, m) msg = issue_input.msg_data process = issue_input.client_data msg -------------------> issue_resp = PP_Issue(s_cfg,c_dat) issue_resp <------------------- tokens = PP_Process(c_cfg,issue_resp,process) store[S.id].push(tokens) In the diagram above, the client MUST know the supported server configuration before it interacts with the Privacy Pass API. The client input "store" is used for appending redemption tokens that are linked to the server id "S.id". 4.3. Redemption phase The redemption phase allows the client to reauthenticate to the server, using data that it has received from a previous issuance phase. We lay out the security requirements in Section 5 that establish that the client redemption data is not linkable to any given issuance session. Davidson Expires 10 September 2020 [Page 14] Internet-Draft PP protocol March 2020 C(cfgs,store,aux) S(s_cfg,ds_idx) ------------------------------------------------------------------- S.id <------------------ c_cfg = cfgs.get(S.id) token = store[S.id].pop() msg = PP_Redeem(c_cfg,token,aux) msg ------------------> if (ds_idx.includes(data)) { panic(ERR_DOUBLE_SPEND) } resp = PP_Verify(srv_cfg,data,tag,aux) if (resp.success) { ds_idx.push(data) } resp <------------------ Output resp The client input "aux" is arbitrary byte data that is used for linking the redemption request to the specific session. We RECOMMEND that "aux" is constructed as the following concatenated byte-encoded data: ${C.id} .. ${S.id} .. ${current_time()} .. ${requested_resource()} The usage of "current_time()" allows the server to check that the redemption request has happened in an appropriate time window. The function "requested_resource()" is an optional suffix that relates to any specific resources that the client has requested from the server, in order to trigger the authorization request. 4.3.1. Double-spend protection To protect against clients that attempt to spend a value "data" more than once, the server uses an index, "ds_idx", to collect valid inputs and then check against in future protocols. Since this store needs to only be optimized for storage and querying, a structure such as a Bloom filter suffices. Importantly, the server MUST only eject this storage after a key rotation occurs since all previous client data will be rendered obsolete after such an event. Davidson Expires 10 September 2020 [Page 15] Internet-Draft PP protocol March 2020 4.4. Handling errors It is possible for the API functions from Section 3.2 to return one of the errors indicated in Section 3.3 rather than their expected value. In these cases, we assume that the entire protocol execution panics with the value of the error. If a panic occurs during the server's operations for one of the documented errors, then the server returns an error response indicating the error that occurred. 5. Security requirements We discuss the security requirements that are necessary to uphold when instantiating the Privacy Pass protocol. In particular, we focus on the security requirements of "unlinkability", and "unforgeability". Informally, the notion of unlinkability is required to preserve the privacy of the client in the redemption phase of the protocol. The notion of unforgeability is to protect against adversarial clients that look to subvert the security of the protocol. Since these are cryptographic security requirements we discuss them with respect to a polynomial-time algorithm known as the adversary that is looking to subvert the security guarantee. More details on both security requirements can be found in [DGSTV18] and [KLOR20]. Note that the privacy requirements of the protocol are covered in the architectural framework document [draft-davidson-pp-architecture]. 5.1. Unlinkability Informally, the "unlinkability" requirement states that it is impossible for an adversarial server to link the client's message in a redemption session, to any previous issuance session that it has encountered. Formally speaking the security model is the following: * The adversary runs "PP_Server_Setup" and generates a key-pair "(k, pk)". * The adversary specifies a number "Q" of issuance phases to initiate, where each phase "i in 1..Q" consists of "m_i" server evaluations. * The adversary runs "PP_Issue" using the key-pair that it generated on each of the client messages in the issuance phase. Davidson Expires 10 September 2020 [Page 16] Internet-Draft PP protocol March 2020 * When the adversary wants it stops the issuance phase, and a random number "l" is picked from "1..Q". * A redemption phase is initiated with a single token with index "i" randomly sampled from "1..m_l". * The adversary guesses an index "l_guess" corresponding to the index of the issuance phase that it believes the redemption token was received in. * The adversary succeeds if "l == l_guess". The security requirement is that the adversary has only a negligible probability of success greater than "1/Q". 5.2. One-more unforgeability The one-more unforgeability requirement states that it is hard for any adversarial client that has received "m" valid tokens from a server to redeem "m+1" of them. In essence, this requirement prevents a malicious client from being able to forge valid tokens based on the server responses that it sees. The security model takes the following form: * A server is created that runs "PP_Server_Setup" and broadcasts the "ServerUpdate" message "update". * The adversary runs "PP_Client_Setup" on "update". * The adversary specifies a number "Q" of issuance phases to initiate with the server, where each phase "i in 1..Q" consists of "m_i" server evaluations. Let "m = sum(m_i)" where "i in 1..Q". * The client receives Q responses, where the response with index "i" contains "m_i" individual tokens. * The adversary initiates "m_adv" redemption sessions with the server and the server verifies that the sessions are successful (return true), and that each request includes a unique token. The adversary succeeds in "m_succ =< m_adv" redemption sessions. * The adversary succeeds if "m_succ > m". The security requirement is that the adversarial client has only a negligible probability of succeeding. Davidson Expires 10 September 2020 [Page 17] Internet-Draft PP protocol March 2020 Note that [KLOR20] strengthens the capabilities of the adversary, in comparison to the original work of [DGSTV18]. In [KLOR20], the adversary is provided with oracle access that allows it to verify that the server responses in the issuance phase are valid. 5.3. Double-spend protection All issuing servers should implement a robust, global storage-query mechanism for checking that tokens sent by clients have not been spent before. Such tokens only need to be checked for each issuer individually. This prevents clients from "replaying" previous requests, and is necessary for achieving the unforgeability requirement. 6. VOPRF instantiation In this section, we show how to instantiate the functional API in Section 3 with the VOPRF protocol described in [I-D.irtf-cfrg-voprf]. Moreover, we show that this protocol satisfies the security requirements laid out in Section 5, based on the security proofs provided in [DGSTV18] and [KLOR20]. 6.1. VOPRF conventions The VOPRF ciphersuite [I-D.irtf-cfrg-voprf] that is used determines the member functions and prime-order group used by the protocol. We detail a number of specific conventions here that we use for interacting with the specific ciphersuite. 6.1.1. Ciphersuites Let "F" denote a generic VOPRF API function as detailed in [I-D.irtf-cfrg-voprf] (Section TODO), and let "ciph" denote the ciphersuite that is used for instantiating the VOPRF. In this document, we explicitly write "ciph.F" to show that "F" is explicitly evaluated with respect to "ciph". In addition, we define the following member functions associated with the ciphersuite. * "recover_ciphersuite_from_id(id)": Takes a string identifier "id" as input, and outputs a VOPRF ciphersuite. Returns "null" if "id" is not recognized. * "group()": Returns the prime-order group associated with the ciphersuite. Davidson Expires 10 September 2020 [Page 18] Internet-Draft PP protocol March 2020 * "H1()": The function "H1()" defined in [I-D.irtf-cfrg-voprf] (Section TODO). This function allows deterministically mapping arbitrary bytes to a random element of the group. In the elliptic curve setting, this is achieved using the functions defined in [I-D.irtf-cfrg-hash-to-curve]. 6.1.2. Prime-order group conventions We detail a few functions that are required of the prime-order group "GG" used by the VOPRF in [I-D.irtf-cfrg-voprf]. Let "p" be the order of the Galois field "GF(p)" associated with the group "GG". We expose the following functions associated with "GG". * "GG.generator()": Returns the fixed generator associated with the group "GG". * "GG.scalar_field()": Provides access to the field "GF(p)". * "GG.scalar_field().random()": Samples a scalar uniformly at random from GF(p). This can be done by sampling a random sequence of bytes that produce a scalar "r", where "r < p" is satisfied (via rejection-sampling). We also use the following functions for transitioning between different data types. * "as_bytes()": For a scalar element of "GG.scalar_field()", or an element of "GG"; the "as_bytes()" functions serializes the element into bytes and returns this array as output. * "as_scalar()": Interprets a sequence of bytes as a scalar value in "GG.scalar_field()". For an array of byte arrays, we define the function "as_scalars()" to individually deserialize each of the individual byte arrays into a scalar and output a new array containing each scalar value. * "as_element()": Interprets a sequence of bytes as a group element in "GG". For an array of byte arrays, we define the function "as_elements()" to individually deserialize each of the individual byte arrays into a single group element and output a new array containing each of these elements. 6.2. API instantiation For the explicit signatures of each of the functions, refer to Section 3.2. Davidson Expires 10 September 2020 [Page 19] Internet-Draft PP protocol March 2020 6.2.1. PP_Server_Setup 1. ciph = recover_ciphersuite_from_id(id) 2. if ciph == null: panic(ERR_UNSUPPORTED_CONFIG) 3. (k,Y,GG) = ciph.VerifiableSetup() 4. key = k.as_bytes() 5. pub_key = Y.as_bytes() 6. cfg = ServerConfig { id: id ciphersuite: ciph, key: key, pub_key: pub_key, max_evals: max_evals } 7. update = ServerUpdate { id: id ciphersuite: ciph, pub_key: pub_key, max_evals: max_evals } 8. Output (cfg, update) 6.2.2. PP_Client_Setup 1. ciph = recover_ciphersuite_from_id(id) 2. if ciph == null: panic(ERR_UNSUPPORTED_CONFIG) 3. cfg = ClientConfig { s: update } 4. Output cfg 6.2.3. PP_Generate Davidson Expires 10 September 2020 [Page 20] Internet-Draft PP protocol March 2020 1. ciph = cli_cfg.s.ciphersuite 2. GG = ciph.group() 3. c_data = [] 4. i_data = [] 5. g_data = [] 6. for i in 0..m: 1. c_data[i] = GG.scalar_field().random().as_bytes() 7. (blinds,group_elems) = ciph.VerifiableBlind(c_data) 8. for i in 0..m: 1. i_data[i] = group_elems[i].as_bytes() 2. g_data[i] = blinds[i].as_bytes() 9. Output ClientIssuanceInput { ClientIssuanceProcessing { client_data: c_data, gen_data: g_data, }, ClientIssuanceElement { msg_data: i_data, } } 6.2.4. PP_Issue 1. ciph = srv_cfg.ciphersuite 2. pk = srv_cfg.pub_key.as_element() 3. GG = ciph.group() 4. m = msg_data.length 5. if m > max_evals: panic(ERR_MAX_EVALS) 6. G = GG.generator() 7. elts = msg_data.as_elements(); 8. Z,D = ciph.VerifiableEval(key.as_scalar(),G,pk,elts) 9. evals = [] 10. for i in 0..m: 1. eval[i] = ServerEvaluation { data: Z[i].as_bytes(); } 11. proof = ServerProof { data: D.as_bytes() } 12. Output IssuanceResponse { evaluations: eval, proof: proof, } 6.2.5. PP_Process Davidson Expires 10 September 2020 [Page 21] Internet-Draft PP protocol March 2020 1. ciph = cli_cfg.s.ciphersuite 2. GG = ciph.group() 3. G = GG.generator() 4. pk = cli_cfg.s.pub_key.as_element() 5. M = i_data.as_elements() 6. Z = evals.as_elements() 7. r = g_data.as_scalars() 8. N = ciph.VerifiableUnblind(G,pk,M,Z,r,proof) 9. if N == "error": panic(ERR_PROOF_VALIDATION) 10. tokens = [] 11. for i in 0..m: 1. issued = N[i].as_bytes() 2. rt = RedemptionToken { data: c_data[i], issued: issued } 3. tokens[i] = rt 12. Output tokens 6.2.6. PP_Redeem 1. ciph = cli_cfg.s.ciphersuite 2. GG = ciph.group() 3. token = store[S.id].pop(); 4. data = token.data 5. issued = token.issued.as_element(); 6. tag = ciph.VerifiableFinalize(data,issued,aux) 7. Output RedemptionMessage { data: data, tag: tag, aux: aux, } 6.2.7. PP_Verify 1. ciph = srv_cfg.ciphersuite 2. GG = ciph.group() 3. key = srv_cfg.key 4. T = ciph.H1(msg.data) 5. N' = ciph.Eval(key,T) 6. tag' = ciph.Finalize(msg.data,N',msg.aux) 7. Output RedemptionResponse { success: (msg.tag == tag') } Note: at this stage we use the non-verifiable VOPRF API functions rather than the verifiable equivalents ("Eval" rather than "VerifiableEval"), as we do not need to recompute the proof data that is used for producing verifiable outputs at this stage. Davidson Expires 10 September 2020 [Page 22] Internet-Draft PP protocol March 2020 6.3. Security justification The protocol that we devise in Section 4, coupled with the API instantiation in Section 6.2, are equivalent to the protocol description in [DGSTV18]. In [DGSTV18], it is proven that this protocol satisfies the security requirements of unlinkability (Section 5.1) and unforgeability (Section 5.2). The unlinkability property follows unconditionally as the view of the adversary in the redemption phase is distributed independently of the issuance phase. The unforgeability property follows from the one- more decryption security of the ElGamal cryptosystem [DGSTV18]. In [KLOR20] it is also proven that this protocol satisfies the stronger notion of unforgeability, where the adversary is granted a verification oracle, under the chosen-target Diffie-Hellman assumption. Note that the existing security proofs do not leverage the VOPRF primitive as a black-box in the security reductions. Instead it relies on the underlying operations in a non-black-box manner. Hence, an explicit reduction from the generic VOPRF primitive to the Privacy Pass protocol would strengthen these security guarantees. 7. Ciphersuites The Privacy Pass protocol essentially operates as a wrapper around the instantiation of the VOPRF that is used in Section 6. There is no extra cryptographic machinery used on top of what is established in the VOPRF protocol. Therefore, the ciphersuites that we support are the transitively exposed from the underlying VOPRF functionality, we detail these below. Each of the ciphersuites is detailed in [I-D.irtf-cfrg-voprf]. * VOPRF-P384-HKDF-SHA512-SSWU-RO - maximum security parameter: 192 bits * VOPRF-curve448-HKDF-SHA512-ELL2-RO - maximum security parameter: 224 bits * VOPRF-P521-HKDF-SHA512-SSWU-RO - maximum security parameter: 256 bits When referring to the 'maximum security parameter' size above, we are referring to the _maximum_ effective key length of the ciphersuite, as specified in [NIST]. The reason that this is the maximum length Davidson Expires 10 September 2020 [Page 23] Internet-Draft PP protocol March 2020 is because there may be attacks that serve to lower the actual value of the security parameter. See [I-D.irtf-cfrg-voprf] for more details. Note than any extension to the Privacy Pass protocol that modifies either VOPRF instantiation, or the way that the Privacy Pass API is implemented, MUST specify its own ciphersuites. 8. Extensions framework policy The intention with providing the Privacy Pass API in Section 3 is to allow new instantiations of the Privacy Pass protocol. These instantiations may provide either modified VOPRF constructions, or simply implement the API in a completely different way. Extensions to this initial draft SHOULD be specified as separate documents taking one of two possible routes: * Produce new VOPRF-like primitives that use the same public API provided in [I-D.irtf-cfrg-voprf] to implement the Privacy Pass API, but with different internal operations. * Implement the Privacy Pass API in a different way to the proposed implementation in Section 6. If an extension requires changing the generic protocol description as described in Section 4, then the change may have to result in changes to the draft specification here also. Each new extension that modifies the internals of the protocol in either of the two ways MUST re-justify that the extended protocol still satisfies the security requirements in Section 5. Protocol extensions MAY put forward new security guarantees if they are applicable. The extensions MUST also conform with the extension framework policy as set out in the architectural framework document. For example, this may concern any potential impact on client privacy that the extension may introduce. 9. References 9.1. Normative References [draft-davidson-pp-architecture] Davidson, A., "Privacy Pass: Architectural Framework", n.d., . Davidson Expires 10 September 2020 [Page 24] Internet-Draft PP protocol March 2020 [I-D.irtf-cfrg-hash-to-curve] Faz-Hernandez, A., Scott, S., Sullivan, N., Wahby, R., and C. Wood, "Hashing to Elliptic Curves", Work in Progress, Internet-Draft, draft-irtf-cfrg-hash-to-curve-05, 2 November 2019, . [I-D.irtf-cfrg-voprf] Davidson, A., Sullivan, N., and C. Wood, "Oblivious Pseudorandom Functions (OPRFs) using Prime-Order Groups", Work in Progress, Internet-Draft, draft-irtf-cfrg-voprf- 02, 4 November 2019, . [NIST] "Keylength - NIST Report on Cryptographic Key Length and Cryptoperiod (2016)", n.d., . [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018, . 9.2. Informative References [DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously", n.d., . [KLOR20] "Anonymous Tokens with Private Metadata Bit", n.d., . [OpenPrivacy] "Token Based Services - Differences from PrivacyPass", n.d., . [PPEXT] "Privacy Pass Browser Extension", n.d., . [PPSRV] Sullivan, N., "Cloudflare Supports Privacy Pass", n.d., . Davidson Expires 10 September 2020 [Page 25] Internet-Draft PP protocol March 2020 [PrivateStorage] Steininger, L., "The Path from S4 to PrivateStorage", n.d., . [RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049, October 2013, . [RFC7159] Bray, T., Ed., "The JavaScript Object Notation (JSON) Data Interchange Format", RFC 7159, DOI 10.17487/RFC7159, March 2014, . [TRUST] WICG, ., "Trust Token API", n.d., . Author's Address Alex Davidson Cloudflare Portugal Largo Rafael Bordalo Pinheiro 29 Lisbon Portugal Email: alex.davidson92@gmail.com Davidson Expires 10 September 2020 [Page 26]