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

From: Steve Hanna <[email-masked]>
Date: Mon, 19 May 2003 05:59:29 -0400

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: Fri, 23 May 2003 00:32:04 -0400

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:
> 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.
> 
> 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.
> 
> 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).
> 
> 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
> 
> >> 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.
> >>
> 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).
> >
> 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).
> >
> 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).
> >
> is meant, 
> >and what is implied, and what will be inferred by implementors when 
> >they see words like "prohibit", "valid" and so forth.
> >
> 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.
> >
> 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
> >> 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.
> >
> everywhere 
> >-- back out when you encounter it garbage collection 
> algorithm to try 
> >to find a known "trust anchor", then you are guaranteed that:
> >
> >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.
> >
> >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
> 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.
> >
> 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
> >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
> >

---

From: "Matt Cooper" <[email-masked]>
Date: Fri, 23 May 2003 11:37:38 -0400

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

> [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
> 
> 
> > 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
> > >FWIW, I'll say a bit more about garbage collection in LISP. If you 
> > >mimic the simplistic recursive descent -- leave spoor
> > everywhere
> transitive 
> > >relations and composition of functions, and the algorithm 
> above does 
> > >nothing more than compute what is known as a closure or limit.
> > >
> > >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.
> > >