Subject: Re: RFC 3280: same certificate in a certification path

From: Steve Hanna <[email-masked]>
Date: Wed, 04 Jun 2003 17:29:31 -0400

How would this rule prohibiting the re-use of a subject
key and subject name pair in a chain apply in the presence
of X.500 alt names? Would they be checked also?

I'm not convinced that this rule is worth adding. One big
reason to prohibit loops (identical certs) in a path is that
it's very hard for a builder to know that running through
the loop one more time won't result in a valid path (especially
if policy mapping is on and there are complicated mappings
in the certs in the loop). A small number of certs can cause
a huge amount of work for the builder. This argument doesn't
apply in the case you cited. No cert would ever appear in
the path more than once.

-Steve

Matt Cooper wrote:
> 
> Walt Tuvell noticed and brought to my attention that I left out an important
> detail -
> 
> The basic idea is to not re-use keys at the same point in the cert graph, so
> the rule I proposed should be "Don't re-use the same key and subject name
> pair." This is the same idea (prevents multiple traversals across the
> bridge, policy loops, etc.) but still allows a CA to perform a "name change"
> on itself should the need arise. (For example, as Walt pointed out, during
> migration to DNS naming from X500 naming.)
> 
> For those of you reading this (if any) who may be using one of the path
> builders I put together, never fear, it is implemented with the Key / DN
> pair, not just the key, so name changes should work without a problem.
> 
> Matt Cooper
> Orion Security Solutions
> 
> > -----Original Message-----
> > From: [email-masked]
> > [mailto:[email-masked]] On Behalf Of Matt Cooper
> > Sent: Friday, May 23, 2003 12:32 AM
> > To: [email-masked]; 'PKIX list'
> > Subject: RE: RFC 3280: same certificate in a certification path
> >
> >
> >
> > Very well put!
> >
> > Now, what say you to the assertion that there is no need to
> > repeat keys in a path, much less certificates? There are a
> > couple very attractive properties to such a rule such as
> > preventing multiple traversals through a Bridge CA, or
> > preventing "policy loops" like in your example but more
> > complicated - through multiple CAs and looped back via a
> > different path - duplicate certs not required.
> >
> > I have yet to encounter a real world example where it was
> > necessary to repeat a key. In fact, the last two path
> > builders I wrote used that rule, and they have yet to run
> > into a snag (as far as I know!) in testing or in the wild as
> > a result of that restriction. Your (and others') thoughts
> > would be welcome!
> >
> > Very Best Regards,
> >
> > Matt Cooper
> > Orion Security Solutions
> >
> >
> > > -----Original Message-----
> > > From: [email-masked]
> > > [mailto:[email-masked]] On Behalf Of Steve Hanna
> > > Sent: Monday, May 19, 2003 5:59 AM
> > > To: Eric Norman; PKIX list
> > > Subject: Re: RFC 3280: same certificate in a certification path
> > >
> > >
> > >
> > > Eric Norman wrote:
> > > >To say that a path is prohibited or is invalid does not mean
> > > that the
> > > >answer to the question of trust that you're trying to
> > > establish is "not
> > > >trusted".  What I think the intent is, and what I think
> > > works, is that
> > > >when you say a path is prohibited, you mean that it needn't be
> > > >considered farther because it will contribute nothing more.
> > >
> > > Yes, that's it. There's no reason to consider paths that
> > > contain the same certificate twice because nobody can come up
> > > with any real-world scenario where they have any value. But
> > > if we consider them valid there are some rather preposterous
> > > scenarios where the only valid path would be one that
> > > contains the same certificate twice.
> > >
> > > For instance, in a path CA1->CA2->CA1->CA2->EE where the user's
> > > acceptable policy is High and policy mapping is enabled and
> > CA1->CA2
> > > has HIGH and TOP SECRET policies and maps HIGH to CONF and
> > TOP SECRET
> > > to Z, CA2->CA1 has CONF policy and maps CONF to TOP SECRET, and
> > > CA2->EE has Z policy. See the example in our paper. This
> > example makes
> > > no real world sense, but it shows that if paths with duplicate
> > > certificates are considered valid then path builders must try
> > > them (at least, when policy mapping is involved).
> > >
> > > The best solution, as you suggest, is for people to not just
> > > stick certs together casually, perform path validation, and
> > > give up if it fails. They should move on to try path
> > > building. The path builder will build a valid path if one can
> > > be built (omitting pointless duplicate certificates). But
> > > there's no problem with declaring paths that contain
> > > duplicate certificates to be invalid.
> > >
> > > I'd love to chat more about the interesting theoretical
> > > issues that you raised (and I will return to do so), but I
> > > have to run off to Jury Duty today. I'll catch up with you
> > > tomorrow and we can discuss this more.
> > >
> > > Thanks,
> > >
> > > Steve
> > >
> > > >On Fri, 16 May 2003, Steve Hanna wrote:
> > > >
> > > >> A path that includes the same cert twice might look like this:
> > > >>
> > > >> CA1 -> CA2 -> CA1 -> CA2 -> EE
> > > >
> > > >[for reference below].
> > > >
> > > >> Eric Norman asks why we want to prohibit paths that
> > > contain the same
> > > >> certificate twice. I agree that there's nothing inherently
> > > wrong with
> > > >> such a path. But nobody has been able to show any reason why it's
> > > >> desirable to support such a path. And if we prohibit such
> > > paths, then
> > > >> path builders can be somewhat simpler and more efficient.
> > > They don't
> > > >> have to consider building paths with loops.
> > > >>
> > > >> Eric, do you have a good reason why we should not prohibit
> > > paths that
> > > >> contain the same certificate twice? I don't find
> > > >
> > > >Because they can happen.  There's nothing that will prevent, and
> > > >there's also probably no way to prevent autonomous CAs
> > from creating
> > > >loops in the certificate network.  Ergo, this must be dealt with
> > > >somehow; more below.
> > > >
> > > >> your argument about sticking two paths together
> > convincing. That's
> > > >> not how PKIX path building is generally done, since it
> > > often doesn't
> > > >> work (if one of the certs in the first part of the path
> > > includes name
> > > >> constraints violated by a cert in the second part of the
> > path, for
> > > >> instance).
> > > >
> > > >In fact, the examples chosen here, e.g. the path segment
> > > >CA1 -> CA2 -> CA1  (append another -> CA2 if you prefer) are
> > > precisely
> > > >what happens when two CAs cross certify each other by signing each
> > > >others keys (really attesting to each other's
> > > >identity) and then publish the fact that they have done so with a
> > > >CrossCertificatePair with both parts filled in (e.g. bridge
> > > stuff and
> > > >the like).
> > > >
> > > >Actually, it's even simpler than that.  Continuing with the
> > > distinction
> > > >you're trying to make above, you could just as well have a
> > path like
> > > >CA1 -> CA2 -> CA2 -> CA2 -> CA2 -> CA3. The same certificate
> > > >(self-signed) appears multiple times. However, this path can
> > > be used to
> > > >verify a trust relationship between CA1 and CA3 (just
> > > pretend CA2 never
> > > >issued the self- signed certificate).
> > > >
> > > >I think that we're really talking about here is what exactly
> > > is meant,
> > > >and what is implied, and what will be inferred by implementors when
> > > >they see words like "prohibit", "valid" and so forth.
> > > >
> > > >To say that a path is prohibited or is invalid does not mean
> > > that the
> > > >answer to the question of trust that you're trying to
> > > establish is "not
> > > >trusted".  What I think the intent is, and what I think
> > > works, is that
> > > >when you say a path is prohibited, you mean that it needn't be
> > > >considered farther because it will contribute nothing more.
> > > >
> > > >What my real problem might be is that I think the language
> > > could lead
> > > >to enough confusion for implementors that they'll get it wrong.
> > > >
> > > >The implication this has for constraints is that if
> > they're properly
> > > >designed (and I think they probably are) then when you
> > > encounter some
> > > >constraints a second time (because you've encountered a certificate
> > > >again), then applying the contraints again will yield
> > nothing new.
> > > >Actually, what I really think is that this shouldn't even happen
> > > >because you should create a spanning tree or something like
> > > that before
> > > >you begin the trust evaluation process; i.e. you should never even
> > > >encounter a certificate twice, but if you do, you'll still
> > > get the same
> > > >answer as far as trust.  All that's left is to worry about
> > > >termination when you have loops in the certificate graph.
> > > >
> > > >Hence,
> > > >
> > > >> P.S. Eric, thanks for tooting your own horn. It's good for us to
> > > >> consider and understand earlier work so we don't reinvent things.
> > > >
> > > >FWIW, I'll say a bit more about garbage collection in LISP. If you
> > > >mimic the simplistic recursive descent -- leave spoor
> > > everywhere
> > > >-- back out when you encounter it garbage collection
> > > algorithm to try
> > > >to find a known "trust anchor", then you are guaranteed that:
> > > >
> > > >(1) you will find a path if one exists, and
> > > >
> > > >(2) the algorithm will always terminate.
> > > >
> > > >What you are not guaranteed is that this simplistic
> > > algorithm will find
> > > >the best path by whatever metric you use to determine what's best.
> > > >
> > > >> Certificate path building is at heart a graph theory problem.
> > > >
> > > >And category theory is at the heart of graph theory; however, I not
> > > >going to suggest that everyone needs to take time out and read the
> > > >works of Saunders MacLane before discussion can continue :) :) :)
> > > >
> > > >I do have a "hidden agenda", though.  I will now try to change its
> > > >status from covert to overt.  I would like to see sound
> > theoretical
> > > >underpinnings to all this stuff.  That means mathematics,
> > the branch
> > > >called "algebra" in particular.  I'm not claiming that
> > concepts like
> > > >splicing chains together completely provide such
> > > underpinnings, but I
> > > >believe that they come real close.  There's a pretty direct
> > > translation
> > > >between splicing chains and the mathematical concepts of
> > transitive
> > > >relations and composition of functions, and the algorithm
> > above does
> > > >nothing more than compute what is known as a closure or limit.
> > > >
> > > >> But the problem is complicated by adding constraints to
> > > certificates
> > > >> and by performance concerns. I recently talked
> > > >
> > > >What you want is for constraints to have a "monotonic"
> > > property. That's
> > > >just another way of saying that they'll contribute nothing new if
> > > >applied again (well, actually that they won't try to
> > > contradict what's
> > > >been done before).
> > > >
> > > >> with someone who said "Cert path building isn't hard. It's only
> > > >> O(n+e) where n is the number of entities and e is the number of
> > > >> certificates." That's true, but you have to download all the
> > > >> certificates in the PKI first! Not very practical in most
> > > >> environments.
> > > >
> > > >It sounds I'm another one who's says "it's easy", doesn't it?
> > > >
> > > >I don't think I'm saying that you have to download all the
> > > certificates
> > > >in the PKI first.  What I think I'm saying is that you
> > > aren't going to
> > > >have much luck if you try to solve such problems by
> > > restrictions of the
> > > >possible topologies. The way to do it is to make sure you
> > > notice that
> > > >you're in a loop.  And when you do notice that, you
> > certainly can't
> > > >give up and pronounce that whole thing untrustworthy; you just try
> > > >something else until you run out of possiblities.
> > > >
> > > >Now the practical performance problems and the "as yet
> > unknown link"
> > > >problems have been introduced.  I'll offer the opinion
> > that the very
> > > >best thing that can to done to alleviate such problems is to
> > > follow the
> > > >often written advice to send all certificates to the other
> > > end that you
> > > >suspect they might need. Every certificate using protocol has
> > > >facilities to do this. In the circles where I've heard this
> > > discussed,
> > > >I'm having a real hard time understanding why there's such
> > > resistance
> > > >to doing this.
> > > >
> > > >
> > > >Eric Norman
> > > >
> > > >   "Congress shall make no law restricting the size of integers
> > > >   that may be multiplied together, or the number of times that
> > > >   an integer may be multiplied by itself, or the modulus by
> > > >   which an integer may be reduced".
> > >
> > >
> >
> >

