Merkle Tree Certificates Deployment Use Cases

3.1.1. Landmark Distribution Point Fetching Mechanism

The ldpBaseURIs X509 V3 extension is held by the Issuer of the Signatureless Merkle Tree Certificate and contains the SEQUENCE of LandmarkDistributionPoints, each which is a LandmarkDistributionPoint of IA5String. Each refers to a BaseURI location indicating where the landmarks are published.¶

id-pe-ldpBaseURIs OBJECT IDENTIFIER ::=  { id-pe TBD }

LandmarkDistributionPoints ::= SEQUENCE (1..MAX) OF LandmarkDistributionPoint

LandmarkDistributionPoint ::= IA5String

The Inclusion Proof structure defined in I-D.ietf-plants-merkle-tree-certs uses the following structure:¶

struct {
    uint64 start;
    uint64 end;
    HashValue inclusion_proof<0..2^16-1>;
    MTCSignature signatures<0..2^16-1>;
} MTCProof;

Note that it contains start and end values which indicate the corresponding parameters of the chosen subtree. To request the required landmark, the client simply combines the URL as follows:¶

LandmarkDistributionPoint?st=start?ed=end¶

This allows the verifier to request the required landmark so the inclusion proof can be verified.¶

The verifier needs to trust the issuer as per RFC 5280.¶

3.1.2. Format of Landmark

The format of the landmark is defined in section 6.3.3 of I-D.ietf-plants-merkle-tree-certs¶

As mentioned above, the verifier may need to request the landmark if it is not readily available.¶

This draft proposes an extension to the landmark format specified in section 6.3.3 of I-D.ietf-plants-merkle-tree-certs which defines a mechanism for publishing active landmarks.¶

The current landmark format describes the tree sizes associated for each landmark. However, it does not provide a mechanism for establishing a cryptographic relationship between a previously published landmark and a more recent landmark. This document defines this mechanism as a Landmark subtree consistency Proof. It includes carrying the necessary hashes so that there is a subtree consistency proof from one landmark to the next. The calculation of the subtree consistency proof from one landmark to the next can occur when a new landmark is published. See section 4.4 of I-D.ietf-plants-merkle-tree-certs for information on subtree consistency proofs.¶

This will allow for periodic and incremental updates for clients that need to request information from the LDP server.¶

struct {
    uint64 source_tree_size;
    uint64 target_tree_size;

    HashValue consistency_proof<0..2^16-1>;
} LandmarkSubtreeProof;

3.1.3. Landmark Subtree Proof Retrieval

A verifier validating an MTCProof obtains the corresponding subtree information from the certificate and retrieves the associated landmark file as described in Section 6.3.3.¶

If the verifier possesses a trusted landmark whose tree size is greater than the retrieved landmark's tree size, the verifier MAY obtain a set of LandmarkSubtreeProofSet connecting the two landmarks.¶

struct {
    LandmarkSubtreeProof proofSet<0..2^16-1>;
} LandmarkSubtreeProofSet;

LandmarkDistributionPoint?
    source=<source_tree_size>&
    target=<target_tree_size>

3.1.4. Validation Procedure

A verifier SHALL perform the following steps:¶

1. Extract the start and end values from the MTCProof.¶

2. Retrieve the landmark file corresponding to the authenticated subtree by contacting the LDP server (or retrieving it from a local cache).¶

3. Obtain a trusted target landmark if one is not already cached. For example, a likely candidate would be the latest landmark referenced by the Landmark File.¶

4. Verify the signature(s) associated with the trusted target landmark. If signature verification fails, the verifier MUST reject the certificate.¶

5. If the source subtree landmark and trusted target landmark differ, retrieve a LandmarkSubtreeProofSet that establishes a sequence of authenticated subtree transitions between the source landmark and the trusted target landmark.¶

6. Verify each LandmarkSubtreeProof contained in the LandmarkSubtreeProofSet in the order in which it appears. The first proof SHALL be verified against the source landmark. Each subsequent proof SHALL be verified against the landmark root reconstructed from the preceding proof.¶

7. Successful verification of the complete LandmarkSubtreeProofSet SHALL establish that the source landmark tree is a cryptographic prefix of the trusted target landmark tree.¶

8. Use the validated source landmark to verify the Inclusion Proof contained within the MTCProof.¶

9. Accept the certificate if all verification steps succeed.¶

Successful completion of this procedure establishes that the certificate entry is included in the authenticated subtree identified by the source landmark and that the source landmark is cryptographically bound via the verified LandmarkSubtreeProofSet to the trusted target landmark.¶

3.1.5. Efficiency Considerations

The purpose of LandmarkSubtreeProofs is to reduce the number of landmarks and signatures that must be processed by a verifier.¶

Without LandmarkSubtreeProofs, a verifier may be required to retrieve multiple intermediate landmarks and validate the signatures associated with each landmark before reaching a currently trusted landmark.¶

With LandmarkProofs, a verifier requires only:¶

• the source landmark;¶

• the trusted target landmark; and¶

• a LandmarkSubtreeProofSet connecting the corresponding tree sizes.¶

As a result, the number of signature verification operations is independent of the number of intermediate landmarks published between the source and target landmarks.¶

This property is particularly beneficial when signatures are generated using computationally expensive algorithms, including post-quantum signature algorithms.¶

3.1.6. Skip links for efficiency

TODO: Generating the consistency proof at the LDP server introduces an O(N^2) problem. For efficiency, we likely want to cache landmark proofs as they are generated between each landmark. For example 1->2, 2->3, 3->4 but also 1->3, 1-4, 2-4. Thus O(n^2). A better approach is to use a skip link which only generates O(Log(num_landmarks)) for each landmark. For example, a system that issued a landmark every hour for 10 years would have 87,600 landmarks. When landmark 87,601 is created, only 17 landmark proofs will need to be created. It would also reduce the LandmarkSubtreeProofSet from O(num_landmarks) to O(Log(num_landmarks), greatly reducing bandwidth requirements!¶

3.1.7. More items to be discussed:

• When a CA issues an MTC certificate, it will decide where the landmark will be published. It needs to provide the LDP service.¶

• Current format uses start and end values from the inclusion proof. This is nice because no other extension is needed in the EE certs¶

• Landmarks should be available in a predictable way. The above format should meet this requirement.¶

• Do Landmark's contain a signature, or is it just the MTH and we use the cumulative landmarks along with the inclusion proof?¶

  • A: No, there is one trusted target that contains a signature. That trusted target should be cached so that the full PQ signatures doesn't need to be continually downloaded. This is where MTC gets its efficiency.¶

• Is there a repository of test landmark certificates that we can use to test this mechanism?¶

  • A: Seems like a good hackathon project!¶

3.1.8. Landmark Distribution server

As mentioned above, the landmarks can be fetched dynamically as needed by combining the start and end values from the MTCProof. The LDP server fulfilling these requests will need to parse the start and end values, aggregate the require landmark subtrees together, and send the responce back to the client. The responce format will be:¶

TODO: DEFINE responce format¶