Subject: Open Issue in Part1: path length constraints

From: Tim Polk <[email-masked]>
Date: Wed, 14 Feb 2001 15:35:47 -0500

Folks,

As noted in the Last Call message, there is an open issue on Part 1 
regarding the processing of path length constraints.  The basic constraints 
text (4.2.1.10, page 37) and path validation algorithm wrap-up procedure 
(6.1.5, page 73) contained in the current draft of Part1 does not consider 
the path length constraint for an end certificate.  This has sparked some 
controversy.

In this message, I will attempt to describe the issue and the trade-offs 
between the two different interpretations.  I apologize in advance for the 
length of this message.  Brevity is not my strong suit.

We first ran into this issue at NIST when we were developing the X.509 path 
validation tests.  There was some debate among the participants whether a 
path should be rejected if the max_path_length state variable was less than 
or equal to zero and the end certificate was a CA certificate (i.e., 
basicConstraints included cA=TRUE).

After some discussion, we decided that the path length constraint in basic 
constraints was intended to specify the number of intermediate certificates 
that could follow this certificate. This meant the max_path_length did not 
apply to the end certificate. The current text of part1 reflects this line 
of reasoning:

 From 4.2.1.10:

 >The pathLenConstraint field is meaningful only if cA is set to TRUE. In this
 >case, it gives the maximum number of CA certificates that may follow this
 >certificate in a certification path. (Note: One end- entity certificate will
 >follow the final CA certificate in the path. The last certificate in a path
 >is considered an end-entity certificate, whether the subject of the
 >certificate is a CA or not.)

6.1.5 supports this interpretation through omission:  there is no 
processing step to consider the value of  max_path_length in the 
wrap-up-procedure.  (The comparison step appears in 6.1.4, "Preparation for 
Certificate i+1" so it is already performed for every other certificate in 
the path.)

If the working group disagrees with this interpretation, the changes to 
Part 1 are straightforward.  First, modify the parenthetical in 4.2.1.10 to 
indicate that the end certificate in the path is considered a CA 
certificate if the basic constraints extension indicates 
cA=TRUE.  Secondly, add one new step (h) to 6.1.5 and reject the 
certification path if (h) fails.

new step:
 >
 >(h) If the certificate was not self-issued, verify that max_path_length is
 >greater than zero and decrement max_path_length by 1.

comparison statement:
 >
 >If check (h) fails, the procedure terminates, returning a failure indication
 >and an appropriate reason.

What is less straightforward (at least to me) is which approach is the 
appropriate one.

Essentially, the relying party wishes to trust the public key of a subject 
to perform an action *other* than validating a signature on a 
certificate.  During the preparation for this certificate the value of 
max_path_length has been decremented or reset to zero (steps (l) or (m) in 
6.1.4) , indicating no additional CA certificates may be processed.

If that subject of the last certificate is not a CA, the path is clearly 
acceptable.  But what if the subject is a CA? Should the relying party 
reject the path because the key is in a CA certificate *or* accept the path 
because the subject is not being treated as a CA?

I cannot come up with a security rationale for rejecting such a 
certificate.  On the other hand, I do need to stretch a bit to devise a 
scenario where accepting this certificate is beneficial.

Here is the beneficial scenario:

CA "A" issues a CA certificate to CA "B".  "A" trusts end entity 
certificates issued by "B", but does not trust "B" to issue certificates to 
other CAs.  "A" includes basic constraints in the certificate it issues to 
"B" with cA = TRUE and pathLen = 0.

"B" does not issue its own CRLs, but delegates this to CA "C".  "B" also 
trusts "C" to issue end entity certificates. So, "B" includes basic 
constraints in the certificate it issues to "B" with cA = TRUE.

Alice's trust point is "A".
Bob's trust point is "B", and "B" issued his certificate.  Bob's 
certificate includes a CRL distribution points extension identifying "C" as 
the indirect CRL issuer.
Carol's trust point is "C", and "C" issued her certificate.

Using the current text/algorithm, Alice can validate the certification path 
for Bob including the indirect CRL signed by "C".  This required Alice to 
validate the certification path ending with the certificated issued by "B" 
to "C".

Alice cannot validate Carol's certificate, though.  Alice cannot trust any 
certification path  that includes the certificate issued by "B" to "C" as 
an intermediate certificate.

This *seems* to satisfy the spirit of the path length constraint, but not 
the letter.

On the other hand:

If max_path_length is used to reject end certificates whose subjects are 
CAs, Alice would not be able to validate Bob's certification path.  Alice 
could not process the indirect CRL.

If "A" relaxed the path length constraint (1 instead of zero) Alice would 
be able to validate Bob's certification path.  Unfortunately, this would 
also permit Alice to validate Carol's certification path, which "A" did not 
intend.

This honors the letter of the path length constraint but did not achieve 
the intended results.

Even with this scenario, there are at least two workarounds.  Either CA "A" 
or CA "B" could issue a certificate to "C" that omitted the basic 
constraints extension (but included the cRLSign bit in keyUsage).  Alice 
would then be able to process paths as intended.  Alice would accept Bob's 
certification path and reject Carol's.

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