---

From: "Matt Cooper" <[email-masked]>
Date: Wed, 11 Jun 2003 12:03:42 -0400

Hi Steve,

The biggest advantage to this rule is when you have a bridge (or any CA with
certs from multiple CAs - such as in a mesh environment) - it prevents
multiple passes through the same bridge point. (Or CA.) This eliminates
unnecessary and unintended paths and can also very significantly reduce the
size of the builder's decision tree.

Given the diagram below, the path
EE->N->L->X->BCA->W->BCA->Y->C->A->Y->BCA->Z is perfectly valid (assuming
policies, etc., validate) - meaning, you don't repeat any certs. I will
happily argue that such a path not only was not intended by the people who
hung the PKIs together off that bridge, but that such a path should never be
necessary in order to validate EE. If such a path *is* necessary - I would
also argue that this is likely indicative of a flaw. It is possible that
unintended trust is being communicated in such a scenario. 

One could also argue about trust dilution in such a convoluted path. (I
won't argue that one because it has been argued at length before!)

Of course, you could now double a couple more arrows or add a couple more
PKIs and make the path even longer. (For example, you could add G->W and
F->W, which would of course then allow a path like
EE->N->L->X->BCA->W->G->F->W->BCA->Y->C->A->Y->BCA->Z) At some point I think
we have to conclude the path becomes ridiculously and unnecessarily long.

On the other hand, if you do not allow key + dn to repeat, only one path
exists between Z and EE. That is the simplest possible path:
EE->N->L->X->BCA->Z. So, my thinking is that you are exactly right - the
small number of certs, or possibly dozens of certs, especially at the
bridge, is the most likely cause of the builder doing large amounts of
unnecessary work while it wanders around from one PKI to the bridge to
another PKI and back through the bridge and to another PKI and so on, each
time using a different bridge cert. If you imagine 50 cross certified PKIs
here and you do allow multiple traversals of key + dn - the decision tree
for the builder can become outrageously large. Now if you chain PKI's with
multiple bridges on an international scale... And then perform validation
over a 28k dialup line on a laptop from your hotel room...

 -{Please see response to the X.500 alt name question below the diagram.}-

         +---+    +---+
         | F |--->| H |
         +---+    +---+
          ^ ^       ^
          |  \       \
          |   \       \
          |    v       v
          |  +---+    +---+
          |  | G |--->| I |
          |  +---+    +---+
          |   ^
          |  /
          | /
      +------+       +-----------+        +------+   +---+   +---+
      | TR W |<----->| Bridge CA |<------>| TR X |-->| L |-->| M |
      +------+       +-----------+        +------+   +---+   +---+
                        ^      ^               \        \
                       /        \               \        \
                      /          \               \        \
                     v            v               v        v
               +------+         +------+        +---+    +---+
               | TR Y |         | TR Z |        | J |    | N |
               +------+         +------+        +---+    +---+
                ^   ^              / \            |        |
               /     \            /   \           |        |
              /       \          /     \          v        v
             v         v        v       v       +---+    +----+
           +---+     +---+    +---+   +---+     | K |    | EE |
           | A |<--->| C |    | O |   | P |     +---+    +----+
           +---+     +---+    +---+   +---+
             \         /      /  \       \
              \       /      /    \       \
               \     /      v      v       v
                v   v    +---+    +---+   +---+
                +---+    | Q |    | R |   | S |
                | B |    +---+    +---+   +---+
                +---+               |
                  /\                | 
                 /  \               |
                v    v              v
             +---+  +---+         +---+
             | E |  | D |         | T |
             +---+  +---+         +---+

[Steve Hanna (June 04, 2003 5:30 PM)]
> of X.500 alt names? Would they be checked also?

[Matt Cooper] I've given some thought to this question and the only scenario
I can come up with where this could be an issue is if for some reason a CA
needed to issue itself a cert with a different alt name but with the same
key. If this isn't a root cert, I'm not sure I see why this would be
necessary; the issuing CA could simply issue another cert with the new alt
name. Unless I'm missing something, if it's a root, then I don't think alt
names have any utility in the cert so this issue wouldn't apply to root
certs. Is this where your question was coming from or did you have something
else in mind that I haven't thought of?

Specifically, of the alt names and renaming: If a cert (1) is named XYZ with
alt name A, issues itself a cert (2) -> XYZ with alt name B, which then
issues a cert (3), would [(?)]->[(1)->(2)]->[(3)] be considered by the path
builder? (I think that is Steve's question with regard to x.500 alt names.)
In the case where (1) is not a root, you could just get (?) to issue a new
cert to eliminate the problem. If (1) is a root, it's messier because you
have to update all the clients if you don't allow re-use of the key when alt
names differ. But why does the root cert need an alt name? Should the
builder even be looking at it?

So then, are the alt names considered (allowing [(1)->(2)]->[(3)] and
complicating the code.) or ignored (eliminating [(1)->(2)]->(3) and
simplifying the code.)?

The purpose of preventing the name + key from repeating is only to eliminate
/ reduce the number of unintended and/or extraneous paths. To that end, at
least with existing implementations that I've seen, I think just using DN +
key will provide for 99.9% of cases. I haven't personally ever seen a
scenario in production that would have this as a problem. That said however,
I would not be at all opposed to making the rule "(dn + alt names + key) can
not repeat" if people feel that there is a need for including the alt names.
That certainly will not decrease the utility of the rule, it adds
flexibility, and may well allow for some situations that I haven't yet
considered.

Very Best Regards,

Matt Cooper
Orion Security Solutions

> From: Steve Hanna [mailto:[email-masked]]
> Sent: Wednesday, June 04, 2003 5:30 PM
> To: Matt Cooper
> Cc: PKIX List
> it's very hard for a builder to know that running through the 
> loop one more time won't result in a valid path (especially 
> if policy mapping is on and there are complicated mappings in 
> the certs in the loop). A small number of certs can cause a 
> huge amount of work for the builder. This argument doesn't 
> apply in the case you cited. No cert would ever appear in the 
> path more than once.
> 
> -Steve
> 
> Matt Cooper wrote:
> > 
> > Walt Tuvell noticed and brought to my attention that I left out an
> > important detail -
> > 
> > The basic idea is to not re-use keys at the same point in the cert
> > graph, so the rule I proposed should be "Don't re-use the 
> same key and
> > subject name pair." This is the same idea (prevents multiple
> > traversals across the bridge, policy loops, etc.) but still 
> allows a
> > CA to perform a "name change" on itself should the need arise. (For
> > example, as Walt pointed out, during migration to DNS 
> naming from X500
> > naming.)
> > 
> > For those of you reading this (if any) who may be using one of the
> > path builders I put together, never fear, it is implemented 
> with the
> > Key / DN pair, not just the key, so name changes should
> work without a
> > problem.
> > 
> > Matt Cooper
> > Orion Security Solutions
> > 
> > > Now, what say you to the assertion that there is no need
> to repeat
> > > keys in a path, much less certificates? There are a couple very
> > > attractive properties to such a rule such as preventing multiple 
> > > traversals through a Bridge CA, or preventing "policy 
> loops" like in
> > > your example but more complicated - through multiple CAs
> and looped
> > > back via a different path - duplicate certs not required.
> > >
> necessary
> > > to repeat a key. In fact, the last two path builders I wrote used
> > > that rule, and they have yet to run into a snag (as far 
> as I know!)
> > > in testing or in the wild as a result of that
> restriction. Your (and
> > > others') thoughts would be welcome!
> > >
> > > Very Best Regards,
> > >
> > > Matt Cooper
> > > Orion Security Solutions
> > >
> > >
> > > > Yes, that's it. There's no reason to consider paths
> that contain
> > > > the same certificate twice because nobody can come up with any
> > > > real-world scenario where they have any value. But if 
> we consider
> > > > them valid there are some rather preposterous scenarios
> where the
> > > > only valid path would be one that contains the same certificate
> > > > twice.
> > > >
> > > > certificates are considered valid then path builders 
> must try them
> > > > (at least, when policy mapping is involved).
> > > >
> > > > The best solution, as you suggest, is for people to not
> just stick
> > > > certs together casually, perform path validation, and
> give up if
> > > > it fails. They should move on to try path building. The path
> > > > builder will build a valid path if one can be built (omitting 
> > > > pointless duplicate certificates). But there's no problem with 
> > > > declaring paths that contain duplicate certificates to 
> be invalid.
> > > >
> > > > I'd love to chat more about the interesting theoretical issues
> > > > that you raised (and I will return to do so), but I have to run 
> > > > off to Jury Duty today. I'll catch up with you tomorrow 
> and we can
> > > > discuss this more.
> > > >
> > > > Thanks,
> > > >
> > > > Steve
> > > >
> > > > >> such a path. But nobody has been able to show any reason why
> > > > >> it's desirable to support such a path. And if we 
> prohibit such
> > > > paths, then
> > > > >In fact, the examples chosen here, e.g. the path
> segment CA1 ->
> > > > >CA2 -> CA1  (append another -> CA2 if you prefer) are
> > > > precisely
> > > > >what happens when two CAs cross certify each other by signing
> > > > >each others keys (really attesting to each other's
> > > > >and what is implied, and what will be inferred by implementors
> > > > >when they see words like "prohibit", "valid" and so forth.
> > > > >
> > > > >constraints a second time (because you've encountered a
> > > > >certificate again), then applying the contraints again 
> will yield
> > > nothing new.
> > > > >you begin the trust evaluation process; i.e. you should never
> > > > >even encounter a certificate twice, but if you do, you'll still
> > > > get the same
> > > > >> P.S. Eric, thanks for tooting your own horn. It's
> good for us
> > > > >> to consider and understand earlier work so we don't reinvent
> > > > >> things.
> > > > >
> > > > >FWIW, I'll say a bit more about garbage collection in LISP. If
> > > > >you mimic the simplistic recursive descent -- leave spoor
> > > > everywhere
> > > > >And category theory is at the heart of graph theory;
> however, I
> > > > >not going to suggest that everyone needs to take time out and
> > > > >read the works of Saunders MacLane before discussion 
> can continue
> > > > >:) :) :)
> > > > >
> > > > >I do have a "hidden agenda", though.  I will now try to change
> > > > >its status from covert to overt.  I would like to see sound
> > > theoretical
> > > > >give up and pronounce that whole thing untrustworthy; you just
> > > > >try something else until you run out of possiblities.
> > > > >

