Tree Hints for the Resource Public Key Infrastructure (RPKI)

Abstract

In the Resource Public Key Infrastructure (RPKI), holders of IP address space can become a Certification Authority (CA), optionally hosting their repository. They can also delegate (part of) their resources to subordinate CAs, who in turn may do the same. This CA hierarchy forms a tree structure. Relying Party (RP) software walks this tree and determines the current valid objects. An underlying assumption is that this tree is finite and kept at a reasonable size. This assumption is not guaranteed to hold. This document proposes a new Tree Hint object on RPKI manifests that can add constraints for use in RP processing that ensure this assumption holds.¶

1. Introduction

In the RPKI, holders of IP address space can host their own repositories and act as their own CA. They have full control over that repository and any objects signed by their CA. They may, for example, sign one or more certificates that hold a subset of the resources from the parent certificate. These certificates may reference publication points in the same repository or different ones. These new certificates can, in turn, do the same, ad infinitum. The nested structure of CAs forms a tree structure. The root of these trees are defined by the Trust Anchor Locators (TALs) [RFC8630]. RP software is assumed to walk this tree, visit every node, and retrieve all objects (e.g. Manifests [RFC6486], Route Origin Authorizations [RFC6482], Ghostbuster records [RFC6493], other certificates [RFC6481], etc.). RP software collects all information from the objects and processes it. It is important to note that RP software needs to visit every repository and consider every object CAs put on manifests. If it would exclude any repository or CA, then a BGP advertisement that should be valid can become invalid. For example, if a ROA for the prefix 2001:DB8::/32 and AS64496 is included, but the ROA for 2001:DB8:123::/48 and AS64497 (from another CA) is not, then a BGP speaker performing ROV validation may falsely reject the latter, more specific, announcement.¶

For RP software to fully walk the tree, the tree needs to be finite and reasonably sized. However, the size of the tree can only be determined while traversing the tree - RP software cannot verify these properties in advance. A malicious CA could, for example, create its children in an ad-hoc fashion while RP software is discovering it, thereby violating the implicit assumption that the tree is finite. That specific behaviour can be countered by RP software by setting a maximum depth for a certificate chain. However, at 10 children per child, the number of repositories would already reach 1111111111 (10^0 + 10^1 + ... + 10^9) after a modest 10 levels. With other strategies, such as serving gigabytes of data and simulating a very low bandwidth, a malicious repository can violate our second assumption that the tree is reasonably sized. Using malicious repository content, any CA can cause the process to take so unreasonably long that RP software does not finish processing in a reasonable amount of time (possibly years). The size and structure of nodes in the RPKI tree varies. For example, a NIR may have a legitimate need for hundreds of child-CAs, while a regular CA under the same parent does not. This diversity makes heuristics unsuitable for detecting this issue adequately, only discarding the malicious repository and its children, without heavily restricting the freedom of the structure of RPKI or causing false positives capping future growth.¶

Other limits may be needed as well. For example, a large repository may be several gigabytes in size, especially after a key roll, but if every repository is gigabytes in size, this may become problematic. Likewise, there may be valid reasons for splitting a prefix into many subprefixes, or authorising subprefixes for many autonomous system numbers (ASNs), but allowing any party to add limitless prefix-ASN pairs may overflow BGP Origin Validation tables. Setting a fixed limit may be problematic in these cases.¶

A new RPKI object (tree hint) is added on manifest to mitigate this issue by providing RP software prior knowledge about limits before walking the tree.¶

2. Scope

The scope of the Tree Hint object is to provide guidance for RP software regarding the expected structure of the tree, as well as impose requirements on other aspects of the CA and its repository. Following the information in the Tree Hint object is RECOMMENDED. However, local policy may prevail over the data in a Tree Hint object.¶

3. Structure

A Tree Hint is consists of a single object on the manifest of a CA. This object contains limits. These limits are imposed on each of the subtrees of children of this CA. For example, if a 5 GB limit on the maximum size of a repository is imposed, then that means that each direct child of this CA and its descendants is allowed to have a repository up to 5 GB as the sum of that child and its children. This means that a limit cannot be circumvented by delegating resources to children of children.¶

Each CA may define its own Tree Hint object. Taking the previous example, if a 5 GB limit is imposed on CA "Foo", then Foo may also create a Tree Hint object to impose a limit of 1 GB for Foo's children, for example "Bar". Note that both the limit imposed on Bar by Foo, and the parent of Foo, apply to Bar, as well as the limit imposed by all parents in the chain of Bar up to the root. In case of conflict, the most strict limit MUST be used.¶

In some cases a limit is not sufficient for a specific child. In those cases, an exception can be made. The Tree Hint object contains a list of exceptions. An exception consists of the subjectKeyIdentifier (SKI) of the child's certificate, and a new set of limits. If a limit is defined for this SKI, this value MUST then be used instead of the global limit for this level. Note that a stricter limit at a higher level may still take precedence over the exception. Additionally, an exception MAY only override a subset of the global limits for a SKI. In case an exception is made for this SKI, a limit is defined at a global level, and this limit does not appear in the exception, then the value at the global level MUST be used. Exceptions SHOULD only be created if absolutely necessary, and custom values SHOULD be subject to human review. Exceptions MUST only be created for direct children (CAs for which the CA certificate is on the manifest the Tree Hint is on).¶

By using reasonable values at the top level, it can be assumed that the tree can be traversed in reasonable time, whilst keeping the flexibility of the tree structure as it is currently.¶

4. Definition

The Tree Hint object uses the template for RPKI digitally signed objects [RFC6488], which defines a Cryptographic Message Syntax [RFC3370] wrapper for the Tree Hint content as well as a generic validation procedure for RPKI signed objects.¶

If a Tree Hint object is present, it MUST be included in the manifest. Having more than one Tree Hint object leads to ambiguity, therefore there MUST NOT be more than one Tree Hint object present in a manifest. The Tree Hint object MAY contain references to Subject Key Identifiers (SKIs) that are not present.¶

   TreeHint ::= SEQUENCE {
     version        [0] INTEGER DEFAULT 0,
     limits             Limit (0..MAX),
     exceptionList      SEQUENCE SIZE (0..MAX) OF Exception
   }

   Exception ::= SEQUENCE {
     ski                OCTET STRING,
     limits             Limit (0..MAX)
   }

   Limit ::= SEQUENCE {
     oid                OBJECT IDENTIFIER,
     limit              OCTET STRING
   }

5. Validation

In order to validate the limits, RP software should construct the chain of certificates from the current certificate up to the root. For each limit, RP software should check for each certificate in this chain whether an exception exists for this value, or, when absent, whether that certificate defines a global limit. Then the most strict limit of all limits present in the chain should be used as limit. Which value is the most strict is defined by the definition of the limit itself. If a limit is absent from the entire chain, a reasonable default SHOULD be used. Root CAs SHOULD define all limits.¶

6. Limits

Limits are aimed to be extensible, as future additions and discoveries may warrant the inclusion of new limits.¶

   maxDescendants ::= INTEGER

   connectionRetryCount ::= INTEGER

   connectionTimeout ::= INTEGER

   connectionTransferTime ::= INTEGER

   maxRepositorySize ::= INTEGER

   maxTransferSize ::= INTEGER

   minTransferSpeed ::= INTEGER

   maxObjectSize ::= INTEGER

   maxPrefixPairs ::= INTEGER

9. References