Internet DRAFT - draft-privacy-pass
draft-privacy-pass
Network Working Group A. Davidson
Internet-Draft Cloudflare Portugal
Intended status: Informational N. Sullivan
Expires: May 6, 2020 Cloudflare
November 03, 2019
The Privacy Pass Protocol
draft-privacy-pass-00
Abstract
This document specifies the Privacy Pass protocol for anonymously
authorizing clients with services on the Internet.
Note to Readers
Source for this draft and an issue tracker can be found at
https://github.com/grittygrease/draft-privacy-pass [1].
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 May 6, 2020.
Copyright Notice
Copyright (c) 2019 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
Davidson & Sullivan Expires May 6, 2020 [Page 1]
Internet-Draft PP protocol November 2019
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
1.1. Terminology . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Preliminaries . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1. Elliptic curve points . . . . . . . . . . . . . . . . 4
1.2.2. Protocol messages . . . . . . . . . . . . . . . . . . 4
1.3. Layout . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4. Requirements . . . . . . . . . . . . . . . . . . . . . . 5
2. Generalized protocol overview . . . . . . . . . . . . . . . . 5
2.1. Key initialisation phase . . . . . . . . . . . . . . . . 6
2.2. Issuance phase . . . . . . . . . . . . . . . . . . . . . 8
2.3. Redemption phase . . . . . . . . . . . . . . . . . . . . 9
2.3.1. Double-spend protection . . . . . . . . . . . . . . . 10
2.3.2. Finalization during redemption . . . . . . . . . . . 11
2.4. Error types . . . . . . . . . . . . . . . . . . . . . . . 11
3. Key registration . . . . . . . . . . . . . . . . . . . . . . 11
3.1. Key rotation . . . . . . . . . . . . . . . . . . . . . . 12
3.2. Client retrieval . . . . . . . . . . . . . . . . . . . . 13
3.3. Key revocation . . . . . . . . . . . . . . . . . . . . . 14
3.4. VOPRF ciphersuites . . . . . . . . . . . . . . . . . . . 14
3.5. ECDSA key material . . . . . . . . . . . . . . . . . . . 15
4. Protocol configurations . . . . . . . . . . . . . . . . . . . 15
4.1. Single-Issuer Single-Verifier . . . . . . . . . . . . . . 15
4.2. Single-Issuer Forwarding-Verifier . . . . . . . . . . . . 16
4.3. Single-Issue Asynchronous-Verifier . . . . . . . . . . . 16
4.4. Bounded-Issuers . . . . . . . . . . . . . . . . . . . . . 17
4.4.1. Fixing the bound . . . . . . . . . . . . . . . . . . 17
5. Privacy considerations . . . . . . . . . . . . . . . . . . . 17
5.1. User segregation . . . . . . . . . . . . . . . . . . . . 18
5.1.1. Key rotation . . . . . . . . . . . . . . . . . . . . 18
5.1.2. Large numbers of issuers . . . . . . . . . . . . . . 18
5.2. Tracking and identity leakage . . . . . . . . . . . . . . 20
6. Security considerations . . . . . . . . . . . . . . . . . . . 20
6.1. Double-spend protection . . . . . . . . . . . . . . . . . 20
6.2. Key rotation . . . . . . . . . . . . . . . . . . . . . . 20
6.3. Token exhaustion . . . . . . . . . . . . . . . . . . . . 21
7. Summary of privacy and security parameters . . . . . . . . . 21
7.1. Justification . . . . . . . . . . . . . . . . . . . . . . 22
7.2. Example parameterization . . . . . . . . . . . . . . . . 23
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 23
8.1. Normative References . . . . . . . . . . . . . . . . . . 23
8.2. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 24
Davidson & Sullivan Expires May 6, 2020 [Page 2]
Internet-Draft PP protocol November 2019
1. Introduction
In some situations, it may only be necessary to check that a client
has been previously authorized by a service; without learning any
other information. Such lightweight authorization mechanisms can be
useful in quickly assessing the reputation of a client in latency-
sensitive communication.
The Privacy Pass protocol was initially introduced as a mechanism for
authorizing clients that had already been authorized in the past,
without compromizing their privacy [DGSTV18]. This document seeks to
standardize the usage and parametrization of the protocol.
The Internet performance company Cloudflare has already implemented
server-side support for an initial version of the Privacy Pass
protocol [PPSRV]. This support allows clients to bypass security
mechanisms, providing that they have successfully passed these
mechanisms previously. There is also a client-side implementation in
the form of a browser extension that interacts with the Cloudflare
network [PPEXT].
The main security requirement of the Privacy Pass protocol is to
ensure that previously authenticated clients do not reveal their
identity on reauthorization. The protocol uses a cryptographic
primitive known as a verifiable oblivious pseudorandom function
(VOPRF) for implementing the authorization mechanism. The VOPRF is
implemented using elliptic curves and is currently in a separate
standardization process [OPRF]. The protocol is split into three
stages. The first two stages, initialisation and evaluation, are
essentially equivalent to the VOPRF setup and evaluation phases from
[OPRF]. The final stage, redemption, essentially amounts to
revealing the client's secret inputs in the VOPRF protocol. The
security (pseudorandomness) of the VOPRF protocol means that the
client retains their privacy even after revealing this data.
In this document, we will give a formal specification of the Privacy
Pass protocol to be used in settings that require high performance.
We will specify the necessary cryptographic operations required by
the underlying VOPRF, along with recommendations on how to perform
key rotation
1.1. Terminology
The following terms are used throughout this document.
o PRF: Pseudorandom function
o VOPRF: Verifiable oblivious PRF [OPRF]
Davidson & Sullivan Expires May 6, 2020 [Page 3]
Internet-Draft PP protocol November 2019
o Server: A service that provides access to a certain resource
(typically denoted S)
o Client: An entity that seeks authorization from a server
(typically denoted C)
o Key: Server VOPRF key
o Commitment: Corresponding public key to server's VOPRF key.
1.2. Preliminaries
Throughout this draft, let D be some object corresponding to an
opaque data type (such as a group element). We write bytes(D) to
denote the encoding of this data type as raw bytes (octet strings).
We assume that such objects can also be interpreted as Buffer
objects, with each internal slot in the buffer set to the value of
the one of the bytes. For two objects x and y, we denote the
concatenation of the bytes of these objects by (bytes(x) ..
bytes(y)). We assume that all bytes are first base64-encoded before
they are sent as part of a protocol message.
We use the notation "[ Ti ]" to indicate an array of objects T1, ...
, TQ where the size of the array is Q, and the size of Q is implicit
from context.
1.2.1. Elliptic curve points
When encoding elliptic curve points into existing data structures or
into protocol messages, we assume that the curve points are first
encoded into bytes. We allow both uncompressed and compressed
encodings, as long as the client and server are aligned on the
encodings that they used. Compressed encodings provide storage and
communication benefits but are slightly more expensive to decode.
1.2.2. Protocol messages
Protocol messages can either be encoded in raw byte format, as
base64-encoded string objects, or as JSON objects where all strings
are represented in base64-encoded format.
1.3. Layout
o Section 2: A generic overview of the Privacy Pass protocol based
on VOPRFs.
Davidson & Sullivan Expires May 6, 2020 [Page 4]
Internet-Draft PP protocol November 2019
o Section 3: Describes the format of trusted registries that are
used for holding public key commitments for each of the Privacy
Pass issuers.
o Section 4: Details different configurations for using the Privacy
Pass protocol.
o Section 5: Privacy considerations and recommendations arising from
the usage of the Privacy Pass protocol.
o Section 6: Additional security considerations to prevent abuse of
the protocol from a malicious client.
o Section 7: A summary of recommended parameter settings for
ensuring privacy and security features of the protocol.
1.4. Requirements
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].
2. Generalized protocol overview
In this document, we will be assuming that a client (C) is attempting
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.
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. As we mentioned previously, the first two stages are
essentially identical to the setup and evaluation phases of the VOPRF
in [OPRF]. The last stage, redemption, corresponds to the client
revealing their secret input data during the VOPRF protocol to the
server. The server can use this data to confirm that the client has
a valid VOPRF output, without being able to link the data to any
individual issuance phase.
Throughout this document, we adhere to the recommendations laid out
in [OPRF] in integrating the VOPRF protocol into our wider workflow.
Where necessary, we lay out exactly which part of the VOPRF API we
use. We stress that the generalized protocol only includes steps and
messages that contain cryptographic data.
Davidson & Sullivan Expires May 6, 2020 [Page 5]
Internet-Draft PP protocol November 2019
We decide against defining abstract interfaces for enclosing Privacy
Pass data and functionality. Instead, we describe the Privacy Pass
protocol in the same group setting that is used in [OPRF].
2.1. Key initialisation phase
In the initialisation phase, essentially we run the VOPRF setup phase
in that the server runs VOPRF_Setup(l) where l is the required bit-
length of the prime used in establishing the order of the group GG.
This outputs the tuple (k,Y,p) where: p = p(l) is the prime order of
GG = GG(l); k is a uniformly sampled element from GF(p); and Y = kG
for some fixed generator of GG.
However, the server must first come to an agreement on what group
instantiation to support. This involves choosing an instantiation
with the required security level implied by the choice of l. The
server has a list of supported group params (GROUP_PARAMS) and
chooses an identifier, id, associated with the preferred group
configuration, and also outputs the implied length of l. It creates
a Privacy Pass key object denoted by ppKey that has fields "private",
"public" and "group". It sets ppKey.private = bytes(k), ppKey.public
= bytes(Y) and ppKey.group = id.
The server creates a JSON object of the form below.
{
"Y": pp_key.public,
"expiry": <expiry_date>,
"sig": <signature>
}
The field "expiry" corresponds to an expiry date for the newly
sampled key. We recommend that each key has a lifetime of between 1
month and 6 months. The field "sig" holds an ASN1-encoded ECDSA
signature evaluated over the contents of "Y" and "expiry". The ECDSA
parameters should be equivalent to the group instantiation used for
the OPRF, and the signing key (ecdsaSK) should be long-term with a
corresponding publicly available verification key (ecdsaVK). We
summarize the creation of this object using the algorithm
PP_key_init(), which we define below.
Davidson & Sullivan Expires May 6, 2020 [Page 6]
Internet-Draft PP protocol November 2019
function PP_key_init(k, Y, id) {
var ppKey = {}
ppKey.private = k
ppKey.public = Y
ppKey.group = id
var today = new Date()
var expiry = today.setMonth(today.getMonth() + n);
var obj = {
Y: ppKey.public,
expiry: expiry,
sig: ECDSA.sign(ecdsaSK, ppKey.public .. bytes(expiry)),
}
return [ppKey, obj]
}
Note that the variable n above should correspond to the number of
months ahead that the expiry date should correspond to.
We give a diagrammatic representation of the initialisation phase
below.
C(ecdsaVK) S(ecdsaSK)
----------------------------------------------------------------------
l = GROUP_PARAMS[id]
(k,Y,p) = VOPRF_Setup(l)
[ppKey,obj] = PP_key_init(k,Y,id)
obj
<-------------------
public = key.Y
if (!ECDSA.verify(ecdsaVK, public .. bytes(obj.expiry)) {
panic(KEY_VERIFICATION_ERROR)
} else if (!(new Date() > obj.expiry)) {
panic(KEY_VERIFICATION_ERROR)
}
store(obj.id, obj.public) push(key)
The variable obj essentially corresponds to a cryptographic
commitment to the server's VOPRF key. We abstract all signing and
verification of ECDSA signatures into the ECDSA.sign and ECDSA.verify
functionality [DSS].
In the initialisation phase above, we require that the server
contacts each viable client. In Section 3 we discuss the possibility
of uploading public key material to a trusted registry that client's
access when communicating with the server.
Davidson & Sullivan Expires May 6, 2020 [Page 7]
Internet-Draft PP protocol November 2019
2.2. Issuance phase
The issuance phase allows the client to receive VOPRF evaluations
from the server. The issuance phase essentially corresponds to a
VOPRF evaluation phase [OPRF]. In essence, the client generates a
valid VOPRF input x (a sequence of bytes from some unpredictable
distribution), and runs the VOPRF evaluation phase with the server.
The client receives an output y of the form:
y = VOPRF_Finalize(x, N, aux)
where N is a group element, and aux is auxiliary data that is
generated by the client. More specifically, N is an unblinded group
element equal to k*H_1(x) where H_1 is a random oracle that outputs
elements in GG. The client stores (x, y) as recommended in [OPRF].
We give a diagrammatic overview of the protocol below.
Davidson & Sullivan Expires May 6, 2020 [Page 8]
Internet-Draft PP protocol November 2019
C(x, aux) S(ppKey)
----------------------------------------------------------------------
var ciph = retrieve(S.id)
var (r,M) = VOPRF_Blind(x)
M
------------------->
(Z,D) = VOPRF_Eval(ppKey.private,
ciph.G,Y,M)
var resp = {
element: Z,
proof: D,
version: "key_version",
}
resp
<------------------
var elt = resp.element
var proof = resp.proof
var version = resp.version
var obj = retrieve(S.id, version)
if obj == "error" {
panic(KEY_VERIFICATION_ERROR)
}
var N = VOPRF_Unblind(ciph.G,obj.Y,M,elt,proof)
var y = VOPRF_Finalize(x,N,aux)
if (y == "error") {
panic(CLIENT_VERIFICATION_ERROR)
}
push((ciph,x,y,aux))
In the diagram above, the client knows the VOPRF ciphersuite
supported by the server when it retrieves in the first step. It uses
this information to correctly perform group operations before sending
the first message.
2.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. By the security of the VOPRF, even revealing the original
input x that is used in the issuance phase does not affect the
privacy of the client.
Davidson & Sullivan Expires May 6, 2020 [Page 9]
Internet-Draft PP protocol November 2019
C() S(ppKey)
----------------------------------------------------------------------
ciph1 = retrieve(S.id, "ciphersuite")
a = pop()
while (a != undefined) {
(ciph2,x,y,aux) = a
if (ciph1 != ciph2) {
// ciphersuites do not match
a = pop()
continue
}
}
if (a == undefined) {
// no valid data to redeem
return
}
(x,y,aux)
-------------------->
if (store.includes(x)) {
panic(DOUBLE_SPEND_ERROR)
}
T = H1(x)
N' = OPRF_Eval(ppKey.private, T)
y' = OPRF_Finalize(x,N',aux)
resp = (y' == y)
? "success"
: "failure"
store.push(x)
resp
<--------------------
output resp
Note that the server uses the API provided by OPRF_Eval and
OPRF_Finalize, rather than the corresponding VOPRF functions. This
is because the VOPRF functions also compute zero-knowledge proof data
that we do not require at this stage of the protocol.
2.3.1. Double-spend protection
To protect against clients that attempt to spend a value x more than
once, the server uses an index, store, 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
Davidson & Sullivan Expires May 6, 2020 [Page 10]
Internet-Draft PP protocol November 2019
storage after a key rotation occurs since all previous client data
will be rendered obsolete after such an event.
2.3.2. Finalization during redemption
The last step if the issuance phase for the client is to run
VOPRF_Finalize and store the output. In some applications, it may be
necessary to link the output of VOPRF_Finalize to the actual
redemption that is occurring. This can be done by tailoring the
auxiliary data "aux" to something specific.
In order to do this, it is necessary to store only (ciph, x, N) in
the issuance phase of the protocol. Then during the redemption
phase, generate auxiliary data "aux" and compute
VOPRF_Finalize(x,N,aux) after retrieving the triplet above.
2.4. Error types
o KEY_VERIFICATION_ERROR: Error occurred when verifying signature
and expiry date for a server public key
o CLIENT_VERIFICATION_ERROR: Error verifying issuance response from
server.
o DOUBLE_SPEND_ERROR: Indicates that a client has attempted to
redeem a token that has already been used for authorization
3. Key registration
Rather than sending the result of the key initialisation procedure
directly to each client, it is preferable to upload the object obj to
a trusted, tamper-proof, history-preserving registry. By trusted, we
mean from the perspective of clients that use the Privacy Pass
protocol. Any new keys uploaded to the registry should be appended
to the list. Any keys that have expired can optionally be labelled
as so, but should never be removed. A trusted registry may hold key
commitments for multiple Privacy Pass service providers (servers).
Clients can either choose to:
o poll the trusted registry and import new keys, rejecting any that
throw errors;
o retrieve the commitments for the server at the time at which they
are used, throwing errors if no valid commitment is available.
To prevent unauthorized modification of the trusted registry,
server's should be required to identify and authenticate themselves
Davidson & Sullivan Expires May 6, 2020 [Page 11]
Internet-Draft PP protocol November 2019
before they can append data to their configuration. Moreover, only
parts of the registry that correspond to the servers configuration
can be modifiable.
The registry that we describe could be fulfilled by Key Transparency
[keytrans] or other similar architectures.
3.1. Key rotation
Whenever a server seeks to rotate their key, they must append their
key to the trusted registry. We recommend that the trusted registry
is arranged as a JSON blob with a member for each JSON provider.
Each provider appends new keys by creating a new sub-member
corresponding to an incremented version label along with their new
commitment object.
Concretely, we recommend that the trusted registry is a JSON file of
the form below.
{
"server_1": {
"ciphersuite": ...,
"1.0": {
"Y": ...,
"expiry": ...,
"sig": ...,
},
"1.1": {
"Y": ...,
"expiry": ...,
"sig": ...,
},
}
"server_2": {
"ciphersuite": ...,
"1.0": {
"Y": ...,
"expiry": ...,
"sig": ...,
},
},
...
}
In this structure, "server_1" and "server_2" are separate service
providers. The sub-member "ciphersuite" corresponds to the choice of
VOPRF ciphersuite made by the server. The sub-members "1.0", "1.1"
of "server_1" correspond to the versions of commitments available to
Davidson & Sullivan Expires May 6, 2020 [Page 12]
Internet-Draft PP protocol November 2019
the client. Increasing version numbers should correspond to newer
keys. Each commitment should be a valid encoding of a point
corresponding to the group in the VOPRF ciphersuite specified in
"ciphersuite".
If "server_2" wants to upload a new commitment with version tag
"1.1", it runs the key initialisation procedure from above and adds a
new sub-member "1.1" with the value set to the value of the output
obj. The "server_2" member should now take the form below.
{
...
"server_2": {
"ciphersuite": ...,
"1.0": {
"Y": ...,
"expiry": ...,
"sig": ...,
},
"1.1": {
"Y": ...,
"expiry": ...,
"sig": ...,
},
},
...
}
3.2. Client retrieval
We define a function "retrieve(server_id, version_id)" which
retrieves the commitment with version label equal to version_id, for
the provider denoted by the string server_id. For example,
retrieve("server_1","1.1") will retrieve the member labelled with
"1.1" above.
We implicitly assume that this function performs the following
verification checks:
if (!ECDSA.verify(ecdsaVK, obj.Y .. bytes(obj.expiry)) {
return "error"
} else if (!(new Date() < obj.expiry)) {
return "error"
}
If "error" is not returned, then it instead returns the entire
object. We also abuse notation and also use "ciph =
Davidson & Sullivan Expires May 6, 2020 [Page 13]
Internet-Draft PP protocol November 2019
retrieve(server_id, "ciphersuite")" to refer to retrieving the
ciphersuite for the server configuration.
3.3. Key revocation
If a server must revoke a key, then it uses a separate member with
label "revoke" corresponding to an array of revoke versions
associated with key commitments. In the above example, if "server_2"
needs to revoke the key with version "1.0", then it appends a new
"revoke" member with the array "[ "1.0" ]". Any future revocations
can simply be appended to this array. For an example, see below.
{
...
"server_2": {
"ciphersuite": ...,
"1.0": {
"Y": ...,
"expiry": ...,
"sig": ...,
},
"1.1": {
"Y": ...,
"expiry": ...,
"sig": ...,
},
"revoked": [ "1.0" ],
},
...
}
Client's are required to check the "revoked" member for new additions
when they poll the trusted registry for new key data.
3.4. VOPRF ciphersuites
We strongly RECOMMEND that a server uses only one VOPRF ciphersuite
at any one time. Should a server choose to change some aspect of the
ciphersuite (e.g., the group instantiation or other cryptographic
functionality) we further RECOMMEND that the server create a new
identifying label (e.g. "server_1_${ciphersuite_id}") where
ciphersuite_id corresponds to the identifier of the VOPRF
ciphersuite. Then "server_1" revokes all keys for the previous
ciphersuite and then only offers commitments for the current label.
An alternative arrangement would be to add a new layer of members
between server identifiers and key versions in the JSON struct,
Davidson & Sullivan Expires May 6, 2020 [Page 14]
Internet-Draft PP protocol November 2019
corresponding to "ciphersuite_id". Then the client may choose
commitments from the appropriate group identifying member.
We strongly recommend that service providers only operate with one
group instantiation at any one time. If a server uses two VOPRF
ciphersuites at any one time then this may become an avenue for
segregating the user-base. User segregation can lead to privacy
concerns relating to the utility of the obliviousness of the VOPRF
protocol (as raised in [OPRF]). We discuss this more in Section 5.
3.5. ECDSA key material
For clients must also know the verification (ecdsaVK) for each
service provider that they support. This enables the client to
verify that the commitment is properly formed before it uses it. We
do not provide any specific recommendations on how the client has
access to this key, beyond that the verification key should be
accessible separately from the trusted registry.
While the number of service providers associated with Privacy Pass is
low, the client can simply hardcode the verification keys directly
for each provider that they support. This may be cumbersome if a
provider wants to rotate their signing key, but since these keys
should be comparatively long-term (relative to the VOPRF key
schedule), then this should not be too much of an issue.
4. Protocol configurations
We provide an overview of some of the possible ways of configuring
the Privacy Pass protocol situation, such that it can be used as a
lightweight trust attestation mechanism for clients.
4.1. Single-Issuer Single-Verifier
The simplest way of considering the Privacy Pass protocol is in a
setting where the same server plays the role of issuer and verifier,
we call this "Single-Issuer Single-Verifier" (SISV). In SISV, we
consider a server S that publishes commitments for their secret key
k, that a client C has access to.
When S wants to issue tokens to C, they invoke the issuance protocol
where C generates their own inputs and S uses their secret key k. In
this setting, C can only perform token redemption with S. When a
token redemption is required, C and S invoke the redemption phase of
the protocol, where C uses an issued token from a previous exchange,
and S uses k as their input again.
Davidson & Sullivan Expires May 6, 2020 [Page 15]
Internet-Draft PP protocol November 2019
In SISV, C proves that S has attested to the honesty of C at some
point in the past (without revealing exactly when). S can use this
information to inform it's own decision-making about C without having
to recompute the trust attestation task again.
4.2. Single-Issuer Forwarding-Verifier
In this setting, each client C obtains issued tokens from a server S
via the issuance phase of the protocol. The difference is that
clients can prove that S has attested to their honesty in the past
with any verifier V. We still only consider S to hold their own
secret key.
When C interacts with V, V can ask C to provide proof that the
separate issuer S has attested to their trust. The first stage of
the redemption phase of the protocol is invoked between C and V,
which sees C send the unused token (x,y,aux) to V. This message is
then used in a redemption exchange between V and S, where V plays the
role of the client. Then S sends the result of the redemption
exchange to V, and V uses this result to determine whether C has the
correct trust attestation.
This configuration is known as "Single-Issuer Forwarding-Verifier" or
SIFV to refer to the verifier V who uses the output of the redemption
phase for their own decision-making.
4.3. Single-Issue Asynchronous-Verifier
This setting is inspired by recently proposed APIs such as [TRUST].
It is similar to the SIFV configuration, except that the verifiers V
no longer interact with the issuer S. Only C interacts with S, and
this is done asynchronously to the trust attestation request from V.
Hence "Asynchronous-Verifier" (SIAV).
When V invokes a redemption for C, C then invokes a redemption
exchange with S in a separate session. If verification is carried
out successfully by S, S instead returns a Signed Redemption Record
(SRR) that contains the following information:
"result": {
"timestamp":"2019-10-09-11:06:11",
"verifier": "V",
},
"signature":sig,
The "signature" field carries a signature evaluated over the contents
of "result" using a long-term signing key for the issuer S, of which
the corresponding public key is well-known to C and V. Then C can
Davidson & Sullivan Expires May 6, 2020 [Page 16]
Internet-Draft PP protocol November 2019
prove that their trust attestation from S to V by sending the SRR to
V. The SRR can be verified by V by verifying the signature using the
well-known public key for S.
Such records can be cached to display again in the future. The
issuer can also add an expiry date to the record to determine when
the client must refresh the record.
4.4. Bounded-Issuers
Each of the configurations above can be generalized to settings where
a bounded number of issuers are allowed, and verifiers can invoke
trust attestations for any of the available issuers. Subsequently,
this leads to three new configurations known as BISV, BIFV, BIAV.
As we will discuss later in Section 5.1.2, configuring a large number
of issuers can lead to privacy concerns for the clients in the
ecosystem. Therefore, we are careful to ensure that the number of
issuers is kept strictly bounded by a fixed small number M. The
actual issuers can be replaced with different issuers as long as the
total never exceeds M. Moreover, issuer replacements also have an
effect on client privacy that is similar to when a key rotation
occurs, so replacement should only be permitted at similar intervals.
See Section 5.1.2 for more details about safe choices of M.
4.4.1. Fixing the bound
Configuring any number of issuers greater than 1 effectively reduces
privacy by an extra bit. As a result, we see an exponential decrease
in privacy in the number of issuers that are currently active.
Therefore the value of M should be kept very low (we recommend no
higher than 4).
5. Privacy considerations
We intentionally encode no special information into redemption tokens
to prevent a vendor from learning anything about the client. We also
have cryptographic guarantees via the VOPRF construction that a
vendor can learn nothing about a client beyond which issuers trust
it. Still there are ways that malicious servers can try and learn
identifying information about clients that it interacts with.
We discuss a number of privacy considerations made in [OPRF] that are
relevant to the Privacy Pass protocol use-case, along with additional
considerations arising from the specific ways of using the Privacy
Pass protocol in Section 4.
Davidson & Sullivan Expires May 6, 2020 [Page 17]
Internet-Draft PP protocol November 2019
5.1. User segregation
An inherent features of using cryptographic primitives like VOPRFs is
that any client can only remain private relative to the entire space
of users using the protocol. In principle, we would hope that the
server can link any client redemption to any specific issuance
invocation with a probability that is equivalent to guessing.
However, in practice, the server can increase this probability using
a number of techniques that can segregate the user space into smaller
sets.
5.1.1. Key rotation
As introduced in [OPRF], such techniques to introduce segregation are
closely linked to the type of key schedule used by the server. When
a server rotates their key, any client that invokes the issuance
protocol shortly afterwards will be part of a small number of
possible clients that can redeem. To mechanize this attack strategy,
a server could introduce a fast key rotation policy which would force
clients into small key windows. This would mean that client privacy
would only have utility with respect to the smaller group of users
that have Trust Tokens for a particular key window.
In the [OPRF] draft it is recommended that great care is taken over
key rotations, in particular server's should only invoke key rotation
for fairly large periods of time such as between 1 and 12 months.
Key rotations represent a trade-off between client privacy and
continued server security. Therefore, it is still important that key
rotations occur on a fairly regular cycle to reduce the harmfulness
of a server key compromise.
Trusted registries for holding Privacy Pass key commitments can be
useful in policing the key schedule that a server uses. Each key
must have a corresponding commitment in this registry so that clients
can verify issuance responses from servers. Clients may choose to
inspect the history of the registry before first accepting redemption
tokens from the server. If a server has updated the registry with
many unexpired keys, or in very quick intervals a client can choose
to reject the tokens.
TODO: Can client's flag bad server practices?
5.1.2. Large numbers of issuers
Similarly to the key rotation issue raised above, if there are a
large number of issuers, similar user segregation can occur. In the
BISV, BIFV, BIAV configurations of using the Privacy Pass protocol
(Section 4), a verifier OV can trigger redemptions for any of the
Davidson & Sullivan Expires May 6, 2020 [Page 18]
Internet-Draft PP protocol November 2019
available issuers. Each redemption token that a client holds
essentially corresponds to a bit of information about the client that
OV can learn. Therefore, there is an exponential loss in privacy
relative to the number of issuers that there are.
For example, if there are 32 issuers, then OV learns 32 bits of
information about the client. If the distribution of issuer trust is
anything close to a uniform distribution, then this is likely to
uniquely identify any client amongst all other Internet users.
Assuming a uniform distribution is clearly the worst-case scenario,
and unlikely to be accurate, but it provides a stark warning against
allowing too many issuers at any one time.
As we noted in Section 4.4, a strict bound should be applied to the
active number of issuers that are allowed at one time. We propose
that allowing no more than 6 issuers at any one time is highly
preferable (leading to a maximum of 64 possible user segregations).
Issuer replacements should only occur with the same frequency as key
rotations as they can lead to similar losses in privacy if users
still hold redemption tokens for previously active issuers.
In addition, we recommend that trusted registries indicate at all
times which issuers are deemed to be active. If a client is asked to
invoke any Privacy Pass exchange for an issuer that is not declared
active, then the client should refuse to participate in the protocol.
5.1.2.1. Selected trusted registries
One recommendation is that only a fixed number (TODO: how many?) of
issuers are sanctioned to provide redemption tokens at any one time.
This could be enforced by the trusted registry that is being used.
Client's can then choose which registries to trust and only accept
redemption tokens from issuers accepted into those registries.
5.1.2.2. Maximum number of issuers inferred by client
A second recommendation is that clients only store redemption tokens
for a fixed number of issuers at any one time. This would prevent a
malicious verifier from being able to invoke redemptions for many
issuers since the client would only be holding redemption tokens for
a small set of issuers. When a client is issued tokens from a new
issuer and already has tokens from the maximum number of issuers, it
simply deletes the oldest set of redemption tokens in storage and
then stores the newly acquired tokens.
Davidson & Sullivan Expires May 6, 2020 [Page 19]
Internet-Draft PP protocol November 2019
5.2. Tracking and identity leakage
While redemption tokens themselves encode no information about the
client redeeming them, there may be problems if we allow too many
redemptions on a single page. For instance, the first-party cookie
for user U on domain A can be encoded in the trust token information
channel and decoded on domain B, allowing domain B to learn the
user's domain A cookie until either first-party cookie is cleared.
Mitigations for this issue are similar to those proposed in
Section 5.1.2 for tackling the problem of having large number of
issuers.
In SIAV, cached SRRs and their associated issuer public keys have a
similar tracking potential to first party cookies in the browser
setting. Therefore these should be clearable by the client using
standard deletion methods.
6. Security considerations
We present a number of security considerations that prevent a
malicious actors from abusing the protocol.
6.1. Double-spend protection
All issuing server should implement a robust 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.
But all issuers must perform global double-spend checks to avoid
clients from exploiting the possibility of spending tokens more than
once against distributed token checking systems. For the same
reason, the global data storage must have quick update times. While
an update is occurring it may be possible for a malicious client to
spend a token more than once.
6.2. Key rotation
We highlighted previously that short key-cycles can be used to reduce
client privacy. However, regular key rotations are still recommended
to maintain good server key hygiene. The key material that we
consider to be important are:
o the VOPRF key;
o the signing key used to sign commitment information;
o the signing key used to sign SRRs in the SIAV configuration.
Davidson & Sullivan Expires May 6, 2020 [Page 20]
Internet-Draft PP protocol November 2019
In summary, our recommendations are that VOPRF keys are rotated from
anywhere between a month and a single year. With an active user-
base, a month gives a fairly large window for clients to participate
in the Privacy Pass protocol and thus enjoy the privacy guarantees of
being part of a larger group. The low ceiling of a year prevents a
key compromise from being too destructive. If a server realizes that
a key compromise has occurred then the server should revoke the
previous key in the trusted registry and specify a new key to be
used.
For the two signing keys, these should both be well-known keys
associated with the issuer (TODO: where should they be stored?).
Issuers may choose to use the same key for both signing purposes.
The rotation schedules for these keys can be much longer, if
necessary.
6.3. Token exhaustion
When a client holds tokens for an issuer, it is possible for any
verifier to invoke that client to redeem tokens for that issuer.
This can lead to an attack where a malicious verifier can force a
client to spend all of their tokens for a given issuer. To prevent
this from happening, methods should be put into place to prevent many
tokens from being redeemed at once.
For example, it may be possible to cache a redemption for the entity
that is invoking a token redemption. In SISV/SIFV, if the verifier
requests more tokens then the client simply returns the cached token
that it returned previously. This could also be handled by simply
not redeeming any tokens for the entity if a redemption had already
occurred in a given time window.
In SIAV, the client instead caches the SRR that it received in the
asynchronous redemption exchange with the issuer. If the same
verifier attempts another trust attestation request, then the client
simply returns the cached SRR. The SRRs can be revoked by the
issuer, if need be, by providing an expiry date or by signaling that
records from a particular window need to be refreshed.
7. Summary of privacy and security parameters
We provide a summary of the parameters that we use in the Privacy
Pass protocol. These parameters are informed by both privacy and
security considerations that are highlighted in Section 5 and
Section 6, respectively. These parameters are intended as a single
reference point for implementers when implementing the protocol.
Davidson & Sullivan Expires May 6, 2020 [Page 21]
Internet-Draft PP protocol November 2019
Firstly, let U be the total number of users, I be the total number of
issuers. Assuming that each user accept tokens from a uniform
sampling of all the possible issuers, as a worst-case analysis, this
segregates users into a total of 2^I buckets. As such, we see an
exponential reduction in the size of the anonymity set for any given
user. This allows us to specify the privacy constraints of the
protocol below, relative to the setting of A.
+----------------------------------------+--------------+
| parameter | value |
+----------------------------------------+--------------+
| Minimum anonymity set size (A) | 5000 |
| | |
| Recommended key lifetime (L) | 1 - 6 months |
| | |
| Recommended key rotation frequency (F) | L/2 |
| | |
| Maximum allowed issuers (I) | log_2(U/A)-1 |
| | |
| Maximum active issuance keys | 1 |
| | |
| Maximum active redemption keys | 2 |
| | |
| Minimum security parameter | 196 bits |
+----------------------------------------+--------------+
7.1. Justification
We make the following assumptions in these parameter choices.
o Inferring the identity of a user in a 5000-strong anonymity set is
difficult
o After 2 weeks, all clients in a system will have rotated to the
new key
The maximum choice of I is based on the equation 1/2 * U/2^I = A.
This is because I issuers lead to 2^I segregations of the total user-
base U. By reducing I we limit the possibility of performing the
attacks mentioned in Section 5.1.
We must also account for each user holding issued data for more then
one possible active keys. While this may also be a vector for
monitoring the access patterns of clients, it is likely to
unavoidable that clients hold valid issuance data for the previous
key epoch. This also means that the server can continue to verify
redemption data for a previously used key. This makes the rotation
period much smoother for clients.
Davidson & Sullivan Expires May 6, 2020 [Page 22]
Internet-Draft PP protocol November 2019
For privacy reasons, it is recommended that key epochs are chosen
that limit clients to holding issuance data for a maximum of two
keys. By choosing F = L/2 then the minimum value of F is 1/2 a
month, since the minimum recommended value of L is 1 month.
Therefore, by the initial assumption, then all users should only have
access to only two keys at any given time. This reduces the
anonymity set by another half at most.
Finally, the minimum security parameter size is related to the
cryptographic security offered by the group instantiation that is
chosen. For example, if we use an elliptic curve over a 256-bit
prime field, then the actual group instantiation offers 128 bits of
security (or a security parameter of size 128 bits). However, as
noted in [OPRF], OPRF protocols reduce the effective security of the
group by log_2(M) where M is the number of queries. As such, we
choose the minimum size of the security parameter to be 196 bits, so
that it is difficult for a malicious client to exploit this.
7.2. Example parameterization
Using the specification above, we can give some example
parameterizations. For example, the current Privacy Pass browser
extension [PPEXT] has over 150,000 active users (from Chrome and
Firefox). Then log_2(U/A) is approximately 5 and so the maximum
value of I should be 4.
If the value of U is much bigger (e.g. 5 million) then this would
permit I = log_2(5000000/5000)-1 = 8 issuers.
8. References
8.1. Normative References
[DGSTV18] "Privacy Pass, Bypassing Internet Challenges Anonymously",
n.d., <https://www.degruyter.com/view/j/
popets.2018.2018.issue-3/popets-2018-0026/popets-
2018-0026.xml>.
[DSS] Federal Information Processing Standards Publication, .,
"FIPS PUB 186-4: Digital Signature Standard (DSS)", n.d.,
<https://nvlpubs.nist.gov/nistpubs/FIPS/
NIST.FIPS.186-4.pdf>.
[keytrans]
"Security Through Transparency", n.d.,
<https://security.googleblog.com/2017/01/security-through-
transparency.html>.
Davidson & Sullivan Expires May 6, 2020 [Page 23]
Internet-Draft PP protocol November 2019
[OPRF] "Oblivious Pseudorandom Functions (OPRFs) using Prime-
Order Groups", n.d.,
<https://tools.ietf.org/html/draft-irrf-cfrg-voprf-01>.
[PPEXT] "Privacy Pass Browser Extension", n.d.,
<https://github.com/privacypass/challenge-bypass-
extension>.
[PPSRV] "Cloudflare Supports Privacy Pass", n.d.,
<https://blog.cloudflare.com/cloudflare-supports-privacy-
pass/>.
[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>.
[TRUST] "Trust Token API", n.d., <https://github.com/WICG/trust-
token-api#security-considerations>.
8.2. URIs
[1] https://github.com/grittygrease/draft-privacy-pass
Authors' Addresses
Alex Davidson
Cloudflare Portugal
Largo Rafael Bordalo Pinheiro 29
Lisbon
Portugal
Email: alex.davidson92@gmail.com
Nick Sullivan
Cloudflare
101 Townsend Street
San Francisco
United States of America
Email: nick@cloudflare.com
Davidson & Sullivan Expires May 6, 2020 [Page 24]