---

From: Steve Hanna <[email-masked]>
Date: Thu, 12 Jun 2003 10:38:04 -0400

Matt Cooper wrote:
> The biggest advantage to this rule is when you have a bridge
> (or any CA with certs from multiple CAs - such as in a mesh
> environment) - it prevents multiple passes through the same
> bridge point. (Or CA.) This eliminates unnecessary and unintended
> paths and can also very significantly reduce the size of the
> builder's decision tree.

In many real-world PKIs, the builder's complete decision tree
is impossibly large. And determining that tree requires fetching
all the certificates in the PKI, which is not feasible. So I'm
not terribly concerned about the size of the builder's decision
tree.

A more reasonable solution to path building is one that uses
a tree search algorithm that works with partial knowledge of
the tree, using heuristics to decide which branches to pursue.
If the builder uses such an algorithm, the example you gave below
is quickly and easily solved. Assuming you're building forward
(from EE to Z), you will find the answer as soon as you get
to the Bridge CA.

I expect there are examples that can show some benefit to
prohibiting paths that include two certs with the same
(subject DN, subject public key) pair. But I doubt that the
benefit will be substantial (assuming that a decent path
building algorithm is used). And I'm not yet convinced
that there is no reasonable use for such a path.

In general, I'd rather not make rules that tell people
how they MUST set up their PKIs unless there's a very
good reason to do so.

