Network Working Group S. Celi
Internet-Draft Cloudflare
Intended status: Informational A. Davidson
Expires: 23 August 2021 LIP
A. Faz-Hernandez
Cloudflare
19 February 2021
Privacy Pass Protocol Specification
draft-ietf-privacypass-protocol-01
Abstract
This document specifies the Privacy Pass protocol. This protocol
provides anonymity-preserving authorization of clients to servers.
In particular, 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 application-layer.
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 23 August 2021.
Copyright Notice
Copyright (c) 2021 IETF Trust and the persons identified as the
document authors. All rights reserved.
Celi, et al. Expires 23 August 2021 [Page 1]
Internet-Draft PP protocol February 2021
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.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Background . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1. Motivating use-cases . . . . . . . . . . . . . . . . . . 4
3.2. Anonymity and security guarantees . . . . . . . . . . . . 5
3.3. Basic assumptions . . . . . . . . . . . . . . . . . . . . 5
4. Protocol description . . . . . . . . . . . . . . . . . . . . 5
4.1. Server setup . . . . . . . . . . . . . . . . . . . . . . 6
4.2. Client setup . . . . . . . . . . . . . . . . . . . . . . 6
4.3. Issuance phase . . . . . . . . . . . . . . . . . . . . . 6
4.4. Redemption phase . . . . . . . . . . . . . . . . . . . . 8
4.4.1. Client info . . . . . . . . . . . . . . . . . . . . . 8
4.4.2. Double-spend protection . . . . . . . . . . . . . . . 9
4.5. Handling errors . . . . . . . . . . . . . . . . . . . . . 9
5. Functionality . . . . . . . . . . . . . . . . . . . . . . . . 9
5.1. Data structures . . . . . . . . . . . . . . . . . . . . . 9
5.1.1. Ciphersuite . . . . . . . . . . . . . . . . . . . . . 9
5.1.2. Keys . . . . . . . . . . . . . . . . . . . . . . . . 9
5.1.3. CommitRequest . . . . . . . . . . . . . . . . . . . . 10
5.1.4. CommitResponse . . . . . . . . . . . . . . . . . . . 10
5.1.5. IssuanceInput . . . . . . . . . . . . . . . . . . . . 10
5.1.6. IssuanceResponse . . . . . . . . . . . . . . . . . . 10
5.1.7. RedemptionToken . . . . . . . . . . . . . . . . . . . 11
5.1.8. RedemptionRequest . . . . . . . . . . . . . . . . . . 11
5.1.9. RedemptionResponse . . . . . . . . . . . . . . . . . 11
5.2. API functions . . . . . . . . . . . . . . . . . . . . . . 12
5.2.1. Prepare . . . . . . . . . . . . . . . . . . . . . . . 12
5.2.2. Commit . . . . . . . . . . . . . . . . . . . . . . . 12
5.2.3. Generate . . . . . . . . . . . . . . . . . . . . . . 12
5.2.4. Issue . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2.5. Process . . . . . . . . . . . . . . . . . . . . . . . 13
5.2.6. Redeem . . . . . . . . . . . . . . . . . . . . . . . 14
5.2.7. Verify . . . . . . . . . . . . . . . . . . . . . . . 14
5.3. Error types . . . . . . . . . . . . . . . . . . . . . . . 14
6. Security considerations . . . . . . . . . . . . . . . . . . . 15
6.1. Unlinkability . . . . . . . . . . . . . . . . . . . . . . 15
6.2. One-more unforgeability . . . . . . . . . . . . . . . . . 16
Celi, et al. Expires 23 August 2021 [Page 2]
Internet-Draft PP protocol February 2021
6.3. Double-spend protection . . . . . . . . . . . . . . . . . 16
6.4. Additional token metadata . . . . . . . . . . . . . . . . 17
6.5. Maximum number of tokens issued . . . . . . . . . . . . . 17
7. VOPRF instantiation . . . . . . . . . . . . . . . . . . . . . 17
7.1. Recommended ciphersuites . . . . . . . . . . . . . . . . 17
7.2. Protocol contexts . . . . . . . . . . . . . . . . . . . . 18
7.3. Functionality . . . . . . . . . . . . . . . . . . . . . . 18
7.3.1. Generate . . . . . . . . . . . . . . . . . . . . . . 18
7.3.2. Issue . . . . . . . . . . . . . . . . . . . . . . . . 19
7.3.3. Process . . . . . . . . . . . . . . . . . . . . . . . 19
7.3.4. Redeem . . . . . . . . . . . . . . . . . . . . . . . 19
7.3.5. Verify . . . . . . . . . . . . . . . . . . . . . . . 19
7.4. Security justification . . . . . . . . . . . . . . . . . 20
8. Protocol ciphersuites . . . . . . . . . . . . . . . . . . . . 20
8.1. PP(OPRF2) . . . . . . . . . . . . . . . . . . . . . . . . 20
8.2. PP(OPRF4) . . . . . . . . . . . . . . . . . . . . . . . . 21
8.3. PP(OPRF5) . . . . . . . . . . . . . . . . . . . . . . . . 21
9. Extensions framework policy . . . . . . . . . . . . . . . . . 21
10. References . . . . . . . . . . . . . . . . . . . . . . . . . 22
10.1. Normative References . . . . . . . . . . . . . . . . . . 22
10.2. Informative References . . . . . . . . . . . . . . . . . 22
Appendix A. Document contributors . . . . . . . . . . . . . . . 23
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 23
1. Introduction
A common problem on the Internet is providing an effective mechanism
for servers to derive trust from clients that they interact with.
Typically, this can be done by providing some sort of authorization
challenge to the client. But this also negatively impacts the
experience of clients that regularly have to solve such challenges.
To mitigate accessibility issues, a client that correctly solves the
challenge can be provided with a cookie. This cookie can be
presented the next time the client interacts with the server, instead
of performing the challenge. However, this does not solve the
problem of reauthorization of clients across multiple domains. Using
current tools, providing some multi-domain authorization token would
allow linking client browsing patterns across those domains, and
severely reduces their online privacy.
The Privacy Pass protocol provides a set of cross-domain
authorization tokens that protect the client's anonymity in message
exchanges with a server. This allows clients to communicate an
attestation of a previously authenticated server action, without
having to reauthenticate manually. The tokens retain anonymity in
the sense that the act of revealing them cannot be linked back to the
session where they were initially issued.
Celi, et al. Expires 23 August 2021 [Page 3]
Internet-Draft PP protocol February 2021
This document lays out the generic description of the protocol, along
with the data and message formats. We detail an implementation of
the protocol functionality based on the description of a verifiable
oblivious pseudorandom function [I-D.irtf-cfrg-voprf].
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]. In addition,
[draft-svaldez-pp-http-api] provides an instantiation of this
protocol intended for the HTTP setting.
2. 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. May be referred to as the issuer.
* Client: An entity that seeks authorization from a server that
supports interactions in the Privacy Pass protocol.
* Key: The secret key used by the server for authorizing client
data.
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.
3. Background
We discuss the core motivation behind the protocol along with the
guarantees and assumptions that we make in this document.
3.1. Motivating use-cases
The Privacy Pass protocol was originally developed to provide
anonymous authorization of Tor users. In particular, the protocol
allows clients to reveal authorization tokens that they have been
issued without linking the authorization to the actual issuance
event. This means that the tokens cannot be used to link the
browsing patterns of clients that reveal tokens.
Celi, et al. Expires 23 August 2021 [Page 4]
Internet-Draft PP protocol February 2021
Beyond these uses-cases, the Privacy Pass protocol is used in a
number of practical applications. See [DGSTV18], [TrustTokenAPI],
[PrivateStorage], [OpenPrivacy], and [Brave] for examples.
3.2. Anonymity and security guarantees
Privacy Pass provides anonymity-preserving authorization tokens for
clients. Throughout this document, we use the terms "anonymous",
"anonymous-preserving" and "anonymity" to refer to the core security
guarantee of the protocol. Informally, this guarantee means that any
token issued by a server key and subsequently redeemed is
indistinguishable from any other token issued under the same key.
Privacy Pass also prohibits clients from forging tokens, as otherwise
the protocol would have little value as an authorization protocol.
Informally, this means any client that is issued "N" tokens under a
given server key cannot redeem more than "N" valid tokens.
Section 6 elaborates on these protocol anonymity and security
requirements.
3.3. Basic assumptions
We make only a few minimal assumptions about the environment of the
clients and servers supporting 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. This ensures that all clients are issued tokens
under the single key associated with any given epoch.
* We assume that the client has access to a global directory of the
current public parts of the configurations used the server.
The wider ecosystem that this protocol is employed in is described in
[draft-davidson-pp-architecture].
4. Protocol description
The Privacy Pass protocol is split into two phases that are built
upon the functionality described in Section 5 later.
Celi, et al. Expires 23 August 2021 [Page 5]
Internet-Draft PP protocol February 2021
The first phase, "issuance", provides the client with unlinkable
tokens that can be used to initiate re-authorization with the server
in the future. The second phase, "redemption", allows the client to
redeem a given re-authorization token with the server that it
interacted with during the issuance phase. The protocol must satisfy
two cryptographic security requirements known as "unlinkability" and
"unforgeability". These requirements are covered in Section 6.
4.1. Server setup
Before the protocol takes place, the server chooses a ciphersuite and
generates a keypair by running "(pkS, skS) = KeyGen()". This
configuration must be available to all clients that interact with the
server (for the purpose of engaging in a Privacy Pass exchange). We
assume that the server has a public (and unique) identity that the
client uses to retrieve this configuration.
4.2. Client setup
The client initialises a global storage system "store" that allows it
store the tokens that are received during issuance. The storage
system is a map of server identifiers ("server.id") to arrays of
stored tokens. We assume that the client knows the server public key
"pkS" ahead of time. The client picks a value "m" of tokens to
receive during the issuance phase. In
[draft-davidson-pp-architecture] we discuss mechanisms that the
client can use to ensure that this public key is consistent across
the entire ecosystem.
4.3. Issuance phase
The issuance phase is a two-round protocol that allows the client to
receive "m" anonymous authorization tokens from the server. The
first round sees the server generate a commitment. The second round
sees the server issue a token to the client.
Celi, et al. Expires 23 August 2021 [Page 6]
Internet-Draft PP protocol February 2021
Client(pkS, m, info) Server(skS, pkS)
------------------------------------------------------------
commit_req = Prepare(info)
commit_req
------------------->
commit_resp = Commit(skS, pkS, commit_req)
commit_resp
<-------------------
cInput = Generate(m, commit_resp)
req = cInput.req
req
------------------->
issueResp = Issue(pkS, skS, req)
serverResp
<-------------------
tokens = Process(pkS, cInput, serverResp)
store[server.id].push(tokens)
Note that the first round of the protocol is only necessitated for
certain ciphersuites that require client and servers commit to some
value. When such commitment "commit_resp" is generated and sent to
the client, the client returns "commit_resp" with the
"IssuanceRequest" message. The server MUST check that the commitment
corresponds to "commit_resp" that was previously committed. This
requires the commitment to either be a reference to some commitment
on the server, or the commitment be an encrypted (and authenticated)
blob that the server can use to recover commitment. The mechanism by
which servers handle this commitment is implementation specific, and
similar to how TLS session resumption state is managed; see [RFC8446]
for details. In addition, the "Commit" function is implementation-
specific and MUST be defined by the underlying ciphersuite.
When the server does not need to generate this commitment, the client
instead DOES NOT send the "CommitRequest" message, and runs:
cInput = Generate(m, "")
Celi, et al. Expires 23 August 2021 [Page 7]
Internet-Draft PP protocol February 2021
A server that is expecting some non-empty "commit_resp" to be passed
must abort the protocol on receiving a request containing an empty
"commit_resp" value.
Note: currently, no ciphersuites are supported that support working
with empty commitment messages.
4.4. Redemption phase
The redemption phase allows the client to anonymously reauthenticate
to the server, using data that it has received from a previous
issuance phase.
Client(info) Server(skS, pkS)
------------------------------------------------------------
token = store[server.id].pop()
req = Redeem(token, info)
req
------------------>
if (dsIdx.includes(req.data)) {
raise ERR_DOUBLE_SPEND
}
resp = Verify(pkS, skS, req)
if (resp.success) {
dsIdx.push(req.data)
}
resp
<------------------
Output resp
4.4.1. Client info
The client input "info" is arbitrary byte data that is used for
linking the redemption request to the specific session. We RECOMMEND
that "info" is constructed as the following concatenated byte-encoded
data:
len(aux) || aux || len(server.id) || server.id || current_time()
where "len(x)" is the length of "x" in bytes, and "aux" is arbitrary
auxiliary data chosen by the client. The usage of "current_time()"
allows the server to check that the redemption request has happened
in an appropriate time window.
Celi, et al. Expires 23 August 2021 [Page 8]
Internet-Draft PP protocol February 2021
4.4.2. Double-spend protection
To protect against clients that attempt to spend a value "req.data"
more than once, the server uses an index, "dsIdx", to collect valid
inputs it witnesses. Since this store needs to only be optimized for
storage and querying, a structure such as a Bloom filter suffices.
The storage should be parameterized to live as long as the server
keypair that is in use. See Section 6 for more details.
4.5. Handling errors
It is possible for the API functions from Section 5.2 to return one
of the errors indicated in Section 5.3 rather than their expected
value. In these cases, we assume that the entire protocol aborts.
5. Functionality
This section details the data types and API functions that are used
to construct the protocol in Section 4.
We provide an explicit instantiation of the Privacy Pass API in
Section 7.3, based on the public API provided in
[I-D.irtf-cfrg-voprf].
5.1. Data structures
The following data structures are used throughout the Privacy Pass
protocol and are 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].
5.1.1. Ciphersuite
The "Ciphersuite" enum provides identifiers for each of the supported
ciphersuites of the protocol. Some initial values that are supported
by the core protocol are described in Section 8. Note that the list
of supported ciphersuites may be expanded by extensions to the core
protocol description in separate documents.
5.1.2. Keys
We use the following types to describe the public and private keys
used by the server.
opaque PublicKey<1..2^16-1>
opaque PrivateKey<1..2^16-1>
Celi, et al. Expires 23 August 2021 [Page 9]
Internet-Draft PP protocol February 2021
5.1.3. CommitRequest
The "CommitRequest" struct is simply a fixed message allowing opaque
metadata.
struct {
opaque info<1..2^16-1>
} CommitRequest;
5.1.4. CommitResponse
The "CommitResponse" struct is contains an opaque set of bytes that
correspond to some commitment that the server has generated. The
structure and format of this value is implementation specific
depending on whether the server is stateful.
struct {
opaque commitment<1..2^16-1>
} CommitResponse;
5.1.5. IssuanceInput
The "IssuanceInput" struct describes the data that is initially
generated by the client during the issuance phase.
Firstly, we define sequences of bytes that partition the client
input.
opaque Internal<1..2^16-1>
opaque IssuanceRequest<1..2^16-1>
These data types represent members of the wider "IssuanceInput" data
type.
struct {
Internal data[m]
IssuanceRequest req[m]
} IssuanceInput;
Note that a "IssuanceInput" contains equal-length arrays of
"Internal" and "IssuanceRequest" types corresponding to the number of
tokens that should be issued.
5.1.6. IssuanceResponse
Firstly, the "IssuedToken" type corresponds to a single sequence of
bytes that represents a single issued token received from the server.
Celi, et al. Expires 23 August 2021 [Page 10]
Internet-Draft PP protocol February 2021
opaque IssuedToken<1..2^16-1>
Then an "IssuanceResponse" corresponds to a collection of
"IssuedTokens" as well as a sequence of bytes "proof".
struct {
IssuedToken tokens[m]
opaque proof<1..2^16-1>
}
The value of "m" is equal to the length of the "IssuanceRequest"
vector sent by the client.
5.1.7. RedemptionToken
The "RedemptionToken" struct contains the data required to generate
the client message in the redemption phase of the Privacy Pass
protocol.
struct {
opaque data<1..2^16-1>;
opaque issued<1..2^16-1>;
} RedemptionToken;
5.1.8. RedemptionRequest
The "RedemptionRequest" struct consists of the data that is sent by
the client during the redemption phase of the protocol.
struct {
opaque data<1..2^16-1>;
opaque tag<1..2^16-1>;
opaque info<1..2^16-1>;
} RedemptionRequest;
5.1.9. RedemptionResponse
The "RedemptionResponse" struct corresponds to a boolean value that
indicates whether the "RedemptionRequest" sent by the client is
valid. It can also contain any associated data.
struct {
boolean success;
opaque ad<1..2^16-1>;
} RedemptionResponse;
Celi, et al. Expires 23 August 2021 [Page 11]
Internet-Draft PP protocol February 2021
5.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 defined by specific instantiations or extensions of
the protocol.
5.2.1. Prepare
A function run by the client to prepare for a commitment will used
during the issuance flow of the Privacy Pass protocol.
Inputs:
"info": An opaque byte application-specific byte string.
Outputs:
"commit_req": A "CommitRequest" struct.
This function should be implemented by any ciphersuites that require
a two-phase issuance protocol ("COMMIT=true").
5.2.2. Commit
A function run by the server that generates a commitment in the first
phase of the issuance protocol.
Inputs:
* "skS": A server "PrivateKey".
* "pkS": A server "PublicKey".
* "commit_req": A "CommitRequest" struct
Outputs:
* "commit_resp": A "CommitResponse" struct.
This function should be implemented by any ciphersuites that require
a two-phase issuance protocol ("COMMIT=true").
5.2.3. Generate
A function run by the client to generate the initial data that is
used as its input in the Privacy Pass protocol.
Celi, et al. Expires 23 August 2021 [Page 12]
Internet-Draft PP protocol February 2021
Inputs:
* "m": A "uint8" value corresponding to the number of Privacy Pass
tokens to generate.
Outputs:
* "input": An "IssuanceInput" struct.
5.2.4. Issue
A function run by the server to issue valid redemption tokens to the
client.
Inputs:
* "pkS": A server "PublicKey".
* "skS": A server "PrivateKey".
* "req": An "IssuanceRequest" struct.
Outputs:
* "resp": An "IssuanceResponse" struct.
Throws:
* "ERR_FAILED_COMMITMENT" (Section 5.3)
5.2.5. Process
Run by the client when processing the server response in the issuance
phase of the protocol.
Inputs:
* "pkS": An server "PublicKey".
* "input": An "IssuanceInput" struct.
* "resp": An "IssuanceResponse" struct.
Outputs:
* "tokens": A vector of "RedemptionToken" structs, whose length is
equal to length of the internal "ServerEvaluation" vector in the
"IssuanceResponse" struct.
Celi, et al. Expires 23 August 2021 [Page 13]
Internet-Draft PP protocol February 2021
Throws:
* "ERR_PROOF_VALIDATION" (Section 5.3)
5.2.6. Redeem
Run by the client in the redemption phase of the protocol to generate
the client's message.
Inputs:
* "token": A "RedemptionToken" struct.
* "info": An "opaque<1..2^16-1>" type corresponding to data that is
linked to the redemption. See Section 4.4.1 for advice on how to
construct this.
Outputs:
* "req": A "RedemptionRequest" struct.
5.2.7. Verify
Run by the server in the redemption phase of the protocol.
Determines whether the data sent by the client is valid.
Inputs:
* "pkS": An server "PublicKey".
* "skS": An server "PrivateKey".
* "req": A "RedemptionRequest" struct.
Outputs:
* "resp": A "RedemptionResponse" struct.
5.3. Error types
* "ERR_PROOF_VALIDATION": Error occurred when a client attempted to
verify the proof that is part of the server's response.
* "ERR_DOUBLE_SPEND": Error occurred when a client has attempted to
redeem a token that has already been used for authorization.
Celi, et al. Expires 23 August 2021 [Page 14]
Internet-Draft PP protocol February 2021
* "ERR_FAILED_COMMITMENT": Error occurs during issuance phase if
non-empty commitment does not match the commitment generated in
the first round.
6. Security considerations
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 anonymity of the client in the redemption
phase of the protocol. The notion of unforgeability is to protect
against an adversarial client that may look to subvert the security
of the protocol.
Both requirements are modelled as typical cryptographic security
games, following the formats laid out in [DGSTV18] and [KLOR20].
Note that the privacy requirements of the protocol are covered in the
architectural framework document [draft-davidson-pp-architecture].
6.1. Unlinkability
Formally speaking the security model is the following:
* The adversary runs the server setup and generates a keypair "(pkS,
skS)".
* The adversary specifies a number "Q" of issuance phases to
initiate, where each phase "i in range(Q)" consists of "m_i" Issue
evaluations.
* The adversary runs "Issue" using the keypair that it generated on
each of the client messages in the issuance phase.
* When the adversary wants, it stops the issuance phase, and a
random number "l" is picked from "range(Q)".
* A redemption phase is initiated with a single token with index "i"
randomly sampled from "range(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".
Celi, et al. Expires 23 August 2021 [Page 15]
Internet-Draft PP protocol February 2021
The security requirement is that the adversary has only a negligible
probability of success greater than "1/Q".
6.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 the
issuance phase to redeem "m+1" of them. In essence, this requirement
prevents a malicious client from being able to forge valid tokens
based on the Issue responses that it sees.
The security model roughly takes the following form:
* The adversary specifies a number "Q" of issuance phases to
initiate with the server, where each phase "i in range(Q)"
consists of "m_i" server evaluation. Let "m = sum(m_i)" where "i
in range(Q)".
* The adversary 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.
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.
6.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 server
individually. This prevents clients from "replaying" previous
requests, and is necessary for achieving the unforgeability
requirement.
Celi, et al. Expires 23 August 2021 [Page 16]
Internet-Draft PP protocol February 2021
6.4. Additional token metadata
Some use-cases of the Privacy Pass protocol benefit from associating
a limited amount of metadata with tokens that can be read by the
server when a token is redeemed. Adding metadata to tokens can be
used as a vector to segment the anonymity of the client in the
protocol. Therefore, it is important that any metadata that is added
is heavily limited.
Any additional metadata that can be added to redemption tokens should
be described in the specific protocol instantiation. Note that any
additional metadata will have to be justified in light of the privacy
concerns raised above. For more details on the impacts associated
with segmenting user privacy, see [draft-davidson-pp-architecture].
Any metadata added to tokens will be considered either "public" or
"private". Public metadata corresponds to unmodifiable bits that a
client can read. Private metadata corresponds to unmodifiable
private bits that should be obscured to the client.
Note that the instantiation in Section 7 provides randomized
redemption tokens with no additional metadata for an server with a
single key.
6.5. Maximum number of tokens issued
Servers SHOULD impose a hard ceiling on the number of tokens that can
be issued in a single issuance phase to a client. If there is no
limit, malicious clients could abuse this and cause excessive
computation, leading to a Denial-of-Service attack.
7. VOPRF instantiation
In this section, we show how to instantiate the functional API in
Section 5 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 6, based on the security proofs
provided in [DGSTV18] and [KLOR20].
7.1. Recommended ciphersuites
The RECOMMENDED server ciphersuites are as follows: detailed in
[I-D.irtf-cfrg-voprf]:
* OPRF(decaf448, SHA-512) (ID = 0x0002);
* OPRF(P-384, SHA-512) (ID = 0x0004);
Celi, et al. Expires 23 August 2021 [Page 17]
Internet-Draft PP protocol February 2021
* OPRF(P-521, SHA-512) (ID = 0x0005).
We deliberately avoid the usage of smaller ciphersuites (associated
with P-256 and ristretto255) due to the potential to reduce security
to unfavourable levels via static Diffie Hellman attacks. See
[I-D.irtf-cfrg-voprf] for more details.
7.2. Protocol contexts
Note that we must run the verifiable version of the protocol in
[I-D.irtf-cfrg-voprf]. Therefore the "server" takes the role of the
"Server" running in "modeVerifiable". In other words, the "server"
runs "ctxtS = SetupVerifiableServer(suite, skS, pkS)"; where "suite"
is one of the ciphersuites in Section 7.1, "skS" and "pkS" is the
server's secret and public key respectively (generated by calling
"KeyGen"). It returns "ctxtS", which is the Server context.
Likewise, run "ctxtC = SetupVerifiableClient(suite, pkS)" to generate
the Client context.
7.3. Functionality
We instantiate each functions using the API functions in
[I-D.irtf-cfrg-voprf]. Note that we use the framework mentioned in
the document to allow for batching multiple tokens into a single
VOPRF evaluation. For the explicit signatures of each of the
functions, refer to Section 5.
7.3.1. Generate
The generate functionality generates an initial set of tokens and
blinded representation on the client-side. The function also takes
an optional (possibly empty) value for a commitment "com" committed
to by the server.
def Generate(m, com):
tokens = []
blindedTokens = []
for i in range(m):
x = random_bytes()
(token, blindedToken) = Blind(x, com)
tokens[i] = token
blindedTokens[i] = blindedToken
return IssuanceInput {
data: tokens,
req: blindedTokens,
}
Celi, et al. Expires 23 August 2021 [Page 18]
Internet-Draft PP protocol February 2021
7.3.2. Issue
For this functionality, note that we supply multiple tokens in "req"
to "Evaluate". This allows batching a single proof object for
multiple evaluations. While the construction in
[I-D.irtf-cfrg-voprf] only permits a single input, we follow the
advice for providing vectors of inputs.
def Issue(pkS, skS, req):
elements, proof = Evaluate(skS, pkS, req)
return IssuanceResponse {
tokens: elements,
proof: proof,
}
7.3.3. Process
Similarly to "Issue", we follow the advice for providing vectors of
inputs to the "Unblind" function for verifying the batched proof
object.
Process(pkS, input, resp):
unblindedTokens = Unblind(input.data, resp.elements,
input.req, pkS, resp.proof)
redemptionTokens = []
for bt in unblindedTokens:
rt = RedemptionToken { data: input.data, issued: bt }
redemptionTokens[i] = rt
return redemptionTokens
7.3.4. Redeem
def Redeem(token, info):
tag = Finalize(token.data, token.issued, info)
return RedemptionRequest {
data: data,
tag: tag,
info: info,
}
7.3.5. Verify
def Verify(pkS, skS, req):
resp = VerifyFinalize(skS, req.data, req.info, req.tag)
Output RedemptionResponse {
success: resp
}
Celi, et al. Expires 23 August 2021 [Page 19]
Internet-Draft PP protocol February 2021
7.4. Security justification
The protocol devised in Section 4, coupled with the API instantiation
in Section 7.3, are equivalent to the protocol description in
[DGSTV18] and [KLOR20] from a security perspective. In [DGSTV18], it
is proven that this protocol satisfies the security requirements of
unlinkability (Section 6.1) and unforgeability (Section 6.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.
8. Protocol ciphersuites
The ciphersuites that we describe for the Privacy Pass protocol are
derived from the core instantiations of the protocol (such as in
Section 7).
In each of the ciphersuites below, the maximum security provided
corresponds to the maximum difficulty of computing a discrete
logarithm in the group. Note that the actual security level MAY be
lower. See the security considerations in [I-D.irtf-cfrg-voprf] for
examples.
The COMMIT parameter refers to whether the first round of the
issuance phase of the protocol is necessary. When this is false, the
client ignores the first message and uses an empty value for the
commitment parameter to "Generate".
8.1. PP(OPRF2)
* OPRF2 = OPRF(decaf448, SHA-512)
* ID = 0x0001
* COMMIT = false
Celi, et al. Expires 23 August 2021 [Page 20]
Internet-Draft PP protocol February 2021
* Maximum security provided: 224 bits
8.2. PP(OPRF4)
* OPRF4 = OPRF(P-384, SHA-512)
* ID = 0x0002
* COMMIT = false
* Maximum security provided: 192 bits
8.3. PP(OPRF5)
* OPRF5 = OPRF(P-521, SHA-512)
* ID = 0x0003
* COMMIT = false
* Maximum security provided: 256 bits
9. Extensions framework policy
The intention with providing the Privacy Pass API in Section 5 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 7.
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 6. Protocol
extensions MAY put forward new security guarantees if they are
applicable.
Celi, et al. Expires 23 August 2021 [Page 21]
Internet-Draft PP protocol February 2021
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 anonymity that the
extension may introduce.
10. References
10.1. Normative References
[draft-davidson-pp-architecture]
Davidson, A., "Privacy Pass: Architectural Framework",
n.d., <https://github.com/alxdavids/privacy-pass-
ietf/tree/master/drafts/draft-davidson-pp-architecture>.
[draft-svaldez-pp-http-api]
Valdez, S., "Privacy Pass: HTTP API", n.d.,
<https://github.com/alxdavids/privacy-pass-
ietf/tree/master/drafts/draft-davidson-pp-architecture>.
[I-D.irtf-cfrg-voprf]
Davidson, A., Faz-Hernandez, A., Sullivan, N., and C.
Wood, "Oblivious Pseudorandom Functions (OPRFs) using
Prime-Order Groups", Work in Progress, Internet-Draft,
draft-irtf-cfrg-voprf-05, 2 November 2020,
<http://www.ietf.org/internet-drafts/draft-irtf-cfrg-
voprf-05.txt>.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<https://www.rfc-editor.org/info/rfc2119>.
[RFC8446] Rescorla, E., "The Transport Layer Security (TLS) Protocol
Version 1.3", RFC 8446, DOI 10.17487/RFC8446, August 2018,
<https://www.rfc-editor.org/info/rfc8446>.
10.2. Informative References
[Brave] "Brave Rewards", n.d., <https://brave.com/brave-rewards/>.
[DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously",
n.d., <https://petsymposium.org/2018/files/papers/issue3/
popets-2018-0026.pdf>.
[KLOR20] "Anonymous Tokens with Private Metadata Bit", n.d.,
<https://eprint.iacr.org/2020/072>.
Celi, et al. Expires 23 August 2021 [Page 22]
Internet-Draft PP protocol February 2021
[OpenPrivacy]
"Token Based Services - Differences from PrivacyPass",
n.d., <https://openprivacy.ca/assets/towards-anonymous-
prepaid-services.pdf>.
[PrivateStorage]
Steininger, L., "The Path from S4 to PrivateStorage",
n.d., <https://medium.com/least-authority/the-path-from-
s4-to-privatestorage-ae9d4a10b2ae>.
[RFC7049] Bormann, C. and P. Hoffman, "Concise Binary Object
Representation (CBOR)", RFC 7049, DOI 10.17487/RFC7049,
October 2013, <https://www.rfc-editor.org/info/rfc7049>.
[RFC7159] Bray, T., Ed., "The JavaScript Object Notation (JSON) Data
Interchange Format", RFC 7159, DOI 10.17487/RFC7159, March
2014, <https://www.rfc-editor.org/info/rfc7159>.
[TrustTokenAPI]
WICG, ., "Trust Token API", n.d.,
<https://github.com/WICG/trust-token-api>.
Appendix A. Document contributors
* Alex Davidson (alex.davidson92@gmail.com)
* Sofia Celi (cherenkov@riseup.net)
* Christopher Wood (caw@heapingbits.net)
Authors' Addresses
SofĂa Celi
Cloudflare
Lisbon
Portugal
Email: sceli@cloudflare.com
Alex Davidson
LIP
Lisbon
Portugal
Email: alex.davidson92@gmail.com
Celi, et al. Expires 23 August 2021 [Page 23]
Internet-Draft PP protocol February 2021
Armando Faz-Hernandez
Cloudflare
101 Townsend St
San Francisco,
United States of America
Email: armfazh@cloudflare.com
Celi, et al. Expires 23 August 2021 [Page 24]