In summary:

(1) The current text describes a comparatively liberal interpretation of 
basic constraints.
(2) A straightforward reading of RFC 2459 or X.509 implies a more 
conservative interpretation.
(3) Either interpretation may be easily accommodated in the new specification.
(4) I cannot devise a security attack based on the more liberal interpretation.
(5) I can devise one scenario where the more liberal interpretation was 
beneficial. (It is unclear if there are others.)
(6) It is certainly possible to implement this same scenario with the more 
conservative interpretation.  It requires issuing one additional certificate.

Any thoughts?

Thanks,

Tim Polk

P.S.  I should state that implementations exist that implement both 
interpretations.

---

From: Steve Hanna <[email-masked]>
Date: Thu, 15 Feb 2001 14:04:19 -0500

Thanks for raising this issue for discussion, Tim. I have several
concerns with the pathLenConstraint semantics described in new-part1-04.

First, this is an incompatible change to the existing semantics.
RFC 2459 clearly states that pathLenConstraint "gives the maximum number
of CA certificates that may follow this certificate in a certification
path." The X.509 specs include similar wording. Many certificates have
been issued with the current semantics and code has been written that
implements these semantics. We shouldn't change the semantics in an
incompatible manner unless we have a very good reason.

Second, you have not described a good reason for this change. In the
example that you presented, certificates issued by CA "B" are covered by
an indirect CRL from CA "C". B wants to vouch for C as a CA *and* a CRL
issuer. To avoid the problem with pathLenConstraint, B should issue two
certificates for C: a CA certificate and an end-entity certificate with
the cRLSign keyUsage bit set.

