Subject: RE: Comments on Path Building I-D

From: "Peter Hesse" <[email-masked]>
Date: Mon, 17 May 2004 16:41:10 -0400

Steve,

<resending because I exceeded the PKIX list size limit...>

Thank you for your in-depth reading of the document and the large number of
comments.  I will attempt to address the majority of them in this message.
I apologize for the time it has taken me to respond.

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

We do understand the problem.  The problem is a traditional graph theory
problem.  The only new part of the problem as it relates to PKI is how to
define the penalty function.  We have defined heuristics that make sense for
PKI.

I'm not sure that this is a reason to prevent this document from
progressing.  This document is based upon the best research we have to date,
which includes real-world experience with operational PKIs and users.  If at
a later time, there is additional research performed, and new conclusions
are reached, then the obvious recommendation would be to update the draft.
Until that time, I do not think it is useful to withhold this document.
 
> 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?

Yes and no.  I can generate a set of PKI structures which will make this
algorithm work best, just as you could generate a set of PKI structure which
would make another algorithm work best.  Until there are useful real-world
examples to test against which demonstrates one approach is generally better
than another, such evidence would be questionable.  The methods described in
the draft have been used in real-world PKIs with success.
 
> 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.

Certainly these are horror stories, and if the path-building software
consistently took 35 minutes to develop a path, it would not be in use
today.  In the document, we advocate finding a valid path fastest to prevent
such a thing from occurring.  

There may be ways to optimize building so that a valid path is even more
likely found first across a wider range of conditions than the approach we
described.  However, this is a balancing act between complexity for
implementers, performance, and functionality.  We may be able to design an
exceedingly complex (to implement) algorithm that almost always yields best
performance and allows for every conceivable scenario, but no one would want
to (or be able to) implement it.

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

We (as authors) have influence but no control as to whether the document
heads down standards, informational, or experimental tracks.  We have
requested informational status, but the IESG can decide whatever they wish.
I truly feel that this document is Informational, it provides potential
implementers with information that they can use when they are creating their
own implementation; it provides little in the way of strict recommendations.
Note the following snippets of RFC2026:

4.2.1  Experimental

   The "Experimental" designation typically denotes a 
   specification that is part of some research or development 
   effort. [...]

4.2.2  Informational

   An "Informational" specification is published for the 
   general information of the Internet community, and does not
   represent an Internet community consensus or recommendation.
   [...]

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

I agree with you and would also like to see additional research and analysis
performed in this area.  However, X.509 has existed in one form or another
since 1988 and there has never been any guidance for implementers on how to
build certification paths.  Now, 16 years later, we are offering to provide
a document with some guidance--a starting point at the least--for
implementers.  We should not wait any longer for additional research.

When new research brings something additional to light, this RFC can be
updated or replaced as warranted.
 
> * 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.

We did receive a significant number of comments from some other folks on
earlier drafts, and we have addressed those comments.  This document must be
based upon the opinions of the authors, because as I mentioned above, one
can always create a path which makes a particular algorithm operate well.
As the section from RFC2026 above, there is no problem with an informational
RFC where the judgment calls in the document are based upon the opinions of
the authors.

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

As I mentioned earlier, based upon RFC2026, I don't think that experimental
status is appropriate.  As far as a caveat at the beginning of the document,
we intended to have already performed that in section 1.2, Purpose:
  
# This document provides information and guidance for certification
# path building.  There are no requirements or protocol
# specifications in this document.  This document provides many
# options for performing certification path building, as opposed to
# one particular way to best perform certification path building.
# This document draws upon the authors' experience with existing
# complex certification paths to offer insights and recommendations
# to developers integrating support for [X.509] digital
# certificates into their applications.
#  
# In addition, this document suggests using an effective general
# approach to path building that involves a depth first tree
# traversal.  While the authors believe this approach offers the
# balance of simplicity in design with very effective and
# infrastructure neutral path building capabilities, the algorithm
# is no more than a suggested approach. Other approaches (e.g.,
# building complete spanning trees of the PKI.) exist and may be
# shown to be more effective under certain conditions.
# Certification path validation is described in detail in
# both [X.509] and [RFC 3280] and is not repeated in this document. 

> * 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 don't disagree with any of these suggestions, and I think that they are
appropriate for capture in a document.  I'm just not sure that this document
is the right place.  This is less of a path development issue and more of a
PKI architecture issue.  Therefore, I recommend that a separate document be
created to provide guidance to PKI implementers on how best to construct
their PKI so that path development routines have a good chance for success.
I would be happy to collaborate with you on such a document.

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

Again, I agree with what you have written here.  However, my practical
experience in this area is a reason for this implication being made.  With
no guidance, a path building implementer might be just concerned with
getting their software to work with the particular PKI they have been faced
with in testing.  This occurred a few times in early revs of the DoD PKI and
government-funded software.

