Subject: Re: Comments on Path Building I-D

From: "Wen-Cheng Wang" <[email-masked]>
Date: Wed, 5 May 2004 19:26:29 +0800

Dear List,

After reading the certpathbuild draft and the comments
from Steve Hanna, my feeling is that this draft is more
like a paper (or thesis) than a PKIX specification. I believe
that is why Steve criticized the text of the draft as if he is
a reviewer of a PKI paper. I really admire the authors and
Steve's rich and deep knowledge of optimization and
implementation technique for path building. I must confess
that I gained much from reading "the paper" and the
comments from Steve. However, I doubt whether it is
suitable for the PKIX WG to publish "the paper" as an RFC.
I think the text of the draft is good enough to become a
paper on a PKI conference proceedings or even  on a journal.
But, that does not mean it will be a good PKIX RFC.

As a faithful reader of PKIX specifications, I would expect that
if the PKIX WG would like to publish an RFC entitled
"Certification Path Building" then its text should focus on:

1. defining what is a legal certification path
           Can certificates with names in different encoding be chained?
           Can certificates with unmached issuer name and subject name
           be chained by matching SKID and AKID?
2. defining a algorithm for certification path building, also including
         specifying the inputs to the algorithm and
         specifying the outputs from the algorithm
3. specifying the format of certificate/CRL extensions (e.g. SKID, AKID,
    AIA, SIA, CRLDP...) that are related to certification path building.
    E.g.,
           the URL format of different procols (such as LDAP, HTTP, FTP...)
                (e.g., Should the LDAP URL contains the ";binary" option?)
4. specifying how a compliant implementation should process
    theose certificate/CRL extensions related certification path building
5. specifying what is the minimum set of repository retrieving protocols
    (such as LDAP, HTTP, FTP, SMTP...) a compliant implementation
    sould support and how these protocols should be supported. E.g.,
               What is the expected object format?
                    (e.g., DER binary vs.Base64-encoded)
               What is the expected MIME type if HTTP is used?
6. discussing security consideration

I believe that the PKIX certpathbuild specification should specify a
baseline certification path building algorithm in the fashion of RFC
3280 specifying a basic certification path validation algorithm. The
purpose of defining the algorithm is for precisely describe the
expected result of the certification path building. There is no need for
a PKIX specification to teach implementators the optimization and
implementation technique for path building. It is up to the
implementators themselves to choose their own the optimization and
implementation technique. Isn't it?

Therefore, I would like to suggest the authors to complete remove the
section 3 of the current draft. It is not only because a PKIX specification
is not supposed to be a paper or textbook for teaching the optimization
and implementation technique for path building, but also because the
optimization and implementation technique described in that section is
not, as Steve said, the consensus of the PKIX WG. I suggest that the draft
sould spend more space and time to cover the areas I mentioned above.
(I know the current draft already covers them, but I think it is still not
in-depth enough.)

Wen-Cheng Wang

----- Original Message ----- 
From: "Steve Hanna" <[email-masked]>
To: "PKIX List" <[email-masked]>
Sent: Wednesday, April 28, 2004 9:53 PM
Subject: Comments on Path Building I-D