-Steve

------------

---

From: "Matt Cooper" <[email-masked]>
Date: Thu, 12 Jun 2003 10:18:11 -0400

Not sure what happened to this message; it seems that the remailer mangled
it a bit by adding the example paths again about 20 characters after they
first appeared. (Perhaps there's a buffer overflow in the remailer?) In any
event, it doesn't look like any of the content is lost. If you ignore the
second (and short the "Z") instance as you read, the result is the original
message.

-Matt

> Sent: Wednesday, June 11, 2003 12:04 PM
> To: 'Steve Hanna'
> Cc: [email-masked]
> bridge point. (Or CA.) This eliminates unnecessary and 
> unintended paths and can also very significantly reduce the 
> EE->N->L->X->BCA->W->BCA->Y->C->A->Y->BCA->Z is perfectly valid 
> EE->N->L->X->BCA->W->BCA->Y->C->A->Y->BCA->(assuming
> policies, etc., validate) - meaning, you don't repeat any 
> certs. I will happily argue that such a path not only was not 
> intended by the people who hung the PKIs together off that 
> bridge, but that such a path should never be necessary in 
> order to validate EE. If such a path *is* necessary - I would 
> also argue that this is likely indicative of a flaw. It is 
> possible that unintended trust is being communicated in such 
> a scenario. 
> 
> One could also argue about trust dilution in such a 
> convoluted path. (I won't argue that one because it has been 
> argued at length before!)
> 
> Of course, you could now double a couple more arrows or add a 
> couple more PKIs and make the path even longer. (For example, 
> you could add G->W and
> EE->N->L->X->BCA->W->G->F->W->BCA->Y->C->A->Y->BCA->Z) At 
> some point I 
> EE->N->L->X->BCA->W->G->F->W->BCA->Y->C->A->Y->BCA->think
> On the other hand, if you do not allow key + dn to repeat, 
> only one path exists between Z and EE. That is the simplest 
> possible path:
> small number of certs, or possibly dozens of certs, 
> especially at the bridge, is the most likely cause of the 
> builder doing large amounts of unnecessary work while it 
> wanders around from one PKI to the bridge to another PKI and 
> back through the bridge and to another PKI and so on, each 
> time using a different bridge cert. If you imagine 50 cross 
> certified PKIs here and you do allow multiple traversals of 
> key + dn - the decision tree for the builder can become 
> outrageously large. Now if you chain PKI's with multiple 
> bridges on an international scale... And then perform 
> validation over a 28k dialup line on a laptop from your hotel room...
> 
> [Matt Cooper] I've given some thought to this question and 
> the only scenario I can come up with where this could be an 
> issue is if for some reason a CA needed to issue itself a 
> cert with a different alt name but with the same key. If this 
> isn't a root cert, I'm not sure I see why this would be 
> necessary; the issuing CA could simply issue another cert 
> with the new alt name. Unless I'm missing something, if it's 
> a root, then I don't think alt names have any utility in the 
> cert so this issue wouldn't apply to root certs. Is this 
> where your question was coming from or did you have something 
> Specifically, of the alt names and renaming: If a cert (1) is 
> named XYZ with alt name A, issues itself a cert (2) -> XYZ 
> with alt name B, which then issues a cert (3), would 
> [(?)]->[(1)->(2)]->[(3)] be considered by the path builder? 
> (I think that is Steve's question with regard to x.500 alt 
> names.) In the case where (1) is not a root, you could just 
> get (?) to issue a new cert to eliminate the problem. If (1) 
> is a root, it's messier because you have to update all the 
> clients if you don't allow re-use of the key when alt names 
> differ. But why does the root cert need an alt name? Should 
> the builder even be looking at it?
> 
> So then, are the alt names considered (allowing 
> [(1)->(2)]->[(3)] and complicating the code.) or ignored 
> (eliminating [(1)->(2)]->(3) and simplifying the code.)?
> 
> The purpose of preventing the name + key from repeating is 
> only to eliminate / reduce the number of unintended and/or 
> extraneous paths. To that end, at least with existing 
> implementations that I've seen, I think just using DN + key 
> will provide for 99.9% of cases. I haven't personally ever 
> seen a scenario in production that would have this as a 
> problem. That said however, I would not be at all opposed to 
> making the rule "(dn + alt names + key) can not repeat" if 
> people feel that there is a need for including the alt names. 
> That certainly will not decrease the utility of the rule, it 
> adds flexibility, and may well allow for some situations that 
> I haven't yet considered.
> 
> Very Best Regards,
> 
> Matt Cooper
> Orion Security Solutions
> 
> 
> > I'm not convinced that this rule is worth adding. One big reason to 
> > prohibit loops (identical certs) in a path is that it's 
> very hard for 
> > a builder to know that running through the loop one more time won't 
> > result in a valid path (especially if policy mapping is on 
> and there 
> > are complicated mappings in the certs in the loop). A small 
> number of 
> > certs can cause a huge amount of work for the builder. This 
> argument 
> > doesn't apply in the case you cited. No cert would ever 
> appear in the
> > path more than once.
> > 
> > -Steve
> > 
> > Matt Cooper wrote:
> > >

---

From: "Matt Cooper" <[email-masked]>
Date: Mon, 16 Jun 2003 19:24:48 -0400

Responses inline:

> Sent: Thursday, June 12, 2003 10:38 AM
> To: Matt Cooper
> Cc: [email-masked]
> > The biggest advantage to this rule is when you have a 
> bridge (or any 
> > CA with certs from multiple CAs - such as in a mesh
> > environment) - it prevents multiple passes through the same bridge 
> > point. (Or CA.) This eliminates unnecessary and unintended 
> paths and 
> > can also very significantly reduce the size of the 
> builder's decision 
> > tree.
> 
> is impossibly large. And determining that tree requires 
> fetching all the certificates in the PKI, which is not 
> feasible. 

Agreed. I wasn't advocating any approach that requires you to retrieve every
certificate. The point is, the decision tree looms out in the darkness in
front of the builder. The number of nodes in the decision tree a builder
visits depends on the design of the builder. Or, in the case of no valid
path existing, it visits every reachable node. By choosing to never traverse
certain branches, the builder eliminates an unknown, but possibly quite
large, number of nodes from the tree.

> So I'm not terribly concerned about the size of the 
> builder's decision tree.

I Strongly Disagree. Reducing the size of the decision tree is absolutely
instrumental to making path development more efficient. You can not
guarantee that any set of heuristics will consistently guide path
development in the desirable direction every time, so the less choices that
exist, the better off you are. (And that is not to say that optimizing
heuristics are not instrumental as well.)

Think of the simple ways to improve path building. What would you call a
simple "validate validity period while you build" approach if it is not a
way to limit the size of the decision tree? Such an approach lops whole
branches from the tree when it realizes that traversing a particular branch
is of no value because the validity period is out of range. What I am
proposing does the same thing but using a different condition for the
pruning.

> the tree, using heuristics to decide which branches to 

Yes. Absolutely agree!

> If the builder uses such an algorithm, the example 
> you gave below is quickly and easily solved. Assuming you're 
> building forward (from EE to Z), you will find the answer as 
> soon as you get to the Bridge CA.

Again, spot on!

> (subject DN, subject public key) pair.

Yes, how about when the cert between Z and the Bridge is expired? Your
builder now has to traverse every possible path in the graph (there are
quite a few, especially if you want to hang a couple mesh PKIs off that
bridge as well) before concluding no path can be found.

> But I doubt that the 
> building algorithm is used). 

