Subject: RE: I-D ACTION:draft-ietf-pkix-certpathbuild-00.txt

From: "Matt Cooper" <[email-masked]>
Date: Thu, 14 Aug 2003 17:59:26 -0400

Hello Masaki,

> 1. path building over http
> 
> This text gives an example as path building algorithm based 
> over LDAP. Shall we consider also about a path building 
> algorithm over http? 

Well, it was our intent, though I think perhaps we ended up rather LDAP
centric, to try to remove the retrieval methods from the doc as much as
possible. Problem is, we could write a whole RFC on retrieval alone. In
fact, as I mentioned at the conference, I think that might not be a bad
idea. On the premise of not addresses retrieval methodology in detail, I
don't want to include examples of how to build paths with different
protocols, AIA, LDAP, etc. I think this will make an already long doc much
too long. 

> 2. forward direction vs. reverse direction
> 
> My basic opinion is shown below as hybrid path building.
> =====
> Path building in the forward direction is very useful for 
> tree topology that each node has unique parent. However, when 
> each node has plural parent (e.g., mesh PKI or bi-lateral 
> cross-certified PKI), this method is useful only a bit. 

Can you explain further why you say this? When I look at the problem, the
decision tree in reverse usually appears to be much larger than in forward.
Take a look at the examples of the forward and reverse decision trees in the
ID. From what I can see, and perhaps I'm missing some of the finer points,
reverse is really only more useful in the event the forward (toThisCA) cross
certs are not populated or available. In addition, once you throw a dozen or
more trust roots into the picture, reverse becomes a real mess in my opinion
as you may have to build from all of them.

> First, therefore, a builder SHOULD attempt to build a path in 
> the forward direction till a self-signed certificate (or 
> maybe intermediate certificate issued by plural CAs). Then, 
> the builder MAY attempt to build the remain path either way.

This, or some hybrid of this, is a fine idea, in the abstract at least. I
found that implementation was a bit of a disaster. How do you know that the
partial path you built will necessarily intersect what you build in reverse?
For example, you could build the forward path you to CA "A" that has
multiple certs and then build all possible reverse paths while never finding
the target and also never intersecting A. On the other hand, if you had
simply continued in the forward direction, you might or might not have found
your trust root.

For the last path building module I wrote, it was necessary to interoperate
with PKIs in which the forward elements are not available, so reverse
building was necessary. Initially, we wanted to try both directions
simultaneously, but soon realized that the only way to do this effectively
was to keep the entire graph in memory and traverse all possibilities in
both directions from both sides until a path was found, checking for
intersections at all endpoints at every iteration. Needless to say, this
idea was discarded.

What I ended up implementing was an exhaustive search in the forward
direction, all the while caching all the certs I found along the way. If
path building failed, the path builder then turned around and tried it in
reverse. Since all the reverse elements were cached as well, network traffic
was kept pretty minimal to non-existent unless reverse building opened a new
branch in the tree.

> 3. Static path vs. Dynamic path
> Static certification path means that the client is given 
> beforehand all certificates and all revocation information 
> required for path validation.

This works fine if we trust the same root. But not at all, and in fact can
lead me in the wrong direction, if we don't. I personally don't believe that
any software should be constructed to depend on being supplied the full
path. It is completely debilitating if and when interoperability with other
PKIs is desired through cross certification. In my opinion, path building
should always be done, even if it is only from a local cache + the certs
supplied as the static path. In any event, the aim of the ID is building; if
you only accept static paths, there's nothing to do but validate it.