> Here are my comments on draft-ietf-pkix-certpathbuild-03.txt.
> 
> I suspect that these will come off sounding negative.
> I'm sorry about that. I'm glad we have this document
> and I hope it will progress in a modified form, but
> I have some serious problems with the document as
> it now stands.
> 
> I also apologize for the length of these comments.
> I wanted to do a careful review of the document
> and there are a lot of problem areas (although
> some are minor). The fact that nobody else has
> commented on these leads me to suspect that nobody
> except the authors and myself has carefully reviewed
> the document. Can anyone refute that suspicion?
> 
> Thanks,
> 
> Steve
> 
> --------
> 
> Overall Comments:
> 
> * My main overall comment is the one I made last July.
>    There is not consensus on path building techniques
>    in the PKIX working group or the IETF. Why? Because
>    we don't understand the problem thoroughly yet.
> 
>    In this document, you advocate depth first search
>    and suggest that building forward is usually best.
>    I don't think you have carefully considered a wide
>    variety of other algorithms like breadth first search,
>    meet in the middle, etc. Can you show me any solid
>    evidence that shows your algorithms are better than
>    the alternatives?
> 
>    I doubt that you have any such proof. In fact, it
>    seems clear to me that depth first search is a poor
>    algorithm for building cert paths. I say this as a
>    person who has implemented that algorithm myself
>    and regretted it. The problem is that if you make
>    a wrong choice, you must completely explore that
>    part of the PKI before you consider backing out
>    and trying other options. I have heard stories of
>    path building taking 35 minutes or more when there
>    was a valid short path because the builder used
>    DFS and headed down the wrong path.
> 
>    We need to do our homework before making any solid
>    recommendations to implementers. I suppose it's better
>    to have some advice than none, but this document
>    should have a prominent warning that these techniques
>    are experimental. In fact, we might want to give
>    the RFC Experimental status.
> 
>    As I've suggested before, I want to see a careful
>    analysis of different path building strategies.
>    Theoretical analysis will probably be useful,
>    but I expect it will also be useful to compare
>    real-world performance with a variety of topologies
>    (some from real-world deployments, some looking at
>    possible futures like many cross-certified bridges).
>    We need to try out a lot of ideas without getting
>    committed to any too early. The cert path building
>    panel at the PKI R&D Workshop this year was a good
>    start, but we need to do more in-depth work. I've
>    started talking to some other researchers about this.
>    I hope that this documents' authors will join this
>    effort. Their experience and aid will be valuable.
> 
> * At several places in the document, you refer to the
>    "authors' opinions". If this was truly a working
>    group document, it would reflect the consensus of
>    the working group, not the opinions of the authors.
>    As I said before, I don't see working group consensus
>    on this topic. Has anyone other than me (and maybe
>    the authors) carefully reviewed the current draft?
>    I haven't seen any comments on it during Last Call.
> 
>    Since this document does not reflect working group
>    consensus, I do not think it should go forward
>    as a working group draft. It should be an individual
>    submission. But I suppose once it becomes an RFC
>    nobody will ever know whether it was a working group
>    submission or not. And I really do think it's useful
>    to have some guidance on cert path building (even if
>    we don't understand the problem very well). So I'd be
>    OK with having it be a working group submission if it
>    goes to Experimental status and a caveat is added
>    at the beginning warning that this is only the authors'
>    opinion (albeit an educated opinion) and that further
>    study is under way to determine which techniques are
>    actually preferred.
> 
> * You should include in this document a section with
>    guidance to PKI designers about what they can do to
>    make path building easier. Here are some ideas:
> 
>    Use a simple topology (hierarchical with one root),
>    when possible. Include AIA, SIA, and CRLDP extensions
>    in certificates. Make certificates (especially CA
>    certificates) and CRLs easily available by LDAP and
>    HTTP, populating both sides of the crossCertificatePair
>    attribute. Use name constraints and policy constraints
>    whenever possible, especially at high fanout points
>    like bridges. Avoid having more than two high fanout
>    CAs (at most) between any two points, if possible.
> 
> * I have a *serious* objection to the idea that someone
>    is going to specially configure path building software
>    for a particular PKI environment (as I think you imply
>    at the end of section 2.3, early in section 3.4, and in
>    a few other places). This is not practical. Most
>    organizations do not have a PKI wizard on staff
>    (especially a path building wizard). The path building
>    software must just work, automatically. If we can't do
>    that, PKI will never be widely used (at least, not in a
>    non-hierarchical topology). Fortunately, I see no reason
>    why we need special configuration. With AIA and SIA and
>    CRLDP and some good algorithms, we should be able to
>    build paths just fine in almost any PKI without any
>    configuration.
> 
> Substantive Comments:
> 
> * Section 1.2 (Purpose) says "... this document suggests
>    using ... depth first tree traversal. ... Other approaches
>    (e.g., building complete spanning trees of the PKI.) exist
>    and may be shown to be more effective under certain conditions."
> 
>    Building a complete spanning tree of the PKI is not a
>    decent solution. Please change this to something more
>    reasonable, like breadth first search. Otherwise, you're
>    just setting up a straw man, an impractical alternative.
> 
> * In section 1.4.1, you mention one disadvantage of the trust
>    list approach. You might want to mention the problem that
>    compromise of any trusted certificate compromises the
>    entire system.
> 
> * In section 1.4.2, you say that a partial mesh is a mixture
>    of unidirectional and bidirectional cross-certifications.
>    It's probably also important to note that in a partial mesh
>    there may be CAs that are not directly cross-certified at all.
> 
> * What is a Root CA doing in Figure 3? As you say, each EE
>    in a mesh usually trusts the CA that issued its certificate.
>    Because of this Root CA, Figure 3 does not depict a full mesh,
>    as stated in 1.4.2. I suggest that you remove the Root CA.
> 
> * At the end of section 1.4.3, you raise the concern that
>    the assurance of a high-assurance PKI may be diluted by
>    cross-certifying with a less restrictive PKI. If you're
>    going to raise this concern, you should mention that it
>    can be addressed through the use of certificate policies.
> 
> * At the end of section 1.4.4, you say that connecting
>    PKIs with a bridge results in a non-hierarchical PKI.
>    Certainly, this is true. But mesh and hybrid PKIs are
>    not hierarchical either. Why raise this here? And the
>    following sentence which states that any PKI can be
>    considered hierarchical from the right perspective
>    only applies if you remove and duplicate links in the
>    PKI. Since you don't have space to get into this here,
>    I suggest you remove those last two sentences.
> 
> * At the end of the first paragraph of section 2.1, you
>    explain that S/MIME messages commonly include certificates.
>    I think you would be wise to also mention SSL/TLS
>    since this is the most widespread use of PKI and it
>    also supplies certificates in the protocol.
> 
> * Before Figure 6, you explain how certificates are
>    depicted with arrows in your figures. You should also
>    explain the "B(A)" notation you use.
> 
> * At the end of the paragraph after Figure 6, you say
>    that building paths is as important as validating them.
>    I don't agree. Many products have been shipping for
>    years and work just fine without building. In a complex
>    PKI, building is important. But in a simple hierarchical
>    PKI, it's not.
> 
> * At the end of section 2.1, you have a large discussion
>    of why you believe building forward is usually better.
>    This duplicates later discussions on this topic. I suggest
>    you save this for later.
> 
> * In section 2.2, you could simplify and clarify Criterion 1
>    by changing it from this:
> 
>     Criterion 1: The implementation is able to find all possible paths.
>     By this, it is meant that all possible certification paths between
>     the trust anchor and the target certificate which may be valid paths
>     can be built by the algorithm.
> 
>    to this:
> 
>     Criterion 1: The implementation is able to find all possible paths.
>     By this, it is meant that all valid certification paths between
>     the trust anchor and the target certificate can be built by the
>     algorithm.
> 
> * In section 2.2, Criterion 2 seems rather odd. Who cares which
>    invalid paths you build first? The important thing is how quickly
>    and efficiently you can build a valid path or determine that
>    no valid path exists.
> 
> * In section 2.3, you say that because certificates are not
>    permitted to repeat, every potentially valid path has a
>    terminus. But every potentially valid path *always* has
>    a terminus, even if certificates are allowed to repeat.
>    As defined in RFC 3280, a certification path is a collection
>    of n certificates. Every path has a finite number of certificates.
>    I suggest you remove the sentence "As a result, every potential
>    valid path has a terminus, a leaf on the tree."
> 
> * In the following paragraph, you say that removing and
>    duplicating nodes and links in a PKI to turn it into
>    a hierarchy greatly simplifies software design. This
>    may be so, but it also removes many opportunities for
>    insight and optimization. For example, it increases
>    the number of nodes in the data structure and makes it
>    harder to mark a certain area of the PKI as unproductive
>    (since that area may appear several places in the tree).
> 
> * Later in that paragraph, you use the phrase "decision tree"
>    without defining it. I suggest that you define it in
>    section 1.3.
> 
> * One paragraph on page 16 (starting with "A more complicated
>    example") talks about problems with building in the
>    reverse direction when there are many trust anchors.
>    The real issue here is fanout. Whether you're building
>    forward or building reverse, it's bad news when you get
>    to a point where you have several choices. It's especially
>    bad if your heuristics (ranking) don't give you much
>    help in deciding which way to go. And it's even worse
>    if you're using depth-first search, since one wrong
>    move can send you off in the wrong direction for hours.
>    That's why I suggest breadth first search or (even
>    better) ranking all candidates at all points in
>    the tree at each decision time.
> 
>    Four trust anchors is a four-way fanout. A similar
>    situation would arise if you were building forward
>    and arrived at a CA that has four certificates with
>    it as the subject. In either case, you hope that your
>    ranking will help choose the right path. And if you're
>    using depth first search, you really hope that you
>    don't take a wrong turn. One technique for dealing
>    with extreme fanout with fairly equal rankings is to
>    start building from the other end. Another is to rank
>    the certs at the fanout point low and try another branch.
>    A third is to use DPD to get help. And a fourth is to
>    tell PKI designers to use name constraints and other
>    techniques at high fanout points (like bridges) to
>    help path building succeed.
> 
>    I hope that you find this analysis useful.
> 
> * In Figure 10, are W, X, Y, and Z all trust anchors?
>    I think so. That's pretty odd. Why would a relying
>    party have all four of those trust anchors? Who needs
>    the bridge CA in that case? I suspect that this
>    topology was created to support your arguments that
>    repeating a (name, key) pair is bad and that building
>    in reverse is bad. If so, I think you can do better.
> 
>    Let's do a careful theoretical analysis and try
>    out different algorithms on different topologies.
>    I suspect you're right that repeating a (name, key)
>    pair is bad but we need to think about this carefully
>    since it is a significant change to RFC 3280. I think
>    you will see below that building in reverse is a
>    useful tool that should be used in conjunction
>    with building forward. But we need to show the
>    merits of our approaches through analysis, not
>    by consructing topologies that serve our own purposes.
> 
> * In the paragraph after Figure 10, you have several
>    sentences explaining the diagram's notation. This
>    was explained much earlier. The rest of the paragraph
>    (explaining where certificates would be stored in
>    an LDAP directory) also duplicates material found
>    elsewhere. I suggest that you remove these, since
>    the document is already too long.
> 
> * In section 2.4.2, you seem to be proposing that
>    software should build a decision tree. I believe
>    you don't intend for the software to actually
>    build a tree for the entire PKI but only to
>    move incrementally through the PKI adding nodes
>    and links to the tree as needed. I hope that's
>    the case, anyway. Otherwise, you'd need to
>    download all certs in the PKI! If I'm right,
>    you need to be much clearer about this. I could
>    easily imagine a developer writing code that
>    actually builds the tree. That code would
>    work fine in a small test PKI but flood the
>    directory with requests and then die in a
>    large PKI.
> 
> * After Figure 11, you point out that building
>    in reverse is not good in this case. Sure.
>    The EE is in a simple hierarchy. Of course,
>    building forward is best there. If you don't
>    know the topology (especially if you have
>    several trust anchors), starting with forward is
>    fine. Then you can switch or meet in the middle
>    if things get hairy.
> 
> * In section 2.6, you say "[...] the path builder
>    only needs to store the current location in
>    the tree [...] All completed branches can be
>    discarded from memory [...]". Maybe. There's
>    a lot to be said for retaining records of
>    paths you have already tried and rejected.
>    Then you can avoid retrying them at a different
>    point in the graph (unless conditions are
>    sufficiently different to merit a retry).
> 
> * Later in section 2.6, you say "Consider HTTPS
>    support" for CRLDP and AIA. Why would this be
>    valuable? You're retrieving signed data. Using
>    HTTPS may trigger another path build, maybe
>    even a loop where one build triggers another
>    which triggers another and so on. I suppose
>    some repositories may require HTTPS to
>    authenticate the client or protect the
>    certs from prying eyes. But you should probably
>    warn that doing so may be expensive and that
>    implementers should protect against loops.
> 
> * Toward the end of section 2.6, you talk about
>    the path cache. You call for "a configurable
>    expiration date for each entry". Who would
>    configure the date and why? I'm a path building
>    geek and I can't imagine configuring such a
>    thing!
> 
> * A few sentences later, you suggest storing
>    issuer-subject cert relationships. If you
>    want to do this, I suggest that you use a
>    cert hash instead of an (issuer, serial)
>    tuple. Issuer, serial is *not* always unique,
>    especially across multiple PKIs or when
>    one CA is malicious (and remember that some
>    CAs are only partly trusted in a modern PKI).
> 
> * In section 2.7.1, you talk about the required
>    inputs. Instead of supplying the actual Target
>    Certificate, it is sometimes useful to provide
>    criteria that describe what sorts of target
>    certificates you're willing to accept. For instance,
>    when doing S/MIME encryption to a new correspondent
>    you may not have the correspondent's encryption
>    certificate. The path building software can
>    help find it if you tell it what you need.
> 
> * In section 3.2, you recommend that path building
>    software output a detailed log. I think you should
>    recommend that this log be carefully structured
>    so that the paths tried can be easily reconstructed
>    by a diagnostic program. My team built a tool that
>    shows the cert graph and then replays the paths
>    our builder tried, lighting up each one in sequence.
>    We found this a great help in understanding the behavior
>    of our software (finding bugs, improving algorithms,
>    etc.). It's also a very cool way to demo path building,
>    which otherwise is a pretty boring demo ("see, there's
>    the web page!").
> 
> * Later in that paragraph, you say "Ideally, there would
>    be a mechanism for turning this logging on and off [...]".
>    I'd change this to "There should be [...]". Logging is
>    expensive (in storage and CPU time), especially for path
>    building where you commonly try hundreds of certificates
>    or more to create a valid path. You really need a way to
>    turn logging off and on.
> 
> * A few paragraphs later, you say "it may be useful to
>    not rule out any paths" and just return each path as
>    its built, even if it's invalid. The problem with this
>    is that (especially with a depth first search) is that
>    there are many topologies that may cause you to wander
>    among many invalid paths. Why is this technique good?
>    You say it will "provid[e] a more rapid response to the
>    caller than one which builds all possible paths." Maybe.
>    I suspect you'll instead waste time by spending a lot
>    of time returning invalid paths to the caller. I don't
>    see much reason to return invalid paths except in a
>    diagnostic log or for your interesting idea of providing
>    one path that's *mostly* valid for debugging and in case
>    the caller finds that invalid path educational or compelling.
> 
> * A few paragraphs later, you lay out your approach.
>    Here are some comments on it:
> 
>    You say "Do not check revocation status if it requires
>    a directory lookup or network access." Why not start the
>    revocation check and let it run in parallel while you do
>    other things (like checking certs deeper in the graph)?
>    That way, you'll have the revocation check done when you
>    need it. And if the check fails you can abort all work
>    that was based on the validity of that certificate.
>    Of course, you'll want to cache the revocation status
>    of certificates for some time.
> 
>    You say "Do not check digital signatures". Again, why
>    not run this in parallel? Most of path building time
>    (about 90%, based on our data) is spent waiting for
>    the network (while downloading certificates and such).
>    That's an ideal time to be checking signatures. And,
>    of course, you'll want to cache the results of signature
>    checks.
> 
>    You say "Do not check anything that can not be checked
>    as part of the iterative process of traversing the tree."
>    Why not? I expect you would want to run these final checks
>    (like full policy processing when building forward) before
>    returning the path to the caller. Otherwise, the caller
>    will need to run a complete validation of the path, which
>    will take much more time than just running these last
>    few checks.
> 
> * In the last paragraph of 3.2, you say "Second, it is fairly
>    uncommon in typical application environments to encounter
>    a revoked key; therefore, most certificates validated will
>    not be revoked." In a PKI, we don't revoke a key. We revoke
>    a certificate. Therefore, this sentence should read "Second,
>    it is fairly uncommon in typical application environments to
>    encounter a revoked certificate."
> 
> * Why include section 3.3 at all? It's very odd to have
>    an IETF spec talking about internal data structures.
>    Maybe you should just give everyone a copy of your
>    code (since it is apparently ideal) and save them the
>    trouble of implementing it! I'm going to skip my more
>    detailed comments on this section since I think it
>    should be entirely removed.
> 
> * In section 3.4, you refer say "developers should evaluate
>    each method with respect to the environment that the
>    application will operate, and assign weights to each
>    accordingly in the path building software.". First, the
>    word "that" in this sentence should be "in which". Second,
>    this is a prime example of the awful idea that developers
>    must examine each PKI and configure their software to
>    run optimally there.
> 
> * In section 3.5.1, you say "According to [RFC 3280],
>    basicConstraints is required to be present with cA=TRUE
>    in all CA certificates." Actually, section 6.1.4 (k) of
>    RFC 3280 says "Verify that the certificate is a CA
>    certificate (as specified in a basicConstraints extension
>    or as verified out-of-band)." Maybe your software doesn't
>    make any provision for out-of-band indication of CA
>    certificates, but you should probably at least note the
>    possibility that other software may do so.
> 
> * In section 3.5.5, you say "Certificates in the path cache
>    have been validated previously. There is some probability
>    that the path from that certificate to a trust anchor is
>    still valid." The path may still be valid but it may
>    contain constraints that are inconsistent with the
>    path from the Target Certificate to this certificate.
>    You should probably note that possibility.
> 
> * In section 3.5.6, you say that the Previously Verified
>    Signatures sorting method doesn't apply when building
>    in reverse. Actually, it does. Your analysis is incorrect.
>    This method never tells you which way the Target or
>    Trust Anchor is (which certificate is most likely).
>    It only lets you rule out certificates because the
>    signature check would certainly fail.
> 
> * In section 3.5.7, you say the Path Length Constraints
>    sorting method "may be applied in reverse, but the
>    benefit is likely less than that of the forward direction".
>    Why? You can argue that the method is more effective
>    when building in reverse because path length constraints
>    often appear close to trust anchors.
> 
> * In section 3.5.8, you say "Certificates that contain
>    nameConstraints that would  be violated by certificates
>    already in the path to this point are given lower priority
>    (or perhaps eliminated)." They should definitely be
>    eliminated. You know they can't be used to build a
>    valid path, so what's the point (unless you're working
>    on building an invalid path)?
> 
> * In section 3.5.9, you say "While this is viable, the
>    signature verifications required make it less attractive
>    as an elimination method." Usually, a CRL check only
>    requires one signature verification so "verification"
>    should be singular.
> 
>    You also say "It is suggested that this method only
>    be used for sorting and that CRLs are validated post
>    path building." As I noted above, fetching CRLs and
>    performing signature checks can be done in parallel
>    with other work. It's a good idea to do this so that
>    you can discover revoked certs before you have invested
>    too much time in them (and also so that you have the
>    results of the revocation check ASAP).
> 
>    You should also probably change this section to include
>    discussion of OCSP. Right now, it's very focussed on
>    CRLs.
> 
> * Here's a sorting method similar to the "Issuer Found
>    in the Path Cache" method, but better suited to building
>    in reverse. Check whether the subject of the candidate
>    certificate matches the issuer of a certificate sent
>    by the target (in SSL/TLS, S/MIME, etc.). If so, then
>    the candidate certificate should be ranked more
>    highly because it is more likely to lead to a path
>    to the Target Certificate. You may also want to do
>    RDN Matching (as in 3.5.15) with the certificates
>    sent by the target.
> 
> * In section 3.5.15 (on RDN matching), you say "Additionally,
>    it should be noted that this method can require a lot of
>    processing if many trust anchors are present." Actually,
>    this should only require a few hash table lookups (of the
>    RDNs).
> 
> * Section 3.5.18 could be clearer. I think you're saying
>    that the subject and issuer of the candidate certificate
>    should have lots of RDNs in common. But this could be
>    understood to be saying that the subject of the
>    candidate certificate should have lots of RDNs in common
>    with the issuer of the next certificate. Of course,
>    they must match exactly so that can't be what you're
>    saying. But it would help if this section was more
>    explicit.
> 
> * Section 3.5.19 also should be clarified. The description
>    of the reverse method is much clearer than that of the
>    forward method. I suggest that you replace the forward
>    method language with language based on the reverse method
>    language. One change to the reverse method language, though.
>    Instead of saying "If an entity named by a reverse certificate",
>    say "If the subject of a certificate". There's no such
>    thing as a "reverse certificate".
> 
>    Note also that just because you find a name in the
>    certificate cache, that doesn't mean you have the
>    right certificates. There may be several different
>    CAs with the same name. Also, you may now have more
>    clues (like AIA and SIA) for finding certificates
>    than you had before. You should be sure to pursue
>    any such new clues.
> 
> * In the Justification for 3.5.19, you say "The presence of
>    required directory values populated in the cache increases
>    the likelihood that all the required certificates and CRLs
>    needed to complete the path from this certificate to the
>    trust anchor (or target if building in reverse) are present
>    in the cache from a prior path being developed [...]".
>    That's fine, but you might also want to keep the actual path
>    previously developed and look at that as a prime candidate
>    for the path this time.
> 
> * In section 3.5.20, you use the presence of a CRL in
>    the CRL cache to indicate whether a complete path
>    through a CA has previously been found. This is
>    rather indirect. It would be better to actually
>    track which certs have been previously included
>    in valid paths. Keeping a copy of the path would
>    also be quite useful.
> 
> * The discussion of Forward Policy Chaining in section 4
>    overstates the benefits of policy checks when building
>    in the forward direction. We should discuss this more.
> 
> * In section 5.2, you suggest that each name/key pair
>    only be allowed to appear once in a path. Since there
>    is no such requirement in X.509 or RFC 3280, this
>    would violate Criterion 1 as stated in section 2.2.
>    You would miss some valid paths.
> 
> * In section 6 (Retrieval Methods), you should mention
>    getting certificates and CRLs from the target (with
>    S/MIME or SSL/TLS, for instance). That's a *great*
>    way to get certificates and CRLs. The ones you get
>    are usually highly valuable.
> 
> * Sections 6.2 and 6.3 should include text that encourages
>    implementers to support AIA and SIA, especially HTTP.
>    This text from the end of section 6.4 could easily
>    be adapted:
> 
>        However, implementers of path building
>     and validation modules are strongly encouraged to support CRLDPs.  At
>     a minimum, developers are encouraged to consider supporting the LDAP
>     and HTTP transports; this will provide for interoperability across a
>     wide range of existing PKIs.
> 
> * In section 7, you should talk about prefetching and
>    parallel fetching. Both are good ways to improve the
>    performance of a cert path building implementation.
> 
> * In section 7.1, you say "Certificate processing systems can
>    cache data retrieved from external sources for some period
>    of time, but not to exceed the useful period of the data
>    (i.e., an expired certificate need not be cached)." CRLs
>    are often issued well before the nextUpdate of the previous
>    CRL. Could you mention this and suggest that implementers
>    check periodically for updated CRLs? Similarly,
>    crossCertificatePairs may be updated on an unpredictable
>    basis. If you don't check back every so often, you'll
>    never know that a new cross certificate is available!
> 
> * The last bullet in section 7.1 offers a few suggestions
>    for other things to cache. I'd add to that list previously
>    built paths and partial paths. If the cache is safe from
>    unauthorized modifications (as with an in-memory cache),
>    you may also want to cache validation and signature check
>    status for certificates and CRLs.
> 
> * In section 7.2 (Retrieval Order), you may want to consider
>    checking repositories in parallel instead of serially.
>    Also, you might want to run ahead with your path building
>    and validation while a network query is ongoing. Maybe
>    you can build and validate the path with just the certificates
>    and CRLs you have already (thus eliminating the need to
>    wait for the network query to complete). Anything to get
>    the answer to the user more quickly!
> 
> * In section 8.1, you should probably add a statement that
>    path building can be used as a denial of service attack.
>    Make a series of simple requests to a server and cause it
>    to do a bunch of long path builds. To avoid this, the
>    server can limit the amount of resources it's willing to
>    devote to a path build. This amount can be reduced when
>    the load is heavy. And standard DOS protections like
>    identifying attackers can be employed.
> 
> * Section 8.2 goes way beyond RFC 3280 and X.509. I know
>    that Santosh is working on getting this into X.509 and
>    the successor to RFC 3280. I'll debate the specifics
>    of his proposal in that context. But for this document,
>    I think you should be careful to explain that this goes
>    beyond the standards. If you implement it, you will
>    violate Criterion 1 from section 2.2. Maybe the best
>    thing to do is to just briefly point out that there's
>    an issue here and it's under discussion in the standards
>    groups. Once it's settled there, this document can be
>    revised to reflect whatever's agreed on.
> 
> Minor Comments:
> 
> * The first paragraph of section 2 says "... guidance is
>    provided on the capabilities path building implementations
>    required in order to ...". I think you want "require" or
>    (maybe better due to RFC 2119) "need" instead of "required".
> 
> * Just below Figure 6, "the certificates cannot be validated"
>    should be "certificates cannot be validated". You're not
>    referring to any particular certificates, just certificates
>    in general.
> 
> * In the paragraph after that, you should say "the
>    crossCertificatePair attribute" instead of "the cross
>    certificates". Otherwise, it's not clear what you mean.
> 
> * In the second paragraph of section 3.2, you say a
>    certificate "may appear again on another point in
>    the tree". That should be "at another point in
>    the tree".
> 
> * At the end of section 3.4, "The list" should be "the list".
> 
> * In section 3.5.17, there are two typos. "it priority"
>    should be "it has priority". "will not successfully"
>    (in the last paragraph) should be "will not verify
>    successfully".
> 
> * In section 5.4, you say certificates "will be" required
>    to use UTF-8 after January 1, 2004. This should now
>    be changed to "are".
> 
> * In section 6, the first sentence should mention CRLs
>    also. I suggest that the second sentence say "obtaining
>    these certificates and CRLs" instead of "performing
>    this retrieval", since retrieval has not yet been
>    mentioned and sometimes the certificates can be
>    obtained without having to be retrieved (as when the
>    EE sends them in SSL).
> 
> * In section 6.1, the description of userCertificate
>    should probably say that it "contains certificates
>    issued by one or more certification authorities with
>    a subject DN that matches that of the directory entry".
>    Also, there's an extra period at the end of the
>    parenthetical comment later in the paragraph.
> 
> * Later in section 6.1, the description of issuedByThisCA
>    should say it contains certificates issued to *other*
>    CAs. And there's an extra comma after "If both elements
>    are present" (later in that paragraph). Why include that
>    sentence anyway. The relying party doesn't need to
>    enforce this requirement. People may think they need
>    to do so.
> 
> * In section 6.2, you say "AIA may be used to retrieve one or
>    more certificates for entities that issued the certificate
>    containing the AIA extension." I think it would be clearer
>    to say "the CA" instead of "entities".
> 
> * At the end of the first paragraph of section 6.3, "AIA"
>    appears twice where it should be "SIA".
> 
> * In section 6.4, you say "the CRL(s) to which the CRLDP(s) refer
>    is the CRL that would contain revocation information for the
>    certificate." I'd say instead "the CRL(s) to which the CRLDP
>    refers are generally the CRLs that would contain revocation
>    information for the certificate." Why? Because a CRLDP may
>    refer an LDAP directory entry that contains many CRLs. Some
>    of them may not pertain to this certificate. And of course
>    there's usually only one CRLDP in a certificate.
> 
> * In section 8.2, "q CRL Signer" should be "a CRL Signer".
> 
> * In the Informative References, you include "[MINHPKIS]"
>    but it's never actually referred to anywhere in the document.
>    Similarly for [X.501] and [X.520]. You should probably
>    remove those references. If you're going to retain them
>    for some reason, please provide a decent reference for
>    [MINHPKIS]: publisher, publication date.
>

---

From: "Peter Hesse" <[email-masked]>
Date: Mon, 17 May 2004 11:23:45 -0400

Wen-Cheng,

I will reply to your comments inline.

> After reading the certpathbuild draft and the comments from Steve 
> Hanna, my feeling is that this draft is more like a paper (or thesis) 
> than a PKIX specification. I believe that is why Steve criticized the 
> text of the draft as if he is a reviewer of a PKI paper. I really 
> admire the authors and Steve's rich and deep knowledge of optimization 
> and implementation technique for path building. I must confess that I 
> gained much from reading "the paper" and the comments from Steve. 
> However, I doubt whether it is suitable for the PKIX WG to publish 
> "the paper" as an RFC.
> I think the text of the draft is good enough to become a paper on a 
> PKI conference proceedings or even  on a journal.

This document is meant to serve as an informational document which
implementers can read and use to make intelligent decisions when building
their own implementation.  Unlike most PKIX RFCs, which are standards-track
RFCs, this document is not intended to be prescriptive.  If you read RFC
2026, section 4.2.2 about Informational RFCs, I believe you will agree that
this document fits the mold of an Informational RFC quite well.

> As a faithful reader of PKIX specifications, I would expect that if 
> the PKIX WG would like to publish an RFC entitled "Certification Path 
> Building" then its text should focus on:
> 

These issues are covered in the document, and both have been brought up on
this list as recommended additions to RFC 3280.

>          specifying the outputs from the algorithm

As I mentioned above, an informational RFC should not be so prescriptive

> 3. specifying the format of certificate/CRL extensions (e.g. SKID, 
> AKID,AIA, SIA, CRLDP...) that are related to certification path 
> building.
>     E.g.,

These extensions are already specified in RFC3280.  The specifics of the
formats of these values may be best captured in a "best-practices" document
which I have suggested (in my response to Steve) as an additional document
to be considered by the group.  Aside from the restrictions identified in
section 4.2.1.7 of RFC3280, I do not think the values can be constrained any
further.

>     theose certificate/CRL extensions related certification path 

Again, this is specified by RFC3280, our document makes no attempt to change
the way any extensions or fields are processed, nor should it.

>5. specifying what is the minimum set of repository retrieving  
>protocols (such as LDAP, HTTP, FTP, SMTP...) a compliant  
>implementation sould support and how these protocols should be  
>supported. E.g., What is the expected object format?

Again, this is best suited for a "best-practices" document.  There need not
be any minimum set of protocols defined as a standard, but a list of best
practices could give guidance on what protocols were most commonly used.

> expected result of the certification path building.

RFC3280 section 3.2 has identified a starting point, which is a
certification path.  We have provided a way to get from nothing to obtaining
that certification path, after which time you can perform validation; a
procedure that RFC3280 is silent on.  There cannot be a basic algorithm for
building defined as a PKIX standard, because this would make any algorithms
not designed in this fashion non-standard.  RFC3280 section 3.2 provides
enough to give us the basic algorithm.
 
> There is no need for a PKIX
> specification to teach implementators the optimization and 

Yes, it is up to the implementors.  Our document provides a recommendation
on what makes a good path builder, with example scenarios and an example
implementation.  All throughout, the document makes it clear that the
implementor can take or leave any of the suggestions.

> section 3 of the current draft. It is not only because a PKIX 
> specification is not supposed to be a paper or textbook for teaching 
> the optimization and implementation technique for path building, but 
> also because the optimization and implementation technique described 
> in that section is not, as Steve said, the consensus of the PKIX WG.
> I suggest that the draft sould spend more space and time to cover the 
> areas I mentioned above.
> (I know the current draft already covers them, but I think it is still 
> not in-depth enough.)

As I mentioned above, I believe that RFC3280 already covers the majority of
these issues, and in addition, a new document may be created to provide
guidance on the best practices of certification path development utilities.
As I mentioned in my message to Steve, I would be happy to collaborate on
such a document.

--Peter

+---------------------------------------------------------------+
| Peter Hesse                    [email-masked]     |
| Phone: (703)934-2031         Gemini Security Solutions, Inc.  |
| ICQ: 1942828                     www.geminisecurity.com       |
+---------------------------------------------------------------+
"Pay no attention to what the critics say; there has never been a statue set
up in honor of a critic." --Jean Sibelius