I agree until such time as no valid path exists. Or if the graph eliminated
simple leaps from the bridge to your destination. (For example, if you were
building from EE to F [add the cross cert from F to W]) It is possible
(though not likely given the diagram) that no hint would exist to guide the
builder to W from the Bridge. The builder may now run off on a tangent
building some convoluted paths through the other CA's in the example. Even
more fun is if the F->W cert were invalid for some reason.

> And I'm not yet convinced that 
> there is no reasonable use for such a path.

Like you, I am also not convinced. I always have some doubt remaining on
this topic. However, no one has yet presented me a necessary use case.
(Perhaps today someone will!)

> how they MUST set up their PKIs unless there's a very

With the ideal I agree, but I believe in this case the benefit outweighs it.
Especially given the lack of examples in which such a rule would break
something. When I'm thinking about building paths and trying to find the
valid path that doesn't exist, I'm envisioning a future PKI environment
where trust is communicated across large and diverse realms that make
today's Bridge CA just a drop in the decision tree bucket. In my mind, the
current thinking of only prohibiting the repetition of certificates is not
sufficient when looking forward to that kind of environment. If just a dozen
certs can yield hundreds and hundreds of paths, what about hundreds, or even
pie-in-the-sky thousands of certs? Thousands of corporate and government
PKIs linked together with bridges? With the current rule set, users could
wait all day and not exhaust all possible paths while looking for a valid
one.

