Key Consistency and Discovery
draft-wood-key-consistency-00

Network Working Group                                        A. Davidson
Internet-Draft                                                LIP Lisboa
Intended status: Informational                                 M. Finkel
Expires: 26 August 2021                                  The Tor Project
                                                              M. Thomson
                                                                 Mozilla
                                                               C.A. Wood
                                                              Cloudflare
                                                        22 February 2021

                     Key Consistency and Discovery
                     draft-wood-key-consistency-00

Abstract

   This document describes the key consistency and correctness
   requirements of protocols such as Privacy Pass, Oblivious DoH, and
   Oblivious HTTP for user privacy.  It discusses several mechanisms and
   proposals for enabling user privacy in varying threat models.  In
   concludes with discussion of open problems in this area.

Discussion Venues

   This note is to be removed before publishing as an RFC.

   Discussion of this document takes place on the mailing list (), which
   is archived at .

   Source for this draft and an issue tracker can be found at
   https://github.com/chris-wood/key-consitency.

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 26 August 2021.

Davidson, et al.         Expires 26 August 2021                 [Page 1]
Internet-Draft        Key Consistency and Discovery        February 2021

Copyright Notice

   Copyright (c) 2021 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully, as they describe your rights
   and restrictions with respect to this document.  Code Components
   extracted from this document must include Simplified BSD License text
   as described in Section 4.e of the Trust Legal Provisions and are
   provided without warranty as described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
     1.1.  Requirements  . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .   3
   3.  Core Requirements . . . . . . . . . . . . . . . . . . . . . .   4
   4.  Deploying Consistency and Correctness . . . . . . . . . . . .   4
     4.1.  Server-Provided Key Discovery . . . . . . . . . . . . . .   5
     4.2.  Proxy-Based Key Discovery . . . . . . . . . . . . . . . .   5
     4.3.  Log-Based Key Discovery . . . . . . . . . . . . . . . . .   6
     4.4.  Anonymous System Key Discovery  . . . . . . . . . . . . .   6
     4.5.  Consensus-based Key Discovery . . . . . . . . . . . . . .   6
     4.6.  Minimum Validity Periods  . . . . . . . . . . . . . . . .   7
   5.  Future Work . . . . . . . . . . . . . . . . . . . . . . . . .   7
   6.  Security Considerations . . . . . . . . . . . . . . . . . . .   7
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   7
     7.1.  Normative References  . . . . . . . . . . . . . . . . . .   7
     7.2.  Informative References  . . . . . . . . . . . . . . . . .   8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   8

Davidson, et al.         Expires 26 August 2021                 [Page 2]
Internet-Draft        Key Consistency and Discovery        February 2021

1.  Introduction

   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 for validating
   privately issued tokens for anonymous session resumption.  Oblivious
   DoH and HTTP both use public keys to encrypt messages to a particular
   server.  In all cases, a common security goal is that recipients
   cannot link usage of a public key to a specific (set of) user(s).  In
   other words, all users of a public key should belong to the same
   anonymity set, and an attacker should not be able to actively reduce
   the size of this anonymity set.  Moreover, an attacker should not be
   able to convince users to use a key that does not belong to the
   intended server.

   In this document, we elaborate on these core requirements, and survey
   various system designs that might be used to satisfy them.  The
   purpose of this document is to highlight challenges in building and
   deploying solutions to this problem.

1.1.  Requirements

   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.

2.  Terminology

   This document defines the following terms:

   Key Consistency and Correctness System (KCCS):  A mechanism for
      providing clients with a consistent view of cryptographic key
      material.

   Reliant System:  A system that embeds one or more key consistency and
      correctness systems.

   The KCCS's consistency model is dependent on the implementation and
   reliant system's threat model.

Davidson, et al.         Expires 26 August 2021                 [Page 3]
Internet-Draft        Key Consistency and Discovery        February 2021