Third, this will change the basic meaning of validating a path (or a
certificate). With the 2459 semantics, a path is either valid or it's
not. With the looser revised semantics, a path may be valid except for
the keyCertSign keyUsage in the final certificate. This means that the
result of a DPV operation ("Is this cert valid?") will not be a boolean
value. It will be something more complicated ("Yes, but not for
keyCertSign keyUsage"). I oppose making such a basic change without a
strong reason and I haven't heard any strong reason.

Thanks,

Steve

---

From: "David A. Cooper" <[email-masked]>
Date: Thu, 15 Feb 2001 17:38:55 -0500

Steve,

As Tim noted in his message yesterday, no matter which way we choose to define the semantics for the pathLenConstraint field in basicConstraints, it will be possible for CAs to issue certificates in a way that achieves their desired results. I do believe however, that the semantics described in new-part1-04 are more straightforward and will make it more likely that CAs will issue certificates properly. So, I think that semantics currently described in the draft are preferable to the alternative.

My detailed comments are included in-line below.

>incompatible manner unless we have a very good reason.

I believe that the problem we are currently experiencing is as a result of the original text not being sufficiently clear. Now that a detailed path validation algorithm has been included in son-of-2459 and NIST has made available a certification path test suite, it is coming to light that different groups have interpreted some of the statements in X.509 and RFC 2459 differently. As Tim mentioned yesterday, we have come across implementations that observe the pathLenConstraint semantics that are described in new-part1-04, so no matter which semantics we choose, there will be current implementations that do things differently.

Fortunately, I do not think that the confusion with the semantics of pathLenConstraint will lead to any significant problems. In particular, I don't think that processing certification paths according to the semantics in new-part1-04 will violate the intentions of any previously issued CA certificates, even if the issuers had interpreted pathLenConstraint according to the semantics that you prefer. On the other hand, implementations that process certification paths according to the semantics that you prefer will only reject certification paths in which the final certificate in the path contains a basicConstraints extension with cA=TRUE and in which a previous CA had imposed a path length constraint that would prevent the subject of this certificate from issuing further certificates. This is a scenario that not likely to be very common.

>the cRLSign keyUsage bit set.

This is certainly one option. One could include in the profile a requirement that certificates issued to a CA for the purposes of "empowering" that CA to issue certificates should be issued only for that purpose (and perhaps also to allow the relying party to validate CRLs issued by that CA for the certificates that it issues). If there is a desire to "empower" the CA to use its private key to perform other functions (e.g., sign indirect CRLs, sign PKI transactions messages, etc.) then a second certificate should be issued in which basicConstraints is absent. The result would be that the certificate that did not contain the basicConstraints extension could be validated even by those relying parties that are using the restrictive pathLenConstraint semantics that could not validate the certificate with basicConstraints in it as a result of a path length constraint in a previous certificate in the path.

I do not see any benefit to requiring CAs to issue two certificates, however. Particularly in the scenario that Tim described yesterday in which a cross-certificate is being issued both to "empower" the subject to issue certificates and to "empower" the subject to issue indirect CRLs. While it would be possible to issue two separate certificates, it may be easier from a management perspective to only issue one. Furthermore, since the people who are issuing the certificates will not be experts on every minute detail of X.509, we have to assume that by imposing more complex requirements on the issuers, we would be making it more likely that mistakes would be made (e.g., a CA may issue a cross-certificate to allow for the validation of indirect CRLs, but may include basicConstraints with cA=TRUE since operator of the CA thinks of the issuer of CRLs as a CA).

>strong reason and I haven't heard any strong reason.

I do not agree that this changes the basic meaning of validating a path. For starters, the result of path validation is not a boolean. Currently, if a path is accepted, it is accepted under a set of certificate policies along with (in theory, at least) a set of policy qualifiers.

You seem to suggest that we are now stating that a path may be valid expect for the keyCertSign key usage. However, one should never make use of the keyCertSign key usage bit when it appears in the last certificate in a path.

Suppose that you have the following set of entities and corresponding certificates:

         CA1 --------> CA2 ----------> CA3 -----------> CA4 -------> .... -------> CAn ---------> EE

If you want to validate the certificate issued to EE, you should always do so by performing path validation on the path that beings with a certificate issued by a trust anchor (e.g., CA1) and that ends with the certificate issued to EE. You should never perform the validation by first performing path validation on a path that ends with the certificate issued to CAn, and then upon determining that the certificate issued to CAn is valid and contains the keyCertSign key usage, using CAn's public key to validate the certificate issued to EE. So, it seems to me that the presence of the keyCertSign bit in a certificate that is at the end of a certification path should never be considered relevant. Am I missing something?

Furthermore, even if you did accept that idea that one could make use of the keyCertSign key usage bit in the final certificate in a certification path, you still could not make the claim that the decision to validate the certificate was a binary one. If you are going to make use of the public key in the final certificate in the path to validate certificates, then the use of that public key is still limited by the path length constraints, name constraints, etc., imposed by previous certificates in the certification path. In other words, the use of the public key to validate certificates should be treated as a continuation of path validation.

So, I do not think that the presence of keyCertSign in the final certificate is a valid concern. What about the other key usages? None of the other key usages require the presence of basicConstraints with cA=TRUE. So, a CA could always issue two certificates: one with basicConstraints, cA=TRUE that has keyCertSign asserted and another with basicConstraints absent that asserts any of the other desired key usages. The results of processing these certificates would be the same under both semantics (Technically the semantics in new-part1-04 would result in the certificate with basicConstraints present being accepted when it is the last certificate in the path in some cases where the certificate would be rejected under the other semantics. However, since this certificate only asserts the keyCertSign keyUsage, it would be useless as an end certificate as I noted above). With the semantics in new-part-04, however, CAs would be able to issue only one certificate. The ability to issue !
just one certificate may be considered simpler from a management perspective. Being less restrictive with the semantics would also make it less likely that paths would not validate as a result of improperly issued certificates.

Of course, as I mentioned earlier, it is possible to achieve the desired results in a PKI using either of the semantics, so the main goal should be to ensure that whatever the final decision is, the semantics are clearly written in the next draft of the certificate and CRL profile.

Perhaps others, particularly those who have already implemented this extension, could provide their opinions on this subject as well.

Dave

---

From: Steve Hanna <[email-masked]>
Date: Fri, 16 Feb 2001 17:23:43 -0500

"David A. Cooper" wrote:
> I believe that the problem we are currently experiencing is as a
> result of the original text not being sufficiently clear.

I thought the original text was quite clear. But I guess not.

The original text said:

   The pathLenConstraint field is meaningful only if cA is set to TRUE.
   In this case, it gives the maximum number of CA certificates that may
   follow this certificate in a certification path. A value of zero
   indicates that only an end-entity certificate may follow in the path.

The revised text says:

   The pathLenConstraint field is meaningful only if cA is set to TRUE.
   In this case, it gives the maximum number of CA certificates that may
   follow this certificate in a certification path. (Note: One end-
   entity certificate will follow the final CA certificate in the path.
   The last certificate in a path is considered an end-entity
   certificate, whether the subject of the certificate is a CA or not.)
   A pathLenConstrinat of zero indicates that only an end-entity
   certificate may follow in the path.

I find it odd to say that a certificate with cA=TRUE is a CA certificate
*unless* it is the last certificate in a path. I suppose this is only a
wording problem, but I find this wording *less* clear than the old
wording.

I also question whether the revised semantics for pathLenConstraint will
be as easy to understand for CA operators.

Do we really need to complicate things like this to handle a case that
you admit will be rare (a CA that uses another CA for indirect CRLs,
combined with max_path_length of 0)?

> You seem to suggest that we are now stating that a path may be valid
> expect for the keyCertSign key usage. However, one should never make
> use of the keyCertSign key usage bit when it appears in the last
> certificate in a path.

This is true. But I doubt that it's widely understood. Perhaps it should
be highlighted in the document.

> Of course, as I mentioned earlier, it is possible to achieve the
> desired results in a PKI using either of the semantics, so the main
> goal should be to ensure that whatever the final decision is, the
> semantics are clearly written in the next draft of the certificate and
> CRL profile.

Agreed.

> Perhaps others, particularly those who have already implemented this
> extension, could provide their opinions on this subject as well.

I agree with this as well. I'll be on vacation next week, but I trust
you folks to make the right decision. If I'm alone in my concern about
this, then we should go with rough consensus, which seems to be running
against me at the moment.

-Steve