-Matt

---

From: Steve Hanna <[email-masked]>
Date: Tue, 17 Jun 2003 16:31:33 -0400

Matt Cooper wrote:
> I Strongly Disagree. Reducing the size of the decision tree
> is absolutely instrumental to making path development more
> efficient.

We both agree that the entire decision tree may be too large
to work with. We both agree that builders should prune the
tree as they go by eliminating paths that could never be valid
and use heuristics to decide which paths are most promising.

You would like to have a rule against repeating a (name, key)
pair in a path. I think this can be a heuristic, since I'm
not yet sure that there's no valid reason to want to do this.

I don't think we're so far apart here.

> I'm envisioning a future PKI environment where trust is
> communicated across large and diverse realms that make
> today's Bridge CA just a drop in the decision tree bucket.
> ...
> With the current rule set, users could wait all day and
> not exhaust all possible paths while looking for a valid
> one.

I agree this is a likely future as more PKIs are interconnected.
But adding a rule against repeating a (name, key) pair in a
path will not solve the problem of path building in a huge
environment. It won't even help much. You can always have a
heuristic that steers you away from these paths if you don't
believe they're promising.

What will help in a huge and complex PKI?

* Sending partial paths or, even better, bags of certs
  (as S/MIME and SSL/TLS allow). Ideally, these certs
  should go beyond the EE's trust anchor to include
  other certs linking into relevant trust points.

