Subject: RFC 3280: same certificate in a certification path

From: Takashi ITO <[email-masked]>
Date: Thu, 15 May 2003 20:58:18 +0900

Hello,

I have a question about "certification path" in RFC 3280.

In X.509(4th) "10.1 Path Processing inputs", text says:

    The inputs to the certification path processing procedure are:

    a)  a set of certificates comprising a certification path;
    NOTE - Each certificate in a certification path is unique.
    A path that contains the same certificate two or more times
    is not a valid certification path.

    ...(snip)

This means, for example, "CA1 -> CA2 -> CA1 -> EE" is not a valid
certification path.

In RFC 3280, is this path appropriate for path processing inputs?
I couldn't find descriptions about this in RFC 3280...

Could you please give me any comments?

Thanks,

Takashi ITO <[email-masked]>
Mitsubishi Electric Corporation

---

From: Steve Hanna <[email-masked]>
Date: Thu, 15 May 2003 11:06:26 -0400

In my opinion, RFC 3280 should be changed (in a
successor RFC) to include a requirement that a valid
certification path cannot include the same certificate
twice. This has been discussed on several occasions and
nobody has been able to come up with a good reason to
allow such a path to be valid. Also, we want to maintain
consistency with X.509. And allowing duplicate certificates
makes path building more difficult.

I don't think there should be any problem with making
this change when RFC 3280 is next revised, since I
suspect nobody is counting on the current behavior.
And I believe that you could even consider the new
behavior to be consistent with RFC 3280 since it says
in section 6.2:

   [...] the path validation algorithm presented in
   section 6.1 defines the minimum conditions for a
   path to be considered valid.

Prohibiting duplicate certificates is an additional
condition and therefore permitted by RFC 3280.

Steve Hanna

---

From: Richard Levitte - VMS Whacker <[email-masked]>
Date: Thu, 15 May 2003 17:06:17 +0200 (CEST)

In message <[email-masked]> on Thu, 15 May 2003 20:58:18 +0900, Takashi ITO <[email-masked]> said:

takashim> I have a question about "certification path" in RFC 3280.
takashim> 
takashim> In X.509(4th) "10.1 Path Processing inputs", text says:
takashim> 
takashim>     The inputs to the certification path processing procedure are:
takashim> 
takashim>     a)  a set of certificates comprising a certification path;
takashim>     NOTE - Each certificate in a certification path is unique.
takashim>     A path that contains the same certificate two or more times
takashim>     is not a valid certification path.
takashim> 
takashim>     ...(snip)
takashim> 
takashim> This means, for example, "CA1 -> CA2 -> CA1 -> EE" is not a valid
takashim> certification path.

Heh, to forbid those may seem silly, but you have to admit that it
gives a good hint that "CA1 -> EE" is the better way to go, wouldn't
you agree?  Why would you at all want to take the longer path?  Or is
there some policy magic that requires the long path to be processed?

-- 
Richard Levitte     | http://richard.levitte.org/ | Spannv. 38, I
Levitte Programming | http://www.lp.se/           | S-168 35 Bromma
T: +46-708-26 53 44 |                             | SWEDEN
     "Price, performance, quality...  choose the two you like"

---

From: Steve Hanna <[email-masked]>
Date: Thu, 15 May 2003 12:18:54 -0400

Yes, it's "policy magic". Because of policy mapping,
it is possible that a path "CA1 -> CA2 -> CA1 -> EE"
might be considered valid under the existing RFC 3280
validation algorithm while "CA1 -> EE" would not. For
an example, see section 5 of our paper from NDSS '01:

http://www.isoc.org/isoc/conferences/ndss/01/2001/papers/elley.pdf

However, nobody has yet demonstrated that this is a
useful feature of the RFC 3280 validation algorithm.
In fact, there seems to be a general consensus that
it is harmful. For instance, allowing such loops means
that path building software must consider the possibility
that a loop (or maybe several loops) might be required
to build a valid path between two entities. Declaring
that a valid certification path cannot contain the same
certificate more than once solves this.

-Steve

---

From: Steve Hanna <[email-masked]>
Date: Thu, 15 May 2003 13:39:34 -0400

The ISOC web site seems to have gone down suddenly.
It must be the incredible load of everyone downloading
our paper. ;-)

If you want a copy of the paper, send me a note
and I'll send you the PDF file by email.

-Steve

---

From: Eric Norman <[email-masked]>
Date: Thu, 15 May 2003 14:09:00 -0500 (CDT)

> > This means, for example, "CA1 -> CA2 -> CA1 -> EE" is not a valid

I have two "valid" certification paths, for instance, the path CA1 -> CA2,
and also the path CA2 -> CA1 -> EE.  Now I splice them together by doing
no more than recognizing that the end of one path is identical to the
beginning of the other.  I cannot imagine why the resulting longer path
should now be considered "invalid".  Note that if the second path is
CA2 -> CA3 -> EE, there's no reason for complaint.  In other words, if
I start with "valid" things and do something "valid" with them, it sure
does seem like the result should also be "valid".

I can imagine that the result of such splicing might be less efficient,
or redundant, or something like that.  But to now call it "invalid"?
That seems stange.

But you say, "but that allows loops in the path".  So what?  You already
have loops in the path; it's just that they're of length 1 (or 0, if you
prefer) and they're called self-signed certificates.

In the above example, two different CAs mutually "do their thing" with
each other.  It seems to me that this would make the keys of each more
trustworthy, not less, and certainly not "invalid".

The path discovery problem has been known for many, many years and has
been solved by every LISP garbage collector, for instance.  And now I'll
go off on a toot-my-own-horn tangent and point out that if you want to
see some actual code, you can see some that I wrote 30 years ago for the
Univac 1108 LISP system on the History of LISP site at

   http://www.frobenius.com/univac.htm

Eric Norman

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

---

From: Steve Hanna <[email-masked]>
Date: Fri, 16 May 2003 11:28:32 -0400

Oh, darn! We've had a problem since the first email
in this thread.

> This means, for example, "CA1 -> CA2 -> CA1 -> EE" is not a valid

Actually, that's a fine path. Each of the arrows is a cert.
And clearly each of these three certs is unique, since each
one has a different subject-issuer pair: (CA1, CA2), (CA2, CA1),
(CA1, EE). So this isn't a problem.

A path that includes the same cert twice might look like this:

CA1 -> CA2 -> CA1 -> CA2 -> EE

Then the first and the third certificates would probably be
the same (although they might not be if CA1 has issued more
than one cert for CA2). If they were the same, then that would
not be allowed per X.509 (2000) but it would be allowed per
RFC 3280.

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

Note that this is somewhat of a moot point. RFC 3280 is a
profile of X.509 and X.509 now prohibits such paths, so we
really need to do so as well unless we want to try to
convince the X.509 folks to reverse themselves on this.
I'd need to see a pretty good argument to consider doing that.

-Steve

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.

Certificate path building is at heart a graph theory problem.
But the problem is complicated by adding constraints to
certificates and by performance concerns. I recently talked
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.

---

From: Eric Norman <[email-masked]>
Date: Sat, 17 May 2003 18:53:53 -0500 (CDT)

> CA1 -> CA2 -> CA1 -> CA2 -> EE

[for reference below].

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

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

> to consider and understand earlier work so we don't reinvent

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.

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

> all the certificates in the PKI first! Not very practical in

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