3.  Core Requirements

   Privacy-focused protocols which rely on widely shared public keys
   typically require keys be consistent and correct.  Informally, key
   consistency is the requirement that all users of a key share the same
   view of the key.  Some protocols depend on large sets of users with
   consistent keys for privacy reasons.  Specifically, all users with a
   consistent key represent an anonymity set wherein each user of the
   key in that set is indistinguishable from the rest.  An attacker that
   can actively cause inconsistent views of keys can therefore
   compromise user privacy.

   An attacker may separately reduce a user's privacy by forcing them
   into a smaller anonymity set by using an incorrect key.  Informally,
   a key is correct if it belongs to the intended server and is not
   otherwise available to an attacker.  In a public key setting, this
   means that the public key is that which is owned by the corresponding
   owner, and only that owner has access to the private key.  An
   attacker that can actively cause users to make use of incorrect keys
   may be able to compromise user privacy.

   Reliant systems must also consider agility when trying to satisfy
   these requirements.  A naive solution to ensuring consistent and
   correct keys is to only use a single, fixed key pair for the entirety
   of the system.  Users can then embed this key into software or
   elsewhere as needed, without any additional mechanics or controls to
   ensure that other users 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, users need some mechanism to ensure that newly
   rotated keys are consistent and correct.  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 consistency.

4.  Deploying Consistency and Correctness

   There are a variety of ways in which reliant systems may build _key
   consistency and correct systems_ (KCCS), ranging in operational
   complexity to ease-of-implementation.  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.  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.

Davidson, et al.         Expires 26 August 2021                 [Page 4]
Internet-Draft        Key Consistency and Discovery        February 2021

4.1.  Server-Provided Key Discovery

   In this model, users would directly query servers for their
   corresponding public key.  The properties of this solution depend on
   external mechanisms in place to ensure consistency or correctness.
   Absent any such mechanisms, servers can produce unique keys for users
   without detection.  External mechanisms to ensure consistency here
   might include, though are not limited to:

   *  Presenting a signed assertion from a trusted entity that the key
      is correct.

   *  Presenting proof that the key is present in some tamper-proof log,
      similar to Certificate Transparency ([RFC6962]) logs.

   *  User communication or gossip ensuring that all users have a shared
      view of the key.

   The precise external mechanism used here depends largely on the
   threat model.  If there is a trusted external log for keys, this may
   be a viable solution.

4.2.  Proxy-Based Key Discovery

   In this model, there exists a proxy that fetches keys from servers on
   behalf of multiple users.  If this proxy is trusted, then all users
   which request a key from this server are assured they have a
   consistent view of the server key.  However, if this proxy is not
   trusted, operational risks may arise:

   *  The proxy can collude with the server to give per-user keys to
      clients.

   *  The proxy can give all users a key owned by the proxy, and either
      collude with the server to use this key or retroactively use this
      key to compromise user privacy when users later make use of the
      key.

   Mitigating these risks may require tamper-proof logs as in
   Section 4.1, or via user gossip protocols.

Davidson, et al.         Expires 26 August 2021                 [Page 5]
Internet-Draft        Key Consistency and Discovery        February 2021

4.3.  Log-Based Key Discovery

   In this model, servers publish keys in a tamper-proof log similar to
   that of Certificate Transparency [RFC6962].  Users may then fetch
   keys directly from the server and subsequently verify their existence
   in the log.  The log is operated and audited in such a way that the
   contents of the log are consistent for all users.  Any reliant system
   which depends on this type of KCCS requires the log be audited or
   users have some other mechanism for checking their view of the log
   state (gossiping).  However, this type of system does not ensure
   proactive security against malicious servers unless log participants
   actively check log proofs.  This requirement may impede deployment in
   practice, given that no web browser checks
   SignedCertificateTimestamps before using (accepting as valid) a
   corresponding TLS certificate.

4.4.  Anonymous System Key Discovery

   In this model, users leverage an anonymity network such as Tor to
   fetch keys directly from servers over multiple vantage points.
   Depending on how clients fetch such keys from servers, it may become
   more difficult for servers to uniquely target individual users with
   unique keys without detection.  This is especially true as the number
   of users of these anonymity networks increases.  However, beyond Tor,
   there does not exist a special-purpose anonymity network for this
   purpose.

