| Internet-Draft | Key Consistency and Discovery | July 2023 |
| Davidson, et al. | Expires 11 January 2024 | [Page] |
This document describes the consistency requirements of protocols such as Privacy Pass, Oblivious DoH, and Oblivious HTTP for user privacy. It presents definitions for consistency and then surveys mechanisms for providing consistency in varying threat models. In concludes with discussion of open problems in this area.¶
This note is to be removed before publishing as an RFC.¶
The latest revision of this draft can be found at https://chris-wood.github.io/key-consistency/draft-ietf-privacypass-key-consistency.html. Status information for this document may be found at https://datatracker.ietf.org/doc/draft-ietf-privacypass-key-consistency/.¶
Source for this draft and an issue tracker can be found at https://github.com/chris-wood/key-consistency.¶
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 11 January 2024.¶
Copyright (c) 2023 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 Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶
Several proposed privacy-enhancing protocols such as Privacy Pass [PRIVACY-PASS], Oblivious DoH [ODOH], and Oblivious HTTP [OHTTP] require clients to obtain and use a public key for execution. For example, Privacy Pass public keys are used by clients when issuing and redeeming tokens for anonymous authorization. Oblivious DoH and HTTP both use public keys to encrypt messages to a particular server.¶
Privacy in these systems depends on clients using an authenticated key that many, if not all, other clients use. If a client were to receive a public key that was specific to them, or restricted to a small set of clients, then use of that public key could be used to learn targeted information about the client. Informally, using the same key is referred to as key consistency. The degree to which clients use consistent keys determines the extent to which use of a particular key can compromise their individual privacy. This document provides definitions for key consistency that captures this concept.¶
Depending on the type of consistency, the design space for building key consistency solutions can be large. This document surveys several common approaches to solving this problem and describes the consistency properties they purport to provide under various threat models.¶
The purpose of this document is twofold: (1) provide a foundation upon which technical solutions can be specified and evaluated, and (2) highlight challenges in building and deploying key consistency solutions in practice.¶
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶
This document defines the following terms:¶
A system that embeds one or more key consistency systems.¶
A cryptographic object used by a reliant system.¶
A unique identifier for a key.¶
A set of one or more keys.¶
A unique identifier for a key set.¶
An entity that uses a key in a reliant system.¶
An entity that provides key material for use by clients.¶
The key consistency model is dependent on the implementation and reliant system's threat model.¶
Privacy-focused protocols which rely on widely shared public keys typically require keys be consistent. Informally, key consistency is the requirement that all clients who use a source-provided key in some reliant system share the same view of the key. Some protocols depend on large sets of clients with consistent keys for privacy reasons. Specifically, all clients with a consistent key represent an anonymity set wherein each client of the key in that set is indistinguishable from the rest. An attacker that can actively cause inconsistent views of keys can therefore compromise client privacy.¶
Formally, consistency is a predicate defined based on key sets. Typically, clients try to assess consistency of one key against one or more keys, but there are no restrictions on whether the clients holding those keys are the same.¶
There are two different predicates for consistency, defined below.¶
Checking for consistency or global consistency of two key sets (singletons or not) consists in applying a verification function to those sets. If the two sets are consistent and the union of those two sets is equal to the set of all possible honestly generated values, then the union is globally consistent.¶
Consistency checks can happen within a reliant system, i.e., as part of the protocol in which consistency is preferred, or out of it, i.e., a separate protocol run alongside the reliant system. We refer to these two paths as in-band and out-of-band verification. In-band verification is a check which is invoked as part of a reliant system. This type of verification is only achieved by participants of the reliant system. In contrast, out-of-band verifiability is a check that happens outside of a reliant system, i.e., by entities that may not be participants of the reliant system. Consistency verification is typically public, meaning that any entity with two key sets can verify (global) consistency without requiring knowledge of a cryptographic secret.¶
Reliant systems must also consider agility when trying to achieve consistency. A naive solution to ensuring consistent keys is to only use a single, fixed key pair for the entirety of the system. Clients can then embed this key into software or elsewhere as needed, without any additional mechanics or controls to ensure that other clients have a different key. However, this solution clearly is not viable in practice. If the corresponding key is compromised, the system fails. Rotation must therefore be supported, and in doing so, clients need some mechanism to ensure that newly rotated keys are consistent.¶
Operationally, servers rotating keys may likely need to accommodate distributed system state-synchronization issues without sacrificing availability. Some systems and protocols may choose to prioritize strong consistency over availability, but this document assumes that availability is preferred to total consistency.¶
There are a variety of ways in which reliant systems may build key consistency solutions, with different trade-offs for operational and implementation complexity. In this section, we survey a number of possible solutions. The viability of each varies depending on the applicable threat model, external dependencies, and overall reliant system's requirements.¶
In each mechanism, the client has as input a candidate key and seeks to determine if it has a (globally) consistent version of the key.¶
We do not include the fixed public key model from Section 3, as this is likely not a viable solution for systems and protocols in practice. In all scenarios, the server corresponding to the desired key is considered malicious.¶
In this model, clients would directly query servers for their corresponding key, as shown below.¶
The properties of this mechanism depend on external mechanisms in place to ensure consistency and whether or not the server colludes with the key source. If the server and source collude, both can present unique per-client keys without detection.¶
In this model, there exists a shared cache that provides keys from servers on behalf of multiple clients, as shown below.¶
The validity window of the cache's response can impact the overall consistency guarantees. In particular, a system needs to ensure that a server cannot rotate its keys too often in order to divide clients into smaller groups based on when keys are acquired. Such considerations are already highlighted within the Privacy Pass ecosystem, more discussion can be found in [PRIVACY-PASS-ARCH]. Setting a minimum validity period limits the ability of a server to rotate keys, but also limits the rate of key rotation.¶
Querying a cache for its stored copy of a key leaks information to that cache. There are several mitigations for this leak. For example, clients could obtain the contents of a cache and query it locally. Alternatively, clients could remotely query the cache using privacy-preserving queries (e.g., a private information retrieval (PIR) protocol). In the case where the cache is downloaded locally, it should be considered stale and re-fetched periodically. The frequency of such updates can likely be infrequent in practice, as frequent key updates or rotations may affect privacy. Downloading the entire cache works best if there are a small number of entries, as it does not otherwise impose bandwidth costs on each client that may be impractical.¶
If this cache is trusted, then all clients which request a key from this server are assured they have a consistent view of the server key compared to all other clients of the cache. A malicious cache can introduce the following threats:¶
Potential mitigations for untrusted caches are described in the following sections.¶
There are several ways the risk of untrusted caches may be mitigated. The first of which is via the use of multiple, non-colluding caches, as shown below.¶
This mechanism provides consistency across all clients that share the same set of caches.¶
If no other caches are available, clients may attempt to confirm the key provided by the cache directly with the server, as shown in the figure below.¶
Ideally, clients confirm with the server via some anonymizing proxy. Examples of proxies include anonymous systems such as Tor. Tor proxies are general purpose and operate at a lower layer, on arbitrary communication flows, and therefore they are oblivious to clients fetching keys. Untrusted proxies that are aware of key fetch requests (Section 4.2) may be used in a similar way. Depending on how clients fetch such keys from servers, it may become more difficult for servers to uniquely target individual clients with unique keys without detection. This is especially true as the number of clients of these anonymity networks increases. However, beyond Tor, there does not exist a special-purpose anonymity network for this purpose.¶
If redundancy is not viable or feasible for a particular deployment, consistency guarantees may also be improved through transparency systems, i.e., those based on tamper-proof, publicly verifiable data structures. Examples of this type of system are below.¶
Consistency may also be improved by forcibly limiting the number of keys that an attacker can feasibly use for targeting particular clients. One way to implement this limit is via key-based encryption, which is a procedure where a client encrypt the information that it sends to a server, such as a token or signed object generated with the server keys. This encryption uses a key derived from the key configuration, specifically not including any form of key identifier along with the encrypted information. If key derivation for the encryption uses a pre-image resistant function (like HKDF), the server can only decrypt the information only if it either knows the key configuration or can guess it. As there is no information the server can use to identify which key was used, it is forced to perform trial decryption if it wants to use multiple keys.¶
These costs are only linear in terms of the number of active keys. This doesn't prevent the use of multiple keys; it only makes their use incrementally more expensive. Adding a nonce with sufficient entropy might be used to force key derivation for every message. Using a time- or memory-hard key derivation function such as [ARGON2] can then be used to increase the cost of trial decryption.¶
Encrypting this way could provide better latency properties than a separate check.¶
The model in Section 4.2.1 seems to be the most lightweight and easy-to-deploy mechanism for ensuring key consistency and correctness. However, it remains unclear if there exists such an anonymity network that can scale to the widespread adoption of and requirements of protocols like Privacy Pass, Oblivious DoH, or Oblivious HTTP. Also, using such a network carries its own set of risks for clients (as described in Section 4.2.1), so in some cases it might be impractical. Existing infrastructure based on technologies like Certificate Transparency or Key Transparency may work, but there is currently no general purpose system for transparency of opaque keys (or other application data).¶
This document discusses several models that systems might use to implement public key discovery while ensuring key consistency and correctness. It does not make any recommendations for such models as the best model depends on differing operational requirements and threat models.¶