* Having each side tell the other what its trust anchors
  are (as SSL/TLS allows servers to do). This helps
  determine which trust points are relevant.

* Using delegated path discovery so that the DPD servers can
  build and use knowledge across many queries.

* And, of course, validating as you build to prune out
  paths that could never be valid. And using heuristics
  to steer you toward paths that look promising. Including
  name constraints and policy constraints in certs helps
  heuristics find their way.

Other ideas, anyone?

> The number of nodes in the decision tree a builder visits
> depends on the design of the builder. Or, in the case of no
> valid path existing, it visits every reachable node.

In a large environment, it isn't feasible to try every
possible path. That could take days. And if certs are
issued rapidly enough, it could simply never end. At a
certain point, you (or maybe the user) must just say
"Enough!" and stop looking. Builders need to provide
for this.

Let's return to the question of whether the proposed rule
against repeating a (name, key) pair in a path has a net
benefit. The downside as I see it is increased complexity
in the validation algorithm and less flexibility for the
CA operator. And the upside? We're not plugging a security
hole here. The main advantage is that builders can knock
out those paths as invalid. But builders could accomplish
almost the same thing by just rating them as unpromising
in their heuristic.

I'd say you should take your case to the ISO/ITU X.509 group.
If they are convinced, then the PKIX working group can
follow suit. But I don't think this is not a sufficiently
convincing argument that PKIX should break new ground
and jump out ahead of ISO/ITU, especially when we're trying
to take RFC 3280 to Draft Standard. The fewer changes,
the better.