4.5.  Consensus-based Key Discovery

   In this model, users query a database containing assertions that bind
   server names and keys.  The assertions provided by this database are
   created by a coalition of entities that periodically agree on the
   correct binding of server names and key material.  In this model the
   agreement is achieve via a consensus protocol, but the specific
   consensus protocol is dependent on the implementation.  For privacy,
   users should either download the entire database and query it
   locally, or remotely query the database using a private information
   retrieval (PIR) protocol.  In the case where the database is
   downloaded locally, it should be considered stale and re-fetch
   periodically, as well.

   When the entire database is downloaded, this model is appropriate in
   small scale deployments where the number of bindings in the database
   is much smaller than the number of users of the reliant system.  In a
   reliant system with a large user base, this model imposes bandwidth
   costs on each user that may be impractical.  In larger scale
   deployments, the short-comings of this model may be similar to
   Section 4.3.

Davidson, et al.         Expires 26 August 2021                 [Page 6]
Internet-Draft        Key Consistency and Discovery        February 2021

   If the database is small and users query it infrequently, retrieval
   techniques based on PIR may be viable.

4.6.  Minimum Validity Periods

   In addition to ensuring that there is one key at any time, or a
   limited number keys, any 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 at [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.

5.  Future Work

   The model in Section 4.4 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.
   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).

6.  Security Considerations

   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.

7.  References

7.1.  Normative References

   [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>.

   [RFC6962]  Laurie, B., Langley, A., and E. Kasper, "Certificate
              Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013,
              <https://www.rfc-editor.org/info/rfc6962>.

Davidson, et al.         Expires 26 August 2021                 [Page 7]
Internet-Draft        Key Consistency and Discovery        February 2021

   [RFC7748]  Langley, A., Hamburg, M., and S. Turner, "Elliptic Curves
              for Security", RFC 7748, DOI 10.17487/RFC7748, January
              2016, <https://www.rfc-editor.org/info/rfc7748>.

   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
              May 2017, <https://www.rfc-editor.org/info/rfc8174>.

7.2.  Informative References

   [ODOH]     Kinnear, E., McManus, P., Pauly, T., and C. Wood,
              "Oblivious DNS Over HTTPS", Work in Progress, Internet-
              Draft, draft-pauly-dprive-oblivious-doh-04, 26 January
              2021, <http://www.ietf.org/internet-drafts/draft-pauly-
              dprive-oblivious-doh-04.txt>.

   [OHTTP]    Thomson, M. and C.A. Wood, "Oblivious HTTP", Work in
              Progress, Internet-Draft, draft-ietf-http-oblivious-
              latest, <https://tools.ietf.org/html/draft-ietf-http-
              oblivious-latest>.

   [PRIVACY-PASS]
              Celi, S., Davidson, A., and A. Faz-Hernandez, "Privacy
              Pass Protocol Specification", Work in Progress, Internet-
              Draft, draft-ietf-privacypass-protocol-00, 5 January 2021,
              <http://www.ietf.org/internet-drafts/draft-ietf-
              privacypass-protocol-00.txt>.

   [PRIVACY-PASS-ARCH]
              Davidson, A., "Privacy Pass Architectural Framework", Work
              in Progress, Internet-Draft, draft-ietf-privacypass-
              architecture-00, 5 January 2021, <http://www.ietf.org/
              internet-drafts/draft-ietf-privacypass-architecture-
              00.txt>.

Authors' Addresses

   Alex Davidson
   LIP Lisboa

   Email: alex.davidson92@gmail.com

   Matthew Finkel
   The Tor Project

   Email: sysrqb@torproject.org

Davidson, et al.         Expires 26 August 2021                 [Page 8]
Internet-Draft        Key Consistency and Discovery        February 2021

   Martin Thomson
   Mozilla

   Email: mt@lowentropy.net

   Christopher A. Wood
   Cloudflare
   101 Townsend St
   San Francisco,
   United States of America

   Email: caw@heapingbits.net

Davidson, et al.         Expires 26 August 2021                 [Page 9]