Best Regards,
Matt Cooper

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Masaki SHIMAOKA
> Sent: Tuesday, July 22, 2003 11:12 PM
> To: [email-masked]
> Subject: Re: I-D ACTION:draft-ietf-pkix-certpathbuild-00.txt
> 
> 
> 
> Dear Cooper,
> 
> > A New Internet-Draft is available from the on-line Internet-Drafts 
> > directories. This draft is a work item of the Public-Key 
> > Infrastructure (X.509) Working Group of the IETF.
> > 
> > 	Title		: Internet X.509 Public Key 
> Infrastructure:       
> >                           Certification Path Building
> > 	Author(s)	: M. Cooper, Y. Dzambasow
> > 	Filename	: draft-ietf-pkix-certpathbuild-00.txt
> > 	Pages		: 59
> > 	Date		: 2003-7-3
> 
> This is an excellent trial.
> 
> Sorry for my delayed comments below.
> 
> 1. path building over http
> 
> This text gives an example as path building algorithm based 
> over LDAP. Shall we consider also about a path building 
> algorithm over http? # I know and agree that  basically path 
> building is used in the environment which have directory 
> system. IMHO, path building over http may be achieved using 
> cAIssuers accessMethod in AIA extension, but it only 
> describes single path like strict hierarchy.
> 
> 
> 2. forward direction vs. reverse direction
> 
> My basic opinion is shown below as hybrid path building.
> =====
> Path building in the forward direction is very useful for 
> tree topology that each node has unique parent. However, when 
> each node has plural parent (e.g., mesh PKI or bi-lateral 
> cross-certified PKI), this method is useful only a bit. 
> First, therefore, a builder SHOULD attempt to build a path in 
> the forward direction till a self-signed certificate (or 
> maybe intermediate certificate issued by plural CAs). Then, 
> the builder MAY attempt to build the remain path either way.
> 
> 
>         2) Path building by the reverse direction
>         ----------------------------------------->
>    +---------+     +--------------+      +-------------+   
>    | Trusted |     | Intermediate |      | Self-Signed |   
>    |  Root   |---->|  Certificate |----->| Certificate |   ^
>    +---------+     +--------------+      +-------------+   |
>                                                 |          |
>                                                 |          |
>                                                 v          |
>                                         +----------------+ | 1) Path
>                                         |  Intermediate  | | building
>                                         | Certificate(*) | |    by
>                                         +----------------+ |  forward 
>                                                  |         | direction
>                                                  |         |
>                                                  v         |
>                                          +--------------+  |
>                                          |     Target   |  |
>                                          |  Certificate |   
>                                          +--------------+   
>         (*) Not self-signed certificate.
> # I know more consideration yet is required for this.
> =====
> 
> And this topic has one problem.
> Some subordinate CA populate their CA certificate to 
> issuedToThisCA of crossCertificatePair attribute in their own 
> (CA) directory entry. On the other hand, most cross-certified 
> (not subordinate) CA also populates their cross-certificate 
> to same location. When a path builder attempts hybrid 
> building as above, the builder in second step (reverse 
> direction) does not require obtaining the subordinate CA information.
> 
> 
> In almost (hierarchical) PKI, path building may finish before 
> second step. Only in some complex PKI, path building may need 
> second step. Anyway, this hybrid algorithm is useful for 
> every PKI, I think.
> 
> 
> 3. Static path vs. Dynamic path
> Static certification path means that the client is given 
> beforehand all certificates and all revocation information 
> required for path validation. On the other hand, dynamic 
> certification path means that the client at least must obtain 
> some certificates and revocation information required for 
> path validation. Dynamic certification path may use some 
> certificates and revocation information in certificate store 
> or local cache. For a client that cannot build a 
> certification path dynamically, we should consider static 
> certification path, e.g., SSL/TLS handshake.
> 
> 
> Your I-D describes that how build a certification path, and 
> my 'memo for mPKI' I-D aims to support how to design a 
> certification path. So I hope to review our documents each 
> other frequently.
> 
> Best Regards,
> -----
> Masaki SHIMAOKA
> 
> SECOM Trust.net
> System Engineering Dpt.
> Tel: +81 422 91 8493 (ext.3551)
> Fax: +81 422 45 0536
> e-mail: [email-masked]
>