Thanks,

Steve

P.S. Thanks for an intelligent discussion.

---

From: Steve Hanna <[email-masked]>
Date: Tue, 17 Jun 2003 18:01:41 -0400

> I agree this is a likely future as more PKIs are interconnected.

I should have said that this is a *possible* future. It's not
likely unless we can remove some of the obstacles to PKI
deployment and usage. But it's still important for researchers
to work on these problems so that PKI can scale better.

-Steve

---

From: Eric Norman <[email-masked]>
Date: Tue, 17 Jun 2003 22:39:23 -0500 (CDT)

>   other certs linking into relevant trust points.

Now this is getting close to a subject that hasn't been
mentioned much in this discussion.  Who's job is it to
round up the certificates needed to verify?  Sender or
receiver?  Standard practice that has evolved over eons
puts this burden on the sender; i.e, the user is expected
to "show up with the proper papers".

Yes, part of the reason for that is the "something you have"
stuff; nevertheless, putting the burden on the sender as RFCs
suggest seems like it should alleviate a lot of the performance
concerns.

I'll even go so far as to say that it's OK for the receiver
to deny verification if the sender doesn't supply all the
certificates needed.

On a tangential note that's prompted by "beyond the trust
anchor" phrase, I think a sender should send the final
certificate as well as all the others even if it is known
that the receiver has that one already (some RFCs seem to
forbid this).  The reason for this is that they can be
compared and alarms sounded if they differ.

>   determine which trust points are relevant.

Whoops, I sure don't read section 7.4.4 of RFC2246 as saying
that.  I read it as meaning "send me a client certificate with
one of these DNs in the chain".  In most cases, that would be
the DN of the issuer of the client certificate, but one can
imagine cases where it would be farther away.  (This comment
is just about the use of the phrase "trust anchor"; it isn't
related to the above).

Furthermore, what happened to the problem identified in the
paper that Steve referred us to a while ago?  Namely, that
there are cases what you have to visit a certificate twice
to complete policy mappings (I think it was).

> almost the same thing by just rating them as unpromising

Isn't the real problem here that there's an implicit assumption
that certificates lie in a strict hierarchy?  This assumption
seems to appear in suggested algorithms and perhaps even in
some extension semantics.  I think a better approach is to
fix the algorithm instead of restricting CAs.  (Here he comes
with the garbage collection algorithm again)!

Eric Norman

		"I may be just a butterfly,
		 but watch out if I flap my wings".

---

From: Stephen Kent <[email-masked]>
Date: Wed, 25 Jun 2003 16:15:31 -0400

>to "show up with the proper papers".

Huh? the RP is responsible for acquiring the necessary certs and CRLs 
to validate a signature. Although it is true that several protocols 
provide a facility to enable a sender to assist an RP by providing 
certs or CRLs that might be useful, this is not a great solution in 
general. This is because the sender usually cannot know what certs 
and companion CRLs will be needed by an RP, especially if there are 
multiple RPs (e.g., in S/MIME). Much of the motivation for sending 
this info arises because of the lack of a readily accessible 
directory infrastructure.

>suggest seems like it should alleviate a lot of the performance

Again I am puzzled by your apparent reference to the vernacular user 
authentication phrase "something you have." Possession of a cert does 
nothing to verify an identity; certs are generally public. It is only 
possession of the corresponding private key that established identity.

>to deny verification if the sender doesn't supply all the

You'll be treading on very thin ice if you make this assertion.