Our goal as stated in the purpose section is an approach which "offers the
balance of simplicity in design with very effective and infrastructure
neutral path building capabilities."  Certainly a design can be simplified
if parts of the implementation are left out, because they will never be used
in the target infrastructure.  The end of our section 2.1 lists the reasons
why users might want to do this.  Additionally, as I mentioned above, one
can always come up with an algorithm that works best in their specific
environment.  While it may not be practical to expect, if there is enough
pressure to ensure that paths are built and validated in a timely fashion, I
can imagine it happening.

Oh, and two additional notes: CRLDP does not help in path development--just
for retrieving data needed for the path.  And, AIA does not help path
development any better than a populated LDAP directory does.  (If a issuer
has multiple certificates, either AIA will be underpopulated or you will
face the same dilemma in terms of which certificate to use to develop the
path.)

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

We will change this to a breadth first search.  Of course as we mention in
the document, in certain cases, this might be impractical as well.  (i.e.
forward cross-certificates not being present)

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

We will add this.

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

We will add this.

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

This was changed to be a root based upon a comment made by Denis Pinkas
stating that the diagrams were inconsistent.  I think I agree with you, it
is more confusing with the root in there.  We will change this.
 
> * 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.

We will add this.

> * 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?

This is mentioned because a lot of people look at a picture involving a
Bridge, and think of the Bridge as a root, and everything being subordinate
to it.  This is just another attempt to prevent that.

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

We already reference section 2.3 where we go into some more detail.

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

We will add this.

> * Before Figure 6, you explain how certificates are depicted 
> with arrows in your figures. You should also explain the 
> "B(A)" notation you use.

We will add an explanation to this section.

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

Even in a simple hierarchical PKI, some amount of building has occurred.
(OK, maybe not in a REAL simple example with one trust root and all target
certificates issued directly by it...)  Building is important.  If you don't
build a path, you can't validate a path.  It's just that building in certain
cases is so easy it doesn't even seem like you're doing any work.

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

We will shorten section 2.1 and provide a cross-reference to the end of 2.3
where we discuss this in more detail.

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

Yes, but I will propose changing it to (potentially) valid because I do not
necessarily want to burden path building software with having to also be
path validation software.  By potentially, I mean it is valid as far as the
builder can tell.  To some builders that is fully valid.  To others it may
still require a final sanity check/run through the validation procedure.
 
> * 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.

The purpose of this criterion is ensure that the users get meaningful
errors.  You want to build paths which are likely to be valid before you go
off and build paths which have a very low chance of success.  What is a
better error for a user to see, "name constraints violation at certificate
14" or "cert 3 revoked"?  We will try and word this a bit better to get that
point across.

> * 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."

Each path does have a terminus, once it becomes a path.  If certificates can
be repeated, the number of certificates in the path and the number of
possible paths both increase to infinity.  This is a wordsmithing issue that
may be able to be worded more clearly.  Perhaps we will change it to say "If
certificates could be repeated, loops can be formed such that the number of
paths and the number of certificates in a path both increase without bound
(e.g. A issues to B, B issues to C, and C issues to A.)"

> * 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).

We will remove "- this greatly simplifies software design." from the
sentence.

> * Later in that paragraph, you use the phrase "decision tree" 
> without defining it. I suggest that you define it in section 1.3.

We will add a definition for "decision tree".

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

I agree that this example may go into a little too much detail without
providing much benefit to the reader--we've done a good job of identifying
the problem but not at clearly identifying a solution.  I will try and
simplify the example, identify that the real enemy here is fanout, and that
to combat it, implementers should strive to use optimizations such as those
discussed in section 3.1 when there are a lot of choices at a particular
point of development. (By the way, this is p18 on my copy.)  

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

They are trust anchors for different relying parties, the trust anchors of
each of the PKIs which are cross-certified with the Bridge.  We will attempt
to make that clearer in the example.  In our example we are treating only W
as our trust anchor.

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

We have identified reasons why a (name, key) pair should not be repeated
within this document, and why building implementations should consider not
allowing them in section 2.4.2.  We have not attempted to change RFC3280
although I think we would have a decent argument for this, it is for a
different time and place.  

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

We will remove the duplication.
 
> * 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.

We will try and make this clearer.

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

As I mentioned before, one can always make an example that is good for a
particular argument!  In this case though, we don't say it is not good, we
say it is not possible, due to a lack of available certificates.
 
> * 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).

I agree with what you've written.  We have even some implementations that
mark a path as bad given a certain set of inputs so that it is not tried
again.  We will reword this section.

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

I think we know of someone that is using HTTPS for one of these cases, and
that is why it was thrown in there.  We will add something to warn users
that HTTPS support needs to be considered in terms of its potential impact
creating a loop.

> * 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!

