Network Working Group S. Li Internet-Draft EFF Intended status: Experimental C. Man Expires: January 3, 2019 J. Watson Stanford University July 02, 2018 Delegated Distributed Mappings draft-watson-dinrg-delmap-00 Abstract Delegated namespaces (domain names, IP address allocation, etc.) underpin almost every Internet entity but are centrally managed, unilaterally revokable, and lack a common interface. This draft specifies a generalized scheme for delegation with a structure that supports explicit delegation guarantees. The resulting data may be secured by any general purpose distributed consensus protocol; clients can query the local state of any number of participants and receive the correct result barring a compromise at the consensus 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 January 3, 2019. Copyright Notice Copyright (c) 2018 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 Li, et al. Expires January 3, 2019 [Page 1] Internet-Draft Delegated Mappings July 2018 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1. Cells . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2. Tables . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3. Root Key Listing . . . . . . . . . . . . . . . . . . . . 6 2.4. Data Structure . . . . . . . . . . . . . . . . . . . . . 7 3. Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1. Validation . . . . . . . . . . . . . . . . . . . . . . . 8 3.2. SCP . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4. Security Considerations . . . . . . . . . . . . . . . . . . . 9 5. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 5.1. Normative References . . . . . . . . . . . . . . . . . . 10 5.2. Informative References . . . . . . . . . . . . . . . . . 10 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 1. Introduction Internet entities rely heavily on delegated namespaces to function properly. Typical web services might have been delegated a domain name under which they host the entirety of their public-facing content, or obtain a public IP range from their ISP, acquiring a portion of a namespace originally assigned by an Internet Numbers Registry [RFC7249]. An enormous amount of economic value is therefore placed in these assignments, or mappings, yet they are dangerously ephemeral. Delgating authorities can unilateraly revoke and replace the assignments they've made (maliciously or accidentally), compromising infrastructure security. Presented in this draft is a generalized mechanism for delegating and managing such mappings. Specifically, we describe the structure for a distributed directory with support for delegation "commitments" that have an explicit duration. Certain known entities are assigned namespaces, loosely associated with a service provided by that entity (i.e domain prefixes for DNS Authorities). Under that namespace, are authorized to create mapping records, or _cells_, a unit of ownership in the service. A namespace's cells are grouped into a logical unit we term a _table_. Li, et al. Expires January 3, 2019 [Page 2] Internet-Draft Delegated Mappings July 2018 Table cells may also explicitly document the delegation of a portion of the authority's namespace to another entity with a given public key, along with a guarantee on that delegation's lifetime. Each delegation forms a new table, for which the delegee is the sole authority. Thus, the delegating entity may not make modifications to a delegated table and need not be trusted by the delegee. The namespace segment may be further delegated to others. The delegation tables maintain security and consistency through a distributed consensus algorithm. When a participant receives an update, they verify and submit it to the consensus layer, after which, if successful, the change is applied to its associated table. Clients may query any number of trusted servers and expect the result to be correct barring widespread collusion. The risk of successful attacks on this system vary based on the consensus scheme used. Detailed descriptions of specific protocol implementations are out of scope for this draft, but at a minimum, the consensus algorithm must apply mapping updates in a consistent order, prevent equivocation or unauthorized modification, and enforce the semantic rules associated with each table. We find that federated protocols such as the Stellar Consensus Protocol [I-D.mazieres-dinrg-scp] are promising given their capability for open participation, broad diversity of interests among consensus participants, and a measure of accountability for submitting deceptive updates. This document specifies the structure for authenticated mapping management and its interface with a consensus protocol implementation. 2. Structure Trust within the delegation structure is solely based on public key signatures. Namespace authorities must sign any mapping additions, modifications, delegations, and revocations as proof to the other consensus participants that such changes are legitimate. For the sake of completeness, the public key and signature types are detailed below. All types in this draft are described in XDR [RFC4506]. typedef publickey opaque<>; /* Typically a 256 byte RSA signature */ struct signature { publickey pk; opaque data<>; }; Li, et al. Expires January 3, 2019 [Page 3] Internet-Draft Delegated Mappings July 2018 2.1. Cells Cells are the basic unit of the delegation structure. In general, they define an authenticated mapping record that may be queried by clients. We describe two types of cells: enum celltype { VALUE = 0, DELEGATE = 1 }; Value cells store individual mapping entries. They resolve a lookup key to an arbitrary value, for example, an encryption key associated with an email address or a the address of an authoritative nameserver for a given DNS zone. The public key of the cell's owner (e.g. the email account holder, the zone manager) is also included, as well as a signature authenticating the current version of the cell. The cell must be signed either by the "owner_key", or in some cases, the authority of the table containing the cell, as is described below. The cell owner may rotate their public key at any time by signing the transition with the old key. struct valuecell { opaque value<>; publickey owner_key; signature transition_sig; /* Owner or table authority */ }; Delegate cells have a similar structure but different semantics. Rather than resolving an individual mapping, they authorize the delegee to create arbitrary value cells within an assigned namespace. This namespace must be a subset of the _delegator_'s own namespace range. The delegee is identified by their public key. Finally, each delegate cell and subsequent updates to the cell are signed by the delegator - this ensures that the delegee cannot unilaterally modify its namespace, which limits the range of mappings they can legitimately create. struct delegatecell { opaque namespace<>; publickey delegee; signature authority_sig; /* Delegator only */ }; Both cell types share a set of common data members, namely a set of UNIX timestamps recording the creation time and, if applicable, the time of last modification. They are useful indicators and will likely be useful in updating consensus nodes that have fallen behind. Li, et al. Expires January 3, 2019 [Page 4] Internet-Draft Delegated Mappings July 2018 An additional "commitment" timestamp must be present in every mapping. It is an explicit guarantee on behalf of the authority creating the cell that the mapping will remain valid until at least the specified time. Therefore, while value cell owners may modify their cell at any moment, the authority cannot successfully change (or remove) the cell until its commitment expires. Similarly, delegated namespaces are guaranteed to be valid until the commitment timestamp. This creates a tradeoff between protecting delegees from arbitrary delegator action and allowing simple reconfiguration that can be customized for the use case. union innercell switch (celltype type) { case VALUE: valuecell vcell; case DELEGATE: delegatecell dcell; }; struct cell { unsigned hyper create_time; /* 64-bit UNIX timestamps */ unsigned hyper *revision_time; unsigned hyper commitment_time; innercell c; } 2.2. Tables Every cell is stored in a table, which groups all the mappings created by a single authority public key for a specific namespace. Individual cells are referenced by an application-specific label in a lookup table. Below, we allow for a single lookup key to reference a list of cells, for the sake of generality. The combination of a lookup key and a referenced cell value forms a mapping. struct tableentry { opaque lookup_key<>; cell cells<>; } Delegating the whole or part of a namespace requires adding a new lookup key for the namespace in question and a matching delegate cell. Each delegation must be validated in the context of the other table entries and the table itself. For example, it should not be possible for the owner of a /8 IPv4 block to delegate the same /16 block to two different delegees. In addition to a collection of entries, each table incorporates a "type" that informs each participating node of the particular delegation rules to apply to table entries. Li, et al. Expires January 3, 2019 [Page 5] Internet-Draft Delegated Mappings July 2018 struct table { tabletype type; tableentry entries<>; }; While there exist more delegation mechanisms than we could reasonably discuss in this draft, we initially propose three general-purpose schemes that cover the majority of use cases: enum tabletype { PREFIX = 0, SUFFIX = 1, FLAT = 2 }; The table type informs the validation procedure when performing consensus; all new or updated delegated namespaces must follow the proper format for their table. Prefix-based delegation, such as in an IP delegation use case, requires every table cell value to be prefixed by the table namespace, and no cell value be a prefix of another cell value. Similar rules apply to suffix-based delegation. In cases where arbitrary values may be mapped (e.g. account names for an email service provider), "flat" delegation rules are used. The delegation rule for a table also determine valid lookup behavior. Given a particular lookup key, "PREFIX"-type tables should have at most one entry whose key is a prefix of the query. Likewise, "SUFFIX" tables have at most one entry whose key is a suffix of the query. As an example, lookup on "irtf.org" in a table of domain names with suffix-based delegation rules may return entries with keys "irtf.org", "tf.org", ".org", etc., but the presence of more than one of these indicates two faulty delegations that control the same namespace. 2.3. Root Key Listing Each linked group of delegation tables for a particular namespace is rooted by a public key stored in a flat root key listing, which is the entry point for lookup operations. Well-known application identifier strings denote the namespace they control. We describe below how lookups can be accomplished on the mappings. Li, et al. Expires January 3, 2019 [Page 6] Internet-Draft Delegated Mappings July 2018 struct rootentry { publickey namespace_root_key; string application_identifier<>; signature listing_sig; } struct rootlisting { rootentry roots<>; } A significant open question is how to properly administer entries in this listing, since a strong authority, such as a single root key, can easily protect the listing from spam and malicious changes, but raises important concerns about censorship resilience and potential compromise. A federated approach to management is more in line with the spirit of this draft but opens the door for counter-productive participation. In the "rootentry" description above, we allow for either a root signing key to authenticate mappings, or first-come- first-served self-signed entries. In either case, no more than one key may control the namespace for a specific application identifier. 2.4. Data Structure Delegation tables are stored in a Merkle hash tree, described in detail in [RFC6962]. In particular, it enables efficient lookups and logarithmic proofs of existence in the tree, and prevents equivocation between different participants. Specifically, we can leverage Google's [Trillian] Merkle tree implementation which generalizes the datastructures used in Certificate Transparency. In map mode, the tree can manages arbitrary key-value pairs at scale. This requires flattening the delegation links such that each table may be queried, while ensuring that a full lookup from the application root be made for each mapping. Given a "rootentry", the corresponding table in the Merkle tree can be found with this concatenation: root_table_name = app_id || namespace_root_key Similarly, tables for delegated namespaces are found at: root_table_name || delegee_key_1 || ... || delegee_key_n Consensus is performed on the Merkle tree containing the flattened collection of tables. While it is possible to reach consensus on entire tables when a cell is modified, this approach does not scale well with the size of the table. Therefore, each table should maintain its entries in its own internal Merkle tree and perform consensus on Merkle proofs for the modified cell. Li, et al. Expires January 3, 2019 [Page 7] Internet-Draft Delegated Mappings July 2018 3. Consensus Safety is ensured by reaching distributed consensus on the state of the tree. The general nature of a Merkle tree as discussed in the previous section enables almost any consensus protocol to support delegated mappings, with varying guarantees on the conditions under which safety is maintained and different trust implications. For example, a deployment on a cluster of nodes running a classic Byzantine Fault Tolerant consensus protocol such as [PBFT] requires a limited, static membership and can tolerate compromises in up to a third of its nodes. In comparison, proof-of-work schemes including many cryptocurrencies have open membership but rely on economic incentives and distributed control of hashing power to provide safety, and federated consensus algorithms like the Stellar Consensus Protocol (SCP) [I-D.mazieres-dinrg-scp] combine dynamic members with real-world trust relationships but require careful configuration. Determining which scheme, if any, is the "correct" protocol to support authenticated delegation is an open question. 3.1. Validation Incorrect (potentially malicious) updates to the Merkle tree should be rejected by nodes participating in consensus. Given the limited set of delegation schemes presented in the previous section, each node can apply the same validation procedure without requiring application-specific knowledge. Upon any modification to the tree - addition of a new root entry, table or cell, or modification of an existing cell - the submitted change to the consensus layer should contain: (1) the updated or newly-created table, and (2) a Merkle proof containing all the hashes necessary to validate the new root tree hash. Finally, each node participating in consensus must confirm before voting for the update that: (1) the Merkle proof is correct, and (2) an addition to the root key listing is correctly signed by an authorized party, or (3) for delegate cells: (3a) a new delegation is correctly authenticated, (3b) the cell contains a valid namespace owned by the delegator, (3c) the Li, et al. Expires January 3, 2019 [Page 8] Internet-Draft Delegated Mappings July 2018 delegation follows the table-specified delegation rules, and (3d) the delegated table is mapped in the Merkle map by the proper key (4) for value cells: (4a) a new mapping is correctly authenticated, (4b) the value belongs to the signing authority's namespace, and (4c) does not conflict with other cells in its table (5) and for all updates, if proposed by the table authority, the cell contains an expired commitment timestamp. Only after a round of the consensus protocol is successful are the changes exposed to client lookups. 3.2. SCP While consensus can be reached with many protocols, this section describes how the delegation tables can interface with an SCP implementation. As discussed above, updates to the delegation tables take the form of Merkle proofs along with the table change itself. Since SCP does not need specific knowledge of the format of these proofs, they directly form the opaque values submitted to the consensus layer. Once a combination of proofs are agreed to as outputs for a given slot, they are applied to the local tables state. Finally, [I-D.mazieres-dinrg-scp] requires the delegation layer to provide a _validity_ function that is applied to each input value, and a _combining function_ to compose multiple candidate values. For this application, the validity function must implement the logic contained in the previous section. The combining function can simply take the union of the valid proofs proposed by the consensus nodes, rejecting valid, duplicate updates to the same cell in favor of the most up-to-date timestamp. 4. Security Considerations The security of the delegation tables is primarily tied to the safety properties of the underlying consensus layer. Further, incorrect use of the public key infrastructure authenticating each mapping or compromise of a namespace root key can endanger mappings delegated by the key after their commitments expire. Li, et al. Expires January 3, 2019 [Page 9] Internet-Draft Delegated Mappings July 2018 5. References 5.1. Normative References [RFC4506] Eisler, M., Ed., "XDR: External Data Representation Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May 2006, . [Trillian] Google, "Trillian: General Transparency", n.d., . 5.2. Informative References [I-D.mazieres-dinrg-scp] Barry, N., Losa, G., Mazieres, D., McCaleb, J., and S. Polu, "The Stellar Consensus Protocol (SCP)", draft- mazieres-dinrg-scp-04 (work in progress), June 2018. [PBFT] Castro, M. and B. Liskov, "Practical Byzantine Fault Tolerance", 1999, . [RFC6962] Laurie, B., Langley, A., and E. Kasper, "Certificate Transparency", RFC 6962, DOI 10.17487/RFC6962, June 2013, . [RFC7249] Housley, R., "Internet Numbers Registries", RFC 7249, DOI 10.17487/RFC7249, May 2014, . Acknowledgments We are grateful for the contributions and feedback on design and applicability by David Mazieres, as well as help and feedback from the IRTF DIN research group, including Dirk Kutscher and Melinda Shore. This work was supported by The Stanford Center For Blockchain Research. Authors' Addresses Li, et al. Expires January 3, 2019 [Page 10] Internet-Draft Delegated Mappings July 2018 Sydney Li Electronic Frontier Foundation 815 Eddy Street San Francisco, CA 94109 US Email: sydney@eff.org Colin Man Stanford University 353 Serra Mall Stanford, CA 94305 US Email: colinman@cs.stanford.edu Jean-Luc Watson Stanford University 353 Serra Mall Stanford, CA 94305 US Email: jlwatson@cs.stanford.edu Li, et al. Expires January 3, 2019 [Page 11]