By configurable, I think it is meant that the software would set the
expiration when it creates the entry, based upon a number of factors.
Examples of factors include the expiry of the information used to make the
determination, bandwidth, assurance level, storage space, whether it is a
server or client, etc.  We will make this clearer.

> * 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).

According to X.509, Issuer, Serial is always unique, since a given issuer
cannot repeat a serial number.  Of course, this assumes a "global directory"
where issuers are never repeated.  Issuer/Serial tuple is used as the
certificate identifier in a number of protocols (S/MIME for example) and of
course it is important for users to ensure that the resultant path is valid
through validation of signatures.

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

We will note this as a possibility.  Our goal for this document was "given a
certificate, how do I build its path" but we will note this.

> * 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!").

Heh.  Mark that up as a good reason to work in R&D.  We will make this
recommendation.  (About the reconstruction of the paths, not necessarily the
lighting-up part.)

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

We also can't be prescriptive since this is an Informational document... I
agree but I will not use the word "should".

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

Of course the simplest case of this is you build a path and everything lines
up except a certificate along the way is expired or revoked.  In this case,
the path is probably the "right" one and is not valid, and won't be.  This
is what we're getting at.

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

Again, this gets back to keeping it simple for the implementer.  See later,
we will add to section 7 some more advanced optimizations that includes
background/parallel processing.
 
> 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.

Same as above.  Signature checks are computationally expensive.  For
3280-compliant certificates, AKID/SKID matching is a much less expensive way
to know that the signatures are likely to chain.
 
> 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.

I'm not entirely sure I understand what you're saying here.  We're
recommending you don't check anything that's going to get checked anyway.
 
> * 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."

Agree.  We will make this change.
 
> * 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.

I have no problem removing the data formats,  I think it is useful to have a
semi-pseudocode example worked through for implementers to read, so I don't
think we should remove the entire section.
 
> * 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.

We will change to "in which".  Again, if efficiency is your number one
concern, it may be worthwhile to tune the path builder for your environment.
An example of a situation that deserves tuning is a server-based
implementation, when it is always processing paths for a particular
infrastructure.  

We have typically implemented the scoring weights to be read from
configuration files so that they can be tuned; default values would be used
in absence of tuned numbers.
 
> * 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.

We will change this to identify this rule must account for out-of-band
indications.
 
> * 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.

We will add an additional note about the changes to initial constraints.

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

I agree that this does help and will be included.

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

Like you mention above, the forward direction lets you immediately rule out
a branch of certificates that would fail.  In the reverse direction, you
rule out branches farther down with some unknown fanout.   That said, I
think this section reads too opinionated and will change it appropriately.

> * 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)?

I agree, this will be changed to eliminate certificates.
 
> * 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.

Will do.
 
> 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).

See my above comments, we are trying to stay simple.
 
> You should also probably change this section to include 
> discussion of OCSP. Right now, it's very focussed on CRLs.

I agree, we will try and make it less specific to 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.

I agree that this is a helpful sorting method.  With your permission, we
will add it to the document.
 
> * 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).

Assuming you implement it with a hash table!
 
> * 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.

We will attempt to reword this to make it clearer.
 
> * 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".

We will reword the forward definition to be closer to the reverse.
 
> 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.

Agree, that's why it's just a sort and not an eliminate rule.
 
> * 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.

We do recommend a cache for relationships and a cache for information in
section 2.6.  The idea of course is that given the cache of relationships
and the cache of information, you could reconstruct the previous path.  See
rule 3.5.10.
 
> * 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.

Agreed.  Again, rule 3.5.10 is more useful, and then this can be a secondary
rule to that.

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

We don't feel like we're overstating, and welcome more discussion.

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

This is what happens when you have 5 authors on a document!  This
contradiction will be resolved, most likely by changing the Criterion 1
(since we feel strongly about the non-repetition of the name/key).  
> 
> * 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.

Yes we will add this.  Of course, most commercial implementations don't
provide CRLs in this way.

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

We will add this (appropriately modified) text to 6.2 and 6.3.

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

We will add these to section 7 as more advanced possibilities.

> * 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!

We could, although it will take a bit of additional writing to explain these
issues.  We will attempt to encourage retrievals before the nextUpdate has
passed.

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

We will add these additional recommendations.

> * 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!

Agreed.  This has been noted a number of times in this message.
 
> * 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.

Yes, we will add something about the threat of DOS attacks on server DPD
systems and systems that handle authentication.
 
> * 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.

This issue has been debated on the list and there has not been any objection
to it.  It does not violate Criterion 1 of Section 2.2 since the path for
the CRL signer needs to be developed for the same CA hierarchy as the
certification path.
 
> Minor Comments:

We will accept all your minor comments.

Steve, I know I speak for all of the authors when I thank you for this
detailed review of the document.  It is a tremendous help to know that
someone else has read and thought about the entire document, and even if you
have differing opinions on parts of it, you were willing to help create a
better finished product